Meta

Tag: #articles/tags/Computer_Science__Machine_Learning, #articles/tags//unread, #articles/tags/bandit/prob/distributed
citekey: zhouDistributedAlgorithmsMultiAgent2025
authors: #articles/authors/Daoyuan-Zhou, #articles/authors/Xuchuang-Wang, #articles/authors/Lin-Yang, #articles/authors/Yang-Gao
year: 2025/10/08
doi: 10.48550/arXiv.2510.06683
url: http://arxiv.org/abs/2510.06683
conference: #articles/conference/
Journal : #articles/journals/

Abstract

We study the stochastic Multiplayer Multi-Armed Bandit (MMAB) problem, where multiple players select arms to maximize their cumulative rewards. Collisions occur when two or more players select the same arm, resulting in no reward, and are observed by the players involved. We consider a distributed setting without central coordination, where each player can only observe their own actions and collision feedback. We propose a distributed algorithm with an adaptive, efficient communication protocol. The algorithm achieves near-optimal group and individual regret, with a communication cost of only O(log⁡log⁡T)\mathcal{O}(\log\log T). Our experiments demonstrate significant performance improvements over existing baselines. Compared to state-of-the-art (SOTA) methods, our approach achieves a notable reduction in individual regret. Finally, we extend our approach to a periodic asynchronous setting, proving the lower bound for this problem and presenting an algorithm that achieves logarithmic regret.

Note

1. key concept

Concept Meaning in MMAB Key Assumption Practical Effect Contrast
Centralized A single controller/coordinator decides arm assignments for players Global information or enough shared information is available to one decision maker (outside the system) Easier coordination, fewer collisions, simpler handling of arrivals/delays Decentralized: each player decides independently using local observations
Synchronized All players act on a shared global round/clock Players choose arms at the same round indices and often receive feedback together Phase-based coordination is easier; many algorithms rely on common timing Asynchronous: players act or start at different times, with misaligned updates
Homogeneous Reward statistics of each arm are the same for every player Arm kk has one common mean μkμ_k for all players Goal is to place players on different arms among the top MM arms Heterogeneous: reward depends on both player and arm, e.g. μi,kμ_{i,k}

Quick intuition

  • Centralized asks: who makes the decisions?
  • Synchronized asks: are players aligned in time?
  • Homogeneous asks: are rewards the same across players for a given arm?

3. Notation

  1. μ(1)>μ(2)>⋅⋅⋅>μ(K)μ(1) > μ(2) > · · · > μ(K) : 分别代表着K个arm的排序
  2. E[R(T)]=T∑k=1Mμ(k)−Eμ[∑t=1T∑m∈Mrt(m)],\mathbb{E}[R(T)] = T \sum_{k=1}^{M} \mu^{(k)} - \mathbb{E}_{\mu}\left[\sum_{t=1}^{T} \sum_{m \in \mathcal{M}} r_t^{(m)}\right], 这里是Regret, 与single agent不同的是这里所考虑的agent是前MM个reward mean
  3. Rind(T):=max⁡m∈MEμ[Tμ∗−∑t=1Trt(m)],R_{\mathrm{ind}}(T) := \max_{m \in \mathcal{M}} \mathbb{E}_{\mu}\left[T \mu^{*} - \sum_{t=1}^{T} r_t^{(m)}\right],

4. Algorithm 1

img

  1. 对于explore部分的探索步骤应该改为Kt[((p+cycle∗Mt−(j+M−Mt)mod  M)mod  M)mod  Kt]\mathcal{K}_t[\big((p+cycle*M_t-(j+M-M_t) \mod M) \mod M\big)\mod K_t]
    img
  2. 对于每个arm,
    • 如果是ACC那么这些轮后将被sample KtK_t 次
    • 如果是待选的, 则将被sample MtM_t 次, 因为每个arm的采样是均匀的, 并且一共采样了 Kt×MtK_t \times M_t次

lemma4 : confidence interval => lemma5

思路

  1. 从置信区间推导出每个arm的最长存活时间, 和UCB的推导是相似的,
  2. 注意这里有一个隐藏的条件, 就是所有的arm是被均匀地pull的, 所以所有arm的confidence Radius是相同的.
intuitively, 你可以反过来看, 也就是estimated reward mean是不会偏离true mean 太多(CR)的, 所以在sorted的情况下是可以通过比较最大次优臂的UCB来断言超过其他的次优臂UCB

lemma5 : 严格的数学证明：为什么“越过第 M+1M+1 臂”等于“越过所有次优臂”？

^ed39c3
我们回到 Lemma 5 的大前提——“好事件（Good Event）” 发生。
好事件的定义是：对于所有摇臂 xx（无论最优还是次优），其真实的期望均值 μ(x)\mu(x) 都被牢牢地锁在它的置信区间内。即：

LCB(x)≤μ(x)≤UCB(x)LCB(x) \le \mu(x) \le UCB(x)

这也等价于：

  • LCB(x)=μ^(x)−R≥μ(x)−2RLCB(x) = \hat{\mu}(x) - R \ge \mu(x) - 2R
  • UCB(x)=μ^(x)+R≤μ(x)+2RUCB(x) = \hat{\mu}(x) + R \le \mu(x) + 2R

