Multi-Armed Bandits

The single feature that separates reinforcement learning from every other kind of learning is that its feedback evaluates the action taken rather than instructs which action was correct.¹ A supervised label tells you the right answer independent of what you guessed; an evaluative reward tells you only how good your choice was, and says nothing about the choices you didn't make. That single difference is what forces an agent to search — to try things in order to find out whether they are good.

This lesson studies evaluative feedback in the simplest possible setting: one that has no notion of state, where the same decision is faced over and over with no lasting consequences. Stripping the problem this far removes almost everything that makes reinforcement learning hard and leaves exactly one thing behind, in isolation, where we can see it clearly: the need to balance exploration against exploitation. Everything built here — value estimates, the incremental update rule, the exploration schemes — carries forward to the full RL problem; what is missing here is precisely what the next lessons add back.

The k-armed bandit problem

Consider being faced repeatedly with a choice among $k$ different actions. After each choice you receive a numerical reward drawn from a stationary probability distribution that depends on the action you selected, and your objective is to maximize expected total reward over some number of selections — say, over $1000$ time steps.²

The name comes by analogy to a slot machine, a one-armed bandit, except that this one has $k$ levers. Each play of a lever pays off from that lever's own reward distribution, and by playing repeatedly you concentrate your pulls on the levers that pay best. (A less cheerful analogy, from Sutton and Barto: a doctor choosing among experimental treatments for a series of seriously ill patients, where each reward is a patient's survival.)

Each of the $k$ actions has an expected reward given that it is selected; call this the value of the action. Write $A_{t}$ for the action selected at step $t$ and $R_{t}$ for the resulting reward. The value of an arbitrary action $a$ , denoted $q_{*} (a)$ , is the expected reward given that $a$ is chosen:

q_{*} (a) ≐ E [R_{t} ∣ A_{t} = a] .

If you knew every $q_{*} (a)$ the problem would be trivial: always pick the action with the largest value. The difficulty is that you do not know the values, and must estimate them from experience. Write $Q_{t} (a)$ for the estimated value of action $a$ at step $t$ . We want $Q_{t} (a)$ to be close to $q_{*} (a)$ , and we get there only by selecting $a$ and watching what comes back.

The bandit interaction loop — at each step the agent selects an arm

A_{t}

and the environment returns a reward

R_{t}

drawn from that arm's fixed distribution with mean

q_{*} (A_{t})

. There is no state and no next situation.

Estimating action values

The most natural way to estimate $q_{*} (a)$ is to average the rewards actually received from $a$ . If, prior to step $t$ , action $a$ has been chosen with rewards $R_{1}, R_{2}, \dots$ , the sample-average estimate is

Q_{t} (a) ≐ \frac{sum of rewards when a taken prior to t}{number of times a taken prior to t} = \frac{\sum _{i = 1}^{t - 1} R _{i} \cdot 1 _{A_{i} = a}}{\sum _{i = 1}^{t - 1} 1 _{A_{i} = a}},

where $1_{predicate}$ is $1$ when the predicate holds and $0$ otherwise. If the denominator is zero (the action has never been tried) we set $Q_{t} (a)$ to a default such as $0$ . By the law of large numbers, as the count of $a$ -selections grows, $Q_{t} (a) \to q_{*} (a)$ . This is only one estimator among many, but it is the one to build intuition on.

Given estimates, the simplest action-selection rule is to take a greedy action — one whose estimated value is currently largest:

A_{t} ≐ ar g a max Q_{t} (a) .

Greedy selection always exploits current knowledge to maximize immediate reward; it spends no time sampling apparently inferior actions to check whether they are secretly better.

Exploration versus exploitation

At any step, at least one action's estimate is the greatest. Selecting a greedy action is exploiting your current knowledge. Selecting a non-greedy action is exploring, because it improves your estimate of that action's value. Exploitation is the right move for maximizing the reward on this one step, but exploration may yield more reward in the long run.

The conflict is genuine and unavoidable. Suppose a greedy action's value is known with certainty, while several alternatives are estimated to be nearly as good but with large uncertainty. At least one of those uncertain actions is probably better than the greedy one — you just don't yet know which. Spend a few steps finding out, and you can exploit the winner for all the steps that remain. Because you cannot both explore and exploit on a single selection, every method must decide how to split its selections between the two.

