Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning

Tong Zhang

Introduction

In the field of sequential decision-making, the tension between exploration and exploitation is often managed by two primary algorithmic families: Upper Confidence Bound (UCB) and Thompson Sampling (TS). While UCB is built on the principle of "optimism in the face of uncertainty" and offers rigorous frequentist (worst-case) regret guarantees, Thompson Sampling relies on Bayesian posterior sampling. Despite its strong empirical performance, standard Thompson Sampling often lacks the robust frequentist guarantees of UCB and can suffer from "pessimism"—a failure to explore sufficiently in adversarial or poorly specified environments.

This paper introduces Feel-Good Thompson Sampling (FGTS), a simple yet powerful modification that injects optimism directly into the Thompson Sampling framework. By adding a "Feel-Good" term to the likelihood function, FGTS bridges the gap between Bayesian sampling and frequentist optimality, achieving minimax optimal regret bounds for contextual bandits and providing a foundation for reinforcement learning.

The Problem: The Frequentist Gap in Thompson Sampling

The primary limitation of standard Thompson Sampling lies in its frequentist regret. While TS performs exceptionally well when the prior distribution matches the environment (Bayesian regret), it can fail to learn efficiently if the true environment is designed to exploit its lack of aggressive exploration. In some scenarios, the posterior distribution can become "flat," causing the algorithm to remain stuck with sub-optimal actions because it hasn't seen enough evidence to favor a potentially superior but uncertain arm. The goal of FGTS is to make Thompson Sampling as theoretically robust as UCB without losing its practical flexibility.

Methodology: Injecting Optimism

The core innovation of FGTS is a modification of the negative log-likelihood used to update the model's beliefs. In a standard setting, one might use a squared error loss to fit a model $f(\theta, x, a)$ to observed rewards $r$. FGTS modifies this loss function $L$ as follows:

$$L(\theta, x, a, r) = \eta(f(\theta, x, a) - r)^2 - \lambda f(\theta, x)$$

  • The Squared Error Term: The first term represents the standard fit, ensuring the model remains consistent with observed data.
  • The Feel-Good Term: By subtracting the predicted reward $f(\theta, x)$ (scaled by $\lambda$), the algorithm effectively biases the posterior toward parameters $\theta$ that predict higher rewards.

This modification effectively implements "Optimism in the Face of Uncertainty" within a sampling framework. To analyze this, the paper introduces a novel mathematical tool called the decoupling coefficient. This coefficient quantifies how much exploration is needed to convert estimation errors (Bellman error) into data-fitting errors (least squares error), allowing the complex bandit regret problem to be reduced to a simpler problem of online regression.

Key Results and Theoretical Bounds

The theoretical contributions of FGTS are significant, providing some of the strongest frequentist guarantees for a sampling-based algorithm to date:

  1. Finite Action Spaces: For bandits with $N$ actions and $K$ dimensions, FGTS achieves a frequentist regret bound of $O(\sqrt{KT \ln N})$, matching known minimax lower bounds.
  2. Linear Bandits: In $d$-dimensional linear bandits, FGTS achieves a regret of $O(d\sqrt{T \ln T})$. This is a notable improvement over previous Thompson Sampling bounds, which typically exhibited a sub-optimal $d^{3/2}$ dependency.
  3. Reinforcement Learning: The paper extends the FGTS framework to episodic Markov Decision Processes (MDPs). For MDPs with deterministic transitions, FGTS provides a robust framework for achieving low regret, marking a step forward in the theoretical understanding of TS in full RL environments.

Empirical Validation

While primarily theoretical, the paper validates FGTS through synthetic simulations of a non-contextual linear bandit ($d=100$). Using Stochastic Gradient Langevin Dynamics (SGLD) to sample from the modified "Feel-Good" posterior, the authors demonstrate that the algorithm is computationally feasible. In these tests, FGTS (where $\lambda > 0$) significantly outperformed standard TS (where $\lambda = 0$), reaching the maximum reward much faster and demonstrating the practical utility of the optimism bias.

Limitations and Future Directions

Despite its theoretical strengths, FGTS faces several challenges:

  • Stochastic Transitions: The current RL analysis is limited to deterministic transitions. Generalizing FGTS to stochastic MDPs remains a critical area for future research.
  • Sampling Complexity: While SGLD is effective for simple models, sampling from non-log-concave "Feel-Good" posteriors in high-dimensional, complex RL tasks remains a significant engineering challenge.
  • Structural Suboptimality: The general bounds provided may be loose for problems with highly specific structures, such as latent bandits. Refining the decoupling coefficient to account for such structures could lead to even tighter regret bounds.

Conclusion

Feel-Good Thompson Sampling offers a compelling synthesis of Bayesian sampling and frequentist optimism. By making a minor adjustment to the likelihood function, the authors provide a version of Thompson Sampling that is as theoretically robust as UCB while maintaining the practical flexibility that makes sampling-based methods attractive for complex decision-making tasks.

Summary updated

BibTeX
@article{zhang2022feel,
  author = {Tong Zhang},
  title = {{Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning}},
  journal = {SIAM J. Math. Data Sci.},
  year = {2022},
  doi = {10.1137/21m140924x},
}
Figure