Answers.Body: <p>In TD(0) learning your are using a one-step bootstrapping equation:</p>
  <p><span class="math-container">$$ V(s_t) = r_{t+1} + V(s_{t+1}) $$</span></p>
  <p>So in order to calculate the value of state <span class="math-container">$s_t$</span> you only do a one step look ahead and you bootstrap with the value of the next state <span class="math-container">$s_{t+1}$</span> (read more <a href="https://pi-tau.github.io/posts/actor-critic/#online-advantage-actor-critic" rel="nofollow noreferrer">here</a>).</p>
  <p>Your value of each state is approximated by a function with weights <span class="math-container">$w$</span>, and you optimize the weights with gradient descent. You try to make the old value <span class="math-container">$V_{w_{old}}(s_t)$</span> closer to the new value <span class="math-container">$V_{w}(s_t) = r_{t+1} + V_{w_{old}}(s_{t+1})$</span> and the objective that you optimize is the least squares objective:</p>
  <p><span class="math-container">$$ L =\frac{1}{2} \Big(V_w(s_t) - r_{t+1} + V_{w_{old}}(s_{t+1}) \Big)^2 $$</span></p>
  <p>The gradient of the objective is:</p>
  <p><span class="math-container">$$ \nabla_w L =  \Big( r_{t+1} + V_{w_{old}}(s_{t+1}) - V_w(s_t) \Big) \nabla_w V_w(s_t)$$</span></p>
  <p>Now, if you approximate the value function with a linear approximator, i.e. <span class="math-container">$V_w(s_t) = w^T x(s_t)$</span>, where <span class="math-container">$x(s_t)$</span> is a vector of (usually) handcrafted features, then you have <span class="math-container">$\nabla_w V_w(s_t) = x(s_t)$</span>, and for the gradient of the objective you get:</p>
  <p><span class="math-container">\begin{align}
    \nabla_w L &amp;= \Big( r_{t+1} + w^Tx(s_{t+1}) - w^Tx(s_t) \Big) x(s_t) \\
               &amp;= r_{t+1} x(s_t) - w^T \Big(x(s_t) - x(s_{t+1}) \Big) x(s_t)  \\
               &amp;= r_{t+1} x(s_t) - x(s_t) \Big(x(s_t) - x(s_{t+1}) \Big)^T w \\
               &amp;= \textbf{b} - \textbf{A} w
  \end{align}</span></p>
  <p>Your gradient update rule would be:
  <span class="math-container">$$ w_{new} = w + \alpha \nabla_w L = w + \alpha \Big(\textbf{b} - \textbf{A} w\Big) $$</span></p>
  <p>Normally you would perform multiple time steps and at each step you will update the weights <span class="math-container">$w$</span>. In LSTD, however, you perform multiple time steps, then you average <span class="math-container">$A$</span> and <span class="math-container">$b$</span> over these timesteps and then you compute the optimal <span class="math-container">$w$</span> with a single calculation by inverting <span class="math-container">$A$</span>:
  <span class="math-container">$$ w_{TD} = A^{-1}b $$</span></p>
  <p><strong>UPDATE:</strong><br />
  To see where these &quot;expecations&quot; come from imagine that you rollout your policy for <span class="math-container">$T$</span> steps, that is you collect <span class="math-container">$T$</span> (state <span class="math-container">$s_t$</span>, reward <span class="math-container">$r_{t+1}$</span>, next state <span class="math-container">$s_{t+1}$</span>) triples. For every triple you have to calculate the delta
  <span class="math-container">$$\Delta w = r_{t+1} x(s_t) - x(s_t) \bigg( x(s_t)-x(s_{t+1}) \bigg)^T w$$</span>
  and update the weights <span class="math-container">$ w' = w + \alpha \Delta w$</span>.</p>
  <p>The optimal value of <span class="math-container">$w$</span> will be such that, after all updates are applied we have <span class="math-container">$w_{new} = w_{old}$</span>. Thus, the sum of all updates has to be zero:
  <span class="math-container">\begin{align}
    \sum_{(s_t, r_{t+1}, s_{t+1}) \in \mathcal{D}} \Delta w &amp;= 0 \\
    \sum_{t=0}^T \Big( r_{t+1} x(s_t) - x(s_t) \bigg( x(s_t)-x(s_{t+1}) \bigg)^T w \Big) &amp;= 0 \\
    \sum_{t=0}^{T} r_{t+1} x(s_t) - \sum_{t=0}^{T} x(s_t) \bigg( x(s_t)-x(s_{t+1}) \bigg)^T w &amp;= 0 \\
    \frac{1}{T}\sum_{t=0}^{T} r_{t+1} x(s_t) - \frac{1}{T}\sum_{t=0}^{T} x(s_t) \bigg( x(s_t)-x(s_{t+1}) \bigg)^T w &amp;= 0
  \end{align}</span></p>
  <p>On the last row we divide both sides of the equation by <span class="math-container">$T$</span>. From here you can see that:
  <span class="math-container">\begin{align}
    \textbf{b} &amp;= \frac{1}{T} \sum_{t=0}^{T} r_{t+1}x(s_t) \\
    &amp;= \frac{1}{|\mathcal{D}|} \sum_{(s_t, r_{t+1}, s_{t+1}) \in \mathcal{D}} \Big[ r_{t+1} x(s_t) \Big] \\
    &amp;= \mathbb{E}_{(s_t, r_{t+1}, s_{t+1}) \in \mathcal{D}} \Big[r_{t+1} x(s_t) \Big]
  \end{align}</span></p>
  <p>So <span class="math-container">$\textbf{b}$</span> is just the average of <span class="math-container">$ \bigg( r x(s) \bigg) $</span>, which is by definition the expectation under the collected data.</p>
  <p>For me the quantity <span class="math-container">$\sum_{t=0}^{T} r_{t+1}x(s_t)$</span> has much more meaning than this expectation. I think that they are using the expectation only to shorten the formula, but for me this is very misleading. Also they do not explicitly state <strong>under what</strong> is this expectation taken, which makes it even harder to read and understand.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-06T10:16:09.150Z
