---
title: "Bandit Exploration Algorithms"
module: Foundations
moduleNumber: 1
lessonNumber: 4
order: 104
summary: >
  Better ways to explore than picking at random. Upper-confidence-bound selection
  explores by optimism about what it hasn't measured; gradient bandits learn action
  preferences by stochastic gradient ascent on reward. We then add context to get
  the contextual bandit, the bridge to full RL, and measure everything by regret —
  where UCB1 and Thompson sampling reach the logarithmic optimum that fixed-ε greedy
  cannot.
topics: [Foundations]
sources:
  - book: Sutton & Barto
    ref: "§2.7 Upper-Confidence-Bound Action Selection; §2.8 Gradient Bandit Algorithms; §2.9 Associative Search"
---

This builds on [Multi-Armed Bandits](/reinforcement-learning/foundations/multi-armed-bandits),
which set up the k-armed bandit, sample-average value estimates, the incremental
update rule, ε-greedy exploration, and optimistic initialization. Those methods all
explore bluntly — uniformly at random, or once at the start. Here we look at
exploration that is targeted by uncertainty, and at how to measure exploration well.

## Upper-confidence-bound selection

ε-greedy exploration is blunt: when it explores, it picks uniformly at random,
with no preference for actions that are nearly greedy or that carry high
uncertainty. It would be better to explore among the non-greedy actions
according to how likely each one is to actually be optimal — weighing both how
close its estimate is to the maximum and how uncertain that estimate is.
**Upper-confidence-bound** (UCB) selection does exactly this:

$$
A_t \doteq \arg\max_a\left[\, Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}} \,\right],
$$

where $N_t(a)$ is the number of times $a$ has been selected before $t$, and
$c > 0$ controls the degree of exploration. (If $N_t(a) = 0$, then $a$ is treated
as a maximizing action, so every arm is tried once at the start.) The square-root
term is a measure of the uncertainty in the estimate of $a$'s value: it is an
_upper bound_ on how good $a$ might plausibly be, with $c$ setting the confidence
level.

The dynamics are self-correcting. Each time $a$ is selected, $N_t(a)$ grows and
the uncertainty term shrinks. Each time some _other_ action is selected, $t$
grows but $N_t(a)$ does not, so $a$'s uncertainty term slowly rises — the arm
gets a nudge back up for having been neglected. Because $\ln t$ grows without
bound but ever more slowly, all actions are eventually selected, but those with
lower estimates or that have already been sampled often are chosen with
decreasing frequency.

$$
% caption: UCB adds an uncertainty bonus to each estimate — a well-sampled arm
% (left) has a tight interval and is judged near its estimate, while a rarely
% tried arm (right) has a wide interval and can be selected on the strength of
% its optimistic upper end even with a lower estimate.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, black] (0,0) -- (0,4.0) node[above] {value};
  \draw[black] (0,0) -- (7.4,0);
  % arm A: high estimate, tight interval
  \node[anchor=north, font=\scriptsize] at (1.6,-0.05) {arm A (many pulls)};
  \fill[acc] (1.6,2.4) circle (2.2pt);
  \draw[acc, thick] (1.6,2.05) -- (1.6,2.75);
  \draw[acc, thick] (1.45,2.05) -- (1.75,2.05);
  \draw[acc, thick] (1.45,2.75) -- (1.75,2.75);
  \node[acc, anchor=south east, font=\scriptsize] at (1.45,2.95) {upper bound};
  % arm B: lower estimate, wide interval, higher upper bound
  \node[anchor=north, font=\scriptsize] at (5.0,-0.05) {arm B (few pulls)};
  \fill[acc] (5.0,1.7) circle (2.2pt);
  \draw[acc, thick] (5.0,0.6) -- (5.0,3.3);
  \draw[acc, thick] (4.85,0.6) -- (5.15,0.6);
  \draw[acc, thick] (4.85,3.3) -- (5.15,3.3);
  \node[acc, anchor=west, font=\scriptsize] at (5.2,3.3) {upper bound};
  % dashed line at A's upper bound extended to B, showing B's interval reaches higher
  \draw[dashed, black] (1.75,2.75) -- (4.85,2.75);
\end{tikzpicture}
$$

### UCB by hand

For example, take a $3$-armed problem
after $t = 10$ plays, with $c = 2$, current estimates and counts

