DQN 总结

发表于 | 分类于 | 0 comments

这篇总结了Q-learning算法和DQN算法2013年的NIPS版本和2015年的NATRUE版本。

Q-Learning

为了得到最优策略Policy，我们考虑估算每一个状态下每一种选择的价值Value有多大。然后我们通过分析发现，每一个时间片的Q(s,a)和当前得到的Reward以及下一个时间片的Q(s,a)有关。在一个实验里，我们只可能知道当前的Q值，而不能够知道下一个时刻的Q值，但是Q-Learning建立在虚拟环境下无限次的实验，这意味着可以把上一次实验计算得到的Q值拿来使用。这样就可以根据当前的Reward及上一次实验中下一个时间片的Q值更新当前的Q值。

Initialize Q arbitrarily, Q(Terminal - state) = 0 // 初始化Q表中的值为0
Repeat (for each episode):
	Initialize S  // 每个新的回合，初始化S
	Repeat (for each step of episode):
		// 使用某个policy比如（e-greedy）根据状态S选取一个动作执行
		// e 的概率去随机选取， 1-e的概率选取Q表中收益最高的action
		// e 一般比较小，例如0.01
		// 执行完动作后，观察reward和新的状态S'
		
		Q(S, A) <— Q(S, A)  + 𝛂(R + 𝛌maxQ(S‘, a) - Q(St, At)) // 贝尔曼方程
		// 更新Q表中的Q(S, A)
		// 𝛂为学习率，越大则保留之前训练的效果就越少
		// 𝛌为折扣因子，即越远的未来收益越不确定
		S <— S'
	Until S is terminal

可以看知乎 - 牛阿的回答，以及CSDN上对Q-learning tutorial的翻译。

Q值可以想象为一个很大的表格，横列代表s，纵列代表a，表格内的值代表Q值：

  a1 a2 a3 a4
s1 Q(1,1) Q(1,2) Q(1,3) Q(1,4)
s2 Q(2,1) Q(2,2) Q(2,3) Q(2,4)
s3 Q(3,1) Q(3,2) Q(3,3) Q(3,4)
s4 Q(4,1) Q(4,2) Q(4,4) Q(4,4)

接下来对Q值进行更新：

  • Step1. 初始化Q矩阵，比如都设置为0
  a1 a2 a3 a4
s1 0 0 0 0
s2 0 0 0 0
s3 0 0 0 0
s4 0 0 0 0

  • Step2. 根据当前Q矩阵以及e-greedy 方法获取动作。比如当前状态s1，那么在s1一列的每一个Q值都是0，那么这个时候选择什么动作都是可行的。

      假设我们选择a2动作，然后得到的reward是1，并且进入到状态3，接下来我们要根据 

  ***Q(St, At) <— Q(St, At)  + 𝛂(Rt+1 + 𝛌maxQ(St+1, a) - Q(St, At))*** 
	
  来更新Q值，这里假设𝛂=1，𝛌=1，并进入到s3状态，也就是每一次都把目标Q值赋给Q。Q(s1, a2) = 1
  • Step3. 现在的状态是s3，假设选择动作a3，得到1的reward，状态变成s1，使用同样的方法，由于之前第一次更新，这次$maxQ(s_1, a) = 1$，因此$Q(s_3, a_3) = 2 + max(Qs_1, a) = 2 + 1 =3$
  • Step3. 反复直至Q收敛。

