Q-learning explained: the update rule, worked examples and DQN

Q-learning is a model-free reinforcement learning algorithm that learns the value of taking each action in each state, called the Q-value, directly from experience. After every step it nudges its estimate toward the reward it just received plus the discounted value of the best action in the next state. Repeated enough, with every state-action pair tried often enough, those estimates converge to the optimal action values, and acting greedily on them is an optimal policy.

It needs no model of the environment, it can learn the optimal policy while behaving quite differently, and with a neural network in place of the table it became the deep Q-network (DQN). This guide works an update by hand, lets you watch an agent learn, and reports seeded simulations of step sizes, exploration, Q-learning against SARSA, and the maximisation bias behind double Q-learning.

A worked example: two updates by hand#

We use the reference gridworld shared by this series of articles: a 5 by 5 grid with a goal worth +1 in the top-right corner, a pit worth −1 just left of the square below it, three walls, and a start in the bottom-left. Moves slip: the agent goes where it intended with probability 0.8 and slides to one of the two perpendicular directions with probability 0.1 each. Bumping into a wall or the edge leaves it in place. Rewards arrive on entering a square, the discount is $\gamma =0.9$, and the goal and pit end the episode. The Markov decision process article builds this world in detail.

The Q-table starts at zero. Suppose the agent stands directly below the goal, at row 1, column 4, chooses up, and enters the goal. With learning rate $\alpha =0.1$, the update is

There is no future term because the goal is terminal. Later the agent is one square further down, at row 2, column 4, chooses up and lands below the goal with reward 0. Now the target uses the value just learned:

This is the whole mechanism. Value seeps backwards from rewards one transition at a time, discounted by $\gamma$ and damped by $\alpha$. Nothing told the agent where the goal is or how the slip works; it only saw transitions.

Where does it end up? If the estimates converge, the value of up below the goal must satisfy its own consistency condition. Up succeeds with probability 0.8 (reward +1), slips right into the edge with probability 0.1 (stay put, then continue with value $V^{\ast }$), and slips left into the pit with probability 0.1 (reward −1). With $V^{\ast }$ the value of that square under optimal play,

Up is the best action there, so $V^{\ast }(s)=Q^{\ast }(s,\text{up})$, and solving $V=0.7+0.09V$ gives $V^{\ast }=0.7/0.91=0.769$. Value iteration on the full model gives the same 0.769, and it gives 0.293 for the start square. Q-learning should approach those numbers without ever seeing the model. The rest of this article is about when and how fast it does.

What is Q-learning, formally?#

An agent in a Markov decision process picks actions to maximise the expected return $G_t={\sum }_{k\ge 0}{\gamma }^k{r}_{t+k+1}$. The optimal action-value function $Q^{\ast }(s,a)$ is the best expected return achievable after taking $a$ in $s$. It satisfies the Bellman optimality equation

where the expectation is over the reward $r$ and next state $s^{\prime }$ produced by the environment, and $\gamma \in [0,1)$ is the discount. In words: the value of an action is what you get now plus the discounted value of the best thing you can do next. If you knew $Q^{\ast }$, the optimal policy would be to pick $\arg {\max }_a{Q}^{\ast }(s,a)$ in each state, with no lookahead and no model.

If you know the transition probabilities you can solve this equation by sweeping it to a fixed point, which is value iteration. Q-learning solves the same equation when you do not know them, by replacing the expectation with single samples.

The Q-learning update rule#

Here $s_t$ and $a_t$ are the current state and action, $r_{t+1}$ and $s_{t+1}$ the observed reward and next state, $\alpha \in (0,1]$ the learning rate (step size), and $\gamma$ the discount. When $s_{t+1}$ is terminal the max term is dropped. The bracket is the temporal-difference (TD) error ${\delta }_t$: how much better or worse this transition turned out than the current estimate predicted. The update moves the estimate a fraction $\alpha$ of the way toward the target.

The target is a noisy but unbiased sample of the Bellman optimality backup applied to the current estimate, so averaging many samples with a suitable step size recovers the expectation. It also bootstraps: it borrows the agent's own estimate of the next state's value instead of waiting for the episode to end, as a Monte Carlo method would. That is what lets value propagate a step at a time, and it is also the source of the instabilities discussed under DQN.

The algorithm, step by step#

1. Initialise $Q(s,a)$ for all states and actions, usually to zero; terminal states stay at zero.
2. At the start of each episode, observe the initial state $s$.
3. Choose an action with an exploratory behaviour policy, typically ε-greedy: a uniformly random action with probability $\epsilon$, otherwise $\arg {\max }_{a}Q(s,a)$ with ties broken at random.
4. Take the action, observe $r$ and $s^{\prime }$.
5. Update $Q(s,a)$ with the rule above, using the max over actions in $s^{\prime }$ (or no future term if $s^{\prime }$ is terminal).
6. Set $s\leftarrow s^{\prime }$ and repeat from step 3 until the episode ends; then start a new episode.
7. When finished, act greedily: $\pi (s)=\arg {\max }_{a}Q(s,a)$.

