Temporal Difference Learning, SARSA & Q-Learning | AI & Machine Learning Engineering

In dynamic programming methods such as Value Iteration, the agent requires a complete transition model $P(s' | s, a)$ and reward model $R(s, a)$ of the environment. In the vast majority of real-world robotics, games, and sequential systems, these environmental transition dynamics are unknown or analytically intractable.

Model-free reinforcement learning enables agents to discover optimal policies directly from sampled experience streams without ever modeling environment transitions. The foundational engine of modern model-free RL is Temporal Difference (TD) Learning.

TD Error FormulaModel-Free RL

delta_t = R_(t+1) + gamma * max_a' Q(S_(t+1), a') - Q(S_t, A_t)

The temporal difference error drives one-step bootstrapping, updating value estimates from successor estimates without waiting for episode termination.

1. Monte Carlo vs Temporal Difference: The Bootstrapping Paradigm#

To estimate the expected return $V^\pi(s) = \mathbb{E}_\pi [G_t \mid S_t = s]$ , an agent must compute an expectation over stochastic trajectories. Two opposing paradigms govern sample-based value estimation:

Architecture Diagram

Rendering diagram...

Monte Carlo (MC) Methods#

Monte Carlo estimation samples complete trajectories until an absorbing terminal state $S_T$ is reached:

V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t - V(S_t) \right]

where $G_t = \sum_{k=0}^{T - t - 1} \gamma^k R_{t+k+1}$ is the empirical accumulated discounted return.

Bias: Zero. $G_t$ is an unbiased estimator of $V^\pi(S_t)$ because $\mathbb{E}[G_t \mid S_t] = V^\pi(S_t)$ .
Variance: Very high. $G_t$ aggregates random actions and stochastic transitions across the entire remaining episode duration.
Limitation: Cannot learn in continuing (non-terminating) environments. Updates occur only after episode completion.

Temporal Difference: TD(0) Prediction#

Temporal Difference methods solve the latency and variance issues of Monte Carlo by bootstrapping: updating a guess toward a guess.

Recall the Bellman expectation equation:

V^\pi(s) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma V^\pi(S_{t+1}) \mid S_t = s \right]

Instead of awaiting the actual infinite return $G_t$ , TD(0) uses the observed one-step transition reward $R_{t+1}$ plus the discounted estimate of the successor state $\gamma V(S_{t+1})$ as the learning target:

\text{TD Target: } Y_t^{\text{TD}} = R_{t+1} + \gamma V(S_{t+1})

The difference between the target and the current estimate is the TD Error $\delta_t$ :

\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)

The tabular update rule with learning rate $\alpha \in (0, 1]$ is:

V(S_t) \leftarrow V(S_t) + \alpha \delta_t = V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]

The Bias-Variance Tradeoff in TD vs MC

TD(0) targets are biased because the successor value estimate

V(S_{t+1})

is an imperfect approximation of the true

V^\pi(S_{t+1})

. However, TD(0) exhibits vastly lower variance than MC because it only depends on a single transition step

(S_t, A_t, R_{t+1}, S_{t+1})

rather than accumulating variance over long stochastic horizons.

2. On-Policy TD Control: SARSA#

To optimize control (finding the optimal policy $\pi^*$ ) when transition dynamics are unknown, we must estimate action-values $Q(s, a)$ rather than state-values $V(s)$ .

SARSA is an on-policy TD control method. The acronym stems from the transition quintuple:

(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})

SARSA Derivation and Update Rule#

At time step $t$ , the agent in state $S_t$ selects action $A_t$ according to its current behavior policy $\pi$ (typically $\epsilon$ -greedy). The environment returns reward $R_{t+1}$ and next state $S_{t+1}$ . The agent then samples its next action $A_{t+1} \sim \pi(\cdot \mid S_{t+1})$ .

The SARSA TD target uses the exact action $A_{t+1}$ selected by the behavior policy:

Y_t^{\text{SARSA}} = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})

The parameter update rule is:

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]

Because the update evaluates the actual exploratory action $A_{t+1}$ executed by the current policy, SARSA is on-policy. In dangerous environments (like Cliff Walking), SARSA learns conservative, safe paths because it accounts for the probability of exploratory mistakes.

3. Off-Policy TD Control: Q-Learning#

Introduced by Christopher Watkins in 1989, Q-Learning is one of the most critical breakthroughs in reinforcement learning. Q-Learning is an off-policy control method: the agent learns the value of the optimal greedy policy $\pi^*$ while following an exploratory behavior policy $b$ (such as $\epsilon$ -greedy).

