Temporal Difference (TD) Learning

Bootstrapping is the defining mechanism of TD Learning. Unlike Monte Carlo methods that must wait until the end of an episode to know the final return, TD methods update their value estimates based on other, existing estimates. They 'bootstrap' by combining the immediate observed reward with the discounted value estimate of the next state. This allows for online, incremental updates after every time step, without requiring a complete model of the environment or a finished episode. The canonical TD update rule is: V(S_t) ← V(S_t) + α [R_{t+1} + γV(S_{t+1}) - V(S_t)], where the term in brackets is the TD error.

TD Learning is fundamentally model-free. It does not require or learn an explicit model of the environment's dynamics (the transition probability function P or the reward function R). Instead, the agent learns directly from raw experience in the form of sample sequences of states, actions, and rewards. This makes TD highly practical for complex domains like robotics or game playing, where the true dynamics are unknown or exceedingly difficult to model accurately. The agent learns a value function or policy purely through interaction and temporal difference updates.

TD algorithms are designed for online learning. Updates can be made after every single time step (TD(0)) or after a short sequence of steps (n-step TD). This incremental nature provides several key advantages:

• Memory Efficiency: The agent does not need to store long trajectories.
• Rapid Feedback: Learning and policy improvement occur continuously during interaction.
• Applicability to Continuing Tasks: TD methods naturally handle non-episodic, infinite-horizon problems. This contrasts with Monte Carlo methods, which are inherently episodic and require a terminal state to compute returns.

TD Learning represents a synthesis of two classical ideas. From Dynamic Programming (DP), it borrows the concept of bootstrapping—using existing estimates to update other estimates. From Monte Carlo (MC) methods, it takes the idea of learning from actual experience rather than from a complete model. TD is often described as a middle ground: like MC, it learns from samples; like DP, it updates estimates based on other estimates. The TD(λ) algorithm, via the use of an eligibility trace, creates a smooth continuum between pure TD (TD(0)) and pure Monte Carlo (as λ approaches 1).

The core learning signal in TD is the TD error (δ_t). It is calculated as: δ_t = R_{t+1} + γV(S_{t+1}) - V(S_t). This scalar signal has profound interpretations:

• Neurological: It resembles the phasic activity of dopamine neurons in the brain, signaling a deviation from expected outcomes.
• Computational: It represents the surprise or the difference between the newly observed outcome and the old prediction.
• Mathematical: It is an unbiased estimate of the error in the current value function. The agent's entire learning process is driven by minimizing this TD error across experiences, often via stochastic gradient descent.

Simple TD prediction forms the cornerstone of most modern, scalable reinforcement learning algorithms. Key developments built directly upon TD principles include:

• Q-Learning: An off-policy TD control algorithm that learns the optimal action-value function.
• SARSA: An on-policy TD control algorithm.
• Deep Q-Networks (DQN): Combines Q-Learning with deep neural networks and experience replay.
• Actor-Critic Methods: The 'Critic' component is almost always a TD-based value function estimating the advantage or value of states. Algorithms like A3C, PPO, and SAC all rely on a TD-learning critic for stable and efficient policy gradient updates.

TD(0) is the simplest temporal difference algorithm. It performs a one-step lookahead, updating the value estimate for a state based on the immediate reward and the estimated value of the next state. Its update rule is:

V(S_t) ← V(S_t) + α [R_{t+1} + γV(S_{t+1}) - V(S_t)]

