马尔可夫决策过程（MDPS）， 安德烈·马尔科夫的名字命名，提供了一个数学建模框架的情况下，结果是部分随机部分的控制下的决策者的决策。 学习了广泛的优化问题解决了通过动态编程和加强学习的MDP是有用的。 至少早在20世纪50年代（参见贝尔曼1957年）的MDP被称为。 马尔可夫决策过程研究的核心机构造成， 罗纳德A.霍华德的书出版于1960年， 动态规划与马氏过程的 。 它们被用在广泛的学科领域，包括机器人 ， 自动化控制 ， 经济学和制造 。
更确切地说，马尔可夫决策过程是一个离散时间的 随机 控制过程。 在每一个时间步长，这个过程是在一些国家 
和决策者可以选择任何行动 
可用状态 。 通过随机移动到一个新的状态，在接下来的时间步长的过程响应 
，并给决策者一个相应的奖励 
。
进入新的状态的概率的过程 是由所选择的动作的影响。 具体来说，它是由状态转换函数 
。 因此，下一个状态 取决于当前状态 
和决策者的行动 。 但考虑到 和 所有以前的状态和行为，它是有条件的独立，换句话说，状态转换的MDP具有马尔可夫性 。
马尔可夫决策过程是马尔可夫链的延伸，所不同的是另外的操作（允许选择）和回报（提供动力）。 相反，如果只存在一个动作，每一个州和所有奖励均为零，马尔可夫决策过程降低到一个马尔可夫链 。
定义
一个简单的例子MDP三个州和两个动作。
马尔可夫决策过程是一个4
- 元组 ，其中
是一组有限的国家，
是一组有限的操作（或者， 从国家的行动是有限的一组 ）
是行动的可能性 在状态 在时间 会导致状态 在时间 ，
即时奖励（或预期的立即回报）后收到的过渡状态 从状态 转移概率 。
（马尔可夫决策过程的理论实际上并不需要 或 是有限的，[ 引文需要 ]，但基本算法中假定它们是有限的。）
[ 编辑 ]问题
核心问题的MDP是为决策者找到了“政策”：一个函数 指定的动作 时，决策者会选择在状态 。 请注意一次马尔可夫决策过程以这种方式结合的政策，修复的动作为每个状态和所得到的组合的行为像一个Markov链 。
我们的目标是选择策略 这将最大限度地累积函数的随机奖励，通常是预期的贴现和潜在的无限的地平线上：
- （在这里我们选择 ）
哪里 是贴现因子，且满足 。 （例如， 时的贴现率为r）。 通常是接近1。
由于马氏性，这个特定的问题的最优政策确实可以被写入作为一个功能的 仅上述假设。
[ 编辑 ]算法
可以求解线性规划或动态规划的MDP
。 在下文中，我们提出了后一种方式。
假设我们知道状态转换函数 和奖励功能 ，我们希望计算的折现期望的奖励政策，最大限度地提高。
标准家庭的算法来计算这个最优策略需要存储两个数组索引的状态： 值 ，其中包含真正的价值和政策 其中包含的行动。 在算法结束时， 将含有该溶液和 将包含贴现和状态后的解决方案，从赚取的回报（平均） 。
该算法具有以下两种步骤，这是为了让所有的国家在某些重复，直到不再发生变化时。 他们是
他们的顺序取决于不同的算法，也可以做他们的所有国家在一次或国家的状态，更多的时候比其他一些国家。 只要没有状态永久排除的步骤之一，该算法将最终到达正确的解决方案。
[ 编辑 ]著名的变种
[ 编辑 ]值迭代
在值迭代（贝尔曼1957年），这也被称为落后的感应 ， 阵列还没有使用，相反，其价值 是需要的，只要它是计算。 1953年Shapley值的文件随机游戏作为一种特殊的情况下，包括值迭代方法的MDP，但是这只是到后来才认识到上。 [1]
代以计算 成计算 给出了合并步骤：
这是迭代的所有状态更新规则， 直到它收敛与左手侧的右手侧（这是针对此问题的“ Bellman方程 “）相等。
[ 编辑 ]策略迭代
在策略迭代（霍华德1960年），第一个步骤是进行一次，然后第二步是反复进行，直到收敛。 然后，步骤1，则再次进行一次，等等。
相反的衔接重复步骤2，它可以制定和作为一组线性方程组的求解。
该变型的优点在于，有一个明确的停止条件：当数组 不改变施加的步骤1到所有状态的过程中，该算法是完成。
[ 编辑 ]修改后的策略迭代
在修改策略迭代（面包车Nunen，1976年Puterman和信1978年），第一个步骤是进行一次，然后第二步是反复多次。 然后，步骤1，则再次进行一次，等等。
[ 编辑 ]优先扫除
在此版本中的步骤是优先适用于在某种程度上是重要的国家 -
无论是基于该算法（有大的变化， 或 围绕这些最近的状态），或使用（这些国家是附近的起始状态，或以其他方式感兴趣的人或程序使用的算法）的基础上。
[ 编辑 ]扩展和推广
马尔可夫决策过程是一个随机的游戏 ，只有一名球员。
[ 编辑 ]部分可观测性
主要文章： 部分可观察马尔可夫决策过程
以上的解决方案假定状态 被称为时将要采取的行动; 无法计算。 当这个假设是不正确的，这个问题被称为部分可观察马尔可夫决策过程或POMDP。
在该领域的一个重大突破“提供了最佳的适应性政策马尔可夫决策过程” [2]的Burnetas和Katehakis中。 在这项工作中，构建了一类具有均匀最大的收敛速度预计总有限地平线奖励属性的适应性政策的假设下，有限的国家行动的空间和不可还原性的过渡法。 这些政策规定，应根据选择的行动，在每个状态和时间周期，通货膨胀的右手边的估计平均报酬最优方程的指数。
[ 编辑 ]强化学习
如果概率或奖励是未知的，问题是强化学习 （Sutton和巴托，1998年）。
为此目的，它是非常有用的进一步定义一个函数，它对应于采取行动 然后继续最佳（或根据任何政策目前有）：
虽然这个功能还未知，在学习过程中的经验的基础上 对（连同结果 ），也就是，“我是在状态 和我试图这样做 和 发生“），因此，一个具有一个数组 和使用经验直接更新它。 这被称为Q-学习 。
强化学习可以解决马尔可夫决策过程没有明确的规范的转移概率，转移概率的值是必要的价值和策略迭代。 在强化学习，而不是明确的规范的转移概率，转移概率可以通过一个模拟器，通常是均匀随机初始状态重新启动多次。 强化学习，也可以结合函数逼近的状态有一个非常大的数量来解决问题。
[ 编辑 ]连续时间马尔可夫决策过程
在离散时间马尔可夫决策过程，决策是在离散时间的时代。 然而，对于连续时间马尔可夫决策过程 ，决策可以在任何时候，决策者希望。 连续时间与离散时间马尔可夫决策过程，马尔可夫决策过程能够更好地模拟决策过程，有兴趣的系统，即系统动力学是指由偏微分方程 （PDE）的连续动态。
[ 编辑 ]定义
为了讨论的连续时间马氏决策过程中，我们将介绍两套符号：
如果状态空间和行为空间是有限的，
：状态空间;
：操作空间;
： 转换率功能;
： ，一个奖励功能。
如果状态空间和行为空间是连续的，
状态空间;
：可能的控制空间;
： 转换率的功能;
： ，报酬率等功能， ，其中 在前面的例子中，我们讨论的奖励功能。
[ 编辑 ]问题
离散时间马尔可夫决策过程一样，在连续时间马氏决策过程中，我们要找到最佳的政策或控制的，可以给我们的最佳预期的综合奖励：
哪里
[ 编辑 ]线性规划的制定
如果状态空间和行为空间是有限的，我们可以使用线性规划的制定，以找到最佳的政策，这是最早的解决方案之一。 在这里，我们只考虑的遍历模式，这意味着我们的连续时间MDP成为一个连续时间马尔可夫链遍历一个静止的政策下。 根据这一假设，虽然决策者可以在任何时候作出决定，在目前的状态，他无法得到更多的好处，使一个以上的行动。 这是更好地对他采取行动的时候，当从当前状态到另一种状态的系统中转。 在某些情况下（ 连续时间马氏决策过程的详细检查推论3.14
），如果我们的最优值函数 状态i是独立的，我们将有一个下面的公式：
如果存在一个函数 ，然后 将是最小g满足上面的方程。 以便找到 ，我们可以有以下的线性规划模型：
原始的线性规划（P-LP）
双线性规划（D-LP）
如果是一个可行的解决方案，D-LP 外来和D-LP问题中的约束满意。 一个可行的解决方案 为D-LP是说是最佳的解决方案，如果
所有可行解y（I，A）D-LP。 一旦我们找到了最佳的解决方案 我们可以使用这些最佳的解决方案，，建立最优策略。
[ 编辑 ]Hamilton-Jacobi-Bellman方程
在连续时间MDP，如果状态空间和动作空间是连续的，最佳的标准可以找到解决汉密尔顿 - 雅可比 -
贝尔曼（HJB）偏微分方程。 为了讨论的HJB方程，我们需要重新制定我们的问题
D（ ）是终端奖励功能， 是系统的状态向量， 我们试图找到系统的控制向量。 F（ ）展示了如何随时间变化的状态向量。 Hamilton-Jacobi-Bellman方程如下：
我们可以解决的方程来找到最优控制 ，这可能让我们的最优值
[ 编辑 ]应用
排队系统，流行的进程， 人口过程 。
[ 编辑 ]替代符号
术语和符号的MDP没有完全解决。 主要有两个来源 -
一个专注于最大化问题，如经济环境下，使用的行动，奖励，价值和调用的贴现因子 或 ，而其他重点工程和导航的最小化问题，使用控制，成本，成本与调用的贴现因子 。 此外，过渡概率的符号变化。
| 在这篇文章中 |
替代 |
评论 |
| 行动 |
控制 |
|
| 奖励 |
成本 |
是负的 |
| 值 |
成本与 |
是负的 |
| 政策 |
政策 |
|
| 贴现因子 |
贴现因子 |
|
| 转移概率 |
转移概率 |
|
此外，转移概率有时写 ， 或者，很少，
[ 编辑 ]参见
部分可观察马尔可夫决策过程
动态规划
Bellman方程的应用经济学的。
Hamilton-Jacobi-Bellman方程
最优控制;
[ 编辑 ]
^ 洛德韦克Kallenberg， 有限状态和动作的MDP，在俄勒冈州尤金A.范伯格，：亚当Shwartz（主编），“马尔可夫决策过程方法及应用 ，施普林格，2002年， ISBN
0-7923-7459-2
^ Burnetas
AN和Katehakis的MN（1997年）。 “最佳适应性政策马尔可夫决策过程”， 数学。 歌剧。 ，22（1），262-268
[ 编辑 ]
R.贝尔曼。 马尔可夫决策过程 。 中国数学和力学6日，1957。
RE贝尔曼动态规划 。 普林斯顿大学出版社，普林斯顿，新泽西州，1957年。 多佛平装版（2003年）， ISBN
0-486-42809-5 。
罗纳德·A.霍华德动态规划法和马尔可夫过程 ，麻省理工学院出版社，1960年。
D.
Bertsekas。 动态规划与最佳化控制。 第2卷，1995年，雅典娜，MA。
Burnetas，AN MN
Katehakis。 “马尔可夫决策过程的最优自适应政策，运筹学数学，22（1），1995年。
ML
Puterman。 马尔可夫决策过程 。 Wiley出版社，1994年。
的HC
Tijms。 随机模型的第一门课 。 Wiley出版社，2003年。
萨顿，RS和巴托AG 强化学习：介绍 。 麻省理工学院出版社，剑桥，MA，1998年。
JAE，?面包车Nunen。 一组折扣马氏决策问题的逐次逼近方法。 Z.运筹学，20:203-208，1976。
SP Meyn，2007年复杂网络控制技术 ，剑桥大学出版社，2007。 ISBN
978-0-521-88441-9 。 附录删节Meyn特威迪 。
SM罗斯。 1983年。 随机动态规划。 学术出版社
十国和O埃尔南德斯莱尔马。 连续时间马氏决策过程 ，施普林格，2009年。
ML
Puterman和申的MC改进的政策折扣马氏决策问题， 管理科学 ，1978年24迭代算法。
[ 编辑 ]外部链接
MDP
MATLAB工具箱 -一个很好的教程和MATLAB工具箱的使用的MDP。
强化学习的理查德·萨顿和Andrew G.巴托介绍
SPUDD的结构性MDP求解器，下载杰西·霍伊
学习解决马尔可夫决策过程 P.辛格Satinder
马尔可夫决策过程的最优自适应政策的Burnetas和Katehakis（1997年）。