$$
Q(1) = 1.4,\ N(1) = 6; \qquad
Q(2) = 1.2,\ N(2) = 3; \qquad
Q(3) = 0.9,\ N(3) = 1.
$$

Arm $1$ is greedy on the estimate. But the selection maximizes
$Q(a) + c\sqrt{\ln t / N(a)}$, and with $\ln 10 = 2.303$ the bonuses are

$$
\begin{aligned}
\text{arm }1:&\quad 1.4 + 2\sqrt{2.303/6} = 1.4 + 1.24 = 2.64, \\
\text{arm }2:&\quad 1.2 + 2\sqrt{2.303/3} = 1.2 + 1.75 = 2.95, \\
\text{arm }3:&\quad 0.9 + 2\sqrt{2.303/1} = 0.9 + 3.03 = 3.93.
\end{aligned}
$$

UCB selects arm $3$ — the one with the _lowest_ estimate — purely because a
single sample leaves its value the most uncertain, and the bonus $3.03$ swamps
the $0.5$ gap in estimates. Pull it, and $N(3)$ becomes $2$: its next bonus
falls to $2\sqrt{2.303/2} = 2.15$, a large drop from one observation. The bonus
falls off as $1/\sqrt{N(a)}$, so the first few pulls of a neglected arm shrink
its uncertainty fast, and selection increasingly depends on the estimates
themselves. This is the self-correction described above.

UCB often outperforms ε-greedy on the bandit, but it is harder to extend to the
full RL problem: it does not cope gracefully with nonstationarity, and its
per-action counts $N_t(a)$ become impractical once the state space is large and
values are represented by function approximation rather than a table.

## Gradient bandit algorithms

Every method so far estimates action _values_ and selects from them. A different
idea is to learn a numerical **preference** $H_t(a)$ for each action, with no
interpretation as a reward. Only relative preferences matter: adding a constant
to every preference leaves behavior unchanged, because actions are selected in
proportion to a **soft-max** (Gibbs, or Boltzmann) distribution over the
preferences,

$$
\Pr\{A_t = a\} \doteq \frac{e^{H_t(a)}}{\sum_{b=1}^{k} e^{H_t(b)}} \doteq \pi_t(a),
$$

where $\pi_t(a)$ is the probability of taking action $a$ at time $t$. Initially
all preferences are equal ($H_1(a) = 0$ for all $a$), so every action is equally
likely.

There is a natural learning rule based on **stochastic gradient ascent**. After
selecting $A_t$ and receiving $R_t$, update all preferences by

$$
\begin{aligned}
H_{t+1}(A_t) &\doteq H_t(A_t) + \alpha\left(R_t - \bar{R}_t\right)\left(1 - \pi_t(A_t)\right), \\[3pt]
H_{t+1}(a)   &\doteq H_t(a) - \alpha\left(R_t - \bar{R}_t\right)\pi_t(a), \qquad \text{for all } a \neq A_t,
\end{aligned}
$$

where $\alpha > 0$ is a step size and $\bar{R}_t$ is the average of all rewards
through step $t$, computed incrementally. The $\bar{R}_t$ term is a **baseline**:
if the reward beats the baseline, the probability of $A_t$ is raised and the
others lowered; if it falls short, $A_t$'s probability is lowered. The baseline
makes the algorithm invariant to a shift in the overall reward level — add $+4$
to every reward and the gradient bandit adapts instantly, whereas without the
baseline the same shift badly degrades performance.

$$
% caption: The gradient bandit compares the received reward $R_t$ against a
% running baseline $\bar{R}_t$ — a reward above baseline pushes the taken arm's
% preference up and the softmax probabilities of all others down; a reward below
% baseline does the reverse.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=24mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (r) at (0,1.2) {reward R(t)};
  \node[box] (b) at (0,-1.2) {baseline mean-R(t)};
  \node[box, draw=acc, text=acc] (cmp) at (3.8,0) {compare};
  \node[box, draw=acc, text=acc] (up) at (8.0,1.2) {raise pref. of taken arm};
  \node[box, draw=red, text=red] (dn) at (8.0,-1.2) {lower pref. of others};
  \draw[->, thick] (r.east) -- (cmp.north west);
  \draw[->, thick] (b.east) -- (cmp.south west);
  \draw[->, acc, thick] (cmp.north east) -- (up.west);
  \draw[->, red, thick] (cmp.south east) -- (dn.west);
  \node[font=\scriptsize, text=black] at (5.9,1.35) {if above};
  \node[font=\scriptsize, text=black] at (5.9,-1.35) {always};
