3.Multi-Armed Bandits: Exploration & Exploitation

3.1 The simplest problem that is still hard

Reacher, a two-link arm, faces a mug. It has $k$ grasp primitives available — top grasp, side grasp, rim hook, and so on. Each attempt either succeeds, partially succeeds, or knocks the mug over, and the outcome is noisy: the same primitive on the same mug does not always produce the same result.

Reacher must choose repeatedly, and wants to accumulate as much success as possible. Formally: at each step $t$ it selects an action $A_t \in \{1, \ldots, k\}$ and receives a reward $R_t$ drawn from a fixed but unknown distribution associated with that action. Define the true value of an action as its expected reward:

$q_*(a) \doteq \mathbb{E}[R_t \mid A_t = a].$

If Reacher knew $q_*$, the problem would be trivial: always pick the argmax. It does not know $q_*$, and the only way to learn about an action is to take it — spending a trial that could have gone to the currently-best-looking option.

3.2 Estimating values, incrementally

The obvious estimator is the sample average of the rewards received from action $a$ so far:

$Q_n(a) \doteq \frac{R_1 + R_2 + \cdots + R_{n-1}}{n - 1}.$

Storing every reward would be wasteful, and it is unnecessary. Expand the average at step $n+1$ and rearrange:

Which is exactly the master pattern promised in Chapter 2:

$\text{New} \leftarrow \text{Old} + \alpha\left(\text{Target} - \text{Old}\right).$

With $\alpha_n = 1/n$ the Robbins–Monro conditions hold ($\sum 1/n = \infty$, $\sum 1/n^2 < \infty$), so $Q_n(a) \to q_*(a)$ almost surely. Sample averaging is stochastic approximation, and we already proved it converges.

Non-stationarity changes the calculus. Replace $1/n$ with a constant $\alpha$ and unroll:

$Q_{n+1} = (1-\alpha)^n Q_1 + \sum_{i=1}^{n} \alpha (1-\alpha)^{n-i} R_i.$

The weights $\alpha(1-\alpha)^{n-i}$ decay geometrically into the past — an exponential recency-weighted average. The second Robbins–Monro condition now fails, so the estimate never fully settles. That is a feature when Reacher's gripper wears down and old data becomes actively misleading.

3.3 Regret: the right scorecard

Total reward is a bad way to compare algorithms, because it depends on how generous the bandit happens to be. The standard measure is regret — how much worse you did than an oracle that knew $q_*$ from the start:

$L_n \doteq n \max_a q_*(a) - \sum_{t=1}^{n} q_*(A_t) = \sum_{a} \Delta_a\, \mathbb{E}[N_n(a)],$

where $\Delta_a = \max_{a'} q_*(a') - q_*(a)$ is the gap of action $a$ and $N_n(a)$ counts how often it was chosen. That identity is worth sitting with: regret is the sum over suboptimal actions of how bad they are, times how often you took them. An algorithm is good precisely when it stops taking bad actions quickly.

Linear regret means the per-step penalty never vanishes: however long Reacher runs, it keeps paying the same exploration tax forever. Any algorithm worth using achieves sublinear regret, so that the average penalty tends to zero. Decaying $\varepsilon$ toward zero — slowly enough that every action is still tried infinitely often — recovers sublinearity, and is the seed of the GLIE conditions Chapter 6 needs for Q-learning to converge.

3.4 UCB: deriving optimism from a concentration bound

The most elegant answer to "which action should I try?" comes from asking a sharper question: which action could plausibly be best, given what I have seen?

Hoeffding's inequality gives the tool. For $n$ independent samples of a bounded random variable with mean $\mu$ and sample mean $\hat\mu$,

$\mathbb{P}\big(\hat\mu + u \le \mu\big) \le e^{-2 n u^2}.$

Set the failure probability to $p = e^{-2nu^2}$ and solve for the bonus:

$u = \sqrt{\frac{-\log p}{2n}}.$

Now choose how confident to be. If we want the bound to hold more tightly as we gather data — say $p = t^{-4}$ at time $t$ — then $-\log p = 4 \log t$ and

$u = \sqrt{\frac{2 \log t}{n}}.$

That is the UCB bonus. The rule is: act greedily with respect to an optimistic estimate,

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

