马尔可夫决策过程

序贯决策的数学模型

马尔可夫决策过程（Markov Decision Process, MDP）是序贯决策（sequential decision）的数学模型，用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报。MDP的得名来自于俄国数学家安德雷·马尔可夫（Андрей Андреевич Марков），以纪念其为马尔可夫链所做的研究。

历史

MDP的历史可以追溯至20世纪50年代动力系统研究中的最优控制（optimal control）问题，1957年，美国学者Richard Bellman通过离散随机最优控制模型首次提出了离散时间马尔可夫决策过程。1960年和1962年，美国学者Ronald A. Howard和David Blackwell提出并完善了求解MDP模型的动态规划方法。

进入1980s后，学界对MDP的认识逐渐由“系统优化”转为“学习”。1987年，美国学者Paul Werbos在研究中试图将MDP和动态规划与大脑的认识机制相联系。1989年，英国学者Chris Watkins首次在强化学习中尝试使用MDP建模。Watkins (1989)在发表后得到了机器学习领域的关注，MDP也由此作为强化学习问题的常见模型而得到应用。

定义

MDP是在环境中模拟智能体的随机性策略（policy）与回报的数学模型，且环境的状态具有马尔可夫性质。

交互对象与模型要素

由定义可知，MDP包含一组交互对象，即智能体和环境：

按定义，MDP包含5个模型要素，状态（state）、动作（action）、策略（policy）、奖励（reward）和回报（return），其符号与说明在表中给出：

在表中建模要素的基础上，MDP按如下方式进行组织：智能体对初始环境进行感知，按策略实施动作，环境受动作影响进入新的状态，并反馈给智能体一个奖励。随后智能体基于采取新的策略，与环境持续交互。MDP中的奖励是需要设计的，设计方式通常取决于对应的强化学习问题。

连续与离散MDP

MDP的指数集（index set）是时间步：，并按时间步进行演化（evolution）。时间步离散的MDP被称为离散时间马尔科夫决策过程（descrete-time MDP），反之则被称为连续时间马尔科夫决策过程（continuous-time MDP），二者的关系可类比连续时间马尔可夫链与离散时间马尔可夫链。

图模型

MDP可以用图模型表示，在逻辑上类似于马尔可夫链的转移图。MDP的图模型包含状态节点和动作节点，状态到动作的边由策略定义，动作到状态的边由环境动力项（参见求解部分）定义。除初始状态外，每个状态都返回一个奖励。

解释性的例子：多臂赌博机

多臂赌博机问题（multi-armed bandit problem）的设定如下：给定K个不同的赌博机，拉动每个赌博机的拉杆，赌博机会按照一个事先设定的概率掉钱或不掉钱。每个赌博机掉钱的概率不一样。MDP可以模拟智能体选择赌博机的策略和回报。在该例子中，MDP的要素有如下对应：

“环境”是K个相互独立的赌博机；“状态”是“掉钱”和“不掉钱”，其马尔可夫性质在于每次使用赌博机，返回结果都与先前的使用记录无关；“动作”是使用赌博机；“策略”是依据前一次操作的赌博机和其返回状态，选择下一次使用的赌博机；“奖励”是一次使用赌博机后掉钱的金额；回报是多次使用赌博机获得的总收益。

与多臂赌博机类似的例子包括广告推荐系统和风险投资组合，在MDP建模后，此类问题被视为离散时间步下的纪元式强化学习。

理论与性质

转移理论

马尔可夫性质与转移概率

按定义，MDP具有马尔可夫性质，按条件概率关系可表示如下：即当前时刻的状态仅与前一时刻的状态和动作有关，与其他时刻的状态和动作条件独立。等式右侧的条件概率被称为MDP的状态间的转移概率。马尔可夫性质是所有马尔可夫模型共有的性质，但相比于马尔可夫链，MDP的转移概率加入了智能体的动作，其马尔可夫性质也与动作有关。

MDP的马尔可夫性质是其被应用于强化学习问题的原因之一，强化学习问题在本质上要求环境的下个状态与所有的历史信息，包括状态、动作和奖励有关，但在建模时采用马尔可夫假设可以在对问题进行简化的同时保留主要关系，此时环境的单步动力学就可以对其未来的状态进行预测。因此即便一些环境的状态信号不具有马尔可夫性，其强化学习问题也可以使用MDP建模。

轨迹

在此基础上，类比马尔可夫链中的样本轨道（sample path），可定义MDP的轨迹（trajectory）：

即环境由初始状态按给定策略演进至当前状态的所有动作、状态和奖励的集合。由于MDP的策略和状态转移具有随机性，因此其模拟得到的轨迹是随机的，且该轨迹出现的概率有如下表示：

