一. 强化学习

1. 什么是强化学习问题？

强化学习是机器学习领域的三大分支之一，深度学习＋强化学习也被认为是通往通用AI的道路。

强化学习问题可以描述为agent从environment中获取观察的state和获取reward，并产生action作用于environment。如上图描述所示。用数学语言描述就是Markov Decision Process（MDP）。

2. 强化学习的理论体系

(1) MDP

强化学习问题可以用MDP来描述。在说MDP之前，需要先了解Markov Property和Markov Process。

i) Markov Property

简言之，当前状态包含了过去所有状态的信息，一旦当前状态信息已知，过去状态信息就可以抛弃。
Markov Property除了包含有这一信息，还有就是状态转移概率$\Rho$。

ii) Markov Process

在说MDP之前要说的就是Markov Process了。

下面是Markov Process的例子。

左面的图是Markov Process的实际体现。圆圈中代表不同的state，以及曲线上的状态转移概率（state transition probability）。

我们可以从这个描述中随机的取样，以$Class 1$为初始状态，上图右侧是部分sample的episodes（即从初始状态到终止状态的路径，包含所有走过的中间状态）。

描述了从Markov Process中sample episodes后，对应的就是在sample时各个state之间的转移概率。下图描述的便是状态转移概率。

iii) Markov Decision Process

说完了Markov Property和Markov Process,现在应该说一下Markov Decision Process了。

MDP中除了之前说的$S,P$之外，还有$A(action),R(reward),\gamma$等信息，所有的这些才构成了MDP的要素。

强化学习问题是通过找到最优的策略（对应MDP的元素，也就是选择最优的$state$，在不同的$state$上选择最优的$action$）来使获得的$reward$最大。

我们将会逐渐的说明所有要素后再回顾MDP的完整架构。

(2) $R(reward)$

$reward$的定义如下：

为什么是从$R_{t+1}$开始呢,是因为回报函数的意义是在$t$时刻,执行一步$action$后到下一状态的回报值.
我们可以通过上面提到的那个例子, 把$reward$的部分添加上, 来理解$G_{t}$式子的意义.
从图中可以看到, 只有从一个状态转移到另一个状态的时候, 才会有奖励值, 这个设置方式正是MDP的设置方式.

为什么需要有$\gamma$ ?

$\gamma$越接近0，表示越注重当前回报，当$\gamma=0$时，$G_{t}=R_{t+1}$, 表示只以执行一次$action$后的$reward$作为最终的$reward$, 此时系统只关注眼前的利益.
$\gamma$越接近1, 表示系统的眼光更长远, 当$\gamma=1$时, $G_{t}$代表从当前步一直到目标所有的奖励值之和, 考虑到所有的奖励情况.

现在, 我们已经有个$reward$的计算公式, 只要遍历MDP结构的所有结点, 就可以得到$G_t$的最大值, 也就可以得到相应的最优的策略. 但问题是, 对于小规模的问题, 这样计算没有问题, 但是大规模的问题, 只有当某个$state$开始, 已知到目标全部遍历完成, 才可以得到这个$state$能获得的最终的$reward$, 计算效率很低.

因此, 再引入一个概念, $value function$.

(3) $Value\ Function$

从定义来看, $value \ function$就是在$S_t$状态下回报的期望值.
从实际意义来理解,就是从$S_t$状态开始,能获得总$reward$的估计,体验出了这个状态的价值.
还是以上面提到的例子来解释.


对于$C1$状态的$value\ function$,就是以$C1$为初始状态一直到终止状态每个episode回报值的平均值.

以$value\ function$代替$G_t$作为评价标准,来寻找最优的策略,那么下面的问题就是求解$value\ function$,只要能解出$value\ function$的最大值,对应的episode就是最优的策略.

(4) $Bellman Equation$

为了求解$value\ function$,我们将$value\ function$展开.

最后的一个等式是因为期望体现在实际的MDP结构中,就是$S_t$到$S_{t+1}$不同的概率乘以$v(S_{t+1})$.

$Bellman Equation$表示的是以迭代的方式求解$value\ function$.
为了求解$Bellman Equation$,我们将其表示为矩阵的形式.
通过此段文字上面的图片的说明,就可以推出下面矩阵的表示形式.

因为$Bellman Equation$是线性方程,所以对于简单的MDP问题,可以直接求解.对于复杂的MDP问题,可以通过迭代的方式求解.

自此,已经说了MDP中的$S,R,P,\gamma$,还有一个重要的元素没有说:$A(action)$.

