Temporal Difference (TD) Learning

Bootstrapping is the core mechanism of TD learning, where the current estimate of the value function is used to update itself. Instead of waiting for a complete episode to end (as in Monte Carlo methods), a TD agent updates its prediction for a state based on the immediate reward and its own estimate of the value of the next state. This is formalized by the TD error, the difference between the new estimate and the old one. This allows for online, incremental learning after every time step, making it highly efficient for continuous tasks.

TD learning is inherently model-free, meaning the agent does not learn or require an explicit model of the environment's dynamics (transition probabilities and reward function). It learns directly from raw experience—sequences of states, actions, and rewards. The value function or policy is learned through interaction and TD updates. This makes TD methods broadly applicable to complex, unknown environments where building an accurate model is impractical, such as playing video games or robotic control.

The Temporal Difference (TD) error (δ) is the scalar signal that drives all learning. It is calculated as: δ = R + γV(S') - V(S) Where R is the immediate reward, γ is the discount factor, V(S') is the estimated value of the next state, and V(S) is the current estimate. This error represents the surprise or the difference between the predicted and the partially observed outcome. The agent adjusts its value estimates to minimize this error, effectively performing credit assignment over short time horizons.

TD learning synthesizes ideas from Dynamic Programming (DP) and Monte Carlo (MC) methods. Like DP, it uses bootstrapping (updating estimates based on other estimates). Like MC, it learns directly from experience without a model. This hybrid approach addresses key limitations: it avoids MC's requirement to wait until the end of an episode, enabling online learning, and it avoids DP's requirement for a complete environment model, enabling learning from interaction. Algorithms like TD(λ) provide a smooth continuum between pure TD(0) and pure Monte Carlo.

Because TD methods update estimates after every step, they can learn significantly faster than Monte Carlo methods in terms of sample efficiency on a per-episode basis. They do not waste experience waiting for a terminal outcome. This enables true online learning, where the policy improves during a single ongoing episode. This characteristic is critical for real-time applications like autonomous systems, where an agent must adapt continuously without the luxury of repeated, complete trial runs.

TD learning is not a single algorithm but a principle underlying many of the most successful RL algorithms. It is the foundation for:

• Q-Learning and Deep Q-Networks (DQN): Learn action-value functions using TD updates.
• SARSA: An on-policy TD control algorithm.
• Actor-Critic methods: The critic component is typically a value function learned via TD, providing the error signal to update the actor (policy).
• TD-Gammon: A seminal application that learned to play backgammon at world-champion level using a neural network trained with TD(λ).

TD(0) is the simplest temporal difference algorithm. It updates the value estimate for a state based on the immediate reward and the estimated value of the next state, using a parameter called the learning rate (α) and the discount factor (γ).

