An Efficient Algorithm for Bandit Linear Optimization
Jacob Duncan Abernethy, Elad Hazan and Alexander Rakhlin
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2008-18
February 21, 2008
http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.pdf
We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal $O^*(\sqrt{T})$ regret. The setting is a natural generalization of the non-stochastic multi-armed bandit problem, and the existence of an efficient optimal algorithm has been posed as an open problem in a number of recent papers. We show how the difficulties encountered by previous approaches are overcome by the use of a self-concordant potential function. Our approach presents a novel connection between online learning and interior point methods.
BibTeX citation:
@techreport{Abernethy:EECS-2008-18,
Author = {Abernethy, Jacob Duncan and Hazan, Elad and Rakhlin, Alexander},
Title = {An Efficient Algorithm for Bandit Linear Optimization},
Institution = {EECS Department, University of California, Berkeley},
Year = {2008},
Month = {Feb},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.html},
Number = {UCB/EECS-2008-18},
Abstract = {We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal $O^*(\sqrt{T})$ regret. The setting is a natural generalization of the non-stochastic multi-armed bandit problem, and the existence of an efficient optimal algorithm has been posed as an open problem in a number of recent papers. We show how the difficulties encountered by previous approaches are overcome by the use of a self-concordant potential function. Our approach presents a novel connection between online learning and interior point methods.}
}
EndNote citation:
%0 Report %A Abernethy, Jacob Duncan %A Hazan, Elad %A Rakhlin, Alexander %T An Efficient Algorithm for Bandit Linear Optimization %I EECS Department, University of California, Berkeley %D 2008 %8 February 21 %@ UCB/EECS-2008-18 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.html %F Abernethy:EECS-2008-18