Gradient Monte Carlo Algorithm

Gradient Monte Carlo waits for each episode to finish, then nudges value weights toward the full returns it actually saw, which is honest descent with no borrowed guesses.

Gradient Monte Carlo turns one finished episode into full return targets, then walks the weights downhill to 2.00 and 2.25

Why Does This Exist?

Tables stop working the moment states get numerous. You cannot keep a separate value for every robot pose or board layout, so you approximate values with weights, written vhat(s, w). The trouble is that changing one weight moves many states at once, so single state fixes can fight each other.

The clean target is the mean squared value error: the average squared gap between your estimates and the truth, weighted by how often each state appears. Temporal difference learning chases a moving target here, because its target contains your own current estimate. That shortcut is fast but it is not true gradient descent, and its guarantees fall away. Gradient Monte Carlo takes the patient route. It waits for the episode to end, builds each return from rewards that actually happened, and steps downhill on the real error. Compare it with semi-gradient TD(0) to see the trade clearly.

The one idea you need first

A return G is the discounted reward total from one time step to the end of the episode. With discount gamma = 1.0 and rewards 1.0, 0.0, 3.0, the returns walking backward are 3.0, then 0.0 + 3.0 = 3.0, then 1.0 + 3.0 = 4.0. Each return is one unbiased sample of the true value of its state.

Think of It Like This

Grading essays only after finals week

A teacher wants to rate how well each week's lessons worked. The hasty version asks students after week three how confident they feel about week four, then treats that guess as fact. One confused class poisons the rating of everything before it.

The Monte Carlo teacher waits. Lessons run all term, finals get marked, and only then does each week's rating move toward the final scores of students who sat through it. One student's grade is noisy, since sleep and luck intrude, but across many students the signal is honest. The price is patience: nobody gets feedback until the term ends.

Where it stops: a teacher can reuse last year's finals, but an agent that changes its policy changes the exam itself, so old returns slowly go stale.

How It Actually Works

Call the error VE(w): the average over states of squared gaps between true values v(s) and estimates vhat(s, w), weighted by visit frequency. True stochastic gradient descent on one visited state S looks like this, with step size alpha:

w_{new} = w + \alpha \, [v(S) - \hat{v}(S, w)] \, \nabla \hat{v}(S, w)

The true value v(S) is unknown, so gradient Monte Carlo plugs in the sampled return G for v(S):

w_{new} = w + \alpha \, [G - \hat{v}(S, w)] \, \nabla \hat{v}(S, w)

This swap is legal in expectation because the return averages to the true value, and it is a true gradient because G contains no weights. Under the usual shrinking step sizes it converges, and with linear features it lands on the single global best fit.

With linear approximation the estimate is weights dot features, vhat(s, w) = w . x(s), so the gradient is just the feature vector x(s) and the update is:

w_{new} = w + \alpha \, [G - w . x(S)] \, x(S)

Worked example

Six states share two weights by grouping: states 1 to 3 use features [1.0, 0.0], states 4 to 6 use [0.0, 1.0]. Start at w = [0.0, 0.0] with alpha = 0.5 and gamma = 1.0. One episode visits state 2, then 4, then 5, with rewards 1.0, 0.0, 3.0.

First compute returns backward: G2 = 3.0, G1 = 0.0 + 3.0 = 3.0, G0 = 1.0 + 3.0 = 4.0.

Then update forward. At t = 0 the estimate is 0.0, the error is 4.0 - 0.0 = 4.0, and w becomes [0.0, 0.0] + 0.5 * 4.0 * [1.0, 0.0] = [2.0, 0.0]. At t = 1 the estimate is still 0.0, the error is 3.0, and w becomes [2.0, 0.0] + 0.5 * 3.0 * [0.0, 1.0] = [2.0, 1.5]. At t = 2 the estimate is now 1.5, the error shrinks to 3.0 - 1.5 = 1.5, and w lands at [2.0, 1.5] + 0.5 * 1.5 * [0.0, 1.0] = [2.0, 2.25].

Final estimates: group one states read 2.00, group two states read 2.25. Notice the second visit to group two profiting from the first, with its error cut from 3.0 to 1.5.

Code

This snippet replays the worked episode with plain lists, printing the same returns and final weights derived by hand.

1def episode_returns(rewards: list[float], gamma: float) -> list[float]:2    out = [0.0] * len(rewards)3    running = 0.04    for t in range(len(rewards) - 1, -1, -1):5        running = rewards[t] + gamma * running6        out[t] = running7    return out8
9
10features = [[1.0, 0.0], [0.0, 1.0], [0.0, 1.0]]11rewards = [1.0, 0.0, 3.0]12weights = [0.0, 0.0]13alpha = 0.514
15returns = episode_returns(rewards, gamma=1.0)16print([f"{g:.1f}" for g in returns])  # -> ['4.0', '3.0', '3.0']17for x, g in zip(features, returns):18    pred = weights[0] * x[0] + weights[1] * x[1]19    err = g - pred20    weights = [w + alpha * err * xi for w, xi in zip(weights, x)]21print([f"{w:.2f}" for w in weights])  # -> ['2.00', '2.25']

Returns [4.0, 3.0, 3.0] and weights [2.00, 2.25] match the backward pass and the three updates above exactly.

Watch Out For

Trusting one long episode as if it were many

A single return bundles every lucky and unlucky bounce across the whole episode, so its variance grows with episode length. One update from one marathon episode can yank the weights far from their good values.

Symptom: weights swing wildly between episodes and only settle if you shrink alpha to a crawl. Fix: average over many episodes, keep alpha small, and switch to bootstrapping methods like semi-gradient TD(0) when episodes run long.

Waiting for an ending that never comes

Gradient Monte Carlo cannot update until termination, so it simply does not apply to continuing tasks with no final step. Hacking in an arbitrary cutoff silently biases every target.

Symptom: no learning signal for thousands of steps, then one giant correction. Fix: use this method for episodic tasks only, and reach for temporal difference updates with value function approximation when the task never ends.

The Quick Version

Gradient Monte Carlo aims at the mean squared value error and steps along its true gradient, not a bootstrapped guess.
Full episode returns are unbiased targets because they average to the true values and contain no weights.
With linear features the update is weights plus step size times error times the feature vector.
One worked episode moved shared weights from zero to 2.00 and 2.25, with the repeat visit halving its error.
The price is variance plus waiting: long or endless episodes need bootstrapping instead.
For the online counterpart, read semi-gradient TD(0), and for the optimizer underneath, stochastic gradient descent in RL.