PaperlayerView exact revision on arXiv

Source-linked AI summary

Boltzmann Exploration Done Right

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

arXiv:1705.10257v2cs.LGstat.ML

TL;DR

Boltzmann exploration is widely used, but its theoretical behavior and learning-rate tuning were poorly understood even in stochastic bandits. This paper analyzes empirical-mean Boltzmann policies, proves failure modes for monotone schedules, and introduces uncertainty-aware Gumbel-based variants. The resulting approach obtains near-optimal regret guarantees without prior knowledge of the gap or horizon, with limitations in the nonmonotone baseline and horizon dependence.

  • Problem

    Theoretical performance and appropriate learning-rate schedules for widely used empirical-mean Boltzmann exploration were poorly understood in stochastic bandits.

  • Method

    The paper analyzes monotone and nonmonotone learning-rate schedules and develops Boltzmann–Gumbel exploration with arm-specific rates that incorporate reward-estimate uncertainty.

  • Results

    Monotone schedules can be suboptimal, while Boltzmann–Gumbel exploration provides distribution-dependent and distribution-independent regret guarantees without prior knowledge of Δ or T.

  • Takeaways & Limitations

    Accounting for uncertainty in each arm’s reward estimate is the paper’s route to consistent Boltzmann-style exploration without prespecifying the gap or horizon.

  • Takeaways & Limitations

    The nonmonotone schedule requires prior knowledge of Δ and T, while the Boltzmann–Gumbel bound has suboptimal dependence on T.

Abstract

from arXiv · show

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 $Δ$). 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}Δ$ 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.

1 Introduction

Boltzmann exploration uses exponential weighting of empirical rewards, but its theoretical behavior in stochastic bandits was poorly understood. The paper establishes failures for monotone learning rates and develops remedies based on nonmonotone scheduling, uncertainty-aware rates, and Gumbel perturbations.

  • Boltzmann, Gibbs, and softmax exploration policies select arms with probabilities proportional to exponentiated empirical mean rewards.The learning rate controls the exponential weighting and is also called the inverse temperature.
  • Theoretical performance of the commonly used empirical-mean Boltzmann policy was largely unknown even for stochastic multi-armed bandits.
  • Monotone learning-rate schedules either oversample suboptimal arms or fail to identify the optimal arm.
  • A nonmonotone schedule achieves regret of order K log T / Δ^2 but requires prior knowledge of Δ and T.
  • Separate arm-specific learning rates account for reward-estimate uncertainty, while the analysis uses the Gumbel–softmax connection.

2 The stochastic multi-armed bandit problem

The paper studies stochastic multi-armed bandits, where each arm produces rewards from a distribution with a mean, and seeks algorithms whose regret grows sublinearly. Most results assume known subgaussian reward distributions.

  • Each arm i produces rewards from distribution ν_i with mean μ_i, and the optimal mean is μ* = max_i μ_i.
  • The learner repeatedly chooses an arm and observes its realized reward.
  • Performance is measured by pseudo-regret, while the goal is to construct algorithms with sublinear regret growth.
  • Most results assume each reward distribution is σ-subgaussian with known parameter σ > 0.
  • Stochastic-bandit algorithms are known to attain logarithmic regret bounds, including finite-horizon guarantees matching classic asymptotic results.

3 Boltzmann exploration done wrong

The paper shows that natural monotone Boltzmann learning-rate schedules can be fundamentally suboptimal, while a carefully staged nonmonotone schedule can achieve logarithmic regret. The latter guarantee depends on prior knowledge of the gap and horizon.

  • Boltzmann exploration done wrong: Boltzmann exploration maintains empirical mean estimates and converts them into an exponential-weights distribution using learning rates η_t.
  • Boltzmann exploration done wrong: Natural learning-rate schedules can either oversample suboptimal arms after accurate estimation or commit prematurely to a suboptimal arm.
  • Boltzmann exploration with monotone learning rates is suboptimal: Monotone schedules must increase sufficiently to reduce suboptimal-arm sampling, yet excessive early growth can cause linear regret.
  • A learning-rate schedule with near-optimal guarantees: A specific nonmonotone schedule achieves near-optimal logarithmic regret by holding the learning rate constant initially and then increasing it.This schedule is essentially an explore-then-commit strategy.
  • A learning-rate schedule with near-optimal guarantees: The nonmonotone guarantee requires prior knowledge of the suboptimality gap Δ and horizon T, which are typically unavailable.

