2025-11-24T22:28:17.253920

Exploration-free Algorithms for Multi-group Mean Estimation

Wei, Zhong, Li
We address the problem of multi-group mean estimation, which seeks to allocate a finite sampling budget across multiple groups to obtain uniformly accurate estimates of their means. Unlike classical multi-armed bandits, whose objective is to minimize regret by identifying and exploiting the best arm, the optimal allocation in this setting requires sampling every group on the order of $Θ(T)$ times. This fundamental distinction makes exploration-free algorithms both natural and effective. Our work makes three contributions. First, we strengthen the existing results on subgaussian variance concentration using the Hanson-Wright inequality and identify a class of strictly subgaussian distributions that yield sharper guarantees. Second, we design exploration-free non-adaptive and adaptive algorithms, and we establish tighter regret bounds than the existing results. Third, we extend the framework to contextual bandit settings, an underexplored direction, and propose algorithms that leverage side information with provable guarantees. Overall, these results position exploration-free allocation as a principled and efficient approach to multi-group mean estimation, with potential applications in experimental design, personalization, and other domains requiring accurate multi-group inference.
academic

Exploration-free Algorithms for Multi-group Mean Estimation

基本信息

  • 论文ID: 2510.10374
  • 标题: Exploration-free Algorithms for Multi-group Mean Estimation
  • 作者: Ziyi Wei (Virginia Tech), Huaiyang Zhong (Virginia Tech), Xiaocheng Li (Imperial College London)
  • 分类: cs.LG, stat.ML
  • 发表时间: 2025年10月12日
  • 论文链接: https://arxiv.org/abs/2510.10374

摘要

本文研究多群体均值估计问题，旨在将有限的采样预算分配给多个群体，以获得对其均值的一致准确估计。与传统多臂老虎机不同（其目标是通过识别和利用最优臂来最小化遗憾），该设置中的最优分配需要对每个群体采样Θ(T)次。这一根本差异使得无探索算法既自然又有效。本文做出三个主要贡献：首先，使用Hanson-Wright不等式强化了亚高斯方差集中的现有结果，并识别出一类严格亚高斯分布，能产生更尖锐的保证；其次，设计了无探索的非自适应和自适应算法，建立了比现有结果更紧的遗憾界；第三，将框架扩展到上下文老虎机设置，这是一个探索不足的方向，提出了利用辅助信息的算法并给出可证明的保证。

研究背景与动机

问题定义

多群体均值估计问题要求在有限时间范围T内，将采样预算分配给K个群体，使得对所有群体均值的估计都达到一致的准确性。具体而言，对于第k个群体，其奖励分布为Pk，均值为μk，方差为σk²，目标是最小化p-范数目标：

Rp(n)=∥{σk2nk}k=1K∥pR_p(n) = \left\|\left\{\frac{\sigma_k^2}{n_k}\right\}_{k=1}^K\right\|_p

其中nk是对第k个群体的采样次数。

研究动机

  1. 实际应用需求：在民意调查、实验设计、个性化推荐等领域，需要对多个群体进行准确且公平的估计，而非仅关注最优群体。
  2. 理论挑战：与传统多臂老虎机不同，最优分配方案要求每个臂都被采样Θ(T)次，这使得传统的探索-利用权衡变得不必要。
  3. 现有方法局限：已有的UCB类算法引入了不必要的探索开销，没有充分利用问题的结构特性。

核心贡献

  1. 理论改进：基于Hanson-Wright不等式改进了亚高斯方差集中不等式，识别出严格亚高斯分布类别，获得更尖锐的理论保证。
  2. 算法设计：提出了两个无探索算法：
    • 非自适应算法（需要方差下界的先验知识）
    • 自适应算法（无需先验知识，使用置信区间）
  3. 扩展框架：首次将多群体均值估计扩展到上下文老虎机设置，提出了相应的算法并给出理论分析。
  4. 性能提升：相比现有最佳结果，在遗憾界中去除了一个log T因子，实现了更紧的理论界。

方法详解

任务定义

给定K个群体，每个群体k的奖励分布Pk具有未知均值μk和方差σk²。在时间范围T内，每个时刻选择一个群体进行采样，目标是最小化所有群体的估计误差的p-范数。

最优分配方案

命题2.1给出了理论最优分配： nk∗=σkq∑j=1Kσjq⋅Tn_k^* = \frac{\sigma_k^q}{\sum_{j=1}^K \sigma_j^q} \cdot T

