A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits

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 $\eta =O({\mathrm{\Delta }}_{\min }^{}\mathrm{/}({\mathrm{\Delta }}_{\max }\log (n)))$ the regret is $O(k\log (k)\log (n)\mathrm{/}\eta )$ where $n$ is the horizon and ${\mathrm{\Delta }}_{\min }$ and ${\mathrm{\Delta }}_{\max }$ are the minimum and maximum gaps.