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.
Later on they estimated A and b as
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?
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 $$
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.
