A Diffusion Analysis of Policy Gradient for Stochastic Bandits

Tor Lattimore

stat.MLMar 10, 2026

A Diffusion Analysis of Policy Gradient for Stochastic Bandits

Authors: Tor Lattimore

Organizations: Google DeepMind

Abstract

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

Figures & tables

Panel of Figure 1 — Algorithm 1: Discrete time policy gradient.

Panel of Figure 2 — Algorithm 2: Continuous time policy gradient.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: The plot shows 40 trajectories of $\pi_{t,1}$ produced by Algorithm 1 on the instance of Theorem 10 for 6 different learning rates with $\Delta_{2}=0.002$ .

Figure 2: The figure shows the results for the same experiment as in Fig. 1 but with $k=3$ , suggesting that the logarithmic number of arms used in the lower bound is needed.

Explore similar work

A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits
Mar 27, 2026Tor LattimoreMulti-Armed Bandits Policy Gradient
Google DeepMind
Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment
Jul 31, 2026Yanwei Jia, Du OuyangMulti-Armed Bandits Regret Minimization in RL
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong SAR · Department of Mathematical Sciences, Tsinghua University, Beijing, Beijing 100084, China
Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits
May 6, 2025Max Qiushi Lin, Jincheng Mei, Matin Aghaei +6Multi-Armed Bandits Policy Gradient
Simon Fraser University · Google DeepMind · Google Research +1

Abstract

Explore similar work

A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits

Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment

Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits