许多重要问题的核心并非单一、孤立的选择，而是在时间长河中一系列相互关联的决策 。一位医生为病人规划治疗方案，或是一个机器人在仓库中导航，都必须考虑今天的行动将如何塑造未来的可能性 。这种按顺序做出一系列决策的过程，被称为序贯决策。

现实世界充满了“噪声和不确定性” 。行动并不总能带来预想中的结果 。机器人接收到向前移动的指令，最终可能略微偏离了方向；一项精心策划的医疗方案，也可能产生意料之外的副作用。这种环境的本质特征是“随机性”（stochastic），即结果“部分是随机的，部分由决策者控制” 。这便是智能体（agent）在复杂环境中面临的核心挑战：在一个结果不完全可控的世界里，如何权衡短期收益与长期目标，从而做出最优选择 。

MDP的出现标志着人工智能领域一个根本性的思维转变。早期的AI规划系统大多假设世界是确定性的（deterministic），即一个动作必然导致一个唯一、可预测的结果 。程序员们往往偏爱这种可预测性，因为它让世界如同一个精确的状态机 。然而，这种模型在现实世界中显得脆弱。MDP则承认了一个更深刻的现实：智能行为不能依赖于完美的预知能力。一个真正智能的决策者，必须能够在概率和期望值的层面上进行推理和规划。

这个框架的核心是一种强大的抽象：将世界划分为“智能体”（agent）和“环境”（environment）两部分 。智能体是决策的主体，而环境是智能体所处的、并与之交互的外部世界。这种划分具有极高的通用性。一个在工厂里搬运货物的机器人是在物理环境中运行的智能体；一个下棋的AI程序是在数字棋盘环境中博弈的智能体；一个进行高频交易的算法则是在金融市场环境中操作的智能体 。MDP通过这种统一的交互模型，使得研究人员能够开发出独立于特定领域的通用求解算法。原则上，同一个算法既可以为机器人找到最优路径，也能为游戏角色制定最佳策略，只要问题能够被有效地构建为一个MDP。

一个简单的导航游戏

为了将抽象的概念具体化，我们将引入一个贯穿全文的简单示例——“网格世界”（Grid World）。这个“玩具问题”虽然简单，却浓缩了真实世界序贯决策问题的核心挑战

想象一个3x4的网格棋盘。这个世界包含以下几个元素：

• 智能体 (Agent): 一个简单的机器人，我们的决策者。它的初始位置在左下角的(1,1)单元格 。
• 目标 (Goal): 机器人的任务是到达右上角的(4,3)单元格，那里有一块“宝藏”。成功到达将获得丰厚的奖励 。
• 危险 (Hazard): 在(4,2)单元格有一个“火坑”。掉进去会导致严重的惩罚 。
• 障碍 (Obstacle): 在(2,2)单元格有一堵“墙”，机器人无法进入或穿过 。
• 行动 (Actions): 在任何非终点单元格，机器人都可以选择四种行动之一：上、下、左、右 。
• 不确定性 (Uncertainty): 这是问题的关键。机器人的移动是随机的，而非完全可控。我们采用一个常见的模型：当机器人意图向某个方向移动时，有80%的概率成功朝该方向移动一格；有10%的概率“打滑”到意图方向的左侧90度方向；还有10%的概率“打滑”到右侧90度方向 。如果任何方向的移动会导致撞墙，机器人将停留在原地 。

棋盘上的方格 (状态, S)

棋盘上的每一个单元格都代表了机器人可能所处的一种独特情况。在MDP的术语中，这被称为状态（State） 。所有可用单元格（除墙外）的集合构成了   状态空间（State Space）。一个状态必须包含做出未来决策所需的所有相关信息。例如，在这个游戏中，机器人的位置 (x, y) 就足以描述其当前情况 。

我们可以采取的移动 (行动, A)

从一个给定状态出发，机器人可以执行的一组可能移动（上、下、左、右）构成了行动空间（Action Space） 。值得注意的是，可用的行动集合有时会依赖于当前状态。例如，当机器人到达宝藏或掉入火坑（这些被称为终点状态）后，游戏结束，它将无法再采取任何行动。

光滑的地面 (转移概率, P)

这是MDP中最核心、也最能体现其随机性的概念。我们可以用“光滑的地面”这个比喻来理解前面提到的80/10/10移动模型。这个模型在形式上被称为转移模型（Transition Model） 或转移函数（Transition Function） ，通常用 T(s,a,s′) 或 P(s′∣s,a) 来表示 。它回答了这样一个问题：“如果我当前在状态   s，并采取行动 a，那么我最终到达状态 s’ 的概率是多少？”正是这个组件，使得环境具有了随机性（stochastic） 。

