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.
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":
- 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.
- 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