# A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits

arXiv: https://arxiv.org/abs/2603.26547 · HTML: https://mlsanity.com/paper/2603.26547/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 7 of its 8 references that are in the map.
- First posted on arXiv 27 Mar 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 7 of 7)

- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs](https://mlsanity.com/paper/2405.13136/) (2024)
- [Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates](https://mlsanity.com/paper/2502.07141/) (2025)
- [A Diffusion Analysis of Policy Gradient for Stochastic Bandits](https://mlsanity.com/paper/2603.10219/) (2026)
- [A Short Note on Soft-max and Policy Gradients in Bandits Problems](https://mlsanity.com/paper/2007.10297/) (2020)

## Built on by (most cited first, 1 of 1)

- [Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment](https://mlsanity.com/paper/2607.29593/) (2026)

## Abstract (arXiv)

We adapt the analysis of policy gradient for continuous time k-armed stochastic bandits by Lattimore (2026) to the standard discrete time setup. As in continuous time, we prove that with learning rate η = O(Deltamin2/(Deltamax log(n))) the regret is O(k log(k) log(n) / η) where n is the horizon and Deltamin and Deltamax are the minimum and maximum gaps.