这个转移函数是环境固有的“物理定律”，智能体无法改变它 。机器人只能选择自己的行动意图（比如“向上”），但最终会移动到哪个格子，则是由环境根据转移概率来决定的。这清晰地划分了智能体和环境的职责：智能体是决策者，而环境（由转移概率和奖励定义）是它运行于其中的系统。智能体的任务不是改变世界的物理规则，而是在这些规则之内，学习如何行动以最好地实现其目标 。

奖励与惩罚 (奖励, R)

为了引导机器人学习，我们需要提供反馈。这种反馈的形式就是奖励（Reward） 。在我们的游戏中：

• 成功到达宝藏位置，会获得一个大的正奖励（例如 +1）。
• 不幸掉入火坑，会受到一个大的负奖励或惩罚（例如 -1）。
• 为了鼓励机器人尽快完成任务（即走最短路径），每走一步（非终点状态）都会获得一个小的负奖励（例如 -0.04），这可以看作是时间成本 。

这个奖励函数（Reward Function），通常表示为 R(s,a,s′)，定义了从状态 s 采取行动 a 并转移到状态 s’ 所能获得的即时价值。

这里蕴含着强化学习的一个基本哲学思想，即“奖励假设”（Reward Hypothesis）。智能体并没有被明确告知“请前往(4,3)单元格”。它被赋予的唯一指令是“最大化你未来获得的累积奖励”。所有复杂的、目标导向的行为，如主动寻找宝藏、小心翼翼地避开火坑，都完全是从这个简单的、标量形式的奖励信号中涌现出来的。设计者不直接编写路径或行为，而是设计激励机制。因此，强化学习的艺术在很大程度上是“奖励工程”（reward engineering）的艺术——设计一个能够引导出期望行为的奖励函数，而不是直接规定行为本身

黄金法则：未来只取决于现在

马尔可夫性质（Markov Property）

在深入探讨如何解决MDP之前，我们必须理解其根基所在的一个核心假设——马尔可夫性质（Markov Property）。这个性质是整个框架得以成立的基石，其名称源于俄罗斯数学家安德雷·马尔可夫（Andrey Markov）。

核心思想：“未来独立于过去，只取决于现在”

马尔可夫性质的通俗解释是“无记忆性”（memoryless）。一个随机过程如果具备马尔可夫性质，意味着其未来的演变概率只依赖于其当前的状态，而与它如何到达这个状态的历史路径完全无关。

在我们的网格世界中，这意味着：当机器人位于(3,1)单元格时，为了决定下一步的最佳移动，它所需要知道的全部信息就是它_当前_在(3,1)。至于它是从(2,1)向上移动过来的，还是从(3,2)向下移动过来的，这些历史信息对于预测它下一步会发生什么（即转移概率和潜在奖励）是完全无关的 。无论历史如何，从(3,1)出发采取“向上”行动，其结果的概率分布（80%到(3,2)，10%到(2,1)，10%到(4,1)）永远是相同的。

一个非马尔可夫的对比示例

为了更好地理解，让我们设想一个不满足马尔可夫性质的场景。修改一下游戏规则：“机器人不允许连续两次采取相同的行动”。现在，当机器人位于(3,1)时，它仅仅知道自己的位置是不够的。它还必须记住上一步采取的行动是什么。如果上一步是“向上”，那么这一步它就不能再选择“向上”。因此，历史信息（上一步的行动）直接影响了未来的可能性（当前可用的行动集合）。在这种情况下，过程就不再是马尔可夫的。状态的定义 (3,1) 不再充分，一个能够满足马尔可夫性质的“新状态”必须包含更多信息，例如 ((当前位置), (上一步的行动))。

为何这个假设如此重要？

马尔可夫性质是一个极其强大的简化假设。它有效地防止了状态空间的爆炸性增长。如果智能体在做决策时需要考虑其完整的历史路径，那么可能的状态数量（即不同的历史路径）将随着时间的推移呈指数级增长，这将使得问题在计算上变得无法处理 。马尔可夫性质通过确保当前状态  s 已经“封装”了所有与未来决策相关的历史信息，从而将问题保持在可控的范围内。

值得强调的是，马尔可夫性质并非世界本身固有的物理定律，而是我们对世界进行_建模_时的一种选择。一个看似非马尔可夫的问题，往往可以通过重新定义“状态”来使其变得马尔可夫化。例如，一个机器人的未来位置可能不仅取决于其当前位置，还取决于其当前的速度。如果只用位置作为状态，系统就是非马尔可夫的。但是，如果我们把状态定义为一个包含 (位置, 速度) 的元组，那么系统的下一个状态 (位置', 速度') 就很可能只依赖于当前状态和采取的行动（如加速或减速），从而满足了马尔可夫性质 。因此，将现实问题应用MDP框架的一个关键步骤，就是进行巧妙的“状态表示”（state representation）设计，选择一个既紧凑又能满足马尔可夫性质的状态定义。

