《Playing Atari with Deep Reinforcement Learning》论文阅读笔记。
简介
本文描述的算法是著名的DQN。这是第一个使用深度学习模型来学习控制策略，而训练数据则来源于强化学习生成的高维感知数据。DQN使用卷积神经网络架构，使用Q-learning的变种算法进行训练，用神经网络近似Q函数。该网络的输入是纯粹的像素点，输出是不同动作的期望报酬。根据期望报酬的大小，来间接学习策略。
传统的方法是使用手工设计的特征来拟合一个线性价值函数或策略函数。这种方法的性能严重依赖于特征的质量。而深度学习可以从纯粹的图像像素点中抽取出高层次特征，但是深度学习目前仅广泛用于监督学习和无监督学习。这篇文章则开拓性得将其应用到强化学习领域。
强化学习领域的挑战主要在于三点：
- 1）数据难获取和处理。深度学习依赖于大数据。而强化学习必须从报酬中学习，这个报酬通常只是简单的数值标量，而且相当稀疏、充满噪声，甚至是延迟反馈。尤其是延迟特性，行为和报酬之间存在时间跨度，这个和监督学习中样本和标签直接给定大有不同。
- 2）不符合数据独立假设。深度学习其中一个假设，数据是独立抽样的。而强化学习中数据通常是高度相关的，囿于强化学习时间步之间的依赖性。
- 3) 不符合同分布假设。深度学习另一个假设，数据满足潜在的同一个分布。然而强化学习数据分布会随着算法学习到新的行为而改变（例如游戏某一行为是往左移动，则下一刻画面受到往左移动这一动作的约束；不同行为导致数据分布可能不同），导致分布不是平稳的。
为了解决上述难题。这篇文章提出一种Q-learning算法的变种。核心的一个思想是，为了减轻数据相关性和非平稳性问题，引入了Experience Replay机制。这一机制能够随机得从前面生成的数据中进行抽样。其中，样本顺序的打破能够减轻数据独立性假设，而随机抽样数据，在过去行为上平滑训练数据分布，能够减轻数据分布的非平稳性。而对于挑战1), 借助游戏模拟器、数据预处理手段来解决。
本文的目标是构建一个单一的神经网络智能体，能够学习玩各种游戏。这一神经网络不需要特定游戏的先验知识和手动设计的特征，也不需要知道模拟器的内部状态，而仅仅是从游戏画面、模拟器的反馈和游戏结束信号以及合法动作集进行学习。并且对于不同游戏，神经网络的超参数保持一致。
算法原理
本文的核心问题是考察智能体如何和环境进行交互。本文以Atari emulator模拟器作为环境，智能体产生一系列合法行为actions, 模拟器则及时反馈一系列画面observations、报酬rewards。具体而言，在每个时间步$t$，智能体需要根据当前局势选择动作$a_t$，然后系统会将智能体的动作传给模拟器，模拟器改变相应的内部状态，智能体无法直接观测这一状态，智能体只能观测到下一时间步$t+1$的屏幕画面$x_t$以及对应的游戏分数变化$r_t$。
智能体只能观察到当前屏幕的图像，相当于只观察到部分信息，而模拟器的实际状态却不得而知。因此不可能仅从屏幕图像$x_t$中就完全理解当前游戏局势。因此本文考虑构建动作和观测序列，$s_t=x_1,a_1,x_2,…,a_{t-1}, x_t$这一序列作为$t$时刻的游戏局势，也就是说当前局势综合了前面时间步的动作和观测结果。模拟器保证任何一个序列都是有限步的，因此序列满足有限马尔科夫决策过程MDP。
智能体的目标是和环境交互，选择最佳动作来最大化未来报酬。一个重要的假设是，未来报酬随时间步进行折扣。也就是说当前时间步的未来报酬$R_t$既和当前立即报酬$r_t$有关，又和未来立即报酬有关，并且距离当前时间步越远，影响越小，故使用折扣因子$\gamma$，依时间步跨度的次幂进行折扣。
$$
R_t = \sum_{t’=t}^T \gamma^{t’-t} r_{t’}
$$
补充数学：个人理解
下面是个人的理解，可能存在错误。
若干数学符号定义：
- 策略：$\pi$, 或记做$\pi(s)$， 是状态到动作的映射，或者称作动作的概率分布。给定$s, \pi$, 就能唯一确定下一步的动作。（但是注意：执行完动作后，转移到的新状态$s’$可能不止一种）
- 未来报酬：$R_t= \sum_{t’=t}^T \gamma^{t’-t} r_{t’}$
- 某个状态$s$、策略$\pi$下的未来报酬$R_t$的期望定义为价值函数：$V^{\pi}(s)=E[R_t|s_t=s,\pi]$
- 某个状态$s$、动作$a$、策略$\pi$下的未来报酬$R_t$的期望定义为动作-价值函数：$Q^{\pi}(s,a) = E[R_t|s_t=s,a_t=a, \pi]$
- 某个状态s、动作a、策略$\pi$下的未来报酬$R_t$期望的最大值定义为最优动作-价值函数：$Q^{*}(s,a) = \mathop{max}_{\pi} E[R_t|s_t=s, a_t=a, \pi] $
上述式子的若干关系：
- 价值函数等于动作-价值函数对所有动作求边缘分布。$V^{\pi}(s)=E_{a’} [Q^{\pi}(s, a’)]$
- 最优动作-价值函数等于对动作-价值函数求最大值。$Q^{*}(s,a) = \mathop{max}_\pi Q^{\pi}(s,a)$
注意$Q^{*}$要从所有的策略$\pi$中找到使得Q值最大的。初步推导$Q^{*}$递推式：
$$
Q^{*}(s,a)= max_{\pi} E[R_t|s_t=s, a_t=a, \pi] \\
=\mathop{max}_{\pi} E[r_t+\sum_{t’=t+1}^T \gamma^{t’-t} r_{t’} \ | s_t=s, a_t=a, \pi] \\
=\mathop{max}_{\pi} E[r_t+ \gamma \sum_{t’=t+1}^T \gamma^{t’-(t+1)} r_{t’} \ | s_t=s, a_t=a, \pi] \\
= \mathop{max}_{\pi} E[r_t + \gamma R_{t+1}|s,a,\pi] \\
= r_t+ \gamma \mathop{max}_{\pi} E[R_{t+1}|s,a,\pi] \\
= r_t + \gamma \mathop{max}_{\pi} E_{s’,a’} \left[ E[R_{t+1}|s_{t+1}=s’, a_{t+1}=a’, s,a,\pi] \right] \\
= r_t + \gamma \mathop{max}_{\pi} E_{s’,a’} [Q^{\pi}(s’,a’)|s,a,\pi]\\
= r_t + \gamma \mathop{max}_{\pi} E_{s’} [\sum_{a’} \pi(a’|s’) Q^{\pi}(s’,a’)|s,a]
$$
根据推导和上图示意图，给定策略$\pi$, $\pi(s)$唯一确定一个动作，如$a$。这样$s$可能转移到$s’1,s’2,s’3$, 需要在这些可能的$s’$上求$Q^{\pi}(s’,a)$的期望。 同理可以求得$Q^{\pi}(s’,b)$的期望，最佳策略是选择$Q^{\pi}$期望的最大值所对应的$\pi$。也就是图中红框标出来的、代表各个期望中的最大值。
这样求解略复杂，考虑进一步简化。若假设转移的状态为$s’$, 以及状态$s’$下的决策动作$a’$, 就能求得对应的$Q^{*}(s’,a’)$，那么遍历$s’$下的所有动作$a’$，就可以求出$Q^{*}(s’,a’)$中的最优值。因此，根据贝尔曼最优方程，贪心选择$a’$,来最大化$Q^{*}(s’,a’)$。注意这里的$a’$是下一状态$s’$下的决策动作，而当前状态s下的决策动作为$a$.
因此，进一步改写递推式如下：
$$
Q^{*}(s,a) = r_t + \gamma \mathop{max}_{\pi} E_{s’} [\sum_{a’} \pi(a’|s’) Q^{\pi}(s’,a’)|s,a] \\
\approx E_{s’ \sim \varepsilon} [r_t+\gamma \mathop{max}_{a’} Q^{*}(s’,a’) |s, a]
$$
另外补充一张图，图中给出model-based的value funtion和bellman equation的关系。只要将基于模型状态转移概率求和的地方替换成期望即可。参考见Deep Reinforcement Learning: An Overview
算法
最终得到贝尔曼最优方程。
$$
Q^{*}(s,a) = E_{s’ \sim \varepsilon} [r+\gamma \mathop{max}_{a’} Q^{*}(s’,a’) |s, a]
$$
上述$s’$是执行$a$动作后，可能转移到的新状态。而$a’$是新状态$s’$下的决策动作，选择使得$Q^{*}(s’,a’)$最大的动作$a’$。
通常的算法通过使用贝尔曼最优方程的迭代法来更新Q函数。
$$
Q_{i+1}(s,a) = E[r+\gamma \mathop{max}_{a’} Q_i(s’,a’)|s,a]
$$
注意下标。当前轮次的Q值，使用上一轮次的下一时间步的Q值来更新，当$i$趋近于正无穷时，$Q_i \rightarrow Q^{*}$
然而这种方法通常是不可取的，因为每次只对一个序列$(s,a)$进行迭代，只能求得该序列的收敛值，不能泛化到新的样本序列上。因此需要使用函数估计的思想来估计Q函数，使其能够泛化到新样本上，故加上一个参数$\theta$, $Q(s,a;\theta) \approx Q^{*}(s,a)$。传统的方法使用线性函数来逼近Q函数，在本文中使用神经网络来逼近Q函数，这样的神经网络称作$Q-network$. 使用下述损失函数来学习：
$$
L_i(\theta_i) = E_{s,a \sim \rho(.)} \left[(y_i-Q(s,a;\theta_i))^2 \right] \\
其中，y_i = E_{s’\sim \varepsilon} [r+\gamma \mathop{max}_{a’}Q(s’,a’;\theta_{i-1})|s,a]
$$
上述$i$代表迭代轮次，$y_i$是目标值，依赖于当前迭代模型的参数，并且使用后续步的Q估计值来估计的，这种方法在强化学习中称作“boostraping”。在这篇论文中，使用当前神经网络求得$y_i$目标值，后续的改进，使用前面若干轮次的神经网络作为目标网络求解目标值，解决目标网络和在线网络之间的相关性问题。$Q(s,a;\theta_i)$代表当前轮次待更新的在线网络。$\rho(s,a)$是序列s和动作a上的概率分布，称作行为分布，通常使用$\epsilon-greedy$策略，并使用该策略分布产生多个样本，求这些样本的期望损失。求梯度如下：
$$
\nabla_{\theta_i} L(\theta_i) = E_{s,a\sim \rho(.); s’\sim \varepsilon}\left[ \left(r+\gamma \mathop{max}_{a’}Q(s’,a’;\theta_{i-1}))-Q(s,a;\theta_i)\right) \nabla_{\theta_i} Q(s,a;\theta_i)\right]
$$
如果使用SGD，且每个时间步更新一次的话，上述期望可以使用单独的一个样本替代。这个样本$(s,a,r,s’)$是使用行为分布$\rho$和模拟器$\varepsilon$生成的。
上述算法有两个特点：
Model-Free: 不需要对模拟器进行近似，也就是说不需要估计状态转移概率。
Off-policy: 不基于给定的策略进行学习。Off-policy的核心任务是学习最优策略或最优价值函数。而On-policy是对给定策略进行价值评估或策略提升。Off-policy在本文中通过学习最优动作价值函数来间接学习到策略。并且最终学习到的策略实际上是不同策略的组合(different-policy)，和实际生成数据的策略(same-policy)有所不同。
具体算法如下：
- $Replay \ memory \ D$ 经验缓存池：保存最新的$N$个经验。
- $Episode$: 表征每一局游戏。
- $t$: 表征每局游戏的每个时间步。
- $a_t$: 根据当前序列决策下一步动作，用于产生样本。$a_t$服从行为分布$\rho$。通常行为分布$\rho$使用$\epsilon-greedy$策略，即以$\epsilon$概率随机选择动作$a’$, 以$1-\epsilon$按照$max_{a’} Q^{*}(s’,a’)$概率选择动作$a’$。注意，这里是off-policy（policy未给定）方法，故基于贪心策略来选择最优动作。若是on-policy方法，则直接根据给定的策略分布抽样动作即可。这里的$Q^{*}$应该是目前正在学习的神经网络Q，即使用当前网络来决策动作。
- $\phi$：特征预处理组件。神经网络要求输入必须是相同长度的，而根据上文可知，$s_t=x_1,a_1,x_2,…,a_{t-1}, x_t$, 因此每个时间步的$s_t$长度是不同的。故需要进行预处理，具体预处理过程见下文。
- $transition$: 样本。$(\phi_t, a_t, r_t, \phi_{t+1})$ 分别指预处理后的当前状态，决策的下一步动作，模拟器返回的报酬，模拟器返回的、经过预处理后的下一步状态。
- $y_j$: 目标值。 若是结束步则设置成相应的报酬。否则传入预处理后的下一步状态$\phi_{t+1}$给上一轮的神经网络，根据$r_j+\gamma \mathop{max}_{a’}Q(\phi_{j+1}, a’;\theta)$计算。其中Q就是上一轮的神经网络，使用上一轮神经网络来生成目标值。
- $SGD$：梯度下降更新参数。
特征预处理和模型架构
特征处理
使用$raw frames$，即纯粹的帧像素，$210*160$, 128种颜色，RGB三通道。首先将RGB转化成Gray-scale，再down-sample下采样为$110*84$规格的图像, 最后crop成$84*84$的图像。$\phi$会截取最新的4帧图像，并叠加起来，作为神经网络的输入。
模型架构
Deep Q-Networks(DQN)
- 输入层：$84*84*4$ image.
- 隐藏层1：8*8 stride=4, 16 filters卷积层。
- ReLU激活。
- 隐藏层2： 4*4 stride=2, 32 filters卷积层。
- ReLU激活。
- 全连接层1：256个units。
- 输出层：全连接层，number of action个units。每个神经元代表对应动作的Q值，一次性输出下一步每个合法动作的Q值。
总结
本文原则上是强化学习和深度学习融合的第一篇论文。强化学习体现在Q-learning学习算法，模拟器的使用，样本的生成等。深度学习则体现在神经网络架构的使用。二者的联系是通过神经网络近似Q函数实现的。同时，本文引入的Experience Replay机制是后续其他研究的基础，也是算法有效性的保证。
后续工作包括：神经网络架构的优化：是否有更好的网络架构；特征处理方法的优化：本文的特征处理略粗糙，如RGB通道是否不合并更好；强化学习算法的优化和选择，是否有其余更好的强化学习算法、算法迭代的时间周期选择，每个时间步连续迭代仍然存在较强的相关性，是否可以调整优化周期，这个优化点体现在Nature论文《Human-level control through deep reinforcement learning》，分离目标网络和迭代网络，使用目标网络生成样本标签，且周期性更新目标网络，比如每隔C-step，将当前迭代网络更新到目标网络上，这样能显著减小目标网络和迭代网络的相关性；最后，随机抽取样本方式的优化，是否可以优先抽取对迭代有帮助的样本等，例如使用TD-error衡量样本的优先级。
