Batch Updating

Batch updating keeps all episodes seen so far and repeatedly presents that growing batch until convergence.

Programming

Learning from a Fixed Record

Many learning methods process experience as it arrives. Batch updating uses a different rhythm. It keeps all episodes seen so far, treats them as one growing collection, and repeatedly presents that collection to the learning method until the value function converges. When a new episode arrives, the earlier episodes are not discarded. They remain part of the batch.

How are previously observed episodes retained, replayed, and incorporated when a new episode is added?

One Complete Batch Pass

Batch updating delays modification of the value function until a complete batch has been processed. Begin with an approximate value function. During one pass through the available experience, calculate the increment associated with every time step at which a nonterminal state is visited. Keep the value function fixed while calculating those increments. After the pass is complete, combine the increments and apply the resulting overall change once. The next pass then uses this newly changed value function.

1
Collect a finite record of experience, such as several episodes or a fixed number of time steps.
2
Treat every episode in the record as one batch.
3
Calculate the required increment for each visited nonterminal state while keeping the current value function fixed.
4
Apply the combined change after the complete batch has been processed.
5
Present the same batch again using the updated value function.
6
Continue repeating complete passes until the value function converges.

What is the sequence from collecting a finite set of episodes to updating estimates and stopping at convergence?

What Monte Carlo Remembers

Batch constant-alpha Monte Carlo converges to the sample averages of the actual returns observed after visits to each state. In other words, its batch result reflects the returns stored in the finite training set. This gives Monte Carlo a limited form of optimality: it minimizes mean-squared error from those training-set returns.

Worked example

A State Visited with Different Observed Returns

A finite batch contains several visits to one state. The recorded returns after those visits are not all the same. What does batch constant-alpha Monte Carlo move toward?

1
Collect the observed returns
The batch keeps the returns actually observed after visits to the state.
2
Compare the observations
The method treats the recorded returns as its training-set evidence for that state.
3
Replay the batch
Repeated processing causes the estimate to move toward the sample average of those observed returns.
4
Interpret the result
The resulting estimate is optimal for reproducing the training-set returns in the mean-squared-error sense described for Monte Carlo.

Result

Batch constant-alpha Monte Carlo converges toward the sample average of the actual returns observed after visits to that state.

How can Monte Carlo be optimal relative to observed episodes while still differing from the target value function?

Why TD(0) Can Win the Comparison

The random-walk comparison separates two questions. First, how closely do estimates reproduce the returns stored in the training set? Second, how closely do estimates match the value function used as the target in the random-walk task? Monte Carlo has the special guarantee for the first question. The reported experiment measured the second question and found that batch TD(0) was consistently better according to root mean-squared error against the target value function.

Question being measured	What batch Monte Carlo guarantees	What the random-walk result reported
Agreement with observed training-set returns	Converges to their sample averages and minimizes mean-squared error from them	This is Monte Carlo's limited form of optimality
Agreement with the target value function	May differ from the target because the observed returns are only the finite training set	Batch TD(0) was consistently better by root mean-squared error

The method that is optimal for one measurement need not be best for another measurement.

How do batch TD(0) and batch Monte Carlo compare when estimates are judged against the target value function?

The Convergence Boundary

Under batch updating, TD(0) has a deterministic convergence result when the step-size parameter alpha is sufficiently small. Starting from the same available experience and applying the same batch procedure leads to one specific answer. The source describes that answer as independent of the particular sufficiently small choice of alpha.

The condition matters. The claim is not that every possible step size produces the same result. It applies only when alpha is sufficiently small. If that boundary is ignored, the deterministic convergence statement is being interpreted more broadly than the source supports.

Batch constant-alpha Monte Carlo also converges deterministically under the stated conditions, but its convergence point differs from the one reached by TD(0). Therefore, deterministic convergence tells you that a method reaches a specific result from a fixed batch; it does not tell you that two different methods reach the same result.

Why does repeated TD(0) processing of a fixed batch have a deterministic result only under the sufficiently-small step-size condition?

Common Interpretation Errors

Common mistake
Treating batch updating as a one-time pass through old experience.
What it looks like
A learner processes the current episodes once and then removes them when a new episode arrives.
Why it fails
Batch updating keeps all episodes seen so far and repeatedly presents the growing batch until convergence.
Do this instead
Retain the earlier episodes, add the new episode, and replay the complete batch.
Common mistake
Saying that Monte Carlo is simply the best method.
What it looks like
Monte Carlo minimizes error against its observed training-set returns, so it must also have the lowest error against the target value function.
Why it fails
Those are different evaluation questions.
Do this instead
State which target is being used. The random-walk comparison reported batch TD(0) as consistently better by root mean-squared error against the target value function.
Common mistake
Assuming all step sizes support the TD(0) convergence claim.
What it looks like
TD(0) reaches a deterministic result for any alpha.
Why it fails
The stated result requires alpha to be sufficiently small.
Do this instead
Include the step-size condition whenever describing deterministic batch TD(0) convergence.
Common mistake
Assuming deterministic convergence means TD(0) and Monte Carlo agree.
What it looks like
Both methods converge deterministically, so they must produce the same value estimates.
Why it fails
The source states that their convergence points differ.
Do this instead
Separate the idea of one reproducible convergence point from the identity of that convergence point.

Check Your Understanding

MEDIUM

A fixed collection of episodes is processed repeatedly. You are told that batch constant-alpha Monte Carlo has converged, while batch TD(0) is being evaluated against a target value function. Explain what Monte Carlo's convergence point represents, why that does not settle the target-value comparison, and which method performed better in the reported random-walk comparison.

Hints

Start with the returns actually observed after visits to each state.
Separate error against the training-set returns from error against the target value function.
Recall the reported root mean-squared-error result for batch TD(0).

Your attempt (not saved)

What do you think happens?

If a new episode is added to a batch, what happens to the earlier episodes?

They are discarded.
They remain in the batch and are replayed with the new episode.
They are used only once more and then removed.

Reveal answer

Answer:

They remain in the batch and are replayed with the new episode.

Batch updating treats all episodes seen so far as one growing collection and repeatedly presents that collection until convergence.

Key Takeaways

1
Batch updating retains every episode seen so far and repeatedly reprocesses the growing batch.
2
During a batch pass, increments are calculated while the value function remains fixed; the combined change is applied after the pass.
3
Batch constant-alpha Monte Carlo converges to sample averages of observed returns and is optimal for mean-squared error against those training-set returns.
4
The random-walk comparison used a different target: root mean-squared error against the target value function, where batch TD(0) performed consistently better.
5
Batch TD(0) has a deterministic convergence result when alpha is sufficiently small, and its convergence point differs from that of batch constant-alpha Monte Carlo.

At a glance

Batch updating keeps all available experience and replays the complete growing batch until convergence.
Batch constant-alpha Monte Carlo converges toward sample averages of the returns observed in the training set.
Monte Carlo's optimality is limited to error measured against those observed returns.
In the reported random-walk comparison, batch TD(0) performed better by root mean-squared error against the target value function.
The deterministic batch TD(0) convergence result depends on alpha being sufficiently small, and it does not imply agreement with batch Monte Carlo.

Related concepts

More concepts starting with B