Linear bandits with polylogarithmic minimax regret

Josep Lumbreras, Marco Tomamichel

We study a noise model for linear stochastic bandits for which the subgaussian noise parameter vanishes linearly as we select actions on the unit sphere closer and closer to the un…