将单智能体算法通用化为多智能体协作的最优动作选择方法
QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits
- 提出黑箱转换框架，任意单智能体算法可无缝扩展到多智能体场景
- 在亚高斯环境下，多智能体遗憾上界与单智能体近似最优，仅差图相关常数
- 适用于重尾、对抗性、隐私保护等多种复杂设定，适合研究多智能体强化学习者
我们研究合作式随机k臂赌博机问题，即由m个智能体组成的网络协同寻找最优动作。与以往工作不同，我们提供一种黑箱归约方法，可将任意单智能体赌博机算法扩展至多智能体设置。在对赌博机环境的温和假设下，证明该归约能将单智能体算法的遗憾保证转移至多智能体场景。这些保证在亚高斯环境中是紧致的：使用近最小最大最优的单智能体算法时，多智能体设置下的性能也近似最小最大最优，仅相差一个图相关的加性项。该归约和理论结果具有普遍性，适用于多种赌博机设置。通过接入合适的单智能体算法，可轻松构造出许多多智能体场景下的可证明高效的算法，如重尾赌博机、对决赌博机、带局部差分隐私的赌博机等。实验表明，该方法在性能上可媲美或优于专用的多智能体算法。
原文摘要 · Abstract (English)
We study the cooperative stochastic $k$-armed bandit problem, where a network of $m$ agents collaborate to find the optimal action. In contrast to most prior work on this problem, which focuses on extending a specific algorithm to the multi-agent setting, we provide a black-box reduction that allows us to extend any single-agent bandit algorithm to the multi-agent setting. Under mild assumptions on the bandit environment, we prove that our reduction transfers the regret guarantees of the single-agent algorithm to the multi-agent setting. These guarantees are tight in subgaussian environments, in that using a near minimax optimal single-player algorithm is near minimax optimal in the multi-player setting up to an additive graph-dependent quantity. Our reduction and theoretical results are also general, and apply to many different bandit settings. By plugging in appropriate single-player algorithms, we can easily develop provably efficient algorithms for many multi-player settings such as heavy-tailed bandits, duelling bandits and bandits with local differential privacy, among others. Experimentally, our approach is competitive with or outperforms specialised multi-agent algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。