Deep Q-Networks (DQN)

WHY do we need DQN?

WHAT problem are we solving? We want an agent that picks actions to maximise long-term reward in an environment with a huge or continuous state space (e.g. raw Atari pixels: $210\times160\times3$ possible images — astronomically many states).

WHY not plain Q-learning? Tabular Q-learning stores one number $Q(s,a)$ per (state,action). For pixels you'd need a table larger than the number of atoms in the universe, and you'd never visit the same state twice — no generalisation.

HOW does DQN fix it? Approximate the whole table with a parametric function $Q(s,a;\theta)$ — a neural net with weights $\theta$. Nearby states share weights, so learning about one state generalises to similar ones.

Recap: what is $Q$? (derivation from first principles)

Deriving the Bellman optimality equation. Split the sum into "first reward" + "rest":

$Q^*(s,a)=\mathbb{E}\big[r_t + \gamma \sum_{k=0}^\infty \gamma^k r_{t+1+k}\big]$

The "rest" term, if we act optimally from $s_{t+1}$ onward, is exactly $\max_{a'} Q^*(s_{t+1},a')$. So:

Turning Bellman into a loss (the DQN objective)

We want $Q(s,a;\theta)$ to satisfy Bellman. If it did, the two sides would be equal, so their difference (the TD error) would be zero. Minimise the squared TD error:

Why is the target $y = r+\gamma\max_{a'}Q(s',a';\theta^-)$ and not the true $Q^*$? We don't know $Q^*$! So we bootstrap: use our current best estimate of the next state's value as a stand-in. This is a moving target — which is exactly why we need the two tricks below.

HOW do we update? Gradient descent on $\mathcal{L}$ (treating $y$ as a constant, i.e. don't backprop through the target): $\theta \leftarrow \theta + \alpha\big(y - Q(s,a;\theta)\big)\nabla_\theta Q(s,a;\theta)$

The two tricks (this is the "Deep" secret sauce)

The full DQN algorithm

1. Initialise net $\theta$, target net $\theta^-\!=\!\theta$, empty replay buffer $D$.
2. For each step:
   • Pick action $\epsilon$-greedy: random with prob $\epsilon$, else $\arg\max_a Q(s,a;\theta)$.
   • Execute $a$, observe $r, s'$; store $(s,a,r,s')$ in $D$.
   • Sample a minibatch from $D$.
   • Compute targets $y = r + \gamma\max_{a'}Q(s',a';\theta^-)$ (use $y=r$ if $s'$ terminal).
   • Gradient step on $(y - Q(s,a;\theta))^2$.
   • Every $C$ steps: $\theta^- \leftarrow \theta$.

Why $\epsilon$-greedy? Pure greedy never explores unknown actions → gets stuck. $\epsilon$ forces exploration; we anneal $\epsilon$ from ~1 down to ~0.1 over time (explore early, exploit late).

Worked Example 1 — one gradient target by hand

State $s$, took action $a$, got reward $r=1$, landed in $s'$ (not terminal), $\gamma=0.9$. Target net says $Q(s',\text{left})=2$, $Q(s',\text{right})=5$. Current net: $Q(s,a)=3$.

• Step: $\max_{a'}Q(s',a')=\max(2,5)=5$. Why? Bellman uses the best next action.
• Step: $y = r+\gamma\cdot 5 = 1 + 0.9(5) = 5.5$. Why? This is our bootstrapped target.
• Step: TD error $=y-Q(s,a)=5.5-3=2.5$. Why? Net underestimates; push $Q(s,a)$ up toward $5.5$.

Worked Example 2 — terminal state

Same but $s'$ is terminal (episode ended). Then $y=r=1$.

• Why? No future rewards after termination, so the $\gamma\max Q$ term is dropped.
• If old $Q(s,a)=1.2$, TD error $=1-1.2=-0.2$ → nudge $Q(s,a)$ down.

Flashcards

Connections

• Q-Learning — tabular ancestor DQN generalises.
• Bellman Equation — the fixed point DQN's loss targets.
• Experience Replay — the buffer trick, also basis of prioritized replay.
• Double DQN — fixes DQN's $\max$ overestimation bias.
• Dueling DQN — splits value & advantage streams.
• Temporal Difference Learning — bootstrapping source.
• Policy Gradient Methods — alternative family for continuous actions.
• Epsilon-Greedy Exploration — action selection strategy.

Concept Map

Hinglish (regional understanding)