Sample-Average Action-Value Estimation

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

Machine Learning

From Rewards to an Estimate

When an action is selected several times, each selection produces a reward. A natural estimate of that action’s value is the average of the rewards observed so far. This estimate is not based on one reward alone; it summarizes the observed rewards for that action.

How does each newly observed reward change the estimated value of an action?

The diagram uses a generated numerical illustration. Its main lesson is that the estimate is recalculated from the observed rewards: after rewards 4 and 6, the average is 5; after adding reward 2, the average becomes 4.

A Worked Sample Average

Worked example

Three observations of one action

An action produces the rewards 4, 6, and 2 on three selections. Use the observed rewards to estimate the action’s value with a sample average.

1
Collect the observations
The observed rewards are 4, 6, and 2.
2
Combine the rewards
The total of the observed rewards is 12.
3
Account for the observations
There are 3 observed rewards, so the total is divided by 3.
4
Interpret the result
The resulting estimate is 4. It represents the average reward observed for this action so far.

Result

The sample-average estimate is 4.

The estimate is tied to the number of times the action has been selected. In the source notation, R_i denotes the reward received after the ith selection of the action. Q_n denotes the estimated action value after the action has been selected n minus 1 times, so the estimate uses the rewards observed before it is labeled Q_n.

The Cost of Full History

The arithmetic of an average is simple, but the way the average is maintained matters. A straightforward method can keep every reward and repeatedly add the entire collection whenever an estimate is needed. As experience accumulates, this method has two separate growing costs: memory for storing the rewards and computation for adding them.

What does the stored reward history look like after 1, 2, and many observations, and how does its size grow?

Cost	What grows in the full-history method	Why it matters
Memory	The stored collection of rewards	More observations require more storage
Computation	The work of adding the full collection	More observations make each repeated calculation longer

Memory growth and computation growth are different costs, although both arise from retaining and reprocessing the full reward history.

These costs should not be conflated. Memory growth describes how much reward history must be retained. Computation growth describes how much work is required when that history is repeatedly added. A method can therefore be discussed in terms of both what it stores and what it does at each update.

Incremental Maintenance

Incremental computation changes the maintenance strategy. Instead of repeatedly treating the entire reward history as a fresh input, the estimate is updated as new observations arrive. For action-value estimation, the desired behavior is constant memory and per-time-step computation.

How can a new estimate be computed from the previous estimate, the observation count, and the newest reward?

The data-flow diagram expresses the principle of incremental computation rather than a particular implementation formula. The prior estimate summarizes earlier observations, the observation count records how much experience has been collected, and the newest reward supplies the new information. The update processes these inputs without requiring the entire reward history to be treated as a fresh input.

As more rewards are collected, which parts of the averaging method require more memory and which require more computation?

Common Reasoning Errors

Common mistake
Treating the latest reward as the action-value estimate.
What it looks like
The observed rewards are 4, 6, and 2, but the estimate is reported as 2 because 2 was observed most recently.
Why it fails
A sample average uses the rewards observed so far, not only the newest reward.
Do this instead
Combine the observed rewards and divide by the number of observations.
Common mistake
Describing full-history averaging as having only a memory problem.
What it looks like
The method is criticized because it stores all rewards, while the repeated addition of those rewards is ignored.
Why it fails
The straightforward method has two growing costs: storage for rewards and computation for adding them.
Do this instead
Evaluate memory growth and computation growth separately.
Common mistake
Assuming constant memory means that no information from earlier observations matters.
What it looks like
An incremental method is described as forgetting all earlier rewards after each new reward arrives.
Why it fails
The purpose of incremental computation is to maintain an estimate as new observations arrive without repeatedly treating the entire history as a fresh input.
Do this instead
Think of the estimate as a maintained summary of earlier observations.
Common mistake
Confusing per-time-step computation with a single calculation performed only once.
What it looks like
An approach is called per-time-step because it eventually computes an average, even though each new observation triggers a longer full-history recomputation.
Why it fails
Per-time-step computation concerns the work required when each new time step is processed.
Do this instead
Ask whether processing a new observation remains bounded instead of becoming an ever-longer recomputation.

Check Your Understanding

EASY

An action has produced the rewards 3, 3, and 9. What is its sample-average estimate after these observations? Then identify which cost grows in a full-history method: the storage for rewards, the computation for repeatedly adding them, or both.

Hints

Add the three observed rewards.
Divide the total by the number of observations.
The source identifies two growing costs in the straightforward method.

Your attempt (not saved)

What do you think happens?

After receiving more rewards, should a desirable incremental method need to store an ever-longer reward history and repeatedly add that entire history?

Yes, because the full history must always be a fresh input
No, it should update the estimate as new observations arrive
Only the storage grows; the computation does not
Only the computation grows; the storage does not

Reveal answer

Answer:

No, it should update the estimate as new observations arrive.

Incremental computation seeks constant memory and per-time-step computation rather than ever-growing storage and repeated full-history recomputation.

Key Takeaways

1
A sample average is a natural estimate of an action’s value from the rewards observed for that action.
2
Keeping every reward and repeatedly adding the full history causes both memory and computation to grow.
3
Memory growth describes stored reward history, while computation growth describes the work of reprocessing that history.
4
Incremental computation updates an estimate as new observations arrive instead of repeatedly treating the entire history as a fresh input.
5
Constant memory and per-time-step computation are desirable because their costs should not grow simply from accumulating more observations.

At a glance

The sample average of observed rewards provides a natural estimate of an action’s value.
A full-history approach becomes less efficient because both stored rewards and repeated addition grow with experience.
Memory growth and computation growth are separate costs that should be analyzed separately.
Incremental computation maintains the estimate as new observations arrive.
The desired efficiency goals are constant memory and per-time-step computation.

More concepts starting with S