多目标多智能体赌博机：从学习效率到公平性优化

# 多目标多智能体博弈：从学习效率到公平性优化

来源：https://arxiv.org/html/2605.06864
John Wang
马萨诸塞大学阿默斯特分校
[email protected]
&
Mengfan Xu
马萨诸塞大学阿默斯特分校
[email protected]

###### 摘要

我们在随机奖励下研究多目标多智能体多臂老虎机（MO-MA-MAB），其中智能体观察到异构的奖励向量，并在时变图上进行通信。我们将这一新兴的问题设定形式化，以解决*高效学习*问题（通过帕累托遗憾衡量），并将*公平学习*作为额外目标纳入考虑（通过社会福利捕捉）。为了衡量效率，我们构建了帕累托遗憾，并开发了 Pareto UCB1 Gossip 算法，其新颖的探索半径明确地将基于帕累托推断中的统计不确定性与共识误差分离开来。为了表达公平性约束，我们在偏好标量化奖励上构建了纳什社会福利（Nash Social Welfare, NSW）目标，并提出了 Simulated NSW UCB Gossip 算法，该算法集成了基于偏好的奖励模拟、基于八卦（gossip）的效用估计以及类似 UCB 的探索。我们证明了 Pareto UCB1 Gossip 实现了 $O(\log T)$ 的遗憾，以及 $O(\sqrt{T})$ 的实例无关速率，而 Simulated NSW UCB Gossip 实现了 $O(T^{3/4})$ 的实例无关遗憾界限。这种分离揭示了将公平性约束施加于效率目标之上的成本：公平性限制了信息聚合并减缓了收敛速度。实验表明，我们的方法在效率设置和公平性设置下分别比基线方法提高了约 100% 和 50% 的性能。

## 1 引言

不确定性下的序贯决策通常使用多臂老虎机（MAB）框架来建模。在其经典形式中，学习者从一组动作（或“臂”）中重复选择，每个动作关联着一个未知的奖励分布，并且学习者只能观察到所选动作的奖励。尽管面临两个根本性挑战——底层奖励分布的不确定性以及反馈有限（因为观察结果仅限于选定的动作），学习者的目标仍是在一段时间内最大化累积奖励。这些挑战引发了探索（收集关于不确定臂的信息）与利用（利用当前估计来选择表现最佳的选项）之间的基本权衡。这种不确定性与部分可观测性的结合自然地出现在许多现实世界的应用中。

在在线推荐系统中，平台必须选择一个项目进行展示，同时只能观察到对该选择的用户反馈，从而使得替代推荐的結果未知。在适应性临床试验中，治疗必须按顺序分配给疗效不确定的患者，且仅能观察到已实施治疗的结果。在网络系统中，诸如资源分配或路由等决策必须在随机条件下做出，且反馈仅限于已实现的行动。在这些领域中，需要从嘈杂、不完整的观察中学习以优化性能，这使得 MAB 框架成为一种强大且广泛适用的建模范式。

许多现代决策系统本质上是多智能体的，其中多个学习者在不确定性下与共享的一组动作进行交互。这促使我们在随机设定下研究多智能体多臂老虎机（MA-MAB），其中每个智能体观察到嘈杂的奖励，并必须随时间推移学习底层的奖励结构。与单智能体情况相比，智能体可以利用他人产生的信息来加速学习，从而部分缓解不确定性和反馈有限带来的挑战。通过将局部观察与跨智能体共享的信息相结合，MA-MAB 框架能够形成更准确、更健壮的奖励估计，从而提高噪声环境下的学习效率。这种合作学习自然地出现在分布式传感器网络（聚合嘈杂的测量值）、无线通信系统（设备通过共享经验学习信道质量）以及大规模推荐平台（跨用户池化反馈等应用中。

虽然智能体间的合作可以显著提高学习效率，但当智能体经历异构奖励时，也会带来新的挑战。在许多场景中，由于偏好、局部环境或情境因素的差异，不同的智能体可能对同一动作观察到系统性地不同的奖励分布。这种异构性构成了除奖励固有的随机性之外的额外不确定性来源。与可以直接聚合信息的同质设置不同，异构性要求智能体在形成估计时协调可能相互冲突的观察结果。

多智能体系统的另一个关键维度是集中式学习与分布式学习之间的区别。在集中式设置中，全局协调者可以聚合所有智能体的观察结果，从而实现完全的信息共享。相比之下，分布式系统缺乏此类协调，智能体必须依赖局部通信，引入了另一层信息限制。当时通信随时间变化时，这一挑战会被进一步放大。虽然一些工作假设具有固定连接的静止网络，但许多现实世界的系统表现出非平稳通信，其中智能体之间的链路随时间演变。对这种动态建模的一种常见方法是通过 Erdos–Renyi (ER) 随机图，其中边在每个时间步以概率形式形成。

