Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization

Keywords

Regret, Generalization, Computer science, Mathematical optimization, Linear programming

References

• Correction to 'Universal prediction of individual sequences' (Jul 92 1258-1270)Meir Feder, Neri Merhav, M. Gutman — 1994
• Closing the gap between bandit and full-information online optimization : high-probability regret boundAlexander Rakhlin, Ambuj Tewari, Peter L. Bartlett — 2007
• Lectures on modern convex optimization - analysis, algorithms, and engineering applicationsAharon Ben‐Tal, Arkadi Nemirovski — 2001
• High-Probability Regret Bounds for Bandit Online Linear OptimizationPeter L. Bartlett, Varsha Dani, Thomas P. Hayes — 2008
• Prediction, learning, and gamesNicolò Cesa‐Bianchi, Gábor Lugosi — 2006
• Interior-point polynomial algorithms in convex programmingYurii Nesterov, Arkadi Nemirovski — 1994
• Robbing the bandit: less regret in online geometric optimization against an adaptive adversaryVarsha Dani, Thomas P. Hayes — 2006
• Some aspects of the sequential design of experimentsHerbert Robbins — 1952
• Adaptive routing with end-to-end feedback: distributed learning and geometric approachesBaruch Awerbuch, Robert Kleinberg — 2004
• The weighted majority algorithmN. Littlestone, Manfred K. Warmuth — 1989
• Exponentiated Gradient Versus Gradient Descent for Linear PredictorsJyrki Kivinen, Manfred K. Warmuth — 1997
• A primal-dual perspective of online learning algorithmsShai Shalev‐Shwartz, Yoram Singer — 2007
• The Nonstochastic Multiarmed Bandit ProblemPeter Auer, Nicolò Cesa‐Bianchi, Yoav Freund — 2002
• The Price of Bandit Information for Online OptimizationVarsha Dani, Sham M. Kakade, Thomas P. Hayes — 2007
• Relative loss bounds for single neuronsDavid P. Helmbold, Jyrki Kivinen, Manfred K. Warmuth — 1999
• Online Convex Programming and Generalized Infinitesimal Gradient AscentMartin Zinkevich — 2003
• Efficient algorithms for online decision problemsAdam Tauman Kalai, Santosh Vempala — 2005
• Online convex optimization in the bandit setting: gradient descent without a gradientAbraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan — 2004
• Online convex optimization in the bandit setting: gradient descent without a gradientAbraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan — 2005
• Path Kernels and Multiplicative UpdatesEiji Takimoto, Manfred K. Warmuth — 2002

Cited by

• Minimax Regret of Finite Partial-Monitoring Games in Stochastic EnvironmentsGábor Bartók, Dávid Pál, Csaba Szepesvári — 2011
• Deterministic Compressed SensingA.R. Calderbank, Robert E. Schapire, Sina Jafarpour — 2011
• Beating Bandits in Gradually Evolving WorldsChao-Kai Chiang, Chia-Jung Lee, Chi-Jen Lu — 2013
• Sequential Decision Making in Non-stochastic EnvironmentsPeter L. Bartlett, Jacob Abernethy — 2011
• An Efficient Bandit Algorithm for sqrt(T) Regret in Online Multiclass Prediction?Jacob Abernethy, Alexander Rakhlin — 2009
• Learning with single view co-training and marginalized dropoutChen, Minmin — 2013
• Online algorithms for submodular minimization with combinatorial constraintsStefanie Jegelka, Jeffrey A. Bilmes — 2010
• Bandits Games and Clustering FoundationsSébastien Bubeck — 2010
• Online Bandit Learning for a Special Class of Non-Convex LossesLijun Zhang, Tianbao Yang, Rong Jin — 2015
• Online Learning of Noisy Data with KernelsNicolò Cesa‐Bianchi, Shai Shalev‐Shwartz, Ohad Shamir — 2010
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic OptimizationMehrdad Mahdavi — 2014
• Marginalizing Corrupted FeaturesLaurens van der Maaten, Minmin Chen, Stephen Tyree — 2014
• High-Probability Regret Bounds for Bandit Online Linear OptimizationPeter L. Bartlett, Varsha Dani, Thomas P. Hayes — 2008
• Bandits and Experts in Metric SpacesRobert Kleinberg, Aleksandrs Slivkins, Eli Upfal — 2013
• Minimax Policies for Combinatorial Prediction GamesJean-Yves Audibert, Sébastien Bubeck, Gábor Lugosi — 2011
• Bandits, Query Learning, and the Haystack DimensionKareem Amin, Michael Kearns, Umar Syed — 2011
• An improved upper bound on the expected regret of UCB-type policies for a matching-selection bandit problemRyo Watanabe, Atsuyoshi Nakamura, Mineichi Kudo — 2015
• No Regret Learning in Oligopolies: Cournot vs. BertrandUri Nadav, Georgios Piliouras — 2010
• New models and algorithms for bandits and marketsKareem Amin — 2015
• Spinal Cord Injury Therapy through Active LearningThomas Desautels — 2014

Related papers

• Online Convex Programming and Generalized Infinitesimal Gradient AscentMartin Zinkevich — 2003
• The Price of Bandit Information for Online OptimizationVarsha Dani, Sham M. Kakade, Thomas P. Hayes — 2007
• The Nonstochastic Multiarmed Bandit ProblemPeter Auer, Nicolò Cesa‐Bianchi, Yoav Freund — 2002
• Online convex optimization in the bandit setting: gradient descent without a gradientAbraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan — 2005
• Prediction, learning, and gamesNicolò Cesa‐Bianchi, Gábor Lugosi — 2006
• Efficient algorithms for online decision problemsAdam Tauman Kalai, Santosh Vempala — 2005
• Finite-time Analysis of the Multiarmed Bandit ProblemPeter Auer, Nicolò Cesa‐Bianchi, Paul Fischer — 2002
• Adaptive routing with end-to-end feedback: distributed learning and geometric approachesBaruch Awerbuch, Robert Kleinberg — 2004
• Logarithmic regret algorithms for online convex optimizationElad Hazan, Amit Agarwal, Satyen Kale — 2006