Bayesian Inference: Priors, Posteriors and Bandits

A bandit algorithm must decide whether to use the option that currently looks best or gather information about another. Thompson sampling makes that choice by sampling plausible reward probabilities from its current posterior beliefs.

Parameters can have distributions

Bayesian inference combines a prior $p(\theta)$ and likelihood $p(D\mid\theta)$:

$p(\theta\mid D)=\frac{p(D\mid\theta)p(\theta)}{p(D)}.$

The posterior describes parameter uncertainty conditional on the model and data. A prior is part of that model. More data can reduce its influence, but only if the likelihood is informative about the parameter in question.

Beta plus Bernoulli

The Beta density on (0,1) has kernel $\theta^{\alpha-1}(1-\theta)^{\beta-1}$ for positive shape parameters. With s successes and f failures, multiply by the Bernoulli likelihood $\theta^s(1-\theta)^f$:

$\theta\mid D\sim\operatorname{Beta}(\alpha+s,\beta+f).$

The posterior stays in the same family, which is called conjugacy. Its mean is $(\alpha+s)/(\alpha+\beta+s+f)$. For posterior shape parameters both greater than one, the mode is $(\alpha+s-1)/(\alpha+\beta+s+f-2)$. Boundary modes require separate treatment.

From a uniform Beta(1,1) prior, eight successes and two failures give Beta(9,3). The MLE is 0.8, the posterior mean is 0.75, and the interior MAP is 0.8. These answer different estimation questions.

Predict by averaging over uncertainty

The posterior predictive integrates parameters out:

$p(x_{new}\mid D)=\int p(x_{new}\mid\theta)p(\theta\mid D)d\theta.$

For one new Bernoulli trial, its success probability equals the posterior mean. For several future trials, using a fixed plug-in probability can miss dependence induced by the shared uncertain θ. The Beta-binomial predictive accounts for that uncertainty.

Gaussian conjugacy

Suppose $\mu\sim\mathcal N(\mu_0,\tau^2)$ and observations are conditionally independent $x_i\mid\mu\sim\mathcal N(\mu,\sigma^2)$ with known σ². Completing the square gives posterior variance and mean

$v_n=\left(\frac1{\tau^2}+\frac n{\sigma^2}\right)^{-1},\qquad m_n=v_n\left(\frac{\mu_0}{\tau^2}+\frac{n\bar x}{\sigma^2}\right).$

Precision, the reciprocal variance, adds. The next observation has predictive variance $\sigma^2+v_n$, combining observation noise with remaining mean uncertainty.

MAP and regularisation

The maximum a posteriori estimate maximises log likelihood plus log prior. An isotropic Gaussian prior on weights has negative log density equal to a constant plus $\|w\|^2/(2\tau^2)$. Thus MAP minimises negative log-likelihood plus an L2 penalty. The penalty coefficient depends on whether the loss is summed or averaged.

MAP supplies one parameter value. The posterior mean and posterior predictive retain different aspects of uncertainty. A credible interval assigns posterior probability to a parameter region under the specified model; it is not automatically a frequentist coverage guarantee.

Thompson sampling

Maintain a Beta posterior for each machine, initially Beta(1,1). Draw one θ from each posterior, choose the largest, observe the reward, and increment the selected arm’s success or failure count. Broad posteriors sometimes produce optimistic draws, encouraging exploration.

No finite budget guarantees discovery of the best arm with a specified confidence for every possible reward configuration. Very similar machines can require many trials. A simulated posterior probability of being best is itself a numerical estimate, conditional on the model.

Read beyond

Read the equation in context

The tutorial presents Thompson sampling as choosing actions from sampled plausible models. In the Bernoulli example, successes and failures update Beta posteriors. The sampled winner is an exploration strategy, not proof that its true reward probability is highest.

Your turn

Pull three machines and update their Beta posteriors. Compare choosing the largest posterior mean with sampling a plausible success probability for each arm. Observe both uncertainty and accumulated reward.

Coding problems