DQN Trio

DQN (Deep Q-Network) approximates the optimal action-value function with a network $Q_\theta(s,a)$, trained by least-squares regression toward a frozen TD target:

$L(\theta) = \mathbb{E}_{(s,a,r,s')\sim\mathcal{D}}\left[\left(r + \gamma \max_{a'} Q_{\theta^-}(s',a') - Q_\theta(s,a)\right)^2\right]$ \nDerivation: 1. The Bellman optimality equation gives the TD target $y = r + \gamma \max_{a'} Q_{\theta^-}(s',a')$: the target network $\theta^-$ (hard copy every $C$ steps or Polyak averaging $\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-$) freezes the target so bootstrapping becomes regression onto a constant, removing oscillations; 2. Differentiating w.r.t. $\theta$: $\nabla_\theta L = -2\mathbb{E}[(y - Q_\theta(s,a))\nabla_\theta Q_\theta(s,a)]$ — the target $y$ does not backpropagate; 3. Experience replay $\mathcal{D}$ stores $(s,a,r,s')$ and samples uniformly, breaking the strong temporal correlation of consecutive samples and enabling reuse and stable batch training; 4. Double DQN corrects overestimation: the $\max$ operator is positively biased since $\mathbb{E}[\max X_i] \ge \max \mathbb{E}[X_i]$ (max is convex; Jensen), and noise + bootstrapping compounds the error — overestimated actions get chosen again. Double DQN decouples action selection from evaluation: $y = r + \gamma Q_{\theta^-}(s', \arg\max_{a'} Q_\theta(s', a'))$ — the online network picks the action, the target network scores it, substantially reducing the bias.

discrete action spaces (games, recommendation candidate ranking, combinatorial actions); the foundational deep-RL algorithm.

states are continuous/high-dimensional so tabular lookup fails. The trio targets deep learning's three enemies: replay breaks correlation, the target network stabilizes the target, and Double-DQN removes max overestimation; later improvements (prioritized replay, dueling, n-step, C51, Rainbow) stack along this lineage.

Write DQN's loss and explain the target network's role and update scheme.

Whiteboard: prove max overestimation E[max X] ≥ max E[X] via Jensen and derive the decoupled Double-DQN target.

What does experience replay solve? Limits of uniform sampling; how does prioritized replay improve it?

The DQN trio: which problem does each of replay, target network, Double-DQN solve? Further improvements?

Why must the TD target be frozen? Consequences of updating the target network too often or too slowly?