提出高效分布式算法，解决多智能体竞态带子问题。
Distributed Algorithms for Multi-Agent Multi-Armed Bandits with Collision
- 设计自适应通信协议，仅需双对数级通信开销
- 实现近最优群体与个体遗憾，显著降低单个智能体损失
- 适用于无中心协调的异步场景，适合大规模多智能体系统
研究随机多玩家多臂老虎机（MMAB）问题，多个智能体选择臂以最大化累积奖励。当两个或以上智能体选择同一臂时发生碰撞，导致无奖励，且参与碰撞的智能体可感知。在无中心协调的分布式设置下，每个智能体仅能观测自身动作和碰撞反馈。提出一种具有自适应高效通信协议的分布式算法，实现近似最优的群体与个体遗憾，通信成本仅为 $\mathcal{O}(\log\log T)$。实验表明，相比现有最优方法，该方案在个体遗憾上显著降低。进一步将方法扩展至周期性异步设置，证明该问题的下界，并提出达到对数遗憾的算法。
原文摘要 · Abstract (English)
We study the stochastic Multiplayer Multi-Armed Bandit (MMAB) problem, where multiple players select arms to maximize their cumulative rewards. Collisions occur when two or more players select the same arm, resulting in no reward, and are observed by the players involved. We consider a distributed setting without central coordination, where each player can only observe their own actions and collision feedback. We propose a distributed algorithm with an adaptive, efficient communication protocol. The algorithm achieves near-optimal group and individual regret, with a communication cost of only $\mathcal{O}(\log\log T)$. Our experiments demonstrate significant performance improvements over existing baselines. Compared to state-of-the-art (SOTA) methods, our approach achieves a notable reduction in individual regret. Finally, we extend our approach to a periodic asynchronous setting, proving the lower bound for this problem and presenting an algorithm that achieves logarithmic regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。