Thompson Sampling and Approximate Inference

My Phan, Yasin Abbasi-Yadkori, Justin Domke

Abstract

Thompson Sampling (TS) is a cornerstone algorithm for decision-making under uncertainty, particularly in multi-armed bandit problems. However, its practical application often necessitates the use of approximate inference to handle complex posterior distributions. This paper investigates the robustness of TS to approximation errors, demonstrating that even small, constant errors in $\alpha$-divergence can lead to linear regret. We further propose a "forced exploration" mechanism that restores sub-linear regret for specific classes of approximation errors, providing a theoretical and practical safeguard for approximate TS.

Introduction

In the multi-armed bandit framework, a learner aims to maximize cumulative rewards by choosing between $k$ actions. Thompson Sampling addresses this by sampling from the posterior distribution of arm rewards and selecting the arm with the highest sample. While theoretically sound for exact inference, real-world applications often rely on approximations like Variational Inference (VI) or Markov Chain Monte Carlo (MCMC). A critical question remains: does TS maintain its performance when the posterior is only approximately known? This research proves that constant approximation errors, regardless of their magnitude, can cause TS to fail catastrophically, resulting in linear regret where the optimal action is never consistently identified.

Theoretical Framework: $\alpha$-Divergence and Approximation Error

The authors characterize approximation errors using $\alpha$-divergence, a generalized distance measure between the true posterior $p$ and the approximation $q$. By varying the parameter $\alpha$, this framework encompasses several standard inference techniques:

  • $\alpha \to 0$: Corresponds to reverse KL divergence, commonly used in Variational Inference.
  • $\alpha = 0.5$: Represents the Hellinger distance.
  • $\alpha \to 1$: Corresponds to forward KL divergence, used in Expectation Propagation.
  • $\alpha = 2$: Represents $\chi^2$ divergence.
Visualizing the impact of $\alpha$ on the approximate distribution (orange) relative to the target distribution (blue). As $\alpha$ increases, the approximation shifts from under-estimating to over-estimating the support of the target.

The choice of $\alpha$ fundamentally alters the behavior of the Thompson Sampling agent. When $\alpha$ is low (e.g., $\alpha \le 0$), the approximation tends to be "mode-seeking," potentially missing the optimal arm's mode and leading to under-exploration. Conversely, higher $\alpha$ values can lead to over-exploration, where the agent continues to sample sub-optimal arms indefinitely because the approximation places excessive mass on them.

The Failure of Approximate Thompson Sampling

The paper's core theoretical contribution (Theorems 1 and 2) establishes that for any error threshold $\epsilon > 0$, there exists an approximation satisfying $D_\alpha(p || q) \le \epsilon$ that still results in linear regret. This occurs because the algorithm can get "stuck":

  1. Under-exploration ($\alpha < 1$): If the approximation misses the optimal arm's peak, the agent may not pull that arm enough to gather the data needed for the posterior to correct itself.
  2. Over-exploration ($\alpha > 0$): If the approximation is too "broad," it may permanently assign non-zero probability to sub-optimal arms, preventing the agent from ever converging to the best policy.

Restoring Convergence via Forced Exploration

To mitigate these failures, the authors propose a modified TS algorithm. For approximations where $\alpha \le 0$ (like standard VI), they introduce a forced exploration step. With a small, time-decaying probability $p_t$, the agent ignores the posterior and selects an arm uniformly at random.

Theorem 3 proves that this simple addition is sufficient to ensure sub-linear regret ($o(T)$) for $\alpha \le 0$. The forced pulls ensure that every arm is sampled infinitely often in the limit, allowing the posterior to eventually concentrate on the true optimal arm, even if the initial approximation was poor.

Empirical Validation

The theoretical findings were validated using synthetic simulations, including 2-armed and 50-armed bandit environments. Results showed that "Naive" approximate TS often exhibited linear regret. However, the addition of forced exploration significantly improved performance, with regret curves flattening and outperforming standard approximate versions in complex environments using Variational Inference and Ensemble Sampling.

Conclusion and Future Directions

This work highlights a significant vulnerability in Thompson Sampling when paired with approximate inference. While forced exploration provides a robust fix for $\alpha \le 0$, the case for $\alpha > 0$ remains challenging, as linear regret may be unavoidable with constant approximation errors. Future research is needed to extend these insights to structured bandit problems, such as linear contextual bandits, and to further refine the tuning of exploration schedules in practical settings.

Summary updated

Abstract

We study the effects of approximate inference on the performance of Thompson sampling in the $k$-armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice. We show that even small constant inference error (in $\alpha$-divergence) can lead to poor performance (linear regret) due to under-exploration (for $\alpha<1$) or over-exploration (for $\alpha>0$) by the approximation. While for $\alpha > 0$ this is unavoidable, for $\alpha \leq 0$ the regret can be improved by adding a small amount of forced exploration even when the inference error is a large constant.
BibTeX
@inproceedings{phan2019thompson,
  author = {My Phan and Yasin Abbasi-Yadkori and Justin Domke},
  title = {{Thompson Sampling and Approximate Inference}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=rMlMcUlu744},
}
Figure