# Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 26 Oct 2025.

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

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/2110.08627/) (2021)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Regret Bounds for Gaussian-Process Optimization in Large Domains](https://mlsanity.com/paper/2104.14113/) (2021)
- [Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games](https://mlsanity.com/paper/2311.00676/) (2023)
- [Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and Beyond](https://mlsanity.com/paper/2508.13679/) (2025)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2510.17103/) (2025)

## Built on by (most cited first, 1 of 1)

- [Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?](https://mlsanity.com/paper/2608.15365/) (2026)

## Abstract (arXiv)

The convergence analysis of online learning algorithms is central to machine learning theory, where the last-iterate convergence is particularly important, as it captures the learner's actual decisions and describes the evolution of the learning process over time. However, in multi-armed bandits, most existing algorithmic analyses mainly focus on the order of regret, while the last-iterate (simple regret) convergence rate remains less explored---especially for the widely studied Follow-the-Regularized-Leader (FTRL) algorithms. Recently, FTRL with the 1/2-Tsallis entropy regularizer Psi(p) = -4sumi=1d √pi (the 1/2-Tsallis-INF algorithm, by arXiv:1807.07623) was shown to achieve the desirable Best-of-Both-Worlds (BOBW) guarantees and perform well in both adversarial and stochastic settings. Nevertheless, its last-iterate convergence rate has not yet been fully studied. This paper studies the 1/2-Tsallis-INF algorithm in stochastic bandits and shows that its sampling simple regret decays at rate O(t-1), without requiring the optimal arm to be unique. Under a unique optimal arm, we further show that the expected Bregman divergence induced by Psi between the point mass on the optimal arm and the sampling distribution at iteration t decays at rate O(t-1/2). Matching lower bounds under the same uniqueness condition show that both exponents of t are tight.