第2章

Markov决策过程
本章介绍强化学习最经典、最重要的数学模型—Markov决策过程（Markov Decision Process，MDP）。首先我们从离散时间智能体/环境接口引入Markov决策过程的定义，然后介绍在求解Markov决策过程时会用到的重要性质，最后介绍一种求解Markov决策过程最优策略的方法。

2.1　Markov决策过程模型

在智能体/环境接口中，智能体可以向环境发送动作，并从环境得到状态和奖励信息。本节将从离散时间的智能体/环境接口出发导出离散时间Markov决策过程模型，并介绍离散时间Markov决策过程模型的关键数学概念。

2.1.1　离散时间Markov决策过程

离散时间Markov决策过程模型可以在离散时间的智能体/环境接口的基础上进一步引入具有Markov性的概率模型得到。首先我们来回顾上一章提到的离散时间智能体/环境接口。
在离散时间智能体/环境接口中，智能体和环境交互的时刻为{0,1,2,3，...}。在时刻t，依次发生以下事情。

智能体观察状态的环境，得到观测，其中是,状态空间（state space），表示状态取值的综合；是观测空间（observation space），表示观测取值的集合。
智能体根据观测决定做出动作，其中是动作集合。
环境根据智能体的动作，给予智能体奖励，并进入下一步的状态。其中是奖励空间（reward space），表示奖励取值的集合，它是实数集R的子集。

在运行过程中，每一步的可能取值范围不同。很多时候，这是由于在不同观测下可选的动作集合可能不同造成的。为了分析方便，往往用一个包括所有可能动作的更大的集合来表示，使得每一步的动作集合在数学上可以用同样的字母表示。
注意：
① 不同的文献可能会用不同的数学记号。例如，有些文献会将动作后得到的奖赏记为，而本书记为。本书采用这样的字母是考虑到和往往是同时确定的。

② 这里的离散时间并不一定是间隔相同或是间隔预先设定好的时间。这里的离散时间指标只是表示决策和动作的指标。
一个时间离散化的智能体/环境接口可以用这样的轨道（trajectory）表示：

对于回合制的任务，可能会有一个终止状态。终止状态和其他普通的状态有着本质的不同：当达到终止状态时，回合结束，不再有任何观测或动作。所以，状态空间里的状态不包括终止状态。在回合制任务中，为了强调终止状态的存在，会将含有终止状态的状态空间记为

。回合制任务的轨道形式是：

其中T是达到终止状态的步数。
注意：回合制任务中一个回合的步数是一个随机变量。它在随机过程中可以视为一个停时（stop time）。
在时间离散化的智能体/环境中，如果智能体可以完全观察到环境的状态，则称环境是完全可观测的。这时，不失一般性地，可以令，完全可观测任务的轨道可以简化为：

这样就不需要再使用字母和了。
注意：智能体/环境接口没有假设状态是完全可观测的。部分不完全可观测的问题可以建模为部分可观测的Markov决策过程（Partially Observable Markov Decision Process，POMDP），并用相应方法求解。
在上述基础上进一步引入概率和Markov性，就可以得到Markov决策过程模型。定义在时间t，从状态和动作跳转到下一状态和奖励的概率为：

引入这一概念，我们就得到了Markov决策过程模型。值得一提的是，这样的概率假设认为奖励和下一状态仅仅依赖于当前的状态和动作，而不依赖于更早的状态和动作。这样的性质称为Markov性。Markov性是Markov决策过程模型对状态的额外约束，它要求状态必须含有可能对未来产生影响的所有过去信息。
注意：智能体/环境接口没有假设状态满足Markov性。Markov性是Markov决策过程的特点。另外，有时也能从不满足Markov性的观测中构造满足Markov性的状态，或者去学习Markov性。
如果状态空间S、动作空间A、奖励空间R都是元素个数有限的集合，这样的Markov决策过程称为有限Markov决策过程（Finite Markov Decision Process，Finite MDP）。

2.1.2　环境与动力

Markov决策过程的环境由动力刻画。本节介绍动力的定义和导出量。
对于有限Markov决策过程，可以定义函数为Markov决策过程的动力（dynamics）：

函数中间的竖线“|”取材于条件概率中间的竖线。
利用动力的定义，可以得到以下其他导出量。

状态转移概率：

给定“状态–动作”的期望奖励：

给定“状态–动作–下一状态”的期望奖励：

对于不是有限Markov决策过程的Markov决策过程，可以用类似的方法定义动力函数与导出量，只是定义时应当使用概率分布函数。动力的定义将离散空间的情况和连续空间的情况用统一的字母表示，简化了书写。
我们来看一个有限Markov决策过程的例子：某个任务的状态空间为，动作空间为，奖励空间为，转移概率由表2-1定义。

该Markov决策过程可以用状态转移图（见图2-1）表示。

