Temporal Difference (TD) Learning

TD(0) is the foundational one-step algorithm. It updates the value estimate for a state based on the immediate reward and the estimated value of the next state (the TD target).

TD(λ) generalizes this with eligibility traces. It provides a spectrum between one-step TD (λ=0) and Monte Carlo methods (λ=1), allowing credit for rewards to be assigned more efficiently back through a sequence of states. The parameter λ controls the decay rate of the eligibility trace.

SARSA (State-Action-Reward-State-Action) is an on-policy TD control algorithm. It learns the action-value function Q(s,a) for the policy it is currently executing.

• Update Rule: 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) ]
• It uses the actual next action (A_{t+1}) taken by the current policy to form the TD target.
• This makes it inherently conservative, as it evaluates and improves the policy it follows, which can be advantageous in safety-critical or online learning scenarios.

Q-Learning is the canonical off-policy TD control algorithm. It directly learns the optimal action-value function Q*(s,a) independent of the policy being followed.

• Update Rule: 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 TD target uses the maximum Q-value of the next state, representing the value of the greedy policy.
• This separation between the behavior policy (for exploration, e.g., ε-greedy) and the target policy (the greedy policy) is key to its power and convergence guarantees to the optimal policy.

Expected SARSA is a variation that, like Q-Learning, forms its TD target based on an expectation over actions, but uses the expected value under the current policy rather than the maximum.

• Update Rule: Q(S_t, A_t) ← Q(S_t, A_t) + α [ R_{t+1} + γ Σ_a π(a|S_{t+1}) Q(S_{t+1}, a) - Q(S_t, A_t) ]
• It eliminates the variance introduced by the random selection of A_{t+1} in standard SARSA.
• It can be used as either an on-policy or off-policy algorithm. When the policy is greedy, it becomes identical to Q-Learning. It often provides more stable learning than SARSA.

Double Q-Learning addresses a significant overestimation bias inherent in standard Q-Learning due to the max operator. This bias can lead to suboptimal policies and unstable learning, especially with function approximation.

• Mechanism: It maintains two separate Q-value estimates, Q1 and Q2. To perform an update, one network selects the greedy action (argmax), and the other provides its value estimate for that action.
• Update (for Q1): A* = argmax_a Q1(S_{t+1}, a); Q1(S_t, A_t) ← Q1(S_t, A_t) + α [ R_{t+1} + γ Q2(S_{t+1}, A*) - Q1(S_t, A_t) ]
• This decoupling of action selection from evaluation removes the positive bias, leading to more accurate value estimates and more reliable performance.

Applying TD methods to complex problems requires function approximation (e.g., neural networks) to estimate value functions over vast state spaces.

• Core Challenge: The interplay between bootstrapping (TD updates) and function approximation can lead to instability and divergence, unlike in the tabular case.
• Key Techniques that enable stable learning include:
  • Gradient TD Methods: Algorithms like TDC (TD with gradient correction) that guarantee convergence under linear function approximation.
  • Experience Replay: Storing and randomly sampling past transitions to break temporal correlations.
  • Target Networks: Using a slowly updated copy of the value network to generate stable TD targets, a cornerstone of Deep Q-Networks (DQN).
• This extension is what enables TD learning to scale to real-world problems like robotics and game playing.

Q-Learning is a foundational, model-free, off-policy TD control algorithm. It directly learns the optimal action-value function, known as the Q-function, which estimates the expected cumulative reward for taking a given action in a given state and thereafter following the optimal policy. The core update rule is a TD update applied to action values: Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s',a') - Q(s,a) ]. Its off-policy nature allows it to learn the value of the optimal policy while following an exploratory behavior policy, making it highly flexible.

Deep Q-Network (DQN) is a breakthrough algorithm that scales Q-Learning to high-dimensional state spaces (e.g., raw pixels) by using a deep neural network as a function approximator for the Q-function. It introduced key stabilizing techniques:

• Experience Replay: Stores transitions in a buffer and samples mini-batches to break temporal correlations.
• Target Network: Uses a separate, periodically updated network to calculate the TD target, reducing instability. This combination enabled RL agents to learn directly from visual inputs, famously mastering Atari games.

SARSA (State-Action-Reward-State-Action) is a model-free, on-policy TD control algorithm. Unlike Q-Learning, it learns the value of the policy it is currently executing. Its update rule is: Q(s,a) ← Q(s,a) + α [ r + γ Q(s',a') - Q(s,a) ], where a' is the action actually selected by the current policy in state s'. This makes it inherently on-policy—it evaluates and improves the policy used for exploration. It is often more conservative than Q-Learning in risky environments, as it accounts for the exploration policy's behavior.

TD(λ) is a generalization of basic TD learning that provides a smooth bridge between one-step TD methods (λ=0) and Monte Carlo methods (λ=1). It uses eligibility traces, a short-term memory vector that marks recently visited states or state-action pairs as "eligible" for learning. When a TD error occurs, it is propagated backward to all eligible states, weighted by their trace. This allows for faster credit assignment over multiple time steps, significantly accelerating learning in environments with delayed rewards.

The Actor-Critic architecture is a foundational framework that combines the strengths of value-based and policy-based methods. It consists of two components:

• Critic: Estimates the value function (e.g., using TD learning) and evaluates the actions taken by the Actor.
• Actor: Updates the policy parameters in the direction suggested by the Critic's evaluation. The Critic's TD error acts as a scalar reinforcement signal for the Actor. This separation decouples the representation of the value function from the policy, leading to more stable and efficient learning than pure policy gradients.

The Bellman equation is the recursive mathematical foundation for value functions in sequential decision-making. For the state-value function, it is expressed as V(s) = E[ R + γV(S') | S=s ]. This equation states that the value of a state equals the expected immediate reward plus the discounted value of the successor state. TD learning is essentially a stochastic, incremental method for solving the Bellman equation without a complete model of the environment. The TD error δ = r + γV(s') - V(s) measures the deviation from this consistency condition.