基于这些挑战，一个新兴的研究方向考虑了多目标多臂老虎机（MO-MAB），其中每个动作产生向量值奖励，而非单一的标量结果。这种表述捕捉了性能本质上具有多维度的场景，决策必须同时考虑多个标准。通过将奖励表示为向量，MO-MAB 为建模现实世界场景提供了更真实的框架，在这些场景中，结果不能仅通过单一指标充分概括。

在多目标表述的基础上，当不同的智能体为奖励向量的分量分配不同的效用时，会产生更真实的设置。在这种情况下，每个智能体根据其自身的偏好评估结果，导致系统中可能出现相互冲突的目标。这引入了以原则性和公平的方式平衡这些偏好的需求，而不是简单地确定全局最优臂或优化累积遗憾。相反，考虑聚合个体效用的社会福利函数变得很自然，从而提供一个统一的系统性能度量，该度量既考虑效率又考虑公平性。

这些挑战凸显了对新学习框架的需求，这些框架既要考虑多目标结构又要考虑公平性约束，从而激发了以下研究问题：
(1) 多智能体多臂老虎机（MA-MAB）框架能否扩展到多目标设置，纳入异构奖励和时变分布式通信，同时仍能实现高效学习？
(2) 我们如何通过智能体特定的效用将公平性在 MO-MA-MAB 设置中形式化，并设计优化原则性社会福利目标（如纳什社会福利）的算法？

我们通过以下贡献对这些问题给予了肯定的回答。

### 1.1 贡献

