Chapter 7 Temporal-Difference learning

In this section we will first introduce TD learning, which refers a wide range of algorithms. It can solve Bellman equation of a given policy $\pi$ without model. We refer TD learning in the first chapter specifically as a classic algorithm for estimating state values. Then we will introduce other algorithms belonging to the wide range of TD learning in the next section.

Basic TD learning algorithms

Recall the RM algorithm we learn in Chapter 6:

$$w_{k+1}=w_k-\alpha _k \tilde g(w_k,\eta_k),$$

where $\tilde g$ is the sample of our optimizing objective obtained through the model (e.g., expectation in mean estimation or the gradient expectation in the gradient descent).

In TD learning, our objective is estimating the state value. Recall that in the model-based methods, we derive state values through solving the Bellman equation (BE). But here we do not have models (TD learning is model free), so in essence, it is a special stochastic approximation algorithm for solving the BE. Recall the definition of the state value is

$$v_{\pi}(s) = \mathbb{E}[R_{t+1} + \gamma G_{t+1}|S_t = s], \quad s \in \mathcal{S}.$$

We can write it into another form by definition:

$$v_{\pi}(s) = \mathbb{E}[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s], \quad s \in \mathcal{S}.$$

Conditioning additionally on the action gives $q_\pi(s,a)=\mathbb{E}[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s,A_t=a]$. The sampled quantity inside this expectation is a one-step target, not the exact action value itself. Averaging action values over the policy gives:

$$v_{\pi}(s) = \mathbb{E}_{A\sim\pi(\cdot|s)}[q_\pi(s,A)], \quad s \in \mathcal{S}.$$

which we will see it in the Chapter 10. From this persepctive, we can also clearly understand the relationship between action value and state value.

Our objective is to find a value vector $v$ whose Bellman residual is zero:

$$g_s(v)=v(s)-\mathbb{E}_\pi[R_{t+1}+\gamma v(S_{t+1})|S_t=s]=0,\quad s\in\mathcal S.$$

A sample estimate of this residual is $v_t(s_t)-r_{t+1}-\gamma v_t(s_{t+1})$. Substituting it into RM gives the TD update. We use the convention that the TD error is target minus current estimate, consistently with Chapter 10:

$$\bar v_t=r_{t+1}+\gamma v_t(s_{t+1}),\qquad \delta_t=\bar v_t-v_t(s_t),\qquad v_{t+1}(s_t)=v_t(s_t)+\alpha_t(s_t)\delta_t.$$

Here, $\bar v_t$ is the TD target. The TD error $\delta_t$ measures how much this target exceeds the current estimate. It provides an innovation from the experience sample $(s_t,r_{t+1},s_{t+1})$. A truly terminal successor has value zero; equivalently, multiply the bootstrap term by $1-d_t$, where $d_t=1$ for true termination. This terminal convention also applies to the action-value targets below. A sampling time limit in a continuing task can still require bootstrapping from the actual final observation.

TD can update after one transition, while ordinary full-return MC waits until the episode ends to obtain its target. Both methods can maintain incremental value estimates; the distinction is whether the target requires a complete return.

Tabular TD policy evaluation converges under appropriate assumptions, including a fixed policy, sufficient state visits, and suitable step sizes. Stochastic approximation provides tools for this analysis; it does not guarantee convergence for every function approximator or off-policy setting.

Other TD learning algorithms

The TD algorithm can only estimate the state values of a given policy. To find optimal policies, we still need to further calculate the action values and then conduct policy improvement. In this section, we introduce the TD algorithms that can directly estimate action values.

These action-value methods can also be viewed through stochastic approximation: choose an appropriate expected backup and replace it with a sampled target. Here we introduce three algorithms: Sarsa, n-step Sarsa, and Q-learning.

Sarsa

For Sarsa, We can replace state value estimation with action value estimation. The expression of the action value can be written as:

$$q_\pi(s, a) = \mathbb{E} [R + \gamma q_\pi(S', A') | s, a], \quad \text{for all } (s, a).$$

This can be understood as follows: q value equals the immediate reward plus the future reward for reaching the next state. Since the next state is unknown, its state value can be obtained by considering all action values ​​in the next step after that. Therefore, we can view it as first fixing the next state $s'$, then calculating the expectation of all actions $a$ in that state to obtain the state value of $s'$. Finally, we calculate the expectation of $s'$ to obtain the future reward for state $s$.

So the expression of Sarsa can be written as:

$$\begin{aligned} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t) \big[ q_t(s_t, a_t) - (r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})) \big], \\ q_{t+1}(s, a) &= q_t(s, a), \quad \text{for all } (s, a) \neq (s_t, a_t), \end{aligned}$$

For Sarsa, we the experience samples $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$.

Sarsa

n-step Sarsa

This section introduces n-step Sarsa, an extension of Sarsa. We will see that Sarsa and MC learning are two extreme cases of n-step Sarsa.Recall that the definition of the action value is

$$q_\pi(s, a) = \mathbb{E}[G_t|S_t = s, A_t = a], \quad (7.16)$$

where $G_t$ is the discounted return satisfying

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$$

We can construct targets that use different numbers of actual rewards before bootstrapping. The expressions below use the true $q_\pi$ to show their expectation relationship; an implementation replaces it with a current estimate:

$$\begin{aligned} \text{Sarsa} \longleftarrow \quad & G_t^{(1)} = R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}), \\ & G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 q_\pi(S_{t+2}, A_{t+2}), \\ & \vdots \\ n\text{-step Sarsa} \longleftarrow \quad & G_t^{(n)} = \sum_{k=0}^{n-1}\gamma^k R_{t+k+1} + \gamma^n q_\pi(S_{t+n}, A_{t+n}), \\ & \vdots \\ \text{MC} \longleftarrow \quad & G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} \dots \end{aligned}$$

These targets are generally different random variables, not equal sample by sample. Under the same fixed policy, with true $q_\pi$ in the bootstrap and correct terminal handling, their conditional expectations agree:

$$\mathbb E_\pi[G_t|S_t=s,A_t=a] =\mathbb E_\pi[G_t^{(n)}|S_t=s,A_t=a] =q_\pi(s,a).$$

For an episode ending at $T\leq t+n$, sum rewards only through $R_T$ and omit the bootstrap. If the bootstrap uses an approximate action value, its error may introduce bias relative to $q_\pi$. The sampled targets can have different variances even when their expectations are equal.

• When $n = 1$, we have

$$q_\pi(s, a) = \mathbb{E}[G_t^{(1)}|s, a] = \mathbb{E}[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1})|s, a].$$

The corresponding stochastic approximation algorithm for solving this equation is

$$q_{t+1}(s_t, a_t) = q_t(s_t, a_t) - \alpha_t(s_t, a_t) \Big[ q_t(s_t, a_t) - (r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})) \Big],$$

which is the Sarsa algorithm.

• When $n = \infty$, we have

$$q_\pi(s, a) = \mathbb{E}[G_t^{(\infty)}|s, a] = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots |s, a].$$

The corresponding algorithm for solving this equation is

$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)+\alpha_t(s_t,a_t)[g_t-q_t(s_t,a_t)], \qquad g_t=\sum_{k=0}^{T-t-1}\gamma^k r_{t+k+1}.$$

Here $g_t$ is the complete sampled return of a terminating episode. Setting $\alpha_t=1$ replaces the estimate with one return, but averaging over repeated visits is needed to reduce sampling noise. A step size of $1/N(s_t,a_t)$ gives the incremental sample mean.

• For a general value of $n$, we have

$$q_\pi(s, a) = \mathbb{E}[G_t^{(n)}|s, a] = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \dots + \gamma^n q_\pi(S_{t+n}, A_{t+n})|s, a].$$

The corresponding algorithm for solving the above equation is

$$\begin{aligned} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) \\ &\quad - \alpha_t(s_t, a_t) \Big[ q_t(s_t, a_t) - (r_{t+1} + \gamma r_{t+2} + \dots + \gamma^n q_t(s_{t+n}, a_{t+n})) \Big]. \quad (7.17) \end{aligned}$$

This algorithm is called n-step Sarsa.

In summary, n-step Sarsa becomes one-step Sarsa for $n=1$. When the backup reaches the end of an episode and contains no bootstrap term, it becomes an MC update with the chosen step size; $\alpha_t=1$ is not required. A nonterminal n-step update waits for the experience through time $t+n$. If the episode ends earlier, the remaining returns can be calculated at termination.

To that end, the q value in n-step Sarsa can be rewritten as

$$\begin{aligned} q_{t+n}(s_t, a_t) &= q_{t+n-1}(s_t, a_t) \\ &\quad - \alpha_{t+n-1}(s_t, a_t) \Big[ q_{t+n-1}(s_t, a_t) - (r_{t+1} + \gamma r_{t+2} + \dots + \gamma^n q_{t+n-1}(s_{t+n}, a_{t+n})) \Big], \end{aligned}$$

Here $q_{t+n}(s_t,a_t)$ is the estimate at time $t+n$. Larger n uses more actual rewards and less immediate dependence on an approximate bootstrap, often reducing bootstrap bias while increasing variance. This is a common trade-off, not a guarantee that performance or variance changes monotonically with n. The algorithm above evaluates a given policy and must be combined with policy improvement for control.

Q-learning

Sarsa based algorithms are solving BE, followed by policy improvement to iteratively derive the optimal policy. Q-learning directly solve the BOE. The BOE want to find the policy that maximizes the state value. And the state value is maximized by choosing the action with maximum value. So the BOE in the q-value form can be written as

