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

arXiv:2510.22819v3 Announce Type: replace Abstract: 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) = -4\sum_{i=1}^d \sqrt{p_i}$ (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 $\mathcal{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 $\mathcal{O}(t^{-1/2})$. Matching lower bounds under the same uniqueness condition show that both exponents of $t$ are tight.

Abstract: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) = -4\sum_{i=1}^d \sqrt{p_i}$ (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 $\mathcal{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 $\mathcal{O}(t^{-1/2})$. Matching lower bounds under the same uniqueness condition show that both exponents of $t$ are tight.

Machine Learning (cs.LG)

arXiv:2510.22819 [cs.LG]

(or arXiv:2510.22819v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2510.22819 Focus to learn more arXiv-issued DOI via DataCite

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.

aiqbench analysis

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

Related coverage