mlsanityData to 14 Oct 2026

A Diffusion Analysis of Policy Gradient for Stochastic Bandits

arXiv 2603.10219 ↗First posted 10 Mar 2026stat.ML cs.AI cs.LGcited by 4

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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).

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.

Builds on

4 of 6 references.

References · 4

  1. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  2. 2016On Explore-Then-Commit Strategiescited by 47
  3. 2024Stochastic Gradient Succeeds for Banditscited by 10
  4. 2025Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning ratescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Banditscited by 1
  2. 2026Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environmentcited by 0
  3. 2026Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regimecited by 0
  4. 2026Safe Meta-Policy Design with Risk Controlcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits
  2. 2026How Log-Barrier Helps Exploration in Policy Optimization
  3. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs
  4. 2026Regret Analysis of Retry-Based Bandits
  5. 2025Efficient and Optimal Policy Gradient Algorithm for Corrupted Multi-armed Bandits
  6. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis
  7. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Bandits
  8. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraints