马尔科夫决策过程（Markov Decision Process）揭秘

RL基本框架、MDP概念

MDP是强化学习的基础。MDP能建模一系列真实世界的问题，它在形式上描述了强化学习的框架。RL的交互过程就是通过MDP表示的。RL中Agent对Environment做出一个动作（Action），Environment给Agent一个反馈（Reward），同时Agent从原状态（ $S_{t}$ ）变为新状态（ $S_{t+1}$ ）。这里的反馈可以是正、负反馈；Agent执行动作是根据某个策略（Policy）进行的。

可以看到，强化学习和传统机器学习的区别是，它不能立即得到标记，而只能得到一个暂时的反馈（多为人为经验设定）。因此可以说强化学习是一种标记延迟的监督学习。

思考：MDP中，Environment是全部可观测的，部分可观测问题也能转化为MDP，如何理解？

Markov Property

假设状态的历史序列： $h_{t}$ ={ $s_{1}$ , $s_{2}$ , ... $s_{t}$ }，状态 $s_{t}$ 具有马尔科夫性，当且仅当

p( $s_{t+1}$ | $s_{t}$ )=p( $s_{t+1}$ | $h_{t}$ )，即“当给定现在(present)，未来(future)独立于过去(past)”。

换言之，马尔科夫性是指不具备记忆特质。未来的状态与任何历史的状态无关，仅与当前状态相关。

Markov Chain

马尔科夫链(Markov Chain)和马尔科夫过程(Markov Process)基本等价。（具备离散状态的马尔可夫过程，通常被称为马尔可夫链）。例如下图中有4个状态，箭头表示状态转移，数字表示转移概率。从一个节点出发的概率之和为1.

我们将状态转移矩阵用P表示，其中每个元素为p( $s_{t+1}$ = $s_{}^{'}$ | $s_{t}$ = $s$ )：

同样P的每一行之和为1.举一个具体例子：

上图的马尔科夫过程(MP)有7个状态，图中标出了每个状态去相邻状态或保留原地的概率。从 $s_{3}$ 出发的采样转移结果可能为：1) $s_{3}$ ， $s_{4}$ ， $s_{5}$ ， $s_{6}$ ， $s_{6}$ 2) $s_{3}$ ， $s_{2}$ ， $s_{3}$ ， $s_{2}$ ， $s_{1}$ 3) $s_{3}$ ， $s_{4}$ ， $s_{4}$ ， $s_{5}$ ， $s_{5}$ 等等，可以说马尔科夫过程（Markov process）是一个具备了马尔科夫性质的随机过程。

马尔科夫奖励过程（MRP）

MRP等于Markov Chain加上奖励，即MRP=Markov Chain+Reward。其中奖励函数(Reward function)是关键，R( $s_{t}$ = $s$ )=E[ $r_{t}$ | $s_{t}$ =s]。

现在，针对上述例子，把奖励放进去，假设 $s_{1}$ 对应奖励为+5， $s_{7}$ 对应奖励为+10，其余状态奖励为0，我们得到R的向量为：[5,0,0,0,0,0,10]。

值函数（Value Function）

首先定义反馈值的折扣求和（Discounted sum），其中 $\gamma\epsilon (0,1)$ ， $G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma ^{2}R_{t+3}+\gamma ^{3}R_{t+4}+...+\gamma ^{T-t-1}R_{T}$

再定义值函数， $V_{t}(s)$ =E[ $G_{t}$ | $s_{t}$ =s]=E[ $R_{t+1}+\gamma R_{t+2}+\gamma ^{2}R_{t+3}+\gamma ^{3}R_{t+4}+...+\gamma ^{T-t-1}R_{T}$ | $s_{t}$ =s]，表示从t时刻开始的未来的奖励。

为啥需要折扣因子 $\gamma$ ？

1. 避免在循环MRP中返回无限大的反馈值

2. 对未来的不确定性需要被完全表示出来

3. 有一层类似金融背景的含义：即时的反馈总是能赚取比延迟反馈更多的利益；对人类来说，更倾向于即时反馈

4. 若使用没有折扣的MRP，如 $\gamma$ =1，那么未来的反馈值就等于即时的反馈值；如 $\gamma$ =0，那么相当于只关心即时的反馈值

MRP的奖励计算举例

取 $\gamma$ =0.5，那么上图中，对于采样路径 $s_{4}$ ， $s_{5}$ ， $s_{6}$ ， $s_{7}$ 的奖励值是：0+0.5*0 +0.25*0 + 0.125*10 =1.25；对于采样路径 $s_{4}$ ， $s_{3}$ ， $s_{2}$ ， $s_{1}$ 的奖励值是：0+0.5*0 +0.25*0+ 0.125*5=0.625；对于采样路径 $s_{4}$ ， $s_{5}$ ， $s_{6}$ ， $s_{6}$ 的奖励值是：0

