Part XVI — Reinforcement Learning: Bandits, MDPs, Policy Gradients & PPO · Chapter 1

Multi-armed bandits (Epsilon-greedy & UCB)

Hook

Every model in this course so far learned from a fixed dataset that already existed before training started. What if the only way to get more data was to act — and every action costs you the chance to have tried something else instead?

Intuition

Three arms, three unknown reward rates. Pull one — its estimate updates. Pull it again, and it either supports or undermines what you just learned. There's no dataset to hand you upfront here; the only way to find out anything is to spend a pull finding out.

Formalize

Each arm's estimated value is just the running average of what it's paid out so far:

Q^(a)=1na∑i=1nari,greedy choice=arg⁡max⁡a  Q^(a)\hat{Q}(a) = \frac{1}{n_a}\sum_{i=1}^{n_a} r_i, \qquad \text{greedy choice} = \underset{a}{\arg\max}\; \hat{Q}(a)
  • Q^(a)\hat{Q}(a) — the running-average estimate of arm aa's value, updated after every pull.
  • aa — one of the arms (actions) available to pull.
  • nan_a — the number of times arm aa has been pulled so far.
  • rir_i — the reward received on the ii-th pull of that arm.
  1. Pure greedy can get stuck

    Always pulling whichever arm currently looks best can lock in a wrong estimate: an early lucky (or unlucky) run of pulls can convince the policy an inferior arm is best, before enough evidence comes in to correct it.

  2. Epsilon-greedy: mostly exploit, sometimes explore

    Epsilon-greedy fixes this with the simplest possible patch: most of the time pull the current best arm (exploit), but some fraction of the time pull a different one anyway, just to keep checking (explore).

Play

Step through a fixed 8-pull run. The first three pulls explore all three arms once each — arm A and arm B both come back showing 1.01.0, a tie. From here, a purely greedy policy could pull only A forever and never find out B is actually the better arm.

Worked example

Arms A, B, C have fixed (but hidden from the policy) true means 0.50.5, 0.80.8, 0.20.2. The script explores A, B, C once each, then exploits:

  1. After the first three explore steps
    • A: [1]→1.0[1]\to1.0
    • B: [1]→1.0[1]\to1.0
    • C: [0]→0.0[0]\to0.0

    A and B are tied for best, purely by chance on a single pull each.

  2. Exploiting the tie

    Ties break alphabetically, so the policy exploits A next: A=[1,0]→0.5=[1,0]\to0.5. Now B is the clear leader and gets exploited: B=[1,1]→1.0=[1,1]\to1.0.

  3. One more explore step saves it

    A scheduled explore step revisits A a third time: A=[1,0,1]→0.667=[1,0,1]\to0.667. Two more exploit steps follow, landing on B=[1,1,0]→0.667=[1,1,0]\to0.667 — tied with A again, by coincidence, after just 8 pulls total.

Even this short run shows the whole tension: without that one extra explore step, the policy might have kept exploiting A on a stale, lucky-looking estimate.

Checkpoint

Pull arms until one arm's estimate exceeds 0.7, backed by at least 3 pulls of it.

Pull an arm to try it
Summary
Q^(a)=1na∑i=1nari\hat{Q}(a) = \frac{1}{n_a}\sum_{i=1}^{n_a} r_i

A bandit is reinforcement learning with everything stripped away except the one tension that defines the whole field: acting changes what you know, and what you know should change how you act. There's no state to track yet — every pull starts from the same "state" the last one did. The next chapter adds exactly that: a world where the action you take also decides what situation you're in next.