mlsanityData to 14 Oct 2026

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

arXiv 2502.07141 ↗First posted 11 Feb 2025cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 22 of its 40 references that are in the map. First posted on arXiv 11 Feb 2025.

Builds on

22 of 40 references.

References · 22

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  4. 2015Trust Region Policy Optimizationcited by 2,580
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  6. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  8. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  9. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  10. 2020Sample Efficient Reinforcement Learning with REINFORCEcited by 86
  11. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  12. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
10 more
  1. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 48
  2. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  3. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
  4. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  5. 2023The Role of Baselines in Policy Gradient Optimizationcited by 25
  6. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  7. 2024Stochastic Gradient Succeeds for Banditscited by 10
  8. 2021An Alternate Policy Gradient Estimator for Softmax Policiescited by 9
  9. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPscited by 7
  10. 2020Regret Analysis of a Markov Policy Gradient Algorithm for Multi-arm Banditscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026A Diffusion Analysis of Policy Gradient for Stochastic Banditscited by 4
  2. 2026How Log-Barrier Helps Exploration in Policy Optimizationcited by 1
  3. 2026A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Banditscited by 1
  4. 2026Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environmentcited by 0