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