Q-learning

Summary

Q-learning (Watkins, 1989) is an off-policy temporal-difference algorithm that learns the optimal action-value function $Q^{\ast }(s,a)$. The expected return from taking action $a$ in state $s$ and then acting optimally. By iterating the Bellman optimality update:

$$Q(s,a)\leftarrow Q(s,a)+\alpha [r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a)].$$

Q-learning is the canonical value-based RL algorithm. Combined with deep neural networks (DQN; Mnih et al., 2015), it produced the original deep RL breakthroughs on Atari and remains the foundation of value-based methods. Knowing Q-learning is the prerequisite for understanding: target networks, experience replay, double DQN, dueling networks, and the relationship to actor-critic methods.

The setup

A Markov decision process (MDP): states $s$, actions $a$, transition $p(s^{\prime }\mid s,a)$, reward $r(s,a)$, discount $\gamma \in [0,1]$.

The optimal action-value function:

$$Q^{\ast }(s,a)=\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{r}_t|s_0=s,a_0=a,{\pi }^{\ast }\right].$$

The optimal policy: ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)$.

Bellman optimality

$Q^{\ast }$ satisfies the Bellman optimality equation:

$$Q^{\ast }(s,a)={\mathbb{E}}_{s^{\prime }}\left[r+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })\right].$$

Q-learning approximates this by sampling: take action $a$, observe $r$ and $s^{\prime }$, update $Q$ toward the target $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$.

Tabular Q-learning

For small finite state-action spaces, store $Q$ as a table. Sample transitions $(s,a,r,s^{\prime })$, apply the update with learning rate $\alpha$. Guaranteed to converge to $Q^{\ast }$ if every state-action pair is visited infinitely often and learning rates satisfy Robbins-Monro conditions.

Off-policy: the update uses ${\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ regardless of which action is actually taken next. This decouples exploration policy (e.g., $\epsilon$-greedy) from the learned greedy policy.

Learning objective: given one transition and the next state’s action values, distinguish the action sampled by the behavior policy from the greedy action used to construct the Q-learning target.

One off-policy backup

The trajectory can explore while the target looks ahead greedily.

Deep Q-Networks (DQN)

For large state spaces, replace the table with a neural network $Q_{\theta }(s,a)$. Two essential tricks make this work:

1. Experience replay: store transitions in a buffer, sample mini-batches uniformly. Breaks temporal correlation; stabilizes training; enables data reuse.
2. Target network: maintain a separate frozen copy $Q_{{\theta }^{-}}$ for the target $r+\gamma {\max }_{a^{\prime }}{Q}_{{\theta }^{-}}(s^{\prime },a^{\prime })$. Update ${\theta }^{-}$ to $\theta$ every $K$ steps. Prevents the target from chasing itself.

The DQN loss:

$$L(\theta )={\mathbb{E}}_{(s,a,r,s^{\prime })\sim \mathcal{D}}\left[(r+\gamma \underset{a^{\prime }}{\max }{Q}_{{\theta }^{-}}(s^{\prime },a^{\prime })-Q_{\theta }(s,a){)}^2\right].$$

Variants

• Double DQN (van Hasselt 2015): use $\arg \max$ from online network, value from target network. Reduces overestimation bias.
• Dueling DQN (Wang 2016): factor $Q(s,a)=V(s)+(A(s,a)-\bar{A}(s))$.
• Prioritized replay (Schaul 2015): sample transitions with high TD error more often.
• Rainbow (Hessel 2018): combines six improvements; canonical strong baseline.
• Distributional RL (C51, IQN): predict the distribution of returns, not just the mean.

Limitations

• Maximization bias: ${\max }_{a}Q(s,a)$ is biased upward when $Q$ is noisy. Double DQN partially fixes.
• Continuous action spaces: ${\max }_a$ becomes a non-trivial optimization; use deterministic policy gradients (DDPG, TD3, SAC) instead.
• Sample efficiency: deep Q-learning needs millions of environment steps; impractical for slow simulators.
• Off-policy correction: off-policy data can be biased; DQN papers often need careful replay buffer management.

Q-learning vs. policy gradient

Method	Q-learning	Policy gradient
Learns	$Q(s,a)$	$\pi (a\mid s)$
Policy	Implicit ($\arg \max$)	Explicit
On/off policy	Off-policy	Usually on-policy
Continuous actions	Hard (${\max }_a$)	Natural
Variance	Lower	Higher
Sample efficiency	Higher (data reuse)	Lower

In practice for continuous control: SAC (combines Q-learning with stochastic policy). For discrete actions with small action space: DQN-family. For large discrete action spaces (LLMs): policy gradient or DPO-family.

Common pitfalls

• Skipping the target network. Loss explodes; training diverges.
• Skipping experience replay. Successive samples are highly correlated; gradient estimates are biased.
• Confusing on-policy and off-policy. Q-learning is off-policy: you can learn from old data with a different policy.
• Ignoring exploration. Greedy policy from a randomly-initialized $Q$ is terrible; $\epsilon$-greedy with decaying $\epsilon$ is the standard.

Related

• Policy gradient. Alternative paradigm.
• Markov chains. MDP background.