Q-learning

The update#

Q-learning (Watkins, 1989) is an off-policy temporal-difference control method:

$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \Big[ \underbrace{r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)}_{\text{TD error } \delta_t} \Big] $$

Symbols: $\alpha \in (0,1]$ the step size, $\gamma$ the discount, $r_{t+1}$ the observed reward, and $\delta_t$ the temporal-difference error. The target $r_{t+1} + \gamma \max_{a'} Q(s_{t+1},a')$ is a one-sample estimate of the Bellman optimality backup, with $P$ replaced by the single transition actually observed.

Off-policy, precisely#

The behaviour policy $\mu$ generates the data; the target policy is greedy with respect to $Q$. Because the target uses $\max_{a'}$ rather than the action $\mu$ will choose next, the fixed point is $Q^*$ regardless of $\mu$ — provided $\mu$ has adequate coverage.

Contrast SARSA, the on-policy sibling: $$ 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] $$ using the action actually taken. SARSA converges to $Q^\pi$ for the $\epsilon$-greedy policy being followed, so it learns a safe policy that accounts for its own exploration. On the classic cliff-walking task, Q-learning learns the optimal path along the cliff edge and falls off during training; SARSA learns a longer, safer path and scores better online. Neither is uniformly correct — they answer different questions.

Convergence#

Watkins and Dayan (1992) proved almost-sure convergence of tabular Q-learning to $Q^*$ under:

1. Every $(s,a)$ is visited infinitely often.
2. Robbins-Monro step sizes: $\sum_t \alpha_t(s,a) = \infty$ and $\sum_t \alpha_t^2(s,a) < \infty$.
3. Bounded rewards.

The proof treats the update as stochastic approximation of a contraction mapping and applies the Jaakkola, Jordan and Singh (1994) framework. Note that condition (2) rules out the constant $\alpha$ that essentially all practical implementations use — constant step sizes converge to a bounded neighbourhood of $Q^*$ rather than to the point, which is the correct trade for a non-stationary problem.

Maximisation bias#

$\mathbb{E}[\max_a \hat{Q}(s,a)] \ge \max_a \mathbb{E}[\hat{Q}(s,a)]$ by Jensen's inequality. Taking a max over noisy estimates systematically overestimates, and the bias compounds through bootstrapping.

Double Q-learning (Hasselt, 2010) decouples selection from evaluation with two tables: $$ Q_A(s,a) \leftarrow Q_A(s,a) + \alpha\left[ r + \gamma\, Q_B!\left(s', \arg\max_{a'} Q_A(s',a')\right) - Q_A(s,a) \right] $$ updating $A$ or $B$ at random each step. $Q_A$ picks the action, $Q_B$ scores it, so the noise in the two is independent and the bias largely cancels. This carries directly into Double DQN.

Sample complexity#

For a $\gamma$-discounted MDP with a generative model, synchronous Q-learning needs $\tilde{\Theta}!\left( \frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^4 \varepsilon^2} \right)$ samples for an $\varepsilon$-accurate $Q$ (Li et al., 2020, with a matching lower bound). Note $(1-\gamma)^{-4}$ — worse than the $(1-\gamma)^{-3}$ achievable by model-based value iteration on the same data. Model-based methods are provably more sample-efficient here, a result that is often overlooked.

Variants worth knowing#

• Q($\lambda$) — eligibility traces spread credit back over many steps, interpolating between one-step TD and Monte Carlo. Watkins's version cuts the trace at a non-greedy action; Peng's does not, trading a small bias for lower variance.
• Expected SARSA — replaces $Q(s_{t+1}, a_{t+1})$ with $\sum_{a'}\pi(a' \mid s_{t+1})Q(s_{t+1},a')$, removing the variance from sampling the next action. Usually dominates SARSA at equal cost.
• Speedy Q-learning (Azar et al., 2011) — attains the improved $(1-\gamma)^{-3}$ rate by using both the current and previous $Q$ in the target.

The limitation that ends the tabular story#

The table has $|\mathcal{S}| \times |\mathcal{A}|$ entries and needs each visited many times. Function approximation is unavoidable for anything real, and it breaks the convergence guarantee: off-policy learning, bootstrapping and function approximation together form the deadly triad (Sutton and Barto, chapter 11), and their combination can diverge. Baird's counterexample (1995) shows linear Q-learning diverging on a seven-state MDP. Everything in the DQN lesson is machinery for making the triad behave in practice, without ever making it safe in theory.

References#

• Watkins (1989), Learning from Delayed Rewards, PhD thesis, Cambridge.
• Watkins and Dayan (1992), Q-learning, Machine Learning 8:279-292.
• Hasselt (2010), Double Q-learning, NeurIPS.
• Baird (1995), Residual Algorithms: Reinforcement Learning with Function Approximation.
• Li et al. (2020), Sample Complexity of Asynchronous Q-Learning — arxiv.org/abs/2006.03041.
• Sutton and Barto (2018), chapters 6 and 11.

What to learn next#

• Deep Q-networks — replacing the table with a neural network.
• Markov decision processes — what Q-learning is approximating, and what it drops.
• Reward shaping — what to do when the goal is too far away to stumble into.