An Efficient Algorithm for Bandit Linear Optimization Export

@techreport{citeulike:3038701, abstract = {We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal O∗ (√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.}, author = {Abernethy, Jacob D. and Hazan, Elad and Rakhlin, Alexander}, citeulike-article-id = {3038701}, citeulike-linkout-0 = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.pdf}, comment = {This tech report is a slight longer version of the authors subsequent COLT 2008 submission "Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization".}, day = {21}, howpublished = {Technical Report EECS-2008-18}, institution = {EECS, Berkeley}, keywords = {algorithm, bandit, bregman\_divergence, convexity, optimisation, theory}, month = {February}, posted-at = {2008-07-24 09:32:05}, priority = {0}, title = {An Efficient Algorithm for Bandit Linear Optimization}, url = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.pdf}, year = {2008} }

TY - RPRT ID - citeulike:3038701 L3 - citeulike-article-id:3038701 N2 - We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal O∗ (√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. TI - An Efficient Algorithm for Bandit Linear Optimization KW - algorithm KW - bandit KW - bregman_divergence KW - convexity KW - optimisation KW - theory N1 - This tech report is a slight longer version of the authors subsequent COLT 2008 submission "Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization". AU - Abernethy, Jacob AU - Hazan, Elad AU - Rakhlin, Alexander PY - 2008/02/21/ UR - http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-18.pdf ER -