多智能体协作博弈中，个体后悔值不依赖通信图直径。
Individual Regret in Cooperative Stochastic Multi-Armed Bandits
- 设计改进的协同消除算法，实现个体后悔上界独立于图直径。
- 在对消息长度和通信轮次受限时，仍保持良好性能，最坏情况为 $O(R/m + A \log T)$。
- 适合研究分布式学习、多智能体系统及低通信开销场景的研究者。
我们研究了在任意连通通信图上多智能体协作的随机多臂老虎机问题。分析了一种改进的协同逐次消除算法（COOP-SE），并证明了个体后悔上界为 $O(R/m + A^2 + A \sqrt{\log T})$，且给出了近乎匹配的下界。其中 $A$ 为动作数，$T$ 为时间范围，$m$ 为智能体数，$R = \sum_{Δ_i > 0} \log(T)/Δ_i$ 为单智能体最优后悔值，$Δ_i$ 为动作 $i$ 的次优间隙。这是首个在协作随机多臂老虎机中获得与图直径无关的个体后悔上界的成果。此外，在限制消息大小为对数级的情况下，该上界依然成立；当通信轮次为对数级时，可得后悔上界为 $O(R/m + A \log T)$。
原文摘要 · Abstract (English)
We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We analyzed a variant of Cooperative Successive Elimination algorithm, COOP-SE, and show an individual regret bound of $O(R/ m + A^2 + A \sqrt{\log T})$ and a nearly matching lower bound. Here $A$ is the number of actions, $T$ the time horizon, $m$ the number of agents, and $R = \sum_{Δ_i > 0}\log(T)/Δ_i$ is the optimal single agent regret, where $Δ_i$ is the sub-optimality gap of action $i$. Our work is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter. When considering communication networks there are additional considerations beyond regret, such as message size and number of communication rounds. First, we show that our regret bound holds even if we restrict the messages to be of logarithmic size. Second, for logarithmic number of communication rounds, we obtain a regret bound of $O(R / m+A \log T)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。