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

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.

Substantially revised; adds $\mathcal{O}(t^{-1})$ simple-regret upper and lower bounds and allows multiple optimal arms in the upper bound