Answers.Body: <p>In short, this works because the derivative of the (implied) loss function happens to be numerically equal to the difference between current estimate and the target (this is actually a relatively common setup in regression and classifier estimators). In turn, the partial derivatives of weights associated with active tiles in tile coding each inherit that property, because their derivative factor used in the chain rule to figure out the impact of changing them in isolation is exactly 1 (whilst inactive weights have a factor of 0 and are not important to the calculation).</p>
  <p>Taking a unit step for any single weight would correct the current estimate to the new observed value. As the next part of the text in S&amp;B explains, you would not usually make such an update step if you need the estimator to <em>generalise</em>.</p>
  <p>We can show this a little more rigorously using the formulae from the book. The general update rule for estimators is:</p>
  <p><span class="math-container">$$\mathbf{w} \leftarrow \mathbf{w} + \alpha[G - \hat{v}(s, \mathbf{w})]\nabla \hat{v}(s, \mathbf{w})$$</span></p>
  <p>Where <span class="math-container">$G$</span> is the sampled or measured return, and <span class="math-container">$G - \hat{v}(s, \mathbf{w})$</span> is therefore a measure of the error in the estimate.</p>
  <p>Let's call the error in the estimate <span class="math-container">$\delta$</span>, we can treat that as a single number from now on - any update that adjusts the estimate by <span class="math-container">$\delta$</span> makes it match the new data exactly.</p>
  <p>So now we have:</p>
  <p><span class="math-container">$$\mathbf{w} \leftarrow \mathbf{w} + \alpha \delta \nabla \hat{v}(s, \mathbf{w})$$</span></p>
  <p>In linear approximators, we have feature vector <span class="math-container">$\mathbf{x} = x(s)$</span>, and:</p>
  <p><span class="math-container">$$\hat{v}(s, \mathbf{w}) = \mathbf{w}^T\mathbf{x}$$</span></p>
  <p>Therefore:</p>
  <p><span class="math-container">$$\nabla \hat{v}(s, \mathbf{w}) = \mathbf{x}$$</span></p>
  <p>In tile coding, we always have <span class="math-container">$n$</span> active features (the <span class="math-container">$n$</span> tiles that the current state vector is contained by) with a feature vector value of <span class="math-container">$1$</span>, and the rest are <span class="math-container">$0$</span>. In terms of calculating <span class="math-container">$\hat{v}$</span> we can ignore all the <span class="math-container">$0$</span> values. The value of <span class="math-container">$\hat{v}$</span> is the sum of all the active weights that are associated with the <span class="math-container">$n \times 1$</span> values. For convenience (of keeping the notation simple) we can create a vector of length <span class="math-container">$n$</span> which is only the weights associated with those <span class="math-container">$1$</span>s - let's call that <span class="math-container">$\mathbf{w^1}$</span>. The associated part of <span class="math-container">$\mathbf{x}$</span> is a vector of <span class="math-container">$n$</span> <span class="math-container">$1$</span>s that we can call <span class="math-container">$\mathbf{1}_n$</span></p>
  <p>With the new vector, only for this one specific value of <span class="math-container">$s$</span> that has these specific <span class="math-container">$n$</span> features:</p>
  <p><span class="math-container">$$\hat{v}(s,\mathbf{w^1}) = \sum_{i=1}^n \mathbf{w^1}_i$$</span></p>
  <p>Now the update rule for the selected weights is:</p>
  <p><span class="math-container">$$\mathbf{w^1} \leftarrow \mathbf{w^1} + \alpha\delta\nabla \hat{v}(s, \mathbf{w^1})$$</span></p>
  <p>We also know that <span class="math-container">$\nabla \hat{v}(s, \mathbf{w^1}) = \mathbf{1}_n$</span>. This matches to the intuition used in the S&amp;B quote - if you change any active weight by some amount <span class="math-container">$y$</span>, then the estimate also changes by that amount. Second-order derivatives need to be always zero for this to hold, otherwise you cannot make such easy statements about large changes (e.g. this logic would not work for any neural network).</p>
  <p>So the update rule becomes:</p>
  <p><span class="math-container">$$\mathbf{w^1} \leftarrow \mathbf{w^1} + \alpha\delta\mathbf{1}_n$$</span></p>
  <p>This causes a change to the value estimate:</p>
  <p><span class="math-container">$$\hat{v}(s,\mathbf{w^1} + \alpha\delta\mathbf{1}_n) = \hat{v}(s,\mathbf{w^1}) + \sum_{i=1}^n \alpha\delta$$</span></p>
  <p>That is when calculated using the <em>old</em> <span class="math-container">$\mathbf{w^1}$</span> from before the update - this works as above because <span class="math-container">$(\mathbf{w^1} + \mathbf{y})\mathbf{x} = \mathbf{w^1}\mathbf{x} + \mathbf{y}\mathbf{x}$</span></p>
  <p>A correction of <span class="math-container">$\delta$</span> would be &quot;perfect&quot; for the single data point, so if we want that, we want:</p>
  <p><span class="math-container">$$\delta = \sum_{i=1}^n \alpha\delta =  n \alpha\delta$$</span></p>
  <p>or</p>
  <p><span class="math-container">$$\alpha = \frac{1}{n}$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-01T23:28:34.213Z
