Gradient Descent for Value-Function Approximation

From Episode Return to Weight Change

A table-based value function can update a state entry directly. With function approximation, the value estimate is represented by v̂(S_t, θ), so learning changes the weight vector θ instead. Gradient Monte Carlo evaluates a policy by generating a complete episode, collecting a return for each visited state, and using those returns to adjust the differentiable approximation.

Why the Return Is a Useful Target

For a visited state S_t, the algorithm uses G_t, the return from that point in the completed episode. The true state value v_π(S_t) is the expected return after that state. Therefore, G_t is an unbiased estimate of v_π(S_t): across returns generated from the same state under the policy, the expected return equals the true state value. One episode supplies a sample, not the exact value.

The Single-State Update

θ ← θ + α [G_t − v̂(S_t, θ)] ∇v̂(S_t, θ)

Complete-Episode Learning

Gradient Monte Carlo first generates a complete episode using policy π. After the episode is complete, it uses the return G_t for every nonterminal time step t from 0 through T − 1. Each visited state therefore contributes its own comparison between an observed return and the current approximate value. The method is a gradient-descent form of Monte Carlo state-value prediction because the differentiable approximation is improved by changing θ.

N-step semi-gradient TD is natural for the on-policy case with a fixed policy because it forms targets from experience generated under that same policy. Semi-gradient TD(0) is the one-step special case. Gradient Monte Carlo is the infinity-step special case, where the target is the full episode return.

Why Semi-Gradient Is Not True Gradient

A true gradient method differentiates the complete objective with respect to the weight vector. Semi-gradient TD methods use an estimated value in their target, but ignore the target’s dependence on the weight vector when computing the gradient. They therefore use only part of the relevant gradient, which is why they are called semi-gradient methods rather than true gradient methods.

• Calling every update involving a gradient a true gradient method.

  Semi-gradient TD ignores the target’s dependence on the weight vector when computing the gradient.

  Fix: Remember that semi-gradient describes a partial gradient calculation.

• Assuming one return is the exact value of a state.

  G_t is a sample return. Its expected value, rather than every individual sample, equals the true state value.

  Fix: Use the return as an unbiased learning target, not as a claim that the exact value has been observed.

• Updating a table entry instead of the approximation parameters.

  Function approximation represents values through the weight vector θ.

  Fix: Apply the prediction error, approximation gradient, and step size to update θ.

Convergence and Step Sizes

The convergence guarantee depends on the target being unbiased. If U_t satisfies E[U_t] = v_π(S_t) for every t, and the step size α decreases according to the usual stochastic approximation conditions, then the parameter sequence θ_t is guaranteed to converge to a local optimum.

Variations of stochastic gradient descent are used to find a good weight vector for function approximation. In this setting, the algorithm repeatedly uses sampled targets and parameter updates rather than requiring the exact state value before learning can begin.

Practice Check

Summary

1. Gradient Monte Carlo generates complete episodes under policy π and uses each visited state’s return G_t as a target.
2. G_t is an unbiased estimate of v_π(S_t) because the true state value is the expected return after the state.
3. The parameter update scales the prediction error by the approximation gradient and step size, then adds the result to θ.
4. With unbiased targets and step sizes satisfying the usual stochastic approximation conditions, the parameter sequence is guaranteed to converge to a local optimum.
5. Semi-gradient TD methods ignore the target’s dependence on the weight vector, so they are not true gradient methods; semi-gradient TD(0) and Gradient Monte Carlo are the one-step and infinity-step special cases of n-step semi-gradient TD.