Jacob Duncan Abernethy and Elad Hazan and Alexander Rakhlin

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-18

February 21, 2008

http://www2.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},
    Year= {2008},
    Month= {Feb},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.html
%F Abernethy:EECS-2008-18