该研究探讨了多人随机多臂赌博问题,其中玩家不能相互通信,且如果两个或两个以上的玩家拉动同一臂,就会发生碰撞并且涉及到的玩家将不会收到奖励,在此研究中,作者提出了两个反馈模型,即一种可以观察到碰撞是否发生和一种更难的模型,即没有碰撞信息。作者提出了一个算法可以实现对于后者的对数后悔度,以及一个不依赖于平均数之间差距的平方根后悔度型算法。对于前一模型,作者给出了第一个不依赖于差距的深度后悔度。基于这些想法,作者还提出了一种在随机反~协调博弈中快速达成近似纳什均衡的算法。
Aug, 2018
提出一种结合 epsilon-greedy 学习规则和避碰机制的算法,用于解决多用户共享多臂赌博问题,应用于认知无线电网络中,实验证明相比其他算法,该算法在此环境中可以显著提高性能,并取得次线性遗憾。
Apr, 2014
通过构建一种通信协议,使多个玩家之间出现冲突以便以极低成本共享信息的方式,我们提出了一种分散式算法,可实现与集中式一样的性能,以解决基于认知无线电网络的随机多人多臂赌博问题;当通信协议不能实现时,我们介绍了更适当的动态设置,并基于新算法证明了该模型仍可实现对数性后悔的增长。
Sep, 2018
本论文针对多人随机多臂老虎机问题中,玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置,并提出了一种新的有效算法,结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析,证明了该算法的次线性极大遗憾界,解决了 NeurIPS2018 的一个开放性问题。
Feb, 2019
研究了分散的随机多臂老虎机问题,在通过 Erdős-Rényi 图连接的多个玩家中,优化各自获得奖励的概率分布,推导了针对不同连接度的算法,利用累计遗憾值比较传统多臂老虎机算法和本研究。
Dec, 2017
设计了第一个能够在任意变化的环境中工作的多人赌博算法,其中武器的损失甚至可能是由对手选择的,同时解决了 Rosenski、Shamir 和 Szlak(2016 年)提出的一个悬而未决的问题。
提出了一种解决多人多臂赌博机问题的分布式算法,利用上置信区间和分布式优化技术,解决了现实世界应用中玩家仅能访问动态局部子集的问题,并获得了接近最优的后悔率。
Dec, 2022
在多人多臂老虎机(MPMAB)竞争模型中,我们提出了基于纳什均衡的自私 MPMAB 和平均分配(SMAA)策略,有效解决了自私玩家学习和最大化奖励的问题,并在理论和实验中证明其有效性和稳健性。
May, 2023
本文探讨了多层次反馈的多人多臂老虎机算法,并在不需要感知信息的情况下引入了一种被称为自私的有希望的启发式方法以适应与物联网网络的应用。研究结果显示,引入这些方法可以提高算法的性能并保证其渐近最优,降低拥堵的可能性。
Nov, 2017
本研究考虑了多个玩家之间,通过 Erdos-Renyi 图,以不同的通信概率下的去中心化随机多臂赌博问题,使用 UCB1、epsilon-Greedy 和 Thompson Sampling 算法探究了玩家之间的连接度对累计遗憾的影响。