Chapter 2 — multi-armed bandits.

Chapter 2 strips RL down to its hardest single idea — evaluative feedback and the explore/exploit trade-off — by removing states entirely. You repeatedly choose among \(k\) actions and get a reward each time; the only job is to learn which arm is best while still earning. This page covers action values, sample-average and incremental estimation, \(\varepsilon\)-greedy selection, the 10-armed testbed, tracking nonstationary problems with a constant step size (with the weighted-average derivation), optimistic initial values, UCB, and gradient bandits. Maps to lectures CS2–CS3.

Why study a problem with no states?

The most important feature distinguishing RL from other learning is that it uses evaluative feedback — feedback that indicates how good the action taken was, but not whether it was the best or worst possible. This is the opposite of instructive feedback (supervised learning), which states the correct action independently of the action taken. To study evaluative feedback in its purest form, Chapter 2 uses a setting with a single state: the nonassociative \(k\)-armed bandit. With no states to complicate matters, every lesson is about exploration, exploitation, and value estimation alone — and those lessons carry directly into the full problem.

The k-armed bandit problem

You are faced repeatedly with a choice among \(k\) different options, or actions. After each choice you receive a numerical reward chosen from a stationary probability distribution that depends on the action you selected. Your objective is to maximize the expected total reward over some time period, say over 1000 action selections (time steps).

The name comes from a slot machine — a "one-armed bandit" — except with \(k\) levers. Each action selection is like a play of one of the machine's levers, and the rewards are the payoffs for hitting the jackpot. Through repeated plays you must learn to concentrate your actions on the best levers. The course frames it exactly this way, with four slot machines whose expected payoffs differ (e.g. \(\mathbb{E}[a]=-\$0.5,\ \mathbb{E}[b]=-\$0.2,\ \mathbb{E}[c]=\$0.1,\ \mathbb{E}[d]=\$0.11\)). The strategy is to identify the best lever(s) and keep pulling them — but that raises the questions: how do we define the best, and how do we find it?

Action values

Each of the \(k\) actions has an expected or mean reward given that the action is selected — its value. Denote the action selected at time step \(t\) as \(A_t\), and the corresponding reward as \(R_t\). The value of an arbitrary action \(a\) is the expected reward given that \(a\) is selected:

If you knew the value of each action, solving the bandit would be trivial — you would always select the action with the highest value. The whole difficulty is that you do not know the action values with certainty, though you may have estimates. Denote the estimated value of action \(a\) at step \(t\) as \(Q_t(a)\); we want \(Q_t(a)\) to be close to \(q_*(a)\).

Greedy actions, exploring and exploiting

At any step there is at least one action whose estimated value is greatest — the greedy action(s). Selecting one of these is exploiting your current knowledge of action values. Selecting a non-greedy action is exploring, because it improves your estimate of that action's value. Exploitation maximizes expected reward on the one step, but exploration may produce greater total reward in the long run, because after discovering better actions you can exploit them many times. During exploration reward is lower in the short run but potentially higher in the long run. Because it is impossible both to explore and to exploit with a single action selection, this conflict — the exploration–exploitation dilemma — is the central problem.

Action-value methods: the sample average

The most natural way to estimate \(q_*(a)\) is to average the rewards actually received when \(a\) was taken:

where \(\mathbb{1}_{\text{predicate}}\) is 1 if the predicate is true and 0 otherwise. If the denominator is zero (the action has never been taken) we define \(Q_t(a)\) as some default such as 0. As the denominator goes to infinity, by the law of large numbers \(Q_t(a)\) converges to \(q_*(a)\). This is the sample-average method — one way, not necessarily the best. Worked example from the slides: pulling arm \(a\) and seeing rewards \(-1,-1,5\) gives \(\widehat{\mathbb{E}}[a]=\tfrac{-1-1+5}{3}=1\).

Greedy and ε-greedy action selection

The simplest selection rule is greedy: pick the action with the highest current estimate.

Greedy selection always exploits current knowledge to maximize immediate reward; it spends no time sampling apparently inferior actions to see if they might really be better. A simple alternative is to behave greedily most of the time but, every once in a while, with small probability \(\varepsilon\), instead select randomly from among all the actions with equal probability, independently of the action-value estimates. This is the \(\varepsilon\)-greedy method.

epsilon = 0.05            # small value to control exploration
def get_action():
    if random.random() > epsilon:
        return argmax_a(Q(a))     # exploit (greedy)
    else:
        return random.choice(A)   # explore (uniform random)

An advantage of \(\varepsilon\)-greedy: as the number of steps increases, every action is sampled an infinite number of times, ensuring all \(Q_t(a)\) converge to their respective \(q_*(a)\). It is easy to implement, easy to tune via the single parameter \(\varepsilon\), and yields good results in practice.

The 10-armed testbed

To compare greedy and \(\varepsilon\)-greedy fairly, the book uses the 10-armed testbed: 2000 randomly generated \(k\)-armed bandit problems with \(k=10\). For each, the true action values \(q_*(a)\) are drawn from a normal (Gaussian) distribution with mean 0 and variance 1; when an action \(A_t\) is selected, the actual reward \(R_t\) is drawn from a normal distribution with mean \(q_*(A_t)\) and variance 1. A method runs for 1000 steps on one problem (a "run"); performance is averaged over the 2000 runs to reveal typical behaviour.

