强化学习笔记3--最优贝尔曼、蒙特卡洛

一、最优贝尔曼公式

一、最优策略的定义与存在性

在马尔可夫决策过程（MDP）中，我们定义状态值函数 vπ(s) 为在策略 π 下从状态 s 出发所能获得的期望累积回报。

1. 最优策略的定义

存在一个策略 π* ，使得对任意状态 s∈S和任意其他策略 π ，都有：

此时称 π* 为最优策略。注意，这里使用的是“≥”而非“>”，因为可能存在多个策略在所有状态下都达到相同最大值，即最优策略不唯一。

2. 最优策略的存在性

有限MDP：当状态空间 S 和动作空间 A 均为有限集时，最优策略一定存在。

无限MDP：在满足一定条件（如折扣因子 γ<1 、奖励有界等）下，最优策略也存在。

唯一性：最优策略不一定唯一。例如，若两个动作在某状态下具有相同的Q值，则选择任一动作的策略都是最优的。但最优状态值函数 v*(s) 是唯一的。

二、贝尔曼最优方程（Bellman Optimality Equation）

这是描述最优状态值函数 v*(s) 的递归关系式，其核心思想是：当前状态的最优值等于所有可能动作中，能带来最大期望回报的那个动作的值。

1. 标量形式

其中：

p(r,s′∣s,a)是在状态 s 执行动作 a 后获得奖励 r 并转移到状态 s′ 的概率；

γ∈[0,1)是折扣因子；

v*(s′)是下一状态的最优值。

2. 向量形式

将所有状态的值函数写成向量 ，则贝尔曼最优方程可写为：

或更常见地写作：

其中 T*是贝尔曼最优算子（Bellman Optimality Operator），定义为：

3. 与动作值函数的关系

我们也可以引入动作值函数 q(s,a) ，其定义为在状态 s 执行动作 a 后，遵循最优策略所能获得的期望回报：

于是贝尔曼最优方程也可写为：

这表明：最优状态值等于该状态下所有动作中最大的动作值。

三、最优策略的构造

从贝尔曼最优方程出发，我们可以直接构造出最优策略：

对于任意状态 s ，最优策略 π* 应选择使 q*(s,a) 最大的动作：

如果存在多个动作同时达到最大值，则可以任意分配概率（如均匀分布），这些策略都是最优的。

✅关键结论：最优策略是确定性的（deterministic），除非有多个动作具有相同最大Q值。

四、不动点理论与压缩映射

贝尔曼最优方程本质上是一个不动点方程：

1. 压缩映射定理（Contraction Mapping Theorem）

若算子 T* 是压缩映射，即存在常数 γ∈[0,1) ，使得对任意两个值函数向量 v,v′ ，有：

则：

2. 为什么贝尔曼最优算子是压缩映射？

因为折扣因子 γ<1，它保证了未来回报的贡献被逐步衰减，从而使得不同初始值函数之间的差异在迭代过程中不断缩小。所以可以采用不断迭代的方式进行v*求解，随意初始化v0，通过不断迭代，收敛时求得v*，每次获得vk后通过最优策略构造求解πk+1，在求解vk+1

📌重要推论：价值迭代算法（Value Iteration）正是基于此原理设计的，它能保证收敛到最优值函数。

五、影响贝尔曼最优方程的因素

1. 环境动态（Transition Dynamics）

p(r,s′∣s,a) ：由环境决定，不可控。

若环境是确定性的（即每个 (s,a) 对应唯一 (r,s′) ），则公式简化为：

2. 奖励函数（Reward Function）

r(s,a) 或 r(s,a,s′)：可由设计者调整。

线性变换不变性：若将奖励函数做仿射变换 r′=a⋅r+b （其中 a>0a>0 ），则最优策略不变，仅值函数缩放和平移。这是因为相对大小未变，而最优策略只关心动作间的相对优劣。

3. 折扣因子（Discount Factor）

γ∈[0,1)：控制智能体对未来回报的重视程度。

γ→0：短视，只关注即时奖励；

γ→1 ：远视，重视长期回报；

若 γ=1 ，需确保任务是有终止状态的（episodic），否则值函数可能发散。

二、最优策略获取

一、核心目标：求解最优状态值函数 v*与最优策略 π*

在马尔可夫决策过程（MDP）中，我们的终极目标是找到一个策略 π* ，使得从任意状态 s 出发，其期望累积回报最大，即：

其中 vπ(s)是在策略 π 下从状态 s 出发的期望回报。

二、值迭代（Value Iteration）

1. 核心思想

