Stochastic Approximation in Reinforcement Learning

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.

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.

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.

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.

From Function Examples to Generalization

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.

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

• Treating one observed reward as the complete performance gradient.

  A sampled reward provides one stochastic contribution. It does not provide the complete set of true action values.

  Fix: View the update as a sample whose expected value connects to the exact gradient-ascent direction.

• Assuming exact gradient ascent can be applied directly when true action values are unknown.

  The true action values q*(b) are not known in the setting described.

  Fix: Use the selected action and observed reward to construct a sampled update.

• Describing the gradient bandit algorithm as only a probability-assignment method.

  The algorithm adjusts preferences so that the resulting action probabilities improve expected reward.

  Fix: Trace the relationship from preferences to probabilities to expected reward.

• Equating the desired function with the approximation.

  The desired function, available examples, and constructed approximation are distinct parts of the process.

  Fix: Identify which object is the target, which information consists of examples, and which representation is built from them.

• Assuming reinforcement learning must create a completely new generalization method.

  Function approximation connects reinforcement learning with existing work on generalization.

  Fix: 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

The Complete Picture

1. Gradient ascent treats expected reward as the performance objective and adjusts preferences in a direction intended to improve it.
2. Exact gradient ascent requires true action values, but those values are unknown in the gradient bandit setting.
3. A selected action and its observed reward provide a sampled performance-gradient contribution, with the average reward and an action indicator also involved in the update.
4. Because the expected reward conditioned on the selected action equals its true action value, the expected value of sampled updates matches the exact gradient-ascent direction.
5. Function approximation constructs a broader representation of a desired function from available examples and connects reinforcement learning with supervised-learning methods for generalization.