• α (alpha) is the learning rate.
• γ (gamma) is the discount factor.
• The term in brackets [ ... ] is the TD error, the difference between the new estimate (R + γV(S')) and the old estimate (V(S)).

This is a bootstrapping method because it uses the current estimate V(S_{t+1}) to update another estimate V(S_t), learning from incomplete episodes without waiting for a final outcome.

SARSA (State-Action-Reward-State-Action) is an on-policy TD control algorithm that learns the action-value function Q(s,a). It follows its current policy to select action A' in the next state S' and uses that same action's value for the update.

Its core update is: Q(S_t, A_t) ← Q(S_t, A_t) + α [R_{t+1} + γQ(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]

• The name comes from the sequence (S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}) used in the update.
• Because it uses A_{t+1} (the action the agent will take under its current policy), it directly learns the value of the policy being executed.
• It is well-suited for online learning where the policy is continuously improved, but can be conservative as it evaluates the exploration policy itself.

Q-Learning is the canonical off-policy TD control algorithm. It learns the optimal action-value function Q*(s,a) directly, independent of the policy being followed. Its update rule uses the maximum Q-value of the next state:

Q(S_t, A_t) ← Q(S_t, A_t) + α [R_{t+1} + γ max_a Q(S_{t+1}, a) - Q(S_t, A_t)]

• The key difference from SARSA is the max_a operator. It assumes the agent will take the best possible action in S_{t+1}, even if its current behavior policy selects a different action (A_{t+1}).
• This separation between the target policy (greedy w.r.t. Q) and the behavior policy (e.g., ε-greedy) allows it to learn the optimal policy while exploring arbitrarily.
• Its off-policy nature makes it powerful for learning from historical data or demonstrations.

TD(λ) generalizes TD(0) and Monte Carlo methods by using eligibility traces. An eligibility trace e(s) is a temporary memory record that tracks how recently and frequently a state has been visited, marking it as "eligible" for learning.

• λ (lambda) is the trace decay parameter, between 0 and 1.
• When λ=0, it reduces to TD(0) (one-step).
• When λ=1, it provides a Monte Carlo-like update (full episode).

On each step, all states are updated in proportion to their trace and the current TD error: V(s) ← V(s) + α δ_t e_t(s) for all states s.

• This creates a bridging mechanism, allowing credit for a reward to be assigned efficiently to states many steps earlier in the trajectory (temporal credit assignment).
• It often leads to significantly faster learning than TD(0).

In Actor-Critic architectures, the TD error is the primary signal driving learning for both components.

• The Critic is a value function V(s; w) or Q(s,a; w). It is trained by minimizing the TD error, just like in TD(0) or SARSA, providing an estimate of the quality of the current state or action.
• The TD error δ is then used as an advantage estimate for the Actor (the policy π(a|s; θ)).
• The policy gradient for the actor is approximated as ∇_θ log π(A_t|S_t; θ) * δ_t. A positive δ (outcome better than expected) increases the probability of action A_t, while a negative δ decreases it.

This setup decouples the policy from the value baseline, reducing variance in policy updates. Algorithms like A2C/A3C (Advantage Actor-Critic) and the critic component of PPO (Proximal Policy Optimization) rely fundamentally on this TD-based advantage estimation.

SARSA (State-Action-Reward-State-Action) is a classic model-free, on-policy TD control algorithm. Unlike Q-Learning, it updates its Q-values based on the action actually taken by the current policy in the next state. Its update rule is: Q(s,a) ← Q(s,a) + α [ r + γ Q(s',a') - Q(s,a) ], where a' is selected by the policy (e.g., ε-greedy). This makes it inherently more conservative, as it evaluates the policy it is following, which can be beneficial in safety-critical or online learning scenarios.

TD(λ) generalizes basic TD learning by introducing eligibility traces, which provide a bridge between TD(0) (one-step) and Monte Carlo (full-episode) methods. An eligibility trace is a temporary record of a visited state or state-action pair, marking it as 'eligible' for learning. The parameter λ (lambda) controls the trace decay rate:

• λ=0: Pure TD(0), uses only immediate one-step backup.
• λ=1: Equivalent to a Monte Carlo update, uses the full return. This mechanism allows for more efficient credit assignment over longer time horizons.

Actor-Critic architectures are a central class of algorithms that combine the strengths of policy-based (Actor) and value-based (Critic) methods. The Critic is typically a value function (e.g., a TD-learned state-value V(s)) that evaluates the actions taken by the Actor (the policy). The TD error (δ = r + γV(s') - V(s)) computed by the Critic is used as a scalar reinforcement signal to update the Actor's policy parameters. This separation provides lower variance updates than pure policy gradients and enables more stable, sample-efficient learning.

The Bellman equation is the recursive mathematical foundation for value functions in sequential decision-making. For a state-value function V(s), it is expressed as V(s) = E[ R + γV(S') | S=s ]. This equation decomposes the value of a state into the immediate reward plus the discounted value of the successor state. TD Learning algorithms are essentially sample-based, incremental methods for solving the Bellman equation without requiring a complete model of the environment. The Bellman optimality equation is the specific form that defines the optimal value function.

This dichotomy defines two primary RL approaches based on their use of an environment model:

• Model-Free RL (like TD Learning): The agent learns a policy or value function directly from experience without explicitly learning the environment's transition P(s'|s,a) or reward R(s,a) dynamics. It is generally more robust to model inaccuracies but can be less sample-efficient.
• Model-Based RL: The agent learns or is given an explicit model of the environment. It can then use this model for planning (e.g., via tree search) or to generate simulated data. TD methods can still be used within model-based approaches to evaluate states or actions within the learned model.