Playing Atari with Deep Reinforcement Learning

Abstract

使用强化学习直接从高维输入中成功学习控制策略。
Q-learning 的变种进行训练，输入是原始像素，输出是估计未来收益的值函数。
应用于 Atari Learning Environment 中的 7个游戏，6个优于之前的方法，3个中优于人类专家。

Introduction

传统RL是十分依赖特征表示的质量。
深度学习进展能够很好地提取高级特征，试图将该技术应用于RL。
从深度学习角度看强化学习存在挑战：
a. 与监督学习中发现的投入与目标之间的直接联系相比，行动与所产生的奖励之间的延迟可能长达数千个时间步。
b. 大多数深度学习算法都假设数据样本是独立的，而在强化学习中，典型地会遇到高度相关状态的序列。
c. 数据分布会随着算法学习新行为而发生变化，这对于采用固定基础分布的深度学习方法可能会产生问题。
本文证明了卷积神经网络可以在复杂的RL环境中从原始视频数据中学习成功的控制策略。
使用Q-learning 算法的变种进行训练，同时使用SGD进行更新。
为了缓解数据相关性和非稳定分布是问题，本文使用reply mechanism。
网络没有任何特定游戏信息或者手工设计的特征，不参与模拟器内部状态。训练过程中，网络结构和超参数保持不变。

BackGround

符号：
Enviroment: ε
Action at t time-step: $a_t \in A\{1, ..., K\}$
Observations at t time-step: $x_t \in \mathbb{R}$
Reward at t time-step: $r_t$
State at t time-step: $\{x_1, a_1, x_2, ..., a_{t-1}, x_t\}$
Agent 看不到 Env. 内部。
可能很多回之后才能收到反馈（回个结束）。
假设所有序列都在有限时间内终止，则每个序列是一个有限的马尔可夫决策过程（MDP），表示为 $s_t$ 。则可利用标准强化学习方法学习MDPs，同时以最大化未来奖励的方式选择动作同Env.交互。
公式：
a. discount factor (per time-step to rewards): $\gamma$
b. future dicounted return at time t: ${R_t=\sum^{T}_{t'=t}{\gamma^{t'-t}r_{t'}}}$
T is the time-step at which the game terminates.
c. optimal action-value function
$Q^*(s,a)=max_\pi E[R_t|s_t=s, a_t=a,\pi]$
$\pi$ is a policy mapping sequences to actions.
d. 优化 action-value 方程服从 Bellman equation. 基于下列直觉: if the optimal value $Q^*(s', a')$ of the sequence $s'$ at the next time-step was known for all possible actions $a'$ , then the optimal strategy is to select the action $a'$ maximising the expected value of ${r+\gamma Q^*(s', a')}$ , ${Q^*(s,a)=E_{s'\sim\varepsilon }[r+\gamma \max_{a'} Q^*(s', a')|s,a]}$
e. 基础的强化学习利用Bellman 方程去更新 $Q_{i+1}(s,a)=E[r + \gamma \max_{a'} Q_i(s',a')|s,a]$ 从而value-action function 收敛于 $Q_i \rightarrow Q^*\ as \ i \rightarrow \infty$
但在实践中，这样基础的方法是完全不合理的， action-value 方程分别对每个序列进行了估计，但是没有进行归纳。
f. 相反的，通常使用一个方程去逼近 action-value 方程 $Q(s,a;\theta)\approx Q^*(s, a)$
在强化学习中通常会使用线性方程进行逼近，但有时也会用非线性方程逼近，例如神经网络。
g. 我们使用带有 $\theta$ 的神经网络进行逼近，称为 Q-network， Q-network可以被训练最小化每次迭代i的损失函数 $L_i(\theta_i)$ ： ${L_i(\theta) = E_{s,a\sim\rho(\cdot)}[(y_i-Q(s,a;\theta_i))^2]}$
where ${y_i=E_{s'\sim\varepsilon }[r+\gamma \max_{a'} Q^*(s', a';\theta_{i-1})|s,a]}$ 是迭代i的目标， $\rho (s,a)$ 是序列s和动作a上的概率分布，称为behabiour distribution.
h. 当优化损失函数 $L_i(\theta_i)$ 的时候 $\theta_{i-1}$ 固定。并且target依赖于网络权重，这和监督学习相反。
i. 通过随机梯度下降优化损失函数。
${\bigtriangledown_{\theta_i}L_i(\theta_i)=E_{s,a\sim\rho(\cdot);s'\sim \epsilon}[(r+\gamma\max_{a'}Q(s',a';\theta_{i-1}-Q(s,a;\theta_i))\bigtriangledown_{\theta_i}Q(s,a;\theta_i))]\cdot}$
j. 如果权重每一步都更新，期望替换为行为分布 $\rho$ 和环境中的单个样本，那么就是Q-learning.
h. 这个算法是model-free的，直接使用来自 $\varepsilon$ 的样本，而不去统计样本分布。
k. 同时是off-policy的，使用 $\epsilon-greedy$ 策略，按 $\epsilon$ 的概率随机选择action，保证对状态空间的充分搜索。

Related work

TD-gammon（Q-learning+多层感知机）在五子棋上的c成功与在其他任务上的失败。表明，将model-free的强化学习，如Q-learning同非线性逼近函数或者是off-police学习相结合，会导致Q-network的不收敛。
目前深度学习与强化学习结合的进展很好，但是都没有解决非线性控制的问题。
neural fitted Q-learning 与该文章工作类似，但是该文章工作直接使用从视觉端到端的应用强化学习，而不先学习数据的低位表示。

Deep Reinforcement Learning

Deep-learning + Reinforcement-learning 前途一片光明，作者如是说。
experience replay方法，将Agent 的结果存到集合 $D=e_1,\cdots e_N$ ，其中 $e_t=(s_t, a_t, r_t, s_{t+1})$ 。在算法内循环中，随机抽取 $e\sim D$ 用于训练，执行experience reply 之后按照 $\varepsilon$ -greedy 策略选择action并且执行。
DQN优势
a.经验的每个步骤可能在许多选中更新中使用，可以提高数据效率。
b. 将样本随机化会破坏这些相关性，减少更新差异。
c. 当学习策略时，当前的参数确定训练参数的下一个数据样本。
d. 通过使用 experience replay，行为分布在许多先前状态中得到平均，从而避免了参数波动或者发散。
e. 更新时候使用的样本，从D中采样，所以当前参数与生成样本时候参数不同，会激发学习能力，实际上，只存储N个体验，并执行均匀采样。