Gradient bandit algorithms

Learning objective

Be able to state the gradient bandit update from memory, derive it line by line as stochastic gradient ascent on expected reward — including why a baseline may be subtracted for free and why $\pi_t(A_t)$ cancels — and predict when the baseline changes the outcome and when it does not.

Intuition

Every method so far estimates $q_*(a)$ and then argues about how to act on the estimates. $\varepsilon$-greedy, optimistic starts and UCB differ only in the argument; all three keep a number per arm that is trying to be a value.

Gradient bandits skip the value. They keep a preference $H_t(a)$ — a number with no units and no meaning on its own, whose only job is to be larger for arms worth taking. Preferences are turned into a probability distribution and actions are drawn from it:

$$\pi_t(a) \;=\; \Pr\{A_t = a\} \;=\; \frac{e^{H_t(a)}}{\sum_{b=1}^{k} e^{H_t(b)}}$$

Two consequences fall out of that definition immediately, and both matter later:

• Only differences of preferences matter. Add a constant $c$ to every $H_t(a)$ and the $e^{c}$ factors cancel top and bottom, leaving $\pi_t$ unchanged. There is no absolute scale to learn, which is why $H$ never has to agree with $q_*$ about anything.
• Exploration is graded and automatic. An arm whose preference is only slightly lower keeps a substantial probability; one far behind is nearly never taken. Nothing needs an $\varepsilon$ or a bonus term — the policy is already stochastic and sharpens itself as the preferences spread out.

The algorithm

On each step, take $A_t \sim \pi_t$, observe $R_t$, and update every arm:

$$H_{t+1}(a) \;=\; H_t(a) \;+\; \alpha \left(R_t - \bar{R}_t\right)\left(\mathbf{1}_{a = A_t} - \pi_t(a)\right)$$

where $\mathbf{1}_{a = A_t}$ is 1 for the arm actually taken and 0 otherwise, and $\bar{R}_t$ is the average of the rewards received before step $t$ — the baseline. Written out as the two cases:

$$\begin{aligned} H_{t+1}(A_t) &= H_t(A_t) + \alpha\left(R_t - \bar{R}_t\right)\left(1 - \pi_t(A_t)\right) && \text{the arm taken} \\[4pt] H_{t+1}(a) &= H_t(a) - \alpha\left(R_t - \bar{R}_t\right)\pi_t(a) && \text{for all } a \neq A_t \end{aligned}$$

Read it as a comparison against the average rather than a measurement. If the reward beat the baseline, the arm taken is made more likely and every other arm less likely; if it fell short, the arm taken is made less likely and everything else picks up the slack. The size of each rival’s demotion is proportional to how likely it already was, so probability mass is taken from where it currently sits.

Gradient bandit algorithm

Initialise, for $a = 1$ to $k$:   $H(a) \leftarrow 0$   (so $\pi$ starts uniform),   $\bar{R} \leftarrow 0$,   $n \leftarrow 0$

Loop forever:

$\quad \pi(a) \leftarrow \dfrac{e^{H(a)}}{\sum_b e^{H(b)}}$   for all $a$

$\quad A \sim \pi$   (sample, do not maximise)

$\quad R \leftarrow \mathrm{bandit}(A)$

$\quad H(a) \leftarrow H(a) + \alpha\,(R - \bar{R})\,(\mathbf{1}_{a=A} - \pi(a))$   for all $a$

$\quad n \leftarrow n + 1$;   $\bar{R} \leftarrow \bar{R} + \dfrac{1}{n}\left(R - \bar{R}\right)$   (baseline updated after the preferences)

The order of the last two lines is deliberate: the baseline used at step $t$ must not depend on which action was taken at step $t$. That is the condition under which the derivation below goes through, and it is easy to break by folding $R_t$ into $\bar{R}_t$ first.

A zero-sum update

Sum the update over all arms:

$$\sum_{a} \left(\mathbf{1}_{a = A_t} - \pi_t(a)\right) \;=\; \underbrace{1}_{\text{one indicator fires}} \;-\; \underbrace{\sum_a \pi_t(a)}_{=\,1} \;=\; 0$$

So $\sum_a H_{t+1}(a) = \sum_a H_t(a)$ exactly, on every step, for any reward. Starting from all zeros, the preferences always sum to zero: the algorithm never moves their mean, only their spread. This is the same fact as “only differences matter” seen from the update side, and it is the cheapest possible unit test — if the sum of your preferences drifts, the update is wrong.

Worked example

Three arms, $\alpha = 0.1$, all preferences starting at 0 so $\pi$ is uniform.

Step	$\bar{R}$	$A$	$R$	$R - \bar{R}$	$H$ after	$\pi$ after
1	0.00	2	1.0	$+1.0$	$(-0.033,\; 0.067,\; -0.033)$	$(0.322,\; 0.356,\; 0.322)$
2	1.00	2	−0.4	$-1.4$	$(0.012,\; -0.024,\; 0.012)$	$(0.337,\; 0.326,\; 0.337)$
3	0.30	3	0.6	$+0.3$	$(0.002,\; -0.033,\; 0.032)$	$(0.334,\; 0.322,\; 0.344)$

Step 1 rewards arm 2 for beating a baseline of zero. Step 2 punishes it: the reward was −0.4 against a baseline of 1.0, so the sign flips and arm 2 drops below the two arms that were not even tried. Step 3 promotes arm 3 for a reward of 0.6 that only just beat the baseline of 0.3, so the move is small. In every row the three preferences sum to zero.

Notice what the second row means. Arm 2 returned a reward of −0.4, and nothing in the algorithm knows whether that is good — it is judged entirely against what the run has been paying so far. That is the whole design.

Questions that make the update click

1. What is a preference, really?

$H_t(a)$ is a score used to rank actions, not an estimate of the reward from action $a$. Its absolute value has no meaning. What matters is the gap between two preferences, because softmax turns that gap into an odds ratio:

$$\frac{\pi_t(a)}{\pi_t(b)} = e^{H_t(a)-H_t(b)}$$

If $H_t(a)-H_t(b)=0$, the two actions are equally likely. If the gap is 1, action $a$ is $e\approx2.72$ times as likely as action $b$. This is why adding the same constant to every preference changes nothing.

2. If larger preference means a better action, why not choose the largest one?

Because choosing the largest preference would remove exploration. Gradient bandits learn a stochastic policy, so the softmax probabilities are the policy, not just an intermediate ranking. Sampling from them lets less-preferred actions continue to provide evidence. As the evidence accumulates, preference gaps usually grow and the policy becomes more decisive on its own.

3. What does the reward-minus-baseline term tell us?

It answers: was this reward better or worse than what I usually receive? This difference is often called an advantage:

• $R_t-\bar{R}_t>0$: the chosen action did better than usual, so make it more likely.
• $R_t-\bar{R}_t<0$: it did worse than usual, so make it less likely.
• $R_t-\bar{R}_t=0$: this observation gives no reason to change the policy.

A reward of 2 is therefore not inherently good. It is good when the baseline is 1 and bad when the baseline is 3.

4. Why are actions that were not selected updated too?

Softmax couples all the actions: increasing one action’s probability must reduce the probability available to the others. The factor $\mathbf{1}_{a=A_t}-\pi_t(a)$ implements that transfer. For a better-than-usual reward, the selected action moves up while every unselected action moves down; for a worse-than-usual reward, all the signs reverse.

Updating only the selected action would ignore this competition and would no longer be the gradient of the softmax policy.

5. Why does the selected action use the one-minus-probability factor?

The factor measures how much room its probability has to move. A rarely selected action has $\pi_t(A_t)\approx0$, so a surprising result produces a large update. An action already chosen with probability near 1 has $1-\pi_t(A_t)\approx0$, so one more expected success changes little.