\end{tikzpicture}
$$

### Why the preferences follow the gradient

The update is not an arbitrary heuristic — it is a sampled version of exact
gradient ascent on expected reward, and the derivation explains why it converges.
In exact gradient ascent each preference
would move proportionally to the effect of that move on performance:

$$
H_{t+1}(a) \doteq H_t(a) + \alpha \frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)},
\qquad \mathbb{E}[R_t] = \sum_x \pi_t(x)\, q_\ast(x).
$$

We cannot compute this directly, because $q_\ast(x)$ is unknown. But the expected
value of the actual update equals this gradient. Expanding the derivative and
inserting an arbitrary baseline $B_t$ (which changes nothing, since the softmax
probabilities always sum to $1$ so $\sum_x \frac{\partial \pi_t(x)}{\partial H_t(a)} = 0$):

$$
\frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)}
= \sum_x \left(q_\ast(x) - B_t\right) \frac{\partial \pi_t(x)}{\partial H_t(a)}
= \mathbb{E}\!\left[\left(q_\ast(A_t) - B_t\right) \frac{\partial \pi_t(A_t)}{\partial H_t(a)} \Big/ \pi_t(A_t)\right].
$$

Choosing the baseline $B_t = \bar{R}_t$ and substituting $R_t$ for $q_\ast(A_t)$
(permitted since $\mathbb{E}[R_t \mid A_t] = q_\ast(A_t)$), then using the softmax
derivative $\frac{\partial \pi_t(x)}{\partial H_t(a)} = \pi_t(x)\left(\mathbb{1}_{a=x} - \pi_t(a)\right)$,
the whole expectation collapses to

$$
\frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)}
= \mathbb{E}\!\left[\left(R_t - \bar{R}_t\right)\left(\mathbb{1}_{a=A_t} - \pi_t(a)\right)\right].
$$

The bracketed quantity reproduces the per-step gradient-bandit update. So the
algorithm's expected update equals the true gradient of expected reward — it is
genuine stochastic gradient ascent, which is why it has sound convergence
behavior.[^sb-gradient] The baseline can be any quantity not depending on the
selected action; it does not change the expected update, but it does reduce the
update's variance, and the running reward average is a simple choice that works
well in practice.

### A gradient-bandit update by hand

Take $3$ arms with preferences $H = (0, 0, 0)$, so the softmax gives
$\pi = (\tfrac13, \tfrac13, \tfrac13)$. Use step size $\alpha = 0.1$ and suppose
the running baseline is $\bar{R} = 0.5$. Select arm $2$ (each arm equally likely
at the start) and receive reward $R = 2.0$, well above baseline, so
$R - \bar{R} = 1.5$. The taken arm rises and the others fall:

$$
\begin{aligned}
H(2) &\gets 0 + 0.1(1.5)(1 - \tfrac13) = 0 + 0.1(1.5)(0.667) = +0.100, \\
H(1) &\gets 0 - 0.1(1.5)(\tfrac13) = -0.050, \\
H(3) &\gets 0 - 0.1(1.5)(\tfrac13) = -0.050.
\end{aligned}
$$

The new preferences $(-0.05, +0.10, -0.05)$ re-normalize through the softmax to
$\pi = (0.316, 0.367, 0.316)$: arm $2$'s probability rose from $0.333$ to
$0.367$, the other two fell symmetrically, and the three still sum to $1$. Now
add $+10$ to _every_ reward. The received reward becomes $12.0$, but the baseline
climbs toward $10.5$ as well, so $R - \bar{R} = 1.5$ is unchanged and the update
is identical — the baseline makes the algorithm blind to the overall reward
level. Drop the baseline (set $\bar{R} = 0$) and the same shift makes
$R - \bar{R} = 12.0$, an update $8\times$ larger and dominated by the offset
rather than the arm's relative merit. That is the failure the baseline prevents.

