7 concepts20 worked examples30 exercises4 exam-level7 figures
What are you here for?
15 Multi-armed bandits and online learning: regret, ε-greedy, UCB and Thompson sampling
Start with this
One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§15.5 — which rate could still be the higher one
Two email subject lines were tested. Line A was opened by 11 of 20 readers, line B by 130 of 200. For each line, take the one-sided Hoeffding upper limit $\hat\mu+\sqrt{\ln(1/\delta)/(2n)}$ with $\delta=0.05$.
Find(a) Which line has the larger upper limit, and about how large is it?
Given
line A: $11$ opens in $n=20$, sample mean $0.55$
line B: $130$ opens in $n=200$, sample mean $0.65$
$\ln(1/0.05)=\ln20=2.9957$
Hint 1/4
An upper limit is the sample mean plus a width, and the width depends on how many readers each line had.
Hint 2/4
One-sided Hoeffding: $\Pr(\mu\ge\hat\mu+\varepsilon)\le e^{-2n\varepsilon^2}$, so the limit at level $\delta$ is $\hat\mu+\sqrt{\ln(1/\delta)/(2n)}$.
Hint 3/4
Here A has $\hat\mu=0.55$, $n=20$ and B has $\hat\mu=0.65$, $n=200$, with $\ln(1/\delta)=2.9957$: widths $\sqrt{2.9957/40}$ and $\sqrt{2.9957/400}$.
Hint 4/4
A: $0.55+0.2737=0.8237$; B: $0.65+0.0865=0.7365$. Line A has the larger upper limit, about $0.82$.
Show solution
Compare limits, not means: the question is how high each true rate could plausibly be, and that depends on $n$.
Width ratio check: $\varepsilon_A/\varepsilon_B=\sqrt{200/20}=3.16$, and $0.2737/0.0865=3.16$.
An option measured on few people can still be the better one; that is the whole reason to keep trying it.
A shop has two coupon designs: A is redeemed by 6 customers in 10, B by 4 in 10, though nobody knows these rates. The shop offers each once, then always the one with the better record so far. At least 16 shops in 100 that follow this rule end up offering B forever.
By the end you can compute why that happens and what it costs, and run the three policies that avoid it, ε-greedy, UCB and , by hand, with the each one is guaranteed.
In 60 seconds
A bandit learner plays one of $K$ arms per round and sees only that arm's reward. Regret counts how far the played arms' means fall short of the best mean. No consistent policy keeps regret below order $\log T$, and tuned $\epsilon_t$-greedy, UCB and Thompson sampling all reach that order.
the floor for every consistent policy, and the guarantee UCB meets
Three most common mistakes
Computing regret from the rewards you saw: $\mathrm{Reg}_\pi(T)$ subtracts the means $\mu_{A_t}$ of the arms played.
Using $N_{a,t}$ or $\log_{10}$ in the UCB index: round $t$ uses $N_{a,t-1}$ and the natural log of $t$.
Swapping successes and failures in the Beta posterior, or updating arms that were not played.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The STARS weekly list has as its fourteenth and last item; the lecture slides teach it as chapter 15, problems.
How much time do you have?
10 minutes
Regret from a list of plays, one UCB round and one Thompson round: the three hand computations of the chapter.
The 60-second card · The stochastic bandit · UCB: play the arm that could still be the best · Thompson sampling · Formula card
45 minutes
Every block once with its first worked example, then UCB from a full solution down to a bare problem.
The 60-second card · The stochastic bandit · Regret by arm: every wasted play costs its gap · The lower bound · Greedy and εt-greedy: explore by coin flips · UCB: play the arm that could still be the best · Why UCB's regret grows like log T · Thompson sampling · Scaffolding comes off · Formula card
full read
Adds the proofs, the look-alike pairs, a full exam-style question and mixed practice with the earlier sections.
The opening pages · Recall first · The stochastic bandit · Regret by arm: every wasted play costs its gap · The lower bound · Greedy and εt-greedy: explore by coin flips · UCB: play the arm that could still be the best · Why UCB's regret grows like log T · Thompson sampling · Method boxes · Look-alike pairs · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Describe the stochastic $K$-armed bandit, what the learner observes in each round, and compute the regret of a sequence of plays.
Decompose expected regret into gaps times expected plays, and decide whether a regret rate is sublinear.
Compute Bernoulli KL divergences and the Lai and Robbins constant, and explain why order $\log T$ is the best rate a consistent policy can have.
Run greedy and $\epsilon_t$-greedy by hand, compute the probability of each arm, and explain why a constant $\epsilon$ gives linear regret.
Compute UCB indices and choose arms round by round, and derive the from Hoeffding's inequality.
Reproduce the regret analysis of UCB and evaluate its bound for a given instance.
Run Thompson sampling for Bernoulli arms: update Beta posteriors, choose arms from given draws, and compute the probability that an arm is played.
Syllabus coverage
covered
Multi-armed bandits — covered
The stochastic $K$-armed bandit: arms with unknown reward distributions, the history, policies that map histories to arms, and the greedy trap that motivates exploration.
The lecturer's chapter title. The blocks follow the lecture's order, except that the regret decomposition, which the lecture proves inside the UCB analysis, gets its own block early, because every later block uses it.
covered
Online learning — covered
Learning while acting: rewards arrive one round at a time, each choice decides which data come next, and performance is judged over the whole sequence by regret. Sample means updated one reward at a time.
The fourteenth item of the STARS weekly list. The lecture teaches it through bandits, and so does this section; online learning with full feedback, where every option's reward is revealed each round, appears only as a contrast.
covered
Regret and good policies — covered
Regret of a policy
expected reward versus expected regret
the decomposition by gaps
sublinear regret as the test of a good policy
The lecture's 'What is a good policy?' slide sits here.
covered
Regret lower bound — covered
Consistent policies, the KL divergence of Bernoulli arms, and the Lai and Robbins bound: order $\log T$ is the least regret any consistent policy can have.
Stated without proof in the lecture; here a one-paragraph reason for $\log T$ is added and labelled as a sketch.
covered
Greedy and ε-greedy policies — covered
Greedy play of the best sample mean
exploration with probability $\epsilon_t$
linear regret for a constant $\epsilon$ and $O(K\log T/\Delta_{\min}^2)$ for $\epsilon_t=cK/(\Delta_{\min}^2t)$
The bound is quoted as in the lecture.
covered
UCB policy — covered
The index $g_{a,t}$
why the bonus $\sqrt{2\log t/N_{a,t-1}}$ makes $g_{a,t}$ an
covered
Regret analysis of the UCB policy — covered
The threshold $m=\lceil8\log T/\Delta_a^2\rceil$, the failures of the two confidence bounds, the union bound over play counts, and the resulting bound.
The union bound the lecture mentions in one line is written out.
covered
Thompson sampling — covered
Posterior sampling in its two equivalent forms
the Beta-Bernoulli algorithm
its asymptotically optimal regret bound
covered
Empirical comparison — covered
Tuned $\epsilon_t$-greedy, UCB and Thompson sampling on the same instance.
The lecture's plots are not reproduced; a simulation of the same kind was run for this page and its numbers are in the table of the Thompson sampling block.
covered
Bandits and reinforcement learning — covered
A bandit is a reinforcement learning problem with a single state.
The link to the previous section returns in two interleaved practice questions.
Recall first
Hoeffding's inequality, one side at a time
For independent $Z_1,\dots,Z_n\in[0,1]$ with mean $\mu$ and average $\bar Z$: $\Pr(\bar Z-\mu\ge\varepsilon)\le e^{-2n\varepsilon^2}$ and $\Pr(\bar Z-\mu\le-\varepsilon)\le e^{-2n\varepsilon^2}$. Adding the two gives the two-sided bound $2e^{-2n\varepsilon^2}$ of the probability review.
The UCB bonus is the $\varepsilon$ that makes one side equal $t^{-4}$.
The UCB proof adds failure probabilities over every possible play count.
Counting with indicators
$N=\sum_{t=1}^{T}\mathbb I(E_t)$ counts the rounds in which $E_t$ happens, and $\mathbb E[N]=\sum_{t=1}^{T}\Pr(E_t)$.
Regret is written through the play counts $N_{a,T}$ and their expectations.
Beta posterior for a success rate
With prior $\mathrm{Beta}(a,b)$ and data of $N_1$ successes and $N_0$ failures, the posterior is $\mathrm{Beta}(a+N_1,\,b+N_0)$, with mean $\frac{a+N_1}{a+b+N_1+N_0}$. $\mathrm{Beta}(1,1)$ is uniform on $[0,1]$.
Thompson sampling keeps one such posterior per arm.
Two sums
$\sum_{t=1}^{T}\frac1t=\log T+0.5772+\text{(a term below }\tfrac1{2T})$ and $\sum_{t=1}^{\infty}\frac1{t^2}=\frac{\pi^2}{6}$.
The first counts the random plays of $\epsilon_t$-greedy, the second gives the $\pi^2/3$ in the UCB bound.
Agent, action, reward and the ε-greedy rule
From the reinforcement learning section: an agent takes action $A_t$ and collects reward; $\epsilon$-greedy explores with probability $\epsilon$ (an action chosen uniformly at random) and otherwise takes the action with the largest estimated value. Q-learning updates $Q\leftarrow(1-\alpha)Q+\alpha\hat Q$.
A bandit is that problem with a single state, and its first policies are these rules.
Try it yourself first (2 questions)
1§15.7 — updating a uniform prior
A new button's click rate $\theta$ gets the uniform prior $\mathrm{Beta}(1,1)$. Ten visitors then see it: 7 click and 3 do not.
Find(a) What is the posterior of $\theta$?
Given
prior $\mathrm{Beta}(1,1)$
7 clicks, 3 non-clicks
Hint 1/4
Name the prior's two parameters and decide which count feeds which.
Hint 2/4
Beta prior and Bernoulli data: $\mathrm{Beta}(a,b)$ becomes $\mathrm{Beta}(a+N_1,\,b+N_0)$.
Hint 3/4
Here $a=b=1$, $N_1=7$ clicks and $N_0=3$ non-clicks.
Hint 4/4
So the posterior is $\mathrm{Beta}(8,4)$, with mean $8/12=0.667$.
Show solution
The Beta family is conjugate to Bernoulli data, so the update is two additions; no integral is needed.
Add the counts
$$\mathrm{Beta}(1+7,\,1+3)=\mathrm{Beta}(8,4)$$
Clicks go to the first parameter, non-clicks to the second.
Shape check: the posterior density is proportional to $\theta^{7}(1-\theta)^{3}$, the likelihood times the flat prior, and $\mathrm{Beta}(8,4)$ has exactly that shape.
With a uniform prior, $\mathrm{Beta}(1+\text{successes},\,1+\text{failures})$; Thompson sampling keeps one per arm.
2§15.2 — adding up probabilities of rare events
A test page shows a banner in round $t$ with probability $1/t$, for $t=1,\dots,100$, independently across rounds. Let $N$ be the number of rounds in which the banner is shown.
Find(a) What is $\mathbb E[N]$, to two decimals?
Given
$\Pr(\text{shown in round }t)=1/t$, $t=1,\dots,100$
$\sum_{t=1}^{100}1/t=5.1874$, $\ln100=4.6052$
Hint 1/4
Write $N$ as a sum of one yes-or-no variable per round.
Hint 2/4
$N=\sum_t\mathbb I(\text{shown in round }t)$, so $\mathbb E[N]=\sum_t\Pr(\text{shown in round }t)$.
Hint 3/4
Here the probabilities are $1, \allowbreak \tfrac12, \allowbreak \tfrac13, \allowbreak \dots, \allowbreak \tfrac1{100}$, whose sum is given as $5.1874$.
Hint 4/4
So $\mathbb E[N]=5.19$.
Show solution
Linearity of expectation needs no independence and no distribution of $N$: add the probabilities.
Round $t$ decides with $\mathcal H_t$, before its own reward.
$\pi$
pi
a policy: a rule from histories to distributions over arms
Deterministic policies put probability 1 on one arm.
$\mathrm{Reg}_\pi(T)$
regret of pi after T rounds
$T\mu^*-\sum_{t=1}^{T}\mu_{A_t}$
Uses means, not observed rewards.
$\Delta_a,\ \ \Delta_{\min}$
gap of a; smallest gap
$\mu^*-\mu_a$; the smallest gap among worse arms
$\Delta_{a^*}=0$.
$N_{a,t}$
N a t
$\sum_{s=1}^{t}\mathbb I(A_s=a)$, plays of arm $a$ in rounds $1,\dots,t$
Round $t$'s index uses $N_{a,t-1}$.
$\hat\mu_{a,t-1}$
mu hat a, t minus 1
the average reward of arm $a$ over its plays in rounds $1,\dots,t-1$
Not the average over all rounds.
$\epsilon_t$
epsilon t
the of round $t$
A probability: capped at $1$.
$g_{a,t}$
g a t
the UCB index $\hat\mu_{a,t-1}+\sqrt{2\log t/N_{a,t-1}}$
Can exceed 1.
$\alpha_{a,t-1},\ \beta_{a,t-1}$
alpha, beta
successes and failures of arm $a$ in rounds $1,\dots,t-1$
Posterior $\mathrm{Beta}(1+\alpha,1+\beta)$.
$\tilde\mu_{a,t}$
mu tilde a t
the draw from arm $a$'s posterior in round $t$
The tilde marks a random draw.
$\mathrm{KL}(a,a^*)$
KL of a from a star
the of $F_a$ from $F_{a^*}$
Not symmetric: order matters.
$\log$
natural log
logarithm to base $e$
Never base 10 here.
Conventions used here
Natural logarithms and rounding.
$\log$ is the natural logarithm. Numbers are computed from unrounded values and printed to 4 decimals. This includes the $\log t$ inside every UCB bonus.
The UCB bonus and the bound's $t^{-4}$ both need base $e$.
What round t may use.
Round $t$ decides with rounds $1,\dots,t-1$ only: $N_{a,t-1}$, $\hat\mu_{a,t-1}$, $\alpha_{a,t-1}$, $\beta_{a,t-1}$. After the play, the chosen arm's numbers move on to $t$.
Putting $N_{a,t}$ into round $t$'s index is the most common slip.
Ties between arms.
When two arms have the same sample mean, index or draw, the lower-numbered arm is played.
The lecture leaves ties open; a fixed rule makes every run checkable.
Random numbers in questions.
Where a policy randomizes, the question gives the outcome: the $\epsilon_t$ coin as a uniform $u$ (explore when $u<\epsilon_t$) and then the explored arm, or the Thompson draws $\tilde\mu_{a,t}$ themselves.
The policy is what is being tested, not a random number generator.
Regret is computed from means.
$\mathrm{Reg}_\pi(T)$ uses the means $\mu_{A_t}$ of the arms played; the observed rewards only decide what the policy does next.
This is the lecture's definition; the shortfall of the observed rewards is a different, noisier number.
Warm-up rounds.
Greedy, $\epsilon_t$-greedy and UCB play arms $1,\dots,K$ once each in rounds $1,\dots,K$, in order. Thompson sampling needs no warm-up.
As in the lecture: the index needs $N_{a,t-1}\ge1$.
Rewards in examples.
Every numerical example has rewards $0$ or $1$, a click or a redemption, so each $\mu_a$ is a probability. The theory only needs rewards in $[0,1]$.
Bernoulli arms keep the arithmetic short and match the Thompson sampling slides.
15.1The stochastic bandit: one arm per round, one reward seen
Sets up the game: play one arm per round, see only its reward, and judge the policy by its regret.
The previous section's agent moved between states. Here there is one state, and every round asks the same question again: which arm, given what we have seen?
Solvable with what we have
Estimate a redemption rate from 200 logged customers, with a Hoeffding interval.
Compare two designs that were each shown to 100 customers.
Update a Beta posterior for one design as results arrive.
Not solvable yet
Choose the design for the next customer when each showing of the worse one costs a redemption.
Learn about a design you stopped offering: its data stop.
Judge 6,300 redemptions in 10,000 without knowing the best rate.
The obvious rule: offer each coupon once, then always the one with the better record so far. With 10,000 customers the averages should settle, so the rule should find A.
Why it fails
Only the coupon on offer gets new data. If A misses and B scores on the first two customers, B's average can never fall back to 0 and A is never offered again: $0.4\times0.4$, so 16 shops in 100.
DefinitionDefinition 15.1: Stochastic K-armed bandit and regret
Conditions
arms $a\in\mathcal A=\{1,\dots,K\}$; arm $a$ pays $R_{a,t}\in[0,1]$ drawn from an unknown $F_a$, independently across rounds and arms
round $t$ is decided from the history $\mathcal H_t=\{A_1, \allowbreak R_{A_1,1}, \allowbreak \dots, \allowbreak A_{t-1}, \allowbreak R_{A_{t-1},t-1}\}$ only
$$\boxed{\begin{aligned}&A_t\sim\pi(\cdot\mid\mathcal H_t),\qquad\text{observe only }R_{A_t,t}\sim F_{A_t}\\&\mu_a=\mathbb E[R_{a,t}],\qquad a^*=\arg\max_a\mu_a,\qquad\mu^*=\mu_{a^*}\\&\mathrm{Reg}_\pi(T)=T\mu^*-\sum_{t=1}^{T}\mu_{A_t}\\&\mathbb E\Big[\sum_{t=1}^{T}R_{A_t,t}\Big]=T\mu^*-\mathbb E[\mathrm{Reg}_\pi(T)]\end{aligned}}$$
Each round the policy picks an arm from what it has seen, and learns that arm's reward alone. Regret adds up, round by round, how far the played arm's mean falls short of the best mean. Expected reward plus expected regret is always $T\mu^*$, so maximizing one is minimizing the other.
Why expected reward and expected regret add up to Tμ*
Given the history and $A_t=a$, the reward is a fresh draw from $F_a$, so $\mathbb E[R_{A_t,t}\mid\mathcal H_t,A_t]=\mu_{A_t}$.
Take expectations and add over rounds: $\mathbb E\big[\sum_tR_{A_t,t}\big]=\mathbb E\big[\sum_t\mu_{A_t}\big]=T\mu^*-\mathbb E[\mathrm{Reg}_\pi(T)]$.
$T\mu^*$ does not depend on the policy, so the policy with the largest expected reward is the one with the smallest expected regret. This is the lecture's 'Fact'.
A shop whose first two customers went A: no, B: yes. $\textcolor{#1f6feb}{\text{Coupon A}}$'s estimate is stuck at 0 while its true rate is 0.6; $\textcolor{#d1690a}{\text{coupon B}}$ is offered every round and its estimate settles near 0.4. Nothing in the rule sends a customer back to A.
Looks like this, but is not
A warehouse robot picks one of four moves at every step and collects a reward. That looks like a 4-armed bandit.
Its move changes where it stands, so the same move pays differently at the next step: the state carries over, as in the Markov decision process of the previous section. A bandit has one state, and every round offers the same arms with the same distributions.
round t
arm played
arm 1
arm 2
arm 3
1
1
1
?
?
2
2
?
0
?
3
3
?
?
0
4
1
0
?
?
5
1
1
?
?
6
2
?
1
?
Eighteen rewards were drawn and six were seen, one per row, chosen by the learner itself. With full feedback every cell would be visible and there would be nothing to explore.
The best-record-so-far rule locks onto the worse coupon in 16 shops out of 100
Coupon A is redeemed with probability $0.6$ and coupon B with $0.4$. A shop offers A to customer 1 and B to customer 2, then always offers the coupon with the higher redemption rate so far, A on a tie. Bound the probability that A is never offered again, and the expected regret after $T$ customers.
FindA lower bound on $\Pr(\text{A never offered after round 2})$ and on $\mathbb E[\mathrm{Reg}(T)]$.
Given
$\mu_A=0.6$, $\mu_B=0.4$, rewards $0$ or $1$
rounds 1 and 2: A, then B; after that, the higher sample mean, A on a tie
Solution
Look for one early event that settles the whole run; a lower bound does not need the probabilities of the other runs.
An event that locks the rule
$$\Pr(R_{A,1}=0,\ R_{B,2}=1)=0.4\times0.4=0.16$$
The first two rewards are independent: A misses with probability $0.4$, B scores with probability $0.4$.
Why A never comes back
$$\hat\mu_{A,t-1}=0<\frac{1}{N_{B,t-1}}\le\hat\mu_{B,t-1}\quad\text{for every }t\ge3$$
A gets no new data, so its average stays 0; B's first success stays in its average, which therefore never reaches 0.
Regret is never negative, so the other shops can only add to the average.
Answer $$\boxed{\Pr(\text{A never again})\ge0.16,\qquad\mathbb E[\mathrm{Reg}(T)]\ge0.032\,(T-1)}$$
Check
A simulation of 20,000 such shops found 3,234 whose first two customers went A: no, B: yes (16 in 100), and 3,799 still offering B at customer 1,000 (19 in 100); tied starts add some locked shops of their own.
The regret of this rule is linear: at least 320 lost redemptions per 10,000 customers here, and the loss never stops growing.
Keeping three running averages one reward at a time
Three headlines are tested on readers, one headline per reader. The first six rounds play the arms $1,2,3,1,1,2$ and see the clicks $1,0,0,0,1,1$. Keep each arm's count and sample mean up to date without storing the rewards.
Find$N_{a,6}$ and $\hat\mu_{a,6}$ for the three arms.
Given
plays $1,2,3,1,1,2$
clicks $1,0,0,0,1,1$
Solution
The running-mean update $\hat\mu\leftarrow\hat\mu+(r-\hat\mu)/N$ touches only the arm that was played, which is exactly what allows.
Rounds 1 to 3: first plays
$$N=(1,1,1),\qquad\hat\mu=(1,\ 0,\ 0)$$
An arm's first reward is its average.
Round 4: arm 1 pays 0
$$\hat\mu_1\leftarrow1+\frac{0-1}{2}=0.5$$
The new reward is 1 of 2, so it moves the average half of the way.
Round 5: arm 1 pays 1
$$\hat\mu_1\leftarrow0.5+\frac{1-0.5}{3}=0.6667$$
Now it is 1 of 3 rewards, so it moves the average by a third of the surprise.
Round 6: arm 2 pays 1
$$\hat\mu_2\leftarrow0+\frac{1-0}{2}=0.5$$
Arms 1 and 3 were not played, so their averages stay.
Expected regret is a sum over arms: each arm's gap times how often you expect to play it. Plays of the best arm cost nothing. A good policy is one whose regret per round dies out, whatever the arms turn out to be.
Proof of the decomposition
One indicator per round. Exactly one arm is played in round $t$, so $\mu_{A_t}=\sum_a\mu_a\mathbb I(A_t=a)$ and $\mu^*=\sum_a\mu^*\mathbb I(A_t=a)$.
Swap the sums.$\sum_t(\mu^*-\mu_{A_t})=\sum_a(\mu^*-\mu_a)\sum_t\mathbb I(A_t=a)=\sum_a\Delta_aN_{a,T}$. This holds run by run, before any expectation.
Average. The gaps are constants, so $\mathbb E[\mathrm{Reg}_\pi(T)]=\sum_a\Delta_a\mathbb E[N_{a,T}]$.
Ten rounds with means $0.7,\ 0.5,\ 0.2$: each bar is the gap of the arm played. Grouping the bars by arm gives $\textcolor{#d1690a}{2\times0.2}+\textcolor{#8250df}{2\times0.5}=1.4$, the decomposition in miniature; $\textcolor{#1f6feb}{\text{arm 1}}$ adds nothing.
Looks like this, but is not
A policy that loses one click in every 1,000 rounds, $\mathbb E[\mathrm{Reg}(T)]=0.001T$, looks nearly perfect.
Its regret per round stays at $0.001$ forever, so it is linear and not a good policy. A policy with $5\sqrt T$ loses more up to $T=25$ million and less after: good is a statement about the limit, not about one horizon.
T
0.001 T
5 √T
3 log T
$10^4$
$10$
$500$
$27.6$
$10^6$
$1{,}000$
$5{,}000$
$41.4$
$2.5\times10^7$
$25{,}000$
$25{,}000$
$51.1$
$10^9$
$1{,}000{,}000$
$158{,}114$
$62.2$
Per round, $0.001T$ stays at $0.001$ while the other two shrink to $0$. The $5\sqrt T$ policy loses more than the linear one until $T=25$ million, and less after.
Regret of choosing a headline uniformly at random
Headlines with $\mu=(0.7,\ 0.5,\ 0.2)$ are chosen uniformly at random in every round, whatever the feedback. Find $\mathbb E[\mathrm{Reg}(T)]$ and the regret per round.
Find$\mathbb E[\mathrm{Reg}(T)]$ and $\mathbb E[\mathrm{Reg}(T)]/T$.
Given
$\mu=(0.7,\ 0.5,\ 0.2)$
$\Pr(A_t=a)=\frac13$ in every round
Solution
The decomposition needs only the expected plays, and counting with indicators gives them in one line.
From the definition: a random round's expected mean is $(0.7+0.5+0.2)/3=0.4667$, and $0.7-0.4667=0.2333$.
Exploring forever is linear too: never using what you learned wastes a fixed share of rounds, just as never exploring does.
Expected regret of UCB from its average play counts
In 1,000 simulated runs of UCB on $\mu=(0.7,\ 0.5,\ 0.2)$ with $T=10{,}000$, the arms were played on average $9629.8$, $307.7$ and $62.5$ times. Estimate $\mathbb E[\mathrm{Reg}(10{,}000)]$.
Find$\mathbb E[\mathrm{Reg}(10{,}000)]$ and the regret per round.
Given
$\mu=(0.7,\ 0.5,\ 0.2)$, $T=10{,}000$
average plays $9629.8$, $307.7$, $62.5$
Solution
The decomposition turns play counts straight into regret, and only the two worse arms enter.
No policy that learns on every instance can keep its regret below a fixed multiple of $\log T$. Each worse arm must be played about $\log T$ over KL times, KL measuring how easily its rewards are told apart from the best arm's, and each play costs the arm's gap.
Why log T: a sketch, not the proof
To rule arm $a$ out, a policy must play it until its rewards could not come from an arm with mean just above $\mu^*$.
After $n$ plays, rewards of $\mathrm{Ber}(\mu_a)$ still look like rewards of $\mathrm{Ber}(\mu^*)$ with probability roughly $e^{-n\,\mathrm{KL}(a,a^*)}$.
If that probability stayed above about $1/T$, then on the instance where $a$ really is best the policy would neglect $a$ often enough to lose far more than $\log T$, which consistency forbids. So $n\gtrsim\log T/\mathrm{KL}(a,a^*)$.
Each of those plays costs $\Delta_a$; adding over the worse arms gives the bound.
With $\textcolor{#1f6feb}{\mu^*=0.7}$, the plays a worse arm needs per unit of $\log T$, which is $1/\mathrm{KL}$: $\textcolor{#8250df}{1.9}$ for an arm at $0.2$, $\textcolor{#d1690a}{11.5}$ for an arm at $0.5$, and without limit as the arm's mean approaches $0.7$.
Looks like this, but is not
The policy 'always play arm 1' has zero regret whenever arm 1 is best, which beats $\log T$.
It is not consistent: on an instance where arm 1 is worst its regret is linear. The bound binds only policies that must learn on every instance, and betting on one instance is not learning.
μa
Δa
KL(a, a*)
plays per log T
regret per log T
$0.1$
$0.6$
$0.7942$
$1.26$
$0.76$
$0.2$
$0.5$
$0.5341$
$1.87$
$0.94$
$0.3$
$0.4$
$0.3389$
$2.95$
$1.18$
$0.4$
$0.3$
$0.1920$
$5.21$
$1.56$
$0.5$
$0.2$
$0.0872$
$11.47$
$2.29$
$0.6$
$0.1$
$0.0226$
$44.28$
$4.43$
$0.65$
$0.05$
$0.0058$
$172.93$
$8.65$
Moving the worse arm from $0.1$ to $0.65$ multiplies the plays it needs by about 137 and its share of the constant by about 11.
The floor for the headline test
For Bernoulli headlines with $\mu=(0.7,\ 0.5,\ 0.2)$, compute $\mathrm{KL}(a,a^*)$ for the two worse arms, the Lai and Robbins constant, and what it says at $T=10{,}000$.
FindThe two KL values, the constant $C$ and $C\log T$.
Given
$\mu^*=0.7$, $\mu_2=0.5$, $\mu_3=0.2$
$\log10{,}000=9.2103$
Solution
The Bernoulli KL formula is two terms per arm, and the constant is one division per arm.
Size check: for close means, KL is about $\Delta^2/(2\sigma^2)$ with $\sigma^2$ between $0.21$ and $0.25$, which brackets arm 2's value: $0.080\le0.0872\le0.095$.
Arm 2 carries 71 parts in 100 of the constant: close arms, not bad arms, set the price of learning.
A close arm is harder than a far one
Two 2-armed Bernoulli instances share $\mu^*=0.7$; the other arm has mean $0.65$ in the first and $0.3$ in the second. Compare their Lai and Robbins constants and the plays the worse arm needs.
Find$\Delta/\mathrm{KL}$ and $1/\mathrm{KL}$ for both instances.
Given
instance 1: $\mu=(0.7,\ 0.65)$
instance 2: $\mu=(0.7,\ 0.3)$
Solution
Each instance has a single worse arm, so each constant is one gap over one KL.
Ratio check: the close arm costs 8 times less per play ($0.05$ against $0.4$) but needs $172.93/2.95=58.6$ times the plays, and $58.6/8=7.3$ is the ratio $8.6467/1.1802$.
A tiny gap is cheap per mistake and expensive in mistakes, and the count wins.
Checkpoint
§15.3 — a claim below the floor
A preprint claims a policy whose expected regret is at most $3\sqrt{\log T}$ for every $T$ and every Bernoulli instance with two arms of different means.
Find(a) What does the Lai and Robbins bound say about the claim?
Givenclaimed: $\mathbb E[\mathrm{Reg}(T)]\le3\sqrt{\log T}$ on every such instance
Hint 1/4
Decide first whether the claimed policy would be consistent, then compare its growth with the floor.
Hint 2/4
Consistent: $\mathbb E[\mathrm{Reg}]/T^p\to0$ for all $p>0$. Floor: $\liminf\mathbb E[\mathrm{Reg}]/\log T\ge C>0$.
Hint 3/4
Here $3\sqrt{\log T}/T^p\to0$, so the policy is consistent, and $3\sqrt{\log T}/\log T=3/\sqrt{\log T}\to0$.
Hint 4/4
The ratio tends to $0$, below every positive constant, so the claim contradicts the bound.
Show solution
The theorem applies only to consistent policies, so consistency is checked first.
Consistent
$$\frac{3\sqrt{\log T}}{T^p}\to0\ \text{for every }p>0$$
The constant is computed for a concrete instance, so plugging in a concrete $T$ feels natural. Our Thompson sampling runs had regret $17.5$ at $T=10{,}000$, below $29.75$, and that is no contradiction.
wrong$$\mathbb E[\mathrm{Reg}(10^4)]\ge29.75\ \text{for every consistent policy}$$
Greedy always plays the best average so far. $\epsilon_t$-greedy does the same, except that with probability $\epsilon_t$ it plays an arm drawn uniformly, possibly the leader itself. With a constant $\epsilon$ the random plays never stop and regret is linear; with $\epsilon_t$ proportional to $1/t$ they add up to about $\log T$.
Where the log T comes from
Count the random plays. Their expected number in rounds $K+1,\dots,T$ is $\sum_t\epsilon_t\approx\frac{cK}{\Delta_{\min}^2}\log\frac TK$, by the harmonic sum.
Split them over the arms. A random play hits arm $a$ with probability $\frac1K$, so arm $a$ gets about $\frac{c}{\Delta_{\min}^2}\log\frac TK$ of them at $\Delta_a$ each: the log term of the bound.
The rest. The random plays also keep every sample mean accurate, so exploiting rounds rarely pick a worse arm; those rare mistakes and the warm-up make the other term.
Constant ε. The same count is $\epsilon(T-K)$, so regret grows at least like $\epsilon(T-K)\frac1K\sum_a\Delta_a$: linear.
Expected random plays so far, three arms: $\textcolor{#d1690a}{\epsilon=0.1}$ adds one every 10 rounds and reaches about 1000 by $t=10{,}000$; $\textcolor{#1f6feb}{\epsilon_t=\min\{1,18.75/t\}}$ reaches about 133.
Looks like this, but is not
A tiny constant $\epsilon=0.01$ looks like greedy with a safety net, and cheap.
It explores in 1 round of every 100, forever. With gaps $0.2$ and $0.5$ among three arms that costs at least $0.01\times0.7/3=0.0023$ per round: linear. Only a shrinking $\epsilon_t$ keeps the cost near $\log T$.
round t
εt
chance of the leader
chance of each other arm
random plays so far
$10$
$1$
$0.3333$
$0.3333$
$7.00$
$100$
$0.1875$
$0.875$
$0.0625$
$46.73$
$1{,}000$
$0.01875$
$0.9875$
$0.00625$
$89.82$
$10{,}000$
$0.001875$
$0.99875$
$0.000625$
$132.98$
At $t=10{,}000$ a random play still happens in about 1 round of 533, which is what stops a wrong leader from lasting forever.
One εt-greedy round on the headline test
Three headlines, with $\Delta_{\min}=0.2$ and $c=0.25$, so $\epsilon_t=\min\{1,\,18.75/t\}$. After round 499 the sample means are $(0.64,\ 0.66,\ 0.21)$. Find each arm's probability in round 500, then the arm played if the coin gives $u=0.03$ and the arm draw gives $u'=0.40$, arm $\lfloor3u'\rfloor+1$.
Find$\Pr(A_{500}=a)$ for each arm, and $A_{500}$.
Given
$\epsilon_t=\min\{1,\ 18.75/t\}$, $K=3$
$\hat\mu_{\cdot,499}=(0.64,\ 0.66,\ 0.21)$
$u=0.03$, $u'=0.40$
Solution
The leader and $\epsilon_{500}$ fix all three probabilities; the two uniforms then play the coin and the draw.
Exploration probability
$$\epsilon_{500}=\frac{18.75}{500}=0.0375$$
After round 18 the cap no longer binds.
Leader
$$\hat a_{500}^*=\arg\max(0.64,\ 0.66,\ 0.21)=2$$
Arm 2 leads by chance; arm 1 has the best true mean.
The three probabilities add up: $0.0125+0.975+0.0125=1$.
Arm 1, the true best, gets 1 round in 80 here, and that trickle is what eventually corrects the ranking.
What the random plays cost up to T = 10,000
Same test, $\mu=(0.7,\ 0.5,\ 0.2)$, with $\epsilon_t=\min\{1,\,18.75/t\}$ from round 4 on. Find the expected number of random plays up to $T=10{,}000$ and their regret, and compare with a constant $\epsilon=0.1$.
FindExpected random plays and their regret for both schedules.
Given
$\epsilon_t=1$ for $4\le t\le18$ and $18.75/t$ after
$\sum_{t=19}^{10{,}000}\frac1t=6.2925$
gaps $0$, $0.2$, $0.5$
Solution
The random plays are the $\log T$ part of the bound, and their expected count is a sum of probabilities.
Count
$$15+18.75\times6.2925=132.98$$
The cap binds in rounds 4 to 18; after that the schedule is $18.75/t$.
The slide writes the schedule without a cap, and in early rounds it exceeds 1.
wrong$$\epsilon_{10}=\frac{18.75}{10}=1.875$$
right$$\epsilon_{10}=\min\{1,\ 1.875\}=1$$
15.5UCB: play the arm that could still be the best
Replaces coin flips with an optimistic index: the sample mean plus a bonus that is large for arms with few plays.
$\epsilon_t$-greedy explores blindly: a random play is as likely to hit a hopeless arm as a promising one. UCB explores where the doubt is.
MethodMethod 15.5: The UCB policy
Conditions
rounds $1,\dots,K$: play each arm once
$N_{a,t-1}$ and $\hat\mu_{a,t-1}$ come from rounds $1,\dots,t-1$, and $\log$ is natural
rewards in $[0,1]$; ties go to the lower index
$$\boxed{\begin{aligned}&t>K:\qquad g_{a,t}=\hat\mu_{a,t-1}+\sqrt{\frac{2\log t}{N_{a,t-1}}}\\&A_t=\arg\max_a\,g_{a,t}\\&\Pr\big(g_{a,t}<\mu_a\big)\le t^{-4}\quad\text{for a fixed }N_{a,t-1}\end{aligned}}$$
Give each arm a score: its average so far plus a bonus that is large when the arm has few plays and grows slowly with the round number. Play the highest score. The score is an upper confidence bound: the true mean lies above it only with probability $t^{-4}$ or less.
Where the bonus comes from
Hoeffding, lower side: with $n$ rewards in $[0,1]$, $\Pr(\hat\mu-\mu\le-\varepsilon)\le e^{-2n\varepsilon^2}$.
Choose $\varepsilon=\sqrt{2\log t/n}$: then $2n\varepsilon^2=4\log t$ and $e^{-4\log t}=t^{-4}$.
So $\Pr(g_{a,t}<\mu_a)=\Pr(\hat\mu_{a,t-1}-\mu_a<-\varepsilon)\le t^{-4}$: the index is below the true mean only rarely, and more rarely as rounds pass.
Hoeffding needs a fixed $n$, but $N_{a,t-1}$ is random; the regret analysis handles that with a union bound.
Round 81: $\textcolor{#1f6feb}{\text{arm 1}}$ has the best mean, $0.667$, but $\textcolor{#d1690a}{\text{arm 2}}$, with 12 plays, has the highest index, $1.356$, and is played; $\textcolor{#8250df}{\text{arm 3}}$ is second. An index above 1 is normal early on: it is a bound, not an estimate.
Looks like this, but is not
The arm with the highest index looks like the arm UCB believes is best.
UCB believes nothing of the kind. In the figure arm 2's average is below arm 1's, and arm 2 is played because it is uncertain. The index answers how good an arm could still be, not how good it is.
arm
plays
mean
bonus at t = 81
index at t = 81
index at t = 82
1
$60$
$0.6667$
$0.3827$
$1.0494$
$1.0499$
2
$12$, then $13$
$0.5000$, then $0.4615$
$0.8558$
$1.3558$
$1.2849$
3
$8$
$0.2500$
$1.0481$
$1.2981$
$1.2996$
The largest index moves from arm 2 to arm 3, and neither has the best mean.
The coupon trap again: UCB offers A in round 5
The coupon shop now uses UCB. Round 1 offers A, not redeemed; round 2 offers B, redeemed. If B is offered in rounds 3 and 4, it pays 0 and then 1. Which coupon does UCB offer in rounds 3, 4 and 5?
Find$A_3$, $A_4$ and $A_5$.
Given
round 1: A pays 0; round 2: B pays 1
B's next two rewards, if offered: 0, then 1
Solution
Two indices per round. A's changes only through $\log t$, which is the point of the example.
Greedy would compare $0$ with $0.6667$ in round 5 and offer B forever. A's index $\sqrt{2\log t}$ is above $1.48$ from round 3 on and keeps growing, so A is always retried.
An arm that is not played gets a growing bonus, so UCB cannot lock an arm out the way greedy did.
Two UCB rounds with three arms
After 80 rounds, arm 1 has 40 clicks in 60 plays, arm 2 has 6 in 12 and arm 3 has 2 in 8. Find the arm UCB plays in round 81; if it pays 0, find the arm in round 82.
Arm 1's index barely moves, $1.0494$ to $1.0499$, because only $\log t$ changed for it; arm 2's index falls by $0.0709$ from its zero and its extra play.
UCB rotates through the uncertain arms; the best-looking arm waits until their indices come down.
Checkpoint
§15.5 — one UCB index
After 20 rounds of UCB, arm 1 has 9 clicks in 15 plays and arm 2 has 2 clicks in 5 plays.
Find(a) What is arm 2's index $g_{2,21}$?
Given
$N_{\cdot,20}=(15,\ 5)$, clicks $(9,\ 2)$
$\log21=3.0445$
Hint 1/4
The index is the sample mean plus a bonus built from the round number and the play count.
Natural log of the current round, plays before it.
Index
$$g_{2,21}=0.4+1.1035=1.5035$$
Mean plus bonus.
Answer $$\boxed{g_{2,21}=1.5035}$$
Check
Arm 1's index is $0.6+\sqrt{6.0890/15}=1.2371$, smaller, so arm 2 is played: fewer plays, larger bonus, as expected.
Read the three numbers off the history first: $t$, $N_{a,t-1}$ and the clicks.
⚠ Using the base-10 log in the bonus
Calculators often have log on the base-10 key.
wrong$$\sqrt{2\log_{10}21/5}=0.7272$$
right$$\sqrt{2\ln21/5}=1.1035$$
⚠ Counting the current round's play in N
After the play the count is $N_{a,t}$, and it is easy to write the updated count into the index.
wrong$$g_{2,21}=0.4+\sqrt{2\log21/6}$$
right$$g_{2,21}=0.4+\sqrt{2\log21/5}$$
⚠ Choosing by the sample mean
The mean is the part of the index that feels like knowledge; the bonus looks like a correction.
wrong$$A_{81}=\arg\max_a\hat\mu_{a,80}=1$$
right$$A_{81}=\arg\max_ag_{a,81}=2$$
Step through rounds 3 to 5 of the coupon shop under UCB. $\textcolor{#1f6feb}{\text{A}}$'s index grows with $\log t$ while it waits, $\textcolor{#d1690a}{\text{B}}$'s shrinks as it is played, and in round 5 A is offered again.
At the edges
t = 3 B: 2.482
B's single success puts its index a full 1 above A's.
t → ∞ A: √(2 log t)
A's index grows without bound while it waits, so A is always offered again eventually.
15.6Why UCB's regret grows like log T
Bounds how often UCB plays a worse arm: about 8 log T over the squared gap, plus a constant.
By the decomposition, bounding $\mathbb E[N_{a,T}]$ for every worse arm bounds UCB's regret, and the bonus was built so that this works.
TheoremTheorem 15.6: Regret of UCB
Conditions
rewards in $[0,1]$, independent across rounds and arms
UCB as in Method 15.5; $\Delta_a=\mu^*-\mu_a>0$ for a worse arm
A worse arm is played at most about $8\log T$ over its squared gap times, plus about $3.3$ more for the rare rounds when a confidence bound fails. Multiplying by the gap and adding over arms, regret grows like $\log T$ divided by the gaps.
The proof in five moves
Split the plays. Fix a worse arm $a$ and a threshold $m$. After round $K$ it is played at most $m-1$ times while $N_{a,t-1}<m$; every other play has $N_{a,t-1}\ge m$ and $g_{a,t}\ge g_{a^*,t}$. So $N_{a,T}\le m+\sum_{t=K+1}^{T}\mathbb I(g_{a,t}\ge g_{a^*,t},\,N_{a,t-1}\ge m)$.
Narrow enough. Take $m=\lceil8\log T/\Delta_a^2\rceil$. If $N_{a,t-1}\ge m$ and $t\le T$, the bonus of $a$ is at most $\sqrt{2\log T\,\Delta_a^2/(8\log T)}=\Delta_a/2$.
Both bounds hold, so a is not played. With bonus $c_a\le\Delta_a/2$, if $\hat\mu_{a,t-1}-c_a<\mu_a$ and $g_{a^*,t}>\mu^*$, then $g_{a,t}<\mu_a+2c_a\le\mu^*<g_{a^*,t}$. So $g_{a,t}\ge g_{a^*,t}$ needs a failed LCB of $a$ or a failed UCB of $a^*$.
Failures are rare. For fixed play counts each failure has probability at most $t^{-4}$. The counts are random, so add over every $s<t$ for $a$ and every $s^*<t$ for $a^*$: fewer than $t^2$ pairs, two failures each, at most $2t^{-2}$.
Add over rounds. $\sum_t2t^{-2}\le2\cdot\frac{\pi^2}{6}=\frac{\pi^2}{3}$, so $\mathbb E[N_{a,T}]\le m+\frac{\pi^2}{3}\le\frac{8\log T}{\Delta_a^2}+1+\frac{\pi^2}{3}$. Multiply by $\Delta_a$ and add over arms, Theorem 15.2.
The key step with $\Delta_a=0.2$: once $\textcolor{#d1690a}{\text{arm }a}$'s half-width is at most $\Delta_a/2$ and both bounds hold, its index, $0.63$, lies below $\textcolor{#1f6feb}{\mu^*=0.7}$, which lies below $\textcolor{#1f6feb}{a^*}$'s index, $0.78$.
Looks like this, but is not
A tiny gap means each wasted play costs almost nothing, so an arm with a tiny gap should cost almost no regret.
Each play is cheap, but the arm needs about $8\log T/\Delta^2$ plays, so its term is $8\log T/\Delta$: halving the gap doubles it. For extreme gaps the bound says nothing: $\Delta=0.001$, $T=10{,}000$ gives $73{,}683$, while that arm can never cost more than $\Delta T=10$.
arm
Δa
m
bound on plays
simulated plays
regret bound
simulated regret
2
$0.2$
$1843$
$1846.29$
$307.7$
$369.26$
$61.54$
3
$0.5$
$295$
$298.29$
$62.5$
$149.14$
$31.25$
total
$518.40$
$92.79$
The bound overcounts the plays about 6 times on arm 2 and 5 times on arm 3; both columns grow like $\log T$.
UCB's guarantee for the headline test at T = 10,000
For $\mu=(0.7,\ 0.5,\ 0.2)$ and $T=10{,}000$, compute the UCB threshold $m_a=\lceil8\log T/\Delta_a^2\rceil$ and the bound $\mathbb E[N_{a,T}]\le m_a+\pi^2/3$ for both worse arms, the regret bound $\sum_a\Delta_a\,\mathbb E[N_{a,T}]$ and its formula form $8\sum_a\log T/\Delta_a+(1+\pi^2/3)\sum_a\Delta_a$, and compare with a simulation of UCB.
The simulation stays inside: plays $307.7\le1846.29$ and $62.5\le298.29$, regret $92.8\le518.40$.
The bound is about 5.6 times the truth here; it guarantees the $\log T$ shape, not the number.
From T = 10,000 to T = 1,000,000
For $\mu=(0.7,\ 0.5,\ 0.2)$ (gaps $0.2$ and $0.5$), compute UCB's formula regret bound $8\sum_a\log T/\Delta_a+(1+\pi^2/3)\sum_a\Delta_a$ at $T=10^6$, and compare its growth from $T=10^4$ with the growth of $T$.
FindThe bound at $10^6$ and its ratio to the bound at $10^4$.
Given
$\mu=(0.7,\ 0.5,\ 0.2)$, gaps $0.2$ and $0.5$, $\pi^2/3=3.2899$
$\log10^6=13.8155$
bound at $10^4$: $518.78$
Solution
Only $\log T$ changes, so the bound is a straight line in $\log T$.
Keep a Beta posterior for each arm's success rate. Each round, draw one plausible rate from every posterior, play the highest draw, and add the reward to that arm's counts. Each arm is played with exactly the posterior probability that it is the best, and the regret bound meets the Lai and Robbins floor.
Why sampling an instance is sampling the best arm
The draws $(\tilde\mu_{1,t},\dots,\tilde\mu_{K,t})$ are one sample of the unknown means from their joint posterior.
$A_t=a$ exactly when $\tilde\mu_{a,t}$ is the largest draw, so $\Pr(A_t=a\mid\mathcal H_t)$ is the posterior probability that $\mu_a$ is the largest mean, $\Pr(a^*=a\mid\mathcal H_t)$.
These are the lecture's two forms of the algorithm: sample $a^*$ from its posterior, or sample an instance and play its best arm.
The regret bound is quoted from the lecture, which states it without proof. Its constant, $\Delta_a/\mathrm{KL}(a,a^*)$, is the one of Theorem 15.3, so for Bernoulli arms no consistent policy can do better as $T\to\infty$.
Three posteriors and one draw from each: $\textcolor{#1f6feb}{\text{arm 1}}$ draws $0.52$, $\textcolor{#d1690a}{\text{arm 2}}$ draws $0.71$ and $\textcolor{#8250df}{\text{arm 3}}$ draws $0.18$. Arm 2 is played although its posterior mean, $0.5$, is below arm 1's, $0.6$: its wide posterior wins the draw in about 35 rounds of 100.
Looks like this, but is not
Thompson sampling looks like 'play the arm with the highest posterior mean', a Bayesian greedy.
That rule is greedy and can lock an arm out in the same way. Thompson sampling plays each arm with the probability that it is best, so the coupon shop with $\mathrm{Beta}(1,2)$ for A and $\mathrm{Beta}(2,1)$ for B still offers A in 1 round of 6.
policy
explores by
exploration adapts to data
randomized
regret order
simulated regret
greedy
not at all
no
no
linear
$543.7$
$\epsilon=0.1$
coin flips, forever
no
yes
linear
$242.5$
$\epsilon_t=\min\{1,18.75/t\}$
coin flips, fading
no
yes
$K\log T/\Delta_{\min}^2$
$35.3$
UCB
optimism
yes
no
$\sum_a\log T/\Delta_a$
$92.8$
Thompson
posterior draws
yes
yes
$\sum_a\log T/\Delta_a$
$17.5$
Thompson sampling lost the least and the tuned schedule came second, while UCB paid for its generous bonus. The schedule needed $\Delta_{\min}$, which a learner does not know: $c=0.1$ gave $50.0$, with a standard error of $7.3$ against $0.9$.
One Thompson round with three headlines
With uniform priors, arm 1 has 5 clicks and 3 misses so far, arm 2 has 1 and 1, arm 3 has 0 and 2. This round's draws are $\tilde\mu=(0.52,\ 0.71,\ 0.18)$ and the played arm pays 0. Find the posteriors, the arm played and the posteriors after the update.
FindThe posteriors before and after, and $A_t$.
Given
$(\alpha,\beta)$: arm 1 $(5,3)$, arm 2 $(1,1)$, arm 3 $(0,2)$
draws $(0.52,\ 0.71,\ 0.18)$; the played arm pays 0
Solution
The draws are given, so the round is bookkeeping: posteriors, argmax, one update.
Before the draw, arm 2 wins with probability $\int f_2F_1F_3\,dx=0.3469$ by numerical integration, so this outcome comes about 35 rounds in 100.
The zero pulls arm 2's posterior mean from $0.5$ to $0.4$, so its next draw is less likely to win.
The coupon trap under Thompson sampling
The coupon shop uses Thompson sampling with uniform priors. Its first two rounds went: A offered, not redeemed; B offered, redeemed. With what probability does it offer A in round 3?
Find$\Pr(A_3=A)$.
Given
A: 0 successes, 1 failure
B: 1 success, 0 failures
priors $\mathrm{Beta}(1,1)$
Solution
By the box, it is $\Pr(\tilde\mu_A>\tilde\mu_B)$ for independent Beta draws; with these small parameters the integral is a polynomial.
Condition on A's draw $x$: B's draw must fall below it.
Answer $$\boxed{\Pr(A_3=A)=\tfrac16}$$
Check
Order statistics: a $\mathrm{Beta}(1,2)$ draw is the smaller of two uniforms and a $\mathrm{Beta}(2,1)$ draw the larger of two others. A wins only when both of its uniforms lie above both of B's, 4 of the $4!=24$ orderings: $\frac16$.
Greedy offers A with probability 0 here; Thompson sampling keeps a 1 in 6 chance, and that chance is how the trap is escaped.
Checkpoint
§15.7 — one Thompson update
Thompson sampling with uniform priors on two arms: arm 1 has 3 successes and 1 failure, arm 2 has never been played. This round the draws are $\tilde\mu=(0.58,\ 0.63)$, and the played arm pays 1.
Find(a) Which arm is played, and what is its posterior after this round?
Given
arm 1: $(\alpha,\beta)=(3,1)$; arm 2: $(0,0)$
draws $(0.58,\ 0.63)$; the played arm pays 1
Hint 1/4
First decide which arm is played; only that arm's posterior changes.
Hint 2/4
$A_t=\arg\max_a\tilde\mu_{a,t}$; a reward of 1 turns $\mathrm{Beta}(1+\alpha,1+\beta)$ into $\mathrm{Beta}(2+\alpha,1+\beta)$.
Hint 3/4
Here the draws are $0.58$ for arm 1 and $0.63$ for arm 2, whose posterior is $\mathrm{Beta}(1,1)$.
Hint 4/4
So arm 2 is played and becomes $\mathrm{Beta}(2,1)$.
Show solution
Method 15.7: argmax of the draws, then one count.
Choose
$$A_t=\arg\max(0.58,\ 0.63)=2$$
Arm 1's posterior mean, $4/6$, plays no part.
Update
$$\mathrm{Beta}(1+1,\ 1+0)=\mathrm{Beta}(2,1)$$
A 1 is a success.
Answer $$\boxed{A_t=2,\quad\mathrm{Beta}(2,1)}$$
Check
Mean check: the posterior mean of arm 2 moves from $1/2$ to $2/3$, up after a success, as it must.
Draw, compare, update the winner only: three moves, every round.
⚠ Swapping successes and failures
Both parameters are counts, and the names $\alpha$ and $\beta$ do not say which is which.
A question gives the means and either the list of plays or the expected play counts.
Gaps
$\Delta_a=\mu^*-\mu_a$ for every arm; the best arm's gap is $0$.
Count
Plays per arm from the list, or the given $\mathbb E[N_{a,T}]$; ignore the rewards.
Weight
$\sum_a\Delta_aN_{a,T}$.
Check
$T\mu^*-\sum_t\mu_{A_t}$ must give the same number.
Where it goes wrong
Observed rewards used in place of the means.
Means used in place of the gaps.
A worse arm left out of the sum.
One εt-greedy round by hand
A question gives $K$, the schedule, the sample means and two uniform numbers.
Schedule
$\epsilon_t=\min\{1,\ cK/(\Delta_{\min}^2t)\}$: check the cap.
Leader
$\hat a_t^*=\arg\max_a\hat\mu_{a,t-1}$, the lower index on a tie.
Probabilities
Leader $1-\epsilon_t+\epsilon_t/K$; every other arm $\epsilon_t/K$.
Coin and draw
Explore when $u<\epsilon_t$, then play arm $\lfloor Ku'\rfloor+1$; otherwise play the leader.
Where it goes wrong
The leader's share of the random plays forgotten.
Random plays spread over $K-1$ arms.
A schedule value above 1 used as a probability.
One UCB round by hand
A question gives counts and clicks after round $t-1$ and asks which arm is played.
Read the history
$N_{a,t-1}$ and $\hat\mu_{a,t-1}$ for every arm; $t$ is the round being decided.
Log
$2\log t$ with the natural log, once for all arms.
Bonuses
$\sqrt{2\log t/N_{a,t-1}}$ for each arm.
Indices
$g_{a,t}=\hat\mu_{a,t-1}+$ bonus; play the largest, the lower index on a tie.
Update
Only the played arm's count and mean change; next round every bonus moves with the new $\log t$.
Where it goes wrong
$\log_{10}$ in place of the natural log.
$N_{a,t}$ in place of $N_{a,t-1}$.
Old bonuses reused for the arms that were not played.
One Thompson round for Bernoulli arms
A question gives successes and failures per arm and this round's draws.
Posteriors
$\mathrm{Beta}(1+\alpha_{a,t-1},\ 1+\beta_{a,t-1})$ for every arm.
Draws
Read $\tilde\mu_{a,t}$ from the question.
Choose
Play the largest draw, not the largest posterior mean.
Update
Add the reward to the played arm's $\alpha$ and one minus the reward to its $\beta$.
Where it goes wrong
$\alpha$ and $\beta$ swapped.
Every arm updated, not only the played one.
The arm chosen by its posterior mean.
Regret of the six-round history
Headlines with $\mu=(0.7,\ 0.5,\ 0.2)$ were played $1,2,3,1,1,2$. Compute $\mathrm{Reg}(6)$.
Find$\mathrm{Reg}(6)$.
Given
$\mu=(0.7,\ 0.5,\ 0.2)$
plays $1,2,3,1,1,2$
Solution
Definition 15.1: subtract the played means from $T\mu^*$.
Played means
$$0.7+0.5+0.2+0.7+0.7+0.5=3.3$$
One mean per round.
Regret
$$6(0.7)-3.3=0.9$$
Six rounds at the best mean, minus the played means.
Answer $$\boxed{\mathrm{Reg}(6)=0.9}$$
Check
By gaps: $2(0.2)+1(0.5)=0.9$.
Regret is fixed by the plays alone.
Reward shortfall of the same six rounds
The same six rounds saw the clicks $1,0,0,0,1,1$. Compute $6\mu^*-\sum_tR_{A_t,t}$.
FindThe shortfall of the observed clicks.
Given
$\mu^*=0.7$
clicks $1,0,0,0,1,1$
Solution
Subtract the clicks, not the means, from $T\mu^*$.
Clicks
$$1+0+0+0+1+1=3$$
What the readers actually did.
Shortfall
$$4.2-3=1.2$$
Six rounds at the best mean, minus the clicks.
Answer $$\boxed{\text{shortfall}=1.2}$$
Check
Over many runs the clicks average to the played means, so the average shortfall equals the average regret, $\mathbb E[\text{shortfall}]=\mathbb E[\mathrm{Reg}]$.
The shortfall mixes the policy's choices with the coin flips of the rewards.
Both start from $T\mu^*=4.2$. Regret subtracts the means of the arms played, $3.3$; the shortfall subtracts the clicks seen, $3$, which carry coin-flip noise. Averaged over runs the two agree, but in one run they need not.
How to tell them apart
If the question asks for regret, use $\mu_{A_t}$ and ignore the rewards; the rewards only decide what the policy plays next.
UCB on a history of 6 in 10 and 1 in 2
After 12 rounds, arm 1 has 6 clicks in 10 plays and arm 2 has 1 in 2. Which arm does UCB play in round 13?
Sign check: arm 2's posterior mean, $0.5$, is below arm 1's, $0.583$, so its chance of being best should be under one half, and $0.3846$ is.
Thompson sampling sends the round to arm 2 only as often as arm 2 is likely to be best.
Same data, two adaptive rules. UCB sends round 13 to arm 2 with certainty because its index is highest; Thompson sampling sends it there with probability $5/13$, and with these draws plays arm 1.
How to tell them apart
Asked which arm is played: for UCB compute the indices and there is one answer; for Thompson sampling you need the draws, and without them the answer is a probability.
Scaffolding comes off
The common skeleton
Read the history: $N_{a,t-1}$ and $\hat\mu_{a,t-1}$ for every arm, and the round $t$ being decided.
Compute $2\log t$ with the natural log, once for all arms.
Bonus of each arm: $\sqrt{2\log t/N_{a,t-1}}$.
Index: $g_{a,t}=\hat\mu_{a,t-1}+$ bonus; play the largest, the lower index on a tie.
Update only the played arm's count and mean; next round every bonus moves with the new $\log t$.
1 · fully worked
Three UCB rounds from round 10
After 9 rounds of UCB, arm 1 has 3 clicks in 4 plays, arm 2 has 1 in 3 and arm 3 has 0 in 2. If played, arm 1 would pay 1 and then 0. Find the arms played in rounds 10, 11 and 12.
Find$A_{10}$, $A_{11}$, $A_{12}$.
Given
$N_{\cdot,9}=(4,\ 3,\ 2)$, clicks $(3,\ 1,\ 0)$
arm 1's next rewards: 1, then 0
Solution
The skeleton three times; only the played arm's numbers change between rounds.
Round 12 is close: arm 1 beats arm 3 by only $0.0004$, and both trail arm 2 by more than $0.04$, so the choice of arm 2 is not a rounding effect.
After an arm is played, compare its new index with the runner-up before assuming it stays in front.
2 · you write the reasoning
Easier: two arms and one round, and this time you write the reasons. After 8 rounds, arm 1 has 3 clicks in 5 plays and arm 2 has 2 in 3. For each line, write in the empty column why it is allowed.
Each arm's own play count goes under the square root: fewer plays, bigger bonus.
$$g_{1,9}=1.5375,\qquad g_{2,9}=1.8770$$
reasoning
Each index is the mean plus the bonus of the same arm.
$$A_9=2$$
reasoning
Arm 2 has the larger index; it leads on the mean too, and its smaller count widens the lead.
3 · find the buried error
Harder, with two errors buried in it. After 19 rounds of UCB, arm 1 has 7 clicks in 10 plays, arm 2 has 3 in 6 and arm 3 has 1 in 3. The arm played in round 20 pays 0. A student computes rounds 20 and 21 as below. Which two steps are wrong?
Step 1. Means after round 19: $\hat\mu=(0.7,\ 0.5,\ 0.3333)$ with $N=(10,\ 6,\ 3)$.
Step 2. Nineteen rounds are done, so $2\log19=5.8889$ and $g_{\cdot,20}=(1.4674,\ 1.4907,\ 1.7344)$: arm 3 is played.
Step 3. Arm 3 pays 0, so its count becomes $N_3=4$.
Step 5. Arm 3 has the largest index, so it is played again in round 21.
the two buried errors (2)
⚠ step 2
Round 20 uses $\log20$, not $\log19$: the bonus is built from the round being decided. With $2\log20=5.9915$ the indices are $(1.4740,\ 1.4993,\ 1.7465)$.
After 19 rounds, 19 is the number on the page, and it is easy to take it for $t$.
right
$g_{\cdot,20}=(1.4740,\ 1.4993,\ 1.7465)$: arm 3 is still played, so this slip hides inside a right decision.
⚠ step 4
Arm 3's mean was not updated after its zero: $\hat\mu_{3,20}=1/4=0.25$, not $1/3$.
Step 3 updated the count, and the mean looks as if it belongs to an earlier line.
right
$g_{3,21}=0.25+1.2338=1.4838$, below arm 2's $1.5074$, so round 21 plays arm 2, not arm 3.
4 · the bare problem
§15.5 — three UCB rounds from scratch
After 15 rounds of UCB on three Bernoulli arms, arm 1 has 6 clicks in 8 plays, arm 2 has 2 in 5 and arm 3 has 0 in 2. If played, arm 1 would pay 1 and then 0, arm 2 would pay 1, and arm 3 would pay 0 and then 0.
Find
(a) Find the arms played in rounds 16, 17 and 18.
(b) Give every arm's count and sample mean after round 18.
Given
$N_{\cdot,15}=(8,\ 5,\ 2)$, clicks $(6,\ 2,\ 0)$
next rewards: arm 1: $1,0$; arm 2: $1$; arm 3: $0,0$
$\log16=2.7726$, $\log17=2.8332$, $\log18=2.8904$
Hint 1/4
Three rounds, three index tables, with one update after each.
Hint 2/4
$g_{a,t}=\hat\mu_{a,t-1}+\sqrt{2\log t/N_{a,t-1}}$; play the largest; update the played arm with its next reward.
Hint 3/4
Here the start is means $(0.75,\ 0.4,\ 0)$ with plays $(8,\ 5,\ 2)$; the logs of 16, 17 and 18 are $2.7726$, $2.8332$ and $2.8904$.
Hint 4/4
So round 16 plays arm 3 (it pays 0), rounds 17 and 18 play arm 1 (paying 1, then 0), ending at plays $(10,\ 5,\ 3)$ and means $(0.7,\ 0.4,\ 0)$.
Show solution
Each round is one index table; the reward stream only matters for the arm actually played.
Part (a) by gaps: arm 2 twice at $0.15$ and arm 3 twice at $0.35$ give $0.3+0.7=1.0$. Part (b) by reasoning: arms 2 and 3 have the same count, hence the same bonus, so the better mean, arm 2, beats arm 3, and arm 1's larger count keeps its bonus $0.43$ lower.
A full bandit question is a tally followed by short formulas; the marks are lost on the tally, the log base and the order inside KL.
Practice
A · concept 4 questions
1§15.5 — can the worst mean win
A classmate says UCB is greedy with a correction, so it never plays the arm whose sample mean is the lowest of all.
Find(a) True or false: UCB never plays the arm with the lowest sample mean.
GivenUCB index $g_{a,t}=\hat\mu_{a,t-1}+\sqrt{2\log t/N_{a,t-1}}$
Hint 1/4
Ask whether a bonus can be larger than the difference between two sample means.
Hint 2/4
$g_{a,t}=\hat\mu_{a,t-1}+\sqrt{2\log t/N_{a,t-1}}$; the bonus is large when $N_{a,t-1}$ is small.
Hint 3/4
Here try $t=31$ with means $0.667$, $0.556$ and $0$ after $18$, $9$ and $3$ plays, so the bonuses are $0.618$, $0.874$ and $1.513$.
Hint 4/4
The indices are $1.284$, $1.429$ and $1.513$: the arm with mean $0$ is played, so the statement is false.
Show solution
One counterexample settles a claim about every run; a small play count is where to look.
Arm 3's bonus exceeds arm 1's by $1.5131-0.6177=0.8954$, more than arm 1's lead of $0.6667$ in mean.
UCB's ranking is by what an arm could still be, so a rarely played arm can outrank every better-looking one.
2§15.2 — a small linear rate
A team reports that its recommender loses only one click in every 1,000 rounds, whatever the horizon: $\mathbb E[\mathrm{Reg}(T)]=0.001\,T$.
Find(a) True or false: this policy has sublinear regret.
Given$\mathbb E[\mathrm{Reg}(T)]=0.001\,T$ for every $T$
Hint 1/4
Sublinear is about what regret per round does as $T$ grows, not about how small it is now.
Hint 2/4
Sublinear means $\lim_{T\to\infty}\mathbb E[\mathrm{Reg}(T)]/T=0$.
Hint 3/4
Here $\mathbb E[\mathrm{Reg}(T)]/T=0.001T/T$.
Hint 4/4
That is $0.001$ for every $T$, not $0$, so the statement is false.
Show solution
The definition of a good policy is a limit, so compute the limit.
Divide
$$\frac{0.001\,T}{T}=0.001$$
The $T$ cancels.
Limit
$$\lim_{T\to\infty}0.001=0.001\neq0$$
A constant does not shrink.
Answer $$\boxed{\text{False}}$$
Check
Compare $5\sqrt T$, which is sublinear: $5\sqrt T/T=5/\sqrt T$ is $0.005$ at $T=10^6$ and $0.0005$ at $T=10^8$, falling.
Linear regret means a fixed fraction of rounds is wasted forever, however small the fraction.
3§15.7 — same history, same arm
A classmate argues that Thompson sampling's posteriors are a fixed function of the history, so two runs with identical histories must play the same arm next.
Find(a) True or false: Thompson sampling is a deterministic policy.
Givenposteriors $\mathrm{Beta}(1+\alpha_{a,t-1},1+\beta_{a,t-1})$, then $A_t=\arg\max_a\tilde\mu_{a,t}$
Hint 1/4
Separate what the history fixes from what the algorithm still draws at random.
Hint 2/4
$\tilde\mu_{a,t}\sim\mathrm{Beta}(1+\alpha_{a,t-1},1+\beta_{a,t-1})$, and $\Pr(A_t=a\mid\mathcal H_t)=\Pr(a^*=a\mid\mathcal H_t)$.
Hint 3/4
Here take two arms at $\mathrm{Beta}(2,1)$ and $\mathrm{Beta}(1,2)$: the same history gives arm 1 with probability $\frac56$ and arm 2 with probability $\frac16$.
Hint 4/4
Both arms have positive probability, so the statement is false: the policy is randomized.
Show solution
A deterministic policy puts probability 1 on one arm, so showing two positive probabilities is enough.
UCB on the same history is deterministic: one index table, one arm. The lecture lists UCB as deterministic and Thompson sampling as randomized.
Thompson sampling randomizes through its draws, UCB does not randomize at all; both adapt to the data.
4§15.3 — which instance is hardest
Three 2-armed Bernoulli instances have a gap of $0.1$: means $(0.5,\ 0.4)$, $(0.9,\ 0.8)$ and $(0.2,\ 0.1)$. A fourth, $(0.9,\ 0.5)$, has a gap of $0.4$.
Find(a) Which instance has the largest Lai and Robbins constant $\Delta/\mathrm{KL}(a,a^*)$?
Variance check: a Bernoulli near $0.5$ has variance $0.25$, near $0.9$ or $0.1$ only $0.09$; noisier rewards need more plays, as the ranking of the first three says.
Equal gaps are not equal difficulty; noise near $0.5$ makes arms hardest to separate.
B · computation 7 questions
1§15.1 — regret against reward shortfall
Four arms have means $\mu=(0.3,\ 0.6,\ 0.45,\ 0.1)$. In 10 rounds a policy plays $1, \allowbreak 2, \allowbreak 3, \allowbreak 4, \allowbreak 2, \allowbreak 2, \allowbreak 3, \allowbreak 2, \allowbreak 2, \allowbreak 2$ and sees the rewards $0, \allowbreak 1, \allowbreak 1, \allowbreak 0, \allowbreak 1, \allowbreak 0, \allowbreak 0, \allowbreak 1, \allowbreak 1, \allowbreak 1$.
Find
(a) Compute $\mathrm{Reg}(10)$.
(b) Compute the shortfall $10\mu^*-\sum_tR_{A_t,t}$ of the observed rewards.
Regret needs the means of the arms played; the shortfall needs the rewards seen. Keep the two lists apart.
Hint 2/4
$\mathrm{Reg}(T)=T\mu^*-\sum_t\mu_{A_t}$ and $\mathrm{Reg}(T)=\sum_a\Delta_aN_{a,T}$.
Hint 3/4
Here $\mu^*=0.6$, the played means add to $4.9$, and the rewards add to $6$; arms 1, 3, 4 were played $1$, $2$, $1$ times with gaps $0.3$, $0.15$, $0.5$.
Hint 4/4
So $\mathrm{Reg}(10)=6.0-4.9=1.1$, the shortfall is $6.0-6=0$, and $0.3+0.3+0.5=1.1$.
Show solution
Two lists, two formulas; the decomposition then checks the first without the second.
Plays add up: arm 2 six times, arm 3 twice, arms 1 and 4 once each, 10 in all.
The shortfall averages to the regret over many runs, but in one run luck can hide all of it.
2§15.4 — a greedy run table
Two Bernoulli arms have $\mu_1=0.8$ and $\mu_2=0.6$. Greedy plays arm 1, then arm 2, then the higher sample mean, arm 1 on a tie. Arm 1's rewards, in the order it is played, would be $0,1,1,\dots$; arm 2's would be $1,1,0,1,1$.
Find
(a) List $A_t$ and both sample means for rounds 1 to 6.
(b) Compute $\mathrm{Reg}(6)$ and explain why arm 1 is never played again.
(c) Under $\epsilon_t$-greedy with $\epsilon_7=0.2$, what is $\Pr(A_7=1)$ after the same six rounds?
Given
$\mu=(0.8,\ 0.6)$
arm 1's reward stream $0,1,1,\dots$; arm 2's $1,1,0,1,1$
ties go to arm 1
Hint 1/4
Fill the table round by round; a sample mean changes only when its arm is played.
Hint 2/4
Greedy: $A_t=\arg\max_a\hat\mu_{a,t-1}$. For (c): a non-leader has probability $\epsilon_t/K$.
Hint 3/4
Here arm 1 gets $0$ in round 1 and arm 2 gets $1,1,0,1,1$ over rounds 2 to 6, while arm 1's mean stays at $0$.
Hint 4/4
So $A=1,2,2,2,2,2$, $\mathrm{Reg}(6)=5(0.2)=1.0$, and $\Pr(A_7=1)=0.2/2=0.1$.
Show solution
A table forces one decision per round, which is where greedy's mistake becomes visible.
By the definition: $6(0.8)-(0.8+5\times0.6)=4.8-3.8=1.0$.
Greedy's lock needs only one unlucky zero; any fixed chance of a random play breaks it.
3§15.4 — a tuned schedule with four arms
An $\epsilon_t$-greedy learner has $K=4$ arms, $\Delta_{\min}=0.1$ and $c=1$, and uses $\epsilon_t=\min\{1,\ cK/(\Delta_{\min}^2t)\}$ from round 5 on.
Find
(a) Compute $\epsilon_{100}$, $\epsilon_{1000}$ and $\epsilon_{10{,}000}$.
(b) In round 1000 arm 2 leads. Give each arm's probability.
(c) Find the expected number of random plays in rounds 5 to 10,000, and how many reach each arm.
Given
$K=4$, $\Delta_{\min}=0.1$, $c=1$
$\sum_{t=401}^{10{,}000}\frac1t=3.2177$
Hint 1/4
Write the schedule as a number over $t$ first, then look for the rounds where the cap binds.
Hint 2/4
$\epsilon_t=\min\{1,\ cK/(\Delta_{\min}^2t)\}$; the leader gets $1-\epsilon_t+\epsilon_t/K$, the others $\epsilon_t/K$; the expected count is $\sum_t\epsilon_t$.
Hint 3/4
Here $cK/\Delta_{\min}^2=4/0.01=400$, so $\epsilon_t=1$ up to $t=400$ and $400/t$ after, with $\sum_{401}^{10{,}000}1/t=3.2177$.
Hint 4/4
So $\epsilon=(1,\ 0.4,\ 0.04)$; in round 1000 arm 2 has $0.7$ and the others $0.1$ each; the count is $396+400(3.2177)=1683.1$, about $420.8$ per arm.
Show solution
The constant $cK/\Delta_{\min}^2$ first; everything else is that number over $t$.
Symmetry check on arm 3: $\mathrm{KL}(0.5,0.9)=0.5\log\frac{0.25}{0.09}=0.5(1.0217)=0.5108$, one term instead of two.
The close arm needs over 11 times the plays of the far one.
7§15.7 — four Thompson rounds
Thompson sampling runs on two Bernoulli arms with $\mathrm{Beta}(1,1)$ priors. The draws $(\tilde\mu_1,\tilde\mu_2)$ in rounds 1 to 4 are $(0.42,\ 0.77)$, $(0.63,\ 0.55)$, $(0.21,\ 0.48)$ and $(0.71,\ 0.66)$; the rewards of the played arms are $1,0,0,1$.
Find
(a) List the arm played in each round and the posteriors after round 4.
(b) With what probability does Thompson sampling play arm 1 in round 5?
Given
priors $\mathrm{Beta}(1,1)$
draws $(0.42,0.77)$, $(0.63,0.55)$, $(0.21,0.48)$, $(0.71,0.66)$
rewards of the played arms $1,0,0,1$
Hint 1/4
Keep a two-line ledger, one line per arm, and change only the played arm's line each round.
Hint 2/4
$A_t=\arg\max_a\tilde\mu_{a,t}$; a 1 adds to the first Beta parameter, a 0 to the second.
Hint 3/4
Here the draws pick arms $2,1,2,1$, and the rewards $1,0,0,1$ go to those arms in that order.
Hint 4/4
Both arms end at $\mathrm{Beta}(2,2)$, so by symmetry arm 1 is played in round 5 with probability $\frac12$.
Show solution
The draws are given, so each round is a comparison and one update.
Counts check: 4 rounds gave 4 updates, 2 per arm, and each arm's parameters add to $2+2=4$, which is $2$ plus its plays.
Identical posteriors give identical chances; Thompson sampling breaks the tie with its draws, not with a rule.
C · exam level 4 questions
1§15.5 — when UCB leaves an arm
After 100 rounds of UCB, arm 1 has 49 clicks in 70 plays, arm 2 has 15 in 25 and arm 3 has 1 in 5. UCB plays arm 3 in round 101, and arm 3 pays 0 every time it is played from then on.
Find(a) In which round does UCB first play an arm other than arm 3?
Arm 1's index is $1.0631$ to $1.0643$ throughout, never in the race; arm 2's rises by only $0.002$ in three rounds.
A played arm's bonus shrinks like $1/\sqrt N$, the others' grow like $\sqrt{\log t}$, so the lead passes on within a few rounds.
2§15.4 — which policy keeps losing
Four policies run on three Bernoulli arms with $\mu=(0.7,\ 0.5,\ 0.2)$: $\epsilon$-greedy with $\epsilon=0.05$ in every round, $\epsilon_t$-greedy with $\epsilon_t=\min\{1,18.75/t\}$, UCB with the lecture's index, and Thompson sampling with $\mathrm{Beta}(1,1)$ priors.
Find(a) Which policy has expected regret that grows linearly in $T$?
Ask of each policy whether its exploration ever stops being a fixed fraction of the rounds.
Hint 2/4
With a fixed $\epsilon$, every arm gets at least a share $\epsilon/K$ of the rounds, so by Theorem 15.2 the regret per round is at least $\epsilon\frac1K\sum_a\Delta_a$.
Hint 3/4
Here $\frac1K\sum_a\Delta_a=0.7/3=0.2333$; the schedule $\min\{1,18.75/t\}$, UCB and Thompson sampling all have $O(\log T)$ regret.
Hint 4/4
So the constant $\epsilon=0.05$ is the linear one, with at least $0.0117$ regret per round.
Show solution
Decaying schedules, UCB and Thompson sampling have logarithmic bounds from this section, so only the constant needs a computation.
Random plays
$$\Pr(\text{random play})=0.05\ \text{in every round}$$
Numbers from the checkpoint: $\Delta_a=0.2$, $T=10^5$ gives $m=2303$ and bonus $0.0999\le0.1$.
In the proof, $m$ sets the width, the $\log t$ sets the failure rate, and the sum of $2t^{-2}$ sets the constant.
D · interleaved 4 questions
1§15.1 — a one-state value update
An agent faces a single state, so every round offers the same actions. It keeps an estimate $Q(a)$ per action, starting at $0$, and after playing $a$ with reward $r$ updates $Q(a)\leftarrow(1-\alpha)Q(a)+\alpha\hat Q$ with $\hat Q=r+\gamma\max_{a'}Q(a')$ and $\gamma=0$. Action 2 is played three times and earns $1,0,1$.
Find
(a) Compute $Q(2)$ after each reward when $\alpha=1/n$ on the $n$-th play of action 2.
(b) Repeat with a constant $\alpha=0.5$.
(c) Which of the two equals the sample mean, and why?
Given
$Q(2)=0$ at the start; rewards $1,0,1$
$\hat Q=r$ because $\gamma=0$
Hint 1/4
Recognise the update as a weighted average of the old estimate and the new reward.
Hint 2/4
$Q\leftarrow(1-\alpha)Q+\alpha r$; with $\alpha=1/n$ this is the running-mean update $Q+(r-Q)/n$.
Hint 3/4
Here the rewards are $1,0,1$ and $Q$ starts at $0$.
Hint 4/4
So $\alpha=1/n$ gives $1,\ 0.5,\ 0.6667$; $\alpha=0.5$ gives $0.5,\ 0.25,\ 0.625$; only the first is the sample mean.
Show solution
With one state and $\gamma=0$ the target is the reward itself, so only the weighting differs.
Weights check for $\alpha=0.5$: the three rewards get weights $0.125,\ 0.25,\ 0.5$, and $0.125(1)+0.25(0)+0.5(1)=0.625$.
A bandit is the one-state case of the previous section: with $\alpha=1/n$ its value update is the sample mean every bandit policy here uses.
2§15.4 — two ways to spread the random plays
An agent has value estimates $Q=(1.0,\ 0.5,\ 0.0)$ for three actions. Compare two exploration rules: $\epsilon$-greedy with $\epsilon=0.3$, and Boltzmann exploration, $\Pr(a)=e^{Q(a)}/\sum_{a'}e^{Q(a')}$.
Find
(a) Give the three action probabilities under each rule.
(b) Which rule gives the middle action more than the worst one, and why does that matter?
Given
$Q=(1.0,\ 0.5,\ 0.0)$
$\epsilon=0.3$
$e^{1}=2.7183$, $e^{0.5}=1.6487$
Hint 1/4
One rule treats every non-leader alike; the other lets each estimate set its own weight.
Each set adds to 1: $0.8+0.1+0.1$ and $0.5065+0.3072+0.1863=1.0000$.
'Uniform exploration' is the weakness the lecture lists for $\epsilon$-greedy; weighting by estimates, as UCB and Thompson sampling also do in their own ways, avoids it.
3§15.5 — how many plays for a width of 0.1
A click rate is estimated from $n$ independent 0/1 outcomes. Two requirements are compared: a fixed test, where the average must be within $0.1$ of the truth with probability at least $0.95$, and a UCB bonus that must fall to $0.1$ by round $T=10{,}000$.
Find
(a) Find the smallest $n$ for the fixed test.
(b) Find the smallest $N$ with $\sqrt{2\log10{,}000/N}\le0.1$.
The constant is computed for a concrete instance, so plugging in a concrete $T$ feels natural. Our Thompson sampling runs had regret $17.5$ at $T=10{,}000$, below $29.75$, and that is no contradiction.
wrong$$\mathbb E[\mathrm{Reg}(10^4)]\ge29.75\ \text{for every consistent policy}$$
uniform priors; update only the played arm; regret constant $\Delta_a/\mathrm{KL}(a,a^*)$ as in the floor
Check yourself
Close the page and write down from memory:
what a bandit learner sees each round, and the definition of regret;
the decomposition of expected regret by arms;
the Lai and Robbins floor and the Bernoulli KL;
the leader's probability under $\epsilon_t$-greedy, and why a constant $\epsilon$ is linear;
the UCB index and where its bonus comes from;
the five moves of the UCB regret proof;
one Thompson round, and the chance that it plays a given arm.
Then reopen the page and compare; whatever is missing is your reread list.
Compute $\mathrm{Reg}(T)$ from a list of plays and say why the observed rewards do not enter?
c-bandit
Turn expected play counts into expected regret, and tell a linear rate from a sublinear one?
c-regret
Compute a Bernoulli KL in the right order and the Lai and Robbins constant of an instance?
c-lower-bound
Give every arm's probability under $\epsilon_t$-greedy, with the cap, and explain why a constant $\epsilon$ is linear?
c-eps-greedy
Run UCB for several rounds from a table of counts and clicks, with the natural log and $N_{a,t-1}$?
c-ucb
Write the five moves of the UCB proof and evaluate the bound for given gaps and $T$?
c-ucb-regret
Run a Thompson round from given draws, and compute the chance of an arm for small Beta posteriors?
c-thompson
Glossary (14 terms)
multi-armed banditçok kollu haydut
A sequential decision problem in which a learner plays one of $K$ arms per round and sees only the reward of the arm it played.
armkol
One option of a bandit; arm $a$ pays rewards drawn from its own unknown distribution $F_a$.
bandit feedback
Feedback that reveals only the reward of the chosen option, not what the other options would have paid.
online learningçevrimiçi öğrenme
Learning from data that arrive one round at a time, where each action is taken before the next observation and performance is judged over the whole sequence.
regretpişmanlık
$\mathrm{Reg}_\pi(T)=T\mu^*-\sum_t\mu_{A_t}$: the expected reward a policy loses against always playing the best arm.
$\Delta_a=\mu^*-\mu_a$, what one play of arm $a$ costs in expected reward.
consistent policy
A policy whose expected regret, on every instance of the class, grows slower than every power $T^p$ with $p>0$.
For Bernoulli distributions $\mathrm{KL}(p,q)=p\log\frac pq+(1-p)\log\frac{1-p}{1-q}$; zero only when $p=q$, and not symmetric.
empirical best arm
$\hat a_t^*=\arg\max_a\hat\mu_{a,t-1}$, the arm with the highest sample mean so far.
exploration probabilitykeşif olasılığı
$\epsilon_t$, the chance that $\epsilon_t$-greedy plays a uniformly random arm in round $t$.
upper confidence boundüst güven sınırı
A number that lies above an unknown mean with high probability; the UCB index is one.
exploration bonus
The term $\sqrt{2\log t/N_{a,t-1}}$ that UCB adds to a sample mean; large for arms with few plays.
optimism under uncertainty
Acting as if each option were as good as the data still allow; the principle behind UCB.
Thompson samplingThompson örneklemesi
A Bayesian policy that draws one value per arm from its posterior and plays the arm with the highest draw.
What comes next
This is the last section of the course, so what comes next is the final. The habit to take there from this chapter: name what a question is about, a mean, a count, a probability or a bound, before you choose a formula.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, and the book does not treat bandits, so no section numbers are cited here.
course materialEEE 485 lecture slides, chapter 15: Multi-armed bandit problems Scope, order and notation (the arm set, F, R, A, the history, the policy, the means and the best arm, regret, the gaps, N, the sample means, the exploration schedule, the UCB index, the threshold m, the Beta counts alpha and beta, the draws, KL) follow these slides; the explanations, examples, numbers, figures and exercises here are original.
course materialEEE 485 lecture slides, chapter 14: Reinforcement learning The epsilon-greedy rule, Boltzmann exploration and the Q-learning update recalled in two interleaved questions.
course materialEEE 485 lecture slides, chapter 1: course information The undergraduate grading split quoted in the exam note.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights and the weekly topic list.
standard resultT. L. Lai and H. Robbins, Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics 6 (1985) Cited in the lecture for the lower bound.
standard resultP. Auer, N. Cesa-Bianchi and P. Fischer, Finite-time analysis of the multiarmed bandit problem, Machine Learning 47 (2002) Cited in the lecture for the epsilon-greedy and UCB bounds.
standard resultE. Kaufmann, N. Korda and R. Munos, Thompson sampling: an asymptotically optimal finite-time analysis (2012) Cited in the lecture for the Thompson sampling bound.
standard resultW. R. Thompson, On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika 25 (1933) Named in the lecture as the origin of posterior sampling.
standard resultHoeffding's inequality, the union bound, the Beta-Bernoulli update and the Bernoulli KL divergence Standard results used in the derivations. Every simulation (1,000 runs per policy with fixed seeds, 20,000 shops for the coupon rule) and every figure was computed for this page.