2025-11-24T01:22:17.846878

Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need

Sarkar, Pandey, Chowdhury
Regret in stochastic multi-armed bandits traditionally measures the difference between the highest reward and either the arithmetic mean of accumulated rewards or the final reward. These conventional metrics often fail to address fairness among agents receiving rewards, particularly in settings where rewards are distributed across a population, such as patients in clinical trials. To address this, a recent body of work has introduced Nash regret, which evaluates performance via the geometric mean of accumulated rewards, aligning with the Nash social welfare function known for satisfying fairness axioms. To minimize Nash regret, existing approaches require specialized algorithm designs and strong assumptions, such as multiplicative concentration inequalities and bounded, non-negative rewards, making them unsuitable for even Gaussian reward distributions. We demonstrate that an initial uniform exploration phase followed by a standard Upper Confidence Bound (UCB) algorithm achieves near-optimal Nash regret, while relying only on additive Hoeffding bounds, and naturally extending to sub-Gaussian rewards. Furthermore, we generalize the algorithm to a broad class of fairness metrics called the $p$-mean regret, proving (nearly) optimal regret bounds uniformly across all $p$ values. This is in contrast to prior work, which made extremely restrictive assumptions on the bandit instances and even then achieved suboptimal regret bounds.
academic

Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need

基本信息

摘要

本文研究多臂老虎机（Multi-Armed Bandits, MAB）问题中的公平性问题。传统的后悔（regret）指标基于算术平均，无法保证跨用户的公平性。为解决这一问题，学界引入了基于几何平均的Nash后悔（Nash regret）指标。然而，现有最小化Nash后悔的方法需要专门的算法设计和强假设（如乘性浓度不等式、有界非负奖励），甚至不适用于高斯分布。本文证明，通过数据自适应的初始均匀探索阶段，结合标准的UCB算法，即可实现近似最优的Nash后悔，且仅依赖加性Hoeffding界，自然扩展到次高斯奖励。进一步，本文将算法推广到p-mean后悔这一广泛的公平性度量类别，在所有p值上证明了（近似）最优的后悔界，且无需先前工作的严格假设。

研究背景与动机

问题定义

  1. 核心问题：在多臂老虎机问题中，如何在最大化累积奖励的同时保证跨时间步（对应不同用户/患者）的公平性？传统的平均后悔（Average Regret）只关注总体效用，可能导致某些时间步获得极低奖励，缺乏公平性保障。
  2. 重要性：在临床试验、资源分配等应用场景中，每个时间步对应一个独立的个体（如患者）。仅优化平均效用可能导致部分个体受到不公平对待，这在伦理和社会福利层面都不可接受。
  3. 现有方法的局限性：
    • Barman et al. (2023) 提出Nash Confidence Bound (NCB)算法，但依赖乘性Hoeffding/Chernoff界，要求奖励有界且非负，不适用于高斯等一般分布，且隐含需要知道μ*的上界
    • Krishna et al. (2025) 研究p-mean后悔，但要求每个臂的期望奖励至少为 Ω̃(√k/T^(1/4))，这一假设极其严格，排除了许多实际场景，且在某些p值下后悔界次优
  4. 研究动机：开发一个通用框架，使用经典UCB算法即可实现公平性目标，无需专门设计的置信界，且适用于一般的次高斯分布，不需要对未知均值施加不切实际的假设。

核心贡献

  1. 归约框架：提出将Nash/p-mean后悔最小化归约为短暂的数据自适应均匀探索 + 标准bandit算法（如UCB）的框架，关键创新是数据自适应的停止规则
  2. 算法设计：设计Welfarist-UCB算法，通过两阶段策略：
    • Phase I：均匀探索直到满足自适应终止条件
    • Phase II：使用标准UCB索引进行探索-利用
  3. 理论保证：
    • 对Nash后悔（p=0）：达到 Õ(σ√(k/T)) 的order-optimal界，适用于σ-次高斯奖励
    • 对p∈0,1：达到 Õ(σ√(k/T)) 的order-optimal界
    • 对p∈[-1,0)：达到 Õ(k/√T)，优于Krishna et al.的 Õ(k^(3/4)T^(-1/4))
    • 对p<-1：达到 Õ(|p|k^((|p|+1)/2)/√T)，在实际相关的T范围内严格优于先前工作
  4. 技术创新：使用加性Hoeffding界而非乘性界，避免了对奖励分布的严格限制，且不需要μ*的上界
  5. 实验验证：通过数值模拟验证了算法在不同p值下的实际有效性，展示了"no-free-lunch"原则：更强的公平性要求导致更高的后悔

