An introduction to Deep Q-Learning: let’s play Doom（三上）

上一章，我们学习了Q-Learning：一种RL算法，它会构建一个Q-table，然后agent在给定state的情况下使用Q-table来找到最优动作。
但是我们会发现，如果我们有一个巨大的state空间环境，生成和更新Q-table会变得非常低效。
本文，我们创建深度Q神经网络。不使用Q-table，我们用神经网络来处理state，然后输出基于该state的每个action的Q-values。

本文要学习的是：

• 什么是Deep Q-Learning（DQL）？
• DQL的最优策略是什么？
• 如何处理temporal limitation problem？
• 为什么要使用experience replay？
• DQL背后的数学原理是什么？

Adding ‘Deep’ to Q-Learning

本文我们来学习玩Doom这款游戏。Doom是一个有着巨大state空间的big env（百万级的states）。对于这个环境创建和更新一个Q-table就会非常低效了。
对于这个case，最好的想法就是创建一个神经网络来逼近，对于给定state的每个action的Q-values。

How does Deep Q-Learning work?

这就是我们DQL的结构：

Preprocessing part

The problem of temporal limitation

关于为什么我们要使用多帧图像堆叠，这是因为如果仅仅使用单帧图像，我们没有办法感知运动信息，也就无法做出正确的决策。
当然有更好的办法来解决时间的问题，也就是使用LSTM网络，但是对于初学者，堆叠多帧更好理解一点。

Using convolution networks

CNN网络所使用到的卷积操作和网络结构能够很好的相对快速的提取图像特征。CNN是目前处理图像数据最好的网络。具体细节请参考其他资料。

Experience Replay: making more efficient use of observed experience

Experience replay　帮助我们处理两件事：

• 避免忘记之前的经验。
• 减少经验间的相关性。

Avoid forgetting previous experiences

存在一个问题，由于actions和states具有很强的相关性，我们网络的权重具有易变性。
在第一章我们提到了强化学习的过程：

Reducing correlation between experiences

还有另一个问题——我们知道每个action都会影响到下一个state。这就使得输出的一系列experience tuples具有很强的相关性。
如果我们按序列顺序训练网络，我们的agent会受到这种强相关性的影响。
从replay buffer里随机采样，就会破坏这个相关性。这就防止action value灾难性的振荡或者不收敛。
下面我们用一个例子来简单理解一下。现在我们在玩一个第一人称射击，怪物要么出现在左边，要么在右边。我们agent的目标就是射中怪物。我们有两把和两个动作：射击左边和射击右边。

Our Deep Q-Learning algorithm

上一章，我们提到了bellman equation。
$$\text{New }Q(s,a)=Q(s,a)+\alpha [R(s,a)+\gamma \max Q^{\prime }(s^{\prime },a^{\prime })-Q(s,a)]$$
在这个例子中，我们想要更新网络权重来减小error。
这个error（或者TD error）是通过计算Q-target（下一个state的最大可能value）和Q-value（我们当前Q-value的预测）的差来表示。
$$\Delta w=\alpha [(R+\gamma ma{x}_a\hat{Q}(s^{\prime },a,w))-\hat{Q}(s,a,w)]{\nabla }_w\hat{Q}(s,a,w)$$

Initialize Doom Environment E
Initialize replay Memory M with capacity N (= finite capacity)
Initialize the DQN weights w
for episode in max_episode:    
	s = Environment state    
	for steps in max_steps:         
		Choose action a from state s using epsilon greedy.         
		Take action a, get r (reward) and s' (next state)         
		Store experience tuple <s, a, r, s'> in M         
		s = s' (state = new_state)                  
		Get random minibatch of exp tuples from M         
		Set Q_target = reward(s,a) +  γmaxQ(s')         
		Update w =  α(Q_target - Q_value) *  ∇w Q_value

在这个算法中有两个流程：

• 我们跟env进行交互，将experiences存入replay memory，然后对env进行采样。
• 随机选择一个小的batch，然后使用sgd进行更新。