Q-Learning: Off-Policy TD Control

Q-learning estimates the optimal action-value function $Q^*(s,a)$, defined as the expected return from taking action $a$ in state $s$ and then behaving optimally forever after. Formally, $Q^*$ satisfies the Bellman optimality equation:

Q-learning turns this equation into a sample-based, incremental update rule. After observing a transition $(S_t, A_t, R_{t+1}, S_{t+1})$, the agent updates its current estimate $Q(S_t, A_t)$ toward a TD target built from the observed reward plus the discounted value of the best action in the next state:

The quantity in brackets is the TD error, $\delta_t$. This is a genuine TD method: it bootstraps (uses an existing estimate, $\max_a Q(S_{t+1},a)$, rather than a full Monte Carlo return) and it updates online from single steps. The crucial design choice is the $\max$. The action actually executed at time $t+1$, call it $A_{t+1}$, is chosen by the behavior policy — usually $\epsilon$-greedy with respect to the current $Q$, to ensure exploration. But the target used in the update ignores $A_{t+1}$ entirely and instead asks: whatever the best action available in $S_{t+1}$ turns out to be, what is its value? This means Q-learning is evaluating and improving a target policy (the greedy policy $\pi(s) = \arg\max_a Q(s,a)$) using data generated by a different behavior policy (the exploratory one). This is precisely the definition of off-policy learning: target policy and behavior policy differ, and the update remains valid because the max operator supplies exactly the value the target policy would have obtained, without needing an importance-sampling correction. Contrast this with SARSA's update, which plugs in $Q(S_{t+1}, A_{t+1})$ — the value of the action actually taken next. SARSA therefore evaluates whatever policy is generating behavior (on-policy), including its exploratory mistakes, and tends to learn safer, exploration-aware policies. Q-learning evaluates the greedy policy directly, learning the objectively optimal values even while its own behavior continues to explore and occasionally step off cliffs.

Q-learning is implemented as a loop over episodes and, within each episode, a loop over time steps. At every step the agent: observes the current state, selects an action via its (exploratory) behavior policy, executes it, observes the reward and next state, and applies the update rule above. Critically, unlike SARSA, the agent does not need to pre-select the next action before updating — the update only needs $\max_a Q(S_{t+1},a)$, which can be computed by scanning the next state's row in the Q-table. ``` Algorithm: Q-Learning (off-policy TD control) Input: step size α ∈ (0,1], exploration rate ε, discount γ ∈ [0,1] Initialize Q(s,a) arbitrarily for all s,a; Q(terminal, ·) = 0 for each episode: Initialize S (start state) for each step of episode, until S is terminal:

# behavior policy: e.g. ε-greedy derived from Q With probability ε: A ← random action in A(S) Otherwise: A ← argmax_a Q(S, a) Take action A; observe reward R and next state S'

# off-policy target: use best next action's value,

# regardless of what the behavior policy will pick next if S' is terminal: target ← R else: target ← R + γ max_a' Q(S', a') δ ← target − Q(S, A) Q(S, A) ← Q(S, A) + α δ S ← S' end for end for return Q # π(s) = argmax_a Q(s,a) is the learned greedy policy ``` A few implementation notes that matter in practice. First, ties in the $\arg\max$ / $\max$ should be broken randomly (or consistently) — always breaking ties toward the first action biases learning. Second, the max over actions is the only extra cost relative to SARSA, and it is computed fresh at each step from the current $Q$ table, so it always reflects the latest estimate, never a stale cached value. Third, $Q(\text{terminal}, \cdot)$ must be fixed at $0$, since there is no future return after termination — omitting this base case is a common bug that inflates values near episode ends. Fourth, exploration ($\epsilon > 0$) must persist throughout learning (or decay slowly enough) so that every state-action pair continues to be visited; without this, some $Q(s,a)$ estimates never get corrected. The diagram below shows the backup structure: the algorithm updates $Q(S_t,A_t)$ using the actual reward received, but the best possible* continuation value from $S_{t+1}$, drawn from a branching set of candidate next actions rather than the one truly taken.

Per-step time complexity. Each update requires computing $\max_{a} Q(S', a)$, a scan over $|\mathcal{A}(S')|$ entries, so the per-step cost is $O(|\mathcal{A}|)$ (or $O(\log|\mathcal{A}|)$ if a max-heap per state is maintained, though this is rarely worth the overhead for typical discrete action sets). Selecting the behavior action via $\epsilon$-greedy is also $O(|\mathcal{A}|)$. An entire episode of length $T$ costs $O(T \cdot |\mathcal{A}|)$.

Space complexity. The tabular representation stores one value per state-action pair: $O(|\mathcal{S}| \cdot |\mathcal{A}|)$. This is identical to SARSA and to tabular Monte Carlo control — the table size is determined by the problem, not the algorithm. This is also the central scalability limitation: for continuous or combinatorially large state spaces, tabular Q-learning is infeasible and one turns to function approximation (as in Deep Q-Networks), trading exact tabular guarantees for approximation error.

Correctness — why Q-learning converges to $Q^*$. The convergence argument rests on treating Q-learning as a stochastic approximation algorithm for solving the Bellman optimality equation. Define the operator