• Update Rule: V(s) ← V(s) + α [ r + γV(s') - V(s) ]
• The term in brackets, δ = r + γV(s') - V(s), is the TD error. It represents the difference between the new estimate and the old one.
• This method is online and incremental, learning after every time step without needing a complete episode to finish, making it more efficient than Monte Carlo methods in continuing tasks.

TD(λ) generalizes TD(0) by using eligibility traces to assign credit not just to the immediately preceding state, but to previously visited states. The trace decay parameter λ controls the temporal credit assignment.

• An eligibility trace is a temporary record of a visited state (or state-action pair) that "marks" it as eligible for learning.
• When a TD error occurs, it propagates backward to all states with non-zero traces, weighted by their trace intensity.
• λ=0 reduces to TD(0), updating only the last state. λ=1 provides Monte Carlo-like updates, considering the entire sequence of rewards until termination.

Q-learning is a powerful off-policy TD algorithm for learning action-value functions (Q-values). It directly learns the optimal policy by updating Q(s,a) estimates using the maximum estimated value of the next state, regardless of the action the agent actually takes next.

• Update Rule: Q(s,a) ← Q(s,a) + α [ r + γ * maxₐ′ Q(s′, a′) - Q(s,a) ]
• It is off-policy because it learns the value of the optimal policy while following a more exploratory behavior policy (e.g., ε-greedy).
• This separation allows for robust learning in stochastic environments and is a cornerstone of algorithms like Deep Q-Networks (DQN).

SARSA (State-Action-Reward-State-Action) is an on-policy TD control algorithm. It learns the Q-values for the policy the agent is currently executing, updating estimates based on the actual action taken in the next state.

• Update Rule: Q(s,a) ← Q(s,a) + α [ r + γ * Q(s′, a′) - Q(s,a) ]
• The name comes from the quintuple (s, a, r, s′, a′) used in each update.
• Because it is on-policy, it evaluates and improves the same policy that generates behavior. This can lead to more cautious learning in risky environments (e.g., near cliffs in gridworlds) compared to Q-learning.

Expected SARSA is a variation that generalizes SARSA by using the expected value of the next state under the current policy, rather than the value of a single sampled action.

• Update Rule: Q(s,a) ← Q(s,a) + α [ r + γ * Σ π(a′|s′) Q(s′, a′) - Q(s,a) ]
• This reduces the variance introduced by the random selection of a′ in standard SARSA, often leading to more stable convergence.
• It can be implemented in both on-policy and off-policy manners. When the target policy is greedy, Expected SARSA becomes identical to Q-learning.

In complex environments with vast state spaces, tabular TD methods are infeasible. Deep Reinforcement Learning combines TD learning with function approximation using neural networks.

• The network parameters (θ) are updated to minimize the TD error as a loss function.
• Example - DQN Loss: L(θ) = 𝔼[( r + γ maxₐ′ Q(s′, a′; θ⁻) - Q(s, a; θ) )²]
• Here, θ⁻ represents a target network, a periodically updated copy of the main network that stabilizes training—a direct extension of the TD bootstrap concept.
• This framework underpins modern successes like AlphaGo and autonomous systems, scaling TD principles to high-dimensional problems.

A reward signal is a scalar, numerical feedback provided by the environment after an agent takes an action. It quantifies the immediate desirability of the resulting state transition. In TD Learning, this signal is the foundational data point for calculating the temporal difference error, which drives all value function updates.

• Sparse vs. Dense: Sparse rewards (e.g., +1 for winning, 0 otherwise) pose a significant credit assignment challenge, while dense rewards provide more frequent guidance.
• Shaping: Engineers often design shaped reward functions to provide intermediate guidance, making learning tractable in complex environments.

Credit assignment is the problem of determining which specific actions in a sequence are responsible for a final outcome (reward or failure). TD Learning inherently addresses this through bootstrapping, as each update assigns credit backwards from a state to its predecessor based on the predicted value difference.

• Temporal Credit Assignment: Focuses on attributing credit to actions over time, which is the primary domain of TD methods.
• Structural Credit Assignment: In neural networks, this refers to attributing credit to specific neurons or weights, often solved with backpropagation.
• TD's use of value estimates provides a principled, incremental method for solving temporal credit assignment.

The Bellman equation is the foundational recursive equation for optimality in sequential decision-making. It decomposes the value of a state into the immediate reward plus the discounted value of the successor state. TD Learning is a sample-based, incremental method for solving the Bellman equation without requiring a complete model of the environment.

• Bellman Optimality Equation: Defines the optimal value function and is the target for algorithms like Q-learning.
• TD Error as Bellman Error: The temporal difference error is essentially an empirical, sampled estimate of the discrepancy between the current value estimate and the Bellman equation's prediction.

Bootstrapping in reinforcement learning refers to updating estimates of state or action values based on other existing estimates, rather than waiting for a complete final outcome (as in Monte Carlo methods). TD Learning is defined by its use of bootstrapping.

• Mechanism: A TD update for a state uses the estimated value of the next state to refine the current state's value.
• Trade-off: Introduces bias but significantly reduces variance and enables online, incremental learning after every step.
• This self-referential update is the core of TD's ability to learn efficiently from incomplete sequences.

A value function is a core component of most RL algorithms, estimating the expected cumulative future reward from a given state (state-value function V(s)) or from taking a specific action in a state (action-value function Q(s,a)). TD Learning's primary goal is to learn an accurate value function through iterative updates.

• Prediction vs. Control: TD can be used for pure prediction (evaluating a fixed policy) or for control (finding an optimal policy, as in SARSA or Q-learning).
• Function Approximation: In complex environments, the value function is represented by a parameterized function (e.g., a neural network), leading to algorithms like Deep Q-Networks (DQN).

This distinction defines how an algorithm uses experience to update its policy. On-policy methods (e.g., SARSA) learn about the policy currently used to generate behavior. Off-policy methods (e.g., Q-learning) can learn about a target policy using data generated by a different behavior policy.

• TD's Flexibility: The TD update rule is a framework that can be applied in both on-policy and off-policy contexts.
• Importance Sampling: Off-policy TD methods often require importance sampling ratios to correct for the difference between the behavior and target policies when estimating expected values.
• This distinction is critical for system design, affecting exploration strategies and data reuse.