简介

在概率论和统计学中，马可夫决策过程（英语：Markov Decision Processes，缩写为 MDPs）提供了一个数学架构模型，用于面对部分随机，部分可由决策者控制的状态下，如何进行决策，以俄罗斯数学家安德雷·马尔可夫的名字命名。在经由动态规划与强化学习以解决最佳化问题的研究领域中，马可夫决策过程是一个有用的工具。

马尔可夫过程在概率论和统计学方面皆有影响。一个通过不相关的自变量定义的随机过程，并（从数学上）体现出马尔可夫性质，以具有此性质为依据可推断出任何马尔可夫过程。实际应用中更为重要的是，使用具有马尔可夫性质这个假设来建立模型。在建模领域，具有马尔可夫性质的假设是向随机过程模型中引入统计相关性的同时，当分支增多时，允许相关性下降的少有几种简单的方式。

马尔可夫决策过程是指决策者周期地或连续地观察具有马尔可夫性的随机动态系统，序贯地作出决策。即根据每个时刻观察到的状态，从可用的行动集合中选用一个行动作出决策，系统下一步（未来）的状态是随机的，并且其状态转移概率具有马尔可夫性。决策者根据新观察到的状态，再作新的决策，依此反复地进行。马尔可夫性是指一个随机过程未来发展的概率规律与观察之前的历史无关的性质。马尔可夫性又可简单叙述为状态转移概率的无后效性。状态转移概率具有马尔可夫性的随机过程即为马尔可夫过程。马尔可夫决策过程又可看作随机对策的特殊情形，在这种随机对策中对策的一方是无意志的。马尔可夫决策过程还可作为马尔可夫型随机最优控制，其决策变量就是控制变量。

发展概况

50年代R.贝尔曼研究动态规划时和L.S.沙普利研究随机对策时已出现马尔可夫决策过程的基本思想。R.A.霍华德(1960)和D.布莱克韦尔(1962)等人的研究工作奠定了马尔可夫决策过程的理论基础。1965年，布莱克韦尔关于一般状态空间的研究和E.B.丁金关于非时齐（非时间平稳性）的研究，推动了这一理论的发展。1960年以来，马尔可夫决策过程理论得到迅速发展，应用领域不断扩大。凡是以马尔可夫过程作为数学模型的问题，只要能引入决策和效用结构，均可应用这种理论。

定义

马尔可夫决策过程是一个五元组，其中

1)是一组有限的状态;

2)是一组有限的行为（或者，是从状态可用的有限的一组行动）;

3)是行动的概率在状态在时间会导致状态在时间;

4)是从状态转移后得到的直接奖励（或期望的直接奖励）；

5)是折现系数，代表未来奖励与现在奖励之间的重要差异。

（注：马尔可夫决策过程的理论并没有说明这一点，或是有限的，但是下面的基本算法假设它们是有限的）。

图1.简单MDP的示例

图1表示具有三个状态（绿色圆圈）和两个动作（橙色圆圈）的简单MDP的示例。

描述

MDP的核心问题是为决策者找到一个策略：一个功能指：决策者什么时候会选择行动。一旦马尔可夫决策过程以这种方式与策略相结合，就可以解决每个状态的行为，并且产生的组合行为就像一个马尔可夫链。

目标是选择一项策略这将最大化随机奖励的一些累积函数，通常是在可能无限的时间范围内的期望折扣总和：，其中）。是折扣因素和满足。（例如，当折扣率为r时）通常接近1。