一般地，MDP中两个状态间的轨迹可以有多条，此时由Chapman-Kolmogorov等式可知，两个状态间的n步转移概率是所有轨迹出现概率的和。

折现

MDP的时间步可以是有限或无限的。时间步有限的MDP存在一个终止状态（terminal state），该状态被智能体触发后，MDP的模拟完成了一个纪元（episode）并得到回报。与之对应的，环境中没有终止状态的MDP可拥有无限的时间步，其回报也会趋于无穷。

在对实际问题建模时，除非无限时间步的MDP有收敛行为，否则考虑无限远处的回报是不适合的，也不利于MDP的求解。为此，可引入折现机制并得到折现回报（discounted return）：

式中为一常数，被称为折现系数。由几何级数的极限可知，无限时间步MDP的折现回报是有限的：

因此折现回报在考虑了无穷远处奖励的同时，使MDP的求解变得可行。此外为便于计算，折现回报可以表示为递归形式：

式中的下标表示轨迹开始的时间步，对应轨迹的回报。

值函数

参见：强化学习

MDP的每组轨迹都对应一个（折现）回报。由于MDP的策略和状态转移都是条件概率，因此在考虑模型的随机性后，轨迹的折现回报可以由其数学期望表示，该数学期望被称为目标函数：

MDP的轨迹依赖于给定的策略，因此目标函数也是控制策略的参数的函数：。例如，若策略由其它机器学习模型，例如神经网络给出，则参数是权重系数。此外对状态收敛的无限时间步MDP，其目标函数也可以是其进入平稳分布时单个时间步的奖励的数学期望。

状态值函数（state value function）

在MDP模拟的一个纪元中，目标函数与初始状态有关，因此按定义，目标函数有可有如下展开：

目标函数中包含初始状态的条件数学期望被定义为状态值函数：，即智能体由初始状态开始，按策略决定后续动作所得回报的数学期望：

式中的数学期望同时考虑了策略的随机性和环境的随机性，为求解值函数，上式可通过折现回报的递归形式改写为贝尔曼方程（Bellman equation）：

上式后两行中的第一个求和表示对策略的随机性求数学期望、第二个求和表示对环境，包括状态和奖励的随机性求期望（参见动作值函数）。说明性地，这两个求和将时间步内所有可能的动作、状态和奖励加权求和。由贝尔曼方程的性质可知，给定MDP的策略、转移概率和奖励，状态值函数可以按迭代的方式进行计算。

动作值函数（action value function）

状态值函数中的条件概率：表示环境对动作的响应，该项也被称为环境动力项（environment dynamics）。环境动力项不受智能体控制，其数学期望可以定义为动作值函数或Q函数：，表示智能体由给定的状态和动作开始，并按策略决定后续动作所得到的回报数学期望：

上式为动作值函数的贝尔曼方程，式中关于的动作值函数包含了的状态值函数，联合上式与动作值函数的贝尔曼方程可以得到二者的相互关系：

式中第二行是另一种形式的动作值函数贝尔曼方程。上式表明，给定策略值函数和动作值函数的贝尔曼方程，可以得到动作值函数的贝尔曼方程。

状态值函数和动作值函数是一些MDP算法需要使用的，目标函数的变体，其实际意义是对策略的评估。例如在状态，若有一个新的动作使得，则实施新动作比当前策略给出的动作要好，因此可通过算法增加新动作所对应的策略的概率。

算法

参见：强化学习

在MDP模型建立后，强化学习算法能够求解一组贯序策略：，使得目标函数，即智能体的折现回报，取全局最大值：

按求解途径，MDP适用的强化学习算法分为两类：值函数算法和策略搜索算法。值函数算法通过迭代策略的值函数求得全局最优；策略搜索算法则通过搜索策略空间得到全局最优。

值函数算法

动态规划（dynamic programming）

参见：动态规划

作为贝尔曼最优化原理（Bellman's principle of Optimality）的推论，有限时间步的MDP至少存在一个全局最优解，且该最优解是确定的（deterministic），可使用动态规划求得。

使用动态规划求解的MDP属于“基于模型的强化学习（model-based reinforcement learning），因为要求状态值函数和动作值函数的贝尔曼方程已知，而后者等价于MDP的环境不是”黑箱“，其环境动力项是已知的。MDP的动态规划分为策略迭代（policy iteration）和值迭代（value iteration）两种，其核心思想是最优化原理：最优策略的子策略在一次迭代中也是以该状态出发的最优策略，因此在迭代中不断选择该次迭代的最优子策略能够收敛至MDP的全局最优。

