具有重尾奖励和信息不对称的鲁棒多智能体多臂老虎机

# 具有重尾奖励与信息不对称性的鲁棒多智能体Bandit算法

###### 摘要

多臂老虎机问题是序贯决策中的核心框架，在次高斯奖励假设下已被广泛研究。然而，现实应用往往涉及重尾奖励分布以及去中心化、信息不对称的交互方式。我们研究了三种信息不对称机制下的多智能体多臂老虎机问题：未观测动作且奖励共享、动作可观测但奖励独立、以及动作不可观测且奖励独立。我们针对每种设置开发了鲁棒的分布式算法，并推导出与集中式重尾速率几乎匹配的遗憾界。在帕累托分布奖励环境上的实验验证了我们的理论发现，并说明了三种机制在同步、协调与探索之间的权衡。

## I 引言

多臂老虎机（MAB）问题是不确定性下序贯决策的核心模型，源于自适应实验和贝叶斯选择的研究[9,13]。每一轮中，学习者选择一个动作并观察一个随机收益，在探索不确定动作与利用表现良好的动作之间取得平衡。老虎机模型支撑着数据驱动的决策系统——在线实验、推荐系统、资源分配、频谱接入、多机器人协调——而这些系统通常是以单智能体抽象所无法捕捉的*分布式*方式运行的：多个智能体同时学习，同时各自只观察系统状态的一部分。

多玩家MAB（MMAB）文献涵盖了多种信息结构。一条研究线路中，玩家通过通信图或闲谈协议共享信息[1,12]。另一条线路中，玩家从共同的臂集合中选择，碰撞会耦合结果[7,11]。近期，合作式MMAB在有限或没有通信的情况下结合结构化观测不对称性进行了研究[4,5]；参见[2]以获得综述。这些工作表明，即使没有显式的消息传递，智能体有时也可以通过共享结构或预先约定的协议进行协调。

另一个大致正交的挑战是许多奖励信号是*重尾*的：罕见的极端事件主导观测，导致弱的集中性，使得次高斯分析不再准确。重尾自然出现在金融收益、网络流量突发以及易受异常值影响的性能指标中。针对重尾奖励的鲁棒算法包括鲁棒UCB方法[3]和确定性探索-利用调度[14]，并扩展到纯探索[17]、线性老虎机[10]和极小极大最优程序[8]，而Catoni风格的置信序列则锐化了在弱矩假设下可实现的结果[15]。

合作式多智能体老虎机、重尾奖励与无在线通信的去中心化运行的*交集*仍未得到充分探索。现有的多智能体重尾工作依赖显式通信：[6]考虑了延迟消息传递，[16]研究了基于图的通信。我们提出的问题是：当智能体通过预先约定的协议隐式协调时，能够实现什么？

**我们的贡献。** 我们引入了三种问题形式，刻画多智能体重尾老虎机中不同的信息不对称性：公共奖励且动作不可观测（问题A）、奖励独立且动作可观测（问题B），以及奖励独立且动作不可观测（问题C）。针对每种问题，我们开发了一种鲁棒的分布式算法——mRUCB-A、mRUCB-Intervals和mHT-DSEE——并证明了总结在表I中的遗憾界。鲁棒均值估计器和单智能体集中性论证改编自[3,14]；我们的贡献在于多智能体问题形式、使用有意的动作偏离作为隐式信号通道，以及对每种信息结构代价的统一比较。

表I：信息结构与遗憾界总结。

## II 预备知识

### II-A 重尾老虎机

考虑一个具有K个臂的随机MAB问题。每个臂\(\bm{a}\in\mathcal{A}:=\{1,\dots,K\}\)具有未知的奖励分布\(\nu_{\bm{a}}\)，其均值为\(\mu_{\bm{a}}\)。在第t轮，智能体选择臂\(\bm{a}_t\)并观察从\(\nu_{\bm{a}_t}\)中抽取的奖励。在时间范围T内的期望遗憾为