策略

定义了MDP的世界和规则后，我们的最终目标是找到一种方法来解决它。一个MDP的解，不是一条单一的路径，而是一套完整的行动指南。

这套完整的行动指南被称为策略（Policy），通常用希腊字母 $\pi$ 表示 。一个策略是一个从状态到行动的映射，它明确地告诉智能体在 每一个可能的状态_下应该采取什么行动 。对于我们的网格世界，一个策略就像是在每个方格里都画上一个箭头（上、下、左或右），为机器人提供在任何位置的行动指示。

策略与传统的“计划”有着本质区别。一个传统的计划可能是一条固定的行动序列，例如“上、上、右、右”。这种计划非常脆弱：在我们的随机世界里，如果第一次“向上”的行动因为打滑而失败，导致机器人偏离了预定路线，那么后续的所有计划都将作废。而策略则具有强大的鲁棒性，因为它为智能体可能遇到的_任何_状态都提供了应对方案。它是一种反应式的、普遍适用的指导方针，而非一条僵化的行程路线 。

目标：最大化累积奖励

我们的目标是找到最优策略（optimal policy），记作 \pi^{*}。所谓最优，就是指遵循该策略能够使智能体在长期运行中获得期望的、最大的总奖励 。这个长期总奖励在文献中也常被称为“回报”（return）或“期望效用”（expected utility）。

无穷问题与远见的需求 (折扣因子, γ)

如果我们的机器人可以永远在网格世界里走下去（例如，在一个没有终点的环境中），那么它获得的奖励总和可能会是无限大，这将导致我们无法比较不同策略的优劣 。为了解决这个数学上的难题，并同时模拟一种对即时奖励的偏好，我们引入了一个名为折扣因子（Discount Factor） 的参数，用 $\gamma $ 表示，其取值范围在0和1之间 。

一个贴切的比喻是：“你愿意今天得到100美元，还是一年后得到100美元？” 。大多数人会选择前者，因为未来的收益存在不确定性，且即时满足感更强。折扣因子就模拟了这种时间偏好。在计算总回报时，一个在1步之后获得的奖励

$R_{1}$ 需要乘以 $\gamma$，2步之后获得的奖励 R_{2} 需要乘以 $\gamma^{2}$，以此类推。因此，智能体试图最大化的总折扣回报是 $R_{0}+\gamma R_{1}+\gamma^{2}R_{2}+…$ 。

折扣因子 $\gamma$ 的作用是双重的。从数学上讲，它确保了在无限时间的任务中，奖励的无限总和能够收敛到一个有限值，使得问题有明确的解 。从行为建模的角度看，它非常符合现实世界中的决策心理。一个接近0的 $\gamma$ 值会塑造一个“短视”的智能体，它几乎只关心眼前的即时奖励。而一个接近1的 $\gamma$ 值则会塑造一个“有远见”的智能体，它会为了长远的更大利益而牺牲一些眼前的得失 。这个参数让我们能够灵活地调整智能体的“规划视野”。

MDP的形式化定义

一个马尔可夫决策过程被形式化地定义为一个五元组 (S,A,P,R,$\gamma$)

• S: 一个有限的状态集合（状态空间）。
• A: 一个有限的行动集合（行动空间）。
• P: 状态转移概率函数，P(s^{’}|s, a) ，表示在状态 s 采取行动 a 后，转移到状态 s′ 的概率 。
• R: 奖励函数，R(s,a,s′)，表示在状态 s 采取行动 a 并转移到 s′ 后，获得的即时奖励 。
• $\gamma$: 折扣因子 ，用于衡量未来奖励的重要性 。

如何找到最佳策略：解锁贝尔曼方程

为状态打分

要评价一个策略的好坏，一个自然的想法是评估在该策略下，每个状态的“价值”。状态价值函数（state-value function），$V^{\pi}(S)$，被定义为：从状态 s 出发，并始终遵循策略 \pi，智能体能够获得的期望总折扣回报 。直观地说，一个状态的价值高，意味着从这个状态出发，未来可以获得很高的奖励。

价值的核心逻辑 (贝尔曼方程)

贝尔曼方程并非凭空而来，它源于一个非常直观的逻辑陈述：

“处于某个状态 s 的长期价值，等于你离开该状态时期望获得的即时奖励，加上你接下来可能进入的各个新状态的折扣后长期价值。”