Q-Learning Target Derivation#

The Bellman optimality equation for $Q^*(s, a)$ states:

Q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) \max_{a'} Q^*(s', a')

Replacing the expected return with a single sampled transition $(S_t, A_t, R_{t+1}, S_{t+1})$ , the Q-Learning TD target replaces the sampled action $A_{t+1}$ with the greedy maximization over all candidate actions:

Y_t^{\text{QLearn}} = R_{t+1} + \gamma \max_{a' \in \mathcal{A}} Q(S_{t+1}, a')

The Q-learning update equation is:

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]

Architecture Diagram

Rendering diagram...

4. Mathematical Proof: Overestimation Bias via Jensen's Inequality#

A famous weakness of standard Q-Learning is overestimation bias. Because the maximization operator $\max$ is non-linear and convex, noise in action-value estimates systematically leads to overestimation of expected returns.

Step-by-Step Derivation#

Let $Q^*(s, a)$ denote the true optimal action values. Suppose our function approximator or tabular sample produces noisy estimates:

\hat{Q}(s, a) = Q^*(s, a) + \epsilon_a

where the noise terms $\epsilon_a$ are zero-mean independent random variables: $\mathbb{E}[\epsilon_a] = 0$ , meaning the underlying estimates are strictly unbiased.

We evaluate the expected value of the target maximization term:

\mathbb{E}\left[ \max_{a \in \mathcal{A}} \hat{Q}(s, a) \right]

Consider the maximum function $g(x) = \max_a x_a$ . The function $g: \mathbb{R}^{|\mathcal{A}|} \to \mathbb{R}$ is convex.

By Jensen's Inequality, for any random vector $X$ and convex function $g$ :

\mathbb{E}[g(X)] \ge g(\mathbb{E}[X])

Applying Jensen's inequality directly to our action-value estimator:

\mathbb{E}\left[ \max_{a} \hat{Q}(s, a) \right] \ge \max_{a} \mathbb{E}\left[ \hat{Q}(s, a) \right]

Since $\mathbb{E}[\hat{Q}(s, a)] = \mathbb{E}[Q^*(s, a) + \epsilon_a] = Q^*(s, a) + 0 = Q^*(s, a)$ :

\mathbb{E}\left[ \max_{a} \hat{Q}(s, a) \right] \ge \max_{a} Q^*(s, a)

> Conclusion: Even when value estimates $\hat{Q}(s, a)$ have zero mean error, the maximization operator $\max_a$ induces a positive systematic bias. In deep networks, this positive bias compounds across iterative Bellman updates, leading to catastrophic value divergence. This phenomenon directly motivates Double Q-Learning.

5. From-Scratch Implementation: Tabular Q-Learning#

Let us implement Tabular Q-Learning from scratch without any external dependencies in both Python and Rust.

We create a 1D Cliff-GridWorld environment of length $N = 6$ :

States: $0, 1, 2, 3, 4, 5$ .
State 0 is the start. State 5 is the goal ( $+10$ reward, terminal).
Action 0: Move Left. Action 1: Move Right.
State 3 is a dangerous trap/cliff ( $-10$ penalty, resets to state 0).
Normal step penalty: $-1$ .

Python Implementation (Pure Standard Library)#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
"""
Tabular Q-Learning from scratch in pure Python standard library.
Solves a 1D navigation environment with a penalty trap and goal.
"""
import random
from typing import Dict, Tuple, List

class CliffLineEnv:
    def __init__(self, length: int = 6, trap: int = 3):
        self.length = length
        self.trap = trap
        self.goal = length - 1
        self.state = 0

    def reset(self) -> int:
        self.state = 0
        return self.state

    def step(self, action: int) -> Tuple[int, float, bool]:
        # Action 0: Left (-1), Action 1: Right (+1)
        step_dir = -1 if action == 0 else 1
        next_state = max(0, min(self.length - 1, self.state + step_dir))

        if next_state == self.goal:
            reward = 10.0
            done = True
        elif next_state == self.trap:
            reward = -10.0
            next_state = 0  # Fell into trap, reset to start
            done = False
        else:
            reward = -1.0
            done = False

        self.state = next_state
        return next_state, reward, done

