马尔可夫决策过程

在数学中，马可夫决策过程（英语：Markov decision process，MDP）是离散时间随机控制过程。 它提供了一个数学框架，用于在结果部分随机且部分受决策者控制的情况下对决策建模。 MDP对于研究通过动态规划解决的最佳化问题很有用。 MDP至少早在1950年代就已为人所知； 一个对马可夫决策过程的核心研究是 罗纳德·霍华德于1960年出版的《动态规划和马可夫过程》。 它们被用于许多领域，包括机器人学，自动化，经济学和制造业。 MDP的名称来自俄罗斯数学家安德雷·马可夫，因为它们是马可夫链的推广。

在每个时间步骤中，随机过程都处于某种状态$s$，决策者可以选择在状态$s$下可用的动作$a$。 该随机过程在下一时间步骤会随机进入新状态$s'$，并给予决策者相应的回馈$R_{a}(s,s')$。

随机过程进入新状态$s'$的机率受所选操作影响。 具体来说，它是由状态转换函数$P_{a}(s,s')$给出的。 因此，下一个状态$s'$取决于当前状态$s$和决策者的动作$a$。 但是给定$s$和$a$，它条件独立于所有先前的状态和动作； 换句话说，MDP的状态转换满足马尔可夫性质。

马尔可夫决策过程是马尔可夫链的推广，不同之处在于添加了行动（允许选择）和奖励（给予动机）。反过来说，如果每个状态只存在一个操作和所有的奖励都是一样的，一个马尔可夫决策过程可以归结为一个马尔可夫链。

定义

一个简单的MDP示例，包含三个状态（绿色圆圈）和两个动作（橙色圆圈），以及两个奖励（橙色箭头）

马尔可夫决策过程是一个4元组$(S,A,P_{a},R_{a})$，其中:

• $S$是状态空间的集合，
• $A$是动作的集合，也被称为动作空间（比如说$A_{s}$是状态$s$中可用的动作集合），
• $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$是$t$时刻$s$状态下的动作$a$导致$t+1$时刻进入状态$s'$的概率，
• $R_{a}(s,s')$状态$s$经过动作$a$转换到状态$s'$后收到的即时奖励（或预期的即时奖励）。

状态和行动空间可能是有限的，也可能是无限的。一些具有可数无限状态和行动空间的过程可以简化为具有有限状态和行动空间的过程。

策略函数$\pi$是从状态空间（$S$）到动作空间（$A$）的（潜在概率）映射。

优化目标

马尔可夫决策过程的目标是为决策者找到一个好的“策略”：一个函数$\pi$，它指定决策者在状态$s$时将选择的动作$\pi (s)$。一旦以这种方式将马尔可夫决策过程与策略组合在一起，就可以确定在每个状态的动作，并且生成的组合行为类似于马尔可夫链（因为在状态$s$的动作都由$\pi (s)$决定，$\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$简化为$\Pr(s_{t+1}=s'\mid s_{t}=s)$，成为一个马尔可夫转移矩阵）。

目标是选择一个策略$\pi$，使随机奖励的累积函数最大化，通常是在潜在的无限范围内的预期贴现总和:

$E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]$（我们选择$a_{t}=\pi (s_{t})$也就是策略给出的动作）。并且期望值为$s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})$。

其中$\ \gamma \$是折现因子，满足$0\leq \ \gamma \ \leq \ 1$，通常接近于1（例如，对于贴现率r，存在$\gamma =1/(1+r)$）。较低的折扣率促使决策者倾向于尽早采取行动，而不是无限期地推迟行动。

使上述函数最大化的策略称为最优策略，通常用$\pi ^{*}$表示。一个特定的MDP可能有多个不同的最佳策略。由于马可夫决策过程的性质，可以证明最优策略是当前状态的函数，就像上面所叙述的那样。

模拟模型

在许多情况下，很难明确地表示转移概率分布$P_{a}(s,s')$。在这种情况下，可以使用模拟器通过提供来自转换发行版的示例来隐式地对MDP建模。隐式MDP模型的一种常见形式是情景环境模拟器，它可以从初始状态启动，生成后续状态，并在每次接收到操作输入时给予奖励。通过这种方式，我们可以模拟出目标经过的状态、采取的行动以及获得的奖励（统称“轨迹”）。

另一种形式的模拟器是生成模型，即能够生成下一个状态的样本并提供所有状态和行动奖励的单步骤模拟器。在用伪代码表示的算法中，$G$通常用来表示生成模型。例如，表达式$s',r\gets G(s,a)$可以表示从生成模型中取样的动作，其中$s$和$a$是当前状态和动作，$s'$和$r$是下一步的状态和奖励。与情景模拟器相比，生成模型的优势在于它可以从任何状态获取数据，而不仅仅是在轨迹中遇到的状态。

这些模型类形成了信息内容的层次结构：显式模型通过从分布中采样简单地生成生成模型，并且生成模型的重复应用生成轨迹模拟器。在相反的方向上，只能通过回归分析研究近似模型。可用于特定MDP的模型类型在确定哪种解决方案算法合适方面起著重要作用。例如，下一节中描述的动态规划算法需要一个显式模型，而蒙地卡罗树搜寻需要一个生成模型（或可以在任何状态下复制的情景模拟器），而大多数强化学习算法只需要一个轨迹模拟器 。

算法

可以通过各种方法（例如动态规划）找到具有有限状态和动作空间的MDP的解决方案。本节中的算法适用于具有有限状态和动作空间并明确给出转移概率和奖励函数的MDP，但基本概念可以扩展到处理其他问题类别，例如使用函数趋近。

为有限状态和动作MDP计算最优策略的标准算法系列需要存储两个按状态索引的数列：第一个数列是$V$，用来储存实数，以及策略$\pi$，用来存动作。在算法结束时，$\pi$将存储每一个状态时的解决方案，而$V(s)$将存储从状态$s$遵循该解决方案获得的奖励的折扣总和（平均）。

$V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)$

$\pi (s):={\underset {a}{\operatorname {arg\,min} }}\left\{\sum _{s'}P(s'\mid s,a)\left(R(s'\mid s,a)+\gamma V(s')\right)\right\}$

它们的顺序取决于你所采用的算法的变体，可以一次或逐个状态地对所有状态执行它们，并且对某些状态比其他状态更频繁。 只要没有状态被永久排除在任何一个步骤之外，算法最终将得出正确的解决方案。

著名的变体

数值迭代

数值迭代也称为反向归纳，不使用$\pi$函数.相反，$\pi (s)$的值在需要时在$V(s)$内计算。 将$\pi (s)$的计算代入$V(s)$的计算得出组合步骤：

$V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s'|s)\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},$

其中$i$是迭代数，值迭代从$i=0$和$V_{0}$开始，作为价值函数的猜测。

参见

• 马尔可夫链
• 半马尔可夫过程
• 随机漫步
• 布朗运动
• 马尔可夫模型
• 隐马尔可夫模型
• 学习自动机
• 部分可观察马可夫决策过程

参考文献

• Yosida, K. “Functional Analysis”, Ch XIII, § 3, Springer-Verlag, 1968. ISBN 3-540-58654-7
• Ribarič.M. and I.Vidav, “An inequality for concave functions.” Glasnik Matematički 8 (28), 183–186 (1973).

外部链接

• 埃里克·韦斯坦因. Markov process. MathWorld.