The ε-greedy rule is the same exploration device as in multi-armed bandits; a bandit is the one-state special case of this problem.

Why Q-learning is off-policy#

The target uses ${\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$, the value of the greedy action in $s^{\prime }$, whatever action the agent actually takes next. So the values being learned are those of the greedy policy, while the data come from the exploratory ε-greedy policy. Learning about one policy from data generated by another is what off-policy means. It is why Q-learning can learn from random play, from logged data, or from a replay buffer of old experience, and it is the starting point for offline reinforcement learning, where the data were collected by someone else entirely.

Does Q-learning converge?#

Watkins sketched a convergence argument in his 1989 thesis [1], and Watkins and Dayan gave the proof in 1992 [2]: in a finite MDP, tabular Q-learning converges to $Q^{\ast }$ with probability 1 provided every state-action pair is updated infinitely often and the step sizes for each pair satisfy the Robbins-Monro conditions

where ${\alpha }_n(s,a)$ is the step size used on the $n$-th update of that pair. The first condition lets the estimate travel any distance; the second makes the noise die out. A schedule like ${\alpha }_n=1/n^{0.8}$ satisfies both. A constant $\alpha$ fails the second, so the estimates keep fluctuating forever around $Q^{\ast }$, which is often what you want in practice when the environment drifts, but it means "converged" is only approximately true. Note what the theorem does not ask for: it does not require the behaviour policy to be greedy, or even sensible. Any policy that keeps visiting every pair will do.

We checked this on the reference gridworld (simulation, 20 seeds). With a uniformly random behaviour policy and ${\alpha }_n=1/n^{0.8}$ per pair, the largest error over all state-action pairs, ${\max }_{s,a}|Q(s,a)-Q^{\ast }(s,a)|$, was 0.39 after 100 episodes, 0.15 after 1,000, 0.069 after 5,000 and 0.035 after 20,000. The agent never once acted on its estimates, yet it learned the optimal action values. That is off-policy learning in its purest form.

Watch a Q-learning agent learn#

The figure runs the update rule live: each square shows ${\max }_{a}Q(s,a)$ and the greedy action, and the curve below tracks the return per episode. Switch to cliff walking, a deterministic 4 by 12 world from Sutton and Barto [7], or to SARSA, the on-policy alternative below. Set $\epsilon$ to zero and the agent stops exploring; push $\alpha$ toward one and the values jitter.

What the simulations show: step size and exploration#

Setup (simulation, seeded). We ran Q-learning on the reference gridworld for 2,000 episodes (capped at 200 steps each) with every combination of $\alpha \in \{0.05,0.1,0.3,0.5\}$ and $\epsilon \in \{0.05,0.1,0.3\}$, 50 seeds each. Every 25 episodes we took the greedy policy and computed its exact value from the start square by solving the Bellman equation for that policy, so the score has no evaluation noise. The optimum is 0.293.

Three results stand out, and none of them is what a quick tutorial would lead you to expect.

A constant step size leaves a gap that does not close. With $\alpha =0.1$, the greedy policy reached within 0.01 of optimal in only 6 of 50 runs after 2,000 episodes. The reason is not a lack of data: the states where the greedy action was wrong had been visited a median of 759 times. The reason is that the action gaps in this world are tiny. At the start square, going up is worth 0.2933 and going right 0.2906, a difference of 0.0027, while a constant-$\alpha$ estimate keeps jittering by several hundredths because each update weights the most recent noisy, slip-affected transition by 10%. When the noise in $Q$ is larger than the gap between actions, the argmax is a coin flip. Small gaps also mean small losses per state, but they compound along the route: the median greedy policy was worth 0.206.

Decaying the step size helps, slowly. With the per-pair schedule ${\alpha }_n=1/n^{0.8}$ and $\epsilon =0.1$ (a separate set of 30 seeds), the mean greedy value at the start was 0.248 ± 0.014 after 2,000 episodes and 0.257 ± 0.013 after 10,000, against 0.201 ± 0.030 and 0.214 ± 0.035 for constant $\alpha =0.1$ on the same seeds. The share of runs within 0.01 of optimal after 10,000 episodes rose from 13% to 33%. This is the Robbins-Monro condition at work: averaging shrinks the noise until small action gaps can be resolved. It is slow because a decaying step size also slows learning in the squares the greedy agent rarely reaches, and with $\epsilon =0.1$ there are several of those.

The table is only as good as the states you visit. The largest-error column stays near 0.5 for every setting, dominated by squares the greedy agent almost never reaches, whose Q-values stay near zero. More exploration ($\epsilon =0.3$) shrank it to about 0.44 but cut the online return collected while learning from 0.142 to 0.089 at $\alpha =0.1$: the bandit trade-off between exploring and exploiting, spread over 21 states.

Q-learning vs SARSA#

SARSA, introduced by Rummery and Niranjan as "modified connectionist Q-learning" [3] and named for the quintuple $(s,a,r,s^{\prime },a^{\prime })$ it uses, differs from Q-learning in one term:

where $a^{\prime }$ is the action the agent will actually take next, drawn from its ε-greedy policy. SARSA therefore learns the value of the policy it is following, exploration included. It is on-policy. Q-learning learns the value of the greedy policy while following another. When exploration is costly, those two values differ, and the classic illustration is the cliff.

Setup (simulation, seeded). Cliff walking [7]: a 4 by 12 grid, start at the bottom left, goal at the bottom right, and the ten squares between them are a cliff. Every step costs −1; stepping into the cliff costs −100 and sends the agent back to the start. No slip, no discount. Both methods used $\alpha =0.5$ and $\epsilon =0.1$ for 500 episodes, 100 seeds each.

Every one of the 100 Q-learning runs learned the optimal 13-step path along the edge, worth −13. But while learning with $\epsilon =0.1$, it averaged −49.6 (95% interval ±0.7) per episode over episodes 101 to 500, because one random step in ten from the edge row sometimes lands in the cliff. SARSA averaged −27.5 (±0.7): its values include the risk of its own exploration, so it prefers the 17-step route along the top row, which it learned in 82 of 100 runs (one more found a 19-step variant). In the other 17 runs the purely greedy SARSA policy circled without reaching the goal; SARSA's values describe the exploring policy, and acting fully greedily on them is not guaranteed to work. If $\epsilon$ is decayed toward zero, both methods converge to the optimal path.

The cliff is also a small safety lesson: a method can be optimal by its objective and still behave badly in the regime it actually runs in. Safe reinforcement learning handles this with explicit constraints.

Maximisation bias and double Q-learning#

The max in the target has a statistical side effect. If the estimates $Q(s^{\prime },a^{\prime })$ are noisy but unbiased, the maximum of them is biased upward: $\mathbb{E}[{\max }_a\hat{Q}(a)]\ge {\max }_a\mathbb{E}[\hat{Q}(a)]$, because the max preferentially picks whichever estimate happened to be too high. Q-learning then bootstraps on that inflated value and passes the bias backwards. Van Hasselt showed that this overestimation can be large in stochastic environments and proposed double Q-learning [4]: keep two tables, $Q^A$ and $Q^B$, and on each step update one of them at random, choosing the action with one table and evaluating it with the other:

Because the noise in $Q^B$ is independent of the noise that made $Q^A$ choose that action, the estimate is no longer biased upward (it can be slightly biased downward). The agent acts ε-greedily on $Q^A+Q^B$.

Setup (simulation, seeded). The example from Sutton and Barto [7, Example 6.7]: from state A, right ends the episode with reward 0; left moves to state B with reward 0, where any of 10 actions ends the episode with a reward drawn from a normal distribution with mean −0.1 and standard deviation 1. Going left is worse in expectation, so with $\epsilon =0.1$ an optimal agent goes left only 5% of the time, through exploration. We ran 10,000 seeded runs of 300 episodes each with $\alpha =0.1$.

Q-learning went left in 93.9% of runs at its worst, around episode 21, and was still at 11.8% after 300 episodes. Double Q-learning never exceeded 50.3% (that peak is the coin flip of the first episodes, before anything is learned) and finished at 6.8%, close to the 5% floor. Large action spaces and noisy rewards make the bias worse, which is the regime of deep RL.

From Q-tables to deep Q-networks (DQN)#

A table needs one entry per state-action pair. For Atari frames or robot sensors that is hopeless, so the table is replaced by a function approximator $Q(s,a;\theta )$, usually a neural network that outputs one value per action. The natural move is to turn the update into regression toward the TD target, minimising

where $\theta$ are the network weights being trained, $\mathcal{D}$ is a replay buffer of past transitions, and ${\theta }^{-}$ is a periodically copied set of target-network weights. Done naively, this is unstable: function approximation, bootstrapping and off-policy data together form what Sutton and Barto call the deadly triad [7, Section 11.3], under which value estimates can diverge. The deep Q-network of Mnih and colleagues [5, 6] made it work with two devices.

Experience replay. Transitions go into a large buffer and training samples random minibatches from it, which breaks the correlation between consecutive frames and reuses each transition many times. The idea goes back to Lin [8], and it works only because Q-learning is off-policy: the buffer holds data from many older policies.

A target network. The TD target is computed with a frozen copy of the network, ${\theta }^{-}$, refreshed every few thousand steps, so updates stop moving the target they regress toward.

The 2013 version learned seven Atari games from raw pixels with one architecture and set of hyperparameters [5]. The 2015 version, with the target network, was evaluated on 49 games and reached a level comparable to a professional human games tester across them [6]. Van Hasselt, Guez and Silver then showed that DQN overestimates values substantially on several games and carried double Q-learning across [9]: choose the next action with the online network and evaluate it with the target network,

where $y$ is the regression target. It is a one-line change that reduced overestimation and improved scores, and it is now the default in most DQN implementations.

Q-learning needs a max over actions, so it suits discrete action spaces. For continuous control and for language models, most systems use policy gradient and actor-critic methods, which keep a learned value function as the critic; that is the route to reinforcement learning for LLMs.

Q-learning in Python#

A complete tabular agent for the reference gridworld in plain numpy:

import numpy as np

LAYOUT = ["....G", ".#.X.", ".#...", "...#.", "S...."]
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]          # up, right, down, left
GAMMA, SLIP = 0.9, 0.2

