强化学习笔记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后通过最优策略构造求解πk1在求解vk1重要推论价值迭代算法Value Iteration正是基于此原理设计的它能保证收敛到最优值函数。五、影响贝尔曼最优方程的因素1. 环境动态Transition Dynamicsp(r,s′∣s,a) 由环境决定不可控。若环境是确定性的即每个 (s,a) 对应唯一 (r,s′) 则公式简化为2. 奖励函数Reward Functionr(s,a) 或 r(s,a,s′)可由设计者调整。线性变换不变性若将奖励函数做仿射变换 r′a⋅rb 其中 a0a0 则最优策略不变仅值函数缩放和平移。这是因为相对大小未变而最优策略只关心动作间的相对优劣。3. 折扣因子Discount Factorγ∈[0,1)控制智能体对未来回报的重视程度。γ→0短视只关注即时奖励γ→1 远视重视长期回报若 γ1 需确保任务是有终止状态的episodic否则值函数可能发散。二、最优策略获取一、核心目标求解最优状态值函数 v*与最优策略 π*在马尔可夫决策过程MDP中我们的终极目标是找到一个策略 π* 使得从任意状态 s 出发其期望累积回报最大即其中 vπ(s)是在策略 π 下从状态 s 出发的期望回报。二、值迭代Value Iteration1. 核心思想直接通过贝尔曼最优方程迭代更新状态值函数 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 Iteration1. 核心思想交替进行两个步骤策略评估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 Iteration1、值迭代与策略迭代的关系可以将这两个算法看作是同一个优化过程的两种极端实现方式。策略迭代评估阶段进行无限次或直到完全收敛的扫描精确计算当前策略的价值。改进阶段基于精确价值进行贪婪更新。特点每次迭代计算量大但迭代次数少。值迭代评估阶段只进行1次扫描即只迭代一次就立即更新策略/价值。改进阶段隐含在价值更新中取 max⁡max 操作。特点每次迭代计算量小但总迭代次数通常较多。本质联系值迭代其实就是策略迭代的一种特例其中策略评估步骤被截断为只做一次迭代。2、截断策略迭代截断策略迭代是连接上述两者的通用框架。当 m1时退化为值迭代。当 m→∞ 时趋近于策略迭代。伪代码【算法】Truncated Policy Iteration 【参数】m (评估阶段的迭代次数m1即为值迭代) 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 策略迭代实现严格贴合 “采样平均近似期望” 的定义初始化初始策略π0策略评估对每一个状态 - 动作对 (s,a)单独从 (s,a) 出发遵循当前策略生成大量完整episode用所有回合起点处return的平均值作为q_πk(s,a) 的估计值策略改进评估完成后对每个状态采用贪婪策略更新选择动作价值最高的动作作为新策略的唯一输出。特点与局限原理直观逻辑简单是理解 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_{t1} 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方法对采样与更新方式做了核心优化每条回合从随机选择的 (s,a) 开始保证所有状态 - 动作对都有被采样的机会维持探索起点假设复用单条回合的全量数据一条完整回合中所有时刻的 (st,at) 都可用于计算对应回报无需为每个 (s,a) 单独生成回合。实现时采用逆序计算回报从回合末尾向前逐步推导累积回报 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_{t1} 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_{t1} 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, π