Computer Science – Learning
Scientific paper
2012-02-14
Computer Science
Learning
Scientific paper
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 $\sqrt{d n \log N}$ for any finite action set with $N$ actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous $\sqrt{d}$ factor compared to previous works, and gives a regret bound of order $d \sqrt{n \log n}$ 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 $d$ dimension is the same as for the basic $d$-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 $d \sqrt{n}$ regret, thus improving by a factor $\sqrt{d \log n}$ over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a $\sqrt{d n \log n}$ regret, again shaving off an extraneous $\sqrt{d}$ compared to previous works.
Bubeck Sébastien
Cesa-Bianchi Nicolò
Kakade Sham M.
No associations
LandOfFree
Towards minimax policies for online linear optimization with bandit feedback does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Towards minimax policies for online linear optimization with bandit feedback, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards minimax policies for online linear optimization with bandit feedback will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-90012