For an unselected action, the factor is $-\pi_t(a)$. Likely competitors absorb more of the change than actions that already have almost no probability. These factors also make all preference changes sum to zero.

6. Does the baseline change which policy the algorithm is trying to learn?

No. Subtracting the same action-independent number from every possible reward leaves the expected gradient unchanged. It changes the variability of the one-sample update, not its average direction. A useful baseline removes the common reward level so that the update focuses on differences between actions.

The baseline must not use the current action or reward. That is why the preferences are updated with the old $\bar{R}_t$ before $R_t$ is folded into the running average.

7. How can every preference change if only one reward was observed?

The reward tells us directly about only the selected action, but it tells us how to redistribute a probability budget shared by all actions. The algorithm is not pretending that it observed the rewards of the other actions. It is applying the gradient of one log-probability, and that gradient has one component for every preference.

This is also why the update is noisy but valid: a single step is only a sample of the gradient; averaged over many sampled actions and rewards, it points in the true gradient direction.

8. What is the shortest way to remember the formula?

Remember three pieces:

$$\text{preference change} = \underbrace{\alpha}_{\text{how fast}} \underbrace{(R_t-\bar{R}_t)}_{\text{better or worse than usual}} \underbrace{(\mathbf{1}_{a=A_t}-\pi_t(a))}_{\text{redistribute probability}}$$

In words: move the policy toward a sampled action when it beats the baseline, and away from it when it falls short. The derivation below explains why this simple rule is an unbiased stochastic gradient rather than just a plausible heuristic.

Deriving the update

The claim is that this is not a heuristic: it is stochastic gradient ascent on expected reward, which is why it inherits the convergence guarantees of gradient ascent. Here is the derivation with every step justified, because each line uses a trick worth keeping.

The objective. With $q_*$ fixed and the policy determined by the preferences, the expected reward on step $t$ is

$$\mathbb{E}[R_t] \;=\; \sum_{x} \pi_t(x)\, q_*(x)$$

The sum runs over all arms $x$; $\pi_t(x)$ depends on every $H_t(a)$ through the softmax, which is why one arm’s preference affects the expected reward of the whole policy. Exact gradient ascent would be

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

but $\partial \mathbb{E}[R_t] / \partial H_t(a)$ contains $q_*$, which we do not know. The derivation’s job is to rewrite that derivative as the expectation of something we can compute from one sampled action and its reward.

Step 1 — differentiate the objective.

$$\frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)} \;=\; \frac{\partial}{\partial H_t(a)} \sum_{x} \pi_t(x)\, q_*(x) \;=\; \sum_{x} q_*(x)\, \frac{\partial \pi_t(x)}{\partial H_t(a)}$$

Why: $q_*(x)$ is a property of the environment, not of our preferences, so it is a constant with respect to $H_t(a)$ and comes straight out of the derivative. Only $\pi_t$ is differentiated.

Step 2 — subtract a baseline, for free.

$$\frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)} \;=\; \sum_{x} \left(q_*(x) - B_t\right) \frac{\partial \pi_t(x)}{\partial H_t(a)}$$

Why: the term we just added is $-B_t \sum_x \partial \pi_t(x) / \partial H_t(a)$, and that sum is zero:

$$\sum_{x} \frac{\partial \pi_t(x)}{\partial H_t(a)} \;=\; \frac{\partial}{\partial H_t(a)} \underbrace{\sum_{x} \pi_t(x)}_{=\,1} \;=\; \frac{\partial\, 1}{\partial H_t(a)} \;=\; 0$$

The probabilities always sum to one no matter what the preferences are, so the rates at which they change must cancel. The only requirement on $B_t$ is that it does not depend on $x$ — it may depend on $t$ and on everything that happened before step $t$, which is what makes the running average $\bar{R}_t$ a legal choice. Nothing has been approximated here: the gradient is identical with any such baseline. What the baseline changes is the variance of the sample we are about to take, and that is the entire subject of the next section.

