Last Iterate Analyses of FTRL in Stochasitc Bandits

2025/10/26 by Zhan, Jingxin, Han, Yuze, Zhang, Zhihua
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2510.22819

Abstract

The convergence analysis of online learning algorithms is central to machine learning theory, where 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, a growing line of work has established the Best-of-Both-Worlds (BOBW) property of FTRL algorithms in bandit problems, showing in particular that they achieve logarithmic regret in stochastic bandits. Nevertheless, their last-iterate convergence rate has not yet been studied. Intuitively, logarithmic regret should correspond to a t^-1 last-iterate convergence rate. This paper partially confirms this intuition through theoretical analysis, showing that the Bregman divergence, defined by the regular function Ψ(p)=-4∑_i=1^d√(p_i) associated with the BOBW FTRL algorithm 1/2-Tsallis-INF (arXiv:1807.07623), between the point mass on the optimal arm and the probability distribution over the arm set obtained at iteration t, decays at a rate of t^-1/2.

Citations

• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
• Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and Beyond
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
• Best-of-Both-Worlds Linear Contextual Bandits
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
• Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm
• Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds
• Revisiting Simple Regret: Fast Rates for Returning a Good Arm
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
• Regret Bounds for Gaussian-Process Optimization in Large Domains
• Bandit Algorithms
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• More Adaptive Algorithms for Adversarial Bandits
• Causal Bandits: Learning Good Interventions via Causal Inference
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• The Nonstochastic Multiarmed Bandit Problem

Related

• A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Θ(T^2/3) and its Application to Best-of-Both-Worlds
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds
• Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm
• Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms
• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits