Double DQN (DDQN)

Standard Q-learning and its deep learning extension, DQN, suffer from a tendency to overestimate the value of actions. This occurs because the update rule involves a maximization step over potentially noisy or inaccurate Q-value estimates. The standard DQN target calculation is:

$$y_t^{DQN} = r_t + \gamma \max_{a'} Q_{\theta'}(s_{t+1}, a')$$

Here, the target network $\theta'$ is used for two purposes: first, to select the action $a'$ that is believed to yield the highest Q-value in the next state $s_{t+1}$, and second, to evaluate the Q-value of that selected action. If the target network happens to overestimate the value for any action $a'$, the $\max$ operator will likely pick that overestimated value, leading to a positively biased target $y_t^{DQN}$. This consistent overestimation can propagate through the learning process, potentially resulting in suboptimal policy convergence and instability.

Double DQN (DDQN), proposed by Hado van Hasselt, Arthur Guez, and David Silver in 2015, offers an elegant solution to mitigate this overestimation bias. The core idea is to decouple the selection of the best next action from the evaluation of that action's value. Instead of using the same network (the target network) for both tasks, DDQN uses two different networks.

The Double DQN Update

Specifically, DDQN modifies the target calculation as follows:

1. Action Selection: Use the current online network $Q_{\theta}$ (the one being actively trained) to determine the action $a^*$ that it estimates to be the best in the next state $s_{t+1}$. $$a^* = \arg\max_{a'} Q_{\theta}(s_{t+1}, a')$$
2. Action Evaluation: Use the target network $Q_{\theta'}$ (the periodically updated, stable network) to evaluate the Q-value of the action $a^*$ selected in the previous step. $$Q_{\theta'}(s_{t+1}, a^*)$$
3. DDQN Target Value: Combine these to form the new target value $y_t^{DDQN}$. $$y_t^{DDQN} = r_t + \gamma Q_{\theta'}(s_{t+1}, \arg\max_{a'} Q_{\theta}(s_{t+1}, a'))$$

Compare this carefully to the standard DQN target. In DQN, the argmax and the value estimation both rely solely on the target network $Q_{\theta'}$. In DDQN, the argmax uses the online network $Q_{\theta}$, while the value estimation uses the target network $Q_{\theta'}$.

Why Does Decoupling Help?

The online network $\theta$ and the target network $\theta'$ represent different sets of parameters (recall that $\theta'$ is typically a delayed copy of $\theta$). While both networks might produce estimation errors, it's less likely that both networks will overestimate the value of the same action simultaneously.

By using the online network to select the action ($a^* = \arg\max_{a'} Q_{\theta}(s_{t+1}, a')$), we are still picking what the current policy believes is best. However, by then using the target network to evaluate that specific action's value ($Q_{\theta'}(s_{t+1}, a^*)$), we get a potentially less biased estimate. If the online network mistakenly picks an action whose value is overestimated by $Q_{\theta}$ but not significantly overestimated by $Q_{\theta'}$, the resulting target value $y_t^{DDQN}$ will be less inflated than $y_t^{DQN}$ would have been. This helps break the positive feedback loop of overestimation.

The diagram below illustrates the difference in how the target value is computed in DQN versus DDQN.

Comparison of target value computation flows. DQN uses only the target network for both selecting the maximum-value action and evaluating its value. DDQN uses the online network to select the action and the target network to evaluate that chosen action.

Implementation Impact

Implementing DDQN requires only a small modification to a standard DQN implementation. Instead of calculating max(target_q_values) for the next state, you need to:

1. Perform a forward pass through the online network for the next states $s_{t+1}$ to get $Q_{\theta}(s_{t+1}, a')$ for all $a'$.
2. Find the actions $a^*$ that maximize these online Q-values using argmax.
3. Perform a forward pass through the target network for the next states $s_{t+1}$ to get $Q_{\theta'}(s_{t+1}, a')$ for all $a'$.
4. Select the target Q-values corresponding to the actions $a^*$ found in step 2.
5. Use these selected target Q-values in the Bellman update calculation ($r_t + \gamma Q_{\theta'}(s_{t+1}, a^*)$).

The rest of the DQN machinery, including experience replay and the periodic updating of the target network, remains unchanged. The computational overhead added by DDQN is typically negligible, as it mainly involves an extra forward pass through the online network during the target calculation step, which is usually much less expensive than the backward pass for gradient updates.

By reducing the overestimation bias, DDQN often leads to more stable training and can converge to better policies compared to the original DQN algorithm, making it a valuable and widely used improvement in deep reinforcement learning.