$\mathcal{T}$ is a contraction in the sup-norm with modulus $\gamma < 1$: for any two Q-functions $Q_1, Q_2$,

because the max operator is non-expansive ($|\max_a f(a) - \max_a g(a)| \le \max_a |f(a)-g(a)|$) and expectation only averages, never amplifies, differences. By the Banach fixed-point theorem, $\mathcal{T}$ has a unique fixed point, and that fixed point is exactly $Q^*$ by definition of the Bellman optimality equation. Q-learning's update is a stochastic version of the fixed-point iteration $Q \leftarrow \mathcal{T}Q$: instead of the exact expectation, it uses a single sampled transition, so the update has the form

which is a Robbins-Monro stochastic approximation to $\mathcal{T}Q_t(s,a)$ with noise that has zero mean (the sampled next state is an unbiased draw from the transition distribution) and bounded variance (rewards and Q-values are bounded in bounded MDPs). Watkins and Dayan's convergence theorem states: if every state-action pair is updated infinitely often, and the step sizes satisfy the Robbins-Monro conditions

then $Q_t \to Q^*$ with probability 1, for any behavior policy that guarantees infinite visitation of every pair (it need not be greedy, or even related to $Q$ at all, beyond exploring sufficiently). This is the formal justification for calling Q-learning off-policy: the proof places no constraint on how actions are chosen, only that exploration never stops.

Tradeoffs. The guarantee is asymptotic and requires infinite exploration — a purely greedy behavior policy can get stuck and never converge to $Q^*$ if it stops visiting some pairs. In finite time, and especially with function approximation, convergence is not guaranteed at all (the "deadly triad" of bootstrapping, function approximation, and off-policy updates can diverge). The max operator, while what enables direct learning of $Q^*$, introduces a statistical bias: because $\max_a \hat Q(s',a)$ is generally an overestimate of $\max_a Q^*(s',a)$ when $\hat Q$ is a noisy estimate (Jensen's inequality applied to the convex max function), Q-learning tends to systematically overestimate action values in stochastic environments — the maximization bias, resolved by Double Q-learning.

Consider a tiny two-state chain: state $A$ has actions {left, right}; going right transitions to terminal state $T$ with a stochastic reward that is $+10$ half the time and $-10$ half the time (mean $0$); going left transitions to state $B$, which has a single action leading to terminal with reward $+1$ deterministically. The true optimal value is $Q^*(A,\text{left}) = 1$ and $Q^*(A,\text{right}) = 0$, so the optimal action is left. Suppose after some early noisy episodes, due to sampling variance, the agent has observed the $+10$ outcome from right more often than the $-10$ outcome (pure chance), so its current estimate is $Q(A,\text{right}) = 4$ and $Q(A,\text{left}) = 0.9$ (not yet converged). Trace one further transition, taken via $\epsilon$-greedy with $\alpha = 0.5$, $\gamma = 1$:

Even though a single unlucky $-10$ sample violently swings $Q(A,\text{right})$, and a following $+10$ swings it back up, the left branch's estimate steadily tightens toward the true value $1$ because its reward has zero variance. Over many episodes the law of large numbers averages out the $\pm 10$ noise on the right branch toward its true mean of $0$, and — because the algorithm keeps exploring both actions with probability $\epsilon$ — $Q(A,\text{right})$ eventually settles near $0$ while $Q(A,\text{left})$ settles at $1$, so the greedy policy correctly prefers left. Notice this example also illustrates the maximization bias concretely: early in learning, because the agent picks the max of two noisy branches when acting greedily, it disproportionately samples (and reinforces) whichever branch happened to look good by chance, temporarily inflating $Q(A,\text{right})$ above its true value of $0$ before enough data accumulates to correct it.

Q-learning was invented as a doctoral contribution to reinforcement learning theory, and it remains one of the field's most cited and widely implemented algorithms — the direct ancestor of Deep Q-Networks and much of modern value-based deep RL.

Q-learning's tabular form is a staple of introductory RL coursework and small-scale control tasks — gridworlds, inventory control, simple game-playing agents — precisely because its update rule is simple to implement and its convergence guarantees are clean. Its conceptual core, however, extends far beyond the tabular setting. The Deep Q-Network (DQN) architecture that reignited deep reinforcement learning research in 2013–2015 is Q-learning with a neural network approximating $Q(s,a;\theta)$, stabilized with experience replay and a slowly-updated target network — the same max-based Bellman target, just estimated by gradient descent rather than a table lookup. Variants and descendants of Q-learning power research and production systems in robotics (learning grasping and manipulation policies from trial interaction), recommendation systems (learning which action to recommend from off-policy logged interaction data, exploiting exactly the off-policy property), autonomous resource allocation (network routing, data center cooling control), and game-playing agents beyond Atari, including components of systems used in strategy games and simulated environments. Its off-policy nature is what makes it attractive whenever data collection and policy optimization must be decoupled — for instance, learning from a large historical log of user interactions gathered under an old, possibly suboptimal policy, without needing to re-run that old policy to compute corrections.

Ask the tutor: How exactly does Double Q-learning use two value tables to eliminate the maximization bias that Q-learning introduces?