Bandit Allocations to Instability: 新規性能指標の導入

arXiv:2602.07472v1 Announce Type: new 本稿では、複数のアーム間の試行回数の配分に関する問題に対処します。マルチアームバンドット（MAB）アルゴリズムが競合する各アーム間に試行回数を割り当てた場合、結果として生じる割り当ては非常に大きな変動を示すことがあります。これは、学習強化型プラットフォーム運用やバンドット後の統計的推論など、現代のアプリケーションにおいて特に有害です。この動機に基づき、MABアルゴリズムの新規性能指標である「割り当て変動性（Allocation Variability）」を導入します。割り当て変動性は、アームごとに試行回数の最大標準偏差を指します。 我々は、割り当て変動性と報酬最大化の正規的性能指標である損失（Regret）の間の基本的なトレードオフを確立しました。具体的には、どのアルゴリズムについても、最悪ケースの損失 $R_T$ と最悪ケースの割り当て変動性 $S_T$ は $T \rightarrow \infty$ において、$R_T \cdot S_T = \Omega(T^{\frac{3}{2}})$ を満たす必要があります（ただし $R_T = o(T)$ のとき）。これは、どのミニマックス損失最良アルゴリズムにおいても、最悪ケースの割り当て変動性が $\Theta(T)$ に達し、これが最大のスケールである必要があることを示しています。一方、最悪ケースの損失が非線形的であるアルゴリズムは、必ず ${S}_T = \omega(\sqrt{T})$ を引き受ける必要があります。 我々は、この下限が本質的に tight（きわに厳密）であることを示し、単純なチューナブルなアルゴリズム UCB-f が、古典的な UCB1 の一般化であり、パーレオ frontier $R_T \cdot S_T = \tilde{\Theta}(T^{3/2})$ 上のどの点も実現可能であることを示しました。最後に、バンドットアルゴリズムが利用される際のプラットフォーム運用および統計的推論における影響について議論します。我々の結果の副産物として、Prahraj と Khamaru（2025）の未解決問題を解決しました。

arXiv:2602.07472v1 Announce Type: new Abstract: 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=\Omega(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 $\Theta(T)$, the largest possible scale; while any algorithm with sublinear worst-case regret must necessarily incur ${S}_T= \omega(\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{\Theta}(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).