Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits

基本信息

• 论文ID: 2506.14988
• 标题: Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits
• 作者: Tianyi Xu, Jiaxin Liu, Nicholas Mattei, Zizhan Zheng
• 机构: Tulane University, University of Illinois Urbana-Champaign
• 分类: cs.LG, cs.AI
• 发表时间: arXiv preprint, 2025年11月26日版本
• 论文链接: https://arxiv.org/abs/2506.14988v4

摘要

本文提出了一个多智能体多臂老虎机（MA-MAB）框架，旨在确保智能体间的公平性同时最大化系统整体性能。针对臂奖励信息有限的决策挑战，引入了一种新颖的探测（probing）机制，在分配前战略性地收集选定臂的信息。在离线设置（已知奖励分布）中，利用子模性质设计了具有常数因子近似保证的贪心探测算法。在在线设置中，开发了一种实现次线性遗憾（sublinear regret）同时保持公平性的算法。在合成和真实世界数据集上的大量实验表明，该方法在公平性和效率方面均优于基线方法。

研究背景与动机

核心问题

传统的多臂老虎机问题通常优化功利主义福利（utilitarian welfare，即总奖励之和），但这会导致严重的不公平现象。例如在网约车场景中，中央调度系统将司机分配到不同地理区域时，优化总收益可能导致部分司机完全没有订单，出现"饥饿"（starvation）现象。

问题重要性

公平的资源分配在许多实际应用中至关重要：

1. 网约车平台：司机需要公平地访问盈利区域
2. 内容推荐系统：创作者曝光不应被垄断
3. 无线网络调度：客户端设备需要公平的带宽分配

现有方法局限性

1. 公平性缺失：现有MA-MAB方法主要关注总奖励最大化，忽视个体公平
2. 信息依赖：依赖即时反馈更新估计，在信息不完整或噪声环境下表现不佳
3. 探索不足：缺乏主动信息收集机制，导致对不确定臂的估计误差传播到分配决策

研究动机

本文通过引入探测机制和纳什社会福利（Nash Social Welfare, NSW）目标，弥合了公平多智能体方法与主动探索策略之间的空白，使通过主动探索获得的信息直接转化为对所有智能体的公平结果。

核心贡献

1. 新框架：扩展MA-MAB框架，引入探测机制在分配前测试选定臂，通过NSW优化确保公平性
2. 离线算法：针对已知奖励模式，开发了具有可证明性能保证的简单有效的贪心探测策略
3. 在线算法：提出平衡探索与公平性的算法，证明探测和公平分配不会损害渐近性能（次线性遗憾）
4. 实验验证：在合成和真实数据上证明方法在公平性和效率方面优于基线

方法详解

任务定义

基本设置：

• 智能体：M个智能体，记为 j ∈ M
• 臂：A个臂，记为 a ∈ A
• 奖励分布：每个智能体-臂对 (j,a) 有未知分布 D_{j,a}，均值 μ_{j,a} ∈ 0,1

决策流程（每轮 t）：

1. 探测阶段：选择探测集 S_t ⊆ A，对每个 a ∈ S_t 获取新鲜奖励样本 R_{j,a,t}
2. 分配阶段：基于观察到的奖励和当前估计，通过策略 π_t 分配臂给智能体

公平性目标：最大化纳什社会福利（NSW） $\text{NSW}(S_t, R_t, \mu, \pi_t) = \prod_{j \in [M]} \left( \sum_{a \in S_t} \pi_{j,a,t} R_{j,a,t} + \sum_{a \notin S_t} \pi_{j,a,t} \mu_{j,a} \right)$

探测开销：有效奖励为 $R^{\text{total}}_t = (1 - \alpha(|S_t|)) \mathbb{E}_{R_t}[\text{NSW}(S_t, R_t, \mu, \pi_t)]$ 其中 α(·) 是非递减开销函数，α(0)=0, α(I)=1

遗憾定义： $R_{\text{regret}}(T) = \sum_{t=1}^T \left[ (1-\alpha(|S^*_t|)) \mathbb{E}[\text{NSW}(S^*_t, R_t, \mu, \pi^*_t)] - R^{\text{total}}_t \right]$

