# Regret Analysis of a Markov Policy Gradient Algorithm for Multi-arm Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2020.

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

- [The Role of Baselines in Policy Gradient Optimization](https://mlsanity.com/paper/2301.06276/) (2023)
- [Understanding the Effect of Stochasticity in Policy Optimization](https://mlsanity.com/paper/2110.15572/) (2021)
- [Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates](https://mlsanity.com/paper/2502.07141/) (2025)
- [Actor-Critic based Improper Reinforcement Learning](https://mlsanity.com/paper/2207.09090/) (2022)
- [Improper Reinforcement Learning with Gradient-based Policy Optimization](https://mlsanity.com/paper/2102.08201/) (2021)
- [Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment](https://mlsanity.com/paper/2607.29593/) (2026)

## Abstract (arXiv)

We consider a policy gradient algorithm applied to a finite-arm bandit problem with Bernoulli rewards. We allow learning rates to depend on the current state of the algorithm, rather than use a deterministic time-decreasing learning rate. The state of the algorithm forms a Markov chain on the probability simplex. We apply Foster-Lyapunov techniques to analyse the stability of this Markov chain. We prove that if learning rates are well chosen then the policy gradient algorithm is a transient Markov chain and the state of the chain converges on the optimal arm with logarithmic or poly-logarithmic regret.