Expected Reward in Multi-Armed Bandits

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

Programming

The Learning Target

A gradient bandit algorithm is trying to improve one performance measure: expected reward. It does this indirectly. Rather than only assigning probabilities to actions, it adjusts action preferences so that the resulting probabilities move toward better performance.

Gradient ascent means moving internal preferences in a direction that increases the performance objective. In this setting, the objective is expected reward. If a preference change makes high-reward actions more likely and improves expected reward, the change points in a useful ascent direction.

What changes in the policy when preferences are adjusted in a direction that improves expected reward?

One Sampled Learning Step

A gradient bandit step starts with a selected action. The algorithm observes the reward produced on that step and uses the observed reward together with the average reward baseline. An indicator identifies whether the preference under consideration belongs to the selected action. This information forms a sampled contribution to the performance gradient.

How does the selected action, its sampled reward, and the average reward baseline flow through one gradient bandit learning step?

Tracing a Reward Relative to the Baseline

Trace the information used when one action is selected and produces an observed reward.

Select: The algorithm selects an action A_t. The selected action determines which preference is directly identified by the action indicator.

Observe: The algorithm observes the current reward R_t from that selected action.

Compare: The observed reward is considered together with the average reward R̄_t, which provides the reward baseline for the sampled contribution.

Update: The resulting sampled performance-gradient contribution is used to adjust preferences. The update is based on available sampled information rather than the unknown true values of every action.

One sampled reward supplies the information needed for a stochastic preference update, while repeated updates provide the stochastic approximation to gradient ascent.

Preferences, Probabilities, and Performance

The performance gradient connects three layers. First, action preferences determine the probabilities of selecting actions. Second, those probabilities determine how often the different action outcomes contribute to performance. Third, the action probabilities combine with the actions' expected rewards to produce the overall expected reward. Gradient ascent acts on the preferences because changing them changes the probabilities and therefore changes expected reward.

How do preferences determine probabilities, and how do those probabilities combine with action values to determine expected reward and its gradient?

Exact and Sampled Ascent

Exact gradient ascent	Stochastic gradient ascent
Uses the complete set of true action values.	Uses the selected action and its observed reward.
Requires knowledge that the gradient bandit setting does not provide.	Can be constructed from information available on the current step.
Provides the exact performance-gradient direction.	Provides a sample of that direction.
Cannot be implemented directly because the true action values are unknown.	Repeated sampled updates match the exact direction in expected value.

Exact gradient ascent would calculate the performance gradient from complete knowledge of every action's expected reward. The gradient bandit algorithm cannot do that because the true action values are unknown. Instead, it samples an action, observes its reward, and builds an update from that observation.

The sampled update is not merely an unrelated approximation. The performance gradient can be written as an expectation over the random selected action. For the selected action, the conditional expected observed reward equals that action's true expected reward: E[R_t | A_t] = q*(A_t). Consequently, averaging the sampled reward-based contributions over repeated selections produces the exact performance-gradient direction.

What information does the exact update use compared with the single sampled reward used by the stochastic gradient bandit update?

How do updates from different possible sampled actions average out to the exact performance gradient?

Reading the Update Correctly

Treating the algorithm as if it knew every true action value.
The true action values are unknown, which is why exact gradient ascent cannot be implemented directly.
Fix: Describe the actual update in terms of the selected action, the observed reward, and the average reward baseline.
Calling one sampled update the exact performance gradient.
One update is a sample of the performance gradient.
Fix: State that repeated sampled updates match the exact gradient-ascent direction in expected value.
Describing gradient bandits as only probability assignment.
The algorithm adjusts preferences so that the resulting probabilities improve expected reward.
Fix: Keep the chain visible: preferences determine probabilities, probabilities affect expected reward, and the performance gradient guides preference adjustment.
Ignoring the selected-action indicator.
The sampled contribution uses an indicator to identify whether the preference being considered belongs to the selected action.
Fix: Include the selected action and its indicator when tracing the sampled update.

When explaining a gradient bandit update, separate three claims: what the exact gradient would require, what one sampled step can observe, and why the expected value of repeated sampled steps equals the exact direction.

Check Your Reasoning

MEDIUM

Explain, in your own words, why a gradient bandit algorithm uses a sampled reward instead of calculating the exact performance gradient.

Hints

Start with what is unknown about the action values.
Name the information available after an action is selected.
Finish by explaining what repeated sampled updates match in expected value.

Your attempt (not saved)

EASY

Trace one learning step using these terms: selected action, observed reward, average reward baseline, action indicator, sampled gradient contribution, and preference update. Do not claim that the algorithm knows the true values of all actions.