写在前面

大家好，好久不见，这里是新人Nobody，立志于在有生之年看到并参与通用人工智能开发工作。这一部分是一起入门强化学习的第二部分，这一部分主要介绍马尔可夫决策过程，由于这一部分比较晦涩且篇幅较长，大家可以先关注点赞收藏，之后慢慢看。

第一部分为和我一起入门强化学习（一），大家没看过的可以先看这一部分。

以下为本文的思维导图

马尔可夫决策过程思维导图.png

一、马尔可夫过程

在介绍马尔可夫决策过程之前，咱们先介绍它的简化版本：马尔可夫过程以及马尔可夫奖励过程。

1.1 马尔可夫性质

在随机过程中，马尔可夫性质（Markov property）是指一个随机过程在给定现在状态以及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。简而言之，就是一个随机过程的下一状态只取决于当前步的状态，与前面的状态无关。

以离散随机过程为例，状态 s_t+1对于过去状态的条件概率分布仅是 s_t的一个函数，即

p(s_{t+1}|s_{0:t})=p(s_{t+1}|s_{t})

也可以理解成，在给定当前状态时，将来状态和过去状态是条件独立的。如果一个过程具有马尔可夫性质，那么未来的转移与过去的事独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

1.2 马尔可夫过程/马尔可夫链

马尔可夫过程是一组具有马尔可夫性质的随机变量序列 s₁，…，s_t，其中一个时刻的状态s_t+1只取决于当前状态 s_t。我们设历史状态为 h_t={s₁，…，s_t}，则马尔可夫过程满足条件：

p(s_{t+1}|s_t)=p(s_{t+1}|h_t)

离散时间上的马尔可夫过程也称为马尔可夫链（Markov chain）。

马尔可夫链.png

如图为马尔可夫链，图上有4个状态，这4个状态在 s₁、s₂、s₃、s₄ 之间互相转移。比如从 s₁开始，它有0.1的概率不动，有0.2的概率转移到 s₂，有0.7的概率转移到 s₄。我们可以用状态转移矩阵（state transition matrix）P来描述状态转移。

P=\begin {bmatrix} p(s_1|s_1) & p(s_2|s_1) & … & p(s_N|s_1)\\ p(s_1|s_2) & p(s_2|s_2) & … & p(s_N|s_2)\\ … & … & … & …\\ p(s_1|s_N) & p(s_2|s_N) & … & p(s_N|s_N) \end{bmatrix}

状态转移矩阵表示当我们知道当前我们在状态 s_t 时，到达其他所有状态的条件概率。所以它的每一行描述的是从一个节点到所有其他节点的概率。

二、马尔可夫奖励过程

马尔可夫奖励过程（Markov reward process，MDP）是马尔可夫链加奖励函数，它只是比马尔可夫过程多了一个奖励函数。奖励函数 R 是一个期望，它表示当我们到达某一状态的时候可以获得多大的奖励。

2.1 回报与价值函数

我们要再提前说明一些枯燥的定义。首先，范围（horizon）是指一个回合的长度（每一个回合最大的时间步数），它是由有限个步数决定的。回报（return）是指把奖励进行折扣后所获得的奖励。回报可以定义为奖励的逐步叠加：

G_t=r_{t+1}+\gamma{r_{t+2}}+\gamma^2{r_{t+3}}+\gamma^3{r_{t+4}}+\gamma^4{r_{t+5}}+…+\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^{T-t-1}{r_{T}}|s_t=s]

其中，G_t是之前定义的折扣回报（discount return），因此期望可以看成是未来可能获得奖励对于当前价值的表现，就是当我们进入某一个状态后，现在有多大的价值。

为什么要使用折扣因子：

某些马尔可夫链是带环的，我们不希望奖励无穷无尽
我们建立的模型有不确定性，因此用折扣因子来模拟这种对模型未来评估的不确定性
如果奖励是有实际价值的，我们更希望马上获得奖励。折扣因子是一个超参数，我们可以根据未来奖励的重要性对其进行调整。

如图所示，马尔可夫奖励过程仍旧是状态转移，我们可以暂时把奖励函数定为：当智能体进入第一个状态 s₁的时候会获得5点奖励，进入第七个状态 s₇ 会获得10点奖励，奖励函数向量表示如下：

R=[5,0,0,0,0,0,10]

我们假设4步回合，其中折扣因子为0.5，来采样回报G：

