When designing algorithms for sequential decision-making—such as multi-armed bandits or reinforcement learning (RL)—we want agents that explore efficiently and learn optimal policies quickly. To evaluate these agents, theorists measure regret: the difference between the rewards earned by an optimal strategy and those earned by the learning agent.
However, the machine learning community evaluates regret through two fundamentally different lenses: the Bayesian framework and the frequentist framework. For years, a significant theoretical gap has separated these two perspectives. Algorithms that excel empirically under Bayesian design principles often lack the rigorous worst-case guarantees demanded by frequentist analysis. Bridging this gap is one of the most active frontiers in learning theory.
Two Lenses on Learning Performance
To understand the gap, we must look at how each framework treats the underlying environment (such as the true reward probabilities of a bandit's arms).
- Bayesian Regret: Assumes the true environment parameters $\theta$ are drawn from a known prior distribution $\pi$. Performance is evaluated on average across all possible environments generated by this prior.
- Frequentist (Worst-Case) Regret: Assumes the true environment $\theta^*$ is fixed, unknown, and potentially adversarial. Performance must be guaranteed for every single possible environment instance, without relying on a helpful prior.
This distinction creates a practical dilemma. Bayesian exploration strategies, most notably Thompson Sampling (or Posterior Sampling), are highly favored in practice. They are computationally elegant and adapt fluidly to complex structures. However, as Tossou et al. note, while these Bayesian methods exhibit superior empirical performance, they historically lacked the rigorous worst-case frequentist guarantees provided by more conservative, optimism-based frameworks.
Why the Gap Exists: The Problem of "Exact Optimism"
The gold standard for frequentist algorithms is the Upper Confidence Bound (UCB) framework. UCB algorithms are built on the principle of optimism in the face of uncertainty. They construct deterministic, high-probability overestimates of each action's value. Because these bounds are mathematically guaranteed to contain the truth with high probability, the agent is forced to explore systematically until the worst-case scenario is ruled out.
Posterior sampling operates differently. Instead of calculating a rigid upper bound, it draws a random parameter from the current posterior distribution and acts optimally according to that sample.
As Ruitu Xu et al. explain, Thompson Sampling lacks a mechanism for exact optimism, making its uncertainty difficult to control mathematically. If the true fixed parameter $\theta^*$ happens to lie in the distant tail of the agent's prior, a vanilla Bayesian agent might sample that region so rarely that it suffers linear frequentist regret, even though its average Bayesian regret across the whole prior looks excellent. As Gouverneur et al. emphasize, theoretical guarantees derived for Bayesian regret simply do not automatically extend to frequentist scenarios.
The Mathematical Asymmetry
The gap is not just conceptual; it manifests as a stark discrepancy in the mathematical bounds themselves.
For decades, frequentist bandit algorithms have enjoyed tight, instance-dependent logarithmic regret bounds ($O(\log T)$), meaning the agent rapidly stops making mistakes. Conversely, finite-time Bayesian regret analyses were frequently trapped at coarser square-root bounds ($O(\sqrt{T})$).
This created a theoretical paradox: incorporating a prior distribution (adding information) seemed to result in looser proven convergence rates. Atsidakou et al. point out that bridging this gap requires integrating frequentist instance-dependent regret over a continuous distribution of possible reward gaps—a task fraught with measure-theoretic difficulties (Lattimore et al.).
Mechanisms for Closing the Gap
To combine the practical agility of Bayesian sampling with the safety nets of frequentist guarantees, researchers have developed several core mechanisms to bridge the gap.
1. Injecting "Feel-Good" Optimism
If vanilla posterior sampling fails frequentist metrics because it isn't reliably optimistic, one solution is to force optimism directly into the Bayesian update.
Zhang et al. introduced Feel-Good Thompson Sampling (FGTS). FGTS modifies the standard posterior distribution by adding an explicit reward-bias term. This modification artificially boosts the likelihood of actions that have performed well, ensuring the randomized agent maintains enough aggressive exploration to satisfy minimax-optimal frequentist regret bounds, even in adversarial environments.
2. Optimistic Posterior Sampling
In reinforcement learning, navigating large state spaces makes worst-case guarantees even harder to secure. Agrawal et al. bypassed this by designing an optimistic variant of Posterior Sampling for Reinforcement Learning (PSRL). Instead of taking a single sample from the posterior to build an environment model, their algorithm takes multiple samples from a boosted posterior to construct an extended, optimistic Markov Decision Process (MDP), successfully matching frequentist lower bounds.
3. Swapping Samples for Quantiles
Rather than sampling randomly from the posterior distribution, why not exploit its shape deterministically? The BUCRL algorithm, introduced by Tossou et al., replaces the random sampling step of Thompson Sampling with posterior quantiles. By selecting actions based on upper quantiles of the posterior, the algorithm behaves like a UCB variant but retains the fluid, data-driven benefits of a Bayesian posterior update, achieving near-optimal frequentist regret.
4. Randomized Value Functions
In model-free RL, the connection can be bridged by injecting structured noise directly into value function updates. Russo demonstrated that adding Gaussian noise to training data in Randomized Least Squares Value Iteration (RLSVI) induces "sufficient optimism." This proof demonstrates that randomized exploration can be tethered to rigorous frequentist guarantees without needing explicit, computationally heavy confidence bounds.
Summary
The ongoing synthesis of Bayesian and frequentist analysis allows modern learning theory to move past historical trade-offs. By modifying posterior distributions to guarantee optimism or leveraging information-theoretic complexities like the eluder dimension (Russo et al.), researchers are successfully designing agents that are both empirically flexible and theoretically bulletproof.