这个陈述将一个看似复杂的长期价值问题，分解为了一个只涉及当前和下一步的局部关系。这正是动态规划思想的精髓 。

对于一个给定的策略 \pi，其状态价值函数 $V^{\pi}(S)$ 满足以下贝尔曼期望方程：

$V^{\pi}(s) = \sum_{a} \pi(a|s)\sum_{s^{‘}}P(s^{’}|s, a)$

这个方程建立了一个递归关系：一个状态的价值，取决于其后继状态的价值。对于所有状态，这构成了一个线性方程组，原则上可以求解得到每个状态的价值 。

贝尔曼最优方程

我们的目标是找到最优策略，而不仅仅是评估一个已知策略。为此，我们需要贝尔曼最优方程（Bellman Optimality Equation）。它描述了最优状态价值函数 V^{*}(s) 必须满足的条件。其背后的逻辑是：

“一个状态的最优价值，等于你在这个状态下选择那个最优行动后，所能获得的期望总回报。”

这个“最优行动”指的是那个能带来最佳“即时奖励 + 折扣后未来价值”组合的行动。这在方程中通过一个 max 算子来体现 ：

$$ V^{*}(s) = \max_{a \in A}\sum_{s^{‘}}P(s^{’}|s, a) $$

贝尔曼最优方程的伟大之处在于，它将寻找最优策略这个全局性的、涉及无限未来的难题，转化成了一系列局部的、递归的计算。它告诉我们，如果能知道所有后继状态的最优价值，就能计算出当前状态的最优价值。这个看似“鸡生蛋，蛋生鸡”的循环，实际上为我们提供了一种迭代求解的思路。通过反复应用这个局部更新规则，正确的、全局最优的长期价值会逐渐浮现出来。

分步求解网格世界

让我们将抽象的贝尔曼最优方程应用到具体的网格世界中，通过一个名为价值迭代（Value Iteration） 的经典算法，一步步地计算出最优策略 。

价值迭代算法的核心思想是，不断地将贝尔曼最优方程作为更新规则，迭代地更新每个状态的价值估计，直到这些价值收敛稳定。

价值迭代步骤

1. 初始化: 我们从一个“无知”的状态开始，假设所有状态的初始价值都为0。即，对于所有状态 s，令 V0(s)=0。
2. 第一次迭代: 我们使用贝尔曼最优方程来计算 V1(s)。对于网格中的每一个非终点状态 s，我们分别计算采取“上、下、左、右”四个行动中，哪一个能带来最大的期望回报。
   • 例如，对于宝藏 (4,3) 旁边的状态 (3,3)，如果它选择行动“右”，有80%的概率进入宝藏（获得+1奖励），10%概率滑到上面（撞墙，留在原地），10%概率滑到下面（进入火坑，获得-1奖励）。计算机会评估所有四个行动，并选择能使 V1(3,3) 最大的那个行动所对应的期望值。
   • 对于远离宝藏和火坑的状态，其第一次迭代后的价值将主要是由那-0.04的移动成本决定。
3. 后续迭代: 在第二次迭代中，我们使用 V1 的值来计算 V2。这时，一个奇妙的现象发生了：价值开始“传播”。在第一次迭代中，只有紧邻宝藏的状态获得了显著的正价值。而在第二次迭代中，这些状态的邻居们，因为有可能一步之内到达一个高价值状态，它们的价值也会相应提升。同样，紧邻火坑的负价值也会向外扩散。
4. • 收敛: 经过多次迭代，每个状态的价值将不再发生显著变化。此时，我们就认为算法已经收敛，得到了近似的最优价值函数 V∗(s) 。
5. 提取最优策略: 一旦我们拥有了最优价值函数 V∗(s)，提取最优策略 π∗(s) 就变得非常简单。对于每一个状态 s，我们只需“向前看一步”，计算采取每个行动 a 会带来的期望回报（即时奖励 + 折扣后的后继状态价值），然后选择那个能使回报最大化的行动。

智能行动的核心逻辑

马尔可夫决策过程不仅仅是一个数学工具，它更是对不确定性环境中目标导向行为逻辑的一种形式化表达。它提供了一个框架，让智能体能够在一个随机的环境中，通过学习一个最优策略来达成一个由奖励信号定义的目标。整个求解过程的核心，是利用马尔可夫性质，通过迭代计算将一个状态的长期价值与其邻近状态的价值联系起来。

理解MDP，就是理解现代人工智能和强化学习背后的基本原理之一 。它教会我们，复杂的智能行为可以从简单的规则和激励中涌现，也为我们设计能够在复杂、动态和不确定的世界中自主学习和决策的智能系统，提供了坚实的理论基石

References

https://gibberblot.github.io/rl-notes/single-agent/MDPs.html