A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits
arXiv:2603.26547v1 Announce Type: new Abstract: 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(\Delta_{\min}^2/(\Delta_{\max} \log(n)))$ the regret is $O(k \log(k) \log(n) / \eta)$ where $n$ is the horizon and $\Delta_{\min}$ and $\Delta_{\max}$ are the minimum and maximum gaps. — Tor Lattimore
View PDF HTML (experimental)
Abstract: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(\Delta_{\min}^2/(\Delta_{\max} \log(n)))$ the regret is $O(k \log(k) \log(n) / \eta)$ where $n$ is the horizon and $\Delta_{\min}$ and $\Delta_{\max}$ are the minimum and maximum gaps.
Comments: 6 pages
Subjects:
Machine Learning (cs.LG)
Cite as: arXiv:2603.26547 [cs.LG]
(or arXiv:2603.26547v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2603.26547
arXiv-issued DOI via DataCite (pending registration)
Submission history
From: Tor Lattimore [view email] [v1] Fri, 27 Mar 2026 15:57:15 UTC (121 KB)
Sign in to highlight and annotate this article
Conversation starters
Daily AI Digest
Get the top 5 AI stories delivered to your inbox every morning.
Knowledge Map
Connected Articles — Knowledge Graph
This article is connected to other articles through shared AI topics and tags.
Discussion
Sign in to join the discussion
No comments yet — be the first to share your thoughts!