Towards Minimax Policies for Online Linear Optimization with Bandit Feedback


Sébastien Bubeck, Nicolo Cesa-Bianchi, Sham M. Kakade ;
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:41.1-41.14, 2012.


We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order √\emphdn log \emphN for any finite action set with \emphN actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous √\emphd factor compared to previous works, and gives a regret bound of order \emphd√\emphn log \emphn for any compact set of actions. Without further assumptions on the action set, this last bound is minimax optimal up to a logarithmic factor. Interestingly, our result also shows that the minimax regret for bandit linear optimization with expert advice in \emphd dimension is the same as for the basic \emphd-armed bandit with expert advice. Our second contribution is to show how to use the Mirror Descent algorithm to obtain computationally efficient strategies with minimax optimal regret bounds in specific examples. More precisely we study two canonical action sets: the hypercube and the Euclidean ball. In the former case, we obtain the first computationally efficient algorithm with a \emphd√\emphn regret, thus improving by a factor √\emphd log \emphn over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a √\emphdn log \emphn, again shaving off an extraneous √\emphd compared to previous works.

Related Material