The findings are the classic result of the chapter: the greedy method improves slightly faster at the very beginning but then levels off at a lower level — it often gets stuck performing suboptimal actions because it never explores. The \(\varepsilon\)-greedy methods eventually perform better because they continue to explore and improve their chances of recognizing the optimal action. \(\varepsilon=0.1\) explores more and usually finds the optimal action earlier; \(\varepsilon=0.01\) improves more slowly but eventually performs better than \(\varepsilon=0.1\). The advantage of exploration depends on the task — noisier rewards favour more exploration, while deterministic rewards favour greed.

Incremental implementation

Computing the average by storing every reward would grow memory and computation without bound. Instead, derive an incremental update. Let \(Q_n\) denote the estimate after \(n-1\) rewards. Then:

This requires memory only for \(Q_n\) and \(n\), and a small constant computation per step. It has the general form that appears throughout the book:

The bracket \([\,\text{Target}-\text{OldEstimate}\,]\) is an error in the estimate; it is reduced by taking a step toward the Target. Here the step size is \(\tfrac1n\), which changes from step to step. This exact pattern is the TD update from Chapter 1 and reappears in DP and beyond.

Tracking a nonstationary problem

Averaging is appropriate for stationary bandits, but RL problems are often nonstationary — the true values drift over time. In such cases it makes sense to weight recent rewards more heavily than long-past ones. A popular way is to use a constant step size \(\alpha\in(0,1]\):

Why a constant α gives an exponentially-weighted average

Unrolling the recursion reveals what the constant-\(\alpha\) update actually computes:

This is a weighted average: the weights sum to 1, and the weight on reward \(R_i\), namely \(\alpha(1-\alpha)^{n-i}\), decays exponentially as we go further back in time (because \(1-\alpha < 1\)). It is therefore called an exponential, recency-weighted average. Recent rewards count more; ancient rewards fade. That is exactly the behaviour you want when the world is changing.

Optimistic initial values

All the methods so far depend to some extent on the initial estimates \(Q_1(a)\) — they are biased by their initial values. For sample averages the bias disappears once every action has been selected at least once; for constant \(\alpha\) the bias is permanent though decreasing. This initial bias can be turned into a feature: set the initial estimates optimistically high. In the 10-armed testbed, setting all \(Q_1(a)=+5\) (when true values average 0) makes every action disappointing at first — whatever action is tried, the reward is less than the rosy starting estimate, so the learner switches to other actions, "disappointed" each time. The result is that all actions are tried several times before the estimates settle. The system explores even with purely greedy selection, no \(\varepsilon\) required.

Upper-Confidence-Bound (UCB) action selection

\(\varepsilon\)-greedy explores indiscriminately — when it explores, it picks any action with equal probability, including clearly bad ones. It would be better to explore among the non-greedy actions according to their potential for actually being optimal, taking into account both how close their estimates are to being maximal and the uncertainty in those estimates. Upper-Confidence-Bound selection does exactly this:

where \(N_t(a)\) is the number of times \(a\) has been selected before \(t\), and \(c>0\) controls the degree of exploration. The square-root term is a measure of the uncertainty in the estimate of \(a\)'s value. Each time \(a\) is selected, \(N_t(a)\) increases and the uncertainty term shrinks; each time another action is selected, \(t\) increases but \(N_t(a)\) does not, so \(a\)'s uncertainty term grows — making it more likely to be tried again eventually. Actions with lower value estimates, or that have already been selected often, get selected with decreasing frequency over time. UCB often performs well but is harder to extend to nonstationary problems and large state spaces than \(\varepsilon\)-greedy.

Gradient bandit algorithms

So far methods estimate action values and use them to pick actions. An alternative is to learn a numerical preference \(H_t(a)\) for each action — not interpreted as a reward, only as how much one action is preferred over another. The probabilities of selecting actions are given by a soft-max (Gibbs/Boltzmann) distribution:

Preferences are updated by stochastic gradient ascent: after selecting \(A_t\) and receiving \(R_t\), the preference of the chosen action is increased (and others decreased) in proportion to how the reward compares with a baseline — the average of all rewards so far. This previews policy-gradient methods (acting directly on a parameterized policy rather than via value estimates), a major theme later in the book.

Associative search (contextual bandits)

The pure bandit is nonassociative: there is only one situation. But many problems present different bandit situations and you must learn to associate the best action with each situation. This is associative search, or a contextual bandit: like a bandit in that each action affects only the immediate reward, but like the full RL problem in that the best action depends on the situation. It is the bridge to the next chapter — once actions also affect the next situation (not just the immediate reward), you have the full reinforcement-learning problem, the Markov decision process of Chapter 3.

Putting the methods side by side

Lecture map & recap

References & next

• Chapter 3 — Finite MDPs → · when actions also change the state
• ← Chapter 1 — The RL Problem
• CS2–CS3 — Slides Explained · the lecture version