Temporal Difference Learning Methods

While Dynamic Programming methods like Value and Policy Iteration provide a formal way to find optimal policies in Markov Decision Processes (MDPs), they rely on a complete model of the environment, knowing all transition probabilities $P(s'|s, a)$ and rewards $R(s, a, s')$. Such a model is unavailable in many practical scenarios. This is where Temporal Difference (TD) learning methods become indispensable. TD learning allows agents to learn directly from raw experience, interacting with the environment (or using logged interactions) without needing explicit knowledge of its dynamics.

TD methods blend ideas from both Monte Carlo (MC) methods and Dynamic Programming (DP). Like MC, TD methods learn from samples of experience. However, like DP, TD methods bootstrap: they update estimates based on other learned estimates, rather than waiting for the final outcome of an episode as MC methods do. This typically leads to faster learning, especially in long or continuous tasks.

TD(0) Prediction: Learning State Values

The simplest TD method, often called TD(0) or one-step TD, focuses on the prediction problem: estimating the state-value function $V^\pi(s)$ for a given policy $\pi$. After taking action $A_t$ in state $S_t$ and observing the reward $R_{t+1}$ and the next state $S_{t+1}$, TD(0) updates the value estimate for state $S_t$ using the following rule:

$$V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$$

Let's break down this update:

1. Target: The term $R_{t+1} + \gamma V(S_{t+1})$ is the TD target. It's an estimate of the return starting from state $S_t$. It uses the immediate reward $R_{t+1}$ and bootstraps using the current estimate of the value of the next state, $V(S_{t+1})$.
2. TD Error: The difference $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the TD error. It measures the discrepancy between the estimated value of $S_t$ before the update and the better-informed TD target calculated after observing the transition.
3. Learning Rate: $\alpha$ is the learning rate (step size), controlling how much the TD error influences the update.

The TD(0) update adjusts the current value estimate $V(S_t)$ in the direction suggested by the TD error. Because it uses $V(S_{t+1})$ (an estimate) in its target, it introduces some bias compared to MC methods (which use the actual full return $G_t$). However, TD updates typically have significantly lower variance than MC updates, as the target depends only on the next reward and state value estimate, not the entire sequence of future rewards in an episode.

SARSA: On-Policy TD Control

To move from prediction to control (finding an optimal policy), we need to estimate action-value functions, $Q(s, a)$. SARSA is an on-policy TD control algorithm that learns $Q(s, a)$ directly from experience. The name "SARSA" stands for the tuple of information involved in the update: $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$.

The agent starts in state $S_t$, chooses action $A_t$ (according to its current policy, often $\epsilon$-greedy), observes reward $R_{t+1}$ and next state $S_{t+1}$, and then chooses the next action $A_{t+1}$ (again, according to its policy). The SARSA update rule is then applied to the Q-value of the initial state-action pair $(S_t, A_t)$:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]$$

Notice the similarity to the TD(0) update. The TD target is now $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$, using the Q-value of the next state and the next action actually taken. Because the update depends on the action $A_{t+1}$ chosen by the current policy, SARSA is an on-policy algorithm. It learns the value of the policy it is currently following, including the effects of its exploration strategy (like $\epsilon$-greedy choices).

The SARSA update process relies on the sequence of state, action, reward, next state, and importantly, the next action selected by the policy.

Q-Learning: Off-Policy TD Control

Q-Learning is another fundamental TD control algorithm, but with a significant difference: it is off-policy. This means it learns the optimal action-value function $Q^*(s, a)$ directly, regardless of the policy being followed to generate the experience (the behavior policy), as long as that policy explores sufficiently.

The Q-Learning update rule is:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t)]$$

The important difference lies in the TD target: $R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a')$. Instead of using the Q-value of the next action actually taken ($A_{t+1}$), Q-Learning uses the Q-value of the action $a'$ that maximizes the Q-function estimate in the next state $S_{t+1}$. This implicitly assumes that the optimal (greedy) action will be taken from state $S_{t+1}$ onwards, effectively learning about the optimal policy $\pi^*$ while potentially following a different, more exploratory behavior policy (like $\epsilon$-greedy).

This off-policy nature makes Q-Learning powerful. It can learn from past experience generated by different policies, or even from observing human demonstrators. However, combining off-policy learning, bootstrapping (inherent in TD methods), and function approximation (necessary for large state spaces) can lead to instability, a phenomenon known as the 'Deadly Triad', which we will discuss shortly.

Summary and Next Steps

TD methods (TD(0), SARSA, Q-Learning) provide efficient, model-free ways to learn value functions directly from experience. They update estimates based on other estimates (bootstrapping), allowing learning before the end of an episode. SARSA is on-policy, learning the value of the behavior policy, while Q-Learning is off-policy, directly estimating the optimal value function.

These tabular methods are foundational. However, their reliance on lookup tables for value functions restricts them to problems with relatively small, discrete state and action spaces. To handle the immense state spaces encountered in complex problems (like robotics control from camera images or playing complex games), we need to generalize these value functions using function approximators, such as linear functions or deep neural networks. The next section introduces this concept, setting the stage for the deep reinforcement learning techniques that form the core of this course and highlighting the challenges that arise when combining TD learning with powerful function approximators.