为了在 MO-MA-MAB 中解决高效学习问题，我们通过扩展在 [drugan2013designing](https://arxiv.org/html/2605.06864#bib.bib5) 中引入的 Pareto UCB1 框架，开发了一种分布式算法，适用于具有异构奖励和时变分布式通信的环境。我们纳入了基于八卦（gossip）的通信协议，用于 Erdos–Renyi 网络，如在 [liu2025distributed](https://arxiv.org/html/2605.06864#bib.bib16) 中所研究的那样，以实现智能体间的信息共享。一项关键的技术贡献是设计了一种探索半径，该半径捕捉了由异构性下的分布式估计产生的采样误差和共识误差，从而能够为学习构建可靠的置信集。

为了在 MO-MA-MAB 中实现感知公平的効率学习，我们将 [hossain2021fair](https://arxiv.org/html/2605.06864#bib.bib10) 中引入的纳什社会福利（NSW）遗憾概念扩展到多目标多智能体设置。我们通过偏好向量对向量值奖励进行标量化，从而对智能体特定的偏好进行建模，使得效用矩阵中的每个条目（代表给定智能体某臂的平均奖励）表示为奖励分量与该智能体偏好加权的线性组合。基于这一表述，我们通过在 [hossain2021fair](https://arxiv.org/html/2605.06864#bib.bib10) 中扩展基于 UCB 的方法，并如 [liu2025distributed](https://arxiv.org/html/2605.06864#bib.bib16) 所述纳入 Erdos–Renyi 网络上的基于八卦的更新，开发了一种分布式算法。我们的方法使智能体能够利用共识信息，尽管存在分布式通信和异构观察，仍能针对全局平均效用优化 NSW。

我们通过遗憾分析为两种提出的算法提供了理论保证。对于 Pareto UCB1 Gossip，我们建立了阶为 $O(\log T)$ 的对数遗憾界限，这意味着 $O(\sqrt{T})$ 的实例无关界限，与随机老虎机的最优速率相匹配。相比之下，对于 Simulated NSW UCB Gossip，我们推导了阶为 $O(T^{3/4})$ 的遗憾界限，反映了在异构奖励下优化非线性纳什社会福利目标所引入的额外复杂性。这一差距突出了效率与公平性之间的基本权衡，因为执行公平性阻止了跨智能体的观察聚合并减缓了学习速度。

我们通过与自然基线进行的实证评估来补充我们的理论结果。在多目标设置中，我们与 [drugan2013designing](https://arxiv.org/html/2605.06864#bib.bib5) 中引入的 Pareto UCB1 的多智能体扩展以及 [liu2025distributed](https://arxiv.org/html/2605.06864#bib.bib16) 中开发的多目标 Gossip Successive Elimination 扩展进行比较，展示了由于更有效的置信界限而带来的更快收敛和更低的遗憾。在社会选择设置中，我们与移除八卦通信或奖励模拟的变体进行比较，表明这两个组件对于实现次线性遗憾都是必不可少的。我们在附录 A.1 ([A1.SS1](https://arxiv.org/html/2605.06864#A1.SS1)) 中回顾了相关工作。

## 2 问题表述

多目标、多智能体、多臂老虎机问题包含 $N$ 个智能体，$K$ 个臂，$D$ 维奖励，以及时间范围 $T$。在时间 $t \in [T]$，每个智能体 $i \in [N]$ 拉动一个臂 $a_i^t \in [K]$。与智能体 $i$ 的臂 $k$ 相关的奖励 $X_{i,k}(t) \in [0,1]^D$ 在时间 $t \in [T]$ 上是独立同分布的，并且服从均值为 $\mu_{i,k}$ 的子高斯分布。我们假设一个异构设置，其中对于 $i \neq j$，有 $\mu_{i,k} \neq \mu_{j,k}$。我们引入 $\mu_k = \frac{1}{N}\sum_{i=1}^N \mu_{i,k}$ 作为臂 $k$ 的中心化均值。

我们的问题遵循分布式通信模型。具体而言，我们引入一个无向基础图 $\mathcal{G}=(V,E)$，其中 $V=[N]$ 是智能体集合，对于 $i,j \in [N]$，当且仅当智能体 $i$ 可以与智能体 $j$ 通信时，$(i,j) \in E$。假设 $\mathcal{G}$ 是连通的，并在某些实例中可能是完整的。随机图 $\mathcal{G}_t$ 限制了时间步 $t \in [T]$ 上智能体之间的通信。$\mathcal{G}_t$ 根据 Erdos–Renyi 模型生成，以概率 $p$ 从基础图 $\mathcal{G}$ 中选择边。在时间 $t$，图 $\mathcal{G}_t$ 对应于权重矩阵 $W_t \in \mathbb{R}^{N \times N}$。我们由其条目定义 $W_t$：
$$
[W_t]_{ij} = \begin{cases} \frac{1}{N} & \text{if } j \in \mathcal{N}_i(t) \\ 1 - \frac{\|\mathcal{N}_i(t)\|}{N} & \text{otherwise} \end{cases}
$$
换句话说，智能体 $i$ 分配给其每个邻居 $\frac{1}{N}$ 的权重，并将剩余的质量应用于自身。注意，$W_t$ 是行随机的，谱隙参数为 $\rho = \sum_t \mathbb{E}[\|W_t - \frac{1}{N}\mathbbm{1}\mathbbm{1}^\top\|_2] < 1$。

### 2.1 多目标帕累托设置

我们使用帕累托最优性将 [liu2025distributed](https://arxiv.org/html/2605.06864#bib.bib16) 中描绘的累积预期遗憾扩展到 MO-MA-MAB。如 [drugan2013designing](https://arxiv.org/html/2605.06864#bib.bib5) 中所述，对于向量 $x,y \in \mathbb{R}^D$，$x$ 支配 $y$，我们写为 $x \succ y$，如果对于所有 $i \in [D]$，$x_i \ge y_i$，且存在某个 $i \in [D]$ 使得 $x_i > y_i$。向量 $x \in \mathbb{R}^D$ 与具有相同样本维度的向量集 $S$ 之间的 $\epsilon$-距离由以下公式给出：
$$
\text{Dist}(x,S) = \inf \{\epsilon > 0 : \nexists y \in S \text{ such that } y \succ x + \epsilon\}
$$
换句话说，$\epsilon$ 是最小的松弛量，使得没有向量 $y \in S$ 支配 $x$。类似地，如果向量 $y \in S$ 不被 $S$ 中的另一个向量支配，则它是帕累托最优的。我们将 MO-MA-MAB 的全局帕累托遗憾表示为：
$$
R_T = \sum_{i=1}^N \sum_{t=1}^T \text{Dist}(\mu_{a_i^t}, O)
$$
其中 $\mu_{a_i^t}$ 是智能体 $i$ 在时间 $t$ 选择的臂的中心化均值，且 $O = \{\mu_{k^*} : \nexists k \in [K] \text{ such that } \mu_k \succ \mu_{k^*}\}$。我们将此集合称为中心化臂均值的帕累托前沿，因为它包含所有帕累托最优向量。换句话说，全局帕累托遗憾的次优间隙是所选臂的中心化均值与帕累托前沿之间的 $\epsilon$-距离。

### 2.2 纳什社会福利设置

常值偏好向量 $w_i \in \Delta_K$ 表示智能体 $i$ 的效用，其中 $\Delta_k$ 指的是臂集上的概率单纯形。当智能体 $i$ 在时间 $t$ 拉动臂 $k$ 时，它接收标量奖励 $w_i^\top X_{i,k}(t)$，即向量奖励与其效用的点积。我们用智能体 $j$ 的偏好表示智能体 $i$ 拉动臂 $k$ 的标量均值 $\mu_{i,j,k}^* = w_j^\top \mu_{i,k}$。使用智能体 $j$ 偏好的臂 $k$ 的中心化标量均值为 $\bar{\mu}_{j,k} = \frac{1}{N}\sum_{i=1}^N \mu_{i,j,k}^*$。

我们的遗憾公式源自纳什社会福利函数，旨在为 MO-MA-MAB 开发公平算法。给定臂集上的分布 $p \in \Delta_K$ 和效用矩阵 $\mu \in \mathbb{R}^{N \times K}$，纳什社会福利由下式给出：
$$
\text{NSW}(p,\mu) = \prod_{j=1}^N \left( \sum_{k=1}^K p_k \cdot \mu_{j,k} \right)
$$
假设