直接通过贝尔曼最优方程迭代更新状态值函数 vk(s) ，直到收敛到 v*(s) 。不需要显式维护策略 π，因为每次更新都隐含了“贪心选择最优动作”的操作。

关于 𝑉𝑘的性质：在收敛之前， 𝑉𝑘不是某个具体策略下的真实状态价值，而是对最优价值 𝑉* 的一个估计值（Estimate）。只有当算法收敛时， 𝑉𝑘→𝑉∗。

虽然算法主要更新价值，但每一步实际上隐含了一个贪婪策略（Greedy Policy），即π(a_max|s)=1。q(a_max|s)在所有q(s|a)中最大。

2. 算法步骤

初始化：任意设定初始值函数 v0(s) （如全0）。

迭代更新：对于每一个状态 s∈S ：

3、终止条件：

4、伪代码：

【算法】Value Iteration 【输入】状态空间 S, 动作空间 A, 转移概率 P, 奖励 R, 折扣因子 γ, 阈值 θ 【输出】最优价值函数 V*, 最优策略 π* 1. 【初始化】 for s ∈ S: V(s) ← 0 (或任意初始值) 2. 【主循环】(直到价值函数收敛) while ||V_new - V_old|| > θ: V_old ← copy(V) (保存上一轮的价值) for s ∈ S: // 步骤 1: 计算该状态下所有动作的 Q 值 max_q_value ← -∞ best_action ← null for a ∈ A(s): // 公式: Q(s,a) = Σ P(s'|s,a)[R + γV(s')] q_val ← Σ_{s'} P(s'|s,a) * [ R(s,a,s') + γ * V_old(s') ] if q_val > max_q_value: max_q_value ← q_val best_action ← a // 步骤 2: 更新价值 (贝尔曼最优算子) V(s) ← max_q_value // 步骤 3: 隐式更新策略 (贪婪策略) π(s) ← best_action 3. return V, π

三、策略迭代（Policy Iteration）

1. 核心思想

交替进行两个步骤：策略评估（Policy Evaluation）和策略改进（Policy Improvement），直到策略不再变化。

2. 算法步骤

3. 伪代码

【算法】Policy Iteration 【输入】同上 【输出】最优策略 π* 1. 【初始化】 for s ∈ S: π(s) ← 随机选择一个动作 V(s) ← 0 2. 【主循环】(直到策略不再改变) while π not converged: policy_stable ← true // --- 第一步：策略评估 (Policy Evaluation) --- // 目标：求解当前策略 π 下的真实价值 V_π while ||V_new - V_old|| > θ: V_old ← copy(V) for s ∈ S: // 公式: V(s) = Σ π(a|s) Q(s,a) // 对于确定性策略，就是直接计算当前动作的期望回报 v_sum ← 0 for a ∈ A(s): if a == π(s): // 只有当前策略选中的动作概率为1 q_val ← Σ_{s'} P(s'|s,a) * [ R(s,a,s') + γ * V_old(s') ] v_sum ← v_sum + q_val V(s) ← v_sum // --- 第二步：策略提升 (Policy Improvement) --- for s ∈ S: old_action ← π(s) // 寻找让 Q 值最大的动作 同值迭代 best_action ← argmax_a { Σ_{s'} P(s'|s,a) * [ R(s,a,s') + γ * V(s') ] } π(s) ← best_action if old_action != best_action: policy_stable ← false if policy_stable == true: break 3. return π

四、截断策略迭代（Truncated Policy Iteration）

1、值迭代与策略迭代的关系

可以将这两个算法看作是同一个优化过程的两种极端实现方式。

策略迭代：

评估阶段：进行无限次（或直到完全收敛）的扫描，精确计算当前策略的价值。

改进阶段：基于精确价值进行贪婪更新。

特点：每次迭代计算量大，但迭代次数少。

值迭代：

评估阶段：只进行1次扫描（即只迭代一次就立即更新策略/价值）。

改进阶段：隐含在价值更新中（取 max⁡max 操作）。

特点：每次迭代计算量小，但总迭代次数通常较多。

本质联系：值迭代其实就是策略迭代的一种特例，其中策略评估步骤被截断为只做一次迭代。

2、截断策略迭代

截断策略迭代是连接上述两者的通用框架。

当 m=1时，退化为值迭代。

当 m→∞ 时，趋近于策略迭代。

伪代码：