离线设置：贪心探测算法

优化目标分解

定义两个效用函数：

1. 探测效用 g(S)：仅使用探测臂的最优NSW期望 $g(S) = \max_{\pi \in \Delta^A_S} \mathbb{E}\left[ \prod_{j \in [M]} \left( \sum_{a \in S} \pi_{j,a} R_{j,a} \right) \right]$
2. 非探测效用 h(S)：仅使用未探测臂的最优NSW $h(S) = \max_{\pi \in \Delta^A_{[A]\backslash S}} \prod_{j \in [M]} \left( \sum_{a \notin S} \pi_{j,a} \mu_{j,a} \right)$

分段线性上界构造

由于 log(g(S)) 非子模，直接优化困难。采用分段线性包络近似：

• 将区间 0, x_max 划分为细粒度分段，断点为 τ_0, τ_1, ..., τ_L
• 在每个断点构造切线 T_{τ_i}(z) = log(τ_i) + (z - τ_i)/τ_i
• 定义 φ(z) = max_{0≤i<L} T_{τ_i}(z)，满足 φ(z) ≥ log(z)
• 设置 f_upper(S) = φ(g(S))

子模性质

引理1-5建立了关键性质：

• 引理1：g(S) 单调递增
• 引理2：f_upper(S) 单调递增
• 引理3：f_upper(S) 子模（核心性质）
• 引理4：h(S) 单调递减
• 引理5：R(S) ≤ (1-α(|S|))(g(S) + h(S))

Algorithm 1: 离线贪心探测

输入：分布 {F_{m,a}}, 开销函数 α(·), 预算 I, 参数 ζ≥1
输出：探测集 S_pr

1. 初始化 S_0 = ∅
2. For i = 1 to I:
   - 选择边际增益最大的臂：
     a = argmax_{a∉S_{i-1}} [f_upper(S_{i-1}∪{a}) - f_upper(S_{i-1})]
   - S_i = S_{i-1} ∪ {a}
3. 按 (1-α(|S_j|))f_upper(S_j) 降序排序候选集
4. 遍历排序后的集合：
   - 如果 (1-α(|S_j|))f_upper(S_j) < h(∅)，返回 ∅
   - 如果 (1-α(|S_j|))f_upper(S_j) > ζR(S_j)，继续
   - 否则返回 S_j

定理1（近似保证）：对任意 ζ≥1，算法返回的 S_pr 满足 $R(S_{pr}) \geq \frac{e-1}{2e-1} \cdot \frac{1}{\zeta} \cdot R(S^*)$ 这是基于子模最大化的 (1-1/e) 近似因子推导得出。

在线设置：OFMUP算法

Algorithm 2: Online Fair Multi-Agent UCB with Probing (OFMUP)

初始化阶段（t = 1 到 MA）：

• 每个智能体-臂对至少探索一次
• 构建经验CDF F̂_{j,a,t} 和均值估计 μ̂_{j,a,t}

主循环阶段（t > MA）：

1. 探测集选择：调用Algorithm 1 基于当前估计 F̂_{j,a,t} 选择 S_t
2. 探测更新：对 S_t 中的臂采样，更新统计量和置信上界 $U_{j,a,t} = \min(\hat{\mu}_{j,a,t} + w_{j,a,t}, 1)$ 其中 w_{j,a,t} 是基于Freedman不等式的置信宽度
3. 策略优化： $\pi_t = \arg\max_{\pi_t \in \Delta^A} (1-\alpha(|S_t|)) \mathbb{E}_{R_t}[\text{NSW}(S_t, R_t, U_t, \pi_t)]$
4. 臂拉取：每个智能体 j 根据 π_t 拉取臂，观察奖励并更新

置信界构造

引理7（浓度界）：以至少 1-δ/2 的概率，对所有 t>A, a∈A, j∈M： $|\mu_{j,a} - \hat{\mu}_{j,a,t}| \leq \sqrt{\frac{2(\hat{\mu}_{j,a,t} - \hat{\mu}^2_{j,a,t}) \ln(\frac{2MAT}{\delta})}{N_{j,a,t}}} + \frac{\ln(\frac{2MAT}{\delta})}{3N_{j,a,t}} = w_{j,a,t}$

