4 马尔可夫决策过程-上 | 自动驾驶小白说

4.1 简介

马尔可夫决策过程（Markov Decision Process，简称MDP）是强化学习中的重要概念，也是序贯决策的主要研究领域，其主要包括状态信息以及状态之间的转移机制。马尔可夫决策过程是一种数学模型，用于描述决策者在不确定环境中进行决策的过程。它基于马尔可夫性质，即当前状态的转移概率仅依赖于当前状态和行动，与历史状态和行动无关。

4.2 马尔可夫过程

4.2.1 随机过程

随机过程是一系列随机变量在时间上的演变过程，是一个数学概念，用于描述随时间变化而变化的随机现象。其可以看作是一组依赖于时间的随机变量，这些随机变量可以是离散的（如某一时刻的股票价格），也可以是连续的（如某地区一天内的温度变化）。

在随机过程中，随机现象在某时刻的取值是一个随机变量，所有可能的状态组成状态集合。随机现象是状态的变化过程，在时刻的状态通常取决于时刻之前的状态。我们将已知历史信息时下一个时刻状态为的概率表示成

4.2.2 马尔可夫性质

当且仅当某时刻的状态只取决于上一时刻的状态时，一个随机过程被成为马尔可夫性质（Markov property），也就是说当前状态是未来的充分统计量，即下一个状态只取决于当前状态，而不会受到过去状态的影响。

🌟Note：具有马尔可夫性并不代表这个随机过程就和历史完全没有关系。因为虽然时刻的状态只与时刻的状态有关，但是时刻的状态其实包含了时刻的状态信息，通过这种链式关系，历史的信息被传递到现在。马尔可夫性可以大大简化运算，因为只要当前状态可知，所有的历史信息都不再需要了，利用当前的状态信息就可以决定未来。

4.2.3 马尔可夫过程

马尔可夫过程（Markov process）指具有马尔可夫性质的随机过程，也被称为马尔可夫链（Markov chain）。通常用元组描述一个马尔可夫过程，其中是有限数量的状态集合，是状态转移矩阵（state transition matrix）。假设一共有个状态，此时，状态转移矩阵定义了所有状态对之间的转移概率，即：

其中表示从状态转移到状态的概率，且我们称为状态转移函数。

🌟Note: 从某个状态出发，到达其他状态的概率和一定为1.0，即状态转移矩阵的每一行和为1.0。

4.2.4 实例

下图是一个具有 6 个状态的马尔可夫过程的简单例子。其中每个绿色圆圈表示一个状态，每个状态都有一定概率（包括概率为 0）转移到其他状态，其中通常被称为终止状态（terminal state），因为它不会再转移到其他状态，可以理解为它永远以概率 1 转移到自己。状态之间的虚线箭头表示状态的转移，箭头旁的数字表示该状态转移发生的概率。从每个状态出发转移到其他状态的概率总和为 1。例如，有 90%概率保持不变，有 10%概率转移到，而又有 50%概率回到，有 50%概率转移到。

由此，我们可以写出状态转移矩阵：

给定一个马尔可夫过程，我们可以从某个状态出发根据它的状态转移矩阵生成一个状态序列（episode），这个步骤也被叫做采样（sampling）。

4.3 马尔可夫奖励过程

在马尔可夫过程的基础上加入奖励函数和折扣因子，就可以得到马尔可夫奖励过程（Markov reward process）。一个马尔可夫奖励过程由构成：

：有限状态的集合

：状态转移矩阵

：奖励函数，某个状态的奖励指转移到该状态时可以获得奖励的期望

：折扣因子（discount factor），其取值范围是。引入折扣因子的理由为远期利益具有一定不确定性，有时我们更希望能够尽快获得一些奖励，所以我们需要对远期利益打一些折扣。接近 1 的更关注长期的累计奖励，接近 0 的更考虑短期奖励。

4.3.1 回报

在一个马尔可夫奖励过程中，从第时刻状态开始，直到终止状态时，所有奖励的衰减之和成为回报（Return），计算方式如下：

其中，表示在时刻获得的奖励。

如下图所示，是在马尔可夫过程的基础上添加了奖励函数，构成了一个马尔可夫奖励过程，例如进入状态可以得到奖励，表示我们不希望进入，进入可以获得最高的奖励，但是进入后奖励为0.0，此时序列终止。

比如选取为起始状态，设置折扣因子，并且采样到一条状态序列为，就可以计算的回报：

4.3.2 价值函数

在马尔可夫奖励过程中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值（value）。所有状态的价值组成了价值函数（value function），价值函数的输入为某个状态，输出为这个状态的价值。我们将价值函数表示为：

展开形式为：

在上式中，一方面，即时奖励的期望正是奖励函数的输出，即；另一方面，等式中剩余部分可以根据从状态出发的转移概率得到，即：

上式就是马尔可夫奖励过程中的贝尔曼方程（Bellman equation），对每个状态都成立。

若一个马尔可夫奖励过程一共有个状态，即，我们将所有状态的价值表示成一个列向量，同理将奖励函数写成一个列向量，因此我们可以将贝尔曼方程写成矩阵的形式：

根据矩阵运算，得到以下的解析解：

以上解析解的计算复杂度为，其中是状态个数，因此这种方法只适用状态空间很小的马尔可夫奖励过程。

