Timezone: »

 
Poster
Boltzmann Exploration Done Right
Nicolò Cesa-Bianchi · Claudio Gentile · Gergely Neu · Gabor Lugosi

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #26
in Posters Wed »
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.
Keywords: Bandit Algorithms · Reinforcement Learning
[ Paper] 

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

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