Approximate Thompson Sampling and Practical Extensions

Summary

Exact conjugate posteriors (Beta-Bernoulli, Gaussian-linear) are the exception, not the rule. This note covers the tutorial’s four approximate-posterior-sampling methods — Gibbs sampling, the Laplace approximation, Langevin Monte Carlo, and the bootstrap — used when models (e.g. binary feedback on log-Gaussian travel times, logistic recommendation models) aren’t conjugate; their incremental (fixed per-period compute) variants and ensemble sampling, which scales the idea to neural-network reward models; and three “make TS practical” modeling extensions — prior specification, nonstationarity, and concurrence — plus TS’s use for deep exploration in reinforcement learning (PSRL).

Overview

Every approximate method targets the same object: a sample $\hat{\theta }$ whose distribution approximates the true posterior $f_{t-1}$, for use in place of an exact conjugate draw inside Algorithm 4.2 (Bernoulli Bandit and Thompson Sampling Algorithm). The motivating running example is binary feedback on the online shortest-path problem (Example 5.1): deterministic edge travel times ${\theta }_e$ (independent Gamma-distributed) with a binary “was this route good” rating $y_t\mid \theta \sim \mathrm{Bernoulli}(1/(1+\exp ({\sum }_{e\in x_t}{\theta }_e-M)))$ — a logistic link that destroys the Gaussian/Gamma conjugacy exploited elsewhere.

Main Content

Four approximate-sampling methods

Gibbs sampling

A general MCMC method: iteratively resample each coordinate ${\hat{\theta }}_k^n\sim f_{t-1}^{n,k}(\cdot )$ — the one-dimensional conditional given the current values of all other coordinates — for $N$ sweeps, converging (under regularity) to the true joint posterior. Broadly applicable and often computationally viable because 1-D conditional sampling is easy, but can still be too slow for problems requiring thousands of simulations over hundreds of periods each.

Laplace approximation

If the target density $g(\varphi )$ is unimodal and $\ln g$ is strictly concave and sharply peaked around its mode $\bar{\varphi }$, a second-order Taylor expansion of $\ln g$ gives a Gaussian approximation $\tilde{g}(\varphi )\propto e^{-\frac{1}{2}(\varphi -\bar{\varphi }{)}^{\top }C(\varphi -\bar{\varphi })}$ with $C=-{\nabla }^2\ln g(\bar{\varphi })$ — i.e. mean $\bar{\varphi }$, covariance $C^{-1}$. Effective when the log-posterior is smooth, concave, and its mode/Hessian are cheap to compute (Chapelle & Li 2011 first used this for TS in display-ad CTR logistic regression). Not invariant to reparameterization — e.g. approximating the log-Gaussian edge-time posterior directly in $\varphi =\ln \theta$ makes the Laplace approximation exact, whereas approximating in $\theta$ itself would not be — so a good variable substitution can materially improve accuracy.

Langevin Monte Carlo (LMC)

Simulates the Langevin diffusion $d{\varphi }_t=\nabla \ln g({\varphi }_t)dt+\sqrt{2}d{B}_t$ (unique stationary distribution $g$) via the Euler discretization ${\varphi }_{n+1}={\varphi }_n+ϵ\nabla \ln g({\varphi }_n)+\sqrt{2ϵ}{W}_n$. In practice: stochastic-gradient LMC (minibatches, following Welling & Teh 2011) for efficiency, and a preconditioning matrix $A$ (e.g. the negative inverse Hessian at the mode) in ${\varphi }_{n+1}={\varphi }_n+ϵA\nabla \ln g({\varphi }_n)+\sqrt{2ϵ}{A}^{1/2}{W}_n$ to fix slow mixing when the log-posterior is ill-conditioned. In the tutorial’s binary-feedback shortest-path experiment, LMC outperforms both Laplace and bootstrap (Fig. 5.1) — evidence that the true posterior isn’t close enough to Gaussian for Laplace to be competitive there.