方法详解

任务定义

输入：

  • k个臂，每个臂i的奖励分布ρᵢ为σ-次高斯，均值μᵢ≥0（未知）
  • 时间范围T
  • 公平性参数p∈(-∞,1]

输出：每轮t∈T选择的臂Iₜ

目标：最小化p-mean后悔 RTp:=μ∗−(1T∑t=1T(E[μIt])p)1/pR^p_T := \mu^* - \left(\frac{1}{T}\sum_{t=1}^T (\mathbb{E}[\mu_{I_t}])^p\right)^{1/p} 其中μ*=maxᵢμᵢ。特别地，p=0对应Nash后悔（几何平均）。

模型架构

Phase I：数据自适应均匀探索

探索策略：

  • 每k步为一个块（block）
  • 每个块开始时，均匀随机抽取臂的排列π∈Πₖ
  • 按π(1), π(2), ..., π(k)顺序依次拉取各臂

终止条件：当存在某臂i满足以下两个条件时终止Phase I：

  1. μ^i>22σ2log⁡Tni\hat{\mu}_i > 2\sqrt{\frac{2\sigma^2\log T}{n_i}}
  2. ni>192pa2σ2log⁡T(μ^i−22σ2log⁡Tni)2n_i > \frac{192p_a^2\sigma^2\log T}{(\hat{\mu}_i - 2\sqrt{\frac{2\sigma^2\log T}{n_i}})^2}

其中：

  • nᵢ：臂i被拉取的次数
  • μ̂ᵢ：臂i观测奖励的经验均值
  • pₐ = 1 (若p≥-1)，pₐ = p (若p<-1)

关键性质（Lemma 4.1）：在高概率事件E下，Phase I持续时间τ满足 32kS≤τ≤128kS32kS \leq \tau \leq 128kS 其中 S=4pa2σ2log⁡T(μ∗)2S = \frac{4p_a^2\sigma^2\log T}{(\mu^*)^2}

这意味着每个臂被拉取Θ(1/(μ*)²)次，这是后续分析的关键。

Phase II：UCB探索-利用

使用标准UCB索引： UCBi=μ^i+22σ2log⁡Tni\text{UCB}_i = \hat{\mu}_i + 2\sqrt{\frac{2\sigma^2\log T}{n_i}}

每轮选择UCB值最大的臂。

技术创新点

1. 数据自适应终止条件的设计

创新：终止条件中的分母 (μ^i−22σ2log⁡Tni)2(\hat{\mu}_i - 2\sqrt{\frac{2\sigma^2\log T}{n_i}})^2 确保Phase I在Θ(1/(μ*)²)轮后终止，而非固定的Θ(√T)或Θ(1/μ*)轮。

合理性：

  • 当μ*较大时，需要较少探索即可识别好臂
  • 当μ*较小时，需要更多探索以区分臂的差异
  • 这种自适应性使得在Phase II中，对任何被拉取的臂i，都能保证 ξi:=22σ2log⁡Tμ∗ni≤1/2\xi_i := \frac{2\sqrt{2\sigma^2\log T}}{\mu^*\sqrt{n_i}} \leq 1/2，这是控制Nash后悔的关键

2. 使用加性Hoeffding界

与NCB的对比：

  • NCB：条件化在事件 {∀i,μi∈[μ^i−4μ^ilog⁡Tni,μ^i+4μ^ilog⁡Tni]}\{\forall i, \mu_i \in [\hat{\mu}_i - 4\sqrt{\frac{\hat{\mu}_i\log T}{n_i}}, \hat{\mu}_i + 4\sqrt{\frac{\hat{\mu}_i\log T}{n_i}}]\}，需要乘性Hoeffding界
  • 本文：条件化在事件 {∀i,μi∈[μ^i−22σ2log⁡Tni,μ^i+22σ2log⁡Tni]}\{\forall i, \mu_i \in [\hat{\mu}_i - 2\sqrt{\frac{2\sigma^2\log T}{n_i}}, \hat{\mu}_i + 2\sqrt{\frac{2\sigma^2\log T}{n_i}}]\}，仅需加性Hoeffding界

