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

CC BY-SA 4.0
2019-05-08T16:20:50.893Z
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
CC BY-SA 4.0
2019-05-08T16:26:58.393Z
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
CC BY-SA 4.0
2019-05-08T16:29:32.693Z
yes its the same thing and states can have any values, they can be scalars or vectors
Brale
CC BY-SA 4.0
2019-05-08T16:03:44.177Z
2022-04-02T10:19:47.200Z
2022-04-02T10:19:47.200Z
Brale
<p>In Sutton's RL:An introduction 2nd edition it says the following(page 203):</p>
<blockquote>
<p>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 <span class="math-container">$(9.7)$</span> in which the gradient, <span class="math-container">$\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$</span>, is 1 for <span class="math-container">$S_{t}$</span> 's group's component and 0 for the other components.</p>
</blockquote>
<p>and follows up with a theoretical example.</p>
<p>My question is, imagining my original state space is <span class="math-container">$[1,100000]$</span>, why can't I just say that the new state space is <span class="math-container">$[1, 1000]$</span> where each of these numbers corresponds to an interval: so 1 to <span class="math-container">$[1,100]$</span>, 2 to <span class="math-container">$[101,200]$</span>, 3 to <span class="math-container">$[201,300]$</span>, and so on, and then just apply the normal TD(0) formula, instead of using the weights?</p>
<p>My main problem with their approach is the last sentence:</p>
<blockquote>
<p>in which the gradient, <span class="math-container">$\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$</span>, is 1 for <span class="math-container">$S_{t}$</span> 's group's component and 0 for the other components.</p>
</blockquote>
<p>If <span class="math-container">$\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$</span> 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.</p>
<p>Let's say that my feature vector is 5 numbers between 0 and 100. For example, <span class="math-container">$(55,23,11,44,99)$</span> for a specific state, how do you choose a specific group of states for state aggregation?</p>
<p>Maybe what I'm not understanding is the feature vector. If we have a state space that is <span class="math-container">$[1, 10000]$</span> 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?</p>

<reinforcement-learning><function-approximation><features>
How can $\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$ be 1 for $S_{t}$ 's group's component and 0 for the other components?
Miguel Saraiva
# How can $\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$ be 1 for $S_{t}$ 's group's component and 0 for the other components?

(Asked by: username_0 on 2019-05-08)

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?

**Tags:** reinforcement-learning, function-approximation, features


---

## 1 answers

### Answer by username_1 on 2019-05-08. Score: 1 | Accepted 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$)

> **Comments:**
> **username_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?  
> **username_0**: 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) ?  
> **username_1**: yes its the same thing and states can have any values, they can be scalars or vectors  

---

