Incremental Updates for Action Values

A sample average is a natural estimate of an action value.

Machine Learning

From Rewards to an Estimate

When an action is selected repeatedly, each selection produces a reward. A natural estimate of that action's value is the sample average of the rewards observed so far. The estimate is therefore not based on one reward alone; it combines the observations collected up to that point.

Worked example

Estimating a value from three rewards

An action produces rewards of 4, 6, and 5 on three selections. What is the sample-average estimate after these observations?

1
First observation
With only the reward 4 observed, the sample average is 4.
2
Second observation
The estimate combines 4 and 6. Their average is 5.
3
Third observation
The estimate combines 4, 6, and 5. Their average is 5.

Result

The sample-average estimate after the three observations is 5.

Following the Estimate Over Time

The important change is not only the final average but also how the estimate develops as new rewards arrive. After each selection, a new observation becomes available, and the action-value estimate must represent the rewards observed so far. Incremental computation treats this as an ongoing update rather than repeatedly treating the entire history as a completely new input.

How does the estimated action value change when one new reward is observed?

The Cost of Keeping the History

The arithmetic of an average is simple, but the way the average is maintained matters. A straightforward method can keep every past reward and repeatedly add the entire collection whenever the estimate is needed. As more rewards are collected, this approach has two growing costs: memory is needed to store the rewards, and computation is needed to add them.

How does the amount of stored data grow as more rewards are collected?

Why does recomputing an average from all stored rewards require more work at later time steps?

Cost	What grows in the straightforward method	Why it matters
Memory	The collection of stored rewards	More observations require more stored data
Computation	The work of adding the stored rewards	A later estimate may require processing a longer history

Memory growth and computation growth are separate costs.

The Incremental-Computing Goal

Incremental computation updates an estimate as new observations arrive instead of repeatedly using the entire reward history as a fresh input. For action-value estimation, the desired behavior is constant memory and per-time-step computation. Constant memory means that the memory requirement should not grow simply because more rewards have been observed. Per-time-step computation means that processing each new time step should remain bounded rather than requiring an ever-longer recomputation.

What information must be retained to update the average without storing every past reward?

Best practice

When designing an action-value estimator, ask two separate questions: Does the stored information grow as observations accumulate? Does processing a new time step require revisiting an increasingly long history? The incremental-computation goal is constant memory and bounded per-time-step computation.

Check Your Understanding

MEDIUM

Suppose an action has been selected many times. Compare these two methods: Method A stores every reward and repeatedly adds the full collection; Method B updates an estimate as each new reward arrives. Identify which method has growing memory use, which method has growing recomputation work, and what computational behavior Method B is intended to achieve.

Hints

Separate memory growth from computation growth.
Look for the method that repeatedly processes the entire reward history.
The desired behavior is described using two terms: constant memory and per-time-step computation.

Your attempt (not saved)

Common mistake
Treating memory growth and computation growth as the same cost
What it looks like
Saying only that the method becomes slow, without identifying whether stored data, repeated additions, or both are growing
Why it fails
The straightforward averaging method has two distinct growing costs: memory for storing rewards and computation for adding them.
Do this instead
Analyze storage and work separately before evaluating the method.
Common mistake
Thinking that a sample average uses only the newest reward
What it looks like
Replacing the previous estimate with the latest observed reward
Why it fails
The sample average is based on the rewards observed so far, not on the newest reward alone.
Do this instead
Treat each new reward as another observation contributing to the action-value estimate.
Common mistake
Assuming constant memory means the estimate remains fixed
What it looks like
Claiming that an estimate cannot change once its memory use is constant
Why it fails
Constant memory describes how much information is retained, while the estimate can still be updated when new observations arrive.
Do this instead
Keep the memory requirement fixed while allowing the estimate to change with new rewards.

Key Takeaways

1
A sample average is a natural estimate of an action value when an action has produced multiple observed rewards.
2
Keeping every reward and repeatedly summing the full history causes both memory and computation costs to grow.
3
Memory growth concerns how much reward data must be stored; computation growth concerns how much work is required to recompute the estimate.
4
Incremental computation updates the estimate as new observations arrive instead of repeatedly processing the entire history.
5
The desired behavior is constant memory and per-time-step computation that remains bounded.

At a glance

The sample average provides a natural estimate of an action value.
Storing every reward creates growing memory requirements.
Recomputing from the full history creates growing computation requirements.
Incremental updates aim to retain a fixed amount of information and process each new time step with bounded work.

More concepts starting with I