Concepts / Monte Carlo State-Value Prediction

Monte Carlo State-Value Prediction

The Gradient Monte Carlo Algorithm evaluates a policy by adjusting the weights of a differentiable value-function approximation.

  • Programming

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.

Policy πComplete episodeS₀, S₁, …, SₜReturns Gₜone for each nonterminalstepPrediction errorGₜ − v̂(Sₜ, θ)Weights θadjusted by the gradientgeneratessuppliescompared with estimateupdates
How does the algorithm move from following a policy through an episode to computing returns and updating the value-function weights?

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.

State SₜPolicy πEpisode after Sₜsampled futureReturn Gₜone sampled outcomeTrue value vπ(Sₜ)expected returncontinue fromgeneratesproducesunbiased estimate of
How is the sampled return G_t generated from a state and why does averaging returns from that state estimate the true value vπ(s)?

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

Definition

For a visited state S_t, the Gradient Monte Carlo update compares the sampled return G_t with the current approximation v̂(S_t, θ). The difference G_t − v̂(S_t, θ) is the prediction error. The algorithm multiplies this error by the gradient of the approximation with respect to the weights, scales the result by the step size α, and adds it to θ.

Formula, step by step
  1. 1
    Compute the current approximate value v̂(S_t, θ).
  2. 2
    Compute the prediction error G_t − v̂(S_t, θ).
  3. 3
    Find the gradient ∇v̂(S_t, θ), which describes how the approximation changes with the weights.
  4. 4
    Multiply the prediction error and gradient by the step size α.
  5. 5
    Add the resulting adjustment to the current weights θ.
State Sₜv̂(Sₜ, θ) = 4Weights θ[2.6, 1.8]Return Gₜ10Weights θ[2, 3]error 6, α 0.1, gradient [1, −2]targetupdated
Given a state, its current approximate value, a return G_t, and a step size, how do the prediction error and feature gradient change the weight vector?
Worked example

Calculating one parameter update

Consider one visited state with current approximate value 4, return G_t equal to 10, step size α equal to 0.1, gradient [1, −2], and current weight vector [2, 3].

  1. 1
    Find the prediction error

    The prediction error is 10 − 4 = 6.

  2. 2
    Scale the gradient

    Multiply the error by the step size and gradient: 0.1 × 6 × [1, −2] = [0.6, −1.2].

  3. 3
    Add the adjustment

    Add the adjustment to the current weights: [2, 3] + [0.6, −1.2].

Result

The updated weight vector is [2.6, 1.8].

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.

Unbiased target UₜE[Uₜ] = vπ(Sₜ)Repeated updatesparameter sequence θₜLocal optimumconvergence destinationDecreasing αusual stochasticapproximation conditionssupports guaranteecontrolsconverges to
What conditions must hold for repeated Gradient Monte Carlo updates to converge, and what does convergence mean for the approximate value function?

Common Reasoning Errors

  • Common mistake

    Treating one return as the exact value of the state.

    What it looks like

    Assuming G_t must equal vπ(S_t) in every episode.

    Why it fails

    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.

    Do this instead

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

  • Common mistake

    Updating only the state value instead of the approximation weights.

    What it looks like

    Replacing a table entry for S_t without considering θ.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Using a return before the episode is complete.

    What it looks like

    Trying to update from a partial trajectory.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Stating convergence without its assumptions.

    What it looks like

    Claiming that repeated updates always reach an optimum.

    Why it fails

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

    Do this instead

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

Check Your Understanding

EASY

A visited state has current approximate value 7 and sampled return 3. The step size is α, and the gradient is g. Describe the update direction before substituting any numerical value for α or g.

Hints
  • Start with the prediction error G_t − v̂(S_t, θ).
  • Determine whether the error is positive or negative.
  • Multiply that error by the gradient and step size.
MEDIUM

Explain why averaging sampled returns from a state can estimate its true value under policy π, even though an individual return may not equal that value.

Hints
  • Recall the definition of the true state value as an expected return.
  • Use the fact that G_t is an unbiased estimate of vπ(S_t).

What do you think happens?

If the sampled return is smaller than the current approximate value, what sign does the prediction error have?

  • Positive

  • Negative

  • It must be zero

Reveal answer
Answer:

Negative

The prediction error is G_t − v̂(S_t, θ). When G_t is smaller than the current approximation, the difference is negative. The resulting weight adjustment is determined by that negative error together with the gradient and step size.

Key Takeaways

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

At a glance

  • A complete episode supplies a return for each visited nonterminal state.
  • The return G_t estimates the true state value because the true value is the expected return after the state.
  • The parameter update moves the differentiable approximation using the prediction error, its gradient, and the step size.
  • The convergence guarantee requires unbiased targets and a decreasing step size satisfying the usual stochastic approximation conditions.
  • Under those conditions, the parameter sequence converges to a local optimum.

Related Topics

Related concepts

More concepts starting with M