技术创新点

1. 探测与公平性结合：首次将主动探测机制与NSW公平目标结合，不同于仅优化总奖励的先前工作
2. 子模近似技术：通过分段线性上界将非子模问题转化为子模优化，保持可处理性
3. UCB-NSW融合：在线算法巧妙结合UCB置信界与NSW优化，平衡探索-利用与公平性
4. 分层遗憾分析：将轮次分为"大γ"和"小γ"两类，分别处理高不确定性和低不确定性情况

实验设置

数据集

合成数据：

• 小规模：M=12 智能体，A=8 臂
• 中等规模：M=20 智能体，A=10 臂
• 奖励分布：
  • Bernoulli分布（奖励0或1，均值在0.3, 0.8）
  • 离散分布（奖励从{0.3, 0.4, 0.5, 0.6, 0.7, 0.8}采样）

真实数据：NYYellowTaxi 2016数据集

• 智能体：车辆（随机预采样位置）
• 臂：离散化的接客位置（0.01°×0.01°网格）
• 奖励：基于车辆到接客点的归一化曼哈顿距离（距离越近奖励越高）

评价指标

• 累积遗憾：按公式(1)计算，最优奖励通过穷举搜索确定
• 数值稳定性：使用几何平均聚合每个智能体奖励的累积NSW
• 近似验证：验证 f_upper(S) 与 log(g(S)) 的差异≤0.03

对比方法

1. Non-Probing：Jones等人(2023)的公平MAB算法，无探测能力，仅基于当前信息优化分配
2. Random P+A：随机选择固定数量臂探测，然后随机分配
3. Greedy P+A：使用相同贪心探测策略，但探测后随机分配

实现细节

• 探测预算：根据问题规模设置
• 开销函数：α(|S|) 为递增函数，α(0)=0, α(I)=1
• 置信参数：δ 设置确保高概率保证
• 代码开源：https://github.com/jiaxin26/Fair-MA-MAB-with-Probing

实验结果

主要结果

图1展示的核心发现：

1. 小规模场景（M=12, A=8, Bernoulli）：
   • OFMUP在T=3000时遗憾比Random P+A低85%
   • 比Greedy P+A低60%
   • 比Non-Probing显著更优
2. 中等规模场景（M=20, A=10, Bernoulli）：
   • OFMUP优势更明显
   • T=3000时遗憾比Random P+A低88%
   • 比Greedy P+A低80%
   • 显示出更好的可扩展性
3. 离散分布场景：
   • OFMUP持续优于基线
   • 随着学习奖励模式，与其他方法的差距增大
   • T=3000时比Random P+A低85%，比Non-Probing低65%
4. Random P+A异常现象：
   • 在小规模测试中遗憾略高于预期
   • 原因：通过几何平均计算公平性时，小样本增加变异性

可扩展性分析

图2展示的扩展性：

1. 固定臂数（A=8），变化智能体数：
   • OFMUP在所有智能体数量下表现良好
   • 相对优势随问题复杂度增加而增长
2. 固定智能体数（M=20），变化臂数：
   • OFMUP优势随臂数增加更明显
   • 证明探测机制在高维度空间更有价值

实验发现

1. 探测的关键作用：探测在信息收集和指导分配中起决定性作用
2. 公平分配的重要性：Greedy P+A表现远不如OFMUP，说明探测后的公平分配至关重要
3. 理论验证：实验结果验证了理论分析——OFMUP有效平衡探索-利用与公平性
4. 真实数据适用性：在NYYellowTaxi数据上的成功证明了实际应用潜力

相关工作

多臂老虎机基础

• 单智能体MAB：Lai & Robbins (1985), Garivier & Cappé (2011)
• 多智能体MAB：Martínez-Rubio等(2019), Hossain等(2021)
• 公平性研究：Joseph等(2016, 2018), Patil等(2021)

纳什社会福利

• 理论基础：Kaneko & Nakamura (1979)
• 计算方法：Cole & Gkatzelis (2015)
• MA-MAB应用：Jones, Nguyen & Nguyen (2023)——本文直接扩展的工作