其中q = 2p/(p+1)（当p有限时）或q = 2（当p = ∞时）。

算法1：非自适应分配

核心思想：分两阶段进行

  1. 第一阶段：对每个群体均匀采样τ轮，估计方差
  2. 第二阶段：根据估计的方差按最优比例分配剩余预算

关键参数：

  • 初始长度：τ=σqσq+(K−1)σ‾q⋅T\tau = \frac{\sigma^q}{\sigma^q + (K-1)\underline{\sigma}^q} \cdot T
  • 分配权重：λk,τ=σ^k,τq∑j=1Kσ^j,τq\lambda_{k,\tau} = \frac{\hat{\sigma}_{k,\tau}^q}{\sum_{j=1}^K \hat{\sigma}_{j,\tau}^q}

算法2：自适应算法

改进点：无需方差下界的先验知识，通过置信区间自适应调整。

核心机制：

  1. 置信区间构造：基于改进的方差集中不等式构造LCB和UCB
  2. 自适应停止：动态计算每个群体的停止时间
  3. 臂消除策略：类似于最优臂识别中的消除技术

置信区间：

  • LCBk,n=max⁡{σ^k,n2−εk,n+,0}LCB_{k,n} = \max\{\hat{\sigma}_{k,n}^2 - \varepsilon_{k,n}^+, 0\}
  • UCBk,n=σ^k,n2+εk,n−UCB_{k,n} = \hat{\sigma}_{k,n}^2 + \varepsilon_{k,n}^-

算法3：上下文扩展

问题设定：每个群体k关联参数向量βk，观察到上下文ct时，奖励为： Xk,n=βkTcn+ηk,nX_{k,n} = \beta_k^T c_n + \eta_{k,n}

目标函数： min⁡E[∑k=1K∥β^k,nk−βk∥2]\min \mathbb{E}\left[\sum_{k=1}^K \|\hat{\beta}_{k,n_k} - \beta_k\|^2\right]

关键创新：

  • 使用岭回归估计器
  • 先决定后观察的采样策略
  • 保持上下文向量的独立性

实验设置

数据集

  1. 高斯分布：K=4个群体，均值从U(-1,1)采样，方差为{1, 1.5, 2, 2.5}
  2. Rademacher + 高斯：复现Carpentier等人的实验设置
  3. 对称Beta分布：验证严格亚高斯性质的优势
  4. 上下文设置：K∈{5,10,20}，维度d=4，上下文从超立方体均匀采样

评价指标

  • 经验遗憾：Rp(nπ)−Rp(n∗)R_p(n^{\pi}) - R_p(n^*)
  • 理论上界的紧度
  • 算法的收敛速度

对比方法

  • 一般亚高斯（GSG）设置 vs 严格亚高斯（SSG）设置
  • 已知方差下界 vs 未知方差下界
  • 不同p值的表现对比

实验结果

主要结果

  1. 理论界的紧度：严格亚高斯设置下的理论上界与经验结果更加接近，特别是在p=∞时。
  2. 方差下界的影响：当方差下界未知时，算法性能会出现显著下降，这种下降在GSG和SSG设置中出现的时间点不同。
  3. 时间复杂度：SSG设置下第一阶段的长度显著减少，从与σ²相关降为仅依赖于log T的常数。

具体数值结果

  • 在高斯实验中，当T > 2×10⁴时，算法开始显示出理论预期的性能
  • SSG设置下的理论界比GSG设置紧约一个数量级
  • 上下文实验中，经验遗憾的斜率接近-2，与理论预测一致

消融实验

  1. 严格亚高斯 vs 一般亚高斯：严格亚高斯分布提供更好的常数因子和更简单的算法实现
  2. 不同p值的比较：p=∞时提供最紧的理论界
  3. 上下文维度的影响：随着臂数增加，性能保持稳定的缩放关系

相关工作

多群体均值估计

  • Antos等人(2008, 2010)：最早研究异方差噪声下的主动学习
  • Carpentier等人(2011)：提出UCB类算法处理无界情况
  • Aznag等人(2023)：引入p-范数目标函数并建立下界

方差集中理论

  • Hanson-Wright不等式的现代发展
  • 严格亚高斯分布的识别和性质
  • 经验Bernstein界的改进

