Gradient Bandit Algorithms for Action Selection

The gradient bandit algorithm can be understood as a stochastic approximation to gradient ascent.

Programming

The Optimization Target

A gradient bandit algorithm is a stochastic approximation to gradient ascent. Its objective is expected reward: the algorithm adjusts internal action preferences in a direction that should improve the expected reward obtained from the resulting action probabilities.

The word gradient describes a direction of improvement. If the algorithm could calculate the exact performance gradient, it could move preferences in the direction that increases expected reward. In the bandit setting, however, the true expected reward of every action is unknown. The algorithm therefore uses information from the action selected on the current step and the reward observed for that action.

How do action preferences determine soft-max probabilities, and how do those probabilities combine with action rewards to determine expected reward and its gradient?

From Preferences to Selection

The selection process moves from action preferences to a soft-max distribution and then to a probabilistic action choice. Soft-max gives more likely selection to actions with stronger preferences. Unlike an all-or-nothing decision, it preserves probabilistic exploration: a less-preferred action is not automatically eliminated from consideration.

How does changing the relative preferences of actions change their selection probabilities, producing graded rather than all-or-nothing exploration?

A Preference Change Without Forced Selection

Suppose action A has a stronger preference than action B. The preference for A then increases relative to B.

Start with preferences: The actions have different preferences, so soft-max assigns them different selection probabilities.

Change the relative preference: Increasing A's preference makes A more likely under the soft-max distribution.

Preserve probabilistic exploration: The selection process remains probabilistic rather than becoming a simple all-or-nothing choice. The less-preferred action can still retain a probability of selection.

A becomes more likely, but the preference-based distribution still supports probabilistic exploration.

Exact and Sampled Gradients

Exact gradient ascent would require the complete performance gradient. In this setting, that gradient depends on the true expected reward of every action, written in the source as q*(b). Those true action values are unknown, so the algorithm cannot directly calculate the exact gradient from complete knowledge of all actions.

The gradient bandit method replaces unavailable complete information with a sample. It selects an action A_t, observes its reward R_t, and uses the observed reward together with the average reward baseline R̄_t. An indicator identifies whether the preference under consideration belongs to the selected action. This sampled contribution is not necessarily the exact gradient on one step, but it provides stochastic information about the performance gradient.

How does the exact expected gradient compare with the update produced from one sampled action and reward, and why do the stochastic updates match the exact update in expectation?

The equivalence is an expected-value statement. Conditioned on selecting action A_t, the expected observed reward satisfies E[R_t | A_t] = q*(A_t). Therefore, when the sampled updates are averaged over the random selected action and its reward, they provide the same gradient direction as the exact performance-gradient expression. The algorithm can learn the correct direction without knowing every q*(b) explicitly.

One Reward Across All Preferences

A single sampled reward affects the preference update for every action, not only the selected action. The selected action is identified by the indicator in the sampled gradient contribution. The difference between the observed reward R_t and the average reward R̄_t acts as the reward prediction error used by the update.

How does one selected action, its sampled reward, the average reward baseline, and the resulting reward prediction error change each action's preference?

Interpreting an Above-Baseline Reward

An action is selected and its observed reward is above the current average reward baseline.

Identify the sampled information: The update uses the selected action A_t, its observed reward R_t, and the average reward R̄_t.

Compare reward with baseline: Because the observed reward is above the average baseline, the reward prediction error is positive.

Update the selected preference: The selected action receives an increase in preference because the observed outcome was better than the baseline.

Update the other preferences: The non-selected actions receive the corresponding contrasting part of the gradient update, so the update is distributed across the action preferences rather than being limited to one isolated estimate.

An above-baseline sampled reward shifts the preference distribution toward the selected action while the update remains a gradient-based change over all actions.

After one action is sampled, which preferences increase, which decrease, and how does the update depend on whether the reward is above or below the baseline?

Exploration Method Comparison

Gradient bandits, ε-greedy methods, and UCB methods all balance exploration and exploitation differently. ε-greedy occasionally chooses randomly. UCB chooses deterministically, while giving some advantage to actions that have received fewer samples. Gradient bandits use action preferences to form a probability distribution, so exploration comes from the soft-max probabilities.

Method	Internal basis for choice	Exploration behavior
ε-greedy	Action-value estimates	Occasional random choice
UCB	Action-value information and sample counts	Deterministic choice with an advantage for less-sampled actions
Gradient bandit	Action preferences	Soft-max probability distribution with graded probabilistic exploration

How do ε-greedy, UCB, and gradient bandit methods distribute action-selection probability over time, and what information drives their exploration decisions?

Common Reasoning Errors

Treating a preference as the action's true expected reward
Gradient bandit algorithms use preferences as internal estimates for forming action probabilities. The source distinguishes these preferences from the unavailable true action values q*(b).
Fix: Interpret preferences as quantities that determine the soft-max distribution, not as directly known true rewards.
Calling one sampled update the exact gradient
The exact gradient requires complete information about the true expected reward of every action. A single sampled update is a stochastic contribution.
Fix: Say that the sampled update estimates the gradient contribution and matches the exact gradient in expected value over repeated sampling.
Describing gradient bandit exploration as occasional random selection
ε-greedy explores through occasional random choices, whereas gradient bandits explore through a soft-max distribution created from preferences.
Fix: Describe gradient bandit exploration as graded probabilistic selection.
Updating only the selected action's preference
The sampled contribution uses an indicator for the selected action but forms an update over the action preferences.
Fix: Trace the selected and non-selected preference components together, using the reward relative to the average reward baseline.

Practice the Update Logic

MEDIUM

An action is selected, and its observed reward is below the current average reward baseline. Explain what happens conceptually to the selected action's preference, what role the non-selected preferences play, and why the resulting update is considered stochastic gradient ascent rather than exact gradient ascent.

Hints

Compare the observed reward with the average reward baseline.
Use the distinction between selected and non-selected action components in the sampled gradient contribution.
Remember that exact gradient ascent would require the unknown true action values for all actions.

Your attempt (not saved)

What do you think happens?

If a selected action receives a reward above the average reward baseline, which direction should the selected action's preference move?

It should increase
It should decrease
It should remain unrelated to the reward

Reveal answer

Answer: It should increase.

An above-baseline reward produces a positive reward prediction error, so the sampled preference update shifts toward the selected action while the corresponding update is also applied across the other action preferences.

A Compact Mental Model

Maintain action preferences rather than directly relying on known true action values.
Convert preferences into a soft-max probability distribution.
Select an action according to that distribution and observe its reward.
Compare the observed reward with the average reward baseline.
Use the sampled reward and selected-action indicator to update the preferences.
Rely on the expected value of repeated sampled updates to match the exact performance-gradient direction.

The central idea is that gradient bandits improve action selection indirectly. They do not need the true expected reward of every action. They maintain preferences, turn those preferences into graded soft-max probabilities, and use sampled rewards to move the preferences in a direction that improves expected reward in expectation.

Key Takeaways

Gradient bandit algorithms are stochastic approximations to gradient ascent on expected reward.
They use action preferences to create a soft-max probability distribution rather than directly selecting from known action values.
Exact gradient ascent is unavailable because the true expected rewards of all actions are unknown.
A sampled action, observed reward, average reward baseline, and selected-action indicator provide a stochastic performance-gradient contribution.
ε-greedy explores through occasional random choices, UCB through deterministic preference for less-sampled actions, and gradient bandits through graded probabilities from soft-max preferences.