Boltzmann Exploration Done Right

By Nicolò Cesa-Bianchi, Claudio Gentile, Gergely Neu, Gábor Lugosi. 2017

205 citations recorded by the source corpus.

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 in 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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “Following a Boltzmann policy over the K-values yields a practical algorithm that we call ‘K-learning’ which attains a Bayes regret upper bounded by Õ(L √ SAT ) where L is the time horizon, S is the number of states, A is the number of actions per state, and T is the total number of elapsed timesteps”
Mastering Complex Control in MOBA Games with Deep Reinforcement Learning (2019, methodology): “Based on the features extracted from game state, hero action is predicted using Boltzman exploration (Cesa-Bianchi et al. 2017), i.”
Making Sense of Reinforcement Learning and Probabilistic Inference (2020, background): “Even for an informed prior φ = ((1) 2 , 1 2 ) action selection according to the exploration strategy of Boltzmann dithering is unlikely to sample action 2 for which Eμ(2) = 0 (Levine, 2018; Cesa-Bianchi et al., 2017).”