$$
% caption: One gradient-bandit step from a uniform start. A reward above the
% baseline raises the taken arm's softmax probability (arm 2, blue) and lowers the
% others' (red) by half as much each, keeping the distribution normalized. The
% shift is proportional to $R - \bar{R}$, so a constant offset added to all
% rewards leaves it unchanged.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (0,3.4) node[above] {probability};
  \draw[black] (0,0) -- (7.2,0);
  \node[anchor=east, font=\scriptsize] at (-0.08,3.0) {0.4};
  \node[anchor=east, font=\scriptsize] at (-0.08,0) {0};
  \draw[black, dashed] (0,2.5) -- (7.2,2.5);
  \node[anchor=east, font=\scriptsize, black] at (-0.08,2.5) {1/3};
  % before bars (light) and after bars (solid) for each arm
  % arm1: before 0.333 (y2.5), after 0.318 (y2.385)
  \fill[black, draw=black] (0.5,0) rectangle (1.2,2.5);
  \fill[red!22, draw=red] (1.3,0) rectangle (2.0,2.385);
  \node[anchor=north, font=\scriptsize] at (1.25,-0.05) {arm 1};
  % arm2: before 0.333, after 0.363 (y2.723)
  \fill[black, draw=black] (2.9,0) rectangle (3.6,2.5);
  \fill[acc!25, draw=acc] (3.7,0) rectangle (4.4,2.723);
  \node[anchor=north, font=\scriptsize] at (3.65,-0.05) {arm 2 (taken)};
  % arm3
  \fill[black, draw=black] (5.3,0) rectangle (6.0,2.5);
  \fill[red!22, draw=red] (6.1,0) rectangle (6.8,2.385);
  \node[anchor=north, font=\scriptsize] at (6.05,-0.05) {arm 3};
  \node[black, anchor=west, font=\scriptsize] at (0.5,3.15) {light = before, solid = after};
\end{tikzpicture}
$$

## Associative search: contextual bandits

Everything so far is **nonassociative**: there is one situation, and the task is
either to find the single best action or to track it as it drifts. The full
reinforcement learning problem has more than one situation, and the goal is to
learn a **policy** — a mapping from situations to the actions best in each.

The bridge between the two is **associative search**, now usually called the
**contextual bandit** problem. Suppose that on each step you face one of several
different bandit tasks, chosen at random, and you are given a distinctive clue
about _which_ task it is (but not its action values). That clue is what
separates the setting from a plain bandit. Imagine a
slot machine that changes the color of its display as it changes its payouts:
seeing the color, you can learn a policy of the form "if red, pull arm 1; if
green, pull arm 2," and do far better than any single fixed choice could.

> **Definition (Associative search / contextual bandit).** A task where each
> step presents an observable context signaling which of several bandit problems
> is active, and the goal is to learn a policy mapping contexts to actions. It
> involves both trial-and-error _search_ for good actions and _association_ of
> those actions with the situations in which they are best.

This sits between the plain bandit and full reinforcement learning. Like the
full problem, it involves learning a policy over situations; like the plain
bandit, each action affects only the **immediate** reward and nothing else. The
one remaining ingredient is the piece we deliberately removed at the start: allow
an action to affect the **next situation** as well as the reward, and the
contextual bandit becomes the
[full reinforcement learning problem](/reinforcement-learning/foundations/markov-decision-processes).

## Regret, UCB1, and Thompson sampling

Sutton and Barto measure a method by its average reward and its optimal-action
rate on the testbed. The theoretical bandit literature measures it by a single
scalar, **regret**, and the results there sharpen every idea in this lesson.
Define the regret after $n$ steps as the reward lost relative to always pulling
the best arm,

$$
\text{Regret}(n) = n\,q_\ast(a^\ast) - \mathbb{E}\!\left[\sum_{t=1}^{n} R_t\right]
  = \sum_{a}\Delta_a\,\mathbb{E}[N_n(a)],
\qquad \Delta_a = q_\ast(a^\ast) - q_\ast(a),
$$

where $a^\ast$ is an optimal arm and $\Delta_a$ is arm $a$'s **suboptimality gap**.
In words: regret is the number of times each
suboptimal arm is pulled, weighted by its gap. A good method pulls the bad
arms rarely.