def step(s, a, rng):
    """Slip to a perpendicular direction with prob SLIP; reward on entering s'."""
    u = rng.random()
    d = a if u < 1 - SLIP else (a + 1) % 4 if u < 1 - SLIP / 2 else (a + 3) % 4
    r, c = s[0] + MOVES[d][0], s[1] + MOVES[d][1]
    if not (0 <= r < 5 and 0 <= c < 5) or LAYOUT[r][c] == "#":
        r, c = s                                       # bumped: stay put
    cell = LAYOUT[r][c]
    return (r, c), {"G": 1.0, "X": -1.0}.get(cell, 0.0), cell in "GX"

def q_learning(episodes=2000, alpha=0.1, eps=0.1, seed=0):
    rng = np.random.default_rng(seed)
    Q = np.zeros((5, 5, 4))
    for _ in range(episodes):
        s = (4, 0)
        for _ in range(200):
            if rng.random() < eps:                     # explore
                a = int(rng.integers(4))
            else:                                      # exploit, random tie-break
                q = Q[s]
                a = int(rng.choice(np.flatnonzero(q == q.max())))
            s2, r, done = step(s, a, rng)
            target = r if done else r + GAMMA * Q[s2].max()
            Q[s][a] += alpha * (target - Q[s][a])      # the Q-learning update
            s = s2
            if done:
                break
    return Q

