---
title: Multi-Armed Bandits
module: Foundations
moduleNumber: 1
lessonNumber: 3
order: 103
summary: >
  A bandit is reinforcement learning stripped to a single decision, repeated:
  no state, no consequences, only the tension between exploiting the arm that
  looks best and exploring the ones that might be better. We build up the whole
  toolkit — sample-average value estimates, the incremental update rule,
  ε-greedy, optimistic initialization, UCB, and gradient bandits — and use it
  to study exploration in isolation, the one problem that carries over to the
  full setting.
topics: [Foundations]
sources:
  - book: Sutton & Barto
    ref: "Ch. 2 — Multi-armed Bandits; §2.1 A k-armed Bandit Problem; §2.2 Action-value Methods"
  - book: Sutton & Barto
    ref: "§2.4 Incremental Implementation; §2.5 Tracking a Nonstationary Problem; §2.6 Optimistic Initial Values"
  - book: Sutton & Barto
    ref: "§2.7 Upper-Confidence-Bound Action Selection; §2.8 Gradient Bandit Algorithms; §2.9 Associative Search"
---

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.[^sb-eval] 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](/reinforcement-learning/foundations/markov-decision-processes);
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**.[^sb-kbandit]

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_\ast(a)$, is the expected reward given that $a$ is chosen:

$$
q_\ast(a) \doteq \mathbb{E}\!\left[R_t \mid A_t = a\right].
$$

If you knew every $q_\ast(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_\ast(a)$, and we get
there only by selecting $a$ and watching what comes back.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=26mm, minimum height=13mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=acc, text=acc, thick] (ag) at (0,0) {agent};
  \node[box] (env) at (6.4,0) {environment\\(k arms)};
  \draw[->, acc, thick] (ag.north) .. controls (2,1.5) and (4.4,1.5) .. (env.north)
    node[midway, above, font=\footnotesize, text=black] {action A(t)};
  \draw[->, thick] (env.south) .. controls (4.4,-1.5) and (2,-1.5) .. (ag.south)
    node[midway, below, font=\footnotesize] {reward R(t)};
\end{tikzpicture}
$$

> **Definition (k-armed bandit).** A repeated decision among $k$ fixed actions
> (arms). Selecting arm $a$ returns a reward sampled from a stationary
> distribution with unknown mean $q_\ast(a)$. The goal is to maximize expected
> cumulative reward. There is no state: the situation is identical on every
> step, so the optimal policy is simply "always pull $\arg\max_a q_\ast(a)$."

## Estimating action values

The most natural way to estimate $q_\ast(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) \doteq \frac{\text{sum of rewards when } a \text{ taken prior to } t}{\text{number of times } a \text{ taken prior to } t}
= \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbb{1}_{A_i = a}}{\sum_{i=1}^{t-1} \mathbb{1}_{A_i = a}},
$$

