提出分布式对抗性博弈的近优解法，通信与学习代价分离。
Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach
- 通过延迟反馈黑箱转换设计新算法，仅需随机对讲通信
- 首次实现近最优后悔界 √(ρ⁻¹/² + K/N)T，优于前人结果
- 适用于多智能体协作场景，尤其适合低通信成本需求
研究分布式对抗性多臂赌博机问题：N个智能体协作以最小化全局平均损失，但仅能观测自身局部损失。我们证明该问题的极小极大后悔界为˜Θ(√((ρ⁻¹/² + K/N)T))，其中T为时长，K为动作数，ρ为通信矩阵的谱隙。所提算法基于新颖的黑箱归约至延迟反馈多臂赌博机，仅通过消息传播（gossip）通信，达到上界，显著优于此前最优的˜O(ρ⁻¹/³ (KT)²/³)。同时给出匹配下界，揭示问题难度由通信成本ρ⁻¹/⁴√T和博弈成本√(KT/N)组成。进一步拓展至分布式线性赌博机（ℝᵈ），获得˜O(√((ρ⁻¹/² + 1/N)dT))的后悔界，每轮每智能体仅需O(d)通信开销，利用体积支撑集实现。
原文摘要 · Abstract (English)
We study distributed adversarial bandits, where $N$ agents cooperate to minimize the global average loss while observing only their own local losses. We show that the minimax regret for this problem is $\tildeΘ(\sqrt{(ρ^{-1/2}+K/N)T})$, where $T$ is the horizon, $K$ is the number of actions, and $ρ$ is the spectral gap of the communication matrix. Our algorithm, based on a novel black-box reduction to bandits with delayed feedback, requires agents to communicate only through gossip. It achieves an upper bound that significantly improves over the previous best bound $\tilde{O}(ρ^{-1/3}(KT)^{2/3})$ of Yi and Vojnovic (2023). We complement this result with a matching lower bound, showing that the problem's difficulty decomposes into a communication cost $ρ^{-1/4}\sqrt{T}$ and a bandit cost $\sqrt{KT/N}$. We further demonstrate the versatility of our approach by deriving first-order and best-of-both-worlds bounds in the distributed adversarial setting. Finally, we extend our framework to distributed linear bandits in $R^d$, obtaining a regret bound of $\tilde{O}(\sqrt{(ρ^{-1/2}+1/N)dT})$, achieved with only $O(d)$ communication cost per agent and per round via a volumetric spanner.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。