以策略迭代为例，在对MDP的建模要素初始化后，其每次迭代都使用贝尔曼方程计算状态值函数以评估策略，并按动作值函数对状态值函数的贝尔曼方程确定当前状态下的最优动作和策略：，迭代在策略的前后变化小于迭代精度时收敛。

随机模拟

以蒙特卡罗方法和时序差分学习（temporal-difference learning）为代表的MDP算法属于“无模型的强化学习（model-free reinforcement learning）”，适用于MDP的环境动力项未知的情形。在MDP的转移概率未知时，状态值函数无法参与优化，因此随机模拟方法通过生成随机数直接估计动作值函数的真实值并求解MDP。

对给定的初始状态和动作，蒙特卡罗方法按N次随机游走试验所得回报的平均估计动作值函数：

在动作值函数的随机游走收敛后，蒙特卡罗方法按策略迭代寻找最优动作并迭代完成MDP的求解。蒙特卡罗算法在总体上是一个泛用性好但求解效率低下的算法，按确定策略采样的蒙特卡罗收敛缓慢，在本质上是智能体对环境单纯的“试错”。一些引入了探索机制的改进版本，例如ϵ-贪心算法（ϵ-greedy method）也需要采样整个轨迹后才能评估和改进策略，在求解复杂MDP时会带来相当的计算开销。

时序差分学习可视为蒙特卡罗方法和动态规划的结合。在使用采样方法估计动作值函数时，时序差分学习将采样改写为贝尔曼方程的形式，以更高的效率更新动作值函数的取值。求解MDP可用的时序差分学习算法包括SARSA 算法（State Action RewardState Action, SARSA）和Q学习（Q-Learning）算法，二者都利用了MDP的马尔可夫性质，但前者的改进策略和采样策略是同一个策略，因此被称为“同策略（on policy）”算法，而后者采样与改进分别使用不同策略，因此被称为“异策略（off policy）”算法。

策略搜索算法

参见：策略搜索

策略搜索（policy search）可以在策略空间直接搜索MDP的最优策略完成求解。策略搜索算法的常见例子包括REINFORCE算法和演员-评论员算法（Actor-Critic Algorithm）。REINFORCE算法使用随机梯度上升求解（可微分的）策略函数的参数使得目标函数最大，一些REINFORCE算法的改进版本通过引入基准线加速迭代的收敛。演员-评论员算法是一种结合策略搜索和时序差分学习的方法。其中“演员（actor）”是指策略函数，即学习一个策略来得到尽量高的回报，“评论员（critic）”是状态值函数，对当前策略的值函数进行估计，即评估演员的好坏。借助于值函数，Actor-Critic 算法可以进行单步更新参数。

推广

约束马尔可夫决策过程

约束马尔可夫决策过程（Constrained MDP, CMDP）是对智能体施加了额外限制的MDP，在CMDP中，智能体不仅要实施策略和获得回报，还要确保环境状态的一些指标不超出限制。例如在基于MDP的投资组合问题中，智能体除了最大化投资回报，也要求限制投资风险；在交通管理中，智能体除了最大化车流量，也要求限制车辆的平均延迟和特定路段的车辆通行种类。

相比于MDP，CMDP中智能体的每个动作都对应多个（而非一个）奖励。此外，由于约束的引入，CMDP不满足贝尔曼最优化原理，其最优策略是对初始状态敏感的，因此CMDP无法使用动态规划求解。离散CMDP的常见解法是线性规划（linear programming）。

模糊马尔可夫决策过程

模糊马尔可夫决策过程（Fuzzy MDP, FMDP）是使用模糊动态规划（fuzzy dynamic programming）求解的MDP模型，是MDP的推广之一。FMDP的求解方法属于值函数算法，其中策略评估部分与传统的动态规划方法相同，但策略改进部分使用了模糊推理（fuzzy inference），即值函数被用作模糊推理的输入，策略的改进是模糊推理系统的输出。

部分可观察马尔可夫决策过程

主条目：部分可观察马尔可夫决策过程

在一些设定中，智能体无法完全观测环境的状态，此类MDP被称为部分可观察马尔可夫决策过程（Partially Observable MDP,POMDP）。POMDP是一个马尔可夫决策过程的泛化。POMDP与MDP的马尔可夫性质相同，但是POMDP框架下智能体只能知道部分状态的观测值。比如在自动驾驶中，智能体只能感知传感器采集的有限的环境信息。与MDP相比，POMDP包含两个额外的模型要素：智能体的观测概率和观测空间。

应用

作为强化学习的模型，MDP适用于很多与强化学习有关的实际问题，包括自动控制领域的人机交互系统、自动驾驶系统、导航系统；运筹学领域的广告/销售问题、投资组合问题等。MDP也可以作为模型构建一些具有博弈性质的强化学习系统，例如国际象棋和围棋AI。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省