Aug, 2023

合作多智能体赌博机：优化个体懊悔并具有恒定通讯开销的分布式算法

PDF
TL;DR合作多智能体多臂赌博算法中的通信策略，既实现了最优个体遗憾，又具有恒定的通信成本。
cooperative multi-agent multi-armed banditsbandit algorithmscommunication policyleader-followerfully distributed algorithms
发现论文，激发创造
  • 合作非随机多臂老虎机中的个体遗憾

    研究通过交换信息在底层网络上通信的代理，以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法，其中保证每个代理 v 的期望遗憾都是（1+K/|N (v)|)^T 的平方根量级。

    Jul, 2019

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

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

    Oct, 2019

  • 博弈中协作学习的最优遗憾界

    我们研究了在一个通用的协作多智能体多臂老虎机模型中的遗憾最小化问题，在该模型中，每个智能体面临一个有限的臂集，并可以通过一个中央控制器与其他智能体进行通信。该模型中每个智能体的最优臂是具有最大期望混合奖励的臂，其中每个臂的混合奖励是其在所有智能体之间的奖励的加权平均，这使得智能体之间的通信至关重要。尽管在这个协作模型下已知最优臂识别的近似复杂度，但最优遗憾问题仍然是开放的。在这项工作中，我们解决了这个问题，并提出了第一个在这个协作老虎机模型下具有最优遗憾界限的算法。此外，我们还展示了只需要一个小的常数期望通信轮数。

    Dec, 2023

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

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

    Jan, 2020

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

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

    Nov, 2021

  • 多臂赌博机中的分布式协作决策：频率学派和贝叶斯算法

    本研究使用频率学派和贝叶斯算法以及运行协商算法解决多智能体多臂赌博机问题中的探索和开发的分布式合作决策问题，并证明了这些算法的性能，以及通信图结构对决策性能的影响。

    Jun, 2016

  • 协作多智体异构多臂赌博机

    研究多人合作多智能体赌博问题，提出一种新的多人合作环境，并利用分散式演算法促进代理之间的合作，推导每个代理的累积遗憾度和群体的遗憾度上下限，并证明了该算法的近似最优行为。

    May, 2023

  • 去中心化协作随机赌博机

    本文研究了多臂赌博机问题在网络上的去中心化协作，采用加速一致性过程来计算所有智能体对每个臂的平均奖励，该算法采用上置信区间来决策，能够达到更好的回归界，同时不需要过多的底层网络信息。

    Oct, 2018

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

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

    Jun, 2023

  • 社交网络上随机赌博机的协同学习

    本文研究了协作在线学习的方法，特别关注于使用多臂老虎机游戏对社交网络中的一组代理进行协作的情况，并对其使用的不同算法进行了遗憾分析。我们发现，单个代理学习策略的自然扩展在网络设置下表现不佳，我们提出了一类策略，并证明其在网络环境中容易遭受大量遗憾。同时，我们也提出了基于网络结构的学习算法，并在拥有不同拓扑结构的网络上进行了实验。

    Feb, 2016