概念

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

定义

马尔可夫决策过程是一个五元组（S,A,P(),R(),γ） 其中:
1)S是一组有限的状态，即状态集 (states)
2)A是一组有限的行为（或者，As 是从状态可用的有限的一组行动s），即动作集 (Action)
3)Pa(s,s')=Pr(st+1=s'midst=s,at=a)表示状态 s 下采取动作 a 之后转移到 s' 状态的概率
4)Ra(s,s')是状态 s 下采取动作 a 获得的奖励（或期望的直接奖励）
5)γ[0,1]是折现系数，代表未来奖励与现在奖励之间的重要差异，也叫做衰减因子

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

目标是选择一项策略π这将最大化随机奖励的一些累积函数，通常是在可能无限的时间范围内的期望折扣总和:

其中at=π(st),γ是衰减因子，0<=γ<=1

分类

1.连续时间马尔可夫决策过程
对于连续时间的马尔可夫决策过程，可以在决策者选择的任何时候作出决定。与离散时间马尔可夫决策过程相比，连续时间马尔可夫决策过程可以更好地模拟连续动态系统的决策过程，即系统动力学由偏微分方程定义。
2.离散时间马尔科夫决策过程
在离散时间马尔科夫决策过程中，决策是在离散的时间间隔进行的。

策略

策略是提供给决策者在各个时刻选取行动的规则，记作π，其中πn是时刻n选取行动的规则。从理论上来说，为了在大范围寻求最优策略πn，最好根据时刻n以前的历史，甚至是随机地选择最优策略。但为了便于应用，常采用既不依赖于历史、又不依赖于时间的策略，甚至可以采用确定性平稳策略。
衡量策略优劣的常用指标有折扣指标和平均指标。折扣指标是指长期折扣〔把t时刻的单位收益折合成0时刻的单位收益的βt(β<1)倍〕期望总报酬；平均指标是指单位时间的平均期望报酬。
采用折扣指标的马尔可夫决策过程称为折扣模型。业已证明：若一个策略是β折扣最优的，则初始时刻的决策规则所构成的平稳策略对同一β也是折扣最优的，而且它还可以分解为若干个确定性平稳策略，它们对同一β都是最优的，已有计算这种策略的算法。
采用平均指标的马尔可夫决策过程称为平均模型。已证明：当状态空间S和行动集A(i)均为有限集时，对于平均指标存在最优的确定性平稳策略；当S和A(i)不是有限的情况,必须增加条件，才有最优的确定性平稳策略。计算这种策略的算法也已研制出来。

扩展

1.约束马尔可夫决策过程
约束马尔可夫决策过程（CMDPs）是马尔可夫决策过程（MDPs）的扩展。MDP和CMDP有三个基本的区别。
1）应用时一个动作而不是一个动作需要多个成本；
2）CMDP只能通过线性程序来解决，动态编程不起作用；
3）最终的政策取决于开始的状态。
CMDP有很多应用。它最近被用在机器人的运动规划场景中。
2.模糊马尔可夫决策过程（FMDPs）
在MDP中，最优策略是使未来奖励的概率加权总和最大化的策略。因此，最优策略由几个属于一组有限行为的动作组成。在模糊马尔可夫决策过程（FMDP）中，首先，价值函数被计算为规则的MDP（即具有有限的一组行动）；那么，这个策略是通过一个模糊推理系统来提取的。换句话说，价值函数被用作模糊推理系统的输入，策略是模糊推理系统的输出

个人理解

和一般的马尔科夫过程不同，马尔科夫决策过程考虑了动作，即系统下个状态不仅和当前的状态有关，也和当前采取的动作有关。还是举下棋的例子，当我们在某个局面（状态s）走了一步 (动作 a )。这时对手的选择（导致下个状态 s’ ）我们是不能确定的，但是他的选择只和 s 和 a 有关，而不用考虑更早之前的状态和动作，即 s’ 是根据 s 和 a 随机生成的。

马尔可夫决策过程整体的思想就是通过回报函数回报值来评价动作执行的效果，当然这一过程是比较复杂的。迭代方法通常分为值迭代方法和策略迭代方法。对于规模较小的MDP，策略迭代一般能够更快的收敛；但对于规模较大的MDP（状态多），值迭代更容易些（没有线性方程组的计算）。