Deep Q-Network

Definition

DQN has large or continuous state space and discrete action space.

Naive DQN

Naive DQN treats $r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a;\theta )$ as a target and minimizes MSE loss by SGD. $L(\theta )=[r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a;\theta )-Q(s_t,a_t;\theta ){]}^2$

Due to the training instability and correlated samples, the Naive DQN has very poor results, even worse than a linear model.

Experience Replay

Online RL agents incrementally update parameters while observing a stream of experience. This structure cause strongly temporally-correlated updates, breaking i.i.d. assumption, and rapidly forget rare experiences that would be useful later on. Experience replay stores experiences $(s,a,r,s^{\prime })$ in the replay buffer, and randomly samples temporally uncorrelated minibatches from the replay buffer when learning.

Target Network

If target function is changed too frequently, then this moving target makes training difficult (non-stationary target problem). The target network technique updates the parameters of the behavior Q-network $Q(\cdot ;\theta )$ at every step, while updating the parameters of the target Q-network $\hat{Q}(\cdot ;\hat{\theta })$ sporadically (e.g. every $k$ steps). $L(\theta )=\frac{1}{B}\sum _{i\in I}[r_{i+1}+\gamma {\max }_a\hat{Q}(s_{i+1},a;\hat{\theta })-Q(s_i,a_i;\theta ){]}^2$ where $B$ is the size of a minibatch, and $I$ is a $B$-sized index set drew from the replay buffer.

Algorithm

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the replay buffer $\mathcal{R}$ to max size $N$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. With probability $ϵ$, select a random action $a_t$ otherwise select $a_t=\underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$.
      4. Sample random minibatch of $B$ transitions $(s_i,a_i,r_{i+1},s_{i+1})$ from $\mathcal{R}$.
      5. $y_i\leftarrow r_{i+1}+\gamma \underset{a}{\max }\hat{Q}(s_{i+1},a;\hat{\theta })$.
      6. Perform Gradient Descent on loss $L(\theta )=(y_i-Q(s_i,a_i;\theta ){)}^2$.
      7. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      8. Update $s_t\leftarrow s_{t+1}$.