# Boltzmann Exploration Done Right

arXiv: https://arxiv.org/abs/1705.10257 · HTML: https://mlsanity.com/paper/1705.10257/

## Key facts

- Cited by 69 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2017.

## Built on by (most cited first, 30 of 69)

- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF](https://mlsanity.com/paper/2405.19320/) (2024)
- [Stochastic Batch Acquisition: A Simple Baseline for Deep Active Learning](https://mlsanity.com/paper/2106.12059/) (2021)
- [Robust Multi-Agent Reinforcement Learning with State Uncertainty](https://mlsanity.com/paper/2307.16212/) (2023)
- [Modeling Content Creator Incentives on Algorithm-Curated Platforms](https://mlsanity.com/paper/2206.13102/) (2022)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximization](https://mlsanity.com/paper/2412.12098/) (2024)
- [An information-theoretic perspective on intrinsic motivation in reinforcement learning: a survey](https://mlsanity.com/paper/2209.08890/) (2022)
- [Latent Exploration for Reinforcement Learning](https://mlsanity.com/paper/2305.20065/) (2023)
- [Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods](https://mlsanity.com/paper/2502.01618/) (2025)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [NextBestPath: Efficient 3D Mapping of Unseen Environments](https://mlsanity.com/paper/2502.05378/) (2025)
- [RTDK-BO: High Dimensional Bayesian Optimization with Reinforced Transformer Deep kernels](https://mlsanity.com/paper/2310.03912/) (2023)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Inverse Decision Modeling: Learning Interpretable Representations of Behavior](https://mlsanity.com/paper/2310.18591/) (2023)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [Accelerated Reinforcement Learning for Temporal Logic Control Objectives](https://mlsanity.com/paper/2205.04424/) (2022)
- [Practical Bandits: An Industry Perspective](https://mlsanity.com/paper/2302.01223/) (2023)
- [Pearl: A Production-ready Reinforcement Learning Agent](https://mlsanity.com/paper/2312.03814/) (2023)
- [DynamixSFT: Dynamic Mixture Optimization of Instruction Tuning Collections](https://mlsanity.com/paper/2508.12116/) (2025)
- [Top-k eXtreme Contextual Bandits with Arm Hierarchy](https://mlsanity.com/paper/2102.07800/) (2021)
- [Quantifying Availability and Discovery in Recommender Systems via Stochastic Reachability](https://mlsanity.com/paper/2107.00833/) (2021)
- [SOMBRL: Scalable and Optimistic Model-Based RL](https://mlsanity.com/paper/2511.20066/) (2025)
- [Optimal scheduling of entropy regulariser for continuous-time linear-quadratic reinforcement learning](https://mlsanity.com/paper/2208.04466/) (2022)
- [FedHQL: Federated Heterogeneous Q-Learning](https://mlsanity.com/paper/2301.11135/) (2023)
- [Random Latent Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.13755/) (2024)
- [Conflict-free collective stochastic decision making by orbital angular momentum of photons through quantum interference](https://mlsanity.com/paper/2107.00877/) (2021)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [How Should We Meta-Learn Reinforcement Learning Algorithms?](https://mlsanity.com/paper/2507.17668/) (2025)

## Abstract (arXiv)

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 fracKlog2 TDelta and a distribution-independent bound of order √KTlog 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.