Multi-armed Bandits

2.1 The k-armed bandit problem

You repeatedly choose among $k$ actions. After each choice you receive a numerical reward drawn from a stationary distribution that depends on the action. Goal: maximise expected total reward over, say, 1000 time steps. The setting is nonassociative — there is only one situation.

$Q_t(a)$ is our estimate of $q_*(a)$ at time $t$. Actions with the highest estimate are greedy. Choosing one is exploiting; choosing a non-greedy action is exploring. Exploitation maximises reward on the one step; exploration may give greater total reward in the long run. You cannot do both with one selection — hence the "conflict". The book's aim is not to balance them optimally (methods that do rely on strong assumptions about stationarity and priors) but simply to balance them at all.

2.2 Action-value methods

If the denominator is zero, use a default (e.g. 0). By the law of large numbers $Q_t(a)\to q_*(a)$ as the count goes to infinity.

ε-greedy: behave greedily with probability $1-\varepsilon$; with probability $\varepsilon$ pick an action uniformly at random (which may itself be the greedy one). In the limit every action is sampled infinitely often, so all $Q_t(a)\to q_*(a)$ and the probability of choosing the optimal action converges to more than $1-\varepsilon$.

2.3 The 10-armed testbed

• 2000 randomly generated bandit problems, $k=10$. True values $q_*(a)\sim\mathcal N(0,1)$; rewards $R_t\sim\mathcal N(q_*(A_t),1)$.
• Each run = 1000 steps on one problem; curves are averaged over the 2000 runs.
• Best possible average reward ≈ 1.54 (the expected maximum of 10 standard normals).

One can also reduce ε over time to get the best of both. The advantage of ε-greedy depends on the task:

• Higher reward variance (e.g. 10) → more exploration needed → ε-greedy does even better relative to greedy.
• Zero variance → greedy learns each value after one try and may do best.
• Nonstationary task → exploration is needed even in the deterministic case. Nonstationarity is the common case in RL (even a stationary task looks nonstationary while the policy is changing).

2.4 Incremental implementation

Storing every reward and re-averaging needs growing memory and computation. Instead, for one action, with $Q_n$ the estimate after $n-1$ rewards:

It holds even for $n=1$ (giving $Q_2=R_1$ for any $Q_1$). Memory: just $Q_n$ and $n$. This is an instance of the most important pattern in the book:

$[\textit{Target}-\textit{OldEstimate}]$ is an error; we take a step toward the (possibly noisy) target. Here the step size is $1/n$, which changes from step to step. The book writes the step size as $\alpha$ or $\alpha_t(a)$.

Initialize, for a = 1 to k:
    Q(a) ← 0
    N(a) ← 0
Loop forever:
    A ← argmax_a Q(a)    with probability 1 − ε   (breaking ties randomly)
        a random action   with probability ε
    R ← bandit(A)
    N(A) ← N(A) + 1
    Q(A) ← Q(A) + (1 / N(A)) · [R − Q(A)]

2.5 Tracking a nonstationary problem — constant vs varying step size

When reward probabilities change over time, it makes sense to weight recent rewards more heavily. The most popular way: a constant step size $\alpha\in(0,1]$.

Unrolling the recursion shows $Q_{n+1}$ is a weighted average of past rewards and the initial estimate:

The weights sum to 1: $(1-\alpha)^n + \sum_{i=1}^n\alpha(1-\alpha)^{n-i}=1$. The weight on $R_i$ decays exponentially with how many rewards ago ($n-i$) it was seen. If $\alpha=1$, all weight goes on the latest reward $R_n$ (using $0^0=1$).

Convergence conditions (stochastic approximation)

Let $\alpha_n(a)$ be the step size used for the $n$-th reward of action $a$. Convergence with probability 1 is assured if

• First condition: steps are large enough to eventually overcome any initial conditions or random fluctuations.
• Second condition: steps eventually become small enough to assure convergence.

Exercise 2.4 — general step-size weighting

With varying step sizes $\alpha_1,\alpha_2,\dots$:

With $\alpha_j=\alpha$ this reduces to (2.6); with $\alpha_j=1/j$ every weight becomes $1/n$ and the weight on $Q_1$ becomes 0.

Exercise 2.7 — the unbiased constant-step-size trick

$\bar o_n = 1-(1-\alpha)^n$, so $\beta_1 = 1$ — the first update sets $Q_2=R_1$ and wipes out $Q_1$ (no initial bias). As $n\to\infty$, $\bar o_n\to1$ and $\beta_n\to\alpha$ — it becomes an exponential recency-weighted average (keeps the tracking advantage).

2.6 Optimistic initial values

