Q-learning is an off-policy stochastic approximation method for the optimal action-value function. It learns greedy control values without following the greedy policy during data collection.
Tabular update
The update samples the Bellman optimality operator for action values.
Definition. For a transition \((S_t,A_t,R_{t+1},S_{t+1})\), tabular Q-learning updates \[ Q_{t+1}(S_t,A_t)=Q_t(S_t,A_t)+\alpha_t\{R_{t+1}+\gamma\max_aQ_t(S_{t+1},a)-Q_t(S_t,A_t)\}. \]
Proposition. Conditionally on \((S_t,A_t)=(s,a)\), the expected update target equals \((T_*^QQ_t)(s,a)\).
Proof. Condition on \((s,a)\). The reward and next-state expectation of \(R_{t+1}+\gamma\max_{a'}Q_t(S_{t+1},a')\) is \(r(s,a)+\gamma\int\max_{a'}Q_t(s',a')P(\mathrm{d}s'\mid s,a)\), which is the optimal \(Q\)-Bellman operator.
Convergence in the tabular case
The classical convergence theorem requires enough exploration and diminishing stepsizes.
Theorem. In a finite discounted MDP, if every state-action pair is visited infinitely often, rewards have bounded variance, and the stepsizes for each pair satisfy Robbins-Monro conditions, tabular Q-learning converges to \(q_*\) almost surely.
Proof. The update is asynchronous stochastic approximation to the contraction \(T_*^Q\). The conditional noise is a martingale difference, the stepsizes remove persistent noise, and infinite visits ensure every coordinate is updated. Standard asynchronous stochastic approximation for contractions gives almost-sure convergence to the unique fixed point \(q_*\).
Off-policy nature
The behavior policy generates data; the target policy is greedy with respect to \(Q\).
Remark. Q-learning can learn the greedy optimal value while taking exploratory actions, because the backup uses \(\max_aQ(S_{t+1},a)\) rather than averaging over the behavior policy's next action.
Function approximation warning
The convergence guarantee is tabular; nonlinear approximation changes the problem.
Remark. With function approximation, bootstrapping, and off-policy data, the update may diverge. Stabilizing devices such as target networks and replay buffers are algorithmic remedies, not replacements for the tabular contraction proof.
Off-policy stochastic Bellman iteration
Tabular Q-learning updates \[ Q_{t+1}(S_t,A_t) =Q_t(S_t,A_t)+\alpha_t \left[ R_{t+1}+\gamma\max_bQ_t(S_{t+1},b)-Q_t(S_t,A_t) \right]. \] The behavior policy generates \((S_t,A_t)\), while the max defines the greedy target policy. Conditionally, \[ E[\text{target}-Q_t(s,a)\mid s,a] =(\mathcal TQ_t)(s,a)-Q_t(s,a). \]
Theorem (tabular convergence). In a finite discounted MDP with bounded reward variance, if every state-action pair is sampled infinitely often and its step sizes satisfy \[ \sum_t\alpha_t(s,a)=\infty,\qquad \sum_t\alpha_t(s,a)^2<\infty, \] then \(Q_t\to Q^*\) almost surely.
The proof combines asynchronous stochastic approximation with the \(\gamma\)-contraction of \(\mathcal T\). Exploration need not converge to the greedy policy during learning, but it must maintain infinite coverage. A fixed \(\varepsilon\)-greedy behavior policy suffices in communicating finite MDPs; rapidly vanishing exploration may not.
SARSA and expected SARSA
SARSA uses the sampled next action, \[ R_{t+1}+\gamma Q_t(S_{t+1},A_{t+1}), \] and is on-policy for the behavior rule. Expected SARSA replaces the last term by \(\gamma\sum_a\pi_t(a\mid S_{t+1})Q_t(S_{t+1},a)\), reducing conditional variance. Under greedy-in-the-limit with infinite exploration, tabular SARSA can converge to \(Q^*\); with fixed exploration it evaluates the exploratory policy instead.
Maximization bias and double Q-learning
Proposition. If \(\widehat q_a=q_a+\varepsilon_a\) with \(E\varepsilon_a=0\), then \[ E\max_a\widehat q_a\ge\max_a q_a. \] The inequality is strict in typical noisy, tied-action settings.
Proof. The maximum is convex, so Jensen gives \[ E\max_a(q_a+\varepsilon_a) \ge\max_aE(q_a+\varepsilon_a)=\max_aq_a. \]
Double Q-learning decouples selection and evaluation: choose \(a^*=\arg\max_aQ^A(s',a)\) and evaluate with \(Q^B(s',a^*)\), alternating roles. Independence is imperfect during online learning, but the construction substantially reduces the same-noise maximization bias.
The function-approximation boundary
Convergence of tabular Q-learning does not extend automatically to \(Q_w\). Bootstrapping, off-policy sampling, and function approximation form the “deadly triad”; even linear semi-gradient methods can diverge because the projected optimality operator need not be a contraction in the sampling norm. Target networks, replay buffers, clipping, and conservative objectives improve practice but do not turn the tabular theorem into a general nonlinear convergence result.