Stochastic Gradient Succeeds for Bandits

Jincheng Mei, Zixin Zhong, Bo Dai +3

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, g…