\(R_T=T\mu^{\star}-\sum_{t=1}^{T}\mathbb{E}[\mu_{\bm{a}_t}]=\sum_{\bm{a}\in\mathcal{A}}\Delta_{\bm{a}}\,\mathbb{E}[n_{\bm{a}}(T)]\),

(1)

其中\(\mu^{\star}=\max_{\bm{a}}\mu_{\bm{a}}\)，\(\Delta_{\bm{a}}=\mu^{\star}-\mu_{\bm{a}}\)是次优间隙，\(n_{\bm{a}}(T)\)是拉取次数。我们假设重尾奖励：存在\(\varepsilon\in(0,1]\)和\(v>0\)，使得对所有\(\bm{a}\in\mathcal{A}\)，

\(\mathbb{E}[|X_{\bm{a}}-\mu_{\bm{a}}|^{1+\varepsilon}]\leq v\).

(2)

这允许具有无限方差的分布（当\(\varepsilon<1\)时），涵盖帕累托分布、t分布和其他重尾族；较小的\(\varepsilon\)对应更重的尾部。

### II-B 多智能体扩展

我们将设置扩展到M个玩家，其中玩家i具有大小为\(K_i\)的个体动作集\(\mathcal{A}_i\)。联合动作空间为\(\mathcal{A}=\mathcal{A}_1\times\cdots\times\mathcal{A}_M\)，包含\(K^M:=\prod_{i=1}^{M}K_i\)个联合臂。在每一轮t，每个玩家同时选择一个臂，形成联合臂\(\bm{a}(t)=(a_1(t),\dots,a_M(t))\)，然后观察从\(\nu_{\bm{a}(t)}\)中采样的奖励。累积遗憾为

\(R_T=T\mu^{\star}-\sum_{t=1}^{T}\mathbb{E}[X_{\bm{a}(t)}]\),

其中\(\mu^{\star}=\max_{\bm{a}\in\mathcal{A}}\mu_{\bm{a}}\)。玩家可以事先约定策略并知道彼此的动作空间，但在学习过程中*不能通信*。我们考虑三种信息结构，每种对应一类不同的部署场景。

*问题A（动作不对称性）。* 所有玩家观察相同的奖励实现\(X_{\bm{a}(t)}\)，但看不到彼此的动作。这对应于团队优化单一聚合指标的场景：共享频谱频段中观察总网络吞吐量的发射机，或根据一个转化数进行评估的广告渠道，其中聚合指标被记录，但个体动作的归因不可用。

*问题B（奖励不对称性）。* 玩家观察联合动作\(\bm{a}(t)\)，但每个玩家收到一个独立的样本\(X_{\bm{a}(t)}^{i}\sim\nu_{\bm{a}(t)}\)。这匹配联邦或多站点实验：配置被联合选择并集中记录，因此每个站点知道部署了什么，而每个站点只测量自己私有持有的结果。

*问题C（完全不对称性）。* 玩家既不观察其他玩家的动作，也不观察公共奖励；每个玩家收到一个i.i.d.样本。这建模完全去中心化的部署，如没有回程通信的传感器或机器人团队，每个单元只看到自己的测量结果。

### II-C 鲁棒上置信界

在整个过程中，\(\widehat{\mu}_{\bm{a}}(t)\)是[3]的截断均值：记\(X_{\bm{a},1},\dots,X_{\bm{a},n_{\bm{a}}(t)}\)为从臂\(\bm{a}\)观察到的奖励，

\(\widehat{\mu}_{\bm{a}}(t)=\frac{1}{n_{\bm{a}}(t)}\sum_{s=1}^{n_{\bm{a}}(t)}X_{\bm{a},s}\,\mathbf{1}\!\left\{|X_{\bm{a},s}|\leq\left(\tfrac{vs}{\log(T^{\gamma})}\right)^{\frac{1}{1+\varepsilon}}\right\}\).

