ICMLNov, 2017

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

PDF
TL;DR本研究考虑了多个玩家之间，通过 Erdos-Renyi 图，以不同的通信概率下的去中心化随机多臂赌博问题，使用 UCB1、epsilon-Greedy 和 Thompson Sampling 算法探究了玩家之间的连接度对累计遗憾的影响。
decentralized stochasticmulti-armed banditcommunication probabilitiescumulative regreterdos-renyi graph
发现论文，激发创造
  • 一种渐近最优算法解决多人多臂老虎机问题

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

    Dec, 2017

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

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

    Sep, 2018

  • 更接近现实：带有不完美通信的协同 Bandit 算法

    本文探讨了协作强盗问题在现实世界通信环境下的三种典型情景，并提出了相应的去中心化算法来实现可比性能并且保证产生小组遗憾次数接近最优解，同时提出了对于完美通信情况下的改进算法，最后给出了群体遗憾的最紧密的网络相关极小极大下限。

    Nov, 2021

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

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

    Oct, 2019

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

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

    Aug, 2018

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

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

    Feb, 2020

  • 多人赌博机：对抗情形

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

    Feb, 2019

  • 多智能体赌博机的闲语插入 - 排除算法

    该论文研究了多智能体多臂赌博机模型下的协作问题，提出了两个算法，通过交换信息来降低每个智能体的累计损失，理论证明通过最小的信息交互次数可以在不增加损失上极大地提高算法性能。

    Jan, 2020

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

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

    Feb, 2019

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

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

    Dec, 2015