1
$\begingroup$

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, $\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$, 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, $\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$, is 1 for $S_{t}$ 's group's component and 0 for the other components.

If $\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$ 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.

Let's say that 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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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, 2019 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, 2019 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, 2019 at 16:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .