Computer Science – Learning
Scientific paper
2011-10-19
Computer Science
Learning
This paper is superseded by S. Bubeck, N. Cesa-Bianchi, and S.M. Kakade, "Towards minimax policies for online linear optimizat
Scientific paper
We provide the first algorithm for online bandit linear optimization whose regret after T rounds is of order sqrt{Td ln N} on any finite class X of N actions in d dimensions, and of order d*sqrt{T} (up to log factors) when X is infinite. These bounds are not improvable in general. The basic idea utilizes tools from convex geometry to construct what is essentially an optimal exploration basis. We also present an application to a model of linear bandits with expert advice. Interestingly, these results show that bandit linear optimization with expert advice in d dimensions is no more difficult (in terms of the achievable regret) than the online d-armed bandit problem with expert advice (where EXP4 is optimal).
Cesa-Bianchi Nicolò
Kakade Sham
No associations
LandOfFree
An Optimal Algorithm for Linear Bandits 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 An Optimal Algorithm for Linear Bandits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Algorithm for Linear Bandits will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-597559