Answers.Text: I understood the dervication of A and b but I dont get how you can estimate E[R_t+1] as average of rewards from time 0 to t-1. Since each reward at each timestep may have a different distribution, wouldn't the estimate be incorrect?
Answers.UserDisplayName: user75923
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-08T18:22:48.390Z
Answers.Text: Thank you so much, I had a vague understanding of expectations when it comes to stochastic random variables but your answer cleared it up. I agree that the formula in the book is very misleading. This is just one such case, there were other sections, for example, section 6.7 on maximisation bias.
Answers.UserDisplayName: user75923
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-06T09:24:34.447Z
Answers.LastActivityDate: 2023-09-07T07:05:56.233Z
Answers.LastEditDate: 2023-09-07T07:05:56.233Z
Answers.UserDisplayName: pi-tau
Body: <p>In the section on LSTD in SuttonBarto's book on RL, there is a proof on convergence of semi-gradient TD(0) using a linear function approximator.</p>
  <p><a href="https://i.sstatic.net/mJT3F.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mJT3F.png" alt="Point of convergence" /></a></p>
  <p><a href="https://i.sstatic.net/wCB3x.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wCB3x.png" alt="enter image description here" /></a></p>
  <p>Later on they estimated A and b as</p>
  <p><a href="https://i.sstatic.net/DQdQw.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DQdQw.png" alt="Estimate of A and b" /></a></p>
  <p>I was under the impression that to calculate an estimate of E[Rt+1*xt], you would have to run multiple episodes till time t and then average those samples but how are they able to estimate <strong>A</strong> and <strong>b</strong> using samples from times 0 to t-1 instead?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-06T07:19:45.123Z