2.1.3　智能体与策略

如前所述，智能体根据其观测决定其行为。在Markov决策过程中，定义策略（policy）为从状态到动作的转移概率。对于有限Markov决策过程，其策略可以定义为

对于动作集为连续的情况，可以用概率分布来定义策略。
如果某个策略对于任意的，均存在一个，使得

则这样的策略被称为确定性策略。这个策略可以简记为，即。
例如，对于表2-1的环境，某个智能体可以采用表2-2中的策略。

2.1.4　奖励、回报与价值函数

在第1章中已经介绍过，强化学习的核心概念是奖励，强化学习的目标是最大化长期的奖励。本节就来定义这个长期的奖励。
对于回合制任务，假设某一回合在第T步达到终止状态，则从步骤t（t回报（return）可以定义为未来奖励的和：

注意：在上式中，是一个确定性的变量，而回合的步数是一个随机变量。因此，在的定义式中，不仅每一项是随机变量，而且含有的项数也是随机变量。
对于连续性任务，上述的定义会带来一些麻烦。由于连续性的任务没有终止时间，所以会包括时刻以后所有的奖励信息。但是，如果对未来的奖励信息简单求和，那么未来奖励信息的总和往往是无穷大。为了解决这一问题，引入了折扣（discount）这一概念，进而定义回报为：

其中折扣因子。折扣因子决定了如何在最近的奖励和未来的奖励间进行折中：未来步后得到的1单位奖励相当于现在得到的单位奖励。若指定，智能体会只考虑眼前利益，完全无视远期利益，就相当于贪心算法的效果；若指定，智能体会认为当前的1单位奖励和未来的1单位奖励是一样重要的。对于连续性任务，一般设定。这时，如果未来每一步的奖励有界，则回报也是有界的。
注意：有些文献为连续性任务定义了平均奖励（average reward）。平均奖励的定义为，是对除以步数的期望求极限的结果。还有文献会进一步定义相对于平均奖励的回报，即让每一步的奖励都减去平均奖励后再求回报。
基于回报的定义，可以进一步定义价值函数（value function）。对于给定的策略，可以定义以下价值函数。

状态价值函数（state value function）：状态价值函数表示从状态开始采用策略的预期回报。如下式所示：

动作价值函数（action value function）：动作价值函数表示在状态采取动作后，采用策略的预期回报。如下式所示：

终止状态不是一个一般的状态，终止状态后没有动作。为了在数学上有统一的形式，一般定义，。
例如，对于表2-1和表2-2的例子，有：

下一节将为给定的动力和策略计算价值函数。

2.2　Bellman期望方程

2.1节定义了策略和价值函数。策略评估（policy evaluation）则是试图求解给定策略的价值函数。本节将介绍价值函数的性质—Bellman期望方程（Bellman Expectation Equations）。Bellman期望方程常用来进行策略评估。
Bellman期望方程刻画了状态价值函数和动作价值函数之间的关系。该方程由以下两部分组成。

用t时刻的动作价值函数表示时刻的状态价值函数：

（推导：对任一状态，有

这样就得到了结果。）如果用空心圆圈代表状态，实心圆圈表示状态–动作对，则用动作价值函数表示状态价值函数的过程可以用备份图（backup diagram）表示，见图2-2a。

用t+1时刻的状态价值函数表示时刻的动作价值函数：

（推导：对任意的状态和动作，有

其中用到了Markov性。利用上式，有

这样就得到了结果。）用状态价值函数表示动作价值函数可以用备份图表示，见图2-2b。

上述Bellman期望方程刻画了状态价值函数和动作价值函数之间的关系。在上式中，也可以用代入法消除其中一种价值函数，得到以下两种结果。

用状态价值函数表示状态价值函数，备份图见图2-3a：

用动作价值函数表示动作价值函数，备份图见图2-3b：

例如，对于表2-1和表2-2的例子中，状态价值函数和动作价值函数有以下关系：

用这个方程可以求得价值函数。
接下来演示如何通过sympy求解Bellman方程，寻找最优策略。不失一般性，假设。
由于这个方程组是含有字母的线性方程组，我们用sympy的solve_linear_system() 函数来求解它。solve_linear_system() 函数可以接受整理成标准形式的线性方程组，它有以下参数：

矩阵参数system。对于有n个等式、m个待求变量的线性方程组，system是一个n*(m+1)的sympy.Matrix对象。
可变列表参数symbols。若有m个待求变量的线性方程组，则symbols是m个sympy.Symbol对象。
可变关键字参数flags。

该函数返回一个dict，为每个待求变量给出结果。
我们把待求的Bellman期望方程整理成标准形式的线性方程组，得到：

用代码清单2-1可以求解上述方程。

代码清单2-1求得的状态价值函数和动作价值函数为：

其中

2.3　最优策略及其性质

前一节我们为策略定义了价值函数。价值函数实际上给出了策略的一个偏序关系：对于两个策略和，如果对于任意，都，则称策略小于等于，记作。本节将基于这个偏序关系来定义最优策略，并考虑最优策略的性质和求解。

2.3.1　最优策略与最优价值函数

对于一个动力而言，总是存在着一个策略，使得所有的策略都小于等于这个策略。这时，策略就称为最优策略（optimal policy）。最优策略的价值函数称为最优价值函数。最优价值函数包括以下两种形式。
最优状态价值函数（optimal state value function），即

最优动作价值函数（optimal action value function），即

对于一个动力，可能存在多个最优策略。事实上，这些最优策略总是有相同的价值函数。所以，对于同时存在多个最优策略的情况，任取一个最优策略来考察不失一般性。其中一种选取方法是选择这样的确定性策略：

其中，如果有多个动作使得取得最大值，则任选一个动作即可。从这个角度看，只要求得了最优价值函数，就可以直接得到一个最优策略。所以，求解最优价值函数是一个值得关注的重要问题。

2.3.2　Bellman最优方程

最优价值函数具有一个重要的性质—Bellman最优方程（Bellman optimal equation）。Bellman最优方程可以用于求解最优价值函数。
回顾2.2节，策略的价值函数满足Bellman期望方程，最优价值函数也是如此。与此同时，将最优函数的性质：

代入Bellman期望方程，就可以得到Bellman最优方程。
Bellman最优方程有以下两个部分。

用最优动作价值函数表示最优状态价值函数，备份图见图2-4a：

用最优状态价值函数表示最优动作价值函数，备份图见图2-4b：

基于最优状态价值函数和最优动作价值函数互相表示的形式，可以进一步导出以下两种形式。

用最优状态价值函数表示最优状态价值函数，备份图见图2-5a：
用最优动作价值函数表示最优动作价值函数，备份图见图2-5b：

例如，对于表2-1的动力系统，我们可以列出其Bellman最优方程为：

用这个方程可以求得最优价值函数。
接下来我们用sympy求解这个方程。Bellman最优方程含有max() 运算，可以通过分类讨论来化解这个max() 运算，将优化问题转为普通线性规划问题。如果用这种方法，可以将这个方程组分为以下4类情况讨论，用代码清单2-2求解。

代码清单2-2求得以下4种情况的解如下。
情况I：且。这时且这种情况的求解结果为：

其中。此时，且可以化简为：

情况II：且。这时且。这种情况的求解结果为：

其中。此时，且可以化简为：

情况III：且。这时且。这种情况的求解结果为：

此时，且可以化简为：

情况IV:且。这时且。这种情况的求解结果为：

其中。此时，且可以化简为：

对于给定数值的情况，更常将松弛为，并消去以减少决策变量，得到新的线性规划：

其中是一组任意取值的正实数。Bellman最优方程的解显然在线性规划的可行域内。而由于，因此线性规划的最优解肯定会让约束条件中的某些不等式取到等号，使得Bellman最优方程成立。可以证明，这个线性规划的最优解满足Bellman最优方程。
例如，在之前的例子中，如果限定，我们用这个线性规划求得最优状态价值为

进而由最优状态价值推算出最优动作价值为

2.3.3　用Bellman最优方程求解最优策略

在理论上，通过求解Bellman最优方程，就可以找到最优价值函数。一旦找到最优价值函数，就能很轻易地找到一个最优策略：对于每个状态，总是选择让最大的动作。
例如，对于表2-1的动力系统，我们已经通过分类讨论求得了Bellman最优方程。那么它的最优策略也可以通过分类讨论立即得到：
情况I：且，即且。这种情况的最优策略是

即一直不吃。
情况II：，即且。这种情况的最优策略是

即饿了不吃，饱时吃。
情况III：，即且。这种情况的最优策略是

即饿了吃，饱时不吃。
情况IV：，即且。这种情况的最优策略是

即一直吃。
对于一个特定的数值，求解则更加明显。例如，当，2.3.2节已经求得了最优动作价值，此时最优动作价值满足且。所以，它对应的最优策略为

但是，实际使用Bellman最优方程求解最优策略可能会遇到下列困难。

难以列出Bellman最优方程。列出Bellman最优方程要求对动力系统完全了解，并且动力系统必须可以用有Markov性的Markov决策过程来建模。在实际问题中，环境往往十分复杂，很难非常周全地用概率模型完全建模。
难以求解Bellman最优方程。在实际问题中，状态空间往往非常巨大，状态空间和动作空间的组合更是巨大。这种情况下，没有足够的计算资源来求解Bellman最优方程。所以这时候会考虑采用间接的方法求解最优价值函数的值，甚至是近似值。

2.4　案例：悬崖寻路