【算法】Truncated Policy Iteration 【参数】m (评估阶段的迭代次数，m=1即为值迭代) 1. 【初始化】 V(s) ← 0, π(s) ← 随机动作 2. 【主循环】 while π not converged: // --- 策略评估 (截断版) --- for i from 1 to m: // 只迭代 m 次，而不是直到收敛 for s ∈ S: // 使用当前策略 π 进行一步价值更新 V(s) ← Σ_{s'} P(s'|s, π(s)) * [ R(s, π(s), s') + γ * V(s') ] // --- 策略提升 --- for s ∈ S: π(s) ← argmax_a { Σ_{s'} P(s'|s,a) * [ R(s,a,s') + γ * V(s') ] } 3. return π

三、蒙特卡洛强化学习方法

核心思想

动态规划类方法（如策略迭代、值迭代）依赖环境的完整模型（状态转移概率 P、奖励函数 R）计算价值函数，而蒙特卡洛方法是典型的无模型（Model-Free）强化学习方法：它无需已知环境动力学，直接通过与环境交互采样完整的回合（Episode）数据，用累积回报Gt的经验平均值近似动作价值的数学期望，以此完成策略的评估与迭代优化。

动作价值函数的定义为：

其中Gt 是从时刻 t 到回合结束的累积折扣回报，πk为第 k 轮迭代的策略。根据大数定律，当采样的回合数量足够多时，回报的算术平均值会依概率收敛于期望价值。

MC 方法整体遵循策略迭代的经典框架，分为「策略评估」与「策略改进」两个阶段循环迭代，核心区别仅在于策略评估阶段用采样平均替代了模型驱动的贝尔曼方程计算。

一、基础蒙特卡洛策略迭代（MC Basic）

方法原理

这是最朴素的 MC 策略迭代实现，严格贴合 “采样平均近似期望” 的定义：

1. 初始化初始策略π0；
2. 策略评估：对每一个状态 - 动作对 (s,a)，单独从 (s,a) 出发，遵循当前策略生成大量完整episode，用所有回合起点处return的平均值作为q_πk(s,a) 的估计值；
3. 策略改进：评估完成后，对每个状态采用贪婪策略更新，选择动作价值最高的动作作为新策略的唯一输出。

特点与局限

原理直观，逻辑简单，是理解 MC 方法的基础版本；

采样效率极低：需要为每一个状态 - 动作对独立生成大量回合，状态与动作空间规模稍大就会产生极高的采样成本；

隐含探索起点假设：必须保证每个 (s,a) 都能作为回合的起点被采样，否则无法完成全空间的价值评估。

伪代码

【算法】Basic Monte Carlo Control (First-Visit) 【输入】状态空间 S, 动作空间 A, 折扣因子 γ, 迭代次数 K 【输出】最优动作价值函数 Q, 确定性最优策略 π 1. 【初始化】 for s ∈ S, a ∈ A(s): Q(s, a) ← 0 Returns(s, a) ← empty list // 用于存储该(s,a) pair的所有回报 π(s) ← arbitrary action // 初始任意策略 2. 【主循环】(重复 K 次或直到收敛) for k = 1 to K: // --- 生成 Episode --- Generate an episode using current policy π: S_0, A_0, R_1, ..., S_{T-1}, A_{T-1}, R_T // --- 策略评估 (Policy Evaluation) --- G ← 0 Visited_SA ← empty set // 确保 First-Visit (首次访问) // 逆序遍历 Episode (从 T-1 到 0) for t = T-1 downto 0: G ← γ * G + R_{t+1} if (S_t, A_t) not in Visited_SA: Append G to Returns(S_t, A_t) Q(S_t, A_t) ← average(Returns(S_t, A_t)) Add (S_t, A_t) to Visited_SA // --- 策略提升 (Policy Improvement) --- for each state s appeared in the episode: // 贪婪策略更新：选择当前 Q 值最大的动作 π(s) ← argmax_{a ∈ A(s)} Q(s, a) 3. return Q, π

二、带探索起点的蒙特卡洛方法（MC with Exploring Starts, MC ES）

方法原理

为解决 MC Basic 采样效率极低的问题，探索起点（Exploring Starts）方法对采样与更新方式做了核心优化：

1. 每条回合从随机选择的 (s,a) 开始，保证所有状态 - 动作对都有被采样的机会，维持探索起点假设；
2. 复用单条回合的全量数据：一条完整回合中所有时刻的 (st,at) 都可用于计算对应回报，无需为每个 (s,a) 单独生成回合。
3. 实现时采用逆序计算回报：从回合末尾向前逐步推导累积回报 Gt，避免重复计算，大幅提升运算效率。

根据统计规则可分为两类：

首次访问 MC：仅用回合中第一次出现 \((s,a)\) 对应的回报更新价值；

