序贯决策（马尔可夫决策过程）

序贯决策形式化了智能体如何在随机环境中随时间行动，它使用马尔可夫决策过程，其中行动产生奖励并以概率方式改变状态，以计算最大化长期预期奖励的策略。

Definition

马尔可夫决策过程由状态、行动、转移概率函数和奖励函数定义；序贯决策旨在找到一个将状态映射到行动的策略，该策略在给定模型的情况下，能够最大化预期的累积（通常是折扣的）奖励。

Scope

本主题涵盖了随时间变化的决策理论规划：马尔可夫决策过程（MDP）模型，包括状态、行动、转移概率、奖励和折扣；策略和价值函数；表征最优行为的贝尔曼方程；以及用于解决已知模型的价值迭代和策略迭代等动态规划算法。它还介绍了部分可观察马尔可夫决策过程（POMDP）和信念状态规划。重点在于模型已知时的规划；在模型未知的情况下从经验中学习策略属于强化学习，该领域属于机器学习子领域。

Core questions

• 在随机转移下随时间行动如何建模为状态、行动、转移和奖励？
• 贝尔曼最优方程如何描述最优策略的价值？
• 当模型已知时，价值迭代和策略迭代如何计算最优策略？
• 部分可观察性如何导致POMDP和基于信念状态的规划？

Key concepts

• 状态、行动、转移、奖励
• 策略
• 价值函数
• 折扣因子
• 贝尔曼方程
• 价值迭代
• 策略迭代
• POMDP和信念状态

Key theories

贝尔曼最优方程

一个状态的最优价值等于最佳即时奖励加上下一个状态的折扣预期最优价值；这种递归关系表征了最优序贯行为，是动态规划解决方案的基础。

价值迭代和策略迭代

对于已知的MDP，价值迭代重复应用贝尔曼更新直到收敛，而策略迭代则交替进行策略评估和改进；两者都保证能找到最优策略。

部分可观察马尔可夫决策过程

当状态不能直接观察时，规划是在信念状态（状态上的分布）上进行的，该信念状态根据观察结果进行更新；解决此类POMDP比完全可观察的情况要困难得多，但它捕捉了现实的感知限制。

Clinical relevance

基于MDP和POMDP的决策制定是机器人导航和控制、自动化对话管理、维护和库存决策以及资源分配的基础，并为强化学习在环境模型必须通过学习获得时提供了决策理论规划基础。

History

序贯决策源于贝尔曼的动态规划（1957年）和霍华德的策略迭代（1960年）。普特曼1994年的专著巩固了马尔可夫决策过程的理论，而Kaelbling、Littman和Cassandra（1998年）将部分可观察马尔可夫决策过程引入主流人工智能，作为在不确定感知下行动的模型。

Key figures

• Richard Bellman
• Ronald A. Howard
• Martin L. Puterman
• Leslie P. Kaelbling
• Michael L. Littman

Seminal works

• bellman1957
• puterman1994
• kaelbling1998

Frequently asked questions

这与强化学习有何不同？

使用MDP的序贯决策假设转移和奖励模型是已知的，因此可以通过动态规划直接计算最优策略。强化学习处理模型未知的情况，智能体必须从经验中学习一个好的策略；它使用MDP作为其底层形式化。

POMDP中的信念状态是什么？

在部分可观察马尔可夫决策过程中，智能体无法看到真实状态，因此它维护一个信念状态，即对可能状态的概率分布，该分布随着智能体采取行动和接收观察而更新。规划随后在这些信念状态上进行，而不是直接在隐藏状态上进行。