ε-greedy action selection

The simplest way to force some exploration is to behave greedily most of the time but, on a small fraction $ε$ of steps, select uniformly at random among all the actions:

A_{t} = {ar g max_{a} Q_{t} (a) a uniformly random action with probability 1 - ε, with probability ε .

These ε-greedy methods have a useful asymptotic guarantee: because every action is eventually sampled infinitely often, every $Q_{t} (a)$ converges to $q_{*} (a)$ , and the probability of selecting the optimal action converges to more than $1 - ε$ . That is only an asymptotic statement, though; what matters in practice is how the methods behave over a finite run.

ε-greedy selection — the greedy arm is chosen with probability

1 - ε

; with probability

ε

an arm is drawn uniformly at random, guaranteeing every arm is sampled indefinitely.

The 10-armed testbed

To compare greedy against ε-greedy quantitatively, Sutton and Barto use a standard benchmark: the 10-armed testbed.³ It is a suite of $2000$ randomly generated $10$ -armed bandit problems. For each problem the true values $q_{*} (a)$ , $a = 1, \dots, 10$ , are drawn independently from a standard normal distribution (mean $0$ , variance $1$ ). When a method selects action $A_{t}$ on a given problem, the reward $R_{t}$ is drawn from a normal distribution with mean $q_{*} (A_{t})$ and variance $1$ . A method is run for $1000$ steps on one problem — one run — and its behavior is averaged over all $2000$ runs to measure how it improves with experience.

Two curves summarize a method's learning: the average reward per step, and the percentage of steps on which the optimal action was chosen. Comparing a greedy method ( $ε = 0$ ) against two ε-greedy methods ( $ε = 0.01$ and $ε = 0.1$ ), all using sample-average estimates, gives the characteristic result.

Average reward on the 10-armed testbed over 1000 steps (schematic, after Sutton and Barto, Figure 2.2). The greedy method (

ε = 0

) climbs fast then plateaus low near

1

;

ε = 0.1

explores most and ends highest;

ε = 0.01

improves slowly but overtakes greedy. The best possible reward-per-step on this testbed is about

1.55

The greedy method improves slightly faster at the very start but plateaus at a reward-per-step of about $1$ , well below the best possible $1.55$ . It gets stuck because it often locks onto a suboptimal action after a few unlucky early samples of the true best one and never reconsiders — on this testbed greedy finds the optimal action only about a third of the time. The ε-greedy methods do worse at first (they waste steps exploring) but keep improving their estimates and eventually pull ahead. The $ε = 0.1$ method explores more, finds the best arm sooner, but caps its optimal-action rate at $91%$ (it keeps exploring $10%$ of the time); $ε = 0.01$ climbs more slowly but would eventually exceed $ε = 0.1$ on both measures.

Percentage of steps on which the optimal arm was selected (schematic, after Sutton and Barto, Figure 2.2).

ε = 0.1

rises fastest but ceilings near

91%

;

ε = 0.01

climbs slowly toward a higher final level; greedy stalls near

33%

A worked ε-greedy trace

The learning curves average over $2000$ problems, which hides the mechanics. It helps to watch a single run step by step. Take a $3$ -armed bandit with true values $q_{*} (1) = 1.0$ , $q_{*} (2) = 1.5$ , $q_{*} (3) = 0.8$ , so arm $2$ is optimal. Run $ε$ -greedy with $ε = 0.1$ , sample-average estimates, all $Q_{1} (a) = 0$ , ties broken toward the lowest index. The rewards below are the values actually sampled from each arm's unit-variance normal on this run.

$t$	greedy?	$A_{t}$	$R_{t}$	update	$Q (1)$	$Q (2)$	$Q (3)$	$N$ 's
$1$	tie $\to 1$	$1$	$0.6$	$Q (1) \leftarrow 0.6$	$0.60$	$0$	$0$	$1, 0, 0$
$2$	argmax $= 1$	$1$	$1.7$	$Q (1) \leftarrow 0.6 + \frac{1}{2} (1.1)$	$1.15$	$0$	$0$	$2, 0, 0$
$3$	argmax $= 1$	$1$	$0.4$	$Q (1) \leftarrow 1.15 + \frac{1}{3} (- 0.75)$	$0.90$	$0$	$0$	$3, 0, 0$
$4$	explore	$2$	$2.3$	$Q (2) \leftarrow 2.3$	$0.90$	$2.30$	$0$	$3, 1, 0$
$5$	argmax $= 2$	$2$	$0.9$	$Q (2) \leftarrow 2.3 + \frac{1}{2} (- 1.4)$	$0.90$	$1.60$	$0$	$3, 2, 0$
$6$	argmax $= 2$	$2$	$1.4$	$Q (2) \leftarrow 1.6 + \frac{1}{3} (- 0.2)$	$0.90$	$1.53$	$0$	$3, 3, 0$
$7$	explore	$3$	$0.5$	$Q (3) \leftarrow 0.5$	$0.90$	$1.53$	$0.50$	$3, 3, 1$
$8$	argmax $= 2$	$2$	$1.9$	$Q (2) \leftarrow 1.53 + \frac{1}{4} (0.37)$	$0.90$	$1.62$	$0.50$	$3, 3, 1$

Two things stand out. On step $1$ every estimate is tied at $0$ , so the greedy rule picks arm $1$ by the tie-break, and three straight exploits of arm $1$ lock in before any exploration happens — a greedy method ( $ε = 0$ ) would have stayed on arm $1$ forever from this start, never discovering that arm $2$ pays more. The lone exploratory step at $t = 4$ is what rescues the run: one pull of arm $2$ returns $2.3$ , its estimate jumps above arm $1$ 's, and from then on the greedy action is the optimal arm. By step $8$ the estimates ( $0.90, 1.62, 0.50$ ) already order the arms correctly, and further pulls will tighten $Q (2)$ toward its true $1.5$ . This is the whole argument for exploration in miniature: a single non-greedy pull changed which action the method commits to for the rest of the run.

The worked trace above, plotted. Each estimate

Q (a)

(three lines) moves only on steps that pull arm

a

; the sample-average step

1/ N (a)

shrinks each move as counts grow. The exploratory pull of arm 2 at step 4 lifts

Q (2)

above

Q (1)

, after which the greedy choice tracks the optimal arm.

The advantage of exploring depends on the task. With noisier rewards it takes more exploration to identify the best arm, so ε-greedy wins by more. With deterministic rewards greedy would know each action's value after one try and never need to explore — except that even then, if the problem is nonstationary (the true values drift over time), exploration is needed to catch an action that has quietly become the best. Nonstationarity is the case most often met in reinforcement learning, which is one reason exploration never goes away.

Incremental implementation

Storing every reward and re-averaging would cost memory and computation that grow without bound. The average can instead be rewritten so each new reward nudges the old estimate a little, with no history stored — a shape that recurs throughout the subject. Concentrate on a single action and let $Q_{n}$ denote the estimate of its value after it has been selected $n - 1$ times, so $Q_{n} = (R_{1} + \dots + R_{n - 1}) / (n - 1)$ . Given the new reward $R_{n}$ , the updated average can be computed from $Q_{n}$ alone:

Q_{n + 1} = \frac{1}{n} i = 1 \sum n R_{i} = \frac{1}{n} (R_{n} + i = 1 \sum n - 1 R_{i}) = \frac{1}{n} (R_{n} + (n - 1) Q_{n}) = \frac{1}{n} (R_{n} + n Q_{n} - Q_{n}) = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}] .