探测机制

• 经济学起源：Weitzman (1979)
• 单智能体带探测的Bandit：
  • Aaron D. Tucker等(2023)：昂贵奖励观察，Θ(c^{1/3}T^{2/3})界
  • Elumar等(2024)：每轮探测一臂，Õ(√KT)遗憾
  • Zuo等(2020)：Observe-Before-Play框架
• 子模探测：Bhaskara等(2020)路由问题
• 本文贡献：首次将探测与多智能体公平性结合

研究空白

现有工作要么关注公平MAB但依赖被动反馈，要么研究探测但忽视公平性。本文填补了这一空白。

理论分析

离线近似保证（定理1）

结果：R(S_pr) ≥ (e-1)/(2e-1) · 1/ζ · R(S*)

证明关键步骤：

1. 利用引理5：R(S) ≤ (1-α(|S|))(g(S) + h(S))
2. 应用子模最大化的(1-1/e)近似
3. 通过算法筛选条件关联f_upper与R
4. 得到常数因子近似保证

在线遗憾界（定理2）

结果：以至少1-δ概率， $R_{\text{regret}}(T) = O\left(\zeta(\sqrt{MAT} + MA) \ln^c\left(\frac{MAT}{\delta}\right)\right)$

证明框架：

1. NSW平滑性（引理6）：NSW关于奖励矩阵的Lipschitz性质
2. 浓度界（引理7）：基于Freedman不等式的置信界
3. 轮次分层（引理8）：
   • 定义γ_{j,t} = Σ_a π_{j,a,t}(1-U_{j,a,t})
   • 大γ轮次：|Q(t,p)| ≥ 2^p·3lnT，贡献≤1/T²
   • 小γ轮次：应用浓度界，分解为根项和线性项
4. 根项界：通过Young不等式和引理8处理
5. 线性项界：利用Jones等(2023)的引理4.4
6. 最终合并：得到O(√MAT)主项加低阶项

关键技术：

• 将遗憾从(S*,π*)转换到(S_t,π_t)，利用定理1的因子
• UCB乐观性：U_{j,a,t}≥μ_{j,a}确保探索
• 分层分析避免直接处理所有轮次的复杂依赖

结论与讨论

主要结论

1. 理论贡献：
   • 离线：常数因子近似保证的可计算算法
   • 在线：次线性遗憾O(√MAT)，与非探测公平算法相当，但实际性能更优
2. 实践价值：
   • 探测机制显著改善奖励估计
   • 平衡探索-利用与公平性
   • 在真实网约车数据上验证有效性
3. 方法论创新：
   • 首次将主动探测与多智能体公平性结合
   • 子模近似技术处理非凸优化
   • UCB-NSW融合的在线学习框架

局限性

1. 计算复杂度：
   • 离线算法需要迭代求解NSW优化（NP-hard）
   • 在线每轮需计算最优策略π_t
   • 大规模场景（M,A很大）可能面临计算瓶颈
2. 理论假设：
   • 分段线性近似需要足够细的分割（假设d/d'≥τ_i/τ_j）
   • 探测预算I需要预先设定
   • 开销函数α(·)形式需要已知
3. 实验范围：
   • 实验规模相对有限（最大M=20, A=10）
   • 真实数据仅测试网约车场景
   • 未与更多最新公平MAB方法对比
4. 公平性度量：
   • 仅考虑NSW，未探索其他公平性概念（如max-min, envy-freeness）
   • NSW对零奖励敏感（需要所有智能体获得正奖励）

未来方向

论文未明确提出，但可推断的方向：

1. 扩展到其他公平性度量：研究探测机制与其他公平性概念的结合
2. 自适应探测预算：动态调整探测数量而非固定I
3. 分布式实现：去中心化的探测和分配决策
4. 非平稳环境：奖励分布随时间变化的场景
5. 约束条件：加入预算、延迟等实际约束

深度评价

优点

1. 理论严谨性：
   • 离线和在线设置都有严格的理论保证
   • 证明完整详尽（附录超过20页）
   • 子模性质的建立巧妙且关键
