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

enter image description here

Later on they estimated A and b as

Estimate of A and b

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?

  • $\begingroup$ Could you please confirm the edition, chapter/section and equation numbers you are looking at? $\endgroup$ Commented Sep 6, 2023 at 7:19
  • 1
    $\begingroup$ @NeilSlater Section 9.8 LSTD and equation 9.20 $\endgroup$
    – user75923
    Commented Sep 6, 2023 at 10:31

1 Answer 1


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

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

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.

  • 1
    $\begingroup$ 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? $\endgroup$
    – user75923
    Commented Sep 6, 2023 at 10:16
  • $\begingroup$ 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. $\endgroup$
    – user75923
    Commented Sep 8, 2023 at 18:22

You must log in to answer this question.

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