3.2 Temporal-Difference, Q-Learning, and Exploration: One Update Does Not Mean You've Learned

In the developer workshop, the robot explores one step at a time, only seeing the outcome after each move. The workshop must decide: wait until the entire episode ends to summarize the experience, or update the model immediately using the estimate of the next state.

The robot has no way of knowing where the wind will carry it next, it can only record the actual transition $(S_t, A_t, R_{t+1}, S_{t+1})$. Waiting until the end of the episode allows for more accurate learning, but introduces delayed feedback. Updating immediately with the next state’s estimate speeds up convergence, yet carries forward the current estimate’s error as a target.

Learning Objectives

• Distinguish between Monte Carlo and Temporal-Difference target methods;
• Properly handle terminal states, valid actions, and random ties in Q-learning;
• Understand the differences between on-policy SARSA and off-policy Q-learning;
• Explain tabular convergence conditions and the risks associated with function approximation.

1. Monte Carlo and TD(0)

Monte Carlo methods update value estimates after an entire episode is completed, using the actual return:

$$ V(S_t)\leftarrow V(S_t)+\alpha[G_t-V(S_t)]. $$

They do not use bootstrapping and must wait until the return is known, which often results in higher variance.

TD(0) uses a one-step target:

$$ V(S_t)\leftarrow V(S_t)+\alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]. $$

TD can update online, has lower target variance, but introduces bootstrap bias. There is no general rule that TD always outperforms Monte Carlo.

2. Q-Learning backup

$$ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[ R_{t+1}+\gamma\max_aQ(S_{t+1},a)-Q(S_t,A_t)]. $$

Actions can be selected epsilon-greedy, while the target uses greedy max, making Q-learning an off-policy control method.

A more complete tabular agent:

import numpy as np

class TabularQLearning:
    def __init__(self, n_states, n_actions, alpha, gamma, epsilon, seed=0):
        self.q = np.zeros((n_states, n_actions), dtype=float)
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.rng = np.random.default_rng(seed)

    def act(self, state, legal_actions):
        legal = np.asarray(legal_actions, dtype=int)
        if len(legal) == 0:
            raise ValueError("non-terminal state has no legal actions")
        if self.rng.random() < self.epsilon:
            return int(self.rng.choice(legal))

        values = self.q[state, legal]
        best = legal[np.flatnonzero(values == values.max())]
        return int(self.rng.choice(best))

    def update(self, state, action, reward, next_state, terminal, next_legal):
        bootstrap = 0.0 if terminal else self.q[next_state, next_legal].max()
        target = reward + self.gamma * bootstrap
        self.q[state, action] += self.alpha * (
            target - self.q[state, action]
        )

The old implementation bootstraps regardless of whether next_state is terminal, injecting fictional values from terminal states into the target. Additionally, argmax always favors the first tie-breaking action.

3. SARSA Learning of Behavioral Policy Value

SARSA target uses the actual next action:

$$ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}). $$

When the behavior policy is epsilon-greedy, SARSA learns the value of a policy that includes exploration risk. In the cliff-walking example, SARSA might choose a path farther from the cliff; in contrast, Q-learning assumes a greedy future policy and may prefer a shorter, but more dangerous, route during exploration.

"The off-policy approach is better" does not hold. The choice depends on the target policy being evaluated or optimized, the source of the data, and the importance sampling correction.

4. Exploration Is Not a Fixed Epsilon Formula

The epsilon-greedy approach is simple but fails to account for uncertainty: all non-greedy actions are chosen with equal probability. Alternative strategies include:

• optimistic initialization;
• decaying epsilon;
• UCB (Upper Confidence Bound);
• Boltzmann/softmax exploration;
• intrinsic motivation;
• posterior sampling.

"Decaying from 1.0 to 0.01" is not a universal rule. The decay rate depends on the horizon, access frequency, non-stationarity, and safety costs. Continuous random exploration in production can be harmful and requires simulators, constrained actions, or approval workflows.

5. Conditional Convergence of Tabular Q-Learning

In classical finite MDPs, tabular Q-learning converges to $Q^*$ under the following conditions:

• All state-action pairs are visited infinitely often;
• The learning rate satisfies the corresponding stochastic approximation conditions;
• Rewards are bounded and the environment is stable;
• Discounting or termination ensures well-defined returns;

Under these standard assumptions, convergence is guaranteed. However, fixed learning rates or early stopping typically yield only approximate stability.

An increasing average return does not imply convergence of the Q-table, nor does it guarantee that the policy deployed in practice will perform well.

6. Maximization Bias and Double Q-Learning

The max operation tends to favor positive noise in estimates, leading to overestimation. Double Q-learning addresses this by using one set of estimates to select an action and a separate set to evaluate that action, thereby reducing the bias. The deep learning version follows the Double DQN approach.

This does not guarantee underestimation or unbiasedness; function approximation and data distribution still influence the outcomes.

7. Eligibility traces

TD($\lambda$) uses eligibility traces to propagate the current TD error back through recent states, thereby connecting one-step TD with Monte Carlo methods. When $\lambda = 0$, the method approaches TD(0); as $\lambda$ approaches 1, it becomes closer to the long return (specific equivalence conditions should be noted, especially regarding online versus offline implementations).

n-step returns also strike a balance among bias, variance, and delay.

8. From Q-Table to Function Approximation

Continuous or vast state spaces cannot be exhaustively tabulated, so we use $Q(s,a;\theta)$. This does not mean "Q-learning immediately fails", we can start with techniques like tile coding, linear function approximation, or discretization. A neural network is merely one option among many.

The combination of off-policy learning, bootstrapping, and function approximation is known as the "deadly triad," which can lead to instability or even divergence. DQN employs several mechanisms to mitigate these risks:

• A replay buffer breaks the correlation between consecutive samples and reuses experience;
• A target network slows down target value drift;
• Engineering safeguards such as gradient clipping and reward scaling.

These mitigations do not guarantee universal convergence. Moreover, replay can alter the data distribution, and older experiences may become harmful in non-stationary environments.

9. How to Read a Training Curve

Record separately:

• Training rewards (including exploration);
• Rewards from a fixed evaluation policy;
• Episode length, success rate, and failure types;
• State-action coverage;
• TD error and Q-value ranges;
• Distributions across multiple random seeds and confidence intervals.

Displaying only the best seed or the average of the last 100 episodes hides instability and selection bias.

Common Misconceptions

• The final Q value is still added during bootstrapping: A true terminal state should not participate in bootstrapping.
• Smaller epsilon values lead to faster convergence: This may result in insufficient exploration of critical actions.
• Q-learning is always better than SARSA: The two algorithms target different policy strategies.
• Using replay and a target network guarantees stability: Function approximation bias and coverage still need to be diagnosed.

Exercise

1. Manually compute the target values for the same trajectory using MC, TD(0), SARSA, and Q-learning.
2. Construct a terminal bootstrap bug and observe how the final Q-value is overestimated.
3. Compare the training and evaluation trajectories of SARSA and Q-learning in a cliff-walking environment.
4. Report the return distribution and state-action coverage using five random seeds.

Summary

The TD method uses the current estimate to improve future estimates, so sample efficiency and stability depend on the target, exploration, and coverage. The one-line formula of Q-learning only makes sense when the terminal state, valid actions, and convergence conditions are correctly implemented.

The next lesson directly parameterizes the policy and discusses high variance, actor-critic methods, offline data, and safety evaluation.