This requires memory only for $Q_{n}$ and $n$ , and a small constant computation per step. The last line has a form that recurs throughout reinforcement learning — the general update rule:

NewEstimate \leftarrow OldEstimate + StepSize \cdot [Target - OldEstimate] .

The bracketed quantity $[Target - OldEstimate]$ is an error in the estimate, reduced by taking a step of size $StepSize$ toward the Target (here the new reward $R_{n}$ ). For the sample average the step size is $\frac{1}{n}$ , shrinking as more rewards accumulate. Almost every method in the rest of the subject is an instance of this one line; only the target and the step size change.

Algorithm:

\textsc{Simple-Bandit}

—

\varepsilon

-greedy action-value method

1
$Q(a) \gets 0$ , $N(a) \gets 0$ , for $a = 1$ to $k$
2
loop
forever
3
with probability $1 - \varepsilon$ do
4
$A \gets \arg\max_a Q(a)$
ties broken at random
5
else
6
$A \gets$ a random action
7
$R \gets \text{bandit}(A)$
8
$N(A) \gets N(A) + 1$
9
$Q(A) \gets Q(A) + \frac{1}{N(A)}\big[R - Q(A)\big]$

Nonstationary problems

The sample average weights every past reward equally — the right choice for a stationary problem, the wrong one where the true values drift. When the problem is nonstationary it makes sense to weight recent rewards more heavily than old ones. The standard way to do this is to use a constant step size $α \in (0, 1]$ in place of $\frac{1}{n}$ :