🌟Note:求解大规划的马尔可夫奖励过程中的价值函数时，可以使用动态规划（dynamic programming）算法、蒙特卡洛方法（Monte-Carlo method）和时序差分（temporal difference）

4.4 马尔可夫决策过程

马尔可夫过程和马尔可夫奖励过程都是自发改变的随机过程，如果有一个外界的”刺激“来共同改变这个随机过程，就有了马尔可夫决策过程（Markov decision process，MDP）。我们将这个来自外界的刺激称为智能体（agent）的动作，在马尔可夫奖励过程（MRP）的基础上加入动作，就得到了马尔可夫决策过程（MDP）。马尔可夫决策过程由五元组构成，其中：

：状态的集合

：动作的集合

：折扣因子

：奖励函数，此时奖励同时取决于状态和动作

：状态转移函数，表示在状态执行动作之后到达状态的概率

在马尔可夫决策过程中，通常存在一个智能体来执行动作。例如，一艘小船在大海中随着水流自由飘荡的过程就是一个马尔可夫奖励过程，它如果凭借运气漂到了一个目的地，就能获得比较大的奖励；如果有个水手在控制着这条船往哪个方向前进，就可以主动选择前往目的地获得比较大的奖励。马尔可夫决策过程是一个与时间相关的不断进行的过程，在智能体和环境 MDP 之间存在一个不断交互的过程。一般而言，它们之间的交互是如下图循环过程：智能体根据当前状态选择动作；对于状态和动作，MDP 根据状态转移函数和奖励函数得到状态和并反馈给智能体。智能体的目标是最大化得到的累计奖励。智能体根据当前状态从动作的集合中选择一个动作的方式，被称为策略。

4.4.1 策略

智能体的策略（policy）通常用字母表示。策略是一个函数，表示在输入状态为的情况下采取动作的概率。

确定性策略（deterministic policy）：在每个状态时只输出一个确定性的动作，即每个状态只有一个动作，且该动作的概率是1。

随机性策略（stochastic policy）：在每个状态时输出的是关于动作的概率分布，然后根据该分布就行采样就可以得到一个动作。

在MDP中，由于马尔可夫性质的存在，策略只需要与当前状态有关，不需要考虑历史状态。且在MDP中，价值函数是和策略相关的。

4.4.2 状态价值函数

我们使用表示在MDP中基于策略的状态价值函数（state-value function），定义为从状态出发遵循策略能获得的期望回报：

4.4.3 动作价值函数

我们用表示在MDP遵循策略时，对当前状态执行动作得到的期望回报：

状态价值函数和动作价值函数之间的关系：在使用策略中，状态的价值等于在该状态下基于策略采取所有动作的概率与相应的价值相乘再求和的结果：

使用策略时，状态下采取动作的价值等于即时奖励加上经过衰减后的所有可能的下一个状态的状态转移概率与相应的价值的乘积：

4.4.4 贝尔曼期望方程

在贝尔曼方程中加上“期望”二字是为了与接下来的贝尔曼最优方程进行区分。我们通过简单推导就可以分别得到两个价值函数的贝尔曼期望方程（Bellman Expectation Equation）：

下图是一个马尔可夫决策过程的简单例子。其中每个深色圆圈代表一个状态，一共有这5个状态。黑色实线箭头代表可以采取的动作，浅色小圆圈代表动作。每个浅色小圆圈旁边的数字代表在某个状态下采取某个动作能获得的奖励。虚线箭头代表采取动作后可能转移到的状态，箭头边上上的数字代表转移概率，如果没有数字则代表转移概率为1。例如在状态下，如果采取动作”前往“，就能得到奖励，并且转移到；在下，如果采取动作”概率前往“，就能得到奖励1，并且会分别以概率0.2，0.4，0.4转移到。

4.5 最优策略

在强化学习中，我们的目标是找到一个策略，使得智能体从初始状态出发能够获得最大的期望回报。我们首先定义策略之间的比较关系：如果对于所有状态，策略的状态价值函数都大于等于策略的状态价值函数，则我们说策略优于策略。

在有限状态和动作集合的马尔可夫决策过程（MDP）中，至少存在一个策略比其他所有策略都好，或者至少存在一个策略不比任何其他策略差，这样的策略被称为最优策略。最优策略可能不唯一，我们将它们统一表示为。

所有最优策略都有相同的状态价值函数，我们称之为最优状态价值函数，表示为：

同样的，我们也可以定义最优动作价值函数，表示为：

为了使最大化，我们需要在当前状态动作对之后都执行最优策略，因此，我们可以得到最优状态价值函数和最优动作价值函数之间的关系：

这与在普通策略下的状态价值函数和动作价值函数之间的关系是相同的。另一方面，最优状态价值是选择使得最优动作价值最大的那个动作时的状态价值：

4.6 贝尔曼最优方程

根据和之间的关系，我们可以得到贝尔曼最优方程（Bellman optimality equation）：

4.7 参考文献

[1] SUTTON R S, BARTO A G. Reinforcement learning: an introduction [M]. Cambridge:MIT press, 2018.

[2] OTTERLO M V, WIERING M. Reinforcement learning and markov decision processes [M]. Berlin, Heidelberg: Springer, 2012: 3-42.