$$
% caption: Regret accumulates only on suboptimal pulls. The dashed line is the
% reward of always pulling the best arm ($n\,q_*(a^*)$); the solid curve is the
% method's cumulative reward. The vertical gap is the regret, and it grows only
% when a pull lands on an arm with gap $\Delta_a > 0$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (8.4,0) node[right] {steps n};
  \draw[->, black] (0,0) -- (0,4.2) node[above] {cumulative reward};
  % optimal line
  \draw[red, thick] (0,0) -- (7.8,4.0);
  \node[red, anchor=south east, font=\scriptsize] at (7.7,3.95) {always best};
  % method curve: stays below the optimal line throughout, gap widens then flattens
  \draw[acc, very thick]
    (0,0) .. controls (1.2,0.55) and (2.6,1.35) .. (4.0,2.05)
    .. controls (5.6,2.85) and (6.8,3.2) .. (7.8,3.35);
  \node[acc, anchor=north west, font=\scriptsize] at (6.0,2.75) {method};
  % gap arrow (regret = vertical gap at the right end)
  \draw[<->, black] (7.8,3.35) -- (7.8,4.0);
  \node[black, anchor=west, font=\scriptsize] at (7.9,3.7) {regret};
\end{tikzpicture}
$$

Lai and Robbins (1985) proved that _no_ method can do better than logarithmic
regret: for any consistent policy, $\mathbb{E}[N_n(a)] \ge (\ln n)/D(a)$
asymptotically, where $D(a)$ is a KL-divergence between arm $a$'s reward
distribution and the best arm's.[^lai-robbins] Regret must grow at least like
$\ln n$, so $\varepsilon$-greedy with a _fixed_ $\varepsilon$ is provably
suboptimal: it explores a constant fraction of the time, pulling each bad arm
$\Theta(\varepsilon n)$ times, for _linear_ regret $\Theta(n)$. That is the
formal statement of what the learning curves showed — a fixed $\varepsilon$
ceilings below the optimum. (A schedule $\varepsilon_t \propto 1/t$ recovers
logarithmic regret, which is why decaying $\varepsilon$ is standard practice.)

Auer, Cesa-Bianchi, and Fischer (2002) showed that the UCB rule of this lesson
_achieves_ the logarithmic bound with no schedule to tune. Their **UCB1**
algorithm, using the bonus $\sqrt{2\ln t / N_t(a)}$ (the same form as ours with
$c = \sqrt{2}$), satisfies a _finite-time_ bound: for any $n$,

$$
\text{Regret}(n) \le \sum_{a:\,\Delta_a > 0}\frac{8\ln n}{\Delta_a}
  + \left(1 + \tfrac{\pi^2}{3}\right)\sum_{a}\Delta_a.[^auer2002]
$$

The first term is the unavoidable $O(\ln n)$; the second is a constant. This
theorem is why UCB performs well: it is within a constant factor of optimal on
_every_ bandit, for _every_ horizon. Lattimore and Szepesvári (2020) give the modern, tightened form of these
bounds and the matching lower bounds in a full-length treatment.[^lattimore]

A different route to the same optimality is older than all of it. **Thompson
sampling**, proposed by Thompson (1933), keeps a Bayesian posterior over each
arm's value and, on each step, draws one sample from every posterior and pulls
the arm with the largest sample.[^thompson] An arm with a wide posterior
sometimes draws high and gets explored; as its posterior concentrates, it is
pulled only when its estimated value warrants it. For Bernoulli rewards the posterior is a Beta
distribution updated by simple success/failure counts, so the method is a few
lines of code. Chapelle and Li (2011) demonstrated empirically that Thompson
sampling matches or beats UCB on real display-advertising and news data, which
returned it to wide use;[^chapelle] Agrawal and Goyal (2012) then proved it also
attains the optimal $O(\ln n)$ regret. Thompson sampling and UCB are the two
default modern answers to the exploration problem this lesson poses.

> **Definition (Regret).** The regret of a bandit method after $n$ steps is the
> expected reward it forgoes relative to always pulling an optimal arm,
> $\sum_a \Delta_a\,\mathbb{E}[N_n(a)]$. Logarithmic regret $O(\ln n)$ is optimal
> (Lai–Robbins); UCB1 and Thompson sampling attain it, fixed-$\varepsilon$ greedy
> does not.

### Contextual bandits in practice

