VF DQN

Deep Q-network(DQN)

Introduction

Deep Q-learning or deep Q-network (DQN) is one of the earliest and most successful algorithms that introduce deep neural networks into reinforcement learning.

The role of neural networks is to be a nonlinear function approximator (mentioned before). Different from the following Q-learning algorithm:

$$w_{t+1}=w_t+{\alpha }_t\left[r_{t+1}+\gamma \underset{a^{\prime }\in \mathcal{A}(s_{t+1})}{\max }\hat{q}(s_{t+1},a^{\prime },w_t)-\hat{q}(s_t,a_t,w_t)\right]{\nabla }_w\hat{q}(s_t,a_t,w_t)$$

Loss Function

DQN aims to minimize the objective/loss function:

$$J(w)=\mathbb{E}\left[{\left(R+\gamma \underset{a\in \mathcal{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w)\right)}^2\right]$$

where $(S,A,R,S^{\prime })$ are random variables.

对 $\mathbb{E}$的符号的理解

• 如果是${\mathbb{E}}_p$，表示对于分布$p$的期望
• 如果是$\mathbb{E}$，没有写出下标，表示对于当前的分布的期望，当前分布一般都指的是括号中大写的字母，如$S,A,R,S^{\prime }$
• 上面形式其实也可以写成： $$J(w)={\mathbb{E}}_{s,a,r,s^{\prime }}\left[{\left(r+\gamma \underset{a\in \mathcal{A}(s^{\prime })}{\max }\hat{q}(s^{\prime },a,w)-\hat{q}(s,a,w)\right)}^2\right]$$

Minimize loss function

Core Idea

先暂时固定之前网络的参数输出target, 再和现在网络参数的输出output，两个做bellman mse loss，然后再更新网络参数

• To calculate the gradient of the objective function $$J(w)=\mathbb{E}\left[{\left(R+\gamma \underset{a\in \mathcal{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w)\right)}^2\right]$$ the parameter $w$ not only appears in $\hat{q}(S,A,w)$ but also in target $$y=R+\gamma \underset{a\in \mathcal{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)$$
• Since the optimal $a$ depends on $w$, $${\nabla }_{w}y\ne \gamma \underset{a\in \mathcal{A}(S^{\prime })}{\max }{\nabla }_w\hat{q}(S^{\prime },a,w)$$
• need to fix $w$ in $y$ when calculating the gradient (make the dependence above of $a$ on $w$ disappear)
• solution ⇒ two networks:
  • main network: $\hat{q}(s,a,w)$
  • target network: $\hat{q}(s,a,w_T)$, where $w_T$ is the fixed target network parameter
• objective function in this case: $$J=\mathbb{E}\left[{\left(R+\gamma \underset{a\in \mathcal{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w_T)-\hat{q}(S,A,w)\right)}^2\right]$$
• gradient of $J$: $${\nabla }_{w}J=\mathbb{E}\left[2\left(R+\gamma \underset{a\in \mathcal{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w_T)-\hat{q}(S,A,w)\right){\nabla }_w\hat{q}(S,A,w)\right]$$
• basic idea of DQN: use gradient-descent algorithm to minimize the objective function
• optimization process involves some important techniques(Replay Buffer, Target Network, etc.)

Two Networks

• Two networks, a main network and a target network
• Let $w$ and $w_T$ denote the parameters of the main and target networks, respectively
  • set to be the same initially
• In every iteration, draw a mini-batch of samples $\{(s,a,r,s^{\prime })\}$ from the replay buffer
• For every $(s,a,r,s^{\prime })$, calculate the desired output as $$y_T\doteq r+\gamma \underset{a\in \mathcal{A}(s^{\prime })}{\max }\hat{q}(s^{\prime },a,w_T)$$ Therefore, obtain a mini-batch of data: $$\{(s,a,y_T)\}$$
• Use $\{(s,a,y_T)\}$ to train the network so as to minimize $(y_T-\hat{q}(s,a,w){)}^2$ (mseloss)

Experience replay

• After we have collected some experience samples, we do NOT use these samples in the order they were collected(please remember the why we use TD learning)
• Instead, we store them in a set, called replay buffer $\mathcal{B}=\{(s,a,r,s^{\prime })\}$
• Every time we train the neural network, we can draw a mini-batch of random samples from the replay buffer
• The draw of samples, or called experience replay, should follow a uniform distribution

Why do we use experience replay? Why must follow a uniform distribution?

Answer:

用这个方法可以天然地、数学地解决$J$中出现的$\mathbb{E}$的问题：

$$J=\mathbb{E}\left[{\left(R+\gamma \underset{a\in \mathcal{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w)\right)}^2\right]$$

• $R\sim p(R|S,A)$, $S^{\prime }\sim p(S^{\prime }|S,A)$: $R$ and $S$ are determined by the system model
• $(S,A)\sim d$: $(S,A)$ is an index and treated as a single random variable
• The distribution of the state-action pair $(S,A)$ is assumed to be uniform
  • Why uniform distribution? Because no prior knowledge
  • Can we use stationary distribution like before? No, since no policy is given
• 但是我们并不是uniformly 搜集到state-action sample的，因为他们都是由特定policy consequently 产生的
• 所以我们需要用replay buffer来存储这些sample，然后再uniformly sample出来(break the correlation between consequent samples)

Revisit the tabular case

• Why does not tabular Q-learning require experience replay?
  • Because it does not require any distribution of $S$ or $A$
  • 之前的tabular case中我们总是用RM的方法来避免直接计算$\mathbb{E}$，而是用某一个sample的$(s,a,r,s^{\prime })$就可以了，所以我们一直没用到distribution
• Why does Deep Q-learning involve distributions?
  • 由我们的loss funcion所决定的
  • define a scalar objective function $J(w)=\mathbb{E}[\ast ]$, where $\mathbb{E}$ is for all $(S,A)$
  • tabular case aims to solve a set of equations(e.g. BE, BOE) for all $(s,a)$ (update weight one sample $(s,a)$ at a time)
  • deep case aims to optimize a scalar objective function (update weight for a mini-batch $(S,A)$ at a time)
• Can we use experience replay in tabular Q-learning?
  • Yes, we can. And more sample efficient

Implementation

和 NIPS2013workshop DQN原论文算法不太一样

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Deep Q-learning with Experience Replay}\\ & \text{Initialization:}\\ & \text{Replay memory }\mathcal{B}\text{ with capacity }N.\\ & \text{Main network }q(s,a;\mathbf{w})\text{ with random weights }\mathbf{w}.\\ & \text{Target network }q(s,a;{\mathbf{w}}_T)\text{ (initially }{\mathbf{w}}_T=\mathbf{w}\text{).}\\ & \text{Discount factor }\gamma ,\text{ exploration probability }ϵ,\text{ update interval }C.\\ & \text{For episode }=1\text{ to }M\text{, do:}\\ & \text{Initialize state }{s}_1.\\ & \text{For }t=1\text{ to }T\text{, do:}\\ & \text{Select action }{a}_t:\\ & \text{With probability }ϵ,\text{ choose random }{a}_t;\text{ else }{a}_t=\arg \underset{a}{\max }q(s_t,a;\mathbf{w}).\\ & \text{Execute }{a}_t\text{ in environment, observe reward }{r}_t\text{ and next state }{s}_{t+1}.\\ & \text{Store transition }(s_t,a_t,r_t,s_{t+1})\text{ in }\mathcal{B}.\\ & \text{// if we do not have enough batch-size samples in }\mathcal{B}\text{, continue to next step}\\ & \text{Sample random minibatch }(s_j,a_j,r_j,s_{j+1})\text{ from }\mathcal{B}.\\ & \text{For each transition in minibatch, do:}\\ & y_j=\{\begin{array}{ll}{r}_j& \text{If }{s}_{j+1}\text{ is terminal}\\ r_j+\gamma {\max }_{a^{\prime }}q(s_{j+1},a^{\prime };{\mathbf{w}}_T)& \text{Otherwise}\end{array}\\ & \text{Update main network:}\\ & \mathbf{w}\leftarrow \mathbf{w}-\alpha {\nabla }_{\mathbf{w}}\left[\frac{1}{|\text{batch}|}\sum (y_j-q(s_j,a_j;\mathbf{w}){)}^2\right]\\ & \text{Update target network every }C\text{ steps:}\\ & \text{If }t\mathrm{mod}C=0,\text{ set }{\mathbf{w}}_T\leftarrow \mathbf{w}.\\ & t\leftarrow t+1\end{array}}$$

一些观点

• 上面的版本就是off-policy的版本，因为我们的behavior policy和target policy明显是不一样的（或者从这个角度理解：我们永远都是从replay buffer中采样来学习的，符合off-policy这个名字）
• 上面为什么没有写出policy-update的部分？和之前的理由是一样的Version 3，我们从大量的state-action pair中学到了optimal q-value，所以不需要再去更新policy了(直接对q-value进行argmax就可以得到policy)