上下文老虎机

  • 线性老虎机中的参数估计
  • 实验设计理论的应用
  • UCB类算法在上下文设置中的局限性

理论分析

主要理论结果

定理3.1（非自适应算法，p=∞）： E[Rp(nπ1)−Rp(n∗)]≤42σ2FAlg1,∞(λ,σ2)T−3/2log⁡T+o(T−3/2)\mathbb{E}[R_p(n^{\pi_1}) - R_p(n^*)] \leq 4\sqrt{2}\sigma^2 F_{Alg1,\infty}(\lambda, \sigma^2) T^{-3/2}\sqrt{\log T} + o(T^{-3/2})

定理3.2（非自适应算法，p<∞）： E[Rp(nπ1)−Rp(n∗)]≤24σ4FAlg1,p(λ,σ2)T−2log⁡T+o(T−2)\mathbb{E}[R_p(n^{\pi_1}) - R_p(n^*)] \leq 24\sigma^4 F_{Alg1,p}(\lambda, \sigma^2) T^{-2}\log T + o(T^{-2})

定理4.1（自适应算法）：提供相同阶的界，但常数因子略有不同。

关键改进

  1. 方差集中：使用Hanson-Wright不等式改进了方差估计的集中不等式，去除了一个log⁡(1/δ)\sqrt{\log(1/\delta)}因子。
  2. 严格亚高斯：识别出严格亚高斯分布类别，其中方差参数等于真实方差，提供更尖锐的界。
  3. 无探索设计：证明了UCB类探索在该问题中是多余的，因为最优解本身就要求每个臂被采样Θ(T)次。

结论与讨论

主要结论

  1. 无探索原理：多群体均值估计问题的结构使得显式探索变得不必要，这与传统多臂老虎机形成鲜明对比。
  2. 理论改进：通过改进的方差集中不等式和严格亚高斯分布的识别，实现了更紧的理论界。
  3. 算法设计：提出的算法在保持简单性的同时实现了最优的渐近性能。
  4. 扩展性：成功将框架扩展到上下文设置，开辟了新的研究方向。

局限性

  1. 分布假设：算法依赖于亚高斯假设，对于重尾分布可能不适用。
  2. 常数因子：虽然渐近最优，但常数因子在小样本情况下可能较大。
  3. 上下文限制：上下文扩展要求先决定后观察的策略，限制了实际应用的灵活性。

未来方向

  1. 结构化分布：研究如何利用更多的分布结构信息来进一步改进算法。
  2. 非参数扩展：将方法扩展到非参数设置。
  3. 实际应用：在具体应用领域（如A/B测试、临床试验）中验证算法效果。

深度评价

优点

  1. 理论贡献显著：在方差集中理论和算法设计两方面都有实质性改进。
  2. 问题洞察深刻：识别出多群体均值估计与传统老虎机问题的根本差异。
  3. 方法设计优雅：算法简单直观，易于理解和实现。
  4. 实验验证充分：通过多种分布和设置验证了理论结果。

不足

  1. 实际应用验证有限：缺乏在真实数据集上的大规模验证。
  2. 计算复杂度分析：没有详细分析算法的计算复杂度。
  3. 鲁棒性讨论不足：对于分布假设违背时的性能缺乏分析。

影响力

  1. 理论价值：为多群体推断问题提供了新的理论框架。
  2. 实用价值：在实验设计、个性化推荐等领域有直接应用价值。
  3. 可复现性：算法描述清晰，理论分析完整，具有良好的可复现性。

适用场景

  1. A/B测试：需要对多个用户群体进行公平比较的场景。
  2. 临床试验：多个治疗组的疗效评估。
  3. 市场调研：对不同人群的偏好进行准确估计。
  4. 推荐系统：个性化推荐中的多群体公平性保证。

参考文献

本文引用了多个重要的相关工作，包括：

  • Aznag et al. (2023): An active learning framework for multi-group mean estimation
  • Carpentier et al. (2011): Upper-confidence-bound algorithms for active learning in multi-armed bandits
  • Hanson-Wright不等式的相关理论工作
  • 亚高斯分布和方差集中的经典结果

该论文在理论和方法上都有重要贡献，为多群体均值估计问题提供了新的视角和有效的解决方案。无探索算法的提出颠覆了传统多臂老虎机中探索-利用的经典范式，具有重要的理论意义和实用价值。