优势：

  • 加性界适用于任意次高斯分布（包括高斯、有界等）
  • 不需要奖励严格非负或有界
  • 不需要预先知道μ*的上界

3. 排列采样的等价性（Lemma B.3）

关键观察：Phase I的排列采样策略在边际分布上等价于每轮独立均匀采样，即PrIₜ=i=1/k，因此𝔼μ_{Iₜ}≥μ*/k。

技术意义：这种静态耦合（static coupling）简化了Phase I的分析，使得可以直接使用均匀采样的性质。

实验设置

数据集

本文使用合成数据进行数值模拟：

  1. Bernoulli臂：k=50个臂，均值从0.005, 1均匀随机采样
  2. 高斯臂：k=50个臂，均值从10, 1000均匀随机采样，标准差σ=20

评价指标

  • Nash后悔（p=0）：μ∗−(∏t=1TE[μIt])1/T\mu^* - (\prod_{t=1}^T \mathbb{E}[\mu_{I_t}])^{1/T}
  • p-mean后悔：μ∗−(1T∑t=1T(E[μIt])p)1/p\mu^* - (\frac{1}{T}\sum_{t=1}^T (\mathbb{E}[\mu_{I_t}])^p)^{1/p}

通过50次运行的平均奖励估计𝔼μ_{Iₜ}。

对比方法

  1. NCB (Barman et al., 2023)：使用Nash Confidence Bound索引
  2. Explore-then-UCB (Krishna et al., 2025)：固定探索阶段后使用UCB

实现细节

  • 时间范围T从较小值逐渐增加到较大值
  • 对不同的p值（p=0.5, 0, -0.5, -1.5）分别测试
  • 所有实验可通过提供的代码库复现

实验结果

主要结果

1. Nash后悔（p=0）

Bernoulli奖励（图1a）：

  • Welfarist-UCB的Nash后悔随T增加下降速度显著快于NCB
  • 验证了理论上的Õ(√(k/T))收敛率

次高斯奖励（图1b）：

  • 在高斯分布下，Welfarist-UCB仍能有效最小化Nash后悔
  • NCB在此设置下表现较差，验证了本文方法对一般分布的适用性

2. p-mean后悔的三个区间

p=0.5（0<p≤1）（图1c）：

  • Welfarist-UCB在所有T值下均优于Explore-then-UCB
  • 后悔下降速度符合理论预测的Õ(√(k/T))

p=-0.5（-1<p<0）（图1d）：

  • Welfarist-UCB显著优于Explore-then-UCB
  • 验证了Õ(k/√T)的界优于Krishna et al.的Õ(k^(3/4)T^(-1/4))

p=-1.5（p≤-1）（图1e）：

  • 更严格的公平性要求导致更高的后悔
  • Welfarist-UCB仍优于基线方法

3. 消融实验：p值的影响（图1f）

关键发现：

  • 随着p减小（公平性要求增强），p-mean后悔持续增加
  • 验证了"no-free-lunch"假说：更强的公平性以更高的后悔为代价
  • 当p→-∞（Rawlsian公平）时，后悔界变得空洞，表明极端公平性在短期内不可达

实验发现

  1. 实际有效性：Welfarist-UCB在所有测试场景下均展示出优越的实际性能
  2. 分布鲁棒性：算法对不同奖励分布（Bernoulli、高斯）均有效，验证了理论的广泛适用性
  3. 公平性-效用权衡：实验清晰展示了公平性参数p与后悔之间的权衡关系，为实际应用中选择合适的p值提供了指导
  4. 收敛速度：在所有p值区间，Welfarist-UCB的后悔下降速度均符合理论预测，且优于现有方法

相关工作

1. 多臂老虎机中的公平性

