A Diffusion Analysis of Policy Gradient for Stochastic Bandits

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