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

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

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.

Machine Learning (cs.LG)

arXiv:2608.15365 [cs.LG]

(or arXiv:2608.15365v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2608.15365 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.