Temporal Difference (TD) learning, introduced by Rich Sutton in 1984, is a fundamental reinforcement learning method that combines ideas from Monte Carlo methods and dynamic programming.

Recap of Monte Carlo Methods

Recall that Monte Carlo methods estimate the value function by:

$$ V_\pi(s) = E[G_n | S_0 = s] $$

where:

  • $G_n = r_{n+1} + r_{n+2} + … + r_N$ is the return (sum of rewards until terminal state)
  • $N$ is the terminal instant of the episode

Monte Carlo methods work with sample average data collected over complete trajectories, requiring episodes to terminate before learning can occur.

TD Learning: Learning from Incomplete Episodes

Unlike Monte Carlo methods, TD learning doesn’t wait for the end of an episode. Instead, it updates estimates based on other estimates - a process called bootstrapping. Collecting returns in Monte Carlo methods is tedious and inefficient as we need the entire trajectory to play out. The key idea in TD learning is that we no longer look at:

$$ V_\pi(s) = E_\pi[G_n|S_n=s] $$

Instead, we look at the Bellman equation:

$$ V_\pi(s) = E_\pi[R_{n+1} + V_\pi(S_{n+1})|S_n=s] $$

Or equivalently:

$$ E_\pi[R_{n+1} + V_\pi(S_{n+1}) - V_\pi(s)|S_n=s] = 0 $$

This leads to the TD update rule, also known as TD recursion:

$$ V_{n+1}(s_n) = V_n(s_n) + \alpha(R_{n+1} + V_n(S_{n+1}) - V_n(s_n)) $$

For all states $s \neq s_n$, we maintain:

$$ V_{n+1}(s) = V_n(s) \quad \forall s \neq s_n $$

An alternative way to write this update rule using an indicator function is:

$$ V_{n+1}(s) = V_n(s) + \alpha I_{\{S_n=s\}}(R_{n+1} + V_n(S_{n+1}) - V_n(s)) $$

Where $\alpha$ is the learning rate and $I_{{S_n=s}}$ is an indicator function that equals 1 when $S_n=s$ and 0 otherwise.

TD(λ) Algorithm

The TD(λ) algorithm extends the basic TD learning by considering multi-step returns. The key idea is to consider the λ-step Bellman equation:

$$ V_\pi(i_n) = E_\pi \left[ \sum_{m=0}^{\ell} r(i_{n+m}, i_{n+m+1}) + V_\pi(i_{n+\ell+1}) \right] $$

Instead of looking at just single-step rewards as in TD(0), TD(λ) looks at multi-step returns. Since the value of ℓ is arbitrary, we can form a weighted average of all such Bellman equations.

Let’s define a parameter λ where 0 ≤ λ < 1. Since the infinite sum:

$$ \sum_{\ell=0}^{\infty} (1-\lambda)\lambda^\ell = 1 $$

We can write the following Bellman equation:

$$ V_\pi(i_n) = (1-\lambda)E_\pi \left[ \sum_{\ell=0}^{\infty} \lambda^\ell \left( \sum_{m=0}^{\ell} r(i_{n+m}, i_{n+m+1}) + V_\pi(i_{n+\ell+1}) \right) \right] $$

this becomes(derivation skipped):

$$ V_\pi(i_n) = E_\pi \left[ \sum_{m=0}^{\infty} \lambda^m \left( r(i_{n+m}, i_{n+m+1}) + V_\pi(i_{n+m+1}) - V_\pi(i_{n+m}) \right) \right] + V_\pi(i_n) $$

Recall that for all $k \geq N$ (terminal instant), $i_k = 0$, $r(i_k, i_{k+1}) = 0$, and $V_\pi(i_k) = 0$.

Let’s define the temporal difference term:

$$ d_m = r(i_m, i_{m+1}) + V_\pi(i_{m+1}) - V_\pi(i_m) $$

Then the above equation will become:

$$ V_\pi(i_n) = E_\pi \left[ \sum_{m=0}^{\infty} \lambda^m d_m \right] + V_\pi(i_n) $$
$$ = E_\pi \left[ \sum_{m=0}^{\infty} \lambda^{m-0} d_m \right] + V_\pi(i_n) $$

Since from the Bellman equation, $E_\pi[d_m] = 0$

Therefore, we can use this property to develop a stochastic approximation algorithm for estimating the value function. The stochastic approximation version can be written as:

$$ V(i_k) = V(i_k) + \alpha \sum_{m=k}^{\infty} \lambda^{m-k} d_m $$

where $d_m = r(i_m, i_{m+1}) + V(i_{m+1}) - V(i_m)$ and $\alpha$ is the step size or learning rate parameter.