(1)s_4,s_5,s_6,s_7:0+0.5*0+0.25*0+0.125*10=1.25\\ (2)s_4,s_3,s_2,s_1:0+0.5*0+0.25*0+0.125*5=0.625\\ (3)s_4,s_5,s_6,s_6:0+0.5*0+0.25*0+0.125*0=0

纸船.png

我们可以把马尔可夫过程看作一个纸船随机漂流，往哪个方向漂流都有一定的概率，没有人为决策干预。马尔可夫奖励过程就是在纸船漂流过程中给予一定的奖励。

我们有了一些轨迹的实际回报了，那如何计算价值函数呢？其中一个可行的办法是从 s₄开始生成很多条轨迹，计算这些轨迹对应的回报的平均值，即价值函数，也就是蒙特卡洛（Monte Carlo，MC）方法。

2.2 贝尔曼方程

我们也可以从价值函数推导出贝尔曼方程：

V(s)=R(s)+\gamma\sum_{s’∈S}p(s’|s)V(s’)，其中R(s)为即时奖励，\gamma\sum_{s’∈S}p(s’|s)V(s’)为未来奖励的折扣总和

其中，s’ 可以看成未来的所有状态，p(s’|s) 是指从当前状态转移到未来状态的概率。V(s’)代表的是未来某一个状态的价值。贝尔曼方程定义了当前状态与未来状态之间的关系。

贝尔曼方程推导过程如下

\begin{aligned} V(s)&=E[G_t|s_t=s] \\ &=E[r_{t+1}+\gamma{r_{t+2}}+\gamma^2r_{t+3}+…|s_t=s]\\ &=E[r_{t+1}|s_t=s]+\gamma{E[{r_{t+2}}+\gamma{r_{t+3}}+\gamma^2r_{t+4}+…|s_t=s]}\\ &=R(s)+\gamma{E[G_{t+1}|s_t=s]}\\ &=R(s)+\gamma{E[V(s_{t+1})|s_t=s]}\\ &=R(s)+\gamma\sum_{s’∈S}p(s’|s)V(s’) \end{aligned}

贝尔曼方程就是当前状态与未来状态的迭代关系，表示当前状态的价值函数可以通过下个状态的价值函数来计算。未来奖励的折扣总和加上即时奖励，就组成了贝尔曼方程。

当我们把贝尔曼方程写成矩阵形式后，可以直接求解

V=R+\gamma{PV}\\ IV=R+\gamma{PV}\\ (I-\gamma{P})V=R\\ V=(I-\gamma{P})^{-1}R

我们可以通过矩阵求逆的方法将价值直接求出来，但是矩阵求逆的复杂度是O(N^3)，时间复杂度过高，求解十分困难。

2.3 计算马尔可夫奖励过程价值的迭代算法

因此，有以下其他几种迭代方法可以应用于状态非常多的马尔可夫奖励过程

动态规划方法
蒙特卡洛方法
时序差分学习（动态规划+蒙特卡洛）

这里因为篇幅原因，仅简单介绍蒙特卡洛方法。

首先，我们将一个智能体放到状态转移矩阵中，让它想咋走就咋走，这样就会产生一条轨迹，产生一条轨迹之后，就会获得一个奖励。
其次，起点不变，随机生成大量轨迹。
最后，将这些轨迹所获得的奖励相加除以轨迹个数，即某个状态的价值。

大家想看其他方法的话，可以之后再加个番外篇哈哈哈。

三、马尔可夫决策过程

相比于马尔可夫奖励过程，马尔可夫决策过程多了决策，即动作。**未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作。**马尔可夫决策过程满足条件

p(s_{t+1}|s_t,a_t)=p(s_{t+1}|h_t,a_t)

即当前的状态以及采取的动作会决定智能体在当前可能得到的奖励多少。

马尔可夫决策过程可以表示为五元组<S，A，P，R，γ>。

3.1 策略

策略定义了智能体在某一状态应该采取什么样的动作，知道当前状态后，我们可以将当前状态代入策略函数来得到一个概率，即

\pi{(a|s)}=p(a_t=a|s_t=s)

已知马尔可夫决策过程和策略，我们可以把马尔可夫决策过程转换成马尔可夫奖励过程。在马尔可夫决策过程中，状态转移函数基于它当前的状态以及它当前的动作。因为我们现在已知策略函数，也就是已知在每一个状态下可能采取的动作概率，所以我们就可以转换成马尔可夫奖励过程，也就是没有了动作