$$q(s, a) = \mathbb{E} \Big[ R_{t+1} + \gamma \max_a q(S_{t+1}, a) \Big| S_t = s, A_t = a \Big].$$

So Q-learning can be written as:

$$\begin{aligned} q_{t+1}(s_t, a_t) &= q_t(s_t, a_t) - \alpha_t(s_t, a_t) \bigg[ q_t(s_t, a_t) - \Big( r_{t+1} + \gamma \max_{a \in \mathcal{A}(s_{t+1})} q_t(s_{t+1}, a) \Big) \bigg], \\ q_{t+1}(s, a) &= q_t(s, a), \quad \text{for all } (s, a) \neq (s_t, a_t), \end{aligned}$$

Proof of the BOE in q-value

By the definition of expectation, we have

$$q(s, a) = \sum_r p(r|s, a)r + \gamma \sum_{s'} p(s'|s, a) \max_{a \in \mathcal{A}(s')} q(s', a).$$

Taking the maximum of both sides of the equation gives

$$\max_{a \in \mathcal{A}(s)} q(s, a) = \max_{a \in \mathcal{A}(s)} \left[ \sum_r p(r|s, a)r + \gamma \sum_{s'} p(s'|s, a) \max_{a \in \mathcal{A}(s')} q(s', a) \right].$$

By denoting $v(s) \doteq \max_{a \in \mathcal{A}(s)} q(s, a)$, we can rewrite the above equation as

$$\begin{aligned} v(s) &= \max_{a \in \mathcal{A}(s)} \left[ \sum_r p(r|s, a)r + \gamma \sum_{s'} p(s'|s, a) v(s') \right] \\ &= \max_\pi \sum_{a \in \mathcal{A}(s)} \pi(a|s) \left[ \sum_r p(r|s, a)r + \gamma \sum_{s'} p(s'|s, a) v(s') \right], \end{aligned}$$

which is clearly the BOE.

on-policy and off-policy

Two policies exist in any reinforcement learning task: a behavior policy and a target policy. The behavior policy is the one used to generate experience samples. The target policy is the one that is constantly updated to converge to an optimal policy. When the behavior policy is the same as the target policy, such a learning process is called on-policy. Otherwise, when they are different, the learning process is called off-policy.

Off-policy learning can use data from other policies, such as an exploratory controller or a human operator, while learning about a target policy. This can improve data reuse, but sufficient coverage remains essential. Neither on-policy nor off-policy learning automatically guarantees efficient exploration or an optimal result from an arbitrary dataset.

The ordinary Sarsa and MC algorithms introduced here are on-policy. MC also has off-policy variants, for example those using importance sampling to correct the mismatch between behavior and target policies.

Q-learning is an off-policy algorithm because its max backup targets a greedy policy even when behavior is exploratory. The behavior may happen to be greedy too, but this does not remove the algorithm's ability to learn off-policy. Purely greedy behavior can fail to visit useful actions, so coverage must still be considered.

Q-learning on-policy

Q-learning off-policy

Another concept that may be confused with on-policy/off-policy is online/offline. Online learning refers to the case where the agent updates the values and policies while interacting with the environment. Offline learning refers to the case where the agent up dates the values and policies using pre-collected experience data without interacting with the environment. If an algorithm is on-policy, then it can be implemented in an online fashion, but cannot use pre-collected data generated by other policies. If an algorithm is off-policy, then it can potentially use either online or offline data. However, ordinary off-policy DQN or SAC does not automatically solve offline RL: limited coverage and inaccurate values for out-of-distribution actions can make learning from a fixed dataset unreliable.

Summary

Algorithm	Expression of the TD target $\bar{q}_t$
Sarsa	$\bar{q}_t = r_{t+1} + \gamma q_t(s_{t+1}, a_{t+1})$
$n$-step Sarsa	$\bar{q}_t = r_{t+1} + \gamma r_{t+2} + \dots + \gamma^n q_t(s_{t+n}, a_{t+n})$
Q-learning	$\bar{q}_t = r_{t+1} + \gamma \max_a q_t(s_{t+1}, a)$
Monte Carlo	$\bar{q}_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots$

Algorithm	Equation to be solved
Sarsa	BE: $q_\pi(s, a) = \mathbb{E}[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]$
$n$-step Sarsa	BE: $q_\pi(s, a) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \dots + \gamma^n q_\pi(S_{t+n}, A_{t+n}) | S_t = s, A_t = a]$
Q-learning	BOE: $q(s, a) = \mathbb{E}[R_{t+1} + \gamma \max_a q(S_{t+1}, a) | S_t = s, A_t = a]$
Monte Carlo	BE: $q_\pi(s, a) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots | S_t = s, A_t = a]$

*Table : A unified point of view of TD algorithms.