4 Boltzmann exploration done right

Boltzmann–Gumbel exploration reformulates exponential weighting with independent Gumbel perturbations and arm-specific uncertainty scales. The resulting algorithm provides regret guarantees without prior knowledge of the gap or horizon, extends to heavy-tailed rewards, and has stated limitations in its dependence on arms and rounds.

  • Algorithm: Boltzmann–Gumbel exploration samples independent standard Gumbel perturbations and selects the arm maximizing its empirical mean plus an arm-specific scaled perturbation.The scaling factors account for uncertainty in each reward estimate, replacing the basic policy’s single learning rate.
  • Algorithm: BGE achieves near-optimal guarantees without prior knowledge of the suboptimality gap or time horizon.The algorithm is straightforward to implement even though its action probabilities lack a simple closed form.
  • Subgaussian rewards: Theorem 3 establishes a regret guarantee for BGE under σ^2-subgaussian rewards, with C and c as tunable parameters.The supplied theorem statement introduces the bound; the displayed quantitative expression is not included in full here.
  • Limitations: The stated BGE bound can be penalized exponentially when the subgaussianity constant σ is underestimated and grows suboptimally with T.The paper also notes that more sophisticated policies have better distribution-free bounds.
  • Regret guarantees: BGE has optimal dependence on T but suboptimal dependence on K, and the log K factor cannot be removed from the stated bounds.A lower bound is given for some bounded-reward bandit problems when K/T log K ≤1.
  • Heavy-tailed rewards: The heavy-tailed variant uses Catoni-based reward estimates and extends the guarantee to rewards with uniformly bounded second moments.Its bound matches Theorem 3 with σ^2 replaced by the second-moment bound V, yielding a distribution-independent bound of square-root order.

5 Analysis

The analysis decomposes suboptimal-arm selections into concentration and perturbation events, then bounds these terms using reward-estimator moment-generating functions. It treats subgaussian empirical means and extends the proof to bounded-variance heavy-tailed rewards.

  • Proof decomposition: The proof represents each perturbed estimate as eµt,i = bµt,i + βt,iZt,i and chooses the action with the largest perturbed estimate.The analysis conditions on the history of actions and rewards through the beginning of round t.
  • Proof decomposition: Suboptimal-arm draws are decomposed using thresholds xi and yi between the arm’s mean and the optimal mean.The thresholds are selected as xi = µi + ∆i/3, while the decomposition separates distinct estimation and perturbation events.
  • Proof decomposition: The first decomposition term captures competition between perturbations and fluctuations of the optimal arm’s empirical estimate.It is small when perturbations are sufficiently large and reward-estimate tails are light.
  • Proof decomposition: The last term counts poorly concentrated reward estimates and depends on the reward estimator rather than the perturbations.The proof bounds relevant terms through the moment-generating function of the reward estimates.
  • Subgaussian analysis: Lemma 1 bounds the number of draws associated with poorly concentrated estimates, while subsequent lemmas control the remaining decomposition terms.The proofs of the three stated lemmas are included in the supplementary material.
  • Subgaussian analysis: For subgaussian rewards with empirical-mean estimates, the proof applies subgaussian moment bounds to the decomposed terms and derives Theorem 3.The same argument is applied to Lemma 2 together with Lemma 3 and the standard regret expression.
  • Heavy-tailed analysis: For heavy-tailed rewards with bounded variance, the proof replaces the empirical-mean concentration step with Catoni’s bounded-variance estimate.Theorem 5 follows from the preceding arguments and Catoni’s proposition.

6 Experiments

The experiments compare Boltzmann variants with Boltzmann–Gumbel exploration and UCB under typical and deliberately misleading initial rewards. They examine whether these methods identify the optimal arm under representative and unrepresentative observations.

  • Experimental setup: The experiments use K = 10 Bernoulli arms, horizon T = 10^6, and gap Δ = 0.01, with one optimal arm.Suboptimal arms have mean 1/2, while the optimal arm has mean 1/2+Δ.
  • Methods compared: They compare BE-const, BE-log, Boltzmann–Gumbel exploration, and UCB with an exploration bonus.The Boltzmann variants differ through their inverse learning-rate parameters.
  • Experimental setup: The two scenarios use i.i.d. rewards or set arm 1’s first T0 = 5,000 rewards to zero.The second scenario simulates misleading initial observations for the optimal arm.
  • Results: Under unrepresentative initial draws, all standard Boltzmann versions fail to identify the optimal arm, whereas UCB and Boltzmann–Gumbel continue to perform well.The misleading event occurs with a small constant probability.
  • Results: Boltzmann–Gumbel performs comparably to UCB in this example and slightly outperforms it.This comparison is reported for the experiment described in the supplied passage.

