马尔可夫决策过程

甲Markov决策过程（MDP）是一个离散时间 的随机 控制过程。它提供了一个数学框架，用于在结果部分随机且部分受决策者控制的情况下对决策建模。MDP对于研究通过动态规划和强化学习解决的优化问题很有用。MDP至少早在1950年代就已为人所知。^[1]马氏决策过程研究的核心是罗纳德·霍华德（Ronald Howard）在1960年出版的《动态规划和马氏过程》一书。。^[2]它们用于许多学科，包括机器人技术，自动控制，经济学和制造。MDP的名称来自俄罗斯数学家Andrey Markov，因为它们是Markov链的扩展。

在每个时间步骤中，过程都处于某种状态 ${\ displaystyle s}$，决策者可以选择任何行动 ${\ displaystyle a}$ 该状态可用 ${\ displaystyle s}$。该过程在下一时间步响应，随机进入新状态${\ displaystyle s'}$，并给予决策者相应的奖励 ${\ displaystyle R_ {a}（s，s'）}$。

流程进入新状态的可能性 ${\ displaystyle s'}$受所选动作的影响。具体来说，由状态转换函数给定${\ displaystyle P_ {a}（s，s'）}$。因此，下一个状态${\ displaystyle s'}$ 取决于当前状态 ${\ displaystyle s}$ 以及决策者的行动 ${\ displaystyle a}$。但是给定${\ displaystyle s}$ 和 ${\ displaystyle a}$，它有条件地独立于所有先前的状态和动作；换句话说，MDP的状态转换满足Markov属性。

马尔可夫决策过程是马尔可夫链的扩展; 区别在于增加了动作（允许选择）和奖励（给予动机）。相反，如果每个状态仅存在一个动作（例如“等待”）并且所有奖励都相同（例如“零”），则马尔可夫决策过程将简化为马尔可夫链。

定义

马尔可夫决策过程是一个4 元组 ${\ displaystyle（S，A，P_ {a}，R_ {a}）}$，在哪里

• ${\ displaystyle S}$ 是一组有限的状态，
• ${\ displaystyle A}$ 是一组有限的动作（或者， ${\ displaystyle A_ {s}}$ 是状态可提供的有限操作集 ${\ displaystyle s}$），
• ${\ displaystyle P_ {a}（s，s'）= \ Pr（s_ {t + 1} = s'\ mid s_ {t} = s，a_ {t} = a）}$ 是行动的概率 ${\ displaystyle a}$ 处于状态 ${\ displaystyle s}$ 在时间 ${\ displaystyle t}$ 会导致状态 ${\ displaystyle s'}$ 在时间 ${\ displaystyle t + 1}$，
• ${\ displaystyle R_ {a}（s，s'）}$ 是从状态转换后获得的立即奖励（或预期的立即奖励） ${\ displaystyle s}$ 陈述 ${\ displaystyle s'}$，由于行动 ${\ displaystyle a}$

（注意：马尔可夫决策过程的理论没有指出 ${\ displaystyle S}$ 要么 ${\ displaystyle A}$ 是有限的，但是下面的基本算法假定它们是有限的。）

问题

MDP的核心问题是为决策者找到“政策”：一种功能 ${\ displaystyle \ pi}$ 指定动作 ${\ displaystyle \ pi（s）}$ 决策者在州内时会选择 ${\ displaystyle s}$。一旦以这种方式将马尔可夫决策过程与策略组合在一起，就可以固定每个状态的操作，并且所得到的组合的行为就像马尔可夫链一样（因为在状态中选择了操作${\ displaystyle s}$ 完全取决于 ${\ displaystyle \ pi（s）}$ 和 ${\ displaystyle \ Pr（s_ {t + 1} = s'\ mid s_ {t} = s，a_ {t} = a）}$ 减少到 ${\ displaystyle \ Pr（s_ {t + 1} = s'\ mid s_ {t} = s）}$，马尔可夫转换矩阵）。

目的是选择一项政策 ${\ displaystyle \ pi}$ 这将最大化随机奖励的某些累积功能，通常是在潜在无限范围内的预期折扣总和：

${\ displaystyle E [\ sum _ {t = 0} ^ {\ infty} {\ gamma ^ {t} R_ {a_ {t}}（s_ {t}，s_ {t + 1}）}]}$    （我们在哪里选择 ${\ displaystyle a_ {t} = \ pi（s_ {t}）}$，即政策规定的操作）。期望接管了${\ displaystyle s_ {t + 1} \ sim P_ {a_ {t}}（s_ {t}，s_ {t + 1}）}$

哪里 ${\ displaystyle \ \ gamma \}$ 折扣因子是否令人满意 ${\ displaystyle 0 \ leq \ \ gamma \ \ leq \ 1}$，通常接近1。（例如， ${\ displaystyle \ gamma = 1 /（1 + r）}$ 一定的折扣率r。）

由于具有马尔可夫性质，因此可以将特定问题的最佳策略写为 ${\ displaystyle s}$ 如上所述。

折扣因素促使决策者倾向于尽早采取行动，而不是无限期地推迟采取行动。

演算法

MDP的解决方案是一种策略，它描述了MDP中每个状态的最佳操作，称为最佳策略。可以通过多种方法（例如动态编程）找到此最佳策略。

一些动态编程解决方案需要状态转换函数的知识 ${\ displaystyle P}$ 和奖励功能 ${\ displaystyle R}$。其他人可以仅通过实验来解决MDP的最佳策略。

考虑状态转换函数的情况 ${\ displaystyle P}$ 和奖励功能 ${\ displaystyle R}$ 给出了MDP，我们寻求最佳策略 ${\ displaystyle \ pi ^ {*}}$ 最大化预期的折扣奖励。

计算此最佳策略的标准算法系列需要存储两个按状态索引的数组：值 ${\ displaystyle V}$，其中包含实际价值和政策 ${\ displaystyle \ pi}$，其中包含动作。在算法的最后，${\ displaystyle \ pi}$ 将包含解决方案和 ${\ displaystyle V（s）}$ 遵循州的解决方案，将包含（平均）要获得的奖励折扣的总和 ${\ displaystyle s}$。

该算法有两个步骤，（1）值更新和（2）策略更新，对所有状态以某种顺序重复此步骤，直到没有进一步的更改发生为止。两者都使用较旧的估算值来递归更新最佳策略和状态值的新估算值。

${\ displaystyle V（s）：= \ sum _ {s'} P _ {\ pi（s）}（s，s'）\ left（R _ {\ pi（s）}（s，s'）+ \ gamma V（s'）\ right）}$

${\ displaystyle \ pi（s）：= \ operatorname {argmax} _ {a} \ left \ {\ sum _ {s'} P（s'\ mid s，a）\ left（R（s'\ mid s ，a）+ \ gamma V（s'）\ right）\ right \}}$

它们的顺序取决于算法的变体。一个人也可以一次为所有州或每个州做这些事情，而且在某些州比其他州更常见。只要任何一个步骤都没有永久排除任何状态，该算法最终将得出正确的解决方案。^[3]

显着的变体

价值迭代

在值迭代（Bellman 1957）中，也称为向后归纳法，${\ displaystyle \ pi}$功能未使用；相反，${\ displaystyle \ pi（s）}$ 在 ${\ displaystyle V（s）}$每当需要它时。代入计算${\ displaystyle \ pi（s）}$ 进入计算 ${\ displaystyle V（s）}$给出合并的步骤： ^[]

${\ displaystyle V_ {i + 1}（s）：= \ max _ {a} \ left \ {\ sum _ {s'} P_ {a}（s，s'）\ left（R_ {a}（s ，s'）+ \ gamma V_ {i}（s'）\ right）\ right \}，}$

哪里 ${\ displaystyle i}$是迭代次数。值迭代始于${\ displaystyle i = 0}$ 和 ${\ displaystyle V_ {0}}$作为价值函数的猜测。然后进行迭代，反复计算${\ displaystyle V_ {i + 1}}$ 对于所有州 ${\ displaystyle s}$， 直到 ${\ displaystyle V}$收敛于左侧等于右侧（这是该问题的“ Bellman方程 ” ）。劳埃德·沙普利（Lloyd Shapley）在1953年发表的关于随机游戏的论文^[4]作为一种特殊情况，包括了MDP的价值迭代方法，但是直到后来才意识到这一点。^[5][]

策略迭代

在策略迭代中（Howard 1960），第一步执行一次，然后重复第二步，直到收敛为止。然后再次执行第一步，依此类推。

代替将第二步重复进行收敛，可以将其公式化并求解为一组线性方程。这些方程只是通过使${\ displaystyle s = s'}$在第二步方程式中。因此，将第二步重复进行收敛可以解释为通过松弛法（迭代法）求解线性方程^[]

该变体的优点是存在明确的停止条件：当数组 ${\ displaystyle \ pi}$ 如果在将步骤1应用于所有状态的过程中没有变化，则算法完成。

对于大量可能的状态，策略迭代通常比值迭代慢。

修改后的政策迭代

在修改的策略迭代中（van Nunen 1976；Puterman＆Shin 1978），第一步执行一次，然后第二步重复几次。然后再次执行第一步，依此类推。

优先清扫

在此变体中，优先考虑将步骤应用到在某种程度上很重要的状态-无论是否基于算法（ ${\ displaystyle V}$ 要么 ${\ displaystyle \ pi}$ 或基于使用情况（这些状态接近开始状态，或者使用该算法的人或程序可能感兴趣的状态）。

扩展和概括

马尔可夫决策过程是一个只有一名玩家的随机游戏。

部分可观察性

上面的解决方案假设状态为 ${\ displaystyle s}$知道何时采取行动；除此以外${\ displaystyle \ pi（s）}$无法计算。如果此假设不成立，则该问题称为部分可观察的马尔可夫决策过程或POMDP。

Burnetas和Katehakis在“马尔可夫决策过程的最佳自适应策略”中提供了这一领域的重大进展。^[6]在这项工作中，在有限的状态作用空间和过渡律的不可约性的假设下，构造了一类具有一致的最大收敛速度特性的自适应策略，该特性对于总的预期有限水平奖励具有统一性。这些政策规定，在每个状态和时间段内，对行动的选择应基于指数，该指数是估计的平均奖励最优性方程式右侧的通货膨胀。

强化学习

如果概率或奖励未知，那么问题就是强化学习之一。^[7]

为此，定义进一步的功能非常有用，它对应于执行操作 ${\ displaystyle a}$ 然后最佳地继续运行（或根据当前的任何一项政策）：

${\ displaystyle \ Q（s，a）= \ sum _ {s'} P_ {a}（s，s'）（R_ {a}（s，s'）+ \ gamma V（s'））。\ }$

虽然此功能也是未知的，但是学习过程中的经验是基于 ${\ displaystyle（s，a）}$ 对（连同结果 ${\ displaystyle s'}$; 也就是说，“我当时处于状态${\ displaystyle s}$ 我试着做 ${\ displaystyle a}$ 和 ${\ displaystyle s'}$ 发生”）。因此，一个数组 ${\ displaystyle Q}$并利用经验直接对其进行更新。这就是所谓的Q学习。

强化学习可以解决马尔可夫决策过程，而无需明确指定过渡概率；价值和策略迭代中需要转移概率的值。在强化学习中，不是通过明确指定过渡概率，而是通过通常从统一随机初始状态重新启动多次的模拟器来访问过渡概率。强化学习也可以与函数逼近结合使用，以解决状态很多的问题。

学习自动机

MDP过程在机器学习理论中的另一种应用称为学习自动机。如果环境是随机的，这也是强化学习的一种。Narendra和Thathachar（1974）对第一份详细学习自动机论文进行了调查，最初将它们明确描述为有限状态自动机。^[8]与强化学习类似，学习自动机算法还具有在概率或奖励未知的情况下解决问题的优点。学习自动机和Q学习之间的区别在于，前一种技术省略了Q值的存储，但是直接更新动作概率以找到学习结果。学习自动机是一种具有严格收敛性证明的学习方案。^[9]

在学习自动机理论时，随机自动机包括：

• 一组X的可能的输入，
• 一组Φ= {Φ ₁，...，Φ _小号 }可能的内部状态，
• 一组α= {α ₁，...，α _{- [R} }可能的输出，或动作，用- [R  ≤  小号，
• 的初始状态概率矢量p（0）=« p ₁（0），...，p _小号（0）»，
• 一个可计算函数 甲其中每个时间步骤之后吨生成p（吨  从+ 1）p（吨），当前输入，与当前状态，并且
• 函数G：Φ→α，它在每个时间步生成输出。

这种自动机的状态对应于“离散状态离散参数马尔可夫过程 ”的状态。^[10]在每个时间步吨  = 0,1,2,3，...，所述自动机读取从其环境的输入时，更新P（吨）至P（吨  + 1）由甲，随机选择一个的后继状态根据概率P（t  + 1）并输出相应的动作。反过来，自动机的环境读取动作并将下一个输入发送到自动机。^[9]

范畴理论解释

除奖励外，马尔可夫决策过程 ${\ displaystyle（S，A，P）}$可以用范畴理论来理解。即让${\ displaystyle {\ mathcal {A}}}$表示具有生成集A的自由monoid。让DIST表示Kleisli类别中的Giry案单子。然后是一个函子${\ displaystyle {\ mathcal {A}} \ to \ mathbf {Dist}}$对状态集S和概率函数P进行编码。

这样，可以将Markov决策过程从Monoid（具有一个对象的类别）推广到任意类别。一个人可以称之为结果${\ displaystyle（{\ mathcal {C}}，F：{\ mathcal {C}} \ to \ mathbf {Dist}}}$一个依赖于上下文的Markov决策过程，因为从一个对象移动到另一个中${\ displaystyle {\ mathcal {C}}}$ 更改可用操作集和可能状态集。

模糊马尔可夫决策过程（FMDP）

在MDP中，最佳策略是使未来奖励的概率加权总和最大化的策略。因此，最优策略由几个动作组成，这些动作属于一组有限的动作。在模糊马尔可夫决策过程（FMDP）中，首先，将值函数计算为常规MDP（即，具有一组有限的动作）；然后，通过模糊推理系统提取策略。换句话说，价值函数被用作模糊推理系统的输入，策略是模糊推理系统的输出。^[11]

连续时间马尔可夫决策过程

在离散时间马尔可夫决策过程中，决策以离散时间间隔进行。但是，对于连续时间的马尔可夫决策过程，决策者可以随时选择做出决策。与离散时间马尔可夫决策过程相比，连续时间马尔可夫决策过程可以更好地对具有连续动力学的系统的决策过程建模，即系统动力学由偏微分方程（PDE）定义。

定义

为了讨论连续时间马尔可夫决策过程，我们引入两组符号：

如果状态空间和动作空间是有限的，

• ${\ displaystyle {\ mathcal {S}}}$：国家空间；
• ${\ displaystyle {\ mathcal {A}}}$：行动空间；
• ${\ displaystyle q（i \ mid j，a）}$： ${\ displaystyle {\ mathcal {S}} \ times {\ mathcal {A}} \ rightarrow \ triangle {\ mathcal {S}}}$，过渡速率函数；
• ${\ displaystyle R（i，a）}$： ${\ displaystyle {\ mathcal {S}} \ times {\ mathcal {A}} \ rightarrow \ mathbb {R}}$，奖励功能。

如果状态空间和动作空间是连续的，

• ${\ displaystyle {\ mathcal {X}}}$：状态空间；
• ${\ displaystyle {\ mathcal {U}}}$：可能的控制空间；
• ${\ displaystyle f（x，u）}$： ${\ displaystyle {\ mathcal {X}} \ times {\ mathcal {U}} \ rightarrow \ triangle {\ mathcal {X}}}$，转换率函数；
• ${\ displaystyle r（x，u）}$： ${\ displaystyle {\ mathcal {X}} \ times {\ mathcal {U}} \ rightarrow \ mathbb {R}}$奖励率函数 ${\ displaystyle r（x（t），u（t））\，dt = dR（x（t），u（t））}$，在哪里 ${\ displaystyle R（x，u）}$ 是我们在先前案例中讨论的奖励函数。

问题

像离散时间马尔可夫决策过程一样，在连续时间马尔可夫决策过程中，我们希望找到可以为我们提供最佳预期综合奖励的最优策略或控制：

${\ displaystyle \ max \ operatorname {E} _ {u} \ left [\ left。\ int _ {0} ^ {\ infty} \ gamma ^ {t} r（x（t），u（t））） \，dt \; \ right | x_ {0} \ right]}$

哪里 ${\ displaystyle 0 \ leq \ gamma <1。}$

线性规划公式

如果状态空间和动作空间是有限的，我们可以使用线性规划来找到最优策略，这是最早应用的方法之一。在这里，我们仅考虑遍历模型，这意味着在固定策略下，我们的连续时间MDP成为遍历的连续时间马尔可夫链。在这种假设下，尽管决策者可以在当前状态下随时做出决定，但他不能通过采取一项以上的行动而获得更多收益。最好只在系统从当前状态转换到另一状态时才采取措施。在某些情况下，（如果需要最优值函数，请参见连续时间马尔可夫决策过程的推论3.14 ）${\ displaystyle V ^ {**}}$ 独立于国家 ${\ displaystyle i}$，我们将具有以下不等式：

${\ displaystyle g \ geq R（i，a）+ \ sum _ {j \ in S} q（j \ mid i，a）h（j）\ quad \ forall i \ in S {\ text {和}} a \ in A（i）}$

如果存在功能 ${\ displaystyle h}$， 然后 ${\ displaystyle {\ bar {V}} ^ {*}}$ 将是最小的 ${\ displaystyle g}$满足上式 为了找到${\ displaystyle {\ bar {V}} ^ {*}}$，我们可以使用以下线性编程模型：

• 原始线性程序（P-LP）

${\ displaystyle {\ begin {aligned} {\ text {Minimize}} \ quad＆g \\ {\ text {st}} \ quad＆g- \ sum _ {j \ in S} q（j \ mid i，a） h（j）\ geq R（i，a）\，\，\ forall i \ in S，\，a \ in A（i）\ end {aligned}}}$

• 双线性程序（D-LP）

${\ displaystyle {\ begin {aligned} {\ text {Maximize}}＆\ sum _ {i \ in S} \ sum _ {a \ in A（i）} R（i，a）y（i，a） \\ {\ text {st}}＆\ sum _ {i \ in S} \ sum _ {a \ in A（i）} q（j \ mid i，a）y（i，a）= 0 \ quad \ forall j \ in S，\\＆\ sum _ {i \ in S} \ sum _ {a \ in A（i）} y（i，a）= 1，\\＆y（i，a）\ geq 0 \ qquad \ forall a \ in A（i）{\ text {和}} \ forall i \ in S \ end {aligned}}}$

${\ displaystyle y（i，a）}$ 是D-LP的可行解决方案，如果 ${\ displaystyle y（i，a）}$是非本机的，并且满足D-LP问题中的约束。可行的解决方案${\ displaystyle y ^ {*}（i，a）}$ 如果满足以下条件，则DLP的最佳解决方案是

${\ displaystyle {\ begin {aligned} \ sum _ {i \ in S} \ sum _ {a \ in A（i）} R（i，a）y ^ {*}（i，a）\ geq \ sum _ {i \ in S} \ sum _ {a \ in A（i）} R（i，a）y（i，a）\ end {aligned}}}$

对于所有可行的解决方案 ${\ displaystyle y（i，a）}$到D-LP。一旦找到最佳解决方案${\ displaystyle y ^ {*}（i，a）}$，我们可以使用它来建立最佳策略。

汉密尔顿–雅各比–贝尔曼方程

在连续时间的MDP中，如果状态空间和动作空间是连续的，则可以通过求解Hamilton–Jacobi–Bellman（HJB）偏微分方程来找到最佳准则。为了讨论HJB方程，我们需要重新构造问题

${\ displaystyle {\ begin {aligned} V（x（0），0）= {}＆\ max _ {u} \ int _ {0} ^ {T} r（x（t），u（t）） \，dt + D [x（T）] \\ {\ text {st}} \ quad＆{\ frac {dx（t）} {dt}} = f [t，x（t），u（t） ] \ end {aligned}}}$

${\ displaystyle D（\ cdot）}$ 是终端奖励功能， ${\ displaystyle x（t）}$ 是系统状态向量， ${\ displaystyle u（t）}$ 是我们试图找到的系统控制向量。 ${\ displaystyle f（\ cdot）}$显示状态向量如何随时间变化。汉密尔顿-雅各比-贝尔曼方程如下：

${\ displaystyle 0 = \ max _ {u}（r（t，x，u）+ {\ frac {\ partial V（t，x）} {\ partial x}} f（t，x，u））}$

我们可以求解方程来找到最优控制 ${\ displaystyle u（t）}$，这可以给我们带来最佳价值 ${\ displaystyle V ^ {**}}$

应用

连续时间马尔可夫决策过程在排队系统，流行过程和人口过程中都有应用。

替代符号

MDP的术语和符号尚未完全确定。主要有两大类：一类是针对诸如经济学之类的上下文中的最大化问题，使用术语“行动”，“奖励”，“价值”和“折现因子”${\ displaystyle \ beta}$ 要么 ${\ displaystyle \ gamma}$，而另一个则侧重于工程和导航方面的最小化问题，使用控制，成本，运输成本和折现系数这些术语^[]${\ displaystyle \ alpha}$。此外，转移概率的表示法也有所不同。

在这篇文章中	另类	评论
行动 ${\ displaystyle a}$	控制 ${\ displaystyle u}$
奖励 ${\ displaystyle R}$	成本 ${\ displaystyle g}$	${\ displaystyle g}$ 是负数 ${\ displaystyle R}$
值 ${\ displaystyle V}$	成本 ${\ displaystyle J}$	${\ displaystyle J}$ 是负数 ${\ displaystyle V}$
政策 ${\ displaystyle \ pi}$	政策 ${\ displaystyle \ mu}$
折现因子 ${\ displaystyle \ \ gamma \}$	折现因子 ${\ displaystyle \ alpha}$
转移概率 ${\ displaystyle P_ {a}（s，s'）}$	转移概率 ${\ displaystyle p_ {ss'}（a）}$

此外，有时会写出转移概率 ${\ displaystyle \ Pr（s，a，s'）}$， ${\ displaystyle \ Pr（s'\ mid s，a）}$ 或很少 ${\ displaystyle p_ {s's}（a）。}$

约束马尔可夫决策过程

约束马尔可夫决策过程（CMDP）是马尔可夫决策过程（MDP）的扩展。MDP和CMDP之间存在三个基本区别。^[12]

• 采取一项行动后会产生多种费用，而不是一项。
• CMDP仅通过线性程序来解决，而动态程序则不起作用。
• 最终策略取决于起始状态。

CMDP有许多应用程序。最近，它已在机器人技术的运动计划场景中使用。^[13]

也可以看看

• 概率自动机
• 量子有限自动机
• 部分可观察的马尔可夫决策过程
• 动态编程
• Bellman方程在经济学中的应用。
• 汉密尔顿–雅各比–贝尔曼方程
• 最佳控制
• 递归经济学
• 马比诺基翁羊问题
• 随机游戏
• Q学习

笔记

参考文献

外部链接

• 用于MATLAB，GNU Octave，Scilab和R的MDP工具箱。马尔可夫决策过程（MDP）工具箱。
• 用于Matlab的MDP工具箱 –一个出色的教程和用于MDP的Matlab工具箱。
• 适用于Python的MDP工具箱用于解决MDP的软件包
• POMDPs.jl灵活的接口，用于使用各种求解器在Julia中定义和求解MDP
• 理查德·萨顿和安德鲁·巴托的《强化学习入门》
• SPUDD由Jesse Hoey下载的结构化MDP求解器
• 学习解决马尔可夫决策过程由Satinder P.辛格
• Burnetas和Katehakis（1997）提出的马尔可夫决策过程的最佳自适应策略。