Step 3 — turn the sum into an expectation. Multiply and divide each term by $\pi_t(x)$:

$$\frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)} \;=\; \sum_{x} \pi_t(x) \left(q_*(x) - B_t\right) \frac{\partial \pi_t(x) / \partial H_t(a)}{\pi_t(x)} \;=\; \mathbb{E}\!\left[\left(q_*(A_t) - B_t\right) \frac{\partial \pi_t(A_t) / \partial H_t(a)}{\pi_t(A_t)}\right]$$

Why: a sum of the form $\sum_x \pi_t(x) f(x)$ is the expectation of $f(A_t)$ when $A_t$ is drawn from $\pi_t$ — which is exactly how the algorithm chooses its action. This is the pivotal step of the whole derivation: it converts a quantity that needs all $k$ arms into one that can be estimated from the single arm we actually pull. (Dividing by $\pi_t(x)$ is safe because the softmax never assigns an arm probability zero.)

Step 4 — replace $q_*(A_t)$ with the observed reward.

$$\frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)} \;=\; \mathbb{E}\!\left[\left(R_t - \bar{R}_t\right) \frac{\partial \pi_t(A_t) / \partial H_t(a)}{\pi_t(A_t)}\right]$$

Why: by definition $\mathbb{E}[R_t \mid A_t] = q_*(A_t)$, so $R_t$ is an unbiased sample of the unknown $q_*(A_t)$ and may be substituted inside an expectation without changing it. This is the step that removes the last piece of unknown information from the formula, and it is also where the noise enters: $R_t$ is right on average and wrong on any particular step.

Step 5 — the softmax derivative. Write $S = \sum_b e^{H_t(b)}$, so $\pi_t(x) = e^{H_t(x)} / S$. By the quotient rule:

$$\begin{aligned} \frac{\partial \pi_t(x)}{\partial H_t(a)} &= \frac{\dfrac{\partial e^{H_t(x)}}{\partial H_t(a)} \cdot S \;-\; e^{H_t(x)} \cdot \dfrac{\partial S}{\partial H_t(a)}}{S^2} && \text{quotient rule} \\[8pt] &= \frac{\mathbf{1}_{a=x}\, e^{H_t(x)} S \;-\; e^{H_t(x)} e^{H_t(a)}}{S^2} && \begin{array}{l}\text{the numerator moves only if } a = x;\\ \text{in } S \text{ exactly one term contains } H_t(a)\end{array} \\[8pt] &= \mathbf{1}_{a=x} \frac{e^{H_t(x)}}{S} \;-\; \frac{e^{H_t(x)}}{S}\cdot\frac{e^{H_t(a)}}{S} && \text{split the fraction} \\[8pt] &= \pi_t(x)\left(\mathbf{1}_{a=x} - \pi_t(a)\right) && \text{by the definition of } \pi_t \end{aligned}$$

Why it looks the way it does: raising $H_t(a)$ raises $\pi_t(a)$ and lowers every other probability, because they must still sum to one. The $-\pi_t(x)\pi_t(a)$ term is that competition, and it is proportional to how much probability each arm currently holds.

Step 6 — substitute and cancel. Putting step 5 into step 4 with $x = A_t$:

$$\frac{\partial\, \mathbb{E}[R_t]}{\partial H_t(a)} \;=\; \mathbb{E}\!\left[\left(R_t - \bar{R}_t\right) \frac{\pi_t(A_t)\left(\mathbf{1}_{a = A_t} - \pi_t(a)\right)}{\pi_t(A_t)}\right] \;=\; \mathbb{E}\!\left[\left(R_t - \bar{R}_t\right)\left(\mathbf{1}_{a = A_t} - \pi_t(a)\right)\right]$$

