马尔可夫决策过程

马尔可夫决策过程是一个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 t}$ 时刻${\displaystyle s}$ 状态下的动作${\displaystyle a}$ 导致${\displaystyle t+1}$ 时刻进入状态${\displaystyle s'}$ 的概率，
• ${\displaystyle R_{a}(s,s')}$ 状态${\displaystyle s}$ 经过动作${\displaystyle a}$ 转换到状态${\displaystyle s'}$ 后收到的即时奖励（或预期的即时奖励）。

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

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

优化目标

马尔可夫决策过程的目标是为决策者找到一个好的“策略”：一个函数${\displaystyle \pi }$ ，它指定决策者在状态${\displaystyle s}$ 时将选择的动作${\displaystyle \pi (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\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]}$ （我们选择${\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（例如，对于贴现率r，存在${\displaystyle \gamma =1/(1+r)}$ ）。较低的折扣率促使决策者倾向于尽早采取行动，而不是无限期地推迟行动。

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

模拟模型

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

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

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

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

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

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

${\displaystyle \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\}}$ 

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

著名的变体

数值迭代

数值迭代也称为反向归纳，不使用${\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}}$ 开始，作为价值函数的猜测。

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