Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?
TL;DR
A Lyapunov function is constructed for the gap process between the estimated cumulative loss of the optimal arm and that of the best competing arm, and establishes a lower bound on the exponent of $\operatorname{Err}_t$ for any $\rho>0$, showing that the exponent $2$ is essentially tight.
Abstract
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 $\eta_t=\alpha/\sqrt t$, $\operatorname{Err}_t$ decays at rate $t^{-2+\alpha^2\mu_{i_*}/4+\rho}$ for any $\rho>0$, where $\mu_{i_*}$ denotes the mean loss of the true optimal arm. We also establish a lower bound $\Omega(t^{-2-\varepsilon})$ for any $\varepsilon>0$, showing that the exponent $2$ is essentially tight.