arXiv:2602.07472cs.LGmath.OC2026-02被引 2

提出分配波动性指标,揭示强化学习中奖励与资源分配的权衡关系。

Bandit Allocational Instability

  • 定义新指标:分配波动性,衡量各臂抽取次数的标准差最大值
  • 证明下界:后悔与分配波动性乘积至少为T^{3/2}量级
  • 设计可调算法UCB-f,实现帕累托前沿上的任意平衡点

当多臂老虎机(MAB)算法在多个臂之间分配尝试时,其分配结果可能产生巨大波动。这在学习增强型平台运营和后老虎机统计推断等现代应用中尤为有害。为此,我们引入一种新的性能度量——分配波动性,即各臂抽取次数标准差的最大值。我们建立了分配波动性与经典后悔指标之间的基本权衡关系:对于任意算法,只要后悔率R_T=o(T),则最坏情况下的后悔R_T与分配波动性S_T必须满足R_T·S_T=Ω(T^{3/2})。这意味着任何最小最大后悔最优算法都必然导致最坏情况下分配波动性Θ(T),达到最大量级;而任何具有次线性最坏情况后悔的算法,其分配波动性必为ω(√T)。我们进一步证明该下界本质上是紧的,并且通过一个简单的可调算法UCB-f(UCB1的推广)可以实现帕累托前沿上任意满足R_T·S_T=tildeΘ(T^{3/2})的点。最后,我们讨论了该结果在平台运营和统计推断中的意义。作为副产品,我们解决了Praharaj和Khamaru(2025)提出的开放问题。

原文摘要 · Abstract (English)

When multi-armed bandit (MAB) algorithms allocate pulls among competing arms, the resulting allocation can exhibit huge variation. This is particularly harmful in modern applications such as learning-enhanced platform operations and post-bandit statistical inference. Thus motivated, we introduce a new performance metric of MAB algorithms termed allocation variability, which is the largest (over arms) standard deviation of an arm's number of pulls. We establish a fundamental trade-off between allocation variability and regret, the canonical performance metric of reward maximization. In particular, for any algorithm, the worst-case regret $R_T$ and worst-case allocation variability $S_T$ must satisfy $R_T \cdot S_T=Ω(T^{\frac{3}{2}})$ as $T\rightarrow\infty$, as long as $R_T=o(T)$. This indicates that any minimax regret-optimal algorithm must incur worst-case allocation variability $Θ(T)$, the largest possible scale; while any algorithm with sublinear worst-case regret must necessarily incur ${S}_T= ω(\sqrt{T})$. We further show that this lower bound is essentially tight, and that any point on the Pareto frontier $R_T \cdot S_T=\tildeΘ(T^{3/2})$ can be achieved by a simple tunable algorithm UCB-f, a generalization of the classic UCB1. Finally, we discuss implications for platform operations and for statistical inference, when bandit algorithms are used. As a byproduct of our result, we resolve an open question of Praharaj and Khamaru (2025).

多臂老虎机算法权衡资源分配

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。