State Aggregation

Why Approximate Values

Reinforcement-learning problems can contain many possible states. A separate learned value for every state can therefore become difficult to organize. Function approximation addresses this challenge by representing values with a smaller set of adjustable components. It also supports generalization: related states can share information through the approximation instead of being treated as completely unrelated cases.

State aggregation is an early function-approximation technique. It compresses a large state space into group-level value estimates. Instead of storing 1000 independently learned values, a representation can assign those states to groups and store one estimated value for each group.

A Short Historical Line

The development of function approximation in reinforcement learning was not one single invention. It brought together several related ideas: gradient-descent methods for adjusting approximations, bootstrapping methods such as semi-gradient TD(0), state aggregation for organizing states compactly, and mathematical results about when linear TD(0) converges.

Mapping States to Groups

Imagine a prediction problem with 1000 possible states but only 10 stored numbers. State aggregation assigns each state to one group. Every state mapped to that group uses the group's estimated value. A state therefore does not receive an independently learned value; it borrows the value associated with the group containing it.

The 1000-State Walk

The source task uses states numbered 1 through 1000 from left to right. Each episode starts near the middle, at state 500. From the current state, the agent can move to one of the 100 states on the left or one of the 100 states on the right, with equal probability. Near an edge, some of those neighboring states do not exist; the probability assigned to missing neighbors instead becomes a probability of terminating on that side.

A state's value reflects how the random walk tends to end when it begins from that state. The task uses 10 consecutive groups of 100 states: group 1 contains states 1 through 100, group 2 contains states 101 through 200, and the pattern continues through group 10.

One Update, One Group

The current state's group determines both the estimate used and the component updated. If the current state is 250, the relevant group is the group for states 201 through 300. An update associated with state 250 changes that group's component, so the revised estimate applies to every state in that same group.

This update is local in the parameter representation but shared in its effect on states. In the stochastic-gradient description, the gradient is 1 for the current state's group component and 0 for every other component. Thus, the update selects one group component rather than changing all group values.

Why the Graph Has Steps

A state-by-state value function could change from one state to the next. State aggregation cannot express those individual changes inside a group, because every state in that group shares one estimate. When the estimates are plotted across all 1000 states, each group appears as a flat section. At a group boundary, the estimate can change abruptly, producing the characteristic staircase shape.

Gradient Monte-Carlo with Groups

The reported experiment applied gradient Monte-Carlo learning to the 1000-state task using the 10-group representation. The learning process adjusted the group-level estimates rather than creating 1000 separate estimates. Because an episode ends with either the left terminal reward of -1 or the right terminal reward of +1, the episode outcome supplies the task's learning signal for the values represented by the visited groups.

After 100,000 episodes with a step size of α = 2 × 10^-5, the learned approximate value function was close to the global minimum of the mean squared value error. It still displayed the staircase pattern, because the representation permits only one value per group.

Common Mistakes

• Treating state aggregation as if it stored one independent value for every state.

  The representation stores one value for the entire group containing states 201 through 300.

  Fix: First identify the current state's group, then use that group's shared component.

• Assuming an update for state 250 affects only state 250.

  The updated component is shared by every state mapped to that group.

  Fix: Describe the update as changing the group component and therefore the estimate used by all states in that group.

• Interpreting the staircase graph as proof that learning failed.

  The aggregated representation cannot express separate within-group values.

  Fix: Recognize the flat sections and jumps as consequences of the ten-group representation.

• Confusing a terminal reward with the reward on every transition.

  A non-terminating transition gives reward zero; the terminal rewards occur at the left and right ends.

  Fix: Keep the reward assignments separate: left termination is -1, right termination is +1, and non-termination is 0.

Check Your Understanding

Key Takeaways

1. Function approximation and generalization help reinforcement learning organize value information across large state spaces.
2. State aggregation maps many states to one group-level value, reducing 1000 state components to 10 in the random-walk example.
3. The current state's group determines both the estimate used and the component updated; the update is local to that component but shared by all states in the group.
4. The 1000-state task has terminal rewards of -1 on the left and +1 on the right, with zero reward for non-terminating transitions.
5. The staircase graph is an expected consequence of grouped representation, and the historical context includes LMS, semi-gradient TD(0), state aggregation, and convergence analysis for linear TD(0).