ICMLMay, 2021

带有随机延迟的组合式封锁赌博机

PDF
TL;DR本文考虑了带障碍的多臂赌博机问题中，包含组合优化的情况下解决局部最优策略的方法。我们扩展了现有模型，使得多个手臂可以按照可行性约束同时进行决策。本文提出了一种自然的贪心算法，并针对其在多种情况下的表现给出了严格的理论保证。
发现论文，激发创造
  • 阻断赌徒

    考虑到重复使用某些选项可能是不可取的或不可行的，本文提出了一种新颖的随机多臂赌博机设置，并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法，但它设计了一种贪婪算法和一种基于 UCB 的算法，具有一定的优异性。

    Jul, 2019

  • 具有臂依赖性延迟的随机赌博机

    本文研究随机延迟赌博机问题，提出了一种基于 UCB 算法的简单但高效的算法 ——PatientBandits，通过针对延迟赋予限制的方法，得出不同类型问题的效果下限和上限。

    Jun, 2020

  • 上下文阻塞赌博机

    该论文研究了一种新的上下文多臂赌博问题，其中玩家在每个时间步观察独立采样的上下文，以确定每个臂的平均回报，但播放一个臂会在未来的一定时间步内阻止它。作者提出了基于 UCB 的算法来解决这个问题，同时介绍了延迟利用和机会抽样的概念。

    Mar, 2020

  • 具有不受限制的延迟分布的随机多臂赌博机

    该研究探讨具有随机延迟的随机多臂赌博问题，在考虑了奖励相关延迟和奖励无关延迟两种情况下，提出了接近最优的算法，并在延迟分布的分位数上增加了附加依赖性，而不需要假设延迟分布来自任何参数化的分布族，还允许无限延迟的情况。

    Jun, 2021

  • 组合多臂赌博机的紧密下界

    本研究探讨了组合多臂赌博的后悔下界，并证明了在所有光滑奖励函数下，这种下界都是合理的，并且根据 Merlis 和 Mannor（2019）提出的 Gini 加权平滑度参数确定单调奖励函数的下界。

    Feb, 2020

  • 已知协方差的组合半赌博算法

    介绍了一个基于线性回归的优化算法，用于解决组合随机半汉带问题中的依赖关系，分析证明其是最优的，并且推出了一个与被拉动手臂数的对数因子成比例的新的下界。

    Dec, 2016

  • 组合赌博机再审

    本文研究了随机和对抗性组合多臂赌博问题。在随机情况下，我们提出了一种特定问题的遗憾下限，并讨论了其与决策空间维数的比例关系。我们提出了 ESCB 算法，该算法能有效地利用问题的结构，并对其遗憾进行了有限时间分析。ESCB 具有比现有算法更好的性能保证，并在实践中显着优于这些算法。在对抗性情况下，我们提出了 CombEXP 算法，其遗憾比比现有最先进算法相同，但对于某些组合问题具有较低的计算复杂度。

    Feb, 2015

  • 组合多臂老虎机及其对概率触发臂的扩展

    该研究提出了一种通用的组合多臂赌博问题框架，将未知分布的基础臂组成超级臂进行玩耍，进一步探讨了更多可能基于已激发臂的结果触发概率的扩展，旨在通过在线学习算法实现最小化（α，β）- 逼近遗憾。

    Jul, 2014

  • 分散式随机多人多臂行走赌博机

    提出了一种解决多人多臂赌博机问题的分布式算法，利用上置信区间和分布式优化技术，解决了现实世界应用中玩家仅能访问动态局部子集的问题，并获得了接近最优的后悔率。

    Dec, 2022

  • 具有时延依赖收益的随机赌博机

    提出了一个非平稳随机 bandit 模型及其评估算法，对比了该算法和 UCB 方法的优越性，从而能够有效地解决音乐推荐中的问题。

    Oct, 2019