Timezone: »
Poster
Boltzmann Exploration Done Right
Nicolò Cesa-Bianchi · Claudio Gentile · Gergely Neu · Gabor Lugosi
Boltzmann exploration is a classic strategy for sequential decision-making under uncertainty, and is one of the most standard tools in Reinforcement Learning (RL). Despite its widespread use, there is virtually no theoretical understanding about the limitations or the actual benefits of this exploration scheme. Does it drive exploration in a meaningful way? Is it prone to misidentifying the optimal actions or spending too much time exploring the suboptimal ones? What is the right tuning for the learning rate? In this paper, we address several of these questions for the classic setup of stochastic multi-armed bandits. One of our main results is showing that the Boltzmann exploration strategy with any monotone learning-rate sequence will induce suboptimal behavior. As a remedy, we offer a simple non-monotone schedule that guarantees near-optimal performance, albeit only when given prior access to key problem parameters that are typically not available in practical situations (like the time horizon $T$ and the suboptimality gap $\Delta$). More importantly, we propose a novel variant that uses different learning rates for different arms, and achieves a distribution-dependent regret bound of order $\frac{K\log^2 T}{\Delta}$ and a distribution-independent bound of order $\sqrt{KT}\log K$ without requiring such prior knowledge. To demonstrate the flexibility of our technique, we also propose a variant that guarantees the same performance bounds even if the rewards are heavy-tailed.
Author Information
Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy)
Claudio Gentile (INRIA)
Gergely Neu (Universitat Pompeu Fabra)
Gabor Lugosi (Pompeu Fabra University)

