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

An agent observes a transition only after taking an action. The learning algorithm must decide whether to wait for the episode's actual return or update immediately from an estimate of the next state.

For example, a robot records the observed transition $(S_t,A_t,R_{t+1},S_{t+1})$. Waiting for the episode return delays feedback. Using the next-state estimate permits an immediate update, but carries estimation error into the target. Updating sooner is not the same as learning more accurately.

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 \underset{a}{max}Q(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.

This Python 3 + NumPy fragment (partial) omits the environment loop. The caller supplies valid state indices, lists of legal action indices, and valid alpha, gamma, and epsilon values. The class handles random tie-breaking and terminal updates.

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):
        if terminal:
            bootstrap = 0.0
        else:
            legal = np.asarray(next_legal, dtype=int)
            if legal.ndim != 1 or len(legal) == 0:
                raise ValueError("non-terminal next state needs legal actions")
            bootstrap = self.q[next_state, legal].max()
        target = reward + self.gamma * bootstrap
        self.q[state, action] += self.alpha * (
            target - self.q[state, action]
        )

A true terminal target contains only the immediate reward, even if the next Q entry accidentally holds a nonzero value. With reward 2, gamma 0.9, and next Q of 100, the terminal target is still 2; the same nonterminal transition gives 92. Supply the task termination flag as terminal, keeping sampling truncation separate.

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^{\ast }$ under the following conditions:

• All state-action pairs are visited infinitely often;
• At the kth update of each state-action pair, learning rates satisfy $\sum _k{\alpha }_k=\mathrm{\infty }$ and $\sum _k{\alpha }_k^2<\mathrm{\infty }$;
• Rewards are bounded and the environment is stable;
• Discounting or termination ensures well-defined returns;

Under these standard assumptions for a finite discounted MDP, tabular Q-learning converges almost surely to $Q^{\ast }$. Undiscounted cases need additional conditions such as absorption; see Watkins and Dayan's original paper. The example above uses a fixed learning rate, so this theorem does not establish its convergence. For the step-size conditions and a complete finite discounted proof, see Regehr and Ayoub, section 5.

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.