# State aggregation methods

In Sutton's RL:An introduction 2nd edition it says the following(page 203):

State aggregation is a simple form of generalizing function approximation in which states are grouped together, with one estimated value (one component of the weight vector w) for each group. The value of a state is estimated as its group’s component, and when the state is updated, that component alone is updated. State aggregation is a special case of SGD (9.7) in which the gradient, rv̂(S t ,w t ), is 1 for S t ’s group’s component and 0 for the other components.

and follows up with a theoretical example.

My question is, imagining my original state space is [1,100000], why can't I just say that the new state space is [1, 1000] where each of these numbers corresponds to an interval: so 1 to [1,100], 2 to [101,200], 3 to [201,300], and so on, and then just apply the normal TD formula, instead of using the weights?

My main problem with their approach is the last sentence:

in which the gradient, rv̂(S t ,w t ), is 1 for St’s group’s component and 0 for the other components.

if v(s,w) is the linear combination of a feature vector and the weights (w), how does the gradient of that function can be 1 for a state and 0 for others? There are not as many w as states or groups of states.

e.g.: if my feature vector is 5 numbers between 0 and 100. For example (55,23,11,44,99) for a specific state, how do you choose a specific group of states for state aggregation?

Maybe what I'm not understanding is the feature vector. If we have a state space that is[1,10000] as in the random walk, what can be the feature vector? does it have the same size as the number of groups after state aggregation?

## 1 Answer

Using the book's random walk example, If you have a state space with $$1000$$ states and you divide them into $$10$$ groups, each of those groups will have $$100$$ neighboring states. The function for approximation will be $$\begin{equation} v(\mathbf w) = x_1w_1 + x_2w_2 + ... + x_{10}w_{10} \end{equation}$$ Now, when you pick a state, the feature vector will be a one-hot encoded vector with $$1$$ that is placed in a position that depends on in which group does the chosen state belong. For example if you have state $$990$$ that state belongs in group $$10$$ so the feature vector will be $$\begin{equation} \mathbf x_t = [0, 0, ..., 0, 1]^T \end{equation}$$ what this means is that the only weight that will be updated is weight $$w_{10}$$ because gradients for all other weights will be $$0$$ (that's because features for those weights are $$0$$)

• And then each each weight corresponds to a group and it would give the same result as the implementation I explained ? So in that example If I just used normal TD(0) with only 10 states where each of the states corresponds to a group, wouldn't it just give the same result? – Miguel Saraiva May 8 '19 at 16:20
• Also in normal semi-gradient TD(0), the feature vector is just a linear representation of the state that can have any values, like (10,21,31,45) ? – Miguel Saraiva May 8 '19 at 16:26
• yes its the same thing and states can have any values, they can be scalars or vectors – Brale May 8 '19 at 16:29