Abernethy, Jacob DHazan, EladRakhlin, Alexander2023-05-232023-05-232009-01-012016-08-19https://repository.upenn.edu/handle/20.500.14332/47461We 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 nonstochastic multiarmed 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.Statistics and ProbabilityPresentation