Monte Carlo State-Value Prediction

From Episode to Prediction

The Gradient Monte Carlo Algorithm evaluates a policy by adjusting the weights of a differentiable approximation to the value function. Rather than requiring the exact value of a state before learning, it generates a complete episode using policy π, observes the return from each visited state, and uses those returns to correct the approximation.

Tracing One Episode

Suppose an episode visits states at times 0 through T − 1 before reaching its terminal point. For every nonterminal time step t, the algorithm takes the state S_t and the return G_t obtained from the rest of that completed episode. It then compares that return with the current approximate value v̂(S_t, θ). The same process is carried out for every visited nonterminal state in the episode.

The return G_t is not the exact value of S_t in a particular episode. It is one sampled return after that state. The true state value vπ(S_t) is the expected return after S_t under policy π. Therefore, G_t is an unbiased estimate of vπ(S_t): across the relevant sampling process, its expected value equals the true state value. This makes the return suitable as a target for correcting the approximate value.

Updating the Approximation

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

The example shows why the update changes weights rather than directly replacing a table entry. The approximation is represented by v̂(S_t, θ), so learning acts on θ. The gradient determines the direction in weight space, while the prediction error determines whether and how strongly the weights should be adjusted.

Convergence Conditions

The convergence guarantee depends on the target being unbiased. More generally, if a target 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.

Common Reasoning Errors

• Treating one return as the exact value of the state.

  G_t is one sampled return. It is an unbiased estimate because its expected value is vπ(S_t), not because every sample is identical to the expectation.

  Fix: Use the return as a target for an update while remembering that individual returns can differ from the true state value.

• Updating only the state value instead of the approximation weights.

  The Gradient Monte Carlo Algorithm represents the value approximation as v̂(S_t, θ), so the update changes the parameter vector θ.

  Fix: Apply the prediction error, gradient, and step size to the weight vector.

• Using a return before the episode is complete.

  The algorithm uses complete episodes generated by policy π and obtains each return from that completed episode.

  Fix: Generate the complete episode, obtain the return for each visited nonterminal state, and then perform the updates.

• Stating convergence without its assumptions.

  The convergence statement requires an unbiased target and a decreasing step size satisfying the usual stochastic approximation conditions.

  Fix: State both the target condition and the step-size condition, and describe the destination as a local optimum.

Check Your Understanding

Key Takeaways

1. The Gradient Monte Carlo Algorithm evaluates policy π using complete episodes and a differentiable value-function approximation.
2. Each return G_t is a sampled target for its corresponding visited state and is an unbiased estimate of vπ(S_t).
3. The update changes θ using the prediction error, the approximation gradient, and the step size α.
4. The update is applied for every nonterminal time step in the generated episode.
5. With an unbiased target and a suitable decreasing step-size schedule, the parameter sequence converges to a local optimum.