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[0] 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?


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$)

  • $\begingroup$ 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? $\endgroup$ – Miguel Saraiva May 8 '19 at 16:20
  • $\begingroup$ 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) ? $\endgroup$ – Miguel Saraiva May 8 '19 at 16:26
  • $\begingroup$ yes its the same thing and states can have any values, they can be scalars or vectors $\endgroup$ – Brale May 8 '19 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.