p_{\pi}(s’|s)=\sum_{a∈A}\pi(a|s)p(s’|s,a)

对于奖励函数，我们也可以把动作去掉

R_{\pi}(s)=\sum_{a∈A}\pi(a|s)R(s,a)

3.2 马尔可夫决策过程和马尔可夫过程/马尔可夫奖励过程的区别

区别.png

如图所示，区别如下：

马尔可夫过程/马尔可夫奖励过程的状态转移是直接决定的。比如当前状态是 s，其直接通过转移概率决定下一个状态是什么
对于马尔可夫决策过程，它中间多了一层动作 a，即智能体在当前状态，首先要决定采取哪种动作，所以当智能体当前状态以及智能体当前采取的动作决定之后，智能体进入未来的状态也是一个概率分布。马尔可夫决策过程和马尔可夫过程/马尔可夫奖励过程的区别是：在当前状态与未来状态转移过程中多了一层决策性。

3.3 马尔可夫决策过程中的价值函数

马尔可夫决策过程中的价值函数可以定义为

V_{\pi}=E_{\pi}[G_t|s_t=s]

其中，期望基于我们采取的策略。当策略决定后，我们通过对策略进行采样来得到一个期望，计算出它的价值函数。

我们还需要引入一个Q函数（Q-function）。Q函数也被称为动作价值函数（action-value function）。

Q函数定义：在某一个状态采取某一个动作可能得到的回报的期望，即

Q_{\pi}(s,a)=E_{\pi}[G_t|s_t=s,a_t=a]

由于这里的期望是基于策略函数的，所以我们对策略函数进行一个求和，然后得到它的价值，对Q函数中的动作进行求和，就可以得到价值函数。

V_{\pi}(s)=\sum_{a∈A}\pi(a|s)Q_{\pi}(s,a)

我们还可以对Q函数的贝尔曼方程进行推导

\begin{aligned} Q(s,a)&=E[G_t|s_t=s,a_t=a] \\ &=E[r_{t+1}+\gamma{r_{t+2}}+\gamma^2r_{t+3}+…|s_t=s,a_t=a]\\ &=E[r_{t+1}|s_t=s,a_t=a]+\gamma{E[{r_{t+2}}+\gamma{r_{t+3}}+\gamma^2r_{t+4}+…|s_t=s,a_t=a]}\\ &=R(s,a)+\gamma{E[G_{t+1}|s_t=s,a_t=a]}\\ &=R(s,a)+\gamma{E[V(s_{t+1})|s_t=s,a_t=a]}\\ &=R(s,a)+\gamma\sum_{s’∈S}p(s’|s,a_t=a)V(s’) \end{aligned}

我们可以发现，相比于马尔可夫奖励过程的贝尔曼方程，Q函数的贝尔曼方程仅是多了一个动作a。

3.4 贝尔曼期望方程

我们可以将状态价值函数和Q函数分为两部分：即时奖励和后续状态的折扣价值。因此，通过将状态价值函数进行分解我们可以得到其贝尔曼期望方程。即

V_{\pi}(s)={E_{\pi}[r_{t+1}+\gamma{V(s_{t+1})|s_t=s]}}

类似的，我们可以得到Q函数的贝尔曼期望方程

Q(s,a)=E[r_{t+1}+\gamma{Q(s_{t+1},a_{t+1})|s_t=s,a_t=a}]

贝尔曼期望方程定义了当前状态与未来状态之间的关联。

为了进一步地说明Q函数，我们先给出Q函数和状态价值函数之间的关系（对动作进行求和）

V_{\pi}=\sum_{a∈A}\pi(a|s)Q_{\pi}(s,a) (1)

Q_{\pi}(s,a)=R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_{\pi}(s’)}(2)

将(2)式代入(1)式，可以得到

V_{\pi}(s)=\sum_{a∈A}\pi(a|s)(R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_{\pi}(s’)})

其代表当前状态的价值与未来价值之间的关联

将(1)式代入(2)式，可以得到

Q_{\pi}(s,a)=R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)\sum_{a’∈A}\pi(a’|s’)Q_{\pi}(s’,a’)}

其代表当前时刻的Q函数与未来时刻的Q函数之间的关联

以上两个式子是贝尔曼期望方程的另一种形式。

3.5 备份图

先介绍备份（backup）的概念：备份类似于自举之间的迭代关系，对于某一个状态，它的当前价值是与它的未来价值线性相关的。

