Sample-Average Action-Value Estimation

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.

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

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.

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.

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.

Common Reasoning Errors

• Treating the latest reward as the action-value estimate.

  A sample average uses the rewards observed so far, not only the newest reward.

  Fix: Combine the observed rewards and divide by the number of observations.

• Describing full-history averaging as having only a memory problem.

  The straightforward method has two growing costs: storage for rewards and computation for adding them.

  Fix: Evaluate memory growth and computation growth separately.

• Assuming constant memory means that no information from earlier observations matters.

  The purpose of incremental computation is to maintain an estimate as new observations arrive without repeatedly treating the entire history as a fresh input.

  Fix: Think of the estimate as a maintained summary of earlier observations.

• Confusing per-time-step computation with a single calculation performed only once.

  Per-time-step computation concerns the work required when each new time step is processed.

  Fix: Ask whether processing a new observation remains bounded instead of becoming an ever-longer recomputation.

Check Your Understanding

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.