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

arXiv:2608.15365v1 Announce Type: new 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^2mu{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-arepsilon}) for any arepsilon>0, showing that the exponent 2 is essentially tight.

Source: arXiv cs.LG | 2026-08-18