多臂赌博机中的可复制性是渐进自由的
内容提要
本文综述多臂赌博机研究进展，涵盖不可重复选项的随机设置、PINWHEEL调度、分散式多玩家问题、隐式探索损失估计、K臂转C+1臂框架、无穷臂随机赌博机、分段稳定赌博、多人异质碰撞场景、Feedback MAB双重算法、无贝叶斯假设方法及预算约束拓展。
延伸解读
不可重复选项带来的计算挑战
文章指出，当某些选项不可重复使用时，优化累积奖励问题被映射到PINWHEEL调度问题，并证明不存在伪多项式时间算法。这意味着该问题在计算上可能非常困难，读者需注意其复杂性。作者为此设计了贪婪算法和基于UCB的算法，这些算法在特定条件下表现出优异性，但并非通用最优解。
分散式多玩家与异质碰撞场景
在分散式随机多臂老虎机中，多个玩家通过Erdős-Rényi图连接，各自优化奖励概率分布。针对玩家无法通信且碰撞得零分的异质设置，文章提出结合强制碰撞隐式通信和匹配消除的算法，并证明其具有次线性遗憾界，解决了NeurIPS 2018的开放性问题。这为多智能体决策提供了理论工具。
算法框架与近似技术
文章涵盖多个算法创新：将K臂问题转化为C+1臂框架以降低遗憾；基于隐式探索的损失估计策略实现高概率遗憾界；针对Feedback MAB的双重算法技术，为1+ε解提供2+ε近似，并适用于喧闹强盗和POMDP。这些方法在特定场景下提升了性能，但需注意其近似保证和适用条件。
无贝叶斯假设与预算约束拓展
对于无贝叶斯假设的多臂老虎机，文章提出元策略学习方法，在马尔可夫链参数未知时学习最优策略，并在机会式频谱访问中取得接近对数级的损失值。此外，预算约束下的拓展给出了UCB和Exp3的具体实现及性能分析。这些工作扩展了多臂老虎机在现实约束下的应用范围。
Q&A
多臂赌博机中不可重复选项的随机设置有什么特点？
该设置考虑到重复使用某些选项可能是不可取的或不可行的，通过映射到PINWHEEL调度问题，证明了优化累积奖励不允许有伪多项式时间算法，但设计了贪婪算法和基于UCB的算法，具有一定的优异性。
分散式多玩家多臂老虎机问题是如何解决的？
在通过Erdős-Rényi图连接的多个玩家中，优化各自获得奖励的概率分布，推导了针对不同连接度的算法，并利用累计遗憾值比较传统多臂老虎机算法和本研究。
如何将K臂赌博机问题转化为C+1臂问题？
该论文提出了一种新的多臂赌博机框架，在该框架下将K-armed bandit问题转化为C+1-armed问题。通过利用该框架下的广义上限置信区间算法可以降低算法的遗憾量，以实现一定的算法性能优势。
无穷臂随机赌博机问题有哪些算法进展？
本文针对无穷臂随机赌博机问题，提出一种算法用以最小化简单损失，并扩展到多种情况下，如未知时间跨度等。
多人异质碰撞场景下的多臂老虎机问题如何解决？
针对玩家无法通信且产生碰撞时得分为零的情形，解决了不同玩家可能具有不同的均值的异质设置，并提出了一种新的有效算法，结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析，证明了该算法的次线性极大遗憾界，解决了NeurIPS2018的一个开放性问题。
Feedback MAB问题为什么不能用贪心指数算法求解？
讨论了一种无法使用贪心指数算法求解的Feedback MAB问题，开发出了一种新颖并且通用的双重算法技术，可为不少于1+epsilon的解提供2+epsilon的近似值，这个技术同样适用于其他不特定的喧闹强盗问题和POMDP。
