In the classic multi-armed bandit problem, an agent must choose between several options (arms) to maximize cumulative rewards. To do this effectively, the agent needs a way to estimate the potential of each arm while accounting for uncertainty. Traditionally, this is done using Upper Confidence Bounds (UCB) derived from general-purpose concentration inequalities like Hoeffding’s.
However, a growing body of research suggests that these general bounds are often too pessimistic. By replacing them with bounds based on Kullback-Leibler (KL) divergence, researchers have unlocked a more precise way to navigate the exploration-exploitation tradeoff, achieving what is known as information-theoretic optimality.
The Limits of Sub-Gaussian Assumptions
Standard bandit algorithms like UCB1 rely on the assumption that reward distributions are "sub-Gaussian." This allows them to use Hoeffding’s inequality to create a symmetric confidence interval around the empirical mean. While mathematically convenient, this approach ignores the specific "shape" of the reward distribution.
For example, in many real-world scenarios like click-through rate optimization or clinical trials, rewards are Bernoulli-distributed (either 0 or 1). As Sumeet Katariya, Branislav Kveton, and Csaba Szepesvari point out in Bernoulli Rank-1 Bandits for Click Feedback, the variance of a Bernoulli distribution shrinks as the mean approaches 0 or 1. A standard Hoeffding bound is "variance-agnostic"—it remains the same width regardless of whether the mean is 0.5 or 0.01. This leads to "over-exploration," where the algorithm wastes trials on arms that are clearly suboptimal.
The Geometry of Information
The shift toward KL-divergence-based bounds—often referred to as the kl-UCB approach—treats uncertainty not as a simple additive "plus-minus" factor, but as a measure of informational distance.
Instead of asking "What is the highest possible mean given this variance?", these algorithms ask: "What is the most optimistic mean $\mu$ such that the KL-divergence between my current observations and a distribution with mean $\mu$ is still statistically plausible?"
As Odalric-Ambrym Maillard and Rémi Munos demonstrated in A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences, this information-theoretic perspective provides a tighter "fit" for the reward distribution. By leveraging the specific geometry of the exponential family (which includes Bernoulli, Poisson, and Gamma distributions), kl-UCB algorithms can shrink their confidence intervals much faster than those using Hoeffding or even Bernstein inequalities.
Achieving Asymptotic Optimality
The primary advantage of using KL-based bounds is that they allow algorithms to meet the Lai-Robbins lower bound, the theoretical limit on how low regret can possibly be for a given distribution.
This optimality extends beyond simple bandits:
- Auctions: In Efficient Algorithms for Stochastic Repeated Second-price Auctions, Juliette Achddou, Olivier Cappé, and Aurélien Garivier show that variance-aware KL bounds lead to a "spectacular" reduction in regret for low-value items.
- Combinatorial Settings: Richard Combes and colleagues in Combinatorial Bandits Revisited use KL-indices to handle complex action spaces, such as graph matchings, with significantly tighter concentration.
- Thompson Sampling: Even randomized algorithms are being adapted. Junchi Yan and Anima Anandkumar introduced variants in Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits that use the negative KL-divergence to shape the sampling distribution, ensuring the agent doesn't over-estimate suboptimal arms.
Beyond Independent Rewards
The power of KL-divergence is not limited to simple, independent (i.i.d.) rewards. It has proven robust in environments with temporal dependencies. Vrettos Moulos in Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds... showed that using the KL-divergence rate of Markov chains allows for optimal allocation even when rewards are state-dependent.
Similarly, in tree-based planning, Anders Jonsson and Emilie Kaufmann utilized KL-divergence in Planning in Markov Decision Processes with Gap-Dependent Sample Complexity to maintain tighter bounds on Q-values, allowing Monte-Carlo Tree Search to find optimal policies with fewer samples.
Why It Works: The Intuition of Betting
A helpful way to understand why these bounds are so effective is through the lens of "betting." In On the near-optimality of betting confidence sets for bounded means, Shubhanshu Shekhar and Aaditya Ramdas argue that these confidence sets are near-optimal because they essentially represent the results of a sequential game.
By viewing the estimation of a mean as a process of betting against alternative hypotheses, the KL-divergence emerges naturally as the rate at which an agent's "wealth" (or evidence) grows. This information-theoretic foundation ensures that the resulting confidence intervals are as narrow as possible while still maintaining their safety guarantees, outperforming classical tools across nearly all bounded-reward scenarios.