where $\mathbb{1}_{\text{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_\ast(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 \doteq \arg\max_a 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.

> **Definition (Exploration vs. exploitation).** _Exploitation_ selects the
> action with the highest current estimate, maximizing expected immediate
> reward. _Exploration_ selects a non-greedy action to reduce uncertainty about
> its value, sacrificing immediate reward for information that may raise future
> reward. Balancing the two is the distinctive challenge of reinforcement
> learning, and the bandit isolates it from everything else.

## ε-greedy action selection

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

$$
A_t =
\begin{cases}
\arg\max_a Q_t(a) & \text{with probability } 1 - \varepsilon, \\[2pt]
\text{a uniformly random action} & \text{with probability } \varepsilon.
\end{cases}
$$

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

$$
% caption: ε-greedy selection — the greedy arm is chosen with probability
% $1-\varepsilon$; with probability $\varepsilon$ an arm is drawn uniformly at
% random, guaranteeing every arm is sampled indefinitely.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=30mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[circle, draw, minimum size=9mm] (start) at (0,0) {};
  \node[box, draw=acc, text=acc] (exploit) at (5.2,1.2) {exploit:\\pick argmax Q(a)};
  \node[box, draw=red, text=red] (explore) at (5.2,-1.2) {explore:\\pick a random arm};
  \draw[->, acc, thick] (start) .. controls (2.4,1.0) .. (exploit.west)
    node[midway, above, font=\scriptsize, text=black] {prob. 1 - e};
  \draw[->, red, thick] (start) .. controls (2.4,-1.0) .. (explore.west)
    node[midway, below, font=\scriptsize, text=black] {prob. e};
\end{tikzpicture}
$$

### The 10-armed testbed

To compare greedy against ε-greedy quantitatively, Sutton and Barto use a
standard benchmark: the **10-armed testbed**.[^sb-testbed] It is a suite of
$2000$ randomly generated $10$-armed bandit problems. For each problem the true
values $q_\ast(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_\ast(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 ($\varepsilon = 0$) against two ε-greedy methods ($\varepsilon = 0.01$
and $\varepsilon = 0.1$), all using sample-average estimates, gives the
characteristic result.

$$
% caption: Average reward on the 10-armed testbed over 1000 steps (schematic,
% after Sutton and Barto, Figure 2.2). The greedy method ($\varepsilon = 0$)
% climbs fast then plateaus low near $1$; $\varepsilon = 0.1$ explores most and
% ends highest; $\varepsilon = 0.01$ improves slowly but overtakes greedy. The
% best possible reward-per-step on this testbed is about $1.55$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{grn}{HTML}{1F9D4D}
  % axes
  \draw[->, black] (0,0) -- (8.6,0) node[right] {steps};
  \draw[->, black] (0,0) -- (0,4.3) node[above] {avg reward};
  \node[anchor=east] at (-0.1,4.0) {1.5};
  \node[anchor=east] at (-0.1,2.0) {0.75};
  \node[anchor=east] at (-0.1,0.0) {0};
  \node[anchor=north] at (0,-0.05) {1};
  \node[anchor=north] at (8.0,-0.05) {1000};
  % dashed best-possible line at 1.55 -> y = 1.55/1.5*4 ~ 4.13 (clip to 4.15)
  \draw[dashed, black] (0,4.13) -- (8.0,4.13);
  \node[anchor=south east, font=\scriptsize, text=black] at (8.0,4.13) {best possible};
  % epsilon = 0.1 (blue), highest
  \draw[acc, very thick]
    (0,0.2) .. controls (0.6,2.6) and (1.6,3.2) .. (3.0,3.5)
    .. controls (5.0,3.75) and (6.5,3.8) .. (8.0,3.85);
  % epsilon = 0.01 (red), slow climb, ends mid
  \draw[red, very thick]
    (0,0.2) .. controls (0.6,2.4) and (1.6,2.9) .. (3.0,3.05)
    .. controls (5.0,3.25) and (6.5,3.4) .. (8.0,3.5);
  % greedy epsilon = 0 (green), fast then flat low
  \draw[grn, very thick]
    (0,0.2) .. controls (0.5,2.5) and (1.2,2.75) .. (2.2,2.78)
    .. controls (4.0,2.8) and (6.0,2.8) .. (8.0,2.8);
  % right-end labels
  \node[acc, anchor=west, font=\scriptsize] at (8.05,3.85) {e = 0.1};
  \node[red, anchor=west, font=\scriptsize] at (8.05,3.5) {e = 0.01};
  \node[grn, anchor=west, font=\scriptsize] at (8.05,2.8) {e = 0 (greedy)};
\end{tikzpicture}
$$

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 $\varepsilon = 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); $\varepsilon = 0.01$ climbs more slowly but would
eventually exceed $\varepsilon = 0.1$ on both measures.

$$
% caption: Percentage of steps on which the optimal arm was selected (schematic,
% after Sutton and Barto, Figure 2.2). $\varepsilon = 0.1$ rises fastest but
% ceilings near $91\%$; $\varepsilon = 0.01$ climbs slowly toward a higher final
% level; greedy stalls near $33\%$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{grn}{HTML}{1F9D4D}
  \draw[->, black] (0,0) -- (8.6,0) node[right] {steps};
  \draw[->, black] (0,0) -- (0,4.3) node[above] {optimal action};
  \node[anchor=east] at (-0.1,4.0) {100\%};
  \node[anchor=east] at (-0.1,2.0) {50\%};
  \node[anchor=east] at (-0.1,0.0) {0\%};
  \node[anchor=north] at (0,-0.05) {1};
  \node[anchor=north] at (8.0,-0.05) {1000};
  % epsilon = 0.1 -> ceiling ~91% -> y ~ 3.64
  \draw[acc, very thick]
    (0,0.1) .. controls (0.8,2.0) and (2.0,3.0) .. (3.5,3.35)
    .. controls (5.5,3.55) and (6.8,3.62) .. (8.0,3.64);
  % epsilon = 0.01 -> slow climb toward ~55% -> y ~ 2.2
  \draw[red, very thick]
    (0,0.1) .. controls (1.5,0.9) and (3.5,1.6) .. (5.5,1.95)
    .. controls (6.6,2.1) and (7.3,2.18) .. (8.0,2.25);
  % greedy -> stalls ~33% -> y ~ 1.32
  \draw[grn, very thick]
    (0,0.1) .. controls (0.5,1.0) and (1.0,1.3) .. (1.8,1.32)
    .. controls (4.0,1.33) and (6.0,1.32) .. (8.0,1.32);
  \node[acc, anchor=west, font=\scriptsize] at (8.05,3.64) {e = 0.1};
  \node[red, anchor=west, font=\scriptsize] at (8.05,2.25) {e = 0.01};
  \node[grn, anchor=west, font=\scriptsize] at (8.05,1.32) {e = 0 (greedy)};
\end{tikzpicture}
$$

### 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_\ast(1) = 1.0$, $q_\ast(2) = 1.5$, $q_\ast(3) = 0.8$, so arm $2$ is optimal.
Run $\varepsilon$-greedy with $\varepsilon = 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)\!\gets\!0.6$ | $0.60$ | $0$ | $0$ | $1,0,0$ |
| $2$ | argmax $=1$ | $1$ | $1.7$ | $Q(1)\!\gets\!0.6+\tfrac12(1.1)$ | $1.15$ | $0$ | $0$ | $2,0,0$ |
| $3$ | argmax $=1$ | $1$ | $0.4$ | $Q(1)\!\gets\!1.15+\tfrac13(-0.75)$ | $0.90$ | $0$ | $0$ | $3,0,0$ |
| $4$ | explore | $2$ | $2.3$ | $Q(2)\!\gets\!2.3$ | $0.90$ | $2.30$ | $0$ | $3,1,0$ |
| $5$ | argmax $=2$ | $2$ | $0.9$ | $Q(2)\!\gets\!2.3+\tfrac12(-1.4)$ | $0.90$ | $1.60$ | $0$ | $3,2,0$ |
| $6$ | argmax $=2$ | $2$ | $1.4$ | $Q(2)\!\gets\!1.6+\tfrac13(-0.2)$ | $0.90$ | $1.53$ | $0$ | $3,3,0$ |
| $7$ | explore | $3$ | $0.5$ | $Q(3)\!\gets\!0.5$ | $0.90$ | $1.53$ | $0.50$ | $3,3,1$ |
| $8$ | argmax $=2$ | $2$ | $1.9$ | $Q(2)\!\gets\!1.53+\tfrac14(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 ($\varepsilon = 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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{grn}{HTML}{1F9D4D}
  \draw[->, black] (0,0) -- (8.6,0) node[right] {step t};
  \draw[->, black] (0,0) -- (0,3.2) node[above] {estimate Q(a)};
  \foreach \t in {1,...,8} \node[anchor=north, font=\scriptsize] at (\t,-0.03) {\t};
  \node[anchor=east, font=\scriptsize] at (-0.08,0) {0};
  \node[anchor=east, font=\scriptsize] at (-0.08,1.0) {1};
  \node[anchor=east, font=\scriptsize] at (-0.08,2.0) {2};
  \node[anchor=east, font=\scriptsize] at (-0.08,3.0) {3};
  % true value guides
  \draw[grn!55, dashed] (0,1.5) -- (8.3,1.5);
  \node[grn, anchor=east, font=\scriptsize] at (8.3,1.68) {q*(2)=1.5};
  % arm 1 (blue): 0.6, 1.15, 0.90, then flat at 0.90
  \draw[acc, thick] (1,0.6) -- (2,1.15) -- (3,0.90) -- (4,0.90) -- (5,0.90) -- (6,0.90) -- (7,0.90) -- (8,0.90);
  \foreach \t/\v in {1/0.6, 2/1.15, 3/0.90, 8/0.90} \fill[acc] (\t,\v) circle (1.3pt);
  % arm 2 (green): starts 0 until step 4 then 2.3, 1.6, 1.53, 1.53, 1.62
  \draw[grn, thick] (3,0) -- (4,2.30) -- (5,1.60) -- (6,1.53) -- (7,1.53) -- (8,1.62);
  \foreach \t/\v in {4/2.30, 5/1.60, 6/1.53, 8/1.62} \fill[grn] (\t,\v) circle (1.3pt);
  % arm 3 (red): 0 until step 7 then 0.5
  \draw[red, thick] (6,0) -- (7,0.50) -- (8,0.50);
  \fill[red] (7,0.50) circle (1.3pt);
  \node[acc, anchor=west, font=\scriptsize] at (8.05,0.90) {Q(1)};
  \node[grn, anchor=west, font=\scriptsize] at (8.05,1.62) {Q(2)};
  \node[red, anchor=west, font=\scriptsize] at (8.05,0.50) {Q(3)};
\end{tikzpicture}
$$

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:

$$
\begin{aligned}
Q_{n+1}
&= \frac{1}{n}\sum_{i=1}^{n} R_i
= \frac{1}{n}\left(R_n + \sum_{i=1}^{n-1} R_i\right)
= \frac{1}{n}\left(R_n + (n-1)Q_n\right) \\[4pt]
&= \frac{1}{n}\left(R_n + nQ_n - Q_n\right)
= Q_n + \frac{1}{n}\left[R_n - Q_n\right].
\end{aligned}
$$

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**:

$$
\text{NewEstimate} \leftarrow \text{OldEstimate} + \text{StepSize} \cdot \left[\text{Target} - \text{OldEstimate}\right].
$$

The bracketed quantity $\left[\text{Target} - \text{OldEstimate}\right]$ is an
**error** in the estimate, reduced by taking a step of size $\text{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
caption: $\textsc{Simple-Bandit}$ — $\varepsilon$-greedy action-value method
$Q(a) \gets 0$, $N(a) \gets 0$, for $a = 1$ to $k$
loop // forever
  with probability $1 - \varepsilon$ do
    $A \gets \arg\max_a Q(a)$ // ties broken at random
  else
    $A \gets$ a random action
  $R \gets \text{bandit}(A)$
  $N(A) \gets N(A) + 1$
  $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 $\alpha \in (0, 1]$ in place of $\frac{1}{n}$:

$$
Q_{n+1} \doteq Q_n + \alpha\left[R_n - Q_n\right].
$$

To see why a fixed $\alpha$ favors recent rewards, expand the recursion — each step
back multiplies by another factor of $(1-\alpha)$, 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 - \alpha)^n Q_1 + \sum_{i=1}^{n} \alpha (1 - \alpha)^{n-i} R_i.
$$

This is a weighted average — the weights $\alpha(1-\alpha)^{n-i}$ together with
$(1-\alpha)^n$ sum to $1$. The weight on reward $R_i$ decays by a factor of
$1 - \alpha$ 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.

$$
% caption: With a constant step size the weight on a reward decays
% exponentially with its age — the most recent reward carries weight $\alpha$
% and each earlier one is discounted by a further factor of $(1-\alpha)$, so the
% estimate tracks recent rewards and forgets the distant past.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, black] (0,0) -- (8.4,0) node[right] {reward age (recent = right)};
  \draw[->, black] (0,0) -- (0,3.6) node[above] {weight};
  % exponential decay bars, most recent at right (tall), older to left (short)
  \foreach \i/\h in {0/0.25, 1/0.40, 2/0.62, 3/0.98, 4/1.55, 5/2.45, 6/3.1} {
    \fill[acc!22, draw=acc] ({0.6 + \i*1.05}, 0) rectangle ({1.35 + \i*1.05}, \h);
  }
  \node[anchor=north, font=\scriptsize] at (7.0,-0.05) {most recent};
  \node[anchor=north, font=\scriptsize] at (1.0,-0.05) {oldest};
  \node[acc, anchor=south, font=\scriptsize] at (7.0,3.1) {weight = a};
\end{tikzpicture}
$$

For a step-size sequence
$\alpha_n(a)$, convergence to the true values with probability $1$ requires
$\sum_n \alpha_n(a) = \infty$ (steps large enough to overcome initial
conditions) and $\sum_n \alpha_n^2(a) < \infty$ (steps small enough to settle).
The sample-average choice $\alpha_n = \frac{1}{n}$ meets both. A constant
$\alpha$ 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 $\alpha$ 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.

> **Definition (Optimistic initial values).** Initializing action-value
> estimates above the plausible range of true values, so that any sampled reward
> disappoints the estimate and drives the learner to try alternatives. It
> produces early exploration with no explicit randomness, but is a stationary
> trick only: it cannot help a nonstationary problem, because its drive to
> explore is temporary — the beginning of time happens only once.

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](/reinforcement-learning/foundations/bandit-exploration-algorithms).

[^sb-eval]: **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.
[^sb-kbandit]: **Sutton & Barto**, §2.1 — A k-armed Bandit Problem: the repeated choice among $k$ actions with stationary reward distributions, the action value $q_\ast(a) \doteq \mathbb{E}[R_t \mid A_t = a]$, and the estimate $Q_t(a)$.
[^sb-testbed]: **Sutton & Barto**, §2.3 — The 10-armed Testbed: 2000 randomly generated 10-armed problems with $q_\ast(a) \sim \mathcal{N}(0,1)$ and unit-variance rewards, averaged to produce the reward and optimal-action learning curves of Figure 2.2.