Bootstrap approximate sampling

Draw a hypothetical history ${\hat{\mathbb{H}}}_{t-1}$ by resampling $t-1$ action–observation pairs with replacement from the real history, draw a prior sample ${\theta }^0\sim f_0$, and solve $\hat{\theta }=\arg {\max }_{\theta }{e}^{-(\theta -{\theta }^0{)}^{\top }\Sigma (\theta -{\theta }^0)}{\hat{L}}_{t-1}(\theta )$ (the randomized-history likelihood, regularized toward ${\theta }^0$ by the prior’s covariance $\Sigma$). Early on, randomness is dominated by the prior draw ${\theta }^0$ (encouraging exploration with little data); late, it’s dominated by the bootstrap resampling of history. Nonparametric — works regardless of the posterior’s functional form — but has essentially no theoretical performance guarantee, unlike Laplace/Langevin.

Sanity check (§5.5): applying all three approximations to the Beta-Bernoulli bandit and the correlated-edge shortest-path problem — where exact TS is tractable — shows all three track exact TS’s regret closely, with Laplace typically the weakest and bootstrap/Langevin competitive with exact sampling (Figs. 5.2a-b).

Incremental implementation and ensemble sampling

Naively, each of the above methods’ per-period compute grows with $t$ because it must revisit the full history. Incremental Laplace fixes this with an online-Newton update of the posterior mode ${\bar{\theta }}_t={\bar{\theta }}_{t-1}-H_t^{-1}\nabla g_t({\bar{\theta }}_{t-1})$ and Hessian accumulator $H_t=H_{t-1}+{\nabla }^2{g}_t({\bar{\theta }}_{t-1})$ (closely related to an extended Kalman filter), giving fixed per-period compute. An analogous incremental bootstrap maintains $N$ models $({\bar{\theta }}_t^n,H_t^n)$, each fit to an independently Poisson(1)-reweighted “replica” of the data stream.

Ensemble sampling

Maintain, incrementally update, and sample from a finite ensemble of $N$ “statistically plausible” models rather than parameterizing the posterior directly — in the spirit of particle filtering, though the interaction between the ensemble and the actions selected makes the dynamics more intricate than standard particle filtering (Lu & Van Roy 2017). At each period, pick one ensemble member uniformly and act greedily on it; each member is incrementally updated (e.g. via SGD on a randomly-perturbed-prior, randomly-reweighted-data loss) to track its share of the posterior.

Ensemble sampling for active learning with a neural network (Lu & Van Roy 2017)

For a two-layer network $g_{\theta }(x)=w_2^{\top }\max (0,w_{1}x)$ with Gaussian priors on weights, $N$ independently-initialized-and-perturbed networks are each trained (a handful of SGD steps per period, on a loss regularized toward the network’s own random prior draw and using randomly-perturbed observed rewards) to approximate a posterior sample. Ensemble TS outperforms both fixed and annealed $ϵ$-greedy (Fig. 7.5) and is efficient with surprisingly few members (as few as ~30); too few members makes the algorithm behave more like plain greedy — good for short horizons but prone to premature, suboptimal convergence.

Practical modeling extensions

