公平最优多智能体赌博机
本文在经典赌博机问题的基础上提出了一个多智能体变种,旨在学会对赌臂进行公平分配并利用纳什社会福利来衡量它的公平性,设计了三个多智能体变种的算法并证明其实现了次线性的损失纳什社会福利, 因此可以对合理的互惠性展现出更大的感受。
Jul, 2020
介绍了一个分布式算法来解决多臂赌博机问题,通过异步交换较少的比特数,在不进行样本交换的情况下,仅通过传递臂 ID 来维护代理之间的合作;文中提出的算法可以将每个代理的后悔最小化,并将通信复杂度降至 $O (logT)$,与不进行合作的方案相比,本算法能够显著降低每个代理的后悔。
Oct, 2019
本论文针对多人随机多臂老虎机问题中,玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置,并提出了一种新的有效算法,结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析,证明了该算法的次线性极大遗憾界,解决了 NeurIPS2018 的一个开放性问题。
Feb, 2019
研究通过交换信息在底层网络上通信的代理,以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法,其中保证每个代理 v 的期望遗憾都是(1+K/|N (v)|)^T 的平方根量级。
Jul, 2019
我们研究了在一个通用的协作多智能体多臂老虎机模型中的遗憾最小化问题,在该模型中,每个智能体面临一个有限的臂集,并可以通过一个中央控制器与其他智能体进行通信。该模型中每个智能体的最优臂是具有最大期望混合奖励的臂,其中每个臂的混合奖励是其在所有智能体之间的奖励的加权平均,这使得智能体之间的通信至关重要。尽管在这个协作模型下已知最优臂识别的近似复杂度,但最优遗憾问题仍然是开放的。在这项工作中,我们解决了这个问题,并提出了第一个在这个协作老虎机模型下具有最优遗憾界限的算法。此外,我们还展示了只需要一个小的常数期望通信轮数。
Dec, 2023
研究多人合作多智能体赌博问题,提出一种新的多人合作环境,并利用分散式演算法促进代理之间的合作,推导每个代理的累积遗憾度和群体的遗憾度上下限,并证明了该算法的近似最优行为。
May, 2023
该研究考虑了单人和多人多臂老虎机模型的学习问题,提出了两种可分散策略,即 E³ (立方) 和 E³-TS,它们显示出预期遗憾增长的上限为 O (log^(1+ε) T),并解决了分散的在线学习所产生的附加成本问题。
May, 2015
本文研究了一种分散式多臂搏击器的问题,提出了一种达到最优秩序并确保公平性的分散式政策,并证明了其总遗憾增长速率的下限,这个问题在认知无线电网络,多通道通信系统,多智能体系统,网络搜索和广告以及社交网络等领域有潜在的应用。
Oct, 2009
该论文研究了多智能体多臂赌博机模型下的协作问题,提出了两个算法,通过交换信息来降低每个智能体的累计损失,理论证明通过最小的信息交互次数可以在不增加损失上极大地提高算法性能。
Jan, 2020
在多臂赌博机领域,多智能体多臂赌博机方法已经受到了广泛关注,但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界,并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时,我们证明了实例相关上界的 O(log T)下界和平均差值独立上界的 sqrt(T)下界。在对抗奖励的假设下,我们建立了连接图的 O(T^(2/3))下界,从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时,我们还展示了线性的遗憾下界。与以前的研究相比,本文全面研究了这些情景下的紧密下界。
Aug, 2023