(5) $Action$

$state$于$action$之间是输入输出的关系,给一个$state$,通过一个函数,输出一个动作或者动作的概率,这个函数就是要说的$Policy$.
一个环境中所有可行的$action$一般称为$action\ spaces$,分为$discrete\ action\ spaces$(例如Atari游戏的action)和$continuous\ action\ space$(例如在真实的世界里控制机器人的动作).

(6) $Policy$

$Policy$的定义如下:

一个$policy$是$agent$用来决定采取什么样的$action$的规则,可以是确定性的策略$(deterministic policy)$,用$a_t=\mu(s_t)$来表示.
对于随机策略$(stochastic\ policy)$,用$a_t\backsim\pi(\cdot|s_t)$来表示.
在深度强化学习中,我们会使用带参数的$policy$,因为在Deep RL中,$policy$的输出是根据一系列参数来的(比如神经网络的weights和bias),神经网络通过优化参数,来调整$policy$朝着更优的动作优化.
在Deep RL中,我们用$a_t=\mu_\theta(s_t),\quad a_t\backsim\pi_\theta(\cdot|s_t)$分别来表示确定性策略和随机策略.

有了$policy$以后,就有对应的$action$输出,前面介绍了$value\ function$,用来表示某个状态的价值.有了$policy$以后,可以根据规则得到相应的动作输出,我们可以直接评定在某个状态下某个动作的价值,这就是$Action-Value\ Function$.

(7) $Action-Value\ Function$

通过$Bellman\ Equation$, $q_\pi(s,a)$同样可以使用迭代的式子来表示.

我们再来回顾下$value\ function$的原始表达式和迭代表达式.


现在有了$value\ function$和$action-value\ function$,还不足以得出最优的策略,所以需要找到最优的$policy$的算法.

(8) $Optimal\ Value\ Function$

怎样通过最优的$value\ function$和$action-value\ function$找到最优的$policy$呢?

在某个策略下的value function和action-value function的值是最大的,那么这个策略就是最优的策略.

所以只要求解出最优的value function或者action-value function,就可以得到最优的policy.
为了求解optimal value function and optimal action-value function,我们需要先表示出这两者的数学表达式,通常有下面几种表示方式:




有了optimal value function的表达式,我们就可以应用optimal value function and optimal action-value function 来求解出optimal policy.

(9) $Optimal\ Policy$

有很多种迭代的算法来求解optimal value function.我们说一下Value Iteration和Policy Iteration,这是两个主要的思想,Q-learning也是基于Value Iteration来做的.

i) Dynamic Programming

说到迭代求解,会应用到动态规划(Dynamic Programming),什么是Dynamic Programming?

简言之,动态规划就是问题可以描述为动态的序列或以时间顺序组织起来的,就可以把复杂的问题分解为一个个小问题来解决.
前面所说的Bellman Equation的形式,把原来需要求解全部的Reward的步骤,转换为求下一步的Reward和下一状态的价值,即下面的式子化简的形式,最后每次迭代,就可以求出每个状态的Value.这是Dynamic Programming用在MDP的规划中的prediction(预测)作用.下面求解最优Policy的时候还会看到Dynamic Programming在control方面的作用.



上图总结了DP(Dynamic Programming,下文以DP代替)在规划方面的两个作用:prediction & control.上面求value function使用的DP的prediction,下面求optimal policy,就会用到DP的control作用.

ii) Policy Iteration

Policy Iteration的目的是迭代计算value function,找到最优的value function,从而得到optimal policy.
我们用另一种形式来表示value function.

value function的表示都是根据Bellman Equation变化得来的.
Policy Iteration一般分为两步:Policy evaluation & Policy improvement.
Policy evaluation的目的是更新value function,在当前的策略下不断优化value function.
Policy improvement的目的是更新优化策略,使用greedy算法在当前的value function中找到最大的value.

具体的算法流程如下:

iii) Value Iteration

value iteration是使用最优Bellman Equation得到的

然后将其转化为迭代形式

具体算法如下:

value iteration和policy iteration有什么区别呢?
从算法中可以看到,policy iteration的迭代规则是
在Policy Evaluation阶段,V(s)的更新结果是在当前$\pi(s)$下的计算值,在Policy Improvement阶段,使用计算的V(s)在当前状态的action space中更新优化$\pi(s)$,然后优化的$\pi(s)$再在Evaluation阶段更新V(s),所以其实是对$\pi(s)$进行优化,所以是Policy Iteration.

