Note

1. initialization

在这个阶段作者采用了两个protocol, 并且由此使得每一个agent自身能够identify整个system里有多少个agent( $M$ )以及自己所在的内部排名( $j$ )

553 535

MusicalChairs: 先每个人fix一个对应的arm, 这样便可以获得external rank, 但是由于这个external rank并不一定是连续的, 所以还要配合第二步
Estimate_M:

这个算法的核心思想是: 每个agent所在的arm要和序号在他前面的所有人发生collision, 由此可以得到自己的internal rank(这是实际的连续排名), 其次每个agent还要和自己后面的所有agent发生碰撞, 以此得到整个system内部到底有多少人.
那么为什么每个arm都要sample自己 $2k$ 次?? ~~每个arm不是只需要sample $k$ 次就够了吗?~~ 只sample k次会发生很严重的问题, 就是会导致前面的agent在和"我"发生碰撞之后, 和我同频每一步都会和我发生碰撞导致 $M$ 的估计不准! 那怎么办? 想办法错位, 那我等到我前面的最后一个agent和我碰撞之后再等待一步再出发不就好了. 于是正好就是每个arm要多等 $k$ 轮

1.1 regret

这个阶段由于一共需要的step^[1]是 $M(2K+T_0)$ 所以实际上只需要bound $T_0$ 即可, 由于每次sample有最少 $\frac{1}{K}$ 的概率能选中空闲臂, 所以可以很快表示出 $T_0$ 次仍未成功分配的概率从而可以得到高概率bound

2. exploration

Distributed Algorithms for Multi-Agent Multi-Armed Bandits with Collision使用的算法和这篇是类似的, 使用的是round robin式的arm elimination, 不同的是这篇文章每个循环有 $2^p$ 轮, 一共有 $K_p$ 个循环, 这个算法是完全的collision-free的算法.

但是注意的是这里和传统的方法不同的是这里用来计算的reward sum是截断过的, 所以在计算confidence interval的时候会多考虑一个不等式, 也就是要bound住阶段的量化误差, 这也能说明为什么 $B_s$ 为什么有一个系数 $\frac{3}{2}$

均匀采样次数

对于一个agent来说每一个 $K_p2^p$ $K_{p} 2^{p}$ 轮之后,
- 要么对应ACC的arm sample $K_p\, 2^p$ 次,
- 要么对应每个候选的arm sample $2^p$ 次, 如果一个arm是候选arm, 那么他们总共会被sample $M_p\, 2^p$ 次

对于接受准则和淘汰准则, 和上面这篇文章都是一样的, 事实上只要最优臂的LCB比 $M+1$ 臂的UCB要更高即可, 次优臂的UCB比M的LCB更低就可以淘汰, 分析可以参考lemma5的内容
这里每轮sample $2^p$ 次这样可以使得需要传递的信息最多是 $2^{p+1}-1$ (求和,并且每轮最多得到1的奖励), 这样只需要 $p+1$ 个二进制位就可以传递信息.
这里还有一个相当巧妙的设计, 就是传递的截断信息使用小数部分作为概率$$\tilde S=\begin{cases}\lfloor S\rfloor & o.w.\ \lfloor S\rfloor+1 & prob. , S-\lfloor S\rfloor\end{cases}$$这样 $\mathbb{E}[\tilde S] = S$ , 所以在期望的条件下传递的数据就是实际的数据

2.1. Regret

$R^{\text{explo}} = \mathbb{E}_{\mu} \left[ \sum_{t \in \text{Explo}} \sum_{j=1}^{M} (\mu_{(j)} - r^{j}(t)) \right]$

exploration阶段的regret可以分为两个部分, 其中一个部分是和single-agent相同的部分, 也就是次优臂选中造成的regret, 另外一个部分是multi-agent特殊的部分, 也就是没有早点选中最优臂而造成的损失, 其中这里 $T^{explo}$ 代表全局exploration的步数(单人的! $K_p \, 2^p$ 不用乘 $M$ ), 这里 $T^{explo}_{(k)}$ 代表的是k的总采样数:

$R^{\text{explo}} = \sum_{k>M} (\mu_{(M)} - \mu_{(k)})T_{(k)}^{\text{explo}} + \sum_{k \le M} (\mu_{(k)} - \mu_{(M)})(T^{\text{explo}} - T_{(k)}^{\text{explo}}),$

2.1.1. confidence bound

对于arm elim 或者 UCB 式的算法通常第一步就是要通过 confidence bound 来得到高概率(good event)下的最大pull arm次数:$$s_k = \mathcal{O} \left( \frac{\log(T)}{(\mu_k - \mu_{(M+1)})^2} \right),$$或者对于suboptimal arm也是相似的只不过 $\Delta(k)=\mu_M-\mu_k$
这里得出一个结论是有关于两次communication之间的关系$$T(p+1)\le 3 T§$$通过2的指数的求和和 $M_p$ 的递减可以得出来这个结论. 这里可能和lemma7所新设计的机制是等效的?只不过那篇文章可以控制速率?

2.1.2. regret for suboptimal arm

这一部分是最简单直观的, 直接把结果带进去就行了

2.1.3. regret for optimal arm

这一部分是相对于single-agent的区别, 这一部分首先要bound住 $T^{explo}-T^{explo}_{(k)}$ 这个term, 这个term只需要记住我们前面所说的均匀采样次数很快就能bound住
具体是怎么利用这些条件进行证明的, 可以直接看论文.

3. Communication cost

对于第p个phase, M个agent直接两两传递 $M^2$ , 两个arm之间要传递 $K$ 个arm, 每两个agent之间传递的数据量是 $P+1$ , 所以传递一共需要 $\sum_pKM^2(p+1)$ 轮, 而regret要对于所有的agent产生所以还要乘 $M$ .
接下来bound住communication的total round, 这是由于所有的Acc arm均被Acc来bound的, 所以这个时间与 $M$ 和 $M+1$ arm之间的分离有关

4. algorithm

631

Q&A

为什么是 $2^p$ $2^{p}$ 次? During the p-th exploration phase, each arm is pulled 2p times and its performance is estimated in a Successive Accepts and Rejects fashion [22, 12].
- A: 首先就是方便计算在p轮之后每个arm的总sample次数, 因为实际上可以转换为等比数列求和的问题. 其次一个, 使用这样的double trick的方式进行处理, 很容易得到 $T(p)$ 和 $T(p+1)$ 之间的scale关系.

takeaway

The horizon T is assumed known to the players (for simplicity of exposure, as the anytime generalization of results is now well understood [14]). 这里是说假设players知道horizon的假设是没什么问题的, 因为可以通过double trick扩展到任意时间的泛化.

(across agents) ↩︎