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 $η= 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)$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 $η= O(Δ_{\min}^2/…
Stochastic Gradient Succeeds for Bandits
We show that the \emph{stochastic gradient} bandit algorithm converges to a \emph{globally optimal} policy at an $O(1/t)$ rate, even with a \emph{constant} step size. Remarkably, global convergence of the stochastic grad…
A Short Note on Soft-max and Policy Gradients in Bandits Problems
This is a short communication on a Lyapunov function argument for softmax in bandit problems. There are a number of excellent papers coming out using differential equations for policy gradient algorithms in reinforcement…
reinforcement-learningReinforcement Learning (RL)An Efficient Algorithm for Deep Stochastic Contextual Bandits
In stochastic contextual bandit (SCB) problems, an agent selects an action based on certain observed context to maximize the cumulative reward over iterations. Recently there have been a few studies using a deep neural n…
Multi-Armed BanditsStochastic OptimizationSmall steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates
We provide a new understanding of the stochastic gradient bandit algorithm by showing that it converges to a globally optimal policy almost surely using \emph{any} constant learning rate. This result demonstrates that th…