All methods so far are biased by their initial estimates $Q_1(a)$. For sample averages the bias disappears once every action is selected; for constant α it is permanent (decaying as $(1-\alpha)^n$). Usually harmless, sometimes helpful — the initial values become user-set parameters that can encode prior knowledge.

Trick: set $Q_1(a)=+5$ on the testbed (wildly optimistic, since $q_*\sim\mathcal N(0,1)$). Whatever is tried, the reward is "disappointing", so the learner switches to other actions. All actions are tried several times even with purely greedy selection.

• Figure 2.3 (α = 0.1): optimistic greedy ($Q_1=5,\varepsilon=0$) is worse at first (explores more) but eventually better than realistic ε-greedy ($Q_1=0,\varepsilon=0.1$) because its exploration dies out.
• Limitation: the drive to explore is temporary. Not suited to nonstationary problems — "the beginning of time occurs only once". (The same criticism applies to sample averages, which also treat the beginning specially.)

2.7 Upper-confidence-bound (UCB) action selection

ε-greedy explores indiscriminately. Better: prefer non-greedy actions according to their potential for being optimal — how close their estimates are to maximal and how uncertain they are.

• $N_t(a)$ = times $a$ was selected before $t$. If $N_t(a)=0$, $a$ is treated as maximising (try every action once first).
• $c>0$ controls the degree of exploration (the confidence level).
• The square-root term measures uncertainty: selecting $a$ increases $N_t(a)$ → bonus shrinks; selecting other actions increases $t$ → bonus grows. Because of $\ln t$, the increases get smaller over time but are unbounded — every action is eventually selected, but low-value or frequently tried actions with decreasing frequency.
• Deterministic exploration (no randomness), unlike ε-greedy.

2.8 Gradient bandit algorithms

Instead of estimating action values, learn a numerical preference $H_t(a)\in\mathbb R$. Only relative preferences matter (adding 1000 to all changes nothing). Action probabilities follow a soft-max (Gibbs/Boltzmann) distribution:

Initially all $H_1(a)=0$ (equal probabilities). After selecting $A_t$ and receiving $R_t$:

Compactly: $H_{t+1}(a) = H_t(a) + \alpha(R_t-\bar R_t)(\mathbb 1_{a=A_t}-\pi_t(a))$ for all $a$.

• $\bar R_t$ = average of rewards so far — the baseline. Reward above baseline → probability of $A_t$ goes up; below → goes down. Non-selected actions move the opposite way.
• Figure 2.5: with $q_*$ near +4, the baseline instantly adapts and performance is unaffected; without a baseline ($\bar R_t=0$) performance is significantly degraded.

Why it is stochastic gradient ascent

Exact gradient ascent on expected reward $\E[R_t]=\sum_x\pi_t(x)q_*(x)$ would be $H_{t+1}(a)=H_t(a)+\alpha\,\partial\E[R_t]/\partial H_t(a)$ (2.13). Using $\partial\pi_t(x)/\partial H_t(a)=\pi_t(x)(\mathbb 1_{a=x}-\pi_t(a))$ and the fact that $\sum_x\partial\pi_t(x)/\partial H_t(a)=0$ (so any baseline $B_t$ independent of $x$ can be subtracted), the gradient equals

So the expected update of (2.12) equals the true gradient → robust convergence. The baseline does not change the expected update, only its variance (and hence the speed of learning). Any baseline that does not depend on the selected action works; the reward average is simple and works well.

2.9 Associative search (contextual bandits)

So far, tasks were nonassociative: find (or track) one best action. In associative search you face one of several bandit tasks each step and receive a clue (e.g. the machine's colour) about which. You learn a policy: situation → best action.

2.10 Summary — comparing the methods

Parameter study (Figure 2.6)

Each point = average reward over the first 1000 steps (∝ area under the learning curve) for one algorithm at one parameter value; parameters vary by factors of two on a log scale. All curves are inverted-U: best at an intermediate value, neither too large nor too small. Assess a method by its best performance and its sensitivity — all are fairly insensitive (good over about an order of magnitude). On this problem UCB performs best.

Beyond the simple methods

• Gittins indices — a special action value giving optimal solutions in some special cases, but require complete knowledge of the prior distribution of problems; don't generalise to full RL.
• Bayesian methods — keep a posterior over action values. Thompson (posterior) sampling: pick each action with its posterior probability of being best; often performs like the best distribution-free methods.
• The Bayes-optimal balance can in principle be computed over the information state, but the tree explodes ($2^{2000}$ leaves for 2 actions, 2 rewards, 1000 steps).

Hyperparameters in this chapter

Self-test

Chapter quiz — check your understanding

Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.