Bernoulli Bandit and Thompson Sampling Algorithm

Summary

The Beta-Bernoulli bandit is the tutorial’s running example: $K$ arms, each paying 1 (success) with unknown probability ${\theta }_k$, learned via a conjugate Beta posterior over each ${\theta }_k$. BernGreedy always plays the arm with highest posterior-mean success probability; BernTS instead draws one sample ${\hat{\theta }}_k\sim \mathrm{Beta}({\alpha }_k,{\beta }_k)$ per arm and plays the arm with the largest sample. This note gives the exact algorithm boxes, the Beta-Bernoulli conjugate update, and the general (non-conjugate) Thompson-sampling and greedy algorithms that later notes specialize to shortest-path, contextual, and linear-bandit problems.

Overview

Every algorithm in the tutorial follows the same generic “online decision algorithm” loop (Fig. 2.1): fit/update a Bayesian model from history, use it to select an action, apply the action, observe an outcome, repeat. Greedy algorithms break this into (1) estimate $\hat{\theta }$ and (2) act optimally for $\hat{\theta }$ — with no accounting for estimation uncertainty. Thompson sampling changes only step (1): instead of a point estimate, it draws $\hat{\theta }$ from the posterior distribution itself, so the randomness in $\hat{\theta }$ correctly reflects the agent’s residual uncertainty.

Main Content

The Beta-Bernoulli model (Example 3.1)

Beta-Bernoulli Bandit

There are $K$ actions. Action $k$ produces reward $1$ with probability ${\theta }_k$ and reward $0$ with probability $1-{\theta }_k$; $\theta =({\theta }_1,\dots ,{\theta }_K)$ is fixed but unknown. Each ${\theta }_k$ has an independent $\mathrm{Beta}({\alpha }_k,{\beta }_k)$ prior,

$$p({\theta }_k)=\frac{\Gamma ({\alpha }_k+{\beta }_k)}{\Gamma ({\alpha }_k)\Gamma ({\beta }_k)}{\theta }_k^{{\alpha }_k-1}(1-{\theta }_k{)}^{{\beta }_k-1}.$$

$({\alpha }_k={\beta }_k=1)$ gives the uniform prior on $[0,1]$.

Beta-Bernoulli conjugate update

Beta priors are conjugate to Bernoulli likelihoods: after playing action $x_t$ and observing reward $r_t\in \{0,1\}$,