• Prior specification (§6.1): the prior should encode genuine plausible-value information — e.g. building a Beta prior on click-through rate for a new ad from the empirical CTR distribution of similar past ads, rather than defaulting to uniform. A misspecified prior (inconsistent with the true generative process) measurably slows learning relative to a coherent one (Fig. 6.2), directly paralleling the coherent-vs.-misspecified-TS contrast in Contextual and Linear Bandits.
• Constraints, context, caution (§6.2): time-varying admissible action sets ${\mathcal{X}}_t$ (e.g. road closures) and contextual side information $z_t$ are absorbed by constraining/augmenting the action space each period — the mechanism formalized in Contextual and Linear Bandits. A caution constraint ${\mathcal{X}}_t=\{x:\mathbb{E}[r_t\mid x_t=x]\ge \underline{r}\}$ enforces a minimum expected-reward floor while still allowing an initially-excluded action back in once related actions’ outcomes raise its estimate.
• Nonstationary systems (§6.3): when ${\theta }_t$ drifts over time, standard TS’s exploration decays to zero and it stops tracking. Nonstationary TS injects uncertainty at rate $\gamma \in [0,1]$ back into the Beta (or general) posterior update at each step, $({\alpha }_k,{\beta }_k)\leftarrow ((1-\gamma ){\alpha }_k+\gamma \overline{\alpha },\dots )$, so the algorithm never fully stops exploring; it materially outperforms stationary TS once drift sets in (Fig. 6.3), though regret can no longer be driven to zero.
• Concurrence (§6.4): when $K$ agents act simultaneously per period (e.g. $K$ commuters on the same graph) using a shared posterior, drawing $K$ independent samples per period is a natural TS extension. Per-action regret decays faster with more concurrent agents (shared observations accelerate learning) but decays more slowly per action count than fully-sequential updating would, since concurrent actions aren’t informed by each other’s outcomes within the period (Fig. 6.4).

Reinforcement learning in MDPs: PSRL and deep exploration (§7.5)

Posterior sampling for reinforcement learning (PSRL)

For a finite-horizon MDP $M=(\mathcal{S},\mathcal{A},R^M,P^M,H,\rho )$ learned over repeated episodes, maintain a posterior over the unknown reward and transition functions $(R^M,P^M)$ (e.g. Gaussian per state-action reward, Dirichlet per state-action transition — the multi-dimensional generalization of the Beta prior). At the start of each episode, draw one sample $(\hat{R},\hat{P})$, solve for its optimal policy, and follow that fixed policy for the whole episode (Strens 2000).

Sampling frequency and deep exploration (Fig. 7.6-7.7)

Sampling a new policy at every timestep within an episode (rather than once per episode) can make exploration exponentially inefficient: in an $N$-state chain MDP where only the two far ends are rewarding, per-timestep resampling is exponentially unlikely to walk all the way to either end, requiring a minimum of $2^N$ episodes before any reward is seen, whereas per-episode TS (holding one sampled policy fixed for a full episode) learns the optimal policy within a single episode. This “deep exploration” — seeking actions whose value lies in the information they reveal about future, not just immediate, reward — is essential whenever consequences are delayed, and requires the sample-once-per-episode discipline rather than fresh sampling at each decision.

PSRL is the sequential/delayed-consequence generalization of everything in this note: episodic RL reduces to an online decision problem over policies rather than single actions, and the same posterior-sampling principle — with the crucial “sample once, commit for the episode” caveat — carries over.

Connections

• These approximation methods make TS usable on exactly the non-conjugate models introduced in Contextual and Linear Bandits (logistic news recommendation) and this note’s own binary-feedback shortest-path and neural-network examples.
• Nonstationarity and caution/constraints are the same practical concerns that motivate adaptive redesign in sequential BED — cf. Sequential and Adaptive BED for the analogous “don’t stop updating” argument in the experimental-design setting.
• PSRL/deep exploration is the bandit-literature counterpart to the sequential-decision-theory framing in Q- and A-learning - Overview and Optimal Regime via Dynamic Programming: both must reason about the future value of current actions, though PSRL does so via posterior sampling over a learned MDP rather than backward-induction value functions over known dynamics.

See Also

• Bernoulli Bandit and Thompson Sampling Algorithm — the exact-conjugate case these methods approximate around
• Contextual and Linear Bandits — the logistic/GLM models motivating Laplace and Langevin approximate sampling
• Multi-Armed Bandits and Thompson Sampling - Overview — where PSRL/deep exploration fits in the broader TS story
• Sequential and Adaptive BED — the BED-side analog of “never stop exploring” under a changing or sequential model