Gabor Lugosi is an ICREA research professor at the Department of Economics and Business, Pompeu Fabra University, Barcelona. He received his Ph.D. from the Hungarian Academy of Sciences in 1991. His research has mostly focused on the mathematical aspects of machine learning and related topics in probability and mathematical statistics, including combinatorial statistics, the analysis of random structures, and information theory. He is a co-author of several monographs on pattern recognition, density estimation, online learning, and concentration inequalities.
More from the Same Authors
-
2023 Poster: First- and Second-Order Bounds for Adversarial Linear Contextual Bandits »
Iuliia Olkhovskaia · Jack Mayo · Tim van Erven · Gergely Neu · Chen-Yu Wei -
2022 Poster: Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits »
Gergely Neu · Iuliia Olkhovskaia · Matteo Papini · Ludovic Schwartz -
2022 Poster: Proximal Point Imitation Learning »
Luca Viano · Angeliki Kamoutsi · Gergely Neu · Igor Krawczuk · Volkan Cevher -
2021 Invited Talk: Do We Know How to Estimate the Mean? »
Gabor Lugosi -
2021 Poster: Online learning in MDPs with linear function approximation and bandit feedback. »
Gergely Neu · Iuliia Olkhovskaia -
2020 Session: Orals & Spotlights Track 11: Learning Theory »
Dylan Foster · Nicolò Cesa-Bianchi -
2019 : Poster and Coffee Break 1 »
Aaron Sidford · Aditya Mahajan · Alejandro Ribeiro · Alex Lewandowski · Ali H Sayed · Ambuj Tewari · Angelika Steger · Anima Anandkumar · Asier Mujika · Hilbert J Kappen · Bolei Zhou · Byron Boots · Chelsea Finn · Chen-Yu Wei · Chi Jin · Ching-An Cheng · Christina Yu · Clement Gehring · Craig Boutilier · Dahua Lin · Daniel McNamee · Daniel Russo · David Brandfonbrener · Denny Zhou · Devesh Jha · Diego Romeres · Doina Precup · Dominik Thalmeier · Eduard Gorbunov · Elad Hazan · Elena Smirnova · Elvis Dohmatob · Emma Brunskill · Enrique Munoz de Cote · Ethan Waldie · Florian Meier · Florian Schaefer · Ge Liu · Gergely Neu · Haim Kaplan · Hao Sun · Hengshuai Yao · Jalaj Bhandari · James A Preiss · Jayakumar Subramanian · Jiajin Li · Jieping Ye · Jimmy Smith · Joan Bas Serrano · Joan Bruna · John Langford · Jonathan Lee · Jose A. Arjona-Medina · Kaiqing Zhang · Karan Singh · Yuping Luo · Zafarali Ahmed · Zaiwei Chen · Zhaoran Wang · Zhizhong Li · Zhuoran Yang · Ziping Xu · Ziyang Tang · Yi Mao · David Brandfonbrener · Shirli Di-Castro · Riashat Islam · Zuyue Fu · Abhishek Naik · Saurabh Kumar · Benjamin Petit · Angeliki Kamoutsi · Simone Totaro · Arvind Raghunathan · Rui Wu · Donghwan Lee · Dongsheng Ding · Alec Koppel · Hao Sun · Christian Tjandraatmadja · Mahdi Karami · Jincheng Mei · Chenjun Xiao · Junfeng Wen · Zichen Zhang · Ross Goroshin · Mohammad Pezeshki · Jiaqi Zhai · Philip Amortila · Shuo Huang · Mariya Vasileva · El houcine Bergou · Adel Ahmadyan · Haoran Sun · Sheng Zhang · Lukas Gruber · Yuanhao Wang · Tetiana Parshakova -
2017 : Poster session »
Nicolò Cesa-Bianchi -
2017 Workshop: Workshop on Prioritising Online Content »
John Shawe-Taylor · Massimiliano Pontil · Nicolò Cesa-Bianchi · Emine Yilmaz · Chris Watkins · Sebastian Riedel · Marko Grobelnik -
2017 Poster: Nonparametric Online Regression while Learning the Metric »
Ilja Kuzborskij · Nicolò Cesa-Bianchi -
2016 Poster: Efficient Second Order Online Learning by Sketching »
Haipeng Luo · Alekh Agarwal · Nicolò Cesa-Bianchi · John Langford -
2013 Poster: Online Learning with Switching Costs and Other Adaptive Adversaries »
Nicolò Cesa-Bianchi · Ofer Dekel · Ohad Shamir -
2013 Poster: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Oral: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Poster: A Gang of Bandits »
Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2012 Workshop: Multi-Trade-offs in Machine Learning »
Yevgeny Seldin · Guy Lever · John Shawe-Taylor · Nicolò Cesa-Bianchi · Yacov Crammer · Francois Laviolette · Gabor Lugosi · Peter Bartlett -
2012 Poster: On Multilabel Classification and Ranking with Partial Feedback »
Claudio Gentile · Francesco Orabona -
2012 Poster: A Linear Time Active Learning Algorithm for Link Classification »
Nicolò Cesa-Bianchi · Claudio Gentile · Fabio Vitale · Giovanni Zappella -
2012 Poster: Mirror Descent Meets Fixed Share (and feels no regret) »
Nicolò Cesa-Bianchi · Pierre Gaillard · Gabor Lugosi · Gilles Stoltz -
2012 Spotlight: On Multilabel Classification and Ranking with Partial Feedback »
Claudio Gentile · Francesco Orabona -
2011 Workshop: New Frontiers in Model Order Selection »
Yevgeny Seldin · Yacov Crammer · Nicolò Cesa-Bianchi · Francois Laviolette · John Shawe-Taylor -
2011 Poster: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Oral: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Poster: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2011 Spotlight: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2009 Workshop: Learning from Multiple Sources with Applications to Robotics »
Barbara Caputo · Nicolò Cesa-Bianchi · David R Hardoon · Gayle Leen · Francesco Orabona · Jaakko Peltonen · Simon Rogers -
2008 Poster: Linear Classification and Selective Sampling Under Low Noise Conditions »
Giovanni Cavallanti · Nicolò Cesa-Bianchi · Claudio Gentile -
2007 Poster: On higher-order perceptron algorithms »
Claudio Gentile · Fabio Vitale · Cristian Brotto