Q = q_learning()
print(np.round(Q.max(axis=2), 2))                     # learned state values
print(np.array(list("↑→↓←"))[Q.argmax(axis=2)])        # greedy policy

With seed 0 it learns the right-hand route, leaves the rarely visited top row at zero, and reports 0.89 below the goal, above the true 0.769: constant-$\alpha$ noise after a run of lucky visits. A per-pair step size $1/n^{0.8}$ makes it settle.

Choosing α, ε and γ in practice#

Report the greedy policy's performance separately from the exploring agent's online return, over many seeds with intervals; the guide to evaluating RL agents covers how.

Failure modes#

Unvisited states. Convergence needs every pair visited infinitely often. In practice much of the table may be visited a handful of times, and a greedy policy that slips into those squares behaves arbitrarily. Tiny action gaps and overestimation, covered above, are the other two tabular traps.

Divergence with function approximation. Off-policy bootstrapping with a function approximator can diverge. Replay, target networks and conservative learning rates are guards, not guarantees.

The reward is the specification. Q-learning optimises exactly the reward you give it. If that reward has a loophole, a capable learner finds it; see reward hacking and reward shaping for how to change rewards without changing the optimal policy.

Frequently asked questions#

Sources#

1. C. J. C. H. Watkins. Learning from Delayed Rewards (PhD thesis, University of Cambridge), 1989. cs.rhul.ac.uk
2. C. J. C. H. Watkins, P. Dayan. Q-learning, 1992. doi.org
3. G. A. Rummery, M. Niranjan. On-line Q-learning using connectionist systems (Technical Report CUED/F-INFENG/TR 166), 1994. mi.eng.cam.ac.uk
4. H. van Hasselt. Double Q-learning, 2010. papers.nips.cc
5. V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, M. Riedmiller. Playing Atari with Deep Reinforcement Learning, 2013. arxiv.org
6. V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al.. Human-level control through deep reinforcement learning, 2015. doi.org
7. R. S. Sutton, A. G. Barto. Reinforcement Learning: An Introduction (2nd ed.), 2018. incompleteideas.net
8. L.-J. Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching, 1992. doi.org
9. H. van Hasselt, A. Guez, D. Silver. Deep Reinforcement Learning with Double Q-learning, 2015. arxiv.org