May, 2024

非精确多臂赌博机

PDF
TL;DR我们引入了一种新颖的多臂赌博问题框架，其中每个臂与一个固定的未知置信集相关联，覆盖了结果空间（可以比奖励更丰富）。臂 - 置信集对应关系来自已知的假设类。我们定义了一种与这些置信集定义的下概率相对应的遗憾概念。等价地，这个设置可以被视为一个两人零和博弈，其中在每一轮中，代理选择一个臂，对手从与该臂相关联的选择集中选择结果分布。遗憾是相对于游戏价值定义的。对于某些自然的假设类，这些类类似于随机线性赌博问题（是结果设置的特殊情况），我们提出了一个算法并证明了遗憾的上界。我们还证明了特定特殊情况下的遗憾下界。
multi-armed bandit frameworkcredal setregrettwo-player zero-sum gameupper bound on regret
发现论文，激发创造
  • 有限臂结构赌博机的有界遗憾

    研究了一种新型的 K 武装强盗问题，介绍了一种针对这一问题的新算法，并展示了在特定条件下可以实现有限的预期累计遗憾，同时提供了依赖于问题的累计遗憾下限，显示出至少在某些特殊情况下，新算法是近乎最优的。

    Nov, 2014

  • 多种最佳臂的遗憾问题

    本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题，通过提出自适应算法来自动适应问题的难度，并在理论和实验方面展现了该算法的优越性。

    Jun, 2020

  • 多臂赌博问题的纯探索

    研究随机多臂老虎机问题的性质和限制，探讨具有在线探索特性的预测器的表现，其中简单后悔被评估，讨论简单后悔与累计后悔的关系，在有限臂数的情况下展示了一种性能下限和预测器的上限后悔，并针对连续老虎臂问题进行了研究。

    Feb, 2008

  • 带有未知变量的组合网络优化：具有线性回报的多臂赌博机

    本文提出了一种适用于多臂赌博机问题的解决方案，只需要以线性时间复杂度存储未知参数，可以处理一般的掌握参数相关性的问题，并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。

    Nov, 2010

  • 无限臂老虎机的简单遗憾

    本文针对无穷臂随机赌博机问题，提出一种算法用以最小化简单损失，并扩展到多种情况下，如未知时间跨度等。

    May, 2015

  • 对抗性赌博机的改进下界

    该研究提供了敌对强盗算法必须遭受的遗憾的新的下界，并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外，研究还证明了两个不可能的结果，即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下，在完全信息设置中这两个结果是可能的。

    May, 2016

  • 稀疏随机赌博机

    本文研究了经典多臂老虎机问题的稀疏情况，并提出了一种算法，其遗憾值与臂数的正比例关系被缩小至仅与正收益臂数相同，同时证明了其最优性。

    Jun, 2017

  • 恢复强盗

    研究回收匪徒问题，使用高斯过程解决估计和规划问题，包括悔恨界限和计算效率的讨论。

    Oct, 2019

  • 协作多智体异构多臂赌博机

    研究多人合作多智能体赌博问题，提出一种新的多人合作环境，并利用分散式演算法促进代理之间的合作，推导每个代理的累积遗憾度和群体的遗憾度上下限，并证明了该算法的近似最优行为。

    May, 2023

  • 对抗性贝叶斯强化学习的对抗攻击

    在对抗式多臂赌博机中，攻击者通过攻击策略干扰损失或奖励信号，以实现对受害者赌徒玩家的行为控制。我们向攻击者显示，攻击者能够引导任何无憾对抗性赌博算法，在每轮之外的几乎所有轮次中选择次优目标臂，而仅产生次线性的攻击成本。这个结果意味着在现实世界中，基于赌博机的系统中存在重要的安全问题，例如，在线推荐中，攻击者可能能够劫持推荐系统并推广所需的产品。我们提出的攻击算法只需要了解后悔率，因此对受害方使用的具体赌博算法没有任何限制。此外，我们还推导了任何受害者不可知攻击算法必须产生的理论下限，并与我们的攻击产生的上限匹配，这表明我们的攻击在渐近意义下是最优的。

    Jan, 2023