本节考虑Gym库中的悬崖寻路问题（CliffWalking-v0）。悬崖寻路问题是这样一种回合制问题：在一个的网格中，智能体最开始在左下角的网格，希望移动到右下角的网格，见图2-6。智能体每次可以在上、下、左、右这4个方向中移动一步，每移动一步会惩罚一个单位的奖励。但是，移动有以下限制。

智能体不能移出网格。如果智能体想执行某个动作移出网格，那么就让本步智能体不移动。但是这个操作依然会惩罚一个单位的奖励。
如果智能体将要到达最下一排网格（即开始网格和目标网格之间的10个网格），智能体会立即回到开始网格，并惩罚100个单位的奖励。这10个网格可被视为“悬崖”。

当智能体移动到终点时，回合结束，回合总奖励为各步奖励之。

2.4.1　实验环境使用

Gym库中的环境'CliffWalking-v0'实现了悬崖寻路的环境。代码清单2-3演示了如何导入这个环境并查看这个环境的基本信息。

这个环境是一个离散的Markov决策过程。在这个Markov决策过程中，每个状态是取自的int型数值（加上终止状态则为），表示当前智能体在图2-6中对应的位置上。动作是取自的int型数值：0表示向上，1表示向右，2表示向下，3表示向左。奖励取自，遇到悬崖为-100，否则为-1。
代码清单2-4给出了用给出的策略运行一个回合的代码。函数play_once() 有两个参数，一个是环境对象，另外一个是策略policy，它是np.array类型的实例。

代码清单2-5给出了一个最优策略optimal_policy。最优策略是在开始处向上，接着一路向右，然后到最右边时向下。

下面的代码用最优策略运行一个回合。采用最优策略，从开始网格到目标网格一共要移动13步，回合总奖励为-13。

2.4.2　求解Bellman期望方程

接下来考虑策略评估。我们用Bellman期望方程求解给定策略的状态价值和动作价值。首先来看状态价值。用状态价值表示状态价值的Bellmn期望方程为：

这是一个线性方程组，其标准形式为：

得到标准形式后就可以调用相关函数直接求解。得到状态价值函数后，可以用状态价值表示动作价值的Bellan期望方程：

来求动作价值函数。
代码清单2-6中的函数evaluate_bellman()实现了上述功能。状态价值求解部分用np.linalg.solve()函数求解标准形式的线性方程组。得到状态价值后，直接计算得到动作价值。

接下来我们用代码清单2-6中的evaluate_bellman()函数评估给出的策略。代码清单2-7和代码清单2-8分别评估了一个随机策略和最优确定性策略，并输出了状态价值函数和动作价值函数。

2.4.3　求解Bellman最优方程

对于悬崖寻路这样的数值环境，可以使用线性规划求解。线性规划问题的标准形式为：

其中目标函数中状态价值的系数已经被固定为1。也可以选择其他正实数作为系数。
代码清单2-9使用scipy.optimize.linprog() 函数来计算这个动态规划问题。这个函数的第0个参数是目标函数中各决策变量在目标函数中的系数，本例中都取1；第1个和第2个参数是形如“Ax<=b”这样的不等式约束的A和b的值。函数optimal_bellman() 刚开始就计算得到这些值。scipy.optimize.linprog() 还有关键字参数bounds，指定决策变量是否为有界的。本例中，决策变量都是无界的。无界也要显式指定，不可以忽略。还有关键字参数method确定优化方法。默认的优化方法不能处理不等式约束，这里选择了能够处理不等式约束的内点法（interior-point method）。

求得最优动作价值后，可以用argmax计算出最优确定策略，代码清单2-10给出了从最优动作价值函数计算最优确定策略的代码。运行结果表明，计算得到的最优策略就是代码清单2-5给出的策略。

2.5　本章小结

本章介绍了强化学习最重要的数学模型：Markov决策模型。Markov决策模型用动力系统来描述环境，用策略来描述智能体。本章还介绍了策略的价值函数和最优策略的最优价值函数。理论上，价值函数和最优价值函数可以通过Bellman期望方程和Bellman最优方程求解。但是在实际问题中，Bellman期望方程和Bellman最优方程往往难以获得或难以求解。在后续的章节中，将给出解决这些问题的方法。

本章要点

在完全可观测的离散时间智能体/环境接口中引入概率和Markov性，可以得到Markov决策过程。
在Markov决策过程中，是状态空间（包括终止状态的状态空间为），A是动作空间，R是奖励空间，p是动力。表示从状态s和动作a到状态和奖励r的转移概率。是策略。表示在状态s决定执行动作a的概率。
回报是未来奖励的和，奖励按折扣因子进行折扣。
对于一个策略，在某个状态s下的期望回报称为状态价值，在某个状态动作对下的期望回报称为动作价值。
状态价值和动作价值满足Bellman期望方程：