Feb, 2019

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

PDF
TL;DR本论文针对多人随机多臂老虎机问题中，玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置，并提出了一种新的有效算法，结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析，证明了该算法的次线性极大遗憾界，解决了 NeurIPS2018 的一个开放性问题。
multiplayer stochastic multi-armed banditforced collisionsmatching eliminationsminimax regret boundoptimization
发现论文，激发创造
  • 一种渐近最优算法解决多人多臂老虎机问题

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

    Dec, 2017

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

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

    Aug, 2018

  • SIC-MMAB: 多人多臂赌博机中涉及通讯的同步

    通过构建一种通信协议，使多个玩家之间出现冲突以便以极低成本共享信息的方式，我们提出了一种分散式算法，可实现与集中式一样的性能，以解决基于认知无线电网络的随机多人多臂赌博问题；当通信协议不能实现时，我们介绍了更适当的动态设置，并基于新算法证明了该模型仍可实现对数性后悔的增长。

    Sep, 2018

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

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

    Dec, 2015

  • 多人赌博机：对抗情形

    设计了第一个能够在任意变化的环境中工作的多人赌博算法，其中武器的损失甚至可能是由对手选择的，同时解决了 Rosenski、Shamir 和 Szlak（2016 年）提出的一个悬而未决的问题。

    Feb, 2019

  • 多人赌博机中的自私鲁棒性和均衡

    研究了利用自我私利游戏玩家的多臂赌博机问题，提出了一种能够实现对恶意玩家具有鲁棒性的算法，并构建了两个不同设置下的鲁棒算法，其中一种包括隐式通信的算法，同时针对只能观察奖励或手臂平均值任意变化的情况进行了研究。

    Feb, 2020

  • 公平最优多智能体赌博机

    研究多智能体多臂赌博学习问题，以无通信和有限奖励为前提，提出了一种分布式拍卖算法并进行样本最优匹配学习和新的拍卖决策策略，通过新颖的基于次序统计量的后悔分析带来了全新的性能，实验模拟表明性能依赖于对数时间。

    Jun, 2023

  • 多智能体多臂赌博机中的社交学习

    介绍了一个分布式算法来解决多臂赌博机问题，通过异步交换较少的比特数，在不进行样本交换的情况下，仅通过传递臂 ID 来维护代理之间的合作；文中提出的算法可以将每个代理的后悔最小化，并将通信复杂度降至 $O (logT)$，与不进行合作的方案相比，本算法能够显著降低每个代理的后悔。

    Oct, 2019

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

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

    Apr, 2019

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

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

    Dec, 2022