Why this matters: the $1/\pi_t(A_t)$ that step 3 introduced is exactly cancelled by the $\pi_t(x)$ that the softmax derivative produces. That is a property of the softmax, not a coincidence of algebra, and it is why the final algorithm contains no division and does not explode when a rarely-taken arm happens to be sampled.

Step 7 — drop the expectation. Gradient ascent with the expectation replaced by the single sample just drawn is

$$H_{t+1}(a) \;=\; H_t(a) \;+\; \alpha \left(R_t - \bar{R}_t\right)\left(\mathbf{1}_{a = A_t} - \pi_t(a)\right)$$

which is the algorithm. Because the sampled quantity has the true gradient as its expectation, this is stochastic gradient ascent, and its convergence properties follow — with a decreasing step size it converges to a local optimum, which for the bandit problem is the global one.

What the baseline is for

The derivation says the baseline does not change the gradient at all. So why does it change the results so much?

Because the update is a single noisy sample of that gradient, and the baseline scales the noise. The multiplier on every arm’s update is $R_t - B_t$. Choose $B_t$ badly and that multiplier carries a large constant offset that says nothing about which arm is good:

• On a testbed with $q_*(a)$ around $+4$ and no baseline, $R_t - 0 \approx +4$ on every step, whatever was pulled. Every update therefore promotes the arm just taken, good or bad. The useful signal — the roughly $\pm 1$ variation between arms — is a fifth of the size of the meaningless common offset, so the preference gaps grow mostly by whichever arm was sampled most, a rich-get-richer effect that entrenches early accidents.
• With the running average as the baseline, $R_t - \bar{R}_t$ is centred on zero. Better than usual promotes, worse than usual demotes, and the common offset is gone.

Both versions are climbing the same gradient in expectation. One of them is reading it through four times as much noise.

Average performance on the 10-armed testbed

Two testbeds, identical except for where the arms are centred: $q_*(a) \sim \mathcal{N}(+4, 1)$ — the shifted version from Sutton and Barto’s figure 2.5 — and the standard $\mathcal{N}(0, 1)$. Rewards $R_t \sim \mathcal{N}(q_*(A_t), 1)$, $H_1(a) = 0$, 2000 runs of 1000 steps.

Every figure here comes from experiments/gradient-bandit.mjs in this repository; it is seeded and dependency-free, so node experiments/gradient-bandit.mjs reprints the tables exactly.

Percent optimal action on the shifted testbed (q* around +4), 2000 runs. Without a baseline every reward is positive, so every update promotes whatever was just tried.

Step	$\alpha=0.1$, baseline	$\alpha=0.4$, baseline	$\alpha=0.1$, none	$\alpha=0.4$, none
10	11.3	19.9	12.5	17.4
50	26.6	46.5	23.6	22.7
100	47.3	54.9	34.3	24.1
200	68.3	59.9	41.8	25.8
500	80.2	63.9	48.0	27.7
1000	83.4	66.0	50.8	27.9

Removing the baseline costs 33 percentage points at $\alpha = 0.1$ and 38 at $\alpha = 0.4$, and the larger step size makes things worse rather than better without one — it entrenches the early accidents faster. The average preference gap between the optimal arm and the mean tells the same story from inside the algorithm: 5.58 with the baseline against 3.32 without, at $\alpha = 0.1$.

Now the same four settings on the standard testbed, where the rewards are already centred near zero:

The same four settings with the arms centred at zero. The dashed no-baseline curves lie on top of the solid ones: the baseline was only ever removing the offset.

Step	$\alpha=0.1$, baseline	$\alpha=0.4$, baseline	$\alpha=0.1$, none	$\alpha=0.4$, none
100	48.0	61.0	48.4	61.7
500	80.5	69.8	80.5	68.8
1000	84.5	71.7	84.0	70.0

The curves collapse into two pairs — half a point apart at $\alpha = 0.1$, under two at $\alpha = 0.4$, against gaps of 33 and 38 on the shifted testbed. That is the cleanest statement of what it does: it is not a general accelerator, it is the term that makes the method indifferent to a constant added to every reward. Without it, the algorithm’s behaviour depends on where zero happens to sit — which is an arbitrary fact about how the problem was written down, and should not affect anything.

The step size shows the familiar horizon trade-off, unchanged by any of this: $\alpha = 0.4$ leads for the first 133 steps and then plateaus lower, because large steps sharpen the policy before the evidence justifies it and the resulting near-deterministic $\pi$ stops collecting evidence about the arms it has written off.

What is wrong with it

It learns no values. Preferences are only comparable within one problem, and there is nothing to inspect afterwards: the algorithm cannot tell you what an arm is worth, only that it prefers it. Every value-based method leaves behind an estimate that is useful on its own.

The policy can sharpen prematurely. Nothing forces continued exploration. If early noise pushes one preference far ahead, $\pi$ becomes nearly deterministic and the updates to the neglected arms shrink to almost nothing — visible above as the $\alpha = 0.4$ plateau.

It is sensitive to reward scale, not just offset. The baseline removes a constant, but multiplying every reward by 100 multiplies the effective step size by 100. $\alpha$ must be tuned for the scale of $R_t - \bar{R}_t$.

The baseline is a running average of everything. On a nonstationary problem the average over the whole history is the wrong reference point, and a constant step-size average of recent rewards is a better one — the same argument as tracking a nonstationary problem.

Common mistakes

Updating only the arm that was taken. The other $k-1$ preferences move on every step. Skipping them breaks the zero-sum property, and the policy drifts toward whatever is sampled most.

Letting the baseline see the current action. Folding $R_t$ into $\bar{R}_t$ before the preference update makes $B_t$ a function of $A_t$, which is exactly the assumption step 2 needs. The bias is small but the derivation no longer applies, and it is free to avoid.

Taking $\arg\max_a \pi_t(a)$ instead of sampling. The method is a stochastic policy; the exploration is the sampling. Acting greedily on $\pi$ turns it into a worse value method with no exploration at all.

Exponentiating raw preferences. $e^{H}$ overflows once preferences reach a few hundred. Subtract $\max_b H_t(b)$ from every preference before exponentiating — it cancels exactly, by the same argument that says only differences matter.

Reading $H$ as a value. $H_t(a) = 3$ says nothing about reward. Only $H_t(a) - H_t(b)$ has meaning, and only through the softmax.

Personal takeaways

The gradient bandit is the first method here that does not pretend to be estimating anything. It optimises the policy directly, and the derivation is the reason to care: seven lines take “maximise expected reward” to an update rule that uses one sampled action, with no unknown quantities left in it, and every step is a legitimate equality rather than an approximation. The one place a sample replaces an expectation is step 7, and that is what makes it stochastic gradient ascent.

The baseline result is the part I expect to keep re-using. It is a term that provably does not change what is being optimised and dramatically changes how fast you get there, purely by removing a common offset from a noisy estimate. Subtracting a baseline is the standard variance-reduction move in policy gradient methods for exactly this reason, and this chapter is where it is small enough to verify by hand.

The connection to chapter 11 is direct. Replace “arm” with “state–action pair” and $\bar{R}_t$ with a learned value function, and this update is REINFORCE with a baseline. The softmax over preferences becomes a softmax policy over actions, and step 3 — turning a sum over all actions into an expectation over the action taken — becomes the policy gradient theorem.

Where next

That closes the bandit chapter: four exploration strategies, all of them operating on a problem with no state, no transitions and no delay. The next chapter puts all three back: Markov decision processes.

References

• Sutton, R. S. & Barto, A. G. Reinforcement Learning: An Introduction, 2nd ed., §2.8 and figure 2.5.
• Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning 8, 229–256.