# A Diffusion Analysis of Policy Gradient for Stochastic Bandits

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

## Key facts

- Cited by 4 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 4 of its 6 references that are in the map.
- First posted on arXiv 10 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, 4 of 4)

- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates](https://mlsanity.com/paper/2502.07141/) (2025)

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

- [A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits](https://mlsanity.com/paper/2603.26547/) (2026)
- [Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment](https://mlsanity.com/paper/2607.29593/) (2026)
- [Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime](https://mlsanity.com/paper/2610.06213/) (2026)
- [Safe Meta-Policy Design with Risk Control](https://mlsanity.com/paper/2610.10393/) (2026)

## Abstract (arXiv)

We study a continuous-time diffusion approximation of policy gradient for k-armed stochastic bandits. We prove that with a learning rate η = O(Delta2/log(n)) the regret is O(k log(k) log(n) / η) where n is the horizon and Delta the minimum gap. Moreover, we construct an instance with only logarithmically many arms for which the regret is linear unless η = O(Delta2).