Information-Theoretic Confidence Bounds for Optimal Bandit Learning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 246 papers61 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 40 papers
  2. Version 1 · 2026-10-04 · 46 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_kl_divergence_confidence_bounds_ce8d9968,
  title = {KL-divergence confidence bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/kl-divergence-confidence-bounds/rdr_ce8d996813b0462299f77df7450d5393},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_information_theoretic_confidence_bounds__ce8d9968_v1,
  title = {Information-Theoretic Confidence Bounds for Optimal Bandit Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-theoretic-confidence-bounds-for-optimal-bandit-learning/rdr_ce8d996813b0462299f77df7450d5393/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}