arXiv:2502.16128cs.LGcs.AI2025-02AAAI被引 2

让多个智能体用最少提示高效协作,实现稳定高收益。

Heterogeneous Multi-Agent Bandits with Parsimonious Hints

  • 引入低代价提示机制,减少重复抢夺动作
  • 中心化算法仅需约MK log T次提示,实现固定时间误差
  • 去中心化方案无需全局协调,适合实际部署

我们研究了一种带有提示的异构多智能体多臂赌博机问题(HMA2B),其中智能体可查询低成本观测(提示)以补充拉杆动作。在该框架中,共M个智能体面对K个动作,每个智能体有独立的奖励分布;在T轮中,只有当无其他智能体选择同一动作时,才能观测到其奖励。目标是在最小化提示次数的前提下,最大化总收益并实现与时间无关的后悔值。本文分别设计了中心化与去中心化算法:中心化算法GP-HCLA基于扩展的HCLA,通过中央决策者协调动作与提示,实现O(M⁴K)后悔值,仅需O(MK log T)次自适应提示;去中心化算法HD-ETC与EBHD-ETC通过碰撞通信机制使智能体独立决策,在停止前均匀查询提示,分别实现O(M³K²)后悔值与O(M³K log T)提示,前者需已知最小奖励差距,后者无需。最后建立下界证明结果最优性,并通过数值模拟验证。

原文摘要 · Abstract (English)

We study a hinted heterogeneous multi-agent multi-armed bandits problem (HMA2B), where agents can query low-cost observations (hints) in addition to pulling arms. In this framework, each of the $M$ agents has a unique reward distribution over $K$ arms, and in $T$ rounds, they can observe the reward of the arm they pull only if no other agent pulls that arm. The goal is to maximize the total utility by querying the minimal necessary hints without pulling arms, achieving time-independent regret. We study HMA2B in both centralized and decentralized setups. Our main centralized algorithm, GP-HCLA, which is an extension of HCLA, uses a central decision-maker for arm-pulling and hint queries, achieving $O(M^4K)$ regret with $O(MK\log T)$ adaptive hints. In decentralized setups, we propose two algorithms, HD-ETC and EBHD-ETC, that allow agents to choose actions independently through collision-based communication and query hints uniformly until stopping, yielding $O(M^3K^2)$ regret with $O(M^3K\log T)$ hints, where the former requires knowledge of the minimum gap and the latter does not. Finally, we establish lower bounds to prove the optimality of our results and verify them through numerical simulations.

多智能体博弈优化提示学习强化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。