Answers.LastActivityDate: 2022-04-02T10:13:33.310Z
Answers.LastEditDate: 2022-04-02T10:13:33.310Z
Answers.UserDisplayName: Neil Slater
Body: <p>Sutton-Barto (Tile Coding, page 218):</p>
  <blockquote>
  <p>For example, choosing <span class="math-container">$\alpha = 1/n$</span>, where n is the number
  of tilings, results in exact one-trial learning. If the example <span class="math-container">$s\to v$</span> is trained on, then
  whatever the prior estimate, <span class="math-container">$\hat{v}(s,w_t)$</span>, the new estimate will be <span class="math-container">$\hat{v}(s,w_t)=v$</span>.</p>
  </blockquote>
  <p>This part is not clear for me. I need to see mathematically why that is the case.</p>
  
Tags: <reinforcement-learning><sutton-barto><tile-coding>
Title: Unclear paragraph in Sutton-Barto on "Tile Coding"
UserDisplayName: DSPinfinity
ThreadText: # Unclear paragraph in Sutton-Barto on "Tile Coding"
  
  (Asked by: username_0 on 2022-04-01)
  
  Sutton-Barto (Tile Coding, page 218):
  
  > For example, choosing $\alpha = 1/n$, where n is the number
  > of tilings, results in exact one-trial learning. If the example $s\to v$ is trained on, then
  > whatever the prior estimate, $\hat{v}(s,w\_t)$, the new estimate will be $\hat{v}(s,w\_t)=v$.
  
  This part is not clear for me. I need to see mathematically why that is the case.
  
  **Tags:** reinforcement-learning, sutton-barto, tile-coding
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-04-01. Score: 3 | Accepted answer
  
  In short, this works because the derivative of the (implied) loss function happens to be numerically equal to the difference between current estimate and the target (this is actually a relatively common setup in regression and classifier estimators). In turn, the partial derivatives of weights associated with active tiles in tile coding each inherit that property, because their derivative factor used in the chain rule to figure out the impact of changing them in isolation is exactly 1 (whilst inactive weights have a factor of 0 and are not important to the calculation).
  
  Taking a unit step for any single weight would correct the current estimate to the new observed value. As the next part of the text in S&B explains, you would not usually make such an update step if you need the estimator to *generalise*.
  
  We can show this a little more rigorously using the formulae from the book. The general update rule for estimators is:
  
  $$\mathbf{w} \leftarrow \mathbf{w} + \alpha[G - \hat{v}(s, \mathbf{w})]\nabla \hat{v}(s, \mathbf{w})$$
  
  Where $G$ is the sampled or measured return, and $G - \hat{v}(s, \mathbf{w})$ is therefore a measure of the error in the estimate.
  
  Let's call the error in the estimate $\delta$, we can treat that as a single number from now on - any update that adjusts the estimate by $\delta$ makes it match the new data exactly.
  
  So now we have:
  
  $$\mathbf{w} \leftarrow \mathbf{w} + \alpha \delta \nabla \hat{v}(s, \mathbf{w})$$
  
  In linear approximators, we have feature vector $\mathbf{x} = x(s)$, and:
  
  $$\hat{v}(s, \mathbf{w}) = \mathbf{w}^T\mathbf{x}$$
  
  Therefore:
  
  $$\nabla \hat{v}(s, \mathbf{w}) = \mathbf{x}$$
  
  In tile coding, we always have $n$ active features (the $n$ tiles that the current state vector is contained by) with a feature vector value of $1$, and the rest are $0$. In terms of calculating $\hat{v}$ we can ignore all the $0$ values. The value of $\hat{v}$ is the sum of all the active weights that are associated with the $n \times 1$ values. For convenience (of keeping the notation simple) we can create a vector of length $n$ which is only the weights associated with those $1$s - let's call that $\mathbf{w^1}$. The associated part of $\mathbf{x}$ is a vector of $n$ $1$s that we can call $\mathbf{1}\_n$
  
  With the new vector, only for this one specific value of $s$ that has these specific $n$ features:
  
  $$\hat{v}(s,\mathbf{w^1}) = \sum\_{i=1}^n \mathbf{w^1}\_i$$
  
  Now the update rule for the selected weights is:
  
  $$\mathbf{w^1} \leftarrow \mathbf{w^1} + \alpha\delta\nabla \hat{v}(s, \mathbf{w^1})$$
  
  We also know that $\nabla \hat{v}(s, \mathbf{w^1}) = \mathbf{1}\_n$. This matches to the intuition used in the S&B quote - if you change any active weight by some amount $y$, then the estimate also changes by that amount. Second-order derivatives need to be always zero for this to hold, otherwise you cannot make such easy statements about large changes (e.g. this logic would not work for any neural network).
  
  So the update rule becomes:
  
  $$\mathbf{w^1} \leftarrow \mathbf{w^1} + \alpha\delta\mathbf{1}\_n$$
  
  This causes a change to the value estimate:
  
  $$\hat{v}(s,\mathbf{w^1} + \alpha\delta\mathbf{1}\_n) = \hat{v}(s,\mathbf{w^1}) + \sum\_{i=1}^n \alpha\delta$$
  
  That is when calculated using the *old* $\mathbf{w^1}$ from before the update - this works as above because $(\mathbf{w^1} + \mathbf{y})\mathbf{x} = \mathbf{w^1}\mathbf{x} + \mathbf{y}\mathbf{x}$
  
  A correction of $\delta$ would be "perfect" for the single data point, so if we want that, we want:
  
  $$\delta = \sum\_{i=1}^n \alpha\delta = n \alpha\delta$$
  
  or
  
  $$\alpha = \frac{1}{n}$$
  
  
  ---
  
  