temporal difference

From David Silver's slides: TD-learning 'updates a guess towards a guess'.

Sutton and Barto define the temporal difference error as the difference between the value estimate for the current state and the updated value estimate after transitioning to the next state, including any reward accrued during the transition:

The overall value estimation error across a trajectory can be straightforwardly written as the telescoping sum of TD errors.

The simple learning algorithm that updates the value function to reduce one-step TD error

is called TD(0). We can also update to reduce $n$-step error for arbitrary $n$: in general, let

be the $n$-step return. Then the $n$-step TD-learning update can be written

Letting $n\to\infty$ we recover the unbiased Monte Carlo value estimate

smaller values of $n$ introduce bias to reduce variance (bias-variance tradeoff).

We can even look at the infinite weighted average of future returns

and update towards this!For a finite trajectory length $T$ we would write $v_t^{\lambda} = (1 - \lambda)\sum_{n=1}^{T-t-1} \lambda^{n-1} v^{(n)}_t + \lambda^{T-t-1} v_t$, implicitly using the empirical return $v_t$ for all post-termination steps. This is called $TD(\lambda)$, where $\lambda\to 1$ recovers the unbiased Monte Carlo estimate.

Forward and backward perspectives

Naively, to do a TD($\lambda$) update we'd need to see 'into the future' all the way to the end of the trajectory. This forward view is nice in theory, but a pain to implement and inefficient because it doesn't learn anything until the very end of the trajectory. In practice we implement the backward view, where at each new state we update all previous state values with the appropriate signal from the current TD error.

Concretely, consider an infinite-length trajectory $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, r_{t+2}, \ldots)$ from the policy $\pi$. The TD($\lambda$) update for $V(s_1)$ from this trajectory is

where the change to the value estimate $\delta_t^\lambda := v_t^\lambda - V(s_t)$ is given by

We see that the update includes terms for all future TD-errors, where the error at step $t+n$ is incorporated into the update at step $t$ with weight $(\lambda\gamma)^n$. This justifies the backward view implementation of TD($\lambda$), in which at each step we update the value estimate for the state from $n$ steps ago (for all $n$) by the current TD error with weight $(\lambda\gamma)^n$. Note that a given state can appear multiple times in the state history, so its total weight may be a sum; e.g., $(\lambda\gamma)^{n_1} + (\lambda\gamma)^{n_2}$ for a state visited twice, at $n_1$ and $n_2$ steps before the current step respectively. The vector containing these per-state total weights is called an eligibility trace.

Note that online updates introduce non-stationarity: although the forward and backward views give equivalent updates in an offline setting, this is no longer true when we apply the backward updates online, since the update at time $t$ can change the value estimates at steps $>t$.

We could define a more rigorous version of online TD-learning:

1. At step $1$, update our initial value estimates $V_0$ using $\delta_1$. Call this updated array of state-values $V_1$.
2. At step 2, where naive online TD($\lambda$) would simply update $V_1$ using $\delta_2$, we instead:
   1. Redo the original $V_0\rightarrow V_1$ update now using the two-step return $\delta_1 + (\lambda\gamma)\delta_2$.
   2. Now recompute $\delta_2'$ using the updated $V_1'$, and use that to compute $V_2.$
3. Continue, so that at each step $t$ you iteratively redo all $t$ updates using the $\lambda$-return at the current horizon.

This algorithm, which Sutton and Barto call the 'online $\lambda$-return algorithm' is computationally impractical, but conceptually nice. Intuitively, at each step we pretend that we've reached the end of the episode and compute the value updates prescribed by forward-view (offline) TD($\lambda$) for all states in order, each using the updated values from the previous states. Apparently this often performs better in practice than online TD($\lambda$).

The online $\lambda$-return algorithm can be made practical in 'nice' settings (tabular or linear value function approximation) by formulating it as an online algorithm using a more complicated eligibility trace called a Dutch trace (as opposed to the eligibility traces used by TD($\lambda$), which are called accumulating traces). Sutton and Barto call this algorithm 'True online TD($\lambda$)'. Apparently this doesn't work in the general case of nonlinear function approximation, though.

Q-learning

Adapting TD-learning methods to action values gives Q-learning and related methods.