Introduction

Let us begin by writing the Q-Learning update once more.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')-Q(S_t,A_t) \right]$$

When there are only a few states and actions, we can store $Q(s,a)$ in a table. If the state is a game screen, however, we cannot turn every possible image into a row in that table.

The central idea of DQN, or Deep Q-Network, is simple.

Replace the Q-table with a neural network that receives a state and outputs the Q-values of every action at once.

The idea may be simple, but combining a neural network with Q-Learning as-is makes training unstable. Consecutive experiences are too similar to one another, and the network changes both its prediction and its target at the same time.

This article examines why each of DQN's three main components—the Q-network, experience replay, and target network—is necessary.

From a Screen to Q-Values

In an environment such as Atari, a single screen does not reveal which direction an object is moving. DQN therefore groups several consecutive frames into one state.

$$S_t = \left[ X_{t-3},X_{t-2},X_{t-1},X_t \right]$$

Feeding $S_t$ into the network produces a Q-value for every available action.

$$Q(S_t,\cdot;\mathbf w) = \begin{bmatrix} Q(S_t,\text{LEFT};\mathbf w) \\ Q(S_t,\text{RIGHT};\mathbf w) \\ Q(S_t,\text{JUMP};\mathbf w) \\ Q(S_t,\text{WAIT};\mathbf w) \end{bmatrix}$$

We can use $\epsilon$-greedy to choose an action. Most of the time, the agent selects the action with the largest Q-value. Occasionally, it chooses a random action to explore.

The DQN Loss

Consider a transition,

$$(S_t,A_t,R_{t+1},S_{t+1}).$$

The Q-Learning target is

$$Y_t = R_{t+1} + \gamma\max_{a'}Q(S_{t+1},a';\mathbf w^-).$$

$\mathbf w^-$ denotes the parameters of the target network, which we will discuss shortly. The current network predicts

$$Q(S_t,A_t;\mathbf w),$$

and training reduces the squared error between the two.

$$L(\mathbf w) = \mathbb E \left[ \left( Y_t-Q(S_t,A_t;\mathbf w) \right)^2 \right]$$

This looks like supervised learning, but the target $Y_t$ is not a fixed label. It is a moving target constructed from Q-values that are themselves being learned. This difference is precisely why DQN needs mechanisms to stabilize training.

Problem 1: Temporally Adjacent Experiences Are Too Similar

Suppose the agent is walking to the right. The screens at times $t$, $t+1$, and $t+2$ will be nearly identical. If we feed these transitions into the network in order, the samples in each mini-batch become strongly correlated.

In ordinary supervised learning, we shuffle the data. DQN follows the same intuition: instead of using an experience once and immediately discarding it, the agent stores it in a replay buffer $\mathcal D$.

$$\mathcal D = \left\{ (s_i,a_i,r_i,s'_i) \right\}$$

During training, past transitions are sampled at random to form a mini-batch.

$$(s,a,r,s') \sim \mathcal D$$

Experience replay serves two purposes.

1. It reduces the correlation between consecutive samples and makes each mini-batch more diverse.
2. It reuses expensive experience collected through interaction with the environment.

Very old experiences, however, may come from a distribution unlike that of the current policy. Reuse is possible because DQN is an off-policy algorithm based on Q-Learning, but the buffer size and its data distribution still affect training.

Problem 2: The Target We Are Chasing Also Moves

If the same network $\mathbf w$ calculates both the current prediction and the next-state target, then

$$Y_t = R_{t+1} + \gamma\max_{a'}Q(S_{t+1},a';\mathbf w).$$

One update to $\mathbf w$ changes both the prediction on the left and the target on the right. It is like revising an exam answer while continually revising the grading standard as well.

DQN uses two networks with the same architecture.

• Online network $Q(s,a;\mathbf w)$: updated by gradient descent at every step.
• Target network $Q(s,a;\mathbf w^-)$: held fixed for a period and used only to calculate targets.

Every $C$ steps, the online network's parameters are copied to the target network.

$$\mathbf w^- \leftarrow \mathbf w$$

Alternatively, a soft update can blend them a little at every step.

$$\mathbf w^- \leftarrow \tau\mathbf w + (1-\tau)\mathbf w^-$$

A Terminal State Has No Future Value

If $S_{t+1}$ is a terminal state, the episode has ended and there are no later rewards.

$$Y_t=R_{t+1}$$

In an implementation, a done mask lets us express both cases in one equation.

$$Y_t = R_{t+1} + \gamma(1-D_t) \max_{a'}Q(S_{t+1},a';\mathbf w^-)$$

When $D_t=1$, the bootstrap term disappears. Be careful, however: treating a truncation caused by a time limit as if it were a genuine terminal state can incorrectly remove future value. We will return to this distinction in the final article of the series.

The DQN Training Process, Step by Step

1. Choose an action in the current state with $\epsilon$-greedy.
2. Receive a reward and next state from the environment.
3. Store the transition in the replay buffer.
4. Sample a random mini-batch from the buffer.
5. Calculate $Y_t$ with the target network.
6. Update the online network so that $Q(s,a;\mathbf w)$ moves closer to $Y_t$.
7. Copy the online parameters to the target network at a fixed interval.

The essential update in one line is

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ Y_t-Q(S_t,A_t;\mathbf w) \right] \nabla_{\mathbf w}Q(S_t,A_t;\mathbf w).$$

Overestimation Caused by the Maximum

When estimates are noisy, the $\max$ in the target tends to select whichever action happened to receive an unusually high value.

$$\max_{a'}Q(S_{t+1},a')$$

This can make Q-values larger than their true values. Double DQN separates action selection from action evaluation.

$$a^* = \arg\max_{a'}Q(S_{t+1},a';\mathbf w)$$ $$Y_t = R_{t+1} + \gamma Q(S_{t+1},a^*;\mathbf w^-)$$

The online network chooses the action, and the target network evaluates the value of that action.

When DQN Is Not a Natural Fit

DQN outputs the Q-value of every action individually, so it fits naturally when the action space is finite and discrete. If actions are continuous, as in robot torque, we cannot list the Q-value of every possible action, and calculating $\max_a Q(s,a)$ is not straightforward.

DQN also has the following limitations.

• It may require a large amount of interaction with the environment.
• It is sensitive to the replay-buffer configuration and the target-update interval.
• Q-value overestimation and instability remain possible.
• It does not represent the policy itself directly.

The next article introduces policy gradient, which handles continuous actions and learns a policy directly.

What to Remember

DQN replaces the Q-table with a neural network, then uses a replay buffer and a target network to mitigate correlated data and a moving target.

1. The network outputs the Q-values of the available actions in a state.
2. Experience replay mixes and reuses experience.
3. The target network is held fixed temporarily so that the learning target does not move too quickly.
4. DQN uses the target $R+\gamma\max Q_{\text{target}}$.
5. Basic DQN is suited to discrete actions and can overestimate values because of the $\max$ operator.

References

• David Silver, Lecture 6: Value Function Approximation
• Mnih et al., Human-level control through deep reinforcement learning
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning