Incremental Updates for Action Values
A sample average is a natural estimate of an action value.
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.
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?
First observation: With only the reward 4 observed, the sample average is 4.
Second observation: The estimate combines 4 and 6. Their average is 5.
Third observation: The estimate combines 4, 6, and 5. Their average is 5.
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.
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.
| 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 |
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.
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
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.
Treating memory growth and computation growth as the same cost
The straightforward averaging method has two distinct growing costs: memory for storing rewards and computation for adding them.
Fix:
Analyze storage and work separately before evaluating the method.Thinking that a sample average uses only the newest reward
The sample average is based on the rewards observed so far, not on the newest reward alone.
Fix:
Treat each new reward as another observation contributing to the action-value estimate.Assuming constant memory means the estimate remains fixed
Constant memory describes how much information is retained, while the estimate can still be updated when new observations arrive.
Fix:
Keep the memory requirement fixed while allowing the estimate to change with new rewards.
Key Takeaways
- A sample average is a natural estimate of an action value when an action has produced multiple observed rewards.
- Keeping every reward and repeatedly summing the full history causes both memory and computation costs to grow.
- Memory growth concerns how much reward data must be stored; computation growth concerns how much work is required to recompute the estimate.
- Incremental computation updates the estimate as new observations arrive instead of repeatedly processing the entire history.
- The desired behavior is constant memory and per-time-step computation that remains bounded.
Key Takeaways
- 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.