Q_{n + 1} ≐ Q_{n} + α [R_{n} - Q_{n}] .

To see why a fixed $α$ favors recent rewards, expand the recursion — each step back multiplies by another factor of $(1 - α)$ , so a reward's influence fades the older it gets. Unrolling the recursion shows what the constant step size does to the weights:

Q_{n + 1} = (1 - α)^{n} Q_{1} + i = 1 \sum n α (1 - α)^{n - i} R_{i} .

This is a weighted average — the weights $α (1 - α)^{n - i}$ together with $(1 - α)^{n}$ sum to $1$ . The weight on reward $R_{i}$ decays by a factor of $1 - α$ for each intervening step, so older rewards contribute exponentially less. For this reason a constant step size is called an exponential recency-weighted average: it tracks a moving target instead of converging to a fixed one.

With a constant step size the weight on a reward decays exponentially with its age — the most recent reward carries weight

α

and each earlier one is discounted by a further factor of

(1 - α)

, so the estimate tracks recent rewards and forgets the distant past.

For a step-size sequence $α_{n} (a)$ , convergence to the true values with probability $1$ requires $\sum_{n} α_{n} (a) = \infty$ (steps large enough to overcome initial conditions) and $\sum_{n} α_{n}^{2} (a) < \infty$ (steps small enough to settle). The sample-average choice $α_{n} = \frac{1}{n}$ meets both. A constant $α$ meets the first but not the second — so the estimate never fully converges and keeps responding to the latest rewards, which is precisely what you want when the target is moving.

Optimistic initial values

Every method so far depends on the initial estimates $Q_{1} (a)$ , which introduces a bias. For sample averages that bias vanishes once each action has been tried; for constant $α$ it is permanent but fades over time. The initial values are usually a nuisance parameter to be set to zero — but they can also be turned into a cheap exploration trick.

Suppose that on the 10-armed testbed, where the true values are near zero, we set every initial estimate to $Q_{1} (a) = + 5$ . That is wildly optimistic: whatever action is tried first returns a reward well below $5$ , so its estimate drops, and the learner becomes disappointed and switches to another still-optimistic action. Every action gets tried several times before the estimates settle — the system explores at the start even if it acts greedily throughout.

Optimistic initialization is effective and simple on stationary problems, but it is not a general solution to exploration. It works exactly once, and any task that changes later gets no benefit from it. This lesson built the value-estimation core of the bandit and the two simplest ways to force exploration. Smarter exploration — optimism under uncertainty, learned preferences, adding context, and the regret theory that ranks these methods — continues in Bandit Exploration Algorithms.

Sutton & Barto, Reinforcement Learning (2nd ed.), Ch. 2 introduction — the defining feature of reinforcement learning is evaluative feedback (how good the action taken was) as opposed to instructive feedback (what the correct action was), which is what creates the need for active exploration. ↩
Sutton & Barto, §2.1 — A k-armed Bandit Problem: the repeated choice among $k$ actions with stationary reward distributions, the action value $q_{*} (a) ≐ E [R_{t} ∣ A_{t} = a]$ , and the estimate $Q_{t} (a)$ . ↩
Sutton & Barto, §2.3 — The 10-armed Testbed: 2000 randomly generated 10-armed problems with $q_{*} (a) \sim N (0, 1)$ and unit-variance rewards, averaged to produce the reward and optimal-action learning curves of Figure 2.2. ↩