Thompson Sampling and Approximate Inference

My Phan, Yasin Abbasi-Yadkori, Justin Domke

This paper provides a rigorous look at a common "shortcut" in machine learning: using approximate inference within Thompson Sampling. While Thompson Sampling is a powerhouse for decision-making under uncertainty, the authors reveal that even tiny, constant errors in how we approximate the "truth" can lead to catastrophic performance failures.

The Core Problem: Is "Close Enough" Good Enough?

Thompson Sampling (TS) is a classic algorithm for the $k$-armed bandit problem. In this scenario, an agent must choose between several actions (arms) to maximize rewards over time. TS works by maintaining a "belief" (a posterior distribution) about the reward of each arm, sampling from that belief, and picking the arm that looks best according to that sample.

In theory, TS is optimal. In practice, however, calculating that exact belief is often computationally impossible for complex models. Engineers instead rely on approximate inference—techniques like Variational Inference (VI), Markov Chain Monte Carlo (MCMC), or Ensemble Sampling—to get a "close enough" distribution.

The core question this paper asks is: If our approximation has a small, constant error, does the agent still eventually learn the best action?

Methods and the Alpha-Divergence Framework

The authors analyze this problem using the framework of $\alpha$-divergence, a generalized metric to measure the distance between two probability distributions. Different values of $\alpha$ correspond to different popular approximation methods:

  • $\alpha \to 0$: Reverse KL-divergence (commonly used in Variational Inference).
  • $\alpha \to 1$: Forward KL-divergence (used in Expectation Propagation).
  • $\alpha = 0.5$: Hellinger distance.
Target vs. Approximate Distributions across different alpha values

As seen in the distributions above, the choice of $\alpha$ drastically changes the shape of the approximate distribution (orange) relative to the target distribution (blue). Negative or zero $\alpha$ values tend to mode-seek (ignoring secondary peaks), while positive $\alpha$ values tend to mass-cover (spreading out to cover all peaks).

Key Insights: The Fragility of Thompson Sampling

The most surprising finding of the paper is that a constant error—no matter how small—can cause linear regret. In bandit theory, linear regret is a failing grade; it means the agent's total mistake count grows at the same rate as time, implying it never actually converges on the optimal strategy.

The authors identify two distinct faces of this error based on the $\alpha$ value:

  1. Under-exploration ($\alpha \le 0$): The approximation is too "narrow" or misses the peak of the true distribution entirely (mode-seeking). The agent might get stuck on a sub-optimal arm because its approximate belief doesn't even consider the possibility that the best arm is superior.
  2. Over-exploration ($\alpha > 0$): The approximation is too "spread out" (mass-covering). The agent keeps trying bad arms forever because it cannot confidently convince itself that they are truly bad.

The "Forced Exploration" Cure

For methods like Variational Inference (where $\alpha \le 0$), the primary failure mode is under-exploration. To fix this, the authors propose a modified TS algorithm that includes forced exploration.

By forcing the agent to be "dumb" and pick an arm uniformly at random with a small, decaying probability $p_t$, you ensure the posterior eventually receives enough data to concentrate on the truth. They formally prove that for $\alpha \le 0$, adding a forced exploration rate of $o(T)$ (e.g., sampling randomly for $\log T$ steps) guarantees sub-linear regret, rescuing the algorithm.

In simulated 50-armed bandit tests, standard Mean-Field Variational Inference performed poorly, exhibiting linear regret. However, once forced exploration was added, its performance drastically improved, nearly matching the gold standard of Exact Thompson Sampling.

Limitations and Future Work

While forced exploration is a powerful fix, it is not a silver bullet:

  • The $\alpha > 0$ Gap: The forced exploration cure only works for $\alpha \le 0$. If your approximation method naturally over-explores (like Expectation Propagation), adding more exploration does not help. Finding a theoretical fix for the $\alpha > 0$ case remains an open challenge.
  • Complexity of Tuning: The paper suggests an exploration rate $p_t$, but in real-world applications, choosing the exact decay rate for this probability can be practically tricky.
  • Beyond Bandits: While the theory is robust for simple $k$-armed bandits, extending these insights to more complex Reinforcement Learning scenarios—where the state dynamically changes—is a significant next step for the field.

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