以下两张图被称为备份图，它们所示的关系构成了更新或备份操作的基础，而这些操作是强化学习方法的核心。这些操作将价值信息从一个状态（或状态-动作对）的后继状态（或状态-动作对）转移回它。每一个空心圆圈代表一个状态，每一个实心圆圈代表一个状态动作对。

V的备份图.png

如图所示，这里有两层加和，第一层加和是对叶子节点进行加和，往上备份一层，我们就可以把未来的价值（s’的价值）备份到黑色的节点。第二层加和是对动作进行了加和，得到黑色节点的价值后，再往上备份一层，就会得到根节点的价值，即当前状态的价值。

V_{\pi}(s)=\sum_{a∈A}\pi(a|s)Q_{\pi}(s,a)

Q_{\pi}(s,a)=R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_{\pi}}(s’)

V_{\pi}(s)=\sum_{a∈A}\pi(a|s)(R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_{\pi}}(s’))

Q的备份图.png

这里也有两层加和。第一层加和先把叶子节点从黑色节点推到空心圆圈节点，进入到空心圆圈节点的状态。当到达某一个状态后，再对空心圆圈节点进行加和，这样就把空心圆圈节点重新推回到当前时刻的Q函数。

V_{\pi}(s’)=\sum_{a∈A}\pi(a’|s’)Q_{\pi}(s’,a’)

Q_{\pi}(s,a)=R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)}\sum_{a∈A}\pi(a’|s’)Q_{\pi}(s’,a’)

3.6 策略评估

策略评估：已知马尔可夫决策过程以及要采取的策略，计算价值函数的过程。

摆渡.png

我们可以将马尔可夫决策过程看作是一个摆渡人在驾驶小船，他控制着船按照自己的决策往自己预想的地方驶去，也就是奖励最大的地方。

3.7 预测与控制

预测和控制是马尔可夫决策过程中的核心问题

预测（评估一个给定的策略）的输入是马尔可夫决策过程<S, A, P, R, γ>和策略，输出的是价值函数。预测是指给定一个马尔可夫决策过程以及一个策略，计算它的价值函数，也就是计算每一个状态的价值。
控制（搜索最佳策略）的输入是马尔可夫决策过程<S, A, P, R, γ>，输出是最佳价值函数和最佳策略。控制是我们去寻找一个最佳的策略，然后同时输出它的最佳价值函数和最佳策略。

3.8 动态规划

动态规划（dynamic programming，DP）适合解决具有最优子结构和重叠子问题两个性质的问题。

其中马尔可夫决策过程是满足动态规划的要求的，在贝尔曼方程中，我们可以把它分解成递归的结构。当我们把它分解成递归的结构的时候，如果子问题的子状态能得到一个值，那么它的未来状态因为与子状态是直接相关的，我们也可以将之推算出来。

因此使用动态规划完成预测问题和控制问题的求解，是解决马尔可夫决策过程预测问题和控制问题的有效方式。

3.9 使用动态规划进行策略评估

策略评估就是给定马尔可夫决策过程和策略，评估我们可以获得多少价值。

我们可以直接把**贝尔曼期望备份（Bellman expection backup）**变成迭代的过程，反复迭代直到收敛。

V_{t+1}(s)=\sum_{a∈A}\pi(a|s)(R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_t(s’)})

上述式子是指我们可以把贝尔曼期望备份转换为动态规划的迭代。当我们得到上一时刻的V_t，就可以通过递推关系推出下一时刻的值，反复迭代就可以得到最后收敛的 V值，V值即当前给定的策略对应的价值函数。

策略评估的核心思想：将上式所示的贝尔曼期望备份反复迭代，然后得到一个收敛的价值函数的值，因为给定了策略函数，因此我们可以把它简化成一个马尔可夫奖励过程的形式，相当于把动作a去掉，即

V_{t+1}(s)=R_{\pi}(s)+\gamma{p_{\pi}(s’|s)V_t(s’)}

通过迭代上式，我们也可以得到每个状态的价值，因为不管是在马尔可夫奖励过程还是在马尔可夫决策过程中，价值函数V包含的变量都只与状态有关。它表示智能体进入某一状态，未来可能得到多大的价值。

我们以一个网格世界采用动态规划策略评估的可视化界面为例

初始化界面.png

上图为网格世界，其中有很多格子，每一个格子都代表一个状态。每个格子里有一个初始值0。每一个格子还有一个箭头，箭头是指智能体在当前状态应该采取什么样的策略，这里采取的是随机策略，也就是上下左右各为0.25的概率。我们可以看到有几个格子的奖励是-1，只有一个格子的奖励是1。