重复 (对每个episode）：

​ 初始化状态S

​ 重复（对edisode中的每一步）

​ 使用某个policy比如（e-greedy）根据状态S选取一个动作执行

​ 执行完动作后，观察reward和新的状态S’

​ $Q(S_t, A_t) <— Q(S_t, A_t) + 𝛂(R_{t+1} + 𝛌max(S_t, a))$

DQN

Value Function Approximation

在DQN中，为了解决状态过多无法用表格存储Q值的问题，使用$f(s, a, w)$近似的表示$Q(s, a)$，也就是使用一个函数来近似求解Q值。这个函数通过一个神经网络来训练参数达到收敛，当然这个收敛的过程还需要很多技巧，例如之后的经验回放机制等。

Network

DQN的输入是经过处理的4个连续的84x84图像，然后经过两个卷积层，两个全连接层，最后输出包含每一个动作Q值的向量。

Layer Input Filter size Stride Num filter Activation Output
Conv1 84x84x4 8x8 4 32 ReLU 20x20x32
Conv2 20x20x32 4x4 2 64 ReLU 9x9x64
Conv3 9x9x64 3x3 1 64 ReLU 7x7x64
fc4 7x7x64     512 ReLU 512
fc5 512     18 Linear 18

Algorithms

2013年 NIPS版：

1、初始化replay memory D 容量为N

2、用一个深度神经网络作为Q值网络，初始化权重参数

3、设定游戏片段总数M

4、初始化网络输入，大小为84x84x4，并且计算网络输出

5、以概率ϵ随机选择动作$a_t$或者通过网络输出的$Q(max)$值选择动作$a_t$

6、得到执行$a_t$后的奖励$r_t$和下一个网络的输入

7、根据当前的值计算下一时刻网络的输出

8、将四个参数作为此刻的状态一起存入到D中（D中存放着N个时刻的状态）

9、随机从D中取出minibatch个状态

10、计算每一个状态的目标值（通过执行at后的reward来更新Q值作为目标值）

11、通过SGD更新weight

这里最关键的部分，一是理解经验回放replay memory的作用：它记录存储一个了经验集，每个经验包含一系列参数值，包括当前状态s，该状态选择的动作a，选择动作a后收获的reward，以及得到的下一个状态s‘；这样做的意义就在于，我们每次次训练Q网络的时候并不是实时的获取游戏屏幕上状态，而是从这个replay memory中随机抽取一个minibatch的经验集作为训练样本，这样的好处是打乱了样本顺序，使样本变的无序，没有关联，使Q网络能够更有效率的学习、收敛。二是理解Q网络是如何更新参数的：Q网络每次输出的一组不同动作Q值，我们去执行Q值对应的动作，从而获取下一个状态，和对应的奖励。这样做了之后，我们获取了下一个状态s’，作为Q网络的下一个输入，去获取Q网络估计的下一个状态的Q值Q‘；然后用Q’和奖励r，利用Q-learning中的贝尔曼方程，去计算当前的Q。Q-learning算出来的Q值和之前Q网络估计的Q值之间有一个偏差，这个偏差就是我们更新Q网络需要使用的损失。

用Q值作为Q网络的标签，损失函数为：$L(w) = \frac{1}{2}[ ( r + 𝛄maxQ(s’, a’, w) - Q(s, a, w) )^2 ) ]$

即对于给定的$<s, a, r, s’>$，更新参数的流程如下：

  1. 将当前状态s输入Q网络，获得所有动作估计的Q值。
  2. 执行Q值最大的动作a‘，并得到状态s‘，与相应的r。
  3. 将s’输入Q网络，得到所有动作的Q值，并选取这组Q值中最大的Q值$maxQ(s’, a’)$。
  4. 根据贝尔曼方程计算$r + \gamma{maxQ(s’, a’)}$

2015年 Natrue版：

dqn-nature

由于玩Atari采集的样本是一个时间序列，样本之间具有连续性，如果每次得到样本就更新Q值，受样本分布影响，效果会不好。因此，一个很直接的想法就是把样本先存起来，然后随机采样如何？这就是Experience Replay的意思。按照脑科学的观点，人的大脑也具有这样的机制，就是在回忆中学习。

算法分析：

  1. 训练分成M个episode，每个episode训练T次。我的理解就是比如玩游戏，一局是一个episode，一局里面有很多时间片，就训练多少次，次数不固定。重启新的episode主要是初始化state 作为新的第一个，而不是用上一局的最后的状态作为state输入。

  2. 实际上每个循环分成两部分：一部分是输出动作并存储。一部分是随机从经验池里取出minibatch个transitions，然后计算target，根据loss function通过RMSProp更新参数。

  3. 这里的算法我们可以看到，参数是一直更新的，而Nature的算法改进了，计算target用的是之前的参数。具体算法的变化等之后分析Nature的文章再说。

优点：

  • 每一步的经验都能带来很多权值的更新，拥有更高的数据效率（个人不是很理解这作为一个优点，以前的算法就没有吗？）
  • 就是experience replay的优势，打破数据的相关性，降低数据更新的不确定性variance。
  • experience replay的另一个优点就是不容易陷入局部最优解或者更糟糕的不收敛。 如果是on-policy learning，也就是来一个新的经验就学一个。那么下一个动作就会受当前的影响，如果最大的动作是向左，那么就会一直向左。使用experience replay 获取的行为的分布就比较平均，就能防止大的波动和发散。也因此，这是一个off-policy的学习。