(3)

联合臂\(\bm{a}\)的鲁棒上置信界（RUCB）为

\(\mathrm{RUCB}_{\bm{a}}(t)=\begin{cases}\infty&\text{if }n_{\bm{a}}(t)=0,\\ \widehat{\mu}_{\bm{a}}(t)+\alpha_{\bm{a}}(t)&\text{otherwise,}\end{cases}\)

(4)

其中第一种情况标记尚未观察到任何样本的臂，因此\(\widehat{\mu}_{\bm{a}}(t)\)未定义；将索引设为\(\infty\)强制每个联合臂在比较之前至少被拉取一次。置信半径为

\(\alpha_{\bm{a}}(t)=v^{\frac{1}{1+\varepsilon}}\!\left(\frac{c\log(T^{\gamma})}{n_{\bm{a}}(t)}\right)^{\!\frac{\varepsilon}{1+\varepsilon}}\),

(5)

其中\(c,\gamma>0\)，且[3, Prop. 1]给出

\(\Pr(|\widehat{\mu}_{\bm{a}}(t)-\mu_{\bm{a}}|>\alpha_{\bm{a}}(t))\leq t^{-\gamma}\).

下面只使用这一集中性质，因此任何满足形如(5)的界的估计器——均值的中位数，或[15]的Catoni风格置信序列——都可以替代。这种替换会改变常数c以及v的进入方式，进而改变三个定理中的常数，但不会改变速率；当\(\varepsilon\to 1\)时，Catoni风格估计器给出最尖锐的常数，但代价是每一轮需要解一个隐式方程。

## III 问题A：公共奖励、动作不可观测

在问题A中，所有玩家观察相同的奖励，但看不到其他玩家的动作。出现两个技术挑战。首先，由于动作是隐藏的，如果玩家的内部估计发生分歧，可能出现协调失误，观察到的奖励随后被归因于错误的联合动作。其次，奖励分布是重尾的，需要在弱矩假设下使用鲁棒估计器来控制估计误差。然而，由于奖励是共享的，在相同的确定性更新规则下，所有玩家的估计保持相同——这是关键的简化特性。

我们在\(\mathcal{A}\)上施加字典序以进行一致的平局打破：\(\bm{a}<\bm{b}\)如果存在\(n\)使得对所有\(i<n\)有\(a_i=b_i\)，且\(a_n<b_n\)。

**算法1** mRUCB-A

1: 玩家对\(\mathcal{A}\)中的联合臂按字典序排序。
2: 对于t = 1, 2, ..., T：
3:     每个玩家计算\(n_{\bm{a}}(t)\)和\(\widehat{\mu}_{\bm{a}}(t)\)（对所有\(\bm{a}\)）。
4:     每个玩家独立选择\(R_t=\arg\max_{\bm{a}}\mathrm{RUCB}_{\bm{a}}(t)\)（按字典序打破平局）。
5:     每个玩家拉取\(R_t\)的个体分量；所有玩家观察公共奖励\(X_{R_t}\)。
6:     每个玩家更新\(\widehat{\mu}_{R_t}\)和\(n_{R_t}\)。

**定理1。** 对于问题A，mRUCB-A在时间范围T内的遗憾满足

\(R_T\le c_A\sum_{\bm{a}:\Delta_{\bm{a}}>0}\left[\Delta_{\bm{a}}\left(\frac{v^{1/(1+\varepsilon)}}{\Delta_{\bm{a}}}\right)^{(1+\varepsilon)/\varepsilon}\log(T)+K^O(1)\right]\),

其中\(c_A\)是一个常数（取决于c、γ、ε）。

*证明思路。* 对任何\(\Delta_{\bm{a}}>0\)，定义第t轮的好事件：

\(\mathcal{G}_t:|\widehat{\mu}_{\bm{a}}(t)-\mu_{\bm{a}}|\le\alpha_{\bm{a}}(t)\)

