Apr, 2019

非随机多人多臂老虎机：有碰撞信息时达到最优速率，无碰撞信息时次线性

HTML
PDF
TL;DR对于（协作式）多人多臂老虎机问题的非随机版本，我们证明了第一个O(√T)-类型的遗憾保证，即使在没有通讯且选择相同行动的情况下也有最大的损失。在反馈模型中，即使对于简单的随机版本，此类约束尚未知。此外，我们还证明了在无冲突信息的情况下反馈模型的第一个亚线性保证，即T ^（1-1 /（2m）），其中m是玩家数量。
发现论文，激发创造
  • 多人多臂赌博机的分布式学习

    本文研究了一种分散式多臂搏击器的问题，提出了一种达到最优秩序并确保公平性的分散式政策，并证明了其总遗憾增长速率的下限，这个问题在认知无线电网络，多通道通信系统，多智能体系统，网络搜索和广告以及社交网络等领域有潜在的应用。

    Oct, 2009

  • 分散式多人多臂搶錢機中的遺憾最小學習

    该研究考虑了单人和多人多臂老虎机模型的学习问题，提出了两种可分散策略，即E³ (立方)和E³-TS，它们显示出预期遗憾增长的上限为O(log^(1+ε)T)，并解决了分散的在线学习所产生的附加成本问题。

    May, 2015

  • 多人博弈 -- 音乐椅子方法

    本研究提出了两种无需通信的算法Musical Chairs和Dynamic Musical Chairs来解决多人博弈中的多臂赌博机问题，其中玩家可能发生碰撞，但不会获得奖励。这些算法有着恒定和次线性的遗憾率，且不需要先验知识，为这类问题解决提供了理论保证。

    Dec, 2015

  • 通信对非合作式多玩家多臂赌博问题的影响

    本研究考虑了多个玩家之间，通过Erdos-Renyi图，以不同的通信概率下的去中心化随机多臂赌博问题，使用UCB1、epsilon-Greedy和Thompson Sampling算法探究了玩家之间的连接度对累计遗憾的影响。

    Nov, 2017

  • 一种渐近最优算法解决多人多臂老虎机问题

    研究了分散的随机多臂老虎机问题，在通过Erdős-Rényi图连接的多个玩家中，优化各自获得奖励的概率分布，推导了针对不同连接度的算法，利用累计遗憾值比较传统多臂老虎机算法和本研究。

    Dec, 2017

  • 不观测冲突信息的多人赌博机

    该研究探讨了多人随机多臂赌博问题，其中玩家不能相互通信，且如果两个或两个以上的玩家拉动同一臂，就会发生碰撞并且涉及到的玩家将不会收到奖励，在此研究中，作者提出了两个反馈模型，即一种可以观察到碰撞是否发生和一种更难的模型，即没有碰撞信息。作者提出了一个算法可以实现对于后者的对数后悔度，以及一个不依赖于平均数之间差距的平方根后悔度型算法。对于前一模型，作者给出了第一个不依赖于差距的深度后悔度。基于这些想法，作者还提出了一种在随机反~协调博弈中快速达成近似纳什均衡的算法。

    Aug, 2018

  • 多人赌博机问题：一种追踪方法

    本文研究了具有许多玩家的随机多臂老虎机。结果表明我们提出的一种新的“徒步旅行策略”不需要估计玩家的数量，同时保证了静态情况下常数风险和动态情况下高概率的子线性风险表现。我们还证明了我们的算法的有效性。

    Sep, 2018

  • 针对玩家武器平均值不同时的多人老虎机实用算法

    本论文针对多人随机多臂老虎机问题中，玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置，并提出了一种新的有效算法，结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析，证明了该算法的次线性极大遗憾界，解决了NeurIPS2018的一个开放性问题。

    Feb, 2019

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

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

    Dec, 2022

  • 无噪音奖励和无通信的最佳合作多人学习赌博机

    合作多人奖励学习中，通信受限的策略选择问题；通过使用上界和下界置信度算法，解决信息不对称导致的动作选择问题，并达到对数和平方根极限遗憾值。

    Nov, 2023