Learning from Incomplete Episodes

Monte Carlo (MC) methods estimate value functions by averaging the returns observed after completing entire episodes. This approach is akin to judging the quality of a multi-day hike only after reaching the final destination and tallying up all experiences. While effective, MC methods have a primary limitation: learning occurs only after an episode is finished. For very long or even continuous tasks—those that never end—waiting for a final outcome is often impractical or impossible.

Temporal-Difference (TD) learning provides a different approach. Instead of waiting for the end of an episode to know the final return $G_t$, TD methods update the value estimate for a state $S_t$ based on the immediate reward $R_{t+1}$ received and the current estimated value of the next state $S_{t+1}$.

Consider being at state $S_t$, taking action $A_t$, receiving reward $R_{t+1}$, and landing in state $S_{t+1}$.

• MC methods would wait until the end of the episode (time $T$) to compute the actual return $G_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{T-t-1} R_T$. They would then use this $G_t$ as the target to update $V(S_t)$.
• TD methods, specifically the simplest form TD(0) which we'll detail soon, form a target using only the next step's information: the immediate reward $R_{t+1}$ plus the discounted current estimate of the next state's value, $\gamma V(S_{t+1})$. The target for the update at time $t$ is $R_{t+1} + \gamma V(S_{t+1})$.

This process of updating an estimate based partially on another learned estimate is called bootstrapping. TD learning bootstraps because the update to $V(S_t)$ relies on the existing estimate $V(S_{t+1})$. It's like adjusting your estimated travel time from City A to City Z based on reaching City B and using your current estimate of the travel time from City B to City Z, rather than waiting until you actually arrive at City Z.

Comparison of update timing. MC methods wait until the episode ends (state $S_T$) to calculate the actual return $G_t$ and update values for states visited in that episode. TD methods update the value of a state (e.g., $V(S_0)$) shortly after visiting it (at the next step, $t+1$), using the observed reward ($R_1$) and the current estimate of the next state's value ($V(S_1)$).

This ability to learn from each step, rather than waiting for the end of an episode, gives TD methods several advantages:

1. Online Learning: TD methods can learn after every single step. They don't need to wait for an episode to complete, making them suitable for continuous tasks where episodes might never technically end.
2. Efficiency: TD methods often converge faster than MC methods in practice on supervised learning benchmarks derived from Markov Reward Processes. They spread information about rewards more gradually but frequently.
3. No Need for Final Outcome: They can learn in environments where the final outcome isn't always available or when episodes are very long.

TD learning combines ideas from both Monte Carlo methods and Dynamic Programming (DP). Like MC, it learns directly from raw experience without requiring a model of the environment's dynamics (the transition probabilities $p(s', r | s, a)$). Like DP, it uses bootstrapping to update estimates based on other estimates. This blend makes TD methods central to modern reinforcement learning.

In the following sections, we will formalize this idea, starting with the TD(0) algorithm for estimating state values, and then move on to control algorithms like SARSA and Q-learning that learn action values.