Temporal Difference (TD) Learning

Bootstrapping is the defining mechanism of TD learning, where current value estimates are updated using subsequent estimates, not just the final outcome. This is a form of incremental learning.

• Contrast with Monte Carlo: Unlike Monte Carlo methods that must wait until the end of an episode, TD methods can learn after every step.
• Bellman Equation Foundation: Bootstrapping implements the recursive nature of the Bellman equation, V(s) = E[r + γV(s')], allowing for efficient, online updates.
• Impact on Robotics: Enables robots to learn continuously from partial trajectories, which is critical for real-time adaptation in physical environments.

TD learning is inherently model-free, meaning it does not require or learn an explicit model of the environment's transition dynamics or reward function.

• Learns Directly from Experience: The agent learns a value function or policy purely from sequences of states, actions, and rewards.
• Practical Advantage: This is essential in complex robotic domains where the physics (transition model) are unknown or too complex to model accurately.
• Examples: Algorithms like Q-Learning and SARSA are classic model-free TD methods used to learn action-value functions directly from interaction.

TD methods perform online learning, updating value estimates after every time step without waiting for a final outcome. This leads to incremental and computationally efficient updates.

• Update Rule: The core TD update for state-value is V(s) ← V(s) + α [r + γV(s') - V(s)], where α is the learning rate and γ is the discount factor.
• Memory Efficiency: Only the current estimate needs to be stored and updated, unlike batch methods that reprocess entire datasets.
• Real-Time Suitability: This characteristic is paramount for robotics, where the agent must learn and adapt its policy while continuously interacting with the physical world.

The TD error (δ) is the central signal that drives all learning in TD methods. It represents the difference between the newly observed reward-plus-estimate and the old estimate.

• Formula: δ = r + γV(s') - V(s).
• Role: A positive TD error indicates the outcome was better than expected, so the value estimate should be increased. A negative error indicates it was worse.
• Biological Analogy: Similar to dopamine signaling in the brain, which encodes reward prediction error. This signal is used not only for value learning but also to guide policy improvement in actor-critic architectures.

TD learning represents a synthesis of ideas from Dynamic Programming (DP) and Monte Carlo (MC) methods, occupying a middle ground on the spectrum of reinforcement learning approaches.

• From DP: It adopts the idea of bootstrapping—using existing estimates to update other estimates.
• From MC: It adopts the idea of learning from raw experience without a model.
• Spectrum Position: This unification allows TD to overcome key limitations: it is more sample-efficient than pure MC (due to bootstrapping) and does not require a complete model like DP.

The principles of TD learning form the foundational core for nearly all modern, scalable deep reinforcement learning algorithms used in robotics.

• Deep Q-Networks (DQN): Uses a TD target (r + γ max_a Q(s', a)) to train a neural network Q-function.
• Actor-Critic Methods: The critic is almost always a TD learner (e.g., using TD error to evaluate the actor's policy). Algorithms like A3C, PPO, and SAC rely on this.
• Eligibility Traces (TD(λ)): Extends basic TD to bridge further toward Monte Carlo by using a trace of recently visited states, improving credit assignment over multiple steps.

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, performing a one-step lookahead.

• Core Update Rule: V(s) ← V(s) + α [r + γV(s') - V(s)]
• Bootstrapping: Uses its own current estimate V(s') to update V(s), unlike Monte Carlo methods which wait for a final outcome.
• Online Learning: Updates occur after every time step, enabling learning from incomplete sequences, which is critical for real-time robotic control loops.

TD(λ) generalizes TD(0) by using eligibility traces to blend multi-step returns. The parameter λ (lambda) controls the weighting between one-step TD updates (λ=0) and Monte Carlo returns (λ=1).

• Eligibility Traces: A short-term memory vector that marks recently visited states/actions as 'eligible' for learning, allowing credit assignment over multiple steps.
• Unified View: Provides a smooth interpolation between TD(0) and Monte Carlo methods, often leading to faster learning and better performance in environments with delayed rewards.
• Forward vs. Backward View: The backward view (using traces) is computationally efficient and is the standard implementation.

SARSA (State-Action-Reward-State-Action) is an on-policy TD control algorithm. It learns the action-value function Q(s,a) by following and updating the policy currently being used for exploration.

• Update Rule: Q(s,a) ← Q(s,a) + α [r + γQ(s',a') - Q(s,a)]
• On-Policy: The update uses the next action a' that the agent actually takes under its current policy (e.g., ε-greedy).
• Safety in Robotics: Because it evaluates the policy it follows, SARSA naturally accounts for exploration noise, often leading to safer, more conservative policies suitable for physical systems.

Q-Learning is the canonical off-policy TD control algorithm. It directly learns the optimal action-value function Q*(s,a) by using the maximum estimated value of the next state, independent of the action the agent actually takes.

• Update Rule: Q(s,a) ← Q(s,a) + α [r + γ * maxₐ' Q(s',a') - Q(s,a)]
• Off-Policy: Learns about the optimal greedy policy while following a more exploratory behavior policy (e.g., ε-greedy).
• Convergence Guarantee: Under standard conditions, Q-learning is proven to converge to the optimal policy, making it a cornerstone of value-based RL.

Expected SARSA is a TD control algorithm that generalizes Q-learning and SARSA. Instead of using the maximum next value (Q-learning) or a single sample next action (SARSA), it uses the expected value of the next state under the current policy.

• Update Rule: Q(s,a) ← Q(s,a) + α [r + γ * Σ π(a'|s') Q(s',a') - Q(s,a)]
• Reduced Variance: By using an expectation, it eliminates the variance due to random selection of a' in SARSA, often leading to more stable learning.
• Flexibility: Can be used as an on-policy or off-policy algorithm depending on the policy (π) used in the expectation.

Deep Q-Networks (DQN) scale Q-learning to high-dimensional state spaces (like images from a robot's camera) by using a deep neural network as a function approximator for the Q-function.

• Core Innovation: Combines Q-learning with experience replay and a target network to stabilize training.
• Experience Replay: Stores transitions (s, a, r, s') in a buffer and samples mini-batches for training, breaking temporal correlations and improving data efficiency.
• Target Network: Uses a separate, slowly updated network to calculate the max Q(s',a') target, preventing destructive feedback loops. This architecture enabled RL breakthroughs in playing Atari games and remains foundational.

Q-Learning is a foundational, model-free, off-policy TD control algorithm. It learns the optimal action-value function (Q-function) by iteratively applying the Bellman optimality equation. The core update rule is:

• Q(s, a) ← Q(s, a) + α [ r + γ * max_a' Q(s', a') - Q(s, a) ] It is guaranteed to converge to the optimal policy for finite MDPs, provided all state-action pairs are visited infinitely often. Its simplicity and theoretical guarantees make it a cornerstone algorithm, though it struggles with large or continuous state spaces without function approximation.

Deep Q-Network is a breakthrough algorithm that combines Q-Learning with deep neural networks to handle high-dimensional sensory inputs like images. Key innovations that stabilized training include:

• Experience Replay: A buffer storing past transitions (s, a, r, s') that are randomly sampled to break temporal correlations.
• Target Network: A separate, periodically updated network used to compute the TD target, reducing harmful feedback loops. DQN demonstrated that RL agents could learn directly from pixel inputs, achieving human-level performance on many Atari 2600 games. It is primarily designed for discrete action spaces.

SARSA is an on-policy TD control algorithm. Unlike Q-learning, which uses the maximum Q-value of the next state for its update (off-policy), SARSA uses the actual action the agent will take under its current policy. Its update rule is:

• Q(s, a) ← Q(s, a) + α [ r + γ * Q(s', a') - Q(s, a) ] where a' is the action selected in state s' by the current policy (e.g., ε-greedy). This makes SARSA inherently more conservative, as it evaluates and improves the policy it is actually following, which can be beneficial in safety-critical applications like robotics where exploratory actions have real consequences.

TD(λ) generalizes one-step TD prediction (TD(0)) by using eligibility traces to blend information from multiple future steps. 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, all eligible states are updated, weighted by their trace intensity.

• λ (lambda) is a decay parameter between 0 and 1. λ=0 yields one-step TD; λ=1 yields a Monte Carlo-like method.
• This provides a smooth interpolation between TD and Monte Carlo methods, often accelerating learning by efficiently propagating credit back over multiple steps, which is crucial for tasks with delayed rewards.

The Actor-Critic architecture is a foundational framework that explicitly separates the policy (the actor) from the value function (the critic). It is a natural fit for TD methods:

• Critic: Estimates the value function (e.g., V(s) or Q(s,a)) using TD learning. It critiques the actor's actions by calculating the TD error (δ).
• Actor: Updates the policy parameters in the direction suggested by the critic, typically using the TD error as a scalar advantage signal. This separation decouples the representation of what to do (policy) from how good it is (value), leading to more stable and efficient learning, especially in continuous action spaces common in robotic control.

TD Learning is a core technique within model-free reinforcement learning. Understanding this distinction is key:

• Model-Free (e.g., TD, Q-learning, Policy Gradients): The agent learns a policy and/or value function directly from experience with the environment. It has no explicit understanding of the environment's transition dynamics or reward function. TD methods are quintessentially model-free, using sampled experience to bootstrap value estimates.
• Model-Based: The agent learns or is given an internal model of the environment's dynamics (T(s'|s,a)) and reward function (R(s,a)). It can use this model for planning (e.g., via tree search) before acting. While often more sample-efficient, model-based RL faces the challenge of model inaccuracy, especially in complex physical worlds.