Value Iteration的迭代规则是一直对V(s)进行更新,最后选择出最优的$\pi(s)$,所以value iteration相比policy iteration更加直接.

3 强化学习的算法体系

到此,强化学习的基本架构已经介绍完成,下面介绍Q-learning和DQN.

二. Q-Learning

1 什么是Q-Leaning

Q-Learning是采用value iteration的思想来做的,但是value iteration每次都会对Q值更新一遍,实际情况我们没法遍历所有的状态和动作,所以Q-Learning提出了一种新的更新Q值的方法:
$Q(S_t,A_t)\gets Q(S_t,A_t)+\alpha(R_{t+1}+\lambda\max\limits_aQ(S_{t+1},a)-Q(S_t,A_t))$
将$R_{t+1}+\lambda\max\limits_aQ(S_{t+1},a)$定义为target Q value,Q-Learning并没有将target q value直接赋给当前q值,而是采用渐进的方式靠近target q value,类似梯度下降的思想.
整个算法流程如下:

算法中需要一个policy来生成动作,这个policy并不是由Q值的迭代来更新的policy,所以q-learning算法也是off-policy的.那么这个policy选取的规则是怎样的?

1. 随机选取(exploration).随机选取有利于扩大搜索的空间,可能会探索到更多的状态和动作,有利于更加全局的更新q值.比如在一个区域内有很多餐馆,为了找到最好吃的那家,随机选取的结果就是当你第一天觉着一家特别好吃的时候,但是以后你每天都去不同的一家,这样就会更加全面的了解所有餐馆的情况,也就是可以拿到相对全局最优的Q值.
2. 贪婪选取(exploitation).根据当前的Q值选择最优的动作,这个policy $\pi$称为greedy policy,即$\pi(S_{t+1})=arg\max\limits_aQ(S_{t+1},a)$.

exploration有利于扩大搜索空间,找到更好的Q值,但是难收敛;exploitation可以快速收敛,但有可能不是最优的Q值,所以两者折中,使用$\epsilon-greedy\ policy$,通过调整$\epsilon$的值来调整exploration和exploitation的比例.

2 分解Q-Learning的计算过程

假设agent在这样的一个房子里,注意房间4和房间5是相通的.房间5是agent的目标房间.

我们可以用下图来表示这个房间的连通关系,注意现在的图还不能叫markov process,因为没有状态转移概率.
然后我们给每一个动作赋予奖励值Reward.因为房间5是目标房间,所以到达房间5的动作的reward为100,其他的reward都是0.

在学习的过程中,agent随机选取一个位置,然后不断学习,达到房间5.
我们假设agent从房间2开始,到达房间5.
从房间2,agent可以到房间3,获得奖励0,,然后到房间4,获得奖励0,到房间5,获得奖励100.但是从房间2不能直接到房间1.所以下面这个表总结了上图的可达房间和对应的奖励.State表示所处的房间,Action表示到某个房间的动作,比如矩阵的第一行第五列表示在房间0,到达房间4,获得奖励0. -1代表不能直接到达这个房间.

上节我们说到Q-Learning的公式为:
Q(S_t,A_t)\gets Q(S_t,A_t)+\alpha (R_{s+1}+\lambda \max \limits_a Q(S_{t+1},a)-Q(S_t,A_t))$$$\alpha$决定了当前Q值向target q值的渐进速度,如果让$\alpha=1$,target q值将会全部赋给当前q值,这也是q-learning算法的简化版本.我们将使用这个简化公式来表示下面的计算过程.Q(S_t,A_t) \gets R_{t+1}+\lambda \max \limits_a Q(S_{t+1},a)$$
对于当前走房间的问题,整个Q-Learning的算法流程如下:

1.设置lambda参数,reward矩阵R
2.初始化Q矩阵为0
3.对于每一个episode(从开始到目标成为一个episode):
● 随机选择一个初始房间
● 从当前状态的所有可能的action中选择一个
● 计算简化公式
● 直到到达goal,结束
复制代码

1.我们设置$\lambda=0.8$,然后手动计算Q-Learning的每个过程.设置初始房间为房间1.
2.将Q矩阵全部初始化为0

观察R矩阵,我们可以看到从房间1可以通往房间3(reward=0)和房间5(reward=100),我们选择去往房间5.
到达房间5后,可以看到有3个action可以选择:去往房间1,房间4和房间5.
现在来计算Q值.
$Q(S_t,A_t) \gets R_{t+1}+\lambda \max \limits_a Q(S_{t+1},a)$
Q(1,5)=R(1,5)+0.8 * max[Q(5,1),Q(5,4),Q(5,5)]=100+0.8 * 0=100