class QLearningAgent:
    def __init__(self, num_states: int, num_actions: int,
                 alpha: float = 0.1, gamma: float = 0.95,
                 epsilon: float = 1.0, epsilon_decay: float = 0.995,
                 min_epsilon: float = 0.05):
        self.num_states = num_states
        self.num_actions = num_actions
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.epsilon_decay = epsilon_decay
        self.min_epsilon = min_epsilon

        # Initialize Q-table with zeros: Q[state][action]
        self.q_table: List[List[float]] = [
            [0.0 for _ in range(num_actions)] for _ in range(num_states)
        ]

    def select_action(self, state: int) -> int:
        # Epsilon-greedy action selection
        if random.random() < self.epsilon:
            return random.randint(0, self.num_actions - 1)
        # Greedy selection with random tie-breaking
        values = self.q_table[state]
        max_val = max(values)
        best_actions = [a for a, v in enumerate(values) if abs(v - max_val) < 1e-9]
        return random.choice(best_actions)

    def update(self, state: int, action: int, reward: float, next_state: int, done: bool) -> float:
        current_q = self.q_table[state][action]
        if done:
            target = reward
        else:
            max_next_q = max(self.q_table[next_state])
            target = reward + self.gamma * max_next_q

        td_error = target - current_q
        self.q_table[state][action] += self.alpha * td_error
        return td_error

    def decay_epsilon(self) -> None:
        self.epsilon = max(self.min_epsilon, self.epsilon * self.epsilon_decay)

if __name__ == "__main__":
    env = CliffLineEnv(length=6, trap=3)
    agent = QLearningAgent(num_states=6, num_actions=2)

    num_episodes = 500
    for ep in range(num_episodes):
        state = env.reset()
        done = False
        step_count = 0

        while not done and step_count < 100:
            action = agent.select_action(state)
            next_state, reward, done = env.step(action)
            agent.update(state, action, reward, next_state, done)
            state = next_state
            step_count += 1

        agent.decay_epsilon()

    print("Learned Q-Table:")
    for s in range(6):
        left_q = self_q = agent.q_table[s][0]
        right_q = agent.q_table[s][1]
        best_act = "Left" if left_q > right_q else "Right"
        print(f"State {s}: Left={left_q:6.2f}, Right={right_q:6.2f} -> Best: {best_act}")

Rust Implementation (Pure Standard Library)#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// Tabular Q-Learning from scratch in pure Rust standard library.
// Solves 1D navigation with trap penalties and goal reward.

struct CliffLineEnv {
    length: usize,
    trap: usize,
    goal: usize,
    state: usize,
}

impl CliffLineEnv {
    fn new(length: usize, trap: usize) -> Self {
        Self {
            length,
            trap,
            goal: length - 1,
            state: 0,
        }
    }

    fn reset(&mut self) -> usize {
        self.state = 0;
        self.state
    }

    fn step(&mut self, action: usize) -> (usize, f64, bool) {
        // action 0: Left, action 1: Right
        let next_state = if action == 0 {
            if self.state > 0 { self.state - 1 } else { 0 }
        } else {
            if self.state + 1 < self.length { self.state + 1 } else { self.length - 1 }
        };

        let (final_state, reward, done) = if next_state == self.goal {
            (next_state, 10.0, true)
        } else if next_state == self.trap {
            (0, -10.0, false) // fell in trap, reset
        } else {
            (next_state, -1.0, false)
        };

        self.state = final_state;
        (final_state, reward, done)
    }
}

// Simple LCG PRNG for zero-dependency pseudo-random numbers
struct SimpleRng {
    seed: u64,
}

impl SimpleRng {
    fn new(seed: u64) -> Self {
        Self { seed }
    }

    fn next_f64(&mut self) -> f64 {
        self.seed = self.seed.wrapping_mul(6364136223846793005).wrapping_add(1);
        ((self.seed >> 11) as f64) / ((1u64 << 53) as f64)
    }

    fn next_range(&mut self, upper: usize) -> usize {
        (self.next_f64() * (upper as f64)) as usize
    }
}

struct QLearningAgent {
    num_states: usize,
    num_actions: usize,
    alpha: f64,
    gamma: f64,
    epsilon: f64,
    epsilon_decay: f64,
    min_epsilon: f64,
    q_table: Vec<Vec<f64>>,
    rng: SimpleRng,
}