对所有\(\bm{a}\)成立。根据第II-C节的集中界，\(\Pr(\mathcal{G}_t^c)\le K^M t^{-\gamma}\)。在\(\mathcal{G}_t\)下，选择\(\bm{a}\)需要

\(\widehat{\mu}_{\bm{a}}(t)+\alpha_{\bm{a}}(t)\ge\widehat{\mu}_{\bm{a}^{\star}}(t)+\alpha_{\bm{a}^{\star}}(t)\),

这意味着\(2\alpha_{\bm{a}}(t)\ge\Delta_{\bm{a}}\)。这在

\(\tau_{\bm{a}}=c\gamma\log(T)(2v^{1/(1+\varepsilon)}/\Delta_{\bm{a}})^{(1+\varepsilon)/\varepsilon}\)

次拉取之后不再成立。因此

\(\mathbb{E}[n_{\bm{a}}(T)]\le\tau_{\bm{a}}+\sum_{t=1}^{T}\Pr(\mathcal{G}_t^c)\),

其中尾部求和对于\(\gamma>1\)收敛。将所有次优臂的\(\Delta_{\bm{a}}\cdot\mathbb{E}[n_{\bm{a}}(T)]\)求和即得结果。∎

这与在\(K^M\)个臂上的最优单智能体重尾速率匹配。由于即使对集中式学习器来说，\(K^M\)的依赖性也是不可避免的，分布式智能体在动作不对称性下没有产生额外代价。

## IV 问题B：奖励独立、动作可观测

在问题B中，玩家观察联合动作，但收到*独立的*奖励样本

\(X_{\bm{a}(t)}^{1},\dots,X_{\bm{a}(t)}^{M}\stackrel{{\scriptstyle\text{i.i.d.}}}{\sim}\nu_{\bm{a}(t)}\).

这颠倒了过来问题A的结构：玩家看到所有动作，但他们的估计会发散，因为每个经验均值使用不同的样本，因此一个玩家可能得出某个臂是次优的结论，而另一个玩家的区间仍然重叠。因此，每个玩家独立应用的索引规则会导致持续的协调失误。

mRUCB-Intervals避免了这一点，用*循环消除*取代索引最大化：玩家在一个公共活动集S上循环，而一个臂只有在每个玩家都能观察到的信号下才会离开S。对于每个联合臂\(\bm{a}\)和玩家i，算法维护

\(I_{\bm{a}}^i(t)=\left[\widehat{\mu}_{\bm{a}}^i(t)-\alpha_{\bm{a}}(t),\;\widehat{\mu}_{\bm{a}}^i(t)+\alpha_{\bm{a}}(t)\right]\),

(6)

其中\(\alpha_{\bm{a}}(t)\)对所有玩家是公共的，因为它只依赖于共享的拉取次数\(n_{\bm{a}}(t)\)。消除分三个阶段进行。

*检测*：如果玩家i发现\(I_{\bm{a}}^i(t)\)严格低于另一个活动臂的区间并且与之不相交，则从玩家i的角度来看，\(\bm{a}\)被支配。

*信号传递*：玩家i然后偏离规定的动作，拉取一个*不同的*个体臂，这是唯一可用的隐式通信形式。

*传播*：由于动作是可观测的，所有玩家检测到预定联合臂\(\bm{a}(t)\)与实际联合臂\(\bm{a}^{\prime}(t)\)之间的不匹配，并标记\(\bm{a}(t)\)进行移除，无论他们自己的区间是否支持这一决定。

两个约定保持玩家的统计数据对齐：信号回合的奖励被丢弃，移除在当前周期结束时生效。算法2给出了具体过程。

**算法2** mRUCB-Intervals