As the number of iterations approaches infinity ($n \to \infty$), the value function estimate $V(i_k)$ converges to the true value function $V_\pi(i_k)$.

This forms the basis of TD(λ) (Temporal Difference Lambda) algorithm, which combines TD learning with eligibility traces to provide a spectrum of algorithms between TD(0) and Monte Carlo methods.

Special Cases of TD(λ)

Case 1: λ = 0 (TD(0) Algorithm)

When λ = 0, the TD(λ) algorithm simplifies to the basic TD(0) algorithm. In this case, the update equation becomes:

$$ V(i_k) = V(i_k) + \alpha d_k $$

where $d_k = r(i_k, i_{k+1}) + V(i_{k+1}) - V(i_k)$

This means that the value function is updated based only on the immediate reward and the value of the next state, without considering any future temporal differences. TD(0) is a one-step bootstrapping method that learns from incomplete episodes by using the current estimate of the value function.

The TD(0) update rule can be written more explicitly as:

$$ V(i_k) = V(i_k) + \alpha [r(i_k, i_{k+1}) + V(i_{k+1}) - V(i_k)] $$

This is a simple yet powerful update that moves the current value estimate toward the observed reward plus the estimated value of the next state.

Case 2: λ = 1 (TD(1) Algorithm)

When λ = 1, the TD(λ) algorithm becomes equivalent to the TD(1) algorithm. In this case, the update equation becomes:

$$ V(i_k) = V(i_k) + \alpha \sum_{m=k}^{\infty} d_m $$

We have seen earlier that the sum of TD terms equals the sum of rewards until termination. This can be shown as follows:

$$ \begin{align} \sum_{m=k}^{\infty} d_m &= \sum_{m=k}^{\infty} [r(i_m, i_{m+1}) + V(i_{m+1}) - V(i_m)] \\ &= \sum_{m=k}^{\infty} r(i_m, i_{m+1}) + \sum_{m=k}^{\infty} [V(i_{m+1}) - V(i_m)] \\ &= \sum_{m=k}^{\infty} r(i_m, i_{m+1}) + [V(i_{\infty}) - V(i_k)] \end{align} $$

Since $V(i_{\infty}) = 0$ for terminal states, this simplifies to:

$$ \sum_{m=k}^{\infty} d_m = \sum_{m=k}^{\infty} r(i_m, i_{m+1}) - V(i_k) $$

Therefore, the TD(1) update rule becomes:

$$ V(i_k) = V(i_k) + \alpha \left[ \sum_{m=k}^{\infty} r(i_m, i_{m+1}) - V(i_k) \right] $$

This gives us the Monte Carlo algorithm, as it updates the value function based on the complete return from state $i_k$ until the end of the episode.

For λ ∈ (0,1), we get a family of algorithms that interpolate between TD(0) and Monte Carlo methods, combining the advantages of both approaches. These algorithms use eligibility traces to assign credit to states visited in the past, with the strength of the credit determined by the λ parameter.

Why in TD learning i do not have to wait till the end of trajectory?

In Temporal Difference (TD) learning, you don’t have to wait until the end of a trajectory to update your value function estimates, which is a fundamental advantage over Monte Carlo methods. Here’s why: Monte Carlo vs TD Learning Monte Carlo methods require complete episodes because they estimate the value function using the actual returns: $$V_\pi(s) = E[G_n | S_0 = s]$$ where $G_n = r_{n+1} + r_{n+2} + … + r_N$ is the sum of all rewards until the terminal state. To calculate this return, you must wait until the episode ends (reaches state $N$) to collect all rewards. TD Learning’s Key Innovation: Bootstrapping TD learning uses a fundamentally different approach called bootstrapping: It leverages the Bellman equation: $$V_\pi(s) = E_\pi[R_{n+1} + V_\pi(S_{n+1})|S_n=s]$$ 2. Instead of waiting for the actual complete return, TD learning uses: The immediate reward $R_{n+1}$ The current estimate of the next state’s value $V_n(S_{n+1})$ The TD update rule is: $$V_{n+1}(s_n) = V_n(s_n) + \alpha(R_{n+1} + V_n(S_{n+1}) - V_n(s_n))$$ Why This Matters This means that after observing just a single transition $(s_n, a_n, r_{n+1}, s_{n+1})$, TD learning can immediately: Calculate the TD error: $\delta_n = R_{n+1} + V_n(S_{n+1}) - V_n(s_n)$ Update the value function Continue learning with each new step You don’t need to wait for the trajectory to complete because TD learning is continuously updating its estimates based on its current understanding of the environment, using each transition as a learning opportunity. This makes TD learning more efficient than Monte Carlo methods, especially in continuing environments where episodes might never terminate or in environments where episodes are very long.