impl QLearningAgent {
    fn new(num_states: usize, num_actions: usize, seed: u64) -> Self {
        Self {
            num_states,
            num_actions,
            alpha: 0.1,
            gamma: 0.95,
            epsilon: 1.0,
            epsilon_decay: 0.995,
            min_epsilon: 0.05,
            q_table: vec![vec![0.0; num_actions]; num_states],
            rng: SimpleRng::new(seed),
        }
    }

    fn select_action(&mut self, state: usize) -> usize {
        if self.rng.next_f64() < self.epsilon {
            self.rng.next_range(self.num_actions)
        } else {
            let mut best_action = 0;
            let mut best_val = self.q_table[state][0];
            for a in 1..self.num_actions {
                if self.q_table[state][a] > best_val {
                    best_val = self.q_table[state][a];
                    best_action = a;
                }
            }
            best_action
        }
    }

    fn update(&mut self, state: usize, action: usize, reward: f64, next_state: usize, done: bool) -> f64 {
        let current_q = self.q_table[state][action];
        let target = if done {
            reward
        } else {
            let mut max_next = self.q_table[next_state][0];
            for a in 1..self.num_actions {
                if self.q_table[next_state][a] > max_next {
                    max_next = self.q_table[next_state][a];
                }
            }
            reward + self.gamma * max_next
        };

        let td_error = target - current_q;
        self.q_table[state][action] += self.alpha * td_error;
        td_error
    }

    fn decay_epsilon(&mut self) {
        self.epsilon = (self.epsilon * self.epsilon_decay).max(self.min_epsilon);
    }
}

fn main() {
    let mut env = CliffLineEnv::new(6, 3);
    let mut agent = QLearningAgent::new(6, 2, 42);

    for _ in 0..500 {
        let mut state = env.reset();
        let mut done = false;
        let mut steps = 0;

        while !done && steps < 100 {
            let action = agent.select_action(state);
            let (next_state, reward, term) = env.step(action);
            agent.update(state, action, reward, next_state, term);
            state = next_state;
            done = term;
            steps += 1;
        }

        agent.decay_epsilon();
    }

    println!("Learned Q-Table (Rust):");
    for s in 0..6 {
        let left_q = agent.q_table[s][0];
        let right_q = agent.q_table[s][1];
        let dir = if left_q > right_q { "Left" } else { "Right" };
        println!("State {}: Left={:6.2}, Right={:6.2} -> Best: {}", s, left_q, right_q, dir);
    }
}

6. On-Policy vs Off-Policy Tradeoffs#

Criterion	SARSA (On-Policy)	Q-Learning (Off-Policy)
Target Action	$A_{t+1} \sim \pi(S_{t+1})$ (actual exploratory action)	$\arg\max_{a'} Q(S_{t+1}, a')$ (greedy action)
Convergence Target	Evaluates $Q^\pi$ for the exploratory policy	Evaluates $Q^*$ for the optimal policy
Behavior in Peril	Chooses safe, conservative paths	Chooses optimal, risky boundary paths
Replay Buffer Support	No (requires current policy transitions)	Yes (learns from arbitrary historical tuples)
Overestimation Bias	Lower	Higher (due to unconditional max operator)

7. Knowledge Check#

Concept check

Question

question: "Why is standard Q-Learning considered an off-policy algorithm?"

options:

"(Recommended) Because the target action is evaluated greedily (max_a') regardless of which action the exploratory behavior policy actually chose"
"Because it requires an explicit model of the transition probability matrix P(s' | s, a)"
"Because it updates only once at the end of the entire episode after observing the total return"
"Because it cannot utilize an experience replay buffer"

explanation: "Q-Learning is off-policy because the target uses max_a' Q(S_(t+1), a'), which corresponds to the greedy target policy, while the agent selects exploratory actions (e.g., epsilon-greedy) under its behavior policy. The policy generating the data differs from the policy being evaluated."

:::

Concept check

Question

question: "According to Jensen's inequality, why does the maximization operator in Q-Learning induce overestimation bias?"

options:

"(Recommended) Because the max operator is convex, ensuring E[max_a Q(s, a)] >= max_a E[Q(s, a)] even with zero-mean noise"
"Because the learning rate alpha is always strictly bounded between 0 and 1"
"Because the discount factor gamma exponentially suppresses terminal rewards"
"Because tabular states are discrete while actions are continuous"

explanation: "Jensen's inequality proves that for any convex function g, E[g(X)] >= g(E[X]). Because g(x) = max_a x_a is convex, taking the expected maximum of noisy estimators is mathematically guaranteed to be greater than or equal to the maximum of their true expected values."

:::