LGMar 27
A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits
arXiv:2603.2654718.9h-index: 38
Predicted impact top 24% in LG · last 90 daysOriginality Synthesis-oriented
AI Analysis
This provides a theoretical guarantee for policy gradient in bandits, but it is incremental as it adapts existing analysis to a standard setup.
The paper tackles the problem of analyzing policy gradient methods for stochastic bandits by adapting a continuous-time analysis to discrete time, proving a regret bound of O(k log(k) log(n)/η) with a specific learning rate.
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(Î_{\min}^2/(Î_{\max} \log(n)))$ the regret is $O(k \log(k) \log(n) / η)$ where $n$ is the horizon and $Î_{\min}$ and $Î_{\max}$ are the minimum and maximum gaps.