每次访问 MC：回合中每一次出现 \((s,a)\) 都用对应回报更新价值。 二者在理论上均收敛到真实价值。

特点

采样效率远高于 MC Basic，单条回合可更新多个状态 - 动作对的价值估计；

仍依赖探索起点假设，在很多真实场景中无法满足（例如无法强制智能体从任意状态开始交互）。

伪代码

【算法】Monte Carlo with Exploring Starts (ES) 【输入】状态空间 S, 动作空间 A, 折扣因子 γ, 迭代次数 K 【输出】最优动作价值函数 Q, 策略 π 1. 【初始化】 for s ∈ S, a ∈ A(s): Q(s, a) ← 0 Count(s, a) ← 0 // 记录访问次数用于增量更新 π(s) ← arbitrary action 2. 【主循环】 for k = 1 to K: // --- 探索起始 --- Randomly select S_0 ∈ S and A_0 ∈ A(S_0) such that all pairs have probability > 0 // --- 生成 Episode --- Generate episode starting from S_0, A_0 following π: S_0, A_0, R_1, ..., S_{T-1}, A_{T-1}, R_T // --- 策略评估 & 提升 (结合进行) --- G ← 0 Visited_SA ← empty set // 逆序处理，提高效率 for t = T-1 downto 0: G ← γ * G + R_{t+1} if (S_t, A_t) not in Visited_SA: // 增量式更新 Q 值 (无需存储所有历史回报) Count(S_t, A_t) ← Count(S_t, A_t) + 1 Q(S_t, A_t) ← Q(S_t, A_t) + (1 / Count(S_t, A_t)) * (G - Q(S_t, A_t)) // 立即进行策略提升 (Greedy) π(S_t) ← argmax_{a ∈ A(S_t)} Q(S_t, a) Add (S_t, A_t) to Visited_SA 3. return Q, π

三、ε- 贪心蒙特卡洛策略迭代（MC with ε-Greedy Policy）

方法原理

探索起点假设在绝大多数真实交互场景中无法成立，因此引入软策略（Soft Policy）思想：策略本身输出动作的概率分布，保证所有动作都有非零概率被选中，从而在交互过程中自然完成探索，无需依赖探索起点假设。

ε- 贪心策略是最经典的软策略实现，核心是平衡「探索」与「利用」：

• 以 1-ε的概率选择当前价值最高的贪心动作（利用已有经验）；
• 以ε的概率在所有动作中均匀随机选择（探索未知动作）。

具体概率公式为：

其中 |A(s)| 为状态 s 下的动作总数，a*为当前价值最高的贪心动作。

该方法属于同策略（On-Policy）方法：用于采样的策略与被评估、改进的策略是同一个，策略在迭代中逐步向更优的方向收敛。

特点

• 无需探索起点假设，适用于绝大多数真实环境的交互场景；
• 通过超参数ε灵活平衡探索与利用：ε越大，探索性越强；ε越小，策略越偏向贪心利用；
• 最终收敛到ε- 最优策略（而非严格最优策略），若要逼近全局最优，可随迭代逐步衰减ε

伪代码

【算法】Monte Carlo Control with ε-Greedy 【输入】状态空间 S, 动作空间 A, 折扣因子 γ, 探索率 ε, 迭代次数 K 【输出】最优动作价值函数 Q, ε-soft 策略 π 1. 【初始化】 for s ∈ S, a ∈ A(s): Q(s, a) ← 0 Count(s, a) ← 0 π(a|s) ← 1/|A(s)| // 初始化为均匀随机策略 2. 【主循环】 for k = 1 to K: // --- 生成 Episode --- // 使用当前的 ε-greedy 策略 π 生成数据 Generate episode: S_0, A_0, R_1, ..., S_{T-1}, A_{T-1}, R_T G ← 0 Visited_SA ← empty set // 逆序遍历 for t = T-1 downto 0: G ← γ * G + R_{t+1} if (S_t, A_t) not in Visited_SA: s ← S_t; a ← A_t // 更新 Q 值 Count(s, a) ← Count(s, a) + 1 Q(s, a) ← Q(s, a) + (1 / Count(s, a)) * (G - Q(s, a)) // --- 策略提升 (更新为新的 ε-greedy) --- // 找到当前 Q 值最大的动作 A_star ← argmax_{x ∈ A(s)} Q(s, x) // 更新策略概率分布 for each action x ∈ A(s): if x == A_star: π(x|s) ← 1 - ε + (ε / |A(s)|) else: π(x|s) ← ε / |A(s)| Add (s, a) to Visited_SA 3. return Q, π