ML10.1 · LESSON 1 OF 6

Bandits and exploration

Distinguish sequential decision-making, temporal prediction, recommendation and causal estimation.

THE IDEA

One choice, repeated, with unknown odds

Imagine four slot machines. Each pays out with some fixed probability you cannot see. You get a limited number of pulls and want as many payouts as possible. This is a multi-armed bandit: each pull is an action, the payout is a reward, and nothing about the world changes between pulls. There is no state to track, which is exactly what separates a bandit from the problems in the next lessons.

The difficulty is a tension. To earn reward you should pull the arm that looks best (exploit). To know which arm is best you must sometimes pull arms that look worse (explore), because early estimates come from very few pulls and can be badly wrong.

Arm A

0 / 0 paid

estimate ?

Arm B

0 / 0 paid

estimate ?

Arm C

0 / 0 paid

estimate ?

Arm D

0 / 0 paid

estimate ?

pulls: 0 · wins: 0 · current leader by estimate: none yet

last pull: none

expected regret so far: hidden until you reveal the odds

Pull the arms yourself. Estimates are the share of pulls that paid. Reveal the true odds only after you have decided which arm you believe in.

Predict first. Arm A paid on its only pull (estimate 1.0). Arm C did not pay on its only pull (estimate 0.0), but unknown to you it truly pays 70% of the time. You always pull the arm with the highest estimate. What happens to Arm C?

Three ways to keep exploring

Epsilon-greedy. With probability epsilon pull a random arm, otherwise pull the best-looking one. Simple, but it keeps wasting pulls on arms it already knows are bad, and a good epsilon depends on the problem.
UCB (upper confidence bound). Pull the arm with the best estimate plus an optimism bonus that is large for rarely pulled arms and shrinks as an arm is tried. Uncertain arms get the benefit of the doubt, then lose it as evidence accumulates.
Thompson sampling. Keep a belief about each arm's payout (a Beta distribution, as in the probabilistic ML chapter), draw one plausible payout from each belief, and pull the arm with the highest draw. Uncertain arms win some of the time, in proportion to how likely they are to be best.

The quantity that scores all of them is regret: the reward you would have expected from always pulling the best arm, minus what your choices were expected to earn. Lower regret means less exploration wasted.

GreedyEpsilon-greedyUCBThompson

epsilon10%

policy	regret after 300	pulls A/B/C/D
Greedy	0.9	1 / 1 / 297 / 1
Epsilon-greedy	7.3	5 / 13 / 273 / 9
UCB	33.4	19 / 37 / 166 / 78
Thompson	25.5	6 / 29 / 187 / 78

Arm C (index 2) is the best with probability 0.70. Same seed means the same casino luck for every policy. Seeds are fixed, so the picture is reproducible.

The same casino, four policies, many seeds. One run proves nothing: luck decides single runs, so these curves average over seeds.

The common mistake

Chapter context

These topics change the structure of the learning problem. Their first lesson is to identify what a prediction or action is allowed to depend on and how feedback is produced. Each section is a bridge to a larger specialist subject.

TRY IT YOURSELF

Part 1. Do it hands-on

Choose a policy and its settings. Each result is the average over 30 seeded runs of 500 pulls. Four goals follow in order of difficulty.

30 seeded runs of 500 pulls, arms 0.25, 0.45, 0.7, 0.5

mean regret: 47 (greedy: 40.4)

runs that mostly pull a wrong arm: 0 of 30

greedyUCB

To do: Show that pure greedy gets stuck: choose Greedy and see at least 1 in 5 of the 30 runs commit mostly to a wrong arm
To do: Find an epsilon-greedy setting whose mean regret is less than 80% of greedy's
To do: Find an epsilon so large that epsilon-greedy is worse than greedy
To do: Choose Thompson sampling and get mean regret below that of the best epsilon-greedy setting

Part 2. Do it in code

Write greedy_arm(estimates): the index of the largest estimate, ties going to the lowest index. An empty list raises ValueError.
Write epsilon_greedy(probs, steps, epsilon, seed) that returns {"counts": [...], "estimates": [...], "reward": total}. Use rng = random.Random(seed). Each step: if some arm has never been pulled, pull the lowest such arm (no random number is used for that choice). Otherwise draw rng.random(): if it is below epsilon pick rng.randrange(n), else greedy_arm(estimates). Then draw the reward with rng.random() < probs[arm] (1 or 0). Estimates are running averages of the rewards of each arm (0.0 for an unpulled arm).
Write expected_regret(probs, counts): the sum over arms of counts[i] * (best probability - probs[i]).

import random

def greedy_arm(estimates):
    pass

def epsilon_greedy(probs, steps, epsilon, seed):
    pass

def expected_regret(probs, counts):
    pass

print(epsilon_greedy([0.2, 0.8], 10, 0.1, 0))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is always choosing the current best empirical arm guaranteed to discover the best arm?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

G_t=\sum_{k\ge0}\gamma^k r_{t+k+1},\quad Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma\max_{a'}Q(s',a')-Q(s,a)].

For a terminal transition the continuation term is zero. A policy-gradient estimator uses a term proportional to $\nabla\log\pi_\theta(a\mid s)$ times a return or advantage estimate.

Worked example

For a nonterminal transition, current Q=2, reward=1, discount=0.9 and best next Q=4 give target 1+0.9×4=4.6. With alpha=0.5, updated Q is 2+0.5×(4.6−2)=3.3. Reusing the same target for a terminal transition would be incorrect.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
q, reward, discount, next_q, rate = 2, 1, .9, 4, .5
target = reward + discount*next_q
assert isclose(target, 4.6)
assert isclose(q+rate*(target-q), 3.3)
terminal_target = reward
assert q+rate*(terminal_target-q) == 1.5

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Prediction is not intervention. Randomly splitting overlapping time windows can leak future information. An environment reward is a modeling choice and may omit important real-world consequences.