Stochastic Approximation in Reinforcement Learning

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

Programming

One Reward, Many Preferences

A gradient bandit algorithm does not merely assign probabilities to actions. It adjusts action preferences so that the resulting probabilities improve performance. Its performance objective is expected reward. The central difficulty is that the true expected reward of every action is unknown, so the algorithm must use information from the action selected and the reward observed on the current step.

How do preference changes alter action probabilities, and how do those probability changes alter expected reward?

The useful mental model is a chain: preferences influence action probabilities, action probabilities influence which rewards are experienced, and those choices determine expected reward. Gradient ascent tries to move the preferences in a direction that improves the expected reward.

Following an Exact Gradient Step

Gradient ascent is an adjustment procedure for maximizing an objective. Here, the objective is expected reward. An exact gradient-ascent update would use the performance gradient: the direction in preference space that increases expected reward. The gradient connects three ingredients: the probabilities assigned to actions, the preferences that produce those probabilities, and the true expected rewards of the actions.

What changes after each gradient-ascent step, and how does the update direction increase expected reward?

The gradient bandit algorithm addresses this limitation by replacing unavailable complete information with a sampled performance-gradient contribution. It selects an action, observes its reward, and uses that experience to construct an update.

Tracing a Sampled Update

On a particular step, the update uses the selected action A_t, the observed reward R_t, the average reward R̄_t, and an indicator showing whether the preference under consideration belongs to the selected action. The selected action and observed reward provide the current sample. The average reward supplies the comparison level used by the sampled contribution.

How does the selected action, observed reward, baseline, and action probability combine to change each action's preference?

Worked example

One Sampled Preference Update

Consider one step on which the algorithm selects an action, observes its reward, and compares that reward with the current average reward.

1
Select
The algorithm identifies the action A_t selected on the current step.
2
Observe
It records the reward R_t produced by that selected action.
3
Compare
It uses the average reward R̄_t as the comparison level in the sampled performance-gradient contribution.
4
Identify
An indicator identifies whether the preference being considered belongs to the selected action.
5
Update
These available quantities form a sampled gradient contribution, which is used to adjust preferences rather than relying on the unavailable true action values for every action.

Result

The single observed reward does not reveal the complete performance gradient. It supplies one stochastic contribution whose expected value participates in the exact gradient-ascent direction.

The key point is not that one reward equals the full gradient. It does not. The key point is that the reward provides a valid sample of the information needed for the update. Repeated sampled updates are connected to the exact gradient through their expected value.

Why Stochastic Updates Match

The performance gradient can be rewritten as an expectation over the random action A_t. The unknown true value q*(A_t) can be replaced inside this expectation by the observed reward because the expected reward conditioned on the selected action satisfies E[R_t | A_t] = q*(A_t). Therefore, sampling an action and observing its reward provides the stochastic information needed for the update.

How does the expected update from many sampled rewards match the exact gradient-ascent update?

Update approach	Information used	Relationship to the performance gradient
Exact gradient ascent	The true action values for the actions	Directly calculates the exact direction
Stochastic gradient ascent	The selected action and its observed reward	Provides a sample whose expected value matches the exact direction

The distinction is between complete unavailable information and sampled available information.

From Function Examples to Generalization

Definition

Function approximation uses examples to construct a broader representation of a desired function. In reinforcement learning, the desired function can be a value function. The learner may have examples from that function without having a complete description of the function itself.

How do observed input-output examples become parameters of an approximation to an unknown desired function?

The examples, the desired function, and the approximation are different things. The desired function is the function the learner is trying to represent. The examples are the evidence available from that function. The approximation is the generalized representation constructed from those examples. The purpose is not simply to store the examples; it is to generalize from them.

What is the difference between the target function, available examples, and the approximation learned from those examples?

Function approximation is an instance of supervised learning. Supervised learning is also studied in artificial neural networks, pattern recognition, and statistical curve fitting. This relationship matters because reinforcement learning can combine its own methods with generalization methods already studied in those fields.

Common Reasoning Errors

Common mistake
Treating one observed reward as the complete performance gradient.
What it looks like
The algorithm selects one action and observes one reward, so the learner assumes it now knows the exact direction for every preference.
Why it fails
A sampled reward provides one stochastic contribution. It does not provide the complete set of true action values.
Do this instead
View the update as a sample whose expected value connects to the exact gradient-ascent direction.
Common mistake
Assuming exact gradient ascent can be applied directly when true action values are unknown.
What it looks like
The learner attempts to calculate the exact performance gradient without complete knowledge of every action's expected reward.
Why it fails
The true action values q*(b) are not known in the setting described.
Do this instead
Use the selected action and observed reward to construct a sampled update.
Common mistake
Describing the gradient bandit algorithm as only a probability-assignment method.
What it looks like
The learner focuses on the action probabilities but ignores the preferences that are adjusted to produce them.
Why it fails
The algorithm adjusts preferences so that the resulting action probabilities improve expected reward.
Do this instead
Trace the relationship from preferences to probabilities to expected reward.
Common mistake
Equating the desired function with the approximation.
What it looks like
The learner calls the representation built from examples the complete desired function.
Why it fails
The desired function, available examples, and constructed approximation are distinct parts of the process.
Do this instead
Identify which object is the target, which information consists of examples, and which representation is built from them.
Common mistake
Assuming reinforcement learning must create a completely new generalization method.
What it looks like
The learner ignores methods from supervised learning, artificial neural networks, pattern recognition, and statistical curve fitting.
Why it fails
Function approximation connects reinforcement learning with existing work on generalization.
Do this instead
Recognize that methods from related fields can take the role of a function approximator, although they may not all fit equally conveniently into reinforcement learning algorithms.

Apply the Two Connections

MEDIUM

Explain the following process in your own words: a gradient bandit selects an action, observes a reward, compares that reward with the average reward, and changes preferences. Then explain why repeated updates can have the same direction in expectation as exact gradient ascent even though the true action values are unknown.

Hints

Name the performance objective first.
Separate one sampled contribution from the full performance gradient.
Use the conditional expected-reward relationship to explain the equivalence.
Mention the indicator for whether a preference belongs to the selected action.

Your attempt (not saved)

EASY

A reinforcement-learning system has examples from a desired value function but does not have a complete description of that function. Identify the desired function, the examples, and the approximation in this situation. Finally, explain why supervised-learning methods may be relevant.