Upper-confidence-bound

Learning objective

Be able to write the UCB rule from memory, say what each term in the bonus is doing and why the bonus has that shape, predict how $c$ changes behaviour, and explain the step-11 spike on the 10-armed testbed in both directions — why the reward jumps and why it falls again.

Intuition

Every method so far explores badly in the same way. $\varepsilon$-greedy explores uniformly: an arm pulled 500 times with a terrible payout is exactly as likely to be sampled as a promising arm pulled twice. It knows which arms it is unsure about and throws that information away at the moment it acts on it. Optimistic initial values do better — they at least sweep the arms in a useful order — but the optimism decays on a fixed schedule regardless of what has actually been learned, and once spent it never comes back.

UCB fixes both faults with one idea. Do not choose whether to explore; make uncertainty part of what “best” means. An arm is worth taking if it either looks good or is poorly understood, and the rule adds those two things together.

The rule

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

$Q_t(a)$ is the usual estimate, $N_t(a)$ the number of times $a$ has been taken before step $t$, and $c > 0$ controls how much the uncertainty is worth. If $N_t(a) = 0$, arm $a$ is treated as maximising — it is taken before any arm with a finite value.

The whole rule is one quantity: an upper confidence bound on $q_*(a)$. The square-root term is a plausible amount by which the true value might exceed the current estimate, so the bracket is roughly the best case still consistent with the data. UCB then acts greedily with respect to that best case. This is optimism in the face of uncertainty, made specific: not “assume everything is great”, but “assume each arm is as good as its own evidence still permits”.

Read the bonus one symbol at a time:

• $N_t(a)$ in the denominator. Each pull of $a$ shrinks $a$‘s own bonus. Take an arm and you reduce your reason to take it again — self-correcting, and targeted at the arm actually sampled rather than spread over all of them.
• $\ln t$ in the numerator. Every arm’s bonus creeps up whenever any arm is pulled. A neglected arm slowly becomes attractive again purely because time has passed, so no arm is abandoned forever.
• The logarithm. $\ln t$ grows without bound, so exploration never fully stops, but it grows slower than any power of $t$, so the fraction of pulls spent exploring goes to zero. That is exactly the balance you want: enough exploration to be sure, little enough to be cheap.
• The square root. The standard error of a mean of $n$ samples shrinks like $1/\sqrt{n}$. The bonus is a confidence-interval half-width, not an arbitrary penalty.
• $c$. The confidence level, in units of that half-width. Larger $c$ means wider intervals, more optimism, more exploration.

Nothing here is random. Given the rewards, the sequence of actions is determined — a fact that looks like a footnote and turns out to explain the whole shape of the learning curve below.

Where the $\sqrt{\ln t / N}$ comes from

Hoeffding’s inequality says that for a mean $Q_t(a)$ of $N_t(a)$ bounded samples,

$$\Pr\left(q_*(a) > Q_t(a) + u\right) \;\le\; \exp\left(-2 N_t(a) u^2\right)$$

Ask for that failure probability to be $t^{-4}$ — a tolerance that tightens as the run gets longer, so the total chance of ever being wrong stays finite — and solve for $u$:

$$\exp\left(-2 N_t(a) u^2\right) = t^{-4} \quad\Longrightarrow\quad u = \sqrt{\frac{2 \ln t}{N_t(a)}}$$

which is the bonus, with $c$ absorbing the constant and the reward scale. So $c$ is not a free-floating knob: it is a claim about how wide the confidence interval on an arm’s value really is, and the right value depends on the noise in the rewards. With $c$ too small the bound is not an upper bound at all and UCB can settle early on a wrong arm; with $c$ too large it keeps re-checking arms it has already ruled out.

The algorithm

UCB, sample-average estimates

Initialise, for $a = 1$ to $k$:   $Q(a) \leftarrow 0$,   $N(a) \leftarrow 0$

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

$\quad A \leftarrow \arg\max_a \left[ Q(a) + c\sqrt{\dfrac{\ln t}{N(a)}} \right]$   (any $a$ with $N(a) = 0$ counts as maximal; ties broken randomly)

$\quad R \leftarrow \mathrm{bandit}(A)$

$\quad N(A) \leftarrow N(A) + 1$

$\quad Q(A) \leftarrow Q(A) + \dfrac{1}{N(A)}\left[R - Q(A)\right]$

There is no $\varepsilon$ and no coin flip. The only new parameter is $c$, and $t$ is the global step count, not the per-arm count — the two appear in the same expression and confusing them breaks the method.

How big is the bonus, really

With $c = 2$, on a testbed where the rewards themselves are around $\pm 2$:

$t$	$N_t(a)$	bonus $2\sqrt{\ln t / N_t(a)}$
11	1	3.10
100	1	4.29
100	10	1.36
1000	10	1.66
1000	100	0.53
1000	900	0.18

Early on the bonus dwarfs every difference in $Q$, which is why the first several steps are pure exploration. By step 1000 an arm that has taken 900 of the pulls carries a bonus of 0.18 while an arm sampled only 10 times carries 1.66 — so the neglected arm gets pulled again unless it is believed to be about 1.5 worse. That gap is the exploration, and it is priced per arm.

Average performance on the 10-armed testbed

Standard testbed: $k = 10$, $q_*(a) \sim \mathcal{N}(0,1)$ drawn fresh per run, $R_t \sim \mathcal{N}(q_*(A_t), 1)$, sample-average estimates, $Q_1(a) = 0$, 2000 independent runs of 1000 steps. UCB at $c = 2$ and $c = 1$ against $\varepsilon$-greedy at $\varepsilon = 0.1$.

Every figure below comes from experiments/ucb-testbed.mjs in this repository. It is seeded and dependency-free, so node experiments/ucb-testbed.mjs reprints the table and the spike diagnostics exactly.

Average reward per step on the 10-armed testbed, 2000 runs. UCB pays for a ten-step sweep, spikes at step 11, and settles above ε-greedy.

Beyond step 40 the curves are averaged over blocks of ten steps, or the spike would be lost in per-step noise. The numbers:

Step	UCB $c=2$	UCB $c=1$	$\varepsilon$-greedy	UCB $c=2$ % optimal	$\varepsilon$-greedy % optimal
1	0.06	0.06	0.02	11.1	10.7
5	−0.02	−0.02	0.55	10.1	21.8
10	−0.03	−0.03	0.79	10.2	28.6
11	1.11	1.11	0.84	42.1	28.9
12	0.90	1.03	0.85	32.3	30.4
20	0.80	1.15	0.93	34.4	35.1
50	1.14	1.42	1.10	50.4	46.1
100	1.23	1.43	1.21	60.9	55.4
500	1.44	1.51	1.36	78.9	75.5
1000	1.48	1.51	1.34	86.8	80.8

UCB pays for its first ten steps: the forced sweep earns an average reward of −0.01 while $\varepsilon$-greedy is already exploiting. It draws level at around step 60 on average reward (step 30 if you score it on percent optimal action) and stays ahead from there, finishing at 1.48 against 1.34 and playing the optimal arm 87% of the time against 81%. The advantage is structural: $\varepsilon$-greedy keeps spending 10% of every step on a uniformly random arm forever, while UCB’s exploration is concentrated on arms that are still genuinely in doubt and thins out as the doubt does.

Note also that $c = 1$ beats $c = 2$ over this horizon (mean reward 1.47 against 1.38 across the 1000 steps), and that the gap has nearly closed by step 1000 as the $c = 2$ curve is still climbing. This is the same horizon argument as $\varepsilon$: more exploration costs more now and is worth more later, and the best setting is a function of how long you get to play.

The spike at step 11

The early part of the curve has a feature that looks like a plotting artefact and is not — this is exercise 2.8. Here are the first 40 steps unsmoothed:

The first 40 steps, unsmoothed. The step-11 peak is identical for both values of c; only the trough after it differs.

Average reward sits near zero for ten steps, jumps to 1.11 at step 11, drops back to 0.90 at step 12, and sags further before recovering. Averaging over 2000 runs removes noise, not structure: UCB’s action sequence is a deterministic function of the rewards, and its exploration is locked to the step number rather than scattered in time by a coin flip, so every run does the same thing at the same step and the feature survives averaging. Two separate mechanisms produce the rise and the fall.

Why the reward rises at step 11

Steps 1–10 are a forced sweep. Every arm starts with $N_t(a) = 0$ and counts as maximal, so the first ten steps try all ten arms in an arbitrary order. Each step therefore lands on a uniformly random arm, and the average reward is the average of $q_*$ over all arms: zero, measured at −0.01.

At step 11 the bonus cancels. Every arm now has $N_{11}(a) = 1$ and $\ln t$ is shared, so the bonus is the same constant $c\sqrt{\ln 11}$ for all ten arms. It shifts every entry in the bracket equally and drops out of the $\arg\max$ entirely. Step 11 is a purely greedy choice, and with one sample per arm $Q_{11}(a)$ is just the single reward that arm returned:

$$A_{11} = \arg\max_a \left[ Q_{11}(a) + c\sqrt{\tfrac{\ln 11}{1}} \right] = \arg\max_a R^{(1)}(a)$$

In the simulation this identity holds in 100% of runs, as it must.

That choice is much better than chance. The arm with the largest of the ten first rewards is the optimal arm 42.1% of the time rather than 10%, and its true value averages $\mathbb{E}[q_*(A_{11})] = 1.08$. The reward collected at step 11 is a fresh draw from that arm, so the average lands at 1.11. The spike is the payoff from the first complete comparison of all $k$ arms — the sweep bought ten samples, and step 11 is the first step allowed to use them.

Why the reward falls at step 12 and after

The winner’s bonus collapses. The arm taken at step 11 now has $N = 2$ while the other nine still have $N = 1$, and $\ln t$ has gone up slightly for everyone. The gap it must overcome to be repeated is

$$c\sqrt{\ln 12} - c\sqrt{\tfrac{\ln 12}{2}} = c\sqrt{\ln 12}\left(1 - \tfrac{1}{\sqrt 2}\right) \approx 0.46\,c$$

which is 0.92 at $c = 2$. Its $Q$ must lead the runner-up by more than that or UCB is obliged to go elsewhere. It only does so in 18.4% of runs.

And its estimate regresses. The arm was selected precisely for having the largest of ten noisy samples, so its $Q$ is biased above its true value. The second pull averages in an unbiased draw and pulls the estimate back down. The step-11 winner loses on both terms at once, while every rival gains slightly on the bonus.

So step 12 is nearly forced onto a worse arm — one that just lost the step-11 comparison — and the average drops to 0.90. Steps 12 to 20 continue down the ranking, working through the arms UCB already believes are inferior, and average 0.82: below the spike, and for a while below $\varepsilon$-greedy, which is free to keep exploiting its favourite. Faint ripples with period near $k$ follow, each new sweep producing another re-ranking, damping out as the pull counts desynchronise and the time-locking that let the structure survive averaging breaks down.

The spike is therefore a contrast effect: step 11 is the one step where UCB is allowed to be purely greedy, and step 12 is a step where it is nearly forbidden from repeating itself.

What $c = 1$ shows

Setting $c = 1$ makes the spike less prominent, and how it does so pins the explanation down:

	$c = 2$	$c = 1$
Average reward, step 11	1.110	1.110
Average reward, step 12	0.904	1.028
Step 12 repeats the step-11 arm	18.4%	37.4%
Ratio $R_{11} / R_{12}$	1.23	1.08

The peak does not move at all. It cannot: the bonus cancels at step 11 for any $c$, so step 11 is the same greedy choice in both runs and collects the same 1.11. Whatever makes the spike less prominent is not acting on the peak.

The trough is what changes. Halving $c$ halves the switching threshold from 0.92 to 0.46, so the step-11 winner is retained twice as often and step 12 falls only to 1.03. With the floor raised and the peak fixed, the spike flattens into the curve. Push $c$ toward zero and the sweep is followed by ordinary greedy behaviour with no discontinuity at all.

That is the cleanest confirmation available that the fall is caused by the bonus term forcing a switch, and not by anything about the peak itself.

What is wrong with it

Nonstationary problems. $\ln t$ grows over the whole history, so an arm pulled heavily long ago is slow to be re-examined even if the world has since changed. UCB’s confidence intervals assume the thing being estimated holds still.

Large state spaces. UCB needs a visit count $N_t(a)$ per action. In a bandit that is $k$ counters; with states and function approximation there is no equivalent, and the count-based bonus has to be replaced by something learned — pseudo-counts, ensemble disagreement, random network distillation.

$c$ has to match the reward scale. The bonus is in reward units. Rescale the rewards by 100 and the same $c$ explores essentially not at all.

The first $k$ steps are spent regardless. On a problem with thousands of arms, the mandatory sweep alone may exhaust the budget.

Common mistakes

Using the per-arm count where $\ln t$ belongs. $t$ is the total step count. With $N_t(a)$ in both places the bonus becomes $c$ and never decays relative to anything, and the method stops working.

Forgetting the $N_t(a) = 0$ case. In code, $\ln t / 0$ is $\infty$ or a divide-by-zero depending on the language. Handle untried arms explicitly, and break the resulting ten-way tie randomly — an index-ordered argmax makes the opening sweep run in arm order, which is harmless here and a real bug elsewhere.

Reading the spike as noise. More runs make it sharper, not smoother. It is the algorithm.

Expecting the ranking at step 11 to mean much. It is a comparison of ten single samples. It is far better than chance and still wrong 58% of the time.

Personal takeaways

What makes UCB feel like a real advance rather than another heuristic is that the exploration is derived rather than chosen. $\varepsilon$ is a number you pick; $c\sqrt{\ln t / N_t(a)}$ is what a confidence interval already implies. The method does not have an exploration policy bolted onto a greedy policy — it is greedy, with respect to a quantity that happens to reward ignorance.

The step-11 exercise is worth the time it takes, because the useful habit it teaches is not about bandits. A feature that survives averaging over thousands of runs is telling you something about the mechanism, and the way to find out what is to ask which step of the algorithm is time-locked. Here the answer was the one step where the exploration term cancels — and the $c = 1$ check separates the cause from the coincidence, because it moves the trough while leaving the peak untouched.

Where next

Every method so far — including this one — estimates $q_*(a)$ and then argues about how to act on the estimate. The last page of the chapter drops the estimate entirely and learns a preference instead: gradient bandit algorithms.

References

• Sutton, R. S. & Barto, A. G. Reinforcement Learning: An Introduction, 2nd ed., §2.7, figure 2.4, and exercise 2.8.
• Auer, P., Cesa-Bianchi, N. & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235–256.