Skip to content
AI360XpertBeta

Gradient Bandits

Gradient bandits skip estimating payouts and instead tune a preference score per action, raising the odds of whatever beats the recent average reward.

Gradient bandits turn preferences into softmax probabilities, then push the chosen action up or down based on whether its reward beat the running average
Gradient bandits turn preferences into softmax probabilities, then push the chosen action up or down based on whether its reward beat the running average

Why Does This Exist?

Most bandit methods are action value methods. They estimate the payout of each arm, then mostly pick the current winner. That works, but it spends effort learning exact numbers nobody needs. If arm one pays about 102 on average and arm two pays about 100, you only need to know that arm one is better, not the numbers 102 and 100.

There is a second problem. Picking by argmax plus random exploration is jumpy, and it teaches nothing about how to adjust a policy smoothly. Gradient bandits fix both at once. Each action gets a preference score with no units, the scores become probabilities through a softmax, and one gradient step per pull moves probability toward whatever beats the average. It is the smallest possible version of what policy gradient later does with states, and the natural next step after epsilon-greedy.

The one idea you need first

A softmax turns arbitrary scores into probabilities by exponentiating and normalizing. With preferences 0.2 and minus 0.2, the weights are about 1.2214 and 0.8187, summing to 2.0401, so the probabilities are 0.5987 and 0.4013. Adding the same constant to every preference changes nothing, because the constant factors out of every term.

Think of It Like This

A food truck testing two spots

You run a food truck and alternate between two corners. You do not try to predict exact daily revenue at each corner. Instead you keep a score per corner and let the scores decide how often you visit each one.

After each day you compare revenue against your running average across both corners. Beat the average and that corner earns more future visits, while the other corner quietly loses share since the visits must add to 100 percent. A good day at a weak corner still counts as a failure if it lands below your average, and that is the point. You learn from relative performance, not absolute coins.

Where it stops: your corners have slow seasons and regulars, so payouts drift. The basic gradient bandit assumes each arm pays from a fixed distribution, with no states and no seasons.

How It Actually Works

Each action a holds a preference H(a). Action probabilities come from the softmax, where pi(a) is the chance of pulling a:

πt(a)=eHt(a)∑beHt(b)\pi_t(a) = \frac{e^{H_t(a)}}{\sum_b e^{H_t(b)}}

The goal is expected reward, which is each arm's true mean q(a) weighted by how often it is pulled:

E[Rt]=∑xπt(x) q(x)\mathbb{E}[R_t] = \sum_x \pi_t(x) \, q(x)

Differentiating with respect to one preference gives the gradient direction. Subtracting any baseline B that ignores the action leaves the expectation unchanged, because probabilities sum to one and the derivative of one is zero. Sampling one pull turns the expectation into the update used in practice, with step size alpha, chosen action A, reward R, and running average baseline Rbar:

Ht+1(a)=Ht(a)+α (Rt−Rˉt) (1a=At−πt(a))H_{t+1}(a) = H_t(a) + \alpha \, (R_t - \bar{R}_t) \, (1_{a = A_t} - \pi_t(a))

In plain words: the chosen arm moves up when its reward beats the average and down when it misses, scaled by how surprising the pick was. Every other arm moves the opposite way, scaled by its own probability, which keeps the probabilities summing to one. The baseline changes nothing on average but shrinks the noise, so learning is calmer.

Worked example

Two arms, step size alpha = 0.20, baseline starting at Rbar = 4.00, preferences at zero, so both probabilities sit at 0.5000.

Round one pulls arm one and earns R = 6.00. The advantage is 6.00 - 4.00 = +2.00. The chosen arm gains 0.20 * 2.00 * (1 - 0.5000) = +0.2000 while the other loses 0.20 * 2.00 * 0.5000 = 0.2000. Preferences become [+0.2000, -0.2000], the baseline moves to 5.00, and the weights e^{+0.20} = 1.2214 and e^{-0.20} = 0.8187 sum to 2.0401, giving probabilities 0.5987 and 0.4013.

Round two pulls arm two and earns R = 2.00. Against the new baseline of 5.00 the advantage is 2.00 - 5.00 = -3.00, negative even though the reward itself is positive. The chosen arm moves by 0.20 * (-3.00) * (1 - 0.4013) = -0.3592 while arm one gains +0.3592. Preferences land at [+0.5592, -0.5592], the weights 1.7493 and 0.5717 sum to 2.3210, and arm one's probability climbs to 0.7537, which is 75.37 percent.

Code

This snippet replays round one of the worked example with plain Python, so you can check the 0.5987 and 0.4013 probabilities yourself.

import math

def softmax(prefs: list[float]) -> list[float]:    top = [math.exp(h) for h in prefs]    total = sum(top)    return [t / total for t in top]

def update(prefs: list[float], action: int, reward: float, baseline: float, alpha: float) -> list[float]:    probs = softmax(prefs)    advantage = reward - baseline    return [h + alpha * advantage * ((1.0 if i == action else 0.0) - p) for i, (h, p) in enumerate(zip(prefs, probs))]

prefs = [0.0, 0.0]print([f"{p:.4f}" for p in softmax(prefs)])  # -> ['0.5000', '0.5000']prefs = update(prefs, action=0, reward=6.0, baseline=4.0, alpha=0.2)print([f"{h:.4f}" for h in prefs])  # -> ['0.2000', '-0.2000']print([f"{p:.4f}" for p in softmax(prefs)])  # -> ['0.5987', '0.4013']

The prints match the hand computation: preferences [+0.20, -0.20] and probabilities [0.5987, 0.4013].

Watch Out For

Dropping the baseline in positive reward tasks

Skipping the baseline looks harmless because it leaves the expected gradient unchanged. In practice, when every payout is positive, each pull pushes its arm up and weak arms only fade through the normalizer. Learning crawls and early luck can lock in a bad arm for hundreds of pulls.

Symptom: all preferences drift upward together while probabilities barely separate. Fix: always track the running average Rbar and update with R - Rbar, so below average pulls actively lose preference.

Setting the step size so high the policy snaps shut

A large alpha feels like faster learning until one good pull slams an arm near probability one. With no more exploration, the agent never tests the alternatives that would have corrected it.

Symptom: one probability jumps past 0.95 within a few pulls and never comes back. Fix: start near 0.1, watch the probability spread for the first fifty pulls, and only raise alpha while every arm keeps getting sampled.

The Quick Version

  • Gradient bandits learn preferences per action, not payout estimates, and pick actions through a softmax.
  • The update rewards arms that beat the running average baseline and punishes arms that miss it, even when the reward is positive.
  • The baseline keeps the gradient unbiased while cutting its variance, which is most of why the method converges quickly.
  • Two pulls moved arm one from 50.0 percent to 59.87 percent and then 75.37 percent in the worked example.
  • Keep the step size modest and never drop the baseline, or one lucky pull can freeze the policy early.
  • This is the single state version of policy gradients, so read policy gradient next, and compare with multi-armed bandits for the value based view.

What to Read Next