Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates

2025/02/11 by Jincheng Mei, Bo Dai, Mei, Jincheng +11
Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2502.07141

openalex publication_date 2025/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide a new understanding of the stochastic gradient bandit algorithm by showing that it converges to a globally optimal policy almost surely using any constant learning rate. This result demonstrates that the stochastic gradient algorithm continues to balance exploration and exploitation appropriately even in scenarios where standard smoothness and noise control assumptions break down. The proofs are based on novel findings about action sampling rates and the relationship between cumulative progress and noise, and extend the current understanding of how simple stochastic gradient methods behave in bandit settings.

Related

• Stochastic Gradient Succeeds for Bandits
• Beyond variance reduction: Understanding the true impact of baselines on policy optimization
• Almost sure convergence rates of stochastic gradient methods under gradient domination
• Global Convergence and Stability of Stochastic Gradient Descent
• New Convergence Aspects of Stochastic Gradient Algorithms