1: 玩家对\(\mathcal{A}\)中的臂排序；设置\(S\leftarrow\mathcal{A}\)，\(P\leftarrow\emptyset\)。
2: 当\(t\le T\)时：
3:     对每个\(\bm{a}\in S\)按顺序：
4:         如果某个玩家i发现\(I_{\bm{a}}^i(t)\)严格低于S中另一个臂的区间，则
5:             该玩家拉取一个*不同的*个体臂；所有玩家观察到\(\bm{a}^{\prime}(t)\neq\bm{a}\)并设置\(P\leftarrow P\cup\{\bm{a}\}\)；该轮的奖励被丢弃。
6:         否则
7:             所有玩家拉取\(\bm{a}\)的分量；玩家i观察\(X_{\bm{a}}^i\)并更新自己的统计数据。

**定理2。** 对于问题B，mRUCB-Intervals在时间范围T内的遗憾满足

\(R_T\le c_B\sum_{\bm{a}:\Delta_{\bm{a}}>0}\Delta_{\bm{a}}\left(\frac{v^{1/(1+\varepsilon)}}{\Delta_{\bm{a}}}\right)^{(1+\varepsilon)/\varepsilon}\log(T)+K^O(1)\),

其中\(c_B\)是一个常数。

*证明思路。* 消除的唯一触发方式是某个玩家的区间被证明性地低于另一个区间；由于所有玩家观察到同样的信号操作（拉取不同的臂），并且移除决定在周期结束时统一生效，所有玩家始终在S上保持一致。对任何在S中停留超过

\(\tau_{\bm{a}}=c\gamma\log(T)(2v^{1/(1+\varepsilon)}/\Delta_{\bm{a}})^{(1+\varepsilon)/\varepsilon}\)

次的臂\(\bm{a}\)，在好事件下，它的区间必然与最优臂的区间重叠，这导致与定理1相同的每个臂拉取计数界。奖励被丢弃的信号回合至多增加每个被消除臂的M次额外拉取，这仅改变常数。∎

因此，奖励独立性的代价不是额外的遗憾阶项，而是信号回合造成的常数因子开销，以及算法设计中消除的延迟。

## V 问题C：完全不对称性

在问题C中，玩家既不观察联合动作，也不观察公共奖励；每个玩家只获得一个独立的奖励样本，且不知道其他玩家选择了什么。这对应于没有共享观测或协调信号的完全去中心化部署。任何依赖检测其他玩家偏离的算法（如mRUCB-Intervals）在此都不可行，因为偏离行为对其他人不可见。

因此，我们采用确定性探索-利用调度，其中玩家的行动安排是预先协调的，因此不需要在线协调。

**算法3** mHT-DSEE

1: 玩家在运行前商定一个确定性调度\(i_t \in \mathcal{A}\)（在所有玩家中共享）。
2: 对于t = 1, 2, ..., T：
3:     每个玩家拉取调度指定的臂\(i_t\)的分量，但有一个重要的例外（见下文）。
4:     每个玩家观察自己的奖励实现，并更新鲁棒均值估计。

这里的关键困难是，玩家无法观察到彼此的动作。如果所有玩家都严格遵循相同的共享调度，那么联合动作是确定的，问题简化为一个集中式重尾老虎机。然而，这种“天真”的调度要求预先选择一个固定的臂序列，并且随着T的增长，最优臂必须在时间上不断被重新选择，而没有任何反馈来指导这一选择。我们克服这一困难的方法是使用预先指定的、与奖励无关的探索调度，如果调度本身是时间-方差最优的，那么其遗憾与最优自适应策略的遗憾在常数因子内匹配（见[14]）。更具体地说，调度由交替的探索块和利用块组成，其中探索块对每个臂进行\(\propto \log T\)次拉取，利用块则以当前经验最佳臂进行拉取。由于所有玩家都知道调度并且共享相同的估计（在相同数据下更新），他们保持一致，不需要检测偏差。

**定理3。** 对于问题C，mHT-DSEE在时间范围T内的遗憾满足

\(R_T\le c_C\sum_{\bm{a}:\Delta_{\bm{a}}>0}\Delta_{\bm{a}}\left(\frac{v^{1/(1+\varepsilon)}}{\Delta_{\bm{a}}}\right)^{(1+\varepsilon)/\varepsilon}\log(T)+K^O(1)\),

其中\(c_C\)是一个常数。

*证明思路。* 由于调度是预先确定的且对所有玩家已知，联合动作序列\((\bm{a}_t)\)在玩家之间是相同的，使得每个玩家的奖励样本可用于更新均值。利用块的遗憾受次优臂的拉取次数限制，而这又受探索块频繁程度的限制。调度被构造为使总体探索次数为\(O(\sum_{\bm{a}}\log T)\)，同时以高概率保证最优臂被识别。鲁棒集中界（第II-C节）将估计误差控制为\(\alpha_{\bm{a}}(t)\)量级，从而得出结果。∎

因此，在完全不对称的情况下，通过预协调的探索-利用调度实现了接近最优的遗憾，与自适应算法相比仅损失常数因子。

## VI 实验

我们在一个合成环境中评估了所提出的算法，该环境具有帕累托分布的奖励，参数\(\varepsilon=0.5\)（因此方差无限）。将\(M=3\)个玩家、每个玩家有\(K_i=3\)个臂，形成\(K^M=27\)个联合臂，均值在\([0.2,1.0]\)范围内。我们比较了mRUCB-A、mRUCB-Intervals和mHT-DSEE，以及两个基线：一个在每轮共享所有信息（相当于集中式RUCB）的中心化算法，和一个使用次高斯UCB的独立agent基线。图1报告了平均值±标准差下的遗憾，超过20次运行。

图1：\(T=10^4\)轮的重尾老虎机设置下的平均遗憾。mRUCB-A与中心化基线匹配，mRUCB-Intervals略高但由于常数因子而略高，而mHT-DSEE展示了由于调度导致的平滑增长。

实验结果与理论一致：mRUCB-A的曲线几乎与集中式基线重合；mRUCB-Intervals的常数因子略大，源于信号回合和消除延迟；mHT-DSEE的探索-利用结构使其在所有机制中具有最平滑的遗憾增长，但常数最高。三种算法都显著优于次高斯UCB基线，后者在重尾奖励下遭受线性遗憾，因为经典置信界不成立。

## VII 结论

我们研究了具有重尾奖励的多智能体bandit问题，并考虑了三种信息不对称机制。当奖励共享时，同步更新规则使估计保持一致，隐式协调是免费的（mRUCB-A）。当奖励独立但动作可观测时，隐式信号可以通过有意的动作偏离实现，代价是常数因子开销（mRUCB-Intervals）。当两者都不可观测时，预先协调的确定性探索-利用调度恢复接近最优的遗憾，但常数更大（mHT-DSEE）。总的来说，我们的结果表明，在重尾、多智能体和去中心化的交叉点上，通过协议进行隐式协调可以达到接近集中式最优的性能；信息不对称的成本表现为常数因子和算法复杂性，而不是统计速率。

## 参考文献

[1] 关于在图上进行通信的多智能体bandits的近期工作。

[2] 多玩家多臂老虎机综述。

[3] 重尾分布鲁棒随机bandits的truncated mean方法。

[4] 利用共享随机性在无通信多智能体bandits中进行协调。

[5] 无通信合作式bandits中的观测不对称性。

[6] 具有延迟通信的重尾多智能体bandits。

[7] 碰撞模型下的多玩家bandits。

[8] 重尾bandits的极小极大最优算法。

[9] 早期bandit问题研究。

[10] 重尾线性bandits。

[11] 多智能体bandits中的通信协议。

[12] 基于gossip的多玩家bandits。

[13] Bandit问题与自适应实验。

[14] 确定性探索-利用调度的重尾bandits。

[15] Catoni风格置信序列。

[16] 图通信下的多智能体重尾bandits。

[17] 纯探索的重尾bandits。

[18] 分布式bandits及其他相关方向。