值函数的计算

利用Bellman equation（贝尔曼方程），即

V(s)包括两部分，即时奖励和未来奖励的折扣求和。

它的另一种表达方式是：

Bellman equation描述了状态（或状态的值）的迭代关系，举例说明：

假如有以下状态和状态转移矩阵（下图左），那么对于 $s_{1}$ 状态，它和它的下一个状态 $s_{1}$ 、 $s_{2}$ 、 $s_{4}$ 的状态转移关系和值迭代关系如下图右所示。

Bellman equation也可以写成矩阵的形式，

即在MRP中， $V=R+\gamma PV$ ，以及 $V=(I-\gamma P)^{-1}R$

因为矩阵的逆求解复杂度为 $O(N^{3})$ ，其中N为状态数。因此直接线性代数求解只适用于较小规模的MRP问题。

真正通用的求解方法是迭代算法，如动态规划算法(DP)、蒙特卡洛算法(MC)、时序差分算法(TD)。其中MC和TD都是无模型强化学习，适用于不知道概率转移情况的模型，但要注意，无模型强化学习并不代表不能被MDP描述，而是指其中的参数是未知的。

蒙特卡洛算法(MC)

MC用“采样”代替直接的策略评估，然后求平均累积奖励，作为期望累积奖励。关于某个状态的奖励返回的经验样本越多，能够得到的平均奖励值就越接近于期望的状态奖励值，井且收敛于这个值。具体如下

以下算法是等价的：

对于前面例子中 $s_{4}$ 的反馈值V( $s_{4}$ )，可能有如下采样过程和奖励返回值，从而计算平均值：

对于采样路径 $s_{4}$ ， $s_{5}$ ， $s_{6}$ ， $s_{7}$ 的奖励值是：0+0.5*0 +0.25*0 + 0.125*10 =1.25；对于采样路径 $s_{4}$ ， $s_{3}$ ， $s_{2}$ ， $s_{1}$ 的奖励值是：0+0.5*0 +0.25*0+ 0.125*5=0.625；对于采样路径 $s_{4}$ ， $s_{5}$ ， $s_{6}$ ， $s_{6}$ 的奖励值是：0，以此类推，最终求平均即可。

动态规划算法(DP)

如果说MC是一种基于一个事件又一个事件的算法（Episode by Episode），那么DP就是一个基于动作选择的算法（Step-by-Step）。两者具有非常多的相似之处。具体如下

其中核心语句是第4行，即Bellman equation

Markov Decision Process (MDP)

MDP是带有决策的MRP，即MDP=MRP+actions或MDP=MRP+decisions。MDP一般用5元组表示，即(S,A,P,R, $\gamma$ )。其中S是有限状态的集合；A是有限动作的集合；P是状态转移矩阵，对于每个action，有P( $s_{t+1}$ =s'| $s_{t}$ =s, $a_{t}$ =a)；R是反馈函数(或奖励值函数)，每个状态对应一个值或每个状态-动作对(State-Action)对应一个值，即R( $s_{t}$ =s, $a_{t}$ =a)=E( $r_{t}$ | $s_{t}$ =s, $a_{t}$ =a)； $\gamma$ 仍是折扣因子， $\gamma\epsilon (0,1)$ 。

MDP中策略(Policy)是指每个状态下应该执行什么动作，即它指定了动作的分布。策略表示为： $\pi (a|s)=P(a_{t}=a|s_{t}=s)$ ，即它是与时间t无关的。对于任意的t>0，有 $A_{t}$ ~ $\pi (a|s)$

MDP和MRP的转换

上图中，等式左边是MRP，等式右边是MDP；右边对动作a求和，消掉a，因此左边都没有a

MDP和MRP的比较

上图中，左边是MRP，右边是MDP；右边比左边多了一层a节点（黑色节点），表示动作；MRP直接从s状态映射（转移）到s'状态，而MDP先把状态s映射到动作a，通过 $\pi (a|s)$ ，再把动作a和状态s的组合映射到新的状态s'，通过P(s'|s,a)；体现了MDP=MRP+actions

MDP中的值函数

在策略 $\pi$ 下，状态s的值函数为： $v^{\pi }(s)=E_{\pi }[G_{t}|s_{t}=s]$ ，表示在初始状态为s的情况下采取策略 $\pi$ 得到的累积期望奖励值。动作值函数为： $q^{\pi }(s,a)=E_{\pi }[G_{t}|s_{t}=s,A_{t}=a]$ ，二者的关系是：