通信对非合作式多玩家多臂赌博问题的影响
该研究考虑了单人和多人多臂老虎机模型的学习问题,提出了两种可分散策略,即E³ (立方)和E³-TS,它们显示出预期遗憾增长的上限为O(log^(1+ε)T),并解决了分散的在线学习所产生的附加成本问题。
May, 2015
本研究提出了两种无需通信的算法Musical Chairs和Dynamic Musical Chairs来解决多人博弈中的多臂赌博机问题,其中玩家可能发生碰撞,但不会获得奖励。这些算法有着恒定和次线性的遗憾率,且不需要先验知识,为这类问题解决提供了理论保证。
Dec, 2015
研究了分散的随机多臂老虎机问题,在通过Erdős-Rényi图连接的多个玩家中,优化各自获得奖励的概率分布,推导了针对不同连接度的算法,利用累计遗憾值比较传统多臂老虎机算法和本研究。
Dec, 2017
该研究探讨了多人随机多臂赌博问题,其中玩家不能相互通信,且如果两个或两个以上的玩家拉动同一臂,就会发生碰撞并且涉及到的玩家将不会收到奖励,在此研究中,作者提出了两个反馈模型,即一种可以观察到碰撞是否发生和一种更难的模型,即没有碰撞信息。作者提出了一个算法可以实现对于后者的对数后悔度,以及一个不依赖于平均数之间差距的平方根后悔度型算法。对于前一模型,作者给出了第一个不依赖于差距的深度后悔度。基于这些想法,作者还提出了一种在随机反~协调博弈中快速达成近似纳什均衡的算法。
Aug, 2018
通过构建一种通信协议,使多个玩家之间出现冲突以便以极低成本共享信息的方式,我们提出了一种分散式算法,可实现与集中式一样的性能,以解决基于认知无线电网络的随机多人多臂赌博问题;当通信协议不能实现时,我们介绍了更适当的动态设置,并基于新算法证明了该模型仍可实现对数性后悔的增长。
Sep, 2018
本文研究了多臂赌博机问题在网络上的去中心化协作,采用加速一致性过程来计算所有智能体对每个臂的平均奖励,该算法采用上置信区间来决策,能够达到更好的回归界,同时不需要过多的底层网络信息。
Oct, 2018
本论文针对多人随机多臂老虎机问题中,玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置,并提出了一种新的有效算法,结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析,证明了该算法的次线性极大遗憾界,解决了NeurIPS2018的一个开放性问题。
Feb, 2019
对于(协作式)多人多臂老虎机问题的非随机版本,我们证明了第一个O(√T)-类型的遗憾保证,即使在没有通讯且选择相同行动的情况下也有最大的损失。在反馈模型中,即使对于简单的随机版本,此类约束尚未知。此外,我们还证明了在无冲突信息的情况下反馈模型的第一个亚线性保证,即T ^(1-1 /(2m)),其中m是玩家数量。
Apr, 2019
研究通过交换信息在底层网络上通信的代理,以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法,其中保证每个代理v的期望遗憾都是(1+K/|N(v)|)^T的平方根量级。
Jul, 2019
介绍了一个分布式算法来解决多臂赌博机问题,通过异步交换较少的比特数,在不进行样本交换的情况下,仅通过传递臂ID来维护代理之间的合作;文中提出的算法可以将每个代理的后悔最小化,并将通信复杂度降至$O(logT)$,与不进行合作的方案相比,本算法能够显著降低每个代理的后悔。
Oct, 2019