不同公平性概念：

  • 臂的公平性（Joseph et al. 2016; Patil et al. 2021）：确保不同臂被公平对待
  • 多智能体公平性（Hossain et al. 2021; Jones et al. 2023）：在每次拉取中公平分配奖励给多个智能体
  • 本文关注：跨时间的公平性，每个时间步对应一个独立个体

2. Nash后悔

Barman et al. (2023)：

  • 首次提出Nash后悔概念
  • 设计NCB算法，达到Õ(√(k/T))界
  • 局限：需要乘性浓度不等式，限制为有界非负奖励

3. p-mean福利

理论基础（Moulin 2004）：

  • p-mean函数由五个公理定义：匿名性、尺度不变性、连续性、单调性、对称性
  • 满足Pigou-Dalton转移原则（p≤1时）

Krishna et al. (2025)：

  • 研究一般p-mean后悔
  • 使用Explore-then-UCB
  • 局限：要求μᵢ≥Ω̃(√k/T^(1/4))，后悔界在某些区间次优

4. 其他相关方向

  • 线性bandit中的Nash后悔（Sawarni et al. 2024）
  • 在线Nash社会福利最大化（Zhang et al. 2024）
  • 多智能体强化学习中的公平性（Mandal & Gan 2022）
  • 隐私与公平性的交叉（Sarkar et al. 2025）：DP-NCB框架

本文相比相关工作的优势

  1. 更弱的假设：仅需μᵢ≥0和次高斯性，无需μᵢ的下界或奖励有界性
  2. 更优的界：在p∈[-1,0)时达到Õ(k/√T)，优于先前的Õ(k^(3/4)T^(-1/4))
  3. 统一框架：单一算法处理所有p值，无需针对不同p设计不同策略
  4. 技术简洁性：使用标准UCB和加性Hoeffding界，避免复杂的专门设计

结论与讨论

主要结论

  1. 理论贡献：证明了经典UCB算法结合数据自适应探索即可实现近似最优的公平性保证，无需专门的置信界设计
  2. 实践意义：使公平性感知的序贯决策更加实用和广泛适用，特别是在需要处理一般分布（如高斯）的场景
  3. "No-free-lunch"原则：更严格的公平性要求本质上增加了学习问题的难度，需要更多样本才能达到低后悔

局限性

  1. 假设限制：
    • 仍需要μᵢ≥0的假设（虽然标准，但在某些应用中可能受限）
    • 次高斯假设可能不适用于重尾分布
  2. p<-1时的界：
    • 后悔界随|p|指数增长，当T≤p²k^|p|时界变得空洞
    • 虽然在实际相关的T范围内优于先前工作，但仍有改进空间
  3. 下界缺失：
    • 对p<-1区间缺乏匹配的下界证明
    • 无法确定当前上界是否紧致
  4. 实验规模：
    • 实验主要在k=50的中等规模上进行
    • 大规模实验（k≫50）的表现未充分探索

未来方向

  1. 理论完善：
    • 证明p<-1时的匹配下界，形式化"no-free-lunch"原则
    • 探索能否进一步改进p<-1时的上界
  2. 假设放松：
    • 研究如何处理μᵢ可以为负的情况
    • 扩展到重尾或其他非次高斯分布
  3. 算法扩展：
    • 推广到上下文bandit或强化学习设置
    • 结合其他公平性概念（如个体公平性）
  4. 实际应用：
    • 在真实临床试验或资源分配场景中验证
    • 开发自适应选择p值的方法
  5. 计算效率：
    • Phase I的终止条件检查可能计算密集，探索更高效的实现

深度评价

优点

  1. 理论创新性强：
    • 数据自适应终止条件的设计巧妙，解决了UCB在Nash后悔最小化中的失败问题
    • 使用加性Hoeffding界而非乘性界是关键技术突破，显著扩展了适用范围
    • 统一处理所有p值的框架优雅且强大
  2. 实验充分性：
    • 覆盖多个p值区间（p>0, p=0, -1<p<0, p<-1）
    • 对比多个基线方法（NCB, Explore-then-UCB）
    • 包含消融实验验证"no-free-lunch"假说
  3. 结果说服力：
    • 理论界在多数情况下order-optimal或接近optimal
    • 实验结果与理论预测高度一致
    • 严格的数学证明，技术引理（如Lemma 4.1, 4.2）逻辑清晰
  4. 写作清晰度：
    • 动机阐述清楚，问题定义精确
    • 证明技巧部分（Section 4）提供了直观解释
    • 与先前工作的对比详细且公正（Remarks 3.1, 3.2, 3.3）
  5. 可复现性：
    • 提供完整代码库
    • 算法伪代码清晰（Algorithm 1）
    • 实验设置描述详细

