Bandit Exploration Algorithms

This builds on 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:

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.

UCB by hand

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

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

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,

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

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.

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:

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$):

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(1_{a=x}-{\pi }_t(a)\right)$, the whole expectation collapses to

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.¹ 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 =(\frac{1}{3},\frac{1}{3},\frac{1}{3})$. 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:

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.

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.

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.

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,

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.

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.² Regret must grow at least like $\ln n$, so $\epsilon$-greedy with a fixed $\epsilon$ is provably suboptimal: it explores a constant fraction of the time, pulling each bad arm $\Theta (\epsilon n)$ times, for linear regret $\Theta (n)$. That is the formal statement of what the learning curves showed — a fixed $\epsilon$ ceilings below the optimum. (A schedule ${\epsilon }_t\propto 1/t$ recovers logarithmic regret, which is why decaying $\epsilon$ 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$,

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.³

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.⁴ 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;⁵ 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.

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$.⁶ 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.

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 picks up.