多智能体在连续空间中实现无通信协作，高效分配高收益区域。
Multi-Agent Lipschitz Bandits
- 通过最大值导向搜索定位高价值区域，实现智能体自主分配。
- 集体后悔上界为$ ilde{O}(T^{(d+1)/(d+2)})$，逼近单智能体最优水平。
- 无需通信，适用于资源竞争场景，适合分布式决策系统研究者。
我们研究在连续、Lipschitz结构化动作空间中的去中心化多玩家随机老虎机问题，硬碰撞导致零奖励。目标是设计一种无通信策略，最大化集体奖励，并将协调成本与学习成本分离。提出模块化协议：首先通过新颖的最大值导向搜索识别并分配玩家至不同高价值区域，再将问题解耦为 $N$ 个独立的单智能体Lipschitz老虎机问题。在共识条件下，获得端到端后悔上界，主导学习项为 $ ilde{O}(T^{(d+1)/(d+2)})$，匹配单智能体最优率；前期协调成本在固定置信度下与时间无关，期望后悔形式下仅对数多项式依赖于 $T$。在额外公共覆盖/调度假设下，还获得无间隙 $ ilde{O}(T^{(d+1)/(d+2)})$ 保证。进一步推导出主导学习项的匹配下界，并将框架扩展至一般距离阈值碰撞模型。
原文摘要 · Abstract (English)
We study the decentralized multi-player stochastic bandit problem over a continuous, Lipschitz-structured action space where hard collisions yield zero reward. Our objective is to design a communication-free policy that maximizes collective reward, while separating coordination costs from learning costs. We propose a modular protocol that first solves the multi-agent coordination problem by identifying and seating players on distinct, high-value regions via a novel maxima-directed search and then decouples the problem into $N$ independent single-player Lipschitz bandits. In the consensus regime, we obtain an end-to-end regret bound whose dominant learning term is \(\tilde{O}(T^{(d+1)/(d+2)})\), matching the single-player Lipschitz rate; the upfront coordination cost is horizon-independent at fixed confidence and only polylogarithmic in \(T\) in the expected-regret form. Under an additional public coverage/scheduling assumption for the epochic extension, we also obtain a gap-free \(\tilde{O}(T^{(d+1)/(d+2)})\) guarantee. We further derive a matching lower bound for the dominant learning term and extend the framework to general distance-threshold collision models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。