2. 问题重要性：
   • 解决了实际应用中的真实痛点（公平性与不确定性）
   • 网约车案例具有直接应用价值
   • 填补了公平MAB与主动探索之间的研究空白
3. 方法创新性：
   • 探测机制与NSW的结合是新颖的
   • 分段线性上界构造技术巧妙
   • UCB与NSW优化的融合非平凡
4. 实验充分性：
   • 覆盖合成和真实数据
   • 多种分布和规模设置
   • 可扩展性分析完整
   • 消融实验（通过对比Greedy P+A）清晰
5. 写作清晰度：
   • 动机阐述清楚
   • 技术细节描述完整
   • 图表直观有效

不足

1. 计算效率未充分讨论：
   • 未报告算法运行时间
   • NSW优化的计算复杂度分析缺失
   • 大规模场景的可行性存疑
2. 探测开销建模简化：
   • α(|S|)函数形式过于抽象
   • 实际应用中如何设置α未详细说明
   • 不同应用场景的开销特性差异未探讨
3. 基线方法有限：
   • 主要对比Jones等(2023)的方法
   • 未与更多最新公平MAB算法比较
   • 缺少与非公平但高效的探测算法对比
4. 实验规模受限：
   • 最大M=20, A=10相对较小
   • 真实数据仅一个数据集
   • 未测试极端不平衡场景（M>>A或A>>M）
5. 理论-实践差距：
   • 定理1的近似因子包含ζ参数，实际如何选择ζ未说明
   • 定理2的遗憾界常数c未明确
   • 分段线性近似的实际误差（0.03）如何影响性能未分析
6. 公平性讨论不足：
   • NSW的局限性（对零奖励敏感）未充分讨论
   • 未与其他公平性度量比较
   • 个体理性（individual rationality）未考虑

影响力

学术影响：

• 高：填补重要研究空白，预期引用率高
• 为公平MAB领域提供新的研究范式
• 探测机制与公平性结合可能启发后续工作

实用价值：

• 中等偏高：
  • 网约车等平台有直接应用潜力
  • 但计算复杂度可能限制大规模部署
  • 需要进一步工程优化

可复现性：

• 高：代码已开源，算法描述详细
• 理论证明完整，易于验证
• 实验设置清晰

适用场景

强适用场景：

1. 网约车调度：中等规模城市（10-20个区域，10-50辆车）
2. 内容推荐：平台需要平衡创作者曝光
3. 无线网络调度：60 GHz WLAN场景（论文提及）
4. 资源分配：需要公平性且存在不确定性的任何场景

弱适用场景：

1. 大规模系统：M,A>100时计算可能不可行
2. 实时系统：NSW优化的计算延迟可能过高
3. 动态环境：奖励分布快速变化的场景
4. 零和竞争：智能体之间存在直接竞争的情况

不适用场景：

1. 单智能体问题：方法过于复杂
2. 已知奖励：探测机制无必要
3. 极端公平要求：NSW可能不够"公平"（考虑max-min）

参考文献（关键文献）

1. Jones, Nguyen & Nguyen (2023): "An efficient algorithm for fair multi-agent multi-armed bandit with low regret" - 本文直接扩展的基础工作
2. Cole & Gkatzelis (2015): "Approximating the Nash social welfare with indivisible items" - NSW优化理论基础
3. Zuo, Zhang & Joe-Wong (2020): "Observe Before Play: Multi-Armed Bandit with Pre-Observations" - 探测机制先驱工作
4. Bhaskara et al. (2020): "Adaptive probing policies for shortest path routing" - 子模探测应用
5. Caragiannis et al. (2019): "The unreasonable fairness of maximum Nash welfare" - NSW公平性理论

总结

本文在多智能体多臂老虎机领域做出了重要贡献，首次系统地将主动探测机制与公平性目标结合。理论上严谨（常数因子近似和次线性遗憾），实验上充分（合成+真实数据），方法上创新（子模近似+UCB-NSW融合）。主要局限在于计算复杂度和实验规模，但不影响其学术价值和实践潜力。该工作为公平机器学习和在线决策领域开辟了新的研究方向，值得进一步探索和应用。