TD Fixed Point

TD Fixed Point

The TD fixed point ${\mathbf{w}}_{TD}$ is the weight vector where the expected semi-gradient TD(0) update is zero. For Linear Function Approximation, this is the unique solution to $\mathbf{Aw}=\mathbf{b}$.

TD Fixed Point Equation

$\mathbf{A}{\mathbf{w}}_{TD}=\mathbf{b}$ where: $\mathbf{A}=\mathbb{E}\left[\mathbf{x}(S_t){\left(\mathbf{x}(S_t)-\gamma \mathbf{x}(S_{t+1})\right)}^{\top }\right]$ $\mathbf{b}=\mathbb{E}\left[R_{t+1}\mathbf{x}(S_t)\right]$

Error Bound

TD Fixed Point Error Bound

$\overline{VE}({\mathbf{w}}_{TD})\le \frac{1}{1-\gamma }{\min }_{\mathbf{w}}\overline{VE}(\mathbf{w})$

The error at the TD fixed point is at most $\frac{1}{1-\gamma }$ times the best possible error with the given features.

Not the Minimum

The TD fixed point is generally NOT the $\mathbf{w}$ that minimizes $\overline{VE}$. MC gradient descent finds the true minimum; TD finds a different (potentially worse) point. The bound above quantifies how much worse it can be.

Connections

• Solved by: LSTD (directly), Semi-gradient TD (iteratively)
• Only guaranteed for: Linear Function Approximation

Appears In

• RL-L06 - On-Policy TD with Approximation, RL-Book Ch9 - On-Policy Prediction with Approximation