Concepts / Gradient MC

Gradient MC

SGD variations are used to find a good weight vector for function approximation.

  • Programming

From Experience to Better Predictions

When a value function is represented with function approximation, learning means finding a good weight vector. A single experience does not usually reveal the perfect weight vector immediately, so learning uses successive updates based on sampled experience. Variations of stochastic gradient descent provide a way to make those successive adjustments.

Gradient MC is best understood as one endpoint in a family of n-step semi-gradient TD methods. At one endpoint, the update uses a one-step target, which gives semi-gradient TD(0). At the other endpoint, the update uses the complete sampled return, which gives gradient MC. Between these endpoints, n-step methods combine observed rewards with a later estimated value.

producescompared with predictiondrives updateSampled episodeexperienceSampled returnlearning targetPrediction errortarget versus predictionWeight vectorupdated parameters
How does a sampled episode return move through the prediction error and change the approximator's weight vector?

Tracing the Gradient MC Update

A qualitative Gradient MC trace

Suppose a fixed policy generates a complete sampled episode. The approximator already predicts a value for the episode's starting state, and the completed episode supplies a sampled return.

Start with a prediction: The current weight vector produces a prediction for the starting state.

Observe the complete return: Because the episode has been sampled to completion, its return can be used as the learning target for the starting state's prediction.

Measure the mismatch: The sampled return and the current prediction determine a prediction error.

Adjust the weights: A stochastic-gradient-descent-style update changes the weight vector so the approximator moves toward a better prediction for the sampled experience.

Gradient MC uses a complete sampled return as the target and updates the weight vector from the resulting prediction error.

Why n-Step TD Fits the Fixed-Policy Case

In the on-policy setting with a fixed policy, the learning process follows the same policy whose values are being learned. This makes n-step semi-gradient TD a natural algorithmic choice: it can use sampled rewards from the current experience and, after n steps, connect the current state's prediction to a later state's estimated value.

The size of n controls how far the update looks into the sampled experience. A one-step method uses the one-step form of the target. A larger n includes more sampled rewards before using a later value estimate. At the complete-return endpoint, no later estimated value is needed because the sampled episode return supplies the target.

follow experiencecontinue for n stepsreachcombine withbootstrap fromCurrent stateprediction being updatedSampled rewardstep 1Sampled rewardsthrough step nLater stateestimated valuen-step targetrewards plus later estimate
What information is included in an n-step target, and how does it connect the current state to a later state's estimated value?

The n-Step Family

increase nextend to complete returnSemi-gradient TD(0)one-step targetn-step semi-gradientTDrewards plus later estimateGradient MCcomplete sampled return
How do the targets change as n increases, and where do TD(0) and gradient MC appear as the endpoints?
MethodPosition in the familyTarget description
Semi-gradient TD(0)One-step special caseUses the one-step target
n-step semi-gradient TDIntermediate casesUses sampled rewards and a later estimated value
Gradient MCInfinity-step special caseUses the complete sampled return

The methods differ by how much sampled experience is used before forming the target.

This family view prevents two common errors. First, gradient MC and semi-gradient TD(0) are not unrelated methods: they are special cases of n-step semi-gradient TD. Second, increasing n does not merely rename the same update. It changes the target by changing how much sampled experience is incorporated before the later estimate, or complete return, is used.

Why Semi-Gradient Is Not Full Gradient

A true gradient method would include every relevant dependence on the weight vector when computing the gradient of its objective. Semi-gradient TD does not do that. Its target uses a weight vector, but the dependence of that target on the weight vector is ignored when the gradient is computed.

accounts for dependenceuses target but treats its dependence as fixedaffectsTrue gradientmethodincludes target dependenceTD targetcontains a weight-basedestimateSemi-gradient TDignores target dependenceComputed gradientdifferent treatment
Which parts of the TD target are treated as fixed during the update, and why does that differ from taking the gradient of the full objective?

Mistakes in Classifying the Methods

  • Treating every method in the family as a true gradient method

    Semi-gradient TD uses a weight vector in its update target, but ignores the target's dependence on that weight vector when computing the gradient.

    Fix: Reserve the true-gradient label for a method whose gradient includes the relevant target dependence. Call the TD methods semi-gradient when that dependence is ignored.

  • Separating gradient MC and semi-gradient TD(0) into unrelated categories

    They are the infinity-step and one-step special cases of n-step semi-gradient TD.

    Fix: Place both methods on the n-step continuum and compare the targets they use.

  • Forgetting the fixed-policy setting

    The source identifies that setting as the context in which n-step semi-gradient TD is suited.

    Fix: State the policy setting before explaining why the algorithm is a natural choice.

Check Your Understanding

MEDIUM

Explain, in your own words, why gradient MC and semi-gradient TD(0) can both be described as special cases of n-step semi-gradient TD.

Hints
  • Compare the amount of sampled experience used by the two methods.
  • Identify which method is the one-step case.
  • Identify which method is the complete-return or infinity-step case.

What do you think happens?

A TD target contains a value estimate that depends on the current weight vector. Does semi-gradient TD include that target dependence when computing its gradient?

  • Yes, always
  • No, it ignores that dependence
  • Only when n is one
Reveal answer

Answer: No, it ignores that dependence.

That omission is the reason these methods are called semi-gradient methods rather than true gradient methods.

Key Takeaways

  1. Variations of stochastic gradient descent update a weight vector from sampled experience to find a good function approximation.
  2. In the on-policy fixed-policy setting, n-step semi-gradient TD naturally connects sampled rewards with a later estimated value.
  3. Semi-gradient TD(0) is the one-step special case of the n-step family.
  4. Gradient MC is the infinity-step special case that uses a complete sampled return.
  5. Semi-gradient TD is not a true gradient method because it ignores the target's dependence on the weight vector when computing the gradient.

Key Takeaways

  • Stochastic gradient descent variations provide successive weight-vector updates for function approximation.
  • n-step semi-gradient TD is natural for on-policy learning with a fixed policy because it combines sampled rewards with a later value estimate.
  • Semi-gradient TD(0) and gradient MC are the one-step and infinity-step special cases of the same n-step family.
  • Semi-gradient methods are not true gradient methods because they ignore the weight dependence of the target during gradient computation.

Related Topics