一. 强化学习

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

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

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

2. 强化学习的理论体系

(1). MDP

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

Markov Property

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

Markov Process

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

下面是Markov Process的例子。

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

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

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

Markov Decision Process

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

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

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

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

(2). $R(reward)$R(reward)

$reward$reward的定义如下：

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

为什么需要有$\gamma$γ ?

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

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

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

(3). $Value\ Function$Value Function

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


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

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

(4). $Bellman Equation$BellmanEquation

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

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

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

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

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

(5). $Action$Action

$state$state于$action$action之间是输入输出的关系,给一个$state$state,有对应的