# An Efficient Algorithm for Bandit Linear Optimization

### 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 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