$$({\alpha }_k,{\beta }_k)\leftarrow \{\begin{array}{ll}({\alpha }_k,{\beta }_k)& x_t\ne k\\ ({\alpha }_k,{\beta }_k)+(r_t,1-r_t)& x_t=k.\end{array}$$

$({\alpha }_k,{\beta }_k)$ are pseudo-counts: ${\alpha }_k$ (resp. ${\beta }_k$) increments by one with each observed success (resp. failure) of arm $k$. The mean is ${\alpha }_k/({\alpha }_k+{\beta }_k)$; concentration grows with ${\alpha }_k+{\beta }_k$.

The two algorithms, side by side (Algorithms 3.1-3.2)

BernGreedy $(K,\alpha ,\beta )$

For $t=1,2,\dots$:

1. Estimate model: for $k=1,\dots ,K$, set ${\hat{\theta }}_k\leftarrow {\alpha }_k/({\alpha }_k+{\beta }_k)$ (the posterior mean).
2. Select and apply action: $x_t\leftarrow \arg {\max }_k{\hat{\theta }}_k$; apply $x_t$, observe $r_t$.
3. Update distribution: $({\alpha }_{x_t},{\beta }_{x_t})\leftarrow ({\alpha }_{x_t}+r_t,{\beta }_{x_t}+1-r_t)$.

BernTS $(K,\alpha ,\beta )$

For $t=1,2,\dots$:

1. Sample model: for $k=1,\dots ,K$, draw ${\hat{\theta }}_k\sim \mathrm{Beta}({\alpha }_k,{\beta }_k)$ (a posterior sample, not the mean).
2. Select and apply action: $x_t\leftarrow \arg {\max }_k{\hat{\theta }}_k$; apply $x_t$, observe $r_t$.
3. Update distribution: $({\alpha }_{x_t},{\beta }_{x_t})\leftarrow ({\alpha }_{x_t}+r_t,{\beta }_{x_t}+1-r_t)$.

The only difference between the two algorithms is step 1. This is the general pattern: TS = greedy with the point estimate replaced by a posterior draw.

A common misconception

${\hat{\theta }}_k$ in BernTS is not a sample of the binary outcome $y_t$ that would occur if arm $k$ were played. It is a sample of the success probability ${\theta }_k$ itself — a statistically plausible parameter value, not a statistically plausible observation.

The general (non-conjugate) algorithms (Algorithms 4.1-4.2)

TS extends far beyond Beta-Bernoulli. Let the agent apply actions $x_t\in \mathcal{X}$ (possibly infinite), observe outcomes $y_t\sim q_{\theta }(\cdot \mid x_t)$, and earn reward $r_t=r(y_t)$ for known function $r$. A prior $p$ over $\theta$ is updated by Bayes’ rule.

Greedy $(\mathcal{X},p,q,r)$ — Algorithm 4.1

For $t=1,2,\dots$:

1. Estimate model: $\hat{\theta }\leftarrow {\mathbb{E}}_p[\theta ]$.
2. Select and apply action: $x_t\leftarrow \arg {\max }_{x\in \mathcal{X}}{\mathbb{E}}_{q_{\hat{\theta }}}[r(y_t)\mid x_t=x]$; apply $x_t$, observe $y_t$.
3. Update distribution: $p\leftarrow {\mathbb{P}}_{p,q}(\theta \in \cdot \mid x_t,y_t)$.

Thompson $(\mathcal{X},p,q,r)$ — Algorithm 4.2

For $t=1,2,\dots$:

1. Sample model: $\hat{\theta }\sim p$.
2. Select and apply action: $x_t\leftarrow \arg {\max }_{x\in \mathcal{X}}{\mathbb{E}}_{q_{\hat{\theta }}}[r(y_t)\mid x_t=x]$; apply $x_t$, observe $y_t$.
3. Update distribution: $p\leftarrow {\mathbb{P}}_{p,q}(\theta \in \cdot \mid x_t,y_t)$.

with the Bayes-rule update, for finite $\theta$-support, ${\mathbb{P}}_{p,q}(\theta =u\mid x_t,y_t)=\frac{p(u)q_u(y_t\mid x_t)}{{\sum }_{v}p(v)q_v(y_t\mid x_t)}$. The Beta-Bernoulli algorithms above are the special case $\mathcal{X}=\{1,\dots ,K\}$, $y_t=r_t$, $q_{\theta }(1\mid k)={\theta }_k$.

Examples

Three-armed Bernoulli bandit (Fig. 2.2, 3.1-3.2)

With posteriors concentrated near $0.6$, $0.4$ for arms 1-2 (1000 plays each) and a near-uniform posterior for arm 3 (3 plays, 1 success), a greedy algorithm locks onto arm 1 forever and never learns whether arm 3 (true mean $0.7$) is actually better. TS instead samples arms 1/2/3 with probabilities $\approx 0.82/0/0.18$ — exactly the posterior probability each is optimal — so it continues to probe arm 3 without wasting effort on arm 2 (posterior probability $\approx 0$ of being optimal). Over 1000 periods and $\theta =(0.9,0.8,0.7)$, TS’s per-period regret vanishes while greedy’s does not (Fig. 3.2).

Independent travel times / shortest path (Example 4.1)

Actions are paths through a graph; each edge $e$ has an independent log-Gaussian-distributed mean travel time ${\theta }_e$ with $\ln ({\theta }_e)\sim N({\mu }_e,{\sigma }_e^2)$, updated in closed form after each traversal by a Gaussian conjugate rule analogous to the Beta update above. The action that maximizes expected reward (minimizes expected cost) is found via Dijkstra’s algorithm on the sampled/estimated edge weights ${\hat{\theta }}_e$ — showing that Algorithms 4.1-4.2 apply even when $|\mathcal{X}|$ is exponentially large, as long as the maximization step is tractable. See Contextual and Linear Bandits for the linear/generalized-linear versions of this same pattern.

Connections

• Both algorithms instantiate the generic online-decision loop of Multi-Armed Bandits and Thompson Sampling - Overview; only the model-estimation step (mean vs. sample) differs.
• The general Algorithm 4.2 is exactly what gets specialized to the linear and generalized linear reward models in Contextual and Linear Bandits, and to cascading bandits (CascadeTS) in UCB and Greedy Algorithms for Bandits.
• When exact conjugate posteriors are unavailable (e.g. binary feedback on travel times, logistic reward models), Algorithm 4.2’s sampling step is approximated — see Approximate Thompson Sampling and Practical Extensions.
• The resulting regret behavior of BernTS vs. BernGreedy is formalized in Regret Bounds for Thompson Sampling.

See Also

• Multi-Armed Bandits and Thompson Sampling - Overview — problem setup and why greedy fails
• UCB and Greedy Algorithms for Bandits — the optimistic (UCB) alternative to sampling
• Regret Bounds for Thompson Sampling — why probability matching controls regret
• Contextual and Linear Bandits — the general algorithm applied to linear/GLM reward models