Temporal-Difference Learning

Temporal-Difference (TD) learning is a central approach in Reinforcement Learning (RL) that combines ideas from both Monte Carlo Methods and Dynamic Programming. It is a model-free learning method where an agent learns to predict a value function by bootstrapping from its current estimate of that value function, updating predictions incrementally after each step rather than waiting for the end of an episode.

---

Core Characteristics

1. Model-Free

TD methods do not require a model of the environment’s dynamics (i.e., state transition probabilities or reward functions). The agent learns solely through direct interaction and raw experience.

2. Bootstrapping

Unlike Monte Carlo methods, which wait until the end of an episode to update state values based on the actual total return, TD learning updates estimates based on other learned estimates. It updates predictions using the immediate reward and the discounted estimated value of the subsequent state.

3. Online & Incremental Updates

Because updates occur step-by-step during an episode, TD learning can be applied to continuous or very long tasks (infinite horizon) where episodes might not have a defined end.

---

Core Formulas

TD(0) Prediction

The simplest form of TD learning, TD(0), updates the estimated state-value function $V(s_t)$ as follows:

$V(s_t)\leftarrow V(s_t)+\alpha \left[r_{t+1}+\gamma V(s_{t+1})-V(s_t)\right]$

Where:

• $\alpha$ is the learning rate (step-size parameter).
• $\gamma$ is the discount factor ($0\le \gamma \le 1$).
• $r_{t+1}$ is the reward received after transitioning from state $s_t$.
• $r_{t+1}+\gamma V(s_{t+1})-V(s_t)$ is the TD Error, which measures the discrepancy between the estimate at time $t$ and the better estimate at $t+1$.

On-Policy Control: SARSA

SARSA (State-Action-Reward-State-Action) is an on-policy control method that updates the action-value function $Q(s_t,a_t)$ using the action $a_{t+1}$ actually chosen by the current policy:

$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right]$

Off-Policy Control: Q-Learning

Q-learning is an off-policy control method that updates the action-value function $Q(s_t,a_t)$ by assuming the optimal action will be chosen in the next state, regardless of the agent’s behavior policy:

$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a)-Q(s_t,a_t)\right]$

---

Related Topics

• Markov Decision Process (MDP): The formal mathematical framework for modeling decision-making in reinforcement learning.
• Dynamic Programming (DP): A collection of algorithms used to compute optimal policies given a perfect model of the environment.
• Monte Carlo Methods: Methods that learn value functions and optimal policies from sample paths/episodes without bootstrapping.
• Eligibility Traces (TD($\lambda$)): A generalization of TD learning that bridges TD(0) and Monte Carlo methods using a decay parameter $\lambda$.
• Function Approximation: The use of models (e.g., neural networks in deep reinforcement learning) to estimate value functions in large or continuous state spaces.