Advantages of TD Learning over MC

While Monte Carlo (MC) methods provide an intuitive way to learn from experience by averaging complete returns, Temporal-Difference (TD) learning often presents several significant advantages, making it a more widely used approach in many Reinforcement Learning scenarios.

Learning from Incomplete Episodes and Continuing Tasks

The most difference is when learning updates occur. MC methods require waiting until the end of an episode to determine the return $G_t$ before any value estimate for states visited in that episode can be updated.

MC updates (left) use the outcome of the entire episode, while TD updates (right) use only the next reward and the estimated value of the next state.

TD methods, in contrast, update their value estimates after just one time step, using the observed reward $R_{t+1}$ and the current estimate of the next state's value $V(S_{t+1})$. The TD(0) update rule, for instance, looks like this:

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

This ability to learn from a single transition ($S_t, A_t, R_{t+1}, S_{t+1}$) has profound implications:

1. Applicability to Continuing Tasks: Many RL problems don't have well-defined episodes. Consider controlling a chemical process, managing an investment portfolio, or a robot operating continuously. These are continuing tasks that theoretically run forever. MC methods cannot be directly applied as there's no "final outcome" to wait for. TD methods, updating step-by-step, handle these scenarios naturally.
2. Efficiency in Long Episodes: Even in episodic tasks, if episodes are very long (e.g., a complex game like Go, or long simulations), waiting for the episode conclusion significantly delays learning. TD provides much more frequent updates, allowing the agent to learn and potentially improve its behavior mid-episode.

Online Learning Capability

TD learning is inherently suited for online learning. The agent can observe a transition, receive a reward, move to the next state, and immediately update the value of the state it just left. This allows the agent to adapt its knowledge and potentially its behavior "on the fly" as it interacts with the environment.

MC methods typically operate offline. An entire episode is collected first, then the returns are calculated, and finally, the value estimates for all visited states in that episode are updated. This requires storing the episode trajectory (states, actions, rewards) until termination. While offline updates are feasible, online learning is often desirable for systems that need to adapt in real time or have memory constraints.

Lower Variance Updates and Convergence Speed

While MC updates use the actual, sampled return $G_t$, which is an unbiased estimate of the true value $v_\pi(S_t)$, this return can have high variance. The final outcome $G_t$ depends on a potentially long sequence of actions, state transitions, and rewards, each contributing randomness. High variance in the target update value can make the learning process noisy and slow to converge.

TD methods update towards a TD target: $R_{t+1} + \gamma V(S_{t+1})$ (for value prediction) or $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ (for Q-learning). This target depends on only one random reward $R_{t+1}$ and one random transition to $S_{t+1}$. The value estimate $V(S_{t+1})$ or $Q(S_{t+1}, A_{t+1})$ itself is used in the update (this is the bootstrapping).

Because the TD target depends on fewer random events than the full MC return, it generally has much lower variance. However, this comes at a cost: the TD target is biased. It uses the current estimate $V(S_{t+1})$, which is likely not perfectly accurate, especially early in learning.

This introduces a classic bias-variance trade-off:

• MC: High variance, zero bias (using the actual sample return).
• TD: Lower variance, some bias (using an estimated value).

In practice, the lower variance of TD updates often leads to faster convergence than MC methods, despite the bias. The learning process tends to be smoother and less sensitive to individual noisy episodes.

Summary of Advantages

To recap, the primary advantages of TD learning over MC methods include:

• Learns without waiting for episode end: Enables learning in continuing tasks and provides faster updates in long episodic tasks.
• Online learning: Updates can occur step-by-step during interaction.
• Lower variance: Updates are based on single transitions, usually resulting in less noisy learning and faster convergence in practice compared to high-variance full returns.

These benefits make TD methods like SARSA and Q-Learning foundational algorithms in reinforcement learning, particularly for problems where episodes are long, non-existent, or where online adaptation is important. However, it's also worth remembering that the bias introduced by bootstrapping in TD can sometimes cause issues, especially when combined with function approximation, a topic we'll explore later.