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

arXiv: https://arxiv.org/abs/2608.15365 · HTML: https://mlsanity.com/paper/2608.15365/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 25 references that are in the map.
- First posted on arXiv 15 Aug 2026.

## Builds on (most cited first, 12 of 12)

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2110.08627/) (2021)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and Beyond](https://mlsanity.com/paper/2508.13679/) (2025)
- [Optimal Top-Two Method for Best Arm Identification and Fluid Analysis](https://mlsanity.com/paper/2403.09123/) (2024)
- [Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Bandits](https://mlsanity.com/paper/2510.22819/) (2025)
- [Rate-optimal Design for Anytime Best Arm Identification](https://mlsanity.com/paper/2510.23199/) (2025)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)

## Abstract (arXiv)

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 operatornameErrt, 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 operatornameErrt: for learning rate ηt=α/√ t, operatornameErrt 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 Omega(t-2-varepsilon) for any varepsilon>0, showing that the exponent 2 is essentially tight.