The associative-search setting is how large-scale recommendation and
ad-placement are formalized. Li, Chu,
Langford, and Schapire (2010) introduced **LinUCB**, which assumes each arm's
expected reward is linear in a context feature vector $x_{t,a}$,
$\mathbb{E}[R_t \mid x_{t,a}] = x_{t,a}^\top\theta_a$, and applies a UCB-style
bonus derived from the confidence ellipsoid of a ridge-regression estimate of
$\theta_a$.[^linucb] Deployed on Yahoo's front-page news module, it raised
click-through over a context-free bandit by a double-digit percentage. LinUCB is
the direct ancestor of the contextual-bandit services now standard for
recommendation, and it realizes the "clue about which task you face" idea of
associative search, made linear and equipped with the UCB confidence bound.

## What the bandit leaves out

The bandit is reinforcement learning with two things deleted, and naming them
sharpens what the rest of the subject is about.

| Ingredient | Bandit | Full RL |
| --- | --- | --- |
| State / situation | none — every step identical | a state $S_t$ observed each step |
| Consequences of an action | immediate reward only | reward **and** the next state |
| What is learned | a value per arm, or a preference | a policy over states |
| The hard problem | exploration vs. exploitation | that, **plus** credit assignment over time |

The one problem present here in pure form — how much to explore — survives
intact into the full setting; the bandit is where we could study it without the
distraction of states and delayed consequences. Add a state that the action
moves you through, so that a reward now can depend on a choice made many steps
ago, and you get the central new difficulty of reinforcement learning:
**temporal credit assignment**, which is where the
[Markov decision process](/reinforcement-learning/foundations/markov-decision-processes)
picks up.


[^sb-gradient]: **Sutton & Barto**, §2.8 — Gradient Bandit Algorithms and the box "The Bandit Gradient Algorithm as Stochastic Gradient Ascent": the softmax preference model, the baseline-subtracted update, and the derivation showing the expected update equals the gradient of expected reward.
[^lai-robbins]: **Lai, T. L. & Robbins, H. (1985)**, "Asymptotically efficient adaptive allocation rules", _Advances in Applied Mathematics_ 6(1), 4–22 — the asymptotic lower bound $\liminf_n \mathbb{E}[N_n(a)]/\ln n \ge 1/D(a)$ on the number of pulls of a suboptimal arm, establishing that regret must grow at least logarithmically.
[^auer2002]: **Auer, P., Cesa-Bianchi, N. & Fischer, P. (2002)**, "Finite-time analysis of the multiarmed bandit problem", _Machine Learning_ 47, 235–256 — the UCB1 algorithm with bonus $\sqrt{2\ln t/N_t(a)}$ and its finite-time $O(\ln n)$ regret bound, matching the Lai–Robbins rate for all horizons.
[^lattimore]: **Lattimore, T. & Szepesvári, C. (2020)**, _Bandit Algorithms_, Cambridge University Press — a book-length modern treatment of stochastic and adversarial bandits, with tightened UCB regret bounds and the matching minimax and instance-dependent lower bounds.
[^thompson]: **Thompson, W. R. (1933)**, "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples", _Biometrika_ 25(3–4), 285–294 — the original posterior-sampling rule (Thompson sampling): maintain a posterior over each arm's value and pull the arm whose single posterior draw is largest.
[^chapelle]: **Chapelle, O. & Li, L. (2011)**, "An empirical evaluation of Thompson sampling", _Advances in Neural Information Processing Systems (NeurIPS)_ 24 — experiments on display-advertising and news data showing Thompson sampling matches or exceeds UCB, which renewed practical interest in the method. Optimal $O(\ln n)$ regret for Thompson sampling was later proved by **Agrawal, S. & Goyal, N. (2012)**, "Analysis of Thompson sampling for the multi-armed bandit problem", _Conference on Learning Theory (COLT)_.
[^linucb]: **Li, L., Chu, W., Langford, J. & Schapire, R. E. (2010)**, "A contextual-bandit approach to personalized news article recommendation", _Proceedings of the 19th International Conference on World Wide Web (WWW)_, 661–670 — the LinUCB algorithm, assuming rewards linear in a context vector with a UCB bonus from the ridge-regression confidence ellipsoid, deployed on Yahoo's news module.