Comments.Text: Could you please confirm the edition, chapter/section and equation numbers you are looking at?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-06T10:31:16.257Z
Comments.Text: @NeilSlater Section 9.8 LSTD and equation 9.20
Comments.UserDisplayName: user75923
Tags: <reinforcement-learning><machine-learning><linear-regression><expectation><random-variable>
Title: How to compute an estimate of the expected value of a stochastic random variable in Reinforcement Learning?
UserDisplayName: user75923
ThreadText: # How to compute an estimate of the expected value of a stochastic random variable in Reinforcement Learning?
  
  (Asked by: username_0 on 2023-09-06)
  
  In the section on LSTD in SuttonBarto's book on RL, there is a proof on convergence of semi-gradient TD(0) using a linear function approximator.
  
  [![Point of convergence](https://i.sstatic.net/mJT3F.png)](https://i.sstatic.net/mJT3F.png)
  
  [![enter image description here](https://i.sstatic.net/wCB3x.png)](https://i.sstatic.net/wCB3x.png)
  
  Later on they estimated A and b as
  
  [![Estimate of A and b](https://i.sstatic.net/DQdQw.png)](https://i.sstatic.net/DQdQw.png)
  
  I was under the impression that to calculate an estimate of E[Rt+1\*xt], you would have to run multiple episodes till time t and then average those samples but how are they able to estimate **A** and **b** using samples from times 0 to t-1 instead?
  
  **Tags:** reinforcement-learning, machine-learning, linear-regression, expectation, random-variable
  > **Comments:**
  > **username_1**: Could you please confirm the edition, chapter/section and equation numbers you are looking at?  
  > **username_0**: @NeilSlater Section 9.8 LSTD and equation 9.20  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2023-09-06. Score: 0 | Accepted answer
  
  In TD(0) learning your are using a one-step bootstrapping equation:
  
  $$ V(s\_t) = r\_{t+1} + V(s\_{t+1}) $$
  
  So in order to calculate the value of state $s\_t$ you only do a one step look ahead and you bootstrap with the value of the next state $s\_{t+1}$ (read more [here](https://pi-tau.github.io/posts/actor-critic/#online-advantage-actor-critic)).
  
  Your value of each state is approximated by a function with weights $w$, and you optimize the weights with gradient descent. You try to make the old value $V\_{w\_{old}}(s\_t)$ closer to the new value $V\_{w}(s\_t) = r\_{t+1} + V\_{w\_{old}}(s\_{t+1})$ and the objective that you optimize is the least squares objective:
  
  $$ L =\frac{1}{2} \Big(V\_w(s\_t) - r\_{t+1} + V\_{w\_{old}}(s\_{t+1}) \Big)^2 $$
  
  The gradient of the objective is:
  
  $$ \nabla\_w L = \Big( r\_{t+1} + V\_{w\_{old}}(s\_{t+1}) - V\_w(s\_t) \Big) \nabla\_w V\_w(s\_t)$$
  
  Now, if you approximate the value function with a linear approximator, i.e. $V\_w(s\_t) = w^T x(s\_t)$, where $x(s\_t)$ is a vector of (usually) handcrafted features, then you have $\nabla\_w V\_w(s\_t) = x(s\_t)$, and for the gradient of the objective you get:
  
  \begin{align}
  \nabla\_w L &= \Big( r\_{t+1} + w^Tx(s\_{t+1}) - w^Tx(s\_t) \Big) x(s\_t) \\
  &= r\_{t+1} x(s\_t) - w^T \Big(x(s\_t) - x(s\_{t+1}) \Big) x(s\_t) \\
  &= r\_{t+1} x(s\_t) - x(s\_t) \Big(x(s\_t) - x(s\_{t+1}) \Big)^T w \\
  &= \textbf{b} - \textbf{A} w
  \end{align}
  
  Your gradient update rule would be:
  $$ w\_{new} = w + \alpha \nabla\_w L = w + \alpha \Big(\textbf{b} - \textbf{A} w\Big) $$
  
  Normally you would perform multiple time steps and at each step you will update the weights $w$. In LSTD, however, you perform multiple time steps, then you average $A$ and $b$ over these timesteps and then you compute the optimal $w$ with a single calculation by inverting $A$:
  $$ w\_{TD} = A^{-1}b $$
  
  **UPDATE:**  
  To see where these "expecations" come from imagine that you rollout your policy for $T$ steps, that is you collect $T$ (state $s\_t$, reward $r\_{t+1}$, next state $s\_{t+1}$) triples. For every triple you have to calculate the delta
  $$\Delta w = r\_{t+1} x(s\_t) - x(s\_t) \bigg( x(s\_t)-x(s\_{t+1}) \bigg)^T w$$
  and update the weights $ w' = w + \alpha \Delta w$.
  
  The optimal value of $w$ will be such that, after all updates are applied we have $w\_{new} = w\_{old}$. Thus, the sum of all updates has to be zero:
  \begin{align}
  \sum\_{(s\_t, r\_{t+1}, s\_{t+1}) \in \mathcal{D}} \Delta w &= 0 \\
  \sum\_{t=0}^T \Big( r\_{t+1} x(s\_t) - x(s\_t) \bigg( x(s\_t)-x(s\_{t+1}) \bigg)^T w \Big) &= 0 \\
  \sum\_{t=0}^{T} r\_{t+1} x(s\_t) - \sum\_{t=0}^{T} x(s\_t) \bigg( x(s\_t)-x(s\_{t+1}) \bigg)^T w &= 0 \\
  \frac{1}{T}\sum\_{t=0}^{T} r\_{t+1} x(s\_t) - \frac{1}{T}\sum\_{t=0}^{T} x(s\_t) \bigg( x(s\_t)-x(s\_{t+1}) \bigg)^T w &= 0
  \end{align}
  
  On the last row we divide both sides of the equation by $T$. From here you can see that:
  \begin{align}
  \textbf{b} &= \frac{1}{T} \sum\_{t=0}^{T} r\_{t+1}x(s\_t) \\
  &= \frac{1}{|\mathcal{D}|} \sum\_{(s\_t, r\_{t+1}, s\_{t+1}) \in \mathcal{D}} \Big[ r\_{t+1} x(s\_t) \Big] \\
  &= \mathbb{E}\_{(s\_t, r\_{t+1}, s\_{t+1}) \in \mathcal{D}} \Big[r\_{t+1} x(s\_t) \Big]
  \end{align}
  
  So $\textbf{b}$ is just the average of $ \bigg( r x(s) \bigg) $, which is by definition the expectation under the collected data.
  
  For me the quantity $\sum\_{t=0}^{T} r\_{t+1}x(s\_t)$ has much more meaning than this expectation. I think that they are using the expectation only to shorten the formula, but for me this is very misleading. Also they do not explicitly state **under what** is this expectation taken, which makes it even harder to read and understand.
  
  > **Comments:**
  > **username_0**: I understood the dervication of A and b but I dont get how you can estimate E[R_t+1] as average of rewards from time 0 to t-1. Since each reward at each timestep may have a different distribution, wouldn't the estimate be incorrect?  
  > **username_0**: Thank you so much, I had a vague understanding of expectations when it comes to stochastic random variables but your answer cleared it up. I agree that the formula in the book is very misleading. This is just one such case, there were other sections, for example, section 6.7 on maximisation bias.  
  
  ---
  
  