mlsanityData to 14 Oct 2026

A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits

arXiv 2603.26547 ↗First posted 27 Mar 2026cs.LGcited by 1

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

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.

Key facts. Cited by 1 paper 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.

Builds on

7 of 8 references.

Closest ancestors · 2

Same direction, newest first

  1. 2026A Diffusion Analysis of Policy Gradient for Stochastic Bandits10 Mar
  2. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs21 May

Other references · 5

  1. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  2. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  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
  5. 2020A Short Note on Soft-max and Policy Gradients in Bandits Problemscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environmentcited 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. 2026Annealed Softmax Greedy in Many-Armed Bayesian Bandits
  3. 2026Regret Analysis of Retry-Based Bandits
  4. 2024Convergence of a L2 regularized Policy Gradient Algorithm for the Multi Armed Bandit
  5. 2026Vanishing L2 regularization for the softmax Multi Armed Bandit
  6. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
  7. 2025Efficient and Optimal Policy Gradient Algorithm for Corrupted Multi-armed Bandits
  8. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Bandits