Reinforcement Learning · One focused lesson
Start with one repeated choice. Learn why exploration matters, then try Bayesian evidence and Thompson sampling.
Reading tips and color key
Start with the explanation and experiment. Open the symbol cards when you want the details. Teal: probabilities; blue: states; orange: actions; green: rewards; purple: values; gray: parameters and settings; crimson: losses and errors. Written labels give every symbol its role.
01 · Start with one decision
Bandits: which mystery button should we press?
Why use it? You must earn rewards while discovering which choice is best.
How does it work? Estimate each arm’s reward, then balance trying uncertain arms with choosing promising ones.
What does it give you? A rule for repeated choices and an estimate for each arm. A bandit is the problem; UCB and Thompson sampling are ways to solve it.
When does it struggle? A basic bandit ignores how an action changes future states. Use an MDP when routes, delayed consequences, or changing situations matter.
Three buttons sometimes give a star. One might be generous; another might only have been lucky. Do you press your current favorite, or try a less familiar button? Exploitation uses what you know. Exploration looks for information that could help later.
A multi-armed bandit repeats this choice without a changing physical state. Begin by keeping each button’s average reward. You do not need to store every past reward: move the old average toward the newest observation.
Equation anatomy · one button, after its nth observation · show / hide
| Symbol | Meaning and kind | Form | Random? | Possible values | In code |
|---|---|---|---|---|---|
| \({\color{#172337}{\color{#7542b0}{q}}_{\color{#525968}{n}},{\color{#7542b0}{q}}_{{\color{#525968}{n}}-1}}\) | New and old reward estimates | Two scalar table entries | Fixed given data; vary across datasets | 0–1 for star rewards | mean[button] |
| \({\color{#172337}{\color{#087444}{r}}_{\color{#525968}{i}},{\color{#087444}{r}}_{\color{#525968}{n}}}\) | Observed rewards | Scalars | Realizations of random rewards | 0 or 1 here; real numbers generally | reward = 1 |
| \({\color{#172337}{\color{#525968}{n}},{\color{#525968}{i}},1/{\color{#525968}{n}}}\) | Visit count, summation index, averaging step | Integer counts; scalar step | Fixed in this calculation | \({\color{#172337}{\color{#525968}{n}}\ge1;\ 1\le {\color{#525968}{i}}\le {\color{#525968}{n}};\ 0\lt 1/{\color{#525968}{n}}\le1}\) | count[button] += 1 |
| \({\color{#172337}{\sum,=}}\) | Add terms; equality of quantities | Operators | No | Sum has reward units | mean += (reward-mean)/count |
Try the numbers. The first three rewards are 1, 0, 1, so the mean is 2/3. A fourth reward of 1 gives 2/3 + (1/4)(1 − 2/3) = 3/4. Here n counts observations of this button, not all button presses. At the first observation the step is 1, so any initial estimate is replaced by that observation.
Greedy
Choose the highest current average. Simple, but early luck can hide a better button.
Epsilon-greedy
Usually choose a best estimate. With probability ε, try a uniformly random button. That random choice can include the current favorite.
Upper confidence bound
Add an uncertainty bonus to the estimated reward. A less-tested button gets a reason to be tried.
Thompson sampling
Draw one plausible success chance from each button’s current belief distribution. Choose the button with the largest draw. Build that belief next.
Choose an exploration rule: why, how, and tradeoffs
Greedy. Why: exploit reliable estimates. How: choose an arm maximizing Q(a). What: no deliberate exploration. Limitation: a lucky early estimate can lock it onto an inferior arm.
Epsilon-greedy. Why: keep a simple exploration baseline. How: with K arms and one greedy winner, its probability is 1−ε+ε/K; each other arm gets ε/K. With K=3 and ε=0.1, that is about 0.933 versus 0.033 each. What: every arm keeps a chance. Limitation: random trials spend effort even on clearly poor arms; fixed ε keeps that cost forever.
UCB. Why: spend trials on uncertain, promising arms. How: after trying every arm, score an arm with the formula below. What: an explicit uncertainty bonus. Limitation: this stationary bounded-reward form needs adaptation when rewards drift.
Symbols: t is total past choices (t ≥ 2); Nₜ(a)>0 counts past choices of arm a; Qₜ(a) is its observed reward mean; c>0 scales exploration; argmax returns an arm. An untried arm is selected before using this fraction. At t=100 and c=1, an arm with N=4 gets a bonus about 1.073; N=25 gives 0.429. The score can exceed the reward range.
Thompson sampling. Why: use uncertainty through plausible reward models. How: draw θₐ ∼ Beta(a₀+sₐ,b₀+fₐ), choose the largest draw, then update only that arm. Here s/f count its successes/failures. What: uncertain arms can still win. Limitation: its exploration depends on the prior and reward model; fixed-chance Beta counts adapt poorly to abrupt change.
Compare fairly. In a stationary star-reward bandit, cumulative pseudo-regret is the sum of μ*−μ(Aₜ), where μ* is the best true mean and μ(Aₜ) is the selected arm’s true mean. Its expectation over the learner’s random experience is expected cumulative regret. Each term compares mean rewards, not a lucky realized reward. A low final estimation error alone does not show that a method earned many rewards along the way.
The interactive below implements Thompson sampling; the other rules here are explained comparisons. See Auer, Cesa-Bianchi and Fischer’s UCB analysis and the Thompson sampling tutorial.
The sample average estimates reward. Greedy, epsilon-greedy, UCB, and Thompson sampling select actions. Estimation and action selection answer different questions.
Need the derivation of prior × likelihood? Read Chance, Averages, and Beliefs, then try both activities below.
Beliefs, evidence & exploration
A mystery reward button
Imagine a button that sometimes gives you a star. You do not know its reward chance, θ (“theta”). Start with a guess, collect evidence, and watch your belief change.
Equation colors: probabilities and distributions, fixed prior parameters, rewards. The three chart colors below identify stages of a belief update.
These buttons record observations you choose; they do not simulate a hidden chance. Changing the prior keeps the same evidence so you can compare starting beliefs.
“∝” means “has the same shape as.” Divide by a normalizing constant to make the posterior a probability distribution.
1. Prior
What seemed plausible before these observations.
Probability density · dashed line
2. Likelihood
How well each possible chance explains the evidence.
Relative likelihood · peak = 1 · dotted line
3. Posterior
Your updated belief after seeing the evidence.
Probability density · solid line
The prior and posterior use the same vertical scale. Their total area is 1; their heights can exceed 1. The likelihood chart uses its own scale: it is not a probability density.
Open the math — one symbol at a time
θ is a possible reward chance between 0 and 1. Each observation is assumed independent, with the same fixed chance.
Prior: Beta(a₀, b₀)
Likelihood: L(θ) = θc(1 − θ)f
Posterior: Beta(a₀ + c, b₀ + f)
c counts rewards; f counts no rewards. The positive numbers a₀ and b₀ set the prior’s shape. They are prior parameters, not observations you actually collected.
Posterior mean = (a₀ + c) / (a₀ + b₀ + c + f)
Beta(1, 1) → Beta(1, 1); mean = 1 / 2 = 50.0%.
The likelihood is for the observed reward/no-reward sequence. The displayed curve divides L(θ) by its maximum. With no evidence, L(θ) = 1 everywhere: no possible chance has gained an advantage.
- θ · one unknown number
- A scalar probability in [0, 1]. Its true value is fixed but unknown. A distribution over θ represents our uncertainty; the horizontal axis tries possible values.
- a₀, b₀ · prior settings
- Two positive scalar parameters, fixed by your prior selection. Implementation: the selected pair is [1, 1], [4, 1], or [1, 4].
- c, f · observed counts
- Two nonnegative integers, not random after observation. Each recorded outcome increments exactly one count. The sequence has length c + f.
- L(θ) · evidence score
- A function of one candidate θ. Before rescaling it is the probability of the observed sequence, in [0, 1]. Implementation: evaluate it across the horizontal axis and divide by its peak.
- Beta(a₀ + c, b₀ + f) · updated distribution
- A distribution over one scalar θ, not a single estimate. Its density is nonnegative with area 1. Implementation: add the two observed counts to the two prior parameters, then draw the density.
- Posterior mean · one estimate
- A deterministic scalar in [0, 1] once the evidence is known. Implementation: divide a₀ + c by a₀ + b₀ + c + f. It is the predictive reward chance for the next observation under this model.
No observations yet. The posterior equals the prior.
From beliefs to choices
Which of three buttons should you try?
Each button has a fixed, hidden reward chance. Thompson sampling draws one possible chance from each button’s current belief, chooses the largest draw, then learns from the result.
Reset applies the seed. The same seed and choices reproduce the same experiment. Each button starts at Beta(1, 1), independent of the prior selected above.
Make a choice to see the three sampled candidates and the result.
A sampled candidate is a random draw from a belief, not its mean. Uncertain buttons can still draw high candidates, which encourages exploration. One lucky reward does not prove a button is best.
Show the decision history
The latest 100 choices, newest first. Candidate draws are made before observing the reward. The chosen button's prior-to-posterior update is recorded. The budget always stops additional choices; it is not a proof that the best button has been identified.
| Choice | Candidate A / B / C | Selected | Reward | Chosen belief before → after |
|---|
How this connects to reinforcement learning
This is a multi-armed bandit: choose an action, get an immediate reward, repeat. It has no changing map or delayed consequences. It isolates the exploration question that also appears in full reinforcement learning.
For button i: sample θᵢ from Beta(1 + cᵢ, 1 + fᵢ), choose the button with the largest θᵢ, and observe reward r ∈ {0, 1}. Increase cᵢ by r and fᵢ by 1 − r for the chosen button only.
The mean shown on each card is updated after the observation. The last sampled candidates came from the beliefs before that observation. Estimates can move down as well as up, and short experiments may favor the wrong button.
- θ₁, θ₂, θ₃ · sampled candidates
- Three random scalar draws in [0, 1], one per button: together a length-3 vector. Implementation: sample two Gamma variables for each Beta draw and divide the first by their sum.
- Chosen button · one action
- A scalar index in {A, B, C}: the candidate’s argmax (the position of the largest value). Deterministic once the random candidates are known. Implementation: compare all three draws.
- r · one reward
- A random Bernoulli scalar in {0, 1}, then an observed number. Implementation: compare a uniform random draw with the chosen button’s fixed true chance.
- cᵢ, fᵢ · memory for each button
- Each is a nonnegative observed integer; the three buttons’ counts form two length-3 vectors. Implementation: increment one chosen button’s reward count or no-reward count.
Ready. All three buttons start equally uncertain.
Be First to Comment