# 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