迭代一次.png

我们迭代一次，可以发现有些状态的值已经发生了变化。比如有些状态的R值为-1，迭代一次之后，它就会得到-1的奖励，对于中间的格子，因为它的奖励为正，所以它是值为+1的状态。

迭代两次.png

我们再迭代一次，之前有值的状态的周围状态也都开始有值。因为周围状态与之前有值的状态是相邻的，就相当于把周围的状态转移过来。

迭代多次.png

我们这样迭代多次之后，各个状态的值会稳定下来，收敛之后，各个状态的值就是它的状态价值。

这个是网址，大家可以自己去玩玩看。

cs.stanford.edu/people/karp…

3.10 马尔可夫决策过程控制

策略评估是指给定马尔可夫决策过程和策略，估算价值函数的值。如果我们只有马尔可夫决策过程，那么如何寻找最佳策略，得到最佳价值函数呢？

首先定义最佳价值函数（optimal value function）

V^*(s)=max_{\pi}V_{\pi}(s)

最佳价值函数是指我们搜索一种策略让每个状态的价值最大。V*就是到达每一个状态，其值的最大化情况，在这种最大化情况中，我们得到的策略就是最佳策略，即

\pi^*(s)=argmax_{\pi}V_{\pi}(s)

但是如何搜索最佳策略呢？最简单的一种方法就是穷举法了，但是穷举法的效率太低，我们搜索最佳策略有两种方法。

策略迭代
价值迭代

而寻找最佳策略的过程就是马尔可夫决策过程的控制过程。

3.11 策略迭代

策略迭代分为以下两个步骤：

策略评估：当我们在优化策略时，在优化过程中得到一个最新的策略，我们先保证这个策略不变，然后估计它的价值，即给定当前的策略函数来估计状态价值函数
策略改进：得到状态价值函数后，我们可以进一步推算出它的Q函数，得到Q函数后，直接对Q函数进行最大化，通过对Q函数做一个贪心搜索来进一步改进策略。

针对于策略改进，是如何进行的呢？

我们得到状态价值函数后，我们就可以通过奖励函数以及状态转移函数来计算Q函数

Q_{\pi_i}(s,a)=R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_{\pi_i}}(s’)

对于每一个状态，策略改进可以得到新一轮的策略，我们取能够使它得到Q函数最大值的动作，即

\pi_{i+1}(s)=argmax_aQ_{\pi_i}(s,a)

策略迭代.png

除此以外，我们还可以把Q函数看成一个Q表格（Q-table）：横轴是它的所有状态，纵轴是它的可能的动作。对于某个状态，我们会取每一列中的最大值，其对应的动作就是它现在应该采取的动作。

Q表格.png

当我们已知采取argmax操作时，会得到一个单调的递增。通过贪心操作，我们就会得到更好的或者不变的策略，而不会使价值函数变差，所以当改进停止后，我们就会得到一个最佳策略。

3.12 价值迭代

3.12.1 最优性原理

最优性原理定理（principle of optimality theorem）：一个策略在状态 s 达到了最优价值，也就是 V_Π(s)=V(s)，当且仅当对于任何能够从 s 到达的 s’ ，都已经达到了最优价值。也就是对于所有的 s‘，V_Π(s)=V(s) 恒成立。

3.12.2 确认性价值迭代

假设我们知道子问题的最优解，就可以通过价值迭代来得到最优的 V*(s) 的解。价值迭代就是把贝尔曼最优方程当成一个更新规则来进行，即

V(s)=max_{a∈A}(R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V(s’)})

为了得到最优的状态价值函数，对于每个状态的状态价值函数，我们直接通过贝尔曼最优方程进行迭代，迭代多次之后，价值函数就会收敛。这种价值迭代算法也被称为确认性价值迭代（deterministic value iteration）。

3.12.3 价值迭代算法

算法过程如下：

初始化：令 k=1，对于所有状态 s，V₀(s)=0
对于 k=1: H（H为迭代数）
- 对于所有状态 s
  $Q_{k+1}(s,a)=R(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_k(s’)}$ $V_{k+1}(s)=max_a(Q_{k+1}(s,a))$
- k = k + 1
在迭代后提取最优策略
$\pi(s)=argmax_aR(s,a)+\gamma{\sum_{s’∈S}p(s’|s,a)V_{k+1}(s’)}$