不足

  1. 方法局限性：
    • μᵢ≥0的假设在某些应用中限制性较强（虽然Remark 2.1提供了合理辩护）
    • Phase I的终止条件涉及p²项，当|p|很大时可能导致过长的探索阶段
    • 对p<-1的界不如其他区间紧致
  2. 实验设置缺陷：
    • 仅使用合成数据，缺乏真实数据集验证
    • k=50的规模相对较小，大规模场景（k=1000+）的表现未知
    • 未探索σ值变化对算法性能的影响
  3. 分析不足：
    • 缺乏Phase I实际终止时间的实验统计（理论界是32kS到128kS，实际分布如何？）
    • 未讨论算法的计算复杂度（特别是终止条件检查）
    • 对不同μ*值下算法行为的分析不够深入
  4. 理论空白：
    • p<-1时缺乏下界，无法判断上界紧致性
    • 未探讨μ*未知时如何选择σ²（算法需要σ²作为输入）
    • log k因子在Nash后悔界中的必要性未充分讨论

影响力

  1. 对领域的贡献：
    • 显著推进了公平性感知bandit算法的理论理解
    • 证明了经典算法（UCB）在新问题上的适用性，鼓励重新审视简单方法
    • 为p-mean福利在在线学习中的应用提供了坚实理论基础
  2. 实用价值：
    • 算法简单，易于实现和部署
    • 适用于广泛的分布类型，增强了实际应用潜力
    • 提供了公平性-效用权衡的定量刻画，指导实践中p值的选择
  3. 可复现性：
    • 代码开源，算法描述清晰
    • 理论证明完整，技术引理可供后续工作参考
    • 实验设置标准化，易于复现和扩展
  4. 启发意义：
    • "No-free-lunch"原则的发现具有深刻洞察
    • 数据自适应探索的思想可能启发其他bandit变体的研究
    • 加性vs乘性浓度不等式的讨论对算法设计有方法论意义

适用场景

  1. 临床试验：需要在探索有效治疗方案的同时保证每位患者获得公平对待
  2. 资源分配：在线分配有限资源（如计算资源、广告位）给不同用户，需要平衡效率和公平性
  3. 推荐系统：向不同时间段的用户推荐内容，需要避免某些时段用户体验极差
  4. A/B测试：在产品测试中需要考虑参与者的福利，而非仅关注平均指标
  5. 教育资源分配：为不同时间入学的学生分配教育资源，需要跨批次的公平性

不适用场景：

  • 需要极端Rawlsian公平（p→-∞）的短期应用（理论界变空洞）
  • 奖励分布重尾或非次高斯的场景
  • μᵢ可能显著为负的应用

参考文献（精选）

  1. Barman et al. (2023): "Fairness and welfare quantification for regret in multi-armed bandits" - 首次提出Nash后悔概念
  2. Krishna et al. (2025): "p-mean regret for stochastic bandits" - 研究一般p-mean后悔
  3. Bubeck et al. (2012): "Regret analysis of stochastic and nonstochastic multi-armed bandit problems" - 经典MAB教材
  4. Moulin (2004): "Fair division and collective welfare" - p-mean福利的公理化基础
  5. Sawarni et al. (2024): "Nash regret guarantees for linear bandits" - 线性bandit中的Nash后悔

总体评价：这是一篇高质量的理论机器学习论文，在公平性感知bandit算法领域做出了重要贡献。通过巧妙的算法设计和严谨的理论分析，证明了简单方法（UCB）在复杂目标（公平性）上的有效性。理论结果强大，实验验证充分，对领域有显著推动作用。主要不足在于缺乏真实数据验证和某些理论空白（如p<-1的下界）。建议后续工作重点关注实际应用验证和理论完善。