现在房间5成为当前状态,因为已经到达目标,所以一个episode完成,更新Q矩阵:

下一个episode,我们随机选择房间3为我们的初始状态,在房间3状态下,我们有去往房间1,2,4三种选择,我们随机选择去往房间1.(在这里,我们采用的是policy中的随机策略exploration,还有exploitation和$\epsilon -greedy\ policy$可以选择).
到达房间1后,我们有去往3,5两种选择,现在计算Q值:$Q(S_t,A_t) \gets R_{t+1}+\lambda \max \limits_a Q(S_{t+1},a)$
Q(3,1)=R(3,1)+0.8 * max[Q(1,3),Q(1,5)] = 0 + 0.8 * 100 = 80
更新Q矩阵

一直持续这个过程,经过很多episode后,Q矩阵会到达一个收敛值

我们对Q矩阵的数据都除以里面的最大值500进行归一化操作

现在我们就可以把Q矩阵的数据体现在下图中

不管在哪个状态,选择最大的Q值就会以最优的方式到达房间5.

三. DQN

直接从高维的数据输入例如视觉和语音来控制agents一直是强化学习领域的具有挑战性的工作。在DQN出现以前，大多数成功的RL应用案例是结合线性value function或者policy representation通过手动设计特征来做到的，算法的性能很大程度上依赖于设计的特征的质量。

深度学习的成功让直接从原始数据中提取特征成为可能，所以DQN尝试进行DL＋RL。

强化学习中应用深度学习有以下一些挑战：
① 深度学习（监督学习）需要大量的有标签的训练数据，应用到强化学习中去时，只能使用Reward来作为标签，但是reward通常来说是稀疏的、带有噪音并且是延时性的信号（通常是进行很多episode之后才给出reward）。
② 深度学习中标签数据和训练数据的联系是实时的，但是强化学习的reward是延时性的。
③ 大多数强化学习的问题都假设使用的数据是独立同分布（i.i.d）的，但是强化学习会遇到序列间高度相关的情况，同时强化学习会学习到新的动作，这对于深度学习是基于同样的动作分布来说是个挑战。

DQN使用以下操作来克服以上的困难：
① DQN使用的神经网络（监督学习）是用变种Q-Learning算法来训练，使用随机梯度下降（SGD）来更新权重。
② 使用replay机制来消除数据间的关联性，随机的在过去的transitions中取样。
③ 在Arcade Learning Environment中测试算法。

DQN的算法流程如下：

公式3如下：

为什么要用$Q(s,a,\theta)$而不用$Q(s,a)$呢？

在Q-Learning中，我们使用表格来表示Q(s,a)，但是这个在现实的很多问题上是几乎不可行的，因为状态实在是太多。使用表格的方式根本存不下。

举Atari为例子。

计算机玩Atari游戏的要求是输入原始图像数据，也就是210×160像素的图片，然后输出几个按键动作。总之就是和人类的要求一样，纯视觉输入，然后让计算机自己玩游戏。那么这种情况下，到底有多少种状态呢？有可能每一秒钟的状态都不一样。因为，从理论上看，如果每一个像素都有256种选择，那么就有：
256^210×160^
这简直是天文数字。所以，我们是不可能通过表格来存储状态的。我们有必要对状态的维度进行压缩，解决办法就是 价值函数近似Value Function Approximation。¹

价值函数近似Value Function Approximation ¹
什么是价值函数近似呢？说起来很简单，就是用一个函数来表示Q(s,a)。即
$Q(s,a)=f(s,a)$
f可以是任意类型的函数，比如线性函数：
$Q(s,a)=\omega_1 s + \omega_2 a + b$
其中$\omega_1,\omega_2,b$是函数f的参数。

大家看到了没有，通过函数表示，我们就可以无所谓s到底是多大的维度，反正最后都通过矩阵运算降维输出为单值的Q。

这就是价值函数近似的基本思路。

如果我们就用$\omega$来统一表示函数f的参数，那么就有
$Q(s,a) = f(s,a,w)$
为什么叫近似，因为我们并不知道Q值的实际分布情况，本质上就是用一个函数来近似Q值的分布，所以，也可以说是
$Q(s,a)\approx f(s,a,w)$

DQN中，作者使用$Q(s,a,;\theta) \approx Q^*(s,a)$来预估action-value function。

DQN更加具体的介绍请参见原文paper：
Playing Atari with Deep Reinforcement Learning