Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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