(注：因为均匀拉杆，所有活跃臂的置信半径 RR 相同)。

现在，假设最优臂 kk 已经满足了我们在上一个回答中推导出的界限，即：

4R≤Δ(k)=μ(k)−μ(M+1)4R \le \Delta(k) = \mu(k) - \mu(M+1)

这意味着置信半径 RR 已经缩小到了：2R≤μ(k)−μ(M+1)22R \le \frac{\mu(k) - \mu(M+1)}{2}。

接下来，我们来看看在这个时刻，最优臂 kk 的下界与任意一个次优臂 ii (i≥M+1i \ge M+1) 的上界，到底是什么关系。

第一步：压低最优臂 kk 的下界 (LCB)

根据好事件，臂 kk 的 LCB 满足：

LCB(k)≥μ(k)−2RLCB(k) \ge \mu(k) - 2R

把刚才的 2R2R 的上限代入：

LCB(k)≥μ(k)−μ(k)−μ(M+1)2LCB(k) \ge \mu(k) - \frac{\mu(k) - \mu(M+1)}{2}

化简得到：

LCB(k)≥μ(k)+μ(M+1)2LCB(k) \ge \frac{\mu(k) + \mu(M+1)}{2}

物理意义：臂 kk 的 LCB 最惨最惨，也不会跌破它和最好次优臂之间的“均值中点”。

第二步：抬高任意次优臂 ii 的上界 (UCB)

现在随便挑一个次优臂 ii（注意：这里 ii 可以是 M+1,M+2,…,KM+1, M+2, \dots, K 中的任意一个）。
根据好事件，臂 ii 的 UCB 满足：

UCB(i)≤μ(i)+2RUCB(i) \le \mu(i) + 2R

因为 ii 是次优臂，它真实的均值 μ(i)\mu(i) 绝对不可能超过最好的次优臂 μ(M+1)\mu(M+1)（这是非随机的、客观存在的真值排序）。所以：

UCB(i)≤μ(M+1)+2RUCB(i) \le \mu(M+1) + 2R

再次把 2R2R 的上限代入：

UCB(i)≤μ(M+1)+μ(k)−μ(M+1)2UCB(i) \le \mu(M+1) + \frac{\mu(k) - \mu(M+1)}{2}

化简得到：

UCB(i)≤μ(k)+μ(M+1)2UCB(i) \le \frac{\mu(k) + \mu(M+1)}{2}

物理意义：哪怕某个特别差的次优臂 ii 运气爆棚，它的 UCB 最高最高，也无法越过这个“均值中点”。

第三步：得出最终结论

把第一步和第二步结合起来，我们得到了一个令人振奋的绝对不等式链：

LCB(k)≥μ(k)+μ(M+1)2≥UCB(i)(∀i≥M+1)LCB(k) \ge \frac{\mu(k) + \mu(M+1)}{2} \ge UCB(i) \quad (\forall i \ge M+1)

lemma6: exploration Regret

  • key step是bound住Texplore−Texplore(k)T^{explore}-T^{explore}(k)
    • 我们要考虑的是optimal arm k 未ACC的case, 因为如果acc了就没有regret了
      • 那么这个case对于每个exploration轮是可以计算的, 因为本应是KtK_t次(ACC)但是只sample了MtM_t次
      • 其次, 分成不同的communication round 使得更方便使用communication trigger条件来进行bound

Texplo≤T(k)explo+∑p=1PNpM(Kp−Mp)1t^k>Tp−1T^{\text{explo}} \le T^{\text{explo}}_{(k)} + \sum_{p=1}^P N_p M (K_p - M_p) \mathbf{1}_{\hat{t}_k > T_{p-1}}

这里实际上很好理解, 就是对于最多的情况, 每一轮可以pull的arm就是MKpMK_p次, 而arm k只pull了MMpM M_p次

lemma7 : bound communication round

  1. ECR作为关键点, 不仅可以作为confident Radius, 还可以通过比值β\beta对数的方式得到communication round, 这样communication round可以被bound住
  2. 这可能也是这个thredhold的方法被设计的初衷, 通过bound communication round就可以得到每次communication的collision times 就可以bound住comm所带来的regret

lemma8 : 量化误差是如何被 Bound 住的？（数学推导）

在论文的 Section 4.2 和 Lemma 8 中，作者定义了这样一个动态量化规则：
对于被拉动了 Tt(k)T_t(k) 次的摇臂 kk，分配的**量化比特数（位数）**为：

B=⌈1+log⁡2Tt(k)2⌉B = \left\lceil 1 + \frac{\log_2 T_t(k)}{2} \right\rceil

(注：表示向上取整，在计算机科学中算比特数默认 log⁡\log 底数为 2)

