Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-08T16:20:50.893Z
Answers.Text: 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?
Answers.UserDisplayName: Miguel Saraiva
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-08T16:26:58.393Z
Answers.Text: 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) ?
Answers.UserDisplayName: Miguel Saraiva
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-08T16:29:32.693Z
Answers.Text: yes its the same thing and states can have any values, they can be scalars or vectors
Answers.UserDisplayName: Brale
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-08T16:03:44.177Z
Answers.LastActivityDate: 2022-04-02T10:19:47.200Z
Answers.LastEditDate: 2022-04-02T10:19:47.200Z
Answers.UserDisplayName: Brale
Body: <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>
  
Tags: <reinforcement-learning><function-approximation><features>
Title: 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?
UserDisplayName: Miguel Saraiva
ThreadText: # 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  
  
  ---
  
  