一、从多臂赌博机到MDP
多臂赌博机问题只需要在单一情境下选择动作，而现实中的决策往往更复杂：一个动作不仅影响当下的奖励，还会改变未来的情境（状态）。例如，下棋时走一步棋会改变棋盘状态，进而影响后续所有可能的走法和最终胜负。
有限马尔可夫决策过程（finite MDP）正是为这种序列决策问题设计的数学框架。它通过明确状态、动作、奖励的交互关系，将“最大化长期累积奖励”这一目标转化为可计算的问题。
二、MDP的核心要素：智能体与环境的交互
MDP的核心是智能体（Agent）与环境（Environment）的动态交互，在离散时间步（t=0,1,2,...）中循环进行。具体流程如下：
- 状态（State）：环境在时间t的状态为（是所有可能状态的集合），代表智能体可观察到的环境信息（如棋盘布局、机器人位置）。
- 动作（Action）：智能体在状态下选择动作（是状态s下的可选动作集合），如“向左移动”“出棋到（x,y）位置”。
- 奖励（Reward）：环境对动作的即时反馈为（是奖励集合），如得分+1、碰撞-10。
- 状态转移：环境根据动作从状态转移到新状态，转移概率由环境动力学决定。
它们形成的交互轨迹为：
三、马尔可夫性与环境动力学
MDP的关键假设是马尔可夫性：下一个状态和奖励仅依赖于当前状态和动作，与过去的历史无关。用数学语言描述，即环境的动力学可表示为：
- ：在状态s下采取动作a后，转移到状态s'并获得奖励r的概率。
- 该函数需满足概率归一化：（对所有s, a）。
基于此，可推导状态转移概率（不考虑奖励）和预期奖励：
- 状态转移概率：
- 状态-动作的预期奖励：
四、目标：最大化长期累积奖励
智能体的目标不是最大化单步奖励，而是长期累积奖励的期望值。根据任务类型，累积奖励（回报，Return）的定义不同：
1. 情节任务（Episodic Tasks）
任务天然分为多个“情节”（如一局游戏、一次迷宫逃脱），每个情节有终止状态（如游戏结束）。回报定义为从当前步到情节结束的奖励总和：
其中T是情节终止的时间步。
2. 持续任务（Continuing Tasks）
任务无终止（如恒温控制、持续监控），需用衰减因子γ（
）确保无限奖励序列的总和有限：
- γ接近1：更关注长期奖励（有远见）；
- γ=0：只关注即时奖励（短视）。
两种任务的回报可统一为：
（递归关系，终止状态的
）。
五、策略与价值函数
为了量化“在某个状态下做得有多好”，MDP引入价值函数，其定义依赖于智能体的策略。
1. 策略（Policy）
策略
是状态到动作概率的映射：
表示在状态s下选择动作a的概率。策略指导智能体的行为，如“在状态s下有80%概率选a1，20%选a2”。
2. 价值函数（Value Functions）
价值函数衡量在策略
下，状态或状态-动作对的长期价值（预期回报）。
- 状态价值函数：
从状态s出发，遵循策略的预期回报：
- 动作价值函数：
在状态s下采取动作a后，遵循策略的预期回报：
3. 贝尔曼方程（Bellman Equation）
价值函数的核心性质是递归性，由贝尔曼方程描述。对于状态价值函数：
含义：状态s的价值 = 选择动作a的概率 × [该动作的即时奖励 + 下一状态s'的衰减价值] 的总和。
类似地，动作价值函数的贝尔曼方程为：
六、最优策略与最优价值函数
解决MDP的目标是找到最优策略——在所有状态下都能最大化长期回报的策略。
1. 最优价值函数
- 最优状态价值函数：所有策略中，状态s的最大可能价值：
- 最优动作价值函数：所有策略中，状态s下采取动作a的最大可能价值：
2. 贝尔曼最优方程
最优价值函数满足贝尔曼最优方程，它是求解最优策略的关键。
对于
：
含义：最优状态价值 = 选择“最好的动作a”（最大化后续回报）带来的预期即时奖励加下一状态的衰减最优价值。
对于
：
3. 如何找到最优策略？
一旦得到
或
，最优策略可通过贪婪选择得到：
- 基于：在状态s下，选择能最大化的动作a；
- 基于：在状态s下，直接选择最大的动作a。
任何对最优价值函数贪婪的策略都是最优策略。
七、实例：网格世界的MDP
考虑一个5×5的网格世界（如图3.2），每个格子是一个状态，动作是“上下左右”移动：
- 移出网格：奖励-1，状态不变；
- 特殊状态A：任何动作都获+10奖励，转移到A'；
- 特殊状态B：任何动作都获+5奖励，转移到B'；
- 其他情况：奖励0。
通过求解贝尔曼最优方程，可得到最优状态价值
（如A的价值≈24.4）和最优策略（如A处所有动作都是最优，因为都能到A'）。
八、总结
有限MDP通过状态、动作、奖励、转移概率四个要素，将序列决策问题形式化，核心是通过价值函数和贝尔曼方程量化长期回报，最终找到最优策略。
- 马尔可夫性简化了问题：只需关注当前状态和动作；
- 价值函数是连接即时奖励和长期目标的桥梁；
- 贝尔曼最优方程是求解最优策略的数学基础，后续强化学习算法（如动态规划、Q-Learning）均源于此。
MDP的框架为强化学习提供了严格的数学基础，但实际应用中常需近似求解（因状态空间可能极大），这也是后续章节的重点。