推导过程如下：

  1. 网格精度： 如果我们用 BB 个比特来表示 [0,1][0, 1] 区间内的一个数，那么这个区间的最小刻度（步长）就是 2−B2^{-B}。
  2. 最大误差： 当我们把真实的均值 μˉ\bar{\mu} 向上取整（Ceil）到最近的网格点上时，最大的误差不会超过一个步长。所以量化误差满足：

    ∣μ~t(m)(k)−μˉt(m)(k)∣≤2−B|\tilde{\mu}_{t}^{(m)}(k) - \bar{\mu}_{t}^{(m)}(k)| \le 2^{-B}

  3. 代入比特数公式： 我们把 BB 的表达式代入进去：

    2−B=2−⌈1+log⁡2Tt(k)2⌉2^{-B} = 2^{-\left\lceil 1 + \frac{\log_2 T_t(k)}{2} \right\rceil}

  4. 放缩（去掉向上取整符号）： 因为 ⌈x⌉≥x\lceil x \rceil \ge x，所以 −⌈x⌉≤−x- \lceil x \rceil \le -x。为了求 Upper Bound，我们把取整符号去掉：

    2−B≤2−(1+log⁡2Tt(k)2)2^{-B} \le 2^{-\left(1 + \frac{\log_2 T_t(k)}{2}\right)}

  5. 指数化简：

    2−(1+log⁡2Tt(k)2)=2−1⋅2−12log⁡2Tt(k)2^{-\left(1 + \frac{\log_2 T_t(k)}{2}\right)} = 2^{-1} \cdot 2^{-\frac{1}{2} \log_2 T_t(k)}

    前半部分 2−1=122^{-1} = \frac{1}{2}。后半部分利用对数性质 alog⁡ax=xa^{\log_a x} = x：

    2−12log⁡2Tt(k)=(2log⁡2Tt(k))−12=(Tt(k))−12=1Tt(k)2^{-\frac{1}{2} \log_2 T_t(k)} = \left(2^{\log_2 T_t(k)}\right)^{-\frac{1}{2}} = (T_t(k))^{-\frac{1}{2}} = \frac{1}{\sqrt{T_t(k)}}

  6. 得出结论：

    ∣μ~t(m)(k)−μˉt(m)(k)∣≤12⋅1Tt(k)≤1Tt(k)|\tilde{\mu}_{t}^{(m)}(k) - \bar{\mu}_{t}^{(m)}(k)| \le \frac{1}{2} \cdot \frac{1}{\sqrt{T_t(k)}} \le \sqrt{\frac{1}{T_t(k)}}

除此之外, lemma8还解释为什么我们说ECR下降β\beta的时候, 可能导致较大的偏离需要交流, 这里就告诉了我们偏移的具体显著程度.

5. algorithm 9

insight

  1. 对于asychronized的case, 我们首先遇到的问题就是dynamic optimal arm, 对于不同的activation下我们对于regret的讨论是不同的, 这也是regret分解和同步不同之处
  2. 在这里没有acc, 而是在所有arm都被sorted的情况下才会进行exploit这也是由于异步导致的, 除此之外还会产生sample了MM内但是不是MIM_I的额外regret(lemma13,lemma14)
  3. 由于非同步的activation所以导致所有的通信regret都要倍增?

1. 什么是这篇论文里的 Critical Arm (k∗k^*)？

这篇论文研究的是多智能体（Multi-Agent）在异步/周期性激活下的老虎机问题。 假设在某个时刻 tt，系统里有 ∣I∣|I| 个智能体醒着（比如 3 个智能体）。为了避免碰撞并最大化收益，这 3 个智能体最理想的策略是：去拉动收益排名前 3 的那 3 个臂（Top-3 Arms）。

在这个场景下：

  • 什么是“最优”？ 并不是只有排名第 1 的臂才叫最优。排名前 3 的臂（第 1、2、3 名）在这个时刻都是我们要找的“最优目标集合”。
  • 什么是“临界臂” (k∗k^*)？ 这个目标集合的守门员！对于 3 个智能体来说，排名第 3 的臂就是 Critical Arm。
  • 什么是“次优臂” (ii)？ 排名在第 3 名开外的臂（比如第 4 名、第 5 名）。

2. 为什么计算 Regret 要用 Critical Arm，而不是第一名的臂？

现在我们重新算这笔账，你会发现用 k∗k^* 才是唯一严谨的做法。

在真实环境 ν\nu 中（算 RTR_T）： 假设当前有 3 个智能体，臂 ii 是第 4 名（次优臂），临界臂 k∗k^* 是第 3 名。 如果一个算法犯错了，让其中一个智能体去拉了第 4 名（臂 ii），它会顶替掉哪一个本来该拉的臂？ 最保守的估计是：它顶替掉了目标集合里最弱的那一个，也就是临界臂（第 3 名）。 所以，拉错一次臂 ii 产生的最小遗憾代价（Gap），恰恰是临界臂的收益减去臂 ii 的收益：

Δ^(i)=μ(k∗)−μ(i)\hat{\Delta}(i) = \mu(k^*) - \mu(i)

（注：这就是为什么原论文定理2的下界定义里，Δ^(k)\hat{\Delta}(k) 是用 μ(M)−μ(k)\mu(M) - \mu(k) 或 μ(k1∗)−μ(k)\mu(k_1^*) - \mu(k) 来定义的！它算的是距离“及格线”的差距，而不是距离“第一名”的差距。）