不依赖探索的算法实现多组均值估计,提升精度与效率
Exploration-free Algorithms for Multi-group Mean Estimation
- 不依赖探索,直接按需分配采样次数
- 在有限预算下实现各组均值估计误差更小
- 适合实验设计与个性化推荐等场景
我们研究多组均值估计问题,旨在有限采样预算下对多个群体的均值进行统一精确估计。与传统多臂老虎机侧重于识别最优臂并减少累积损失不同,该问题最优采样策略要求每个组都采样约 Θ(T) 次。这一本质差异使得无需探索的算法既自然又高效。本文贡献包括:第一,利用Hanson-Wright不等式强化次高斯方差集中性结果,识别出一类严格次高斯分布可获得更优保证;第二,设计了无需探索的非自适应与自适应算法,并建立了比现有方法更紧的后悔界;第三,将框架拓展至上下文老虎机场景,提出利用辅助信息的算法并提供可证明性能保障。整体上,这些成果确立了无需探索的采样分配是一种有理论依据且高效的多组均值估计方法,适用于实验设计、个性化等需要多组推断的领域。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。