arXiv:2608.15365cs.LG2026-08

1/2-Tsallis-INF算法在随机环境下能可靠识别最优臂,无需额外探索。

Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

  • 基于扩散模型构建能量函数,分析累积损失估计的波动机制。
  • 失败概率随时间以t^{-2+α²μ_{i_*}/4+ρ}速率下降,指数接近-2。
  • 首次证明该算法在不增加探索的前提下可实现高效最优臂识别。

后悔最小化(RM)与最优臂识别(BAI)是多臂赌博机中的两个基本目标。在后悔最小化算法中,1/2-Tsallis-INF 是一种典型的‘双世界最优’FTRL算法:在随机环境和对抗环境中均能实现对数级伪后悔和极小后悔,且无需预先知道环境类型。这引发了一个自然问题:该算法是否能在不增加探索的情况下,也可靠地识别出最优臂?本文在随机带宽环境下研究此问题,分析了失败概率 $ ext{Err}_t$——即基于1/2-Tsallis-INF的累计重要性加权损失估计所选出的实证最优臂与真实最优臂不同的概率。主要难点在于,当处于对数后悔尺度时,次优臂被采样的概率约为 $1/t$,导致重要性加权使累积估计量的波动与均值分离量同阶。为此,受扩散玩具模型启发,我们为最优臂与最佳竞争臂间的损失差距过程构造了一个李雅普诺夫函数,从而得到 $ ext{Err}_t$ 的多项式上界:对于学习率 $η_t=α/ ext{√}t$,有 $\text{Err}_t = O(t^{-2+α^2μ_{i_*}/4+ρ})$(任意 $ρ>0$),其中 $μ_{i_*}$ 表示真实最优臂的均值损失。同时,我们还建立了下界 $Ω(t^{-2-ε})$(任意 $ε>0$),表明指数2本质上是紧的。

原文摘要 · Abstract (English)

Regret minimization (RM) and best-arm identification (BAI) are two fundamental objectives in multi-armed bandits. Among regret-minimizing algorithms, $1/2$-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm: it achieves logarithmic pseudo-regret in stochastic bandits while retaining minimax-optimal regret in adversarial bandits, without knowing the environment in advance. This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably? We study this question in stochastic bandits by analyzing the failure probability $\operatorname{Err}_t$, defined as the probability that the empirical best arm determined by the cumulative importance-weighted loss estimates of 1/2-Tsallis-INF differs from the true optimal arm. The main difficulty is that, at the logarithmic-regret scale, suboptimal arms are sampled with probability heuristically of order $1/t$. Consequently, importance weighting causes the cumulative estimator to fluctuate on the same linear scale as its mean separation. To overcome this obstacle, guided by a diffusion toy model, we construct a Lyapunov function for the gap process between the estimated cumulative loss of the optimal arm and that of the best competing arm. This leads to polynomial upper bounds on $\operatorname{Err}_t$: for learning rate $η_t=α/\sqrt t$, $\operatorname{Err}_t$ decays at rate $t^{-2+α^2μ_{i_*}/4+ρ}$ for any $ρ>0$, where $μ_{i_*}$ denotes the mean loss of the true optimal arm. We also establish a lower bound $Ω(t^{-2-\varepsilon})$ for any $\varepsilon>0$, showing that the exponent $2$ is essentially tight.

多臂赌博机最优臂识别算法分析理论优化

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