A.1 The proof of Theorem 2

The proof analyzes suboptimal-arm draws after an initial phase by decomposing their probability into terms controlled through concentration and sampling-count arguments. It then combines these bounds to obtain the theorem’s result.

  • Proof of Theorem 2: The proof considers each suboptimal action i > 1 and bounds its behavior after an initial round index τ.The analysis sums over rounds t = τ + 1 through T.
  • Proof of Theorem 2: The first term is bounded using a condition established for the initial τ rounds.The proof takes expectations of three terms and sums over the subsequent rounds.
  • Proof of Theorem 2: The second term is controlled through the event that the optimal arm’s empirical mean is sufficiently low while its sampling count exceeds a threshold.The argument introduces thresholds t1 ≤ t − 1 and applies concentration bounds.
  • Proof of Theorem 2: Because the expected number of optimal-arm draws after the initial phase is large, Chernoff bounds control the probability of insufficient sampling.The proof sets a specific threshold and derives an exponential probability bound.
  • Proof of Theorem 2: Combining the bounds yields the claimed inequality for every suboptimal action i > 1.The proof concludes immediately after assembling the three terms.

A.2 The proof of Lemma 1

The proof of Lemma 1 tracks the times when an arm is sampled and bounds the resulting terms using subgaussian concentration, perturbation distributions, measurability, and elementary exponential inequalities.

  • Proof of Lemma 1: The proof indexes the rounds τk at which arm i is drawn for the k-th time.It sets τ0 = 0 and τk = T when k exceeds the total number of draws.
  • Proof of Lemma 1: At these sampling times, the identity Nτk,i = k enables a bound based on reward subgaussianity and Markov’s inequality.This controls the last term in the proof.
  • Proof of Lemma 1: The argument relies on Lemma 1 of Agrawal and Goyal and introduces Lemma 4 as an intermediate result.The supplied passages identify this prior lemma as crucial to the proof.
  • Proof of Lemma 1: The proof bounds probabilities involving empirical means by combining event inclusions, independence, and expectations of exponential quantities.Several steps use the distributional properties of the relevant random variables.
  • Proof of Lemma 1: For perturbation terms, the proof rewrites qτk,i, applies the perturbation distribution, uses measurability, and invokes 1−e^-x ≤ x.Summing over rounds and taking expectations completes the bound.
  • Proof of Lemma 1: The resulting bound follows after applying the definition of βt,i and summing the controlled terms over t.The final step uses the definition of L and bounds an indicator by 1.

A.5 The proof of Corollary 1

The corollary proof converts a suboptimal-draw bound into a distribution-independent regret bound by thresholding the gaps and decomposing regret accordingly. It then applies the stated constants to obtain the final numerical estimate.

  • Proof of Corollary 1: The number of suboptimal draws is bounded using the arguments from Section 5.1.This bound is the starting point for the corollary.
  • Proof of Corollary 1: A distribution-independent bound is obtained by choosing a gap threshold Δ and writing regret in terms of that threshold.The proof separates contributions according to whether gaps are above or below the threshold.
  • Proof of Corollary 1: The resulting expression contains a term proportional to T K A and an additional B log^2(K log^2 K) term.These terms appear in the displayed bound supplied for the corollary.
  • Proof of Corollary 1: For K ≥ 2, the proof uses the inequality stated in the passage and notes that 2A + 2B + 1 ≈ 187.63 < 200.This numerical comparison concludes the proof.

A.6 The proof of Theorem 4

The proof uses a deterministic-reward counterexample and splits on the probability of selecting the optimal arm. In one case it shows suboptimal selection occurs with constant probability, yielding a regret lower bound.

  • The proof divides the analysis according to whether P[At−1] is at most or at least 1/2.
  • When the optimal arm is selected with probability at least 1/2, a suboptimal arm is drawn with at least constant probability.
  • The probability calculation factors the events that the optimal arm is underestimated and some suboptimal arm is overestimated.
  • The resulting bound is written as T K log K, and Equation (8) handles the complementary case to complete the proof.
Loading 1705.10257v2…