Three things are worth doing in that testbed before reading on. Set $\varepsilon = 0$ and watch the greedy curve plateau below every other method — it locks onto whichever arm happened to look good first. Raise $\varepsilon$ and observe that early reward drops while the percent-optimal curve keeps climbing: exploration is paid for immediately and repaid later. Finally, compare the regret panel: UCB's curve visibly bends toward logarithmic while ε-greedy's stays a straight line, exactly as Proposition 3.1 predicts.

3.5 Gradient bandits: the seed of everything in Chapter 10

So far we have estimated values and acted greedily on them. There is a different approach: learn a preference $H_t(a)$ for each action, with no interpretation as a reward estimate, and act stochastically according to a softmax:

$\pi_t(a) \doteq \frac{e^{H_t(a)}}{\sum_b e^{H_t(b)}}.$

This is the book's first stochastic policy, and it is a genuinely different object from $Q$. Preferences are only meaningful relative to each other; adding a constant to all of them changes nothing.

The update rule is:

$H_{t+1}(a) = H_t(a) + \alpha\left(R_t - \bar R_t\right)\left(\mathbb{1}[a = A_t] - \pi_t(a)\right),$

where $\bar R_t$ is a running average of all rewards, serving as a baseline. This is not a heuristic — it is exact stochastic gradient ascent on expected reward. In expectation,

$\mathbb{E}\left[H_{t+1}(a) - H_t(a)\right] = \alpha \frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)}.$

3.6 Thompson sampling, and what comes next

One more algorithm, because it is both the oldest (1933) and among the best performing in practice. Thompson sampling maintains a posterior distribution over each action's value, then at each step draws one sample from each posterior and acts greedily on the samples.

The elegance is that exploration falls out for free. An action with a wide posterior sometimes draws a high sample and gets tried; as evidence accumulates its posterior narrows and it is chosen only if it deserves to be. There is no bonus term to tune — the uncertainty is the exploration mechanism.

Contextual bandits add the one ingredient we have been suppressing: a context $x_t$ observed before choosing. Reacher now sees the mug's estimated pose and picks a grasp conditioned on it. Regret is redefined against the best policy in a class rather than the best fixed action.

And here is the cliff the chapter ends on, stated precisely because it defines the rest of the book:

use rand::Rng;
 
/// A k-armed bandit problem with unknown true action values.
pub trait Bandit {
    fn arms(&self) -> usize;
    fn pull<R: Rng>(&self, arm: usize, rng: &mut R) -> f64;
    fn optimal_arm(&self) -> usize;
}
 
/// Any rule for choosing among arms and learning from what it observes.
pub trait BanditPolicy {
    fn select<R: Rng>(&mut self, step: usize, rng: &mut R) -> usize;
    fn update(&mut self, arm: usize, reward: f64);
}
 
pub struct Ucb1 {
    q: Vec<f64>,
    counts: Vec<u64>,
    c: f64,
}
 
impl BanditPolicy for Ucb1 {
    fn select<R: Rng>(&mut self, step: usize, _rng: &mut R) -> usize {
        // Untried arms have an infinite bound — try each one once first.
        if let Some(a) = self.counts.iter().position(|&n| n == 0) {
            return a;
        }
        let t = (step.max(2)) as f64;
        self.q
            .iter()
            .zip(&self.counts)
            .map(|(&q, &n)| q + self.c * (t.ln() / n as f64).sqrt())
            .enumerate()
            .max_by(|a, b| a.1.partial_cmp(&b.1).unwrap())
            .map(|(a, _)| a)
            .unwrap()
    }
 
    fn update(&mut self, arm: usize, reward: f64) {
        self.counts[arm] += 1;
        // Robbins–Monro with α = 1/n: the sample average, computed incrementally.
        self.q[arm] += (reward - self.q[arm]) / self.counts[arm] as f64;
    }
}

3.7 Chapter bridge

We isolated the exploration–exploitation dilemma by removing state, and found that even then the problem has real mathematical content: regret decomposes into gaps times counts, optimism in the face of uncertainty is derivable from a concentration inequality rather than merely sensible, and a softmax over learned preferences performs exact gradient ascent on expected reward.

Chapter 4 puts state back. Once actions influence what you face next, "the value of an action" must account for the future it leads to, and the equations that express this — the Bellman equations — are the mathematical centre of the entire subject. Rusty's warehouse becomes a formal object, and the contraction theorem from Chapter 2 finally does the job it was built for.

References