强化学习最优策略：贝尔曼最优方程与价值迭代详解

强化学习写到现在这个系列第三篇前面两篇把马尔可夫决策过程、回报折扣、状态价值函数和贝尔曼方程都过了一遍。但不少读者卡在同一个地方我已经能对一个给定策略算出价值函数了可最优到底怎么定义一个策略比另一个策略好好在哪里更关键的是好到顶的那个策略该怎么找这篇就是把最优状态价值函数和最优策略这条逻辑链彻底拆干净。先讲清楚最优是在什么集合里定义、用什么标准比较然后从贝尔曼最优方程出发推导出v*(s)和q*(s,a)的关系再讲怎么从最优价值函数贪心提取策略最后给出策略迭代和价值迭代两条算法路线配合一个3×3网格世界的手算示例把每一步迭代数值都摆到台面上。适合那些已经懂贝尔曼方程、但一想到最优就发懵的读者。1. 最优到底在哪个集合里定义策略空间与比较标准很多资料一上来就写最优价值函数v*(s)却没先说清楚一个前提我们是在多大一个策略池子里找最优的这个问题看起来抽象实际上直接影响你后面是用穷举、动态规划还是迭代法。1.1 确定性策略与随机策略谁更值得搜索强化学习里的策略分为两类。确定性策略是每个状态下只选一个动作记作π(s)a随机策略是每个状态下按概率分布选动作记作π(a|s)。初学者往往觉得随机策略更灵活、搜索空间更大最优策略应该藏在里面。这个直觉在连续控制、部分可观测环境里有一点点道理但在有限状态、有限动作的马尔可夫决策过程MDP里有个重要结论只要存在最优策略就一定存在一个确定性最优策略。也就是说你在随机策略的海滩上费劲淘金到头来会发现最优解已经躺在确定性策略的浅滩上了。这个定理的细节不展开证明但它的实际意义很直接搜索策略时把注意力放在确定性策略上就够了不用为每个状态维护一个动作概率分布计算量小得多。当然这说的是存在性不是说随机策略没有用探索阶段、博弈场景里随机性依然有价值那是另一个话题。1.2 策略优劣用什么尺子量逐状态字典序有了策略池子接下来要解决比较标准。一个策略π在状态s下有一个价值v_π(s)那π1比π2好是指平均下来更好还是每个状态都不差严格的定义是逐状态字典序策略π优于策略π当且仅当对所有状态s都有v_π(s) ≥ v_π(s)且至少存在一个状态取严格大于。这个定义很苛刻它要求你全盘不落后于对手至少在一个地方领先。最优策略π就是那个对所有其他策略π处处都满足v_π(s) ≥ v_π(s)的策略。为什么不能用所有状态的期望总价值更高这种单指标因为强化学习最终是在状态空间上做决策一个策略可能牺牲一小块区域换取另一块区域的高回报但如果那块被牺牲的区域恰好是智能体经常路过的必经之地实际表现就会很糟糕。逐状态比较能避免这种拆东墙补西墙的陷阱。当然实践中我们常把多个状态的价值汇总成一个标量去做超参调优那是工程上的便利不是理论学习上的定义。1.3 最优策略一定存在吗价值迭代的信心来源定义都立住了还有一个吓人的问题没解决万一这个处处不落后的策略根本不存在怎么办放心在有限MDP、折扣因子γ∈[0,1)、单步奖励有界的条件下最优策略是存在的。这个结论的严格证明要用到贝尔曼最优算子是个压缩映射也就是把所有权价值向量扔进这个算子后距离会按γ的比例缩小因此迭代会收敛到唯一的不动点。这个唯一不动点的视角极其重要。它意味着最优价值函数v是唯一的不管你用什么算法去逼近最后收敛到的都是同一个值函数但最优策略不唯一多个策略可以共享同一个v。记住这个区分后面好多疑惑都会迎刃而解。2. v*(s)与q*(s,a)两块基石的关系与直觉价值函数分两种状态价值v_π(s)和动作价值q_π(s,a)。到最优这里对应的就是最优状态价值v*(s)和最优动作价值q*(s,a)。初学者容易犯的毛病是只盯着v*看动手做决策时才发现还要算动作。所以我把这两个定义并排讲并且直接点出它们的分工。2.1 最优状态价值的定义状态本身值多少钱最优状态价值v*(s)是指在状态s下如果之后每一步都采用某种最优策略智能体能拿到的期望折扣回报最大值。写成公式就是v*(s) max_π v_π(s)注意右侧的max是对策略π做的不是对动作做的。这个定义看起来像废话但它的潜台词是v*(s)已经隐含了从状态s出发的所有后续决策都达到最优这件事。所以它描述的不是这一步怎么走而是站在这块地皮上按最聪明的走法未来一共能折现出多少钱。2.2 最优动作价值的定义决策才是终极需求最优动作价值q*(s,a)是指在状态s下先执行动作a然后之后每一步都采用最优策略所能拿到的期望折扣回报最大值q*(s,a) max_π q_π(s,a)q*(s,a)比v*(s)多了一个维度——动作维度。当智能体真的站在决策关口时它需要比较的是如果在s做了a未来最好能拿多少这个数值只能从q里读出来。v再好也只是把所有动作的最优结果打包成了状态的价值拆包时你仍然需要q*。2.3 两个价值函数互为表里一组互相嵌套的公式这两个定义不是孤立存在的它们之间有非常干净的递归关系v*(s) max_a q*(s,a)q*(s,a) R(s,a) γ · Σ_{s} P(s|s,a) · v*(s)把第二条式子代进第一条就得到完整的贝尔曼最优方程v*(s) max_a [ R(s,a) γ · Σ_{s} P(s|s,a) · v*(s) ]这组公式的直观含义是状态s的价值等于先选一个让当前回报和未来价值总和最大的动作a后面的所有状态全部继续按最优方式接续。第一式说的是决策第二式说的是动作之后的后果。打个比方v*(s)像一个路口的含金量q*(s,a)像从这个路口选某条岔路的含金量。路口含金量的最准估计就是挑所有岔路里最值钱的那条而一条岔路的含金量又是这条路通向的下一个路口的含金量再打折过来的。一环套一环最后就套出了整个地图上每个点的价值。3. 贝尔曼最优方程把最优写进递推贝尔曼最优方程是整个策略搜索的核心。它的地位类似普通贝尔曼方程但多了一个关键动作取最大化。这一章我把它拆开讲顺便回答一个很多人的疑问——为什么这个方程能保证最优性。3.1 与普通贝尔曼方程的差别max放在哪一步普通贝尔曼方程描述的是某一个给定策略π的价值v_π(s) Σ_a π(a|s) [ R(s,a) γ · Σ_{s} P(s|s,a) · v_π(s) ]这里动作是通过策略π(a|s)做加权平均不需要挑最好的动作只需要按策略的概率把各种后果平均掉。贝尔曼最优方程则不同它不再有任何策略参数v*(s) max_a [ R(s,a) γ · Σ_{s} P(s|s,a) · v*(s) ]差异一眼就能看出来普通方程是给定策略平均所有动作的后果最优方程是比较所有动作选出使总价值最大的动作。这个max就是最优二字的数学化身。如果环境是随机的注意max必须放在期望外面也就是先对每个动作分别算奖励未来折扣价值的期望再从这些期望值里取最大顺序反了就会出大问题。3.2 最优子结构为什么局部最优能拼出全局最优贝尔曼最优方程之所以成立靠的是最优子结构一个从s出发的最优轨迹拆成第一步动作a和剩余轨迹两段后剩余轨迹必须也是从s出发的最优轨迹。这不像一句废话吗但这是必须验证的性质不是白给的。如果剩余轨迹不是最优那一定存在另一条从s出发、价值更高的走法把它接到第一步后面整条轨迹的价值还会更高这就和原轨迹是最优矛盾。所以最优性的积木是有可组装性的。这个性质和最短路径问题里的松弛条件是同一个原理理解了它后面价值迭代能收敛的原因也就理解了。3.3 通勤路线类比每个岔路口都先查最值用生活场景类比一下。假设你每天开车上班目标是让通勤时间折现后的总省时最大。你站在一个路口时不需要把到公司的所有路线都从头到尾列一遍只需要做一件事对每条岔路问走这条路到下一个路口要多久加上从下一个路口按最优方式开到公司的省时哪个总和最小。你选最小的那条。这个最小总和就是这个路口的最优价值。关键点在于你选岔路时依赖从下一个路口到公司的最优省时而那个数值又由下一个路口的岔路继续递归下去。这就是典型的动态规划。贝尔曼最优方程做的就是这回事只不过把省时换成了期望折扣回报把下一个路口换成了后继状态s。3.4 从方程到算法方程解出来就是最优价值贝尔曼最优方程是一个关于v的非线性方程组——非线性正来自那个max。对这个方程组我们可以用迭代法求解也就是所谓的价值迭代。它的思路朴素得惊人先猜一个v(s)初值然后反复套用最优方程右侧的更新公式去刷新每个状态的价值更新的过程会越刷越接近真正的v。为什么不是一次解出来因为v*出现在等式两边数学上叫不动点问题迭代式地逼近是实际可行的路径。4. 从最优价值到最优策略贪心提取的底气这一章回答一个实际动手时绕不开的问题假设我已经求出了v*(s)或者q*(s,a)策略到底怎么拿出来答案是一个字贪。4.1 从q*(s,a)直接取argmax最干脆的路径如果手里有q*(s,a)那最优策略几乎不需要思考π*(s) argmax_a q*(s,a)每个状态直接把动作价值最大的动作选出来。因为q*(s,a)已经把做了a之后未来最优回报算清楚了所以当前步最贪、未来又最优整体就是最优。这就像你已经把所有岔路的全程导航耗时都算好贴在了路牌上到路口照着最小耗时的岔路开就完事。4.2 只有v*(s)时先给状态打包动作价值再贪心很多算法求解的是v*(s)比如价值迭代直接维护价值表。这时要提取策略需要先把v*变成q的估计q*(s,a) ≈ R(s,a) γ · Σ_{s} P(s|s,a) · v*(s)然后照旧取出argmax。注意这里绕了一步如果环境转移概率P和奖励R都是已知的模型已知这一步就是精确计算不存在近似误差如果是模型未知的环境就得靠采样的隐式估计了那是强化学习后面的故事。4.3 为什么贪心不会短视策略改进定理的底气有人说贪心是最容易目光短浅的决策方式放到这里怎么反而成立呢因为这里的贪心对象不是眼前的即时奖励而是当前奖励后继状态的最优价值。后继状态的v*已经把所有未来收益都折现汇总进去了相当于远见被打包进了一个值里。你对这个值贪本质上是在对全时间跨度的最优化做出选择不是短视。策略改进定理说得更严格对任意策略π如果按某个策略π在每个状态都选择使q_π(s,a)最大的动作那么π比π在所有状态下都不差即v_π(s) ≥ v_π(s)。正因为每次贪心改进都能保证价值不下降从一个任意策略出发反复贪心改进最终会被顶到一个不可能再改进的策略——那就是最优策略。这个循环往复的过程就是下一章要讲的策略迭代。5. 两条求解路线策略迭代与价值迭代以及一个3×3网格实例模型已知的动态规划类方法里最经典的两套算法是策略迭代和价值迭代。它们不是互斥的后者经常被理解成前者的一种极限情况。这里用同一个3×3网格世界实例把两条路线的行为差异展现出来。5.1 策略迭代先评估后改进一条龙逼近策略迭代的思路特别像团队管理先定一套方案评估这套方案的效果然后针对每个环节做改进改进之后再评估直到方案不再变化为止。伪代码如下随机初始化策略π。重复 a. 策略评估对当前π求v_π一般通过反复应用贝尔曼方程普通版完成 b. 策略改进对每个状态s令 π(s) argmax_a [ R(s,a) γ·Σ P(s|s,a)·v_π(s) ] c. 如果π与π在所有状态一致则停止否则π ← π继续循环。策略评估那一步需要最多计算量因为它要做一轮完整的贝尔曼备份直到价值表收敛策略改进则是把v_π当作输入产出一个新的确定性策略。两者交替推进在有限MDP下一定能终止到最优策略。5.2 价值迭代把评估砍短让改进自己冒出来价值迭代是更精简的路线它不维护显式策略只维护一张价值表反复套用贝尔曼最优方程初始化v(s)0任意状态均为非终止状态。重复 a. 对每个状态s更新 v_new(s) max_a [ R(s,a) γ·Σ P(s|s,a)·v_old(s) ] b. 计算变化量δ max_s |v_new(s) - v_old(s)| c. 如果δ θ停止否则v_old ← v_new继续。最后利用收敛的v*再用argmax提取策略。从策略迭代的视角看价值迭代相当于只做了一步策略评估就立刻转去改进省略了让评估彻底收敛这一环节。这样做依然收敛正是贝尔曼最优算子压缩映射性质带来的红利。5.3 3×3网格世界手算价值迭代前几轮看伪代码容易犯困我拿一个极简环境走一遍。考虑3×3网格状态编号如下(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(2,2)目标在(2,2)。到达目标并执行任意动作后获得1奖励过程结束其余转移奖励为0。动作集为上、下、左、右环境确定性很强撞到边界就原地不动。折扣因子取γ0.9。初始时所有状态价值v0。第一轮价值迭代后只有(1,2)和(2,1)的值变成1它们是能一步到达目标的两个邻居其他状态一步够不到目标价值仍为0。第二轮价值开始向更外围扩散从(0,2)向下能到(1,2)且(1,2)上一轮价值为1所以(0,2)更新为0.9从(1,1)向下能到(2,1)、向右能到(1,2)两个方向都通向价值1于是(1,1)也变0.9从(2,0)向右能到(2,1)同样变0.9。而(1,2)、(2,1)自己因为可以直接拿1奖励价值保持在1。继续迭代第三轮时(0,1)和(1,0)会变成0.81第四轮(0,0)变成0.729。整个过程就像目标位置的价值涟漪向外扩散每往外扩一格价值就被γ打了一次折扣。迭代轮次(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)第1轮00000101第2轮000.900.910.91第3轮00.810.90.810.910.91第4轮0.7290.810.90.810.910.91收敛后每个状态的价值就是这个表格里的数值。可以看到到目标的步数越多价值越低一步邻居是1两步邻居是0.9三步邻居是0.81四步步长是0.729完美符合γ的幂次折算。最终策略也很直观每个状态指向能让价值最大的方向。例如(1,2)向下走直接进目标(0,2)向下走到(1,2)(1,1)向下或向右都可以——注意价值相同的时候最优动作不唯一这说明最优策略不是孤本而是存在一族等价策略它们的v*完全相同。5.4 复杂度与适用场景对比策略迭代的优点是收敛轮数通常很少缺点是每一轮里的策略评估要完整迭代多次价值迭代的优点是实现简单、每轮开销小缺点是可能要迭代很多轮才能让远距离状态的价值传到位。维度策略迭代价值迭代是否维护策略显式维护并反复改进不维护策略只维护价值表每轮成本较高完整策略评估较低一次贝尔曼最优备份收敛轮数通常较少通常较多适用场景状态空间小、模型已知状态空间较大、模型已知或需配合近似实际工程里很少有人会把策略评估跑到完全收敛再去改进常见的做法是限制评估步数形成截断策略迭代价值迭代只是截断到一步的特殊情况。理解了这个谱系你就不会把它们当成两个毫无关联的孤立算法。6. 收敛判据与实战中反复踩到的几个坑算法框架背熟了不等于写出来能跑。下面几个问题是我在实际写动态规划类求解器时遇到过、也看过别人踩过的列出来当检查清单用。6.1 停止条件与θ取值太苛刻是自虐价值迭代的停止条件是最小状态价值变化量δ θ。θ取多少教科书经常写1e-4或1e-6初学者照着抄没毛病但要注意θ越小迭代越多然而对策略的影响往往微乎其微。很多时候价值还没完全收敛策略早就稳定了。你可以每隔若干轮对比一下当前策略如果策略连续N轮没变就可以提早收工。我个人的习惯是任务对策略精度要求高时用θ1e-4要求策略能跑起来时用θ1e-3同样能拿到可用策略速度却快不少。6.2 折扣因子γ的取舍价值迭代的隐形调速器γ越接近1远期奖励越值钱价值迭代需要传到更远距离的状态迭代轮数会显著增加。反过来γ太小比如0.5多数状态的远期价值会迅速衰减迭代很快收敛但策略会显得短视。这个参数千万不要一开始随便选要回到问题本身你的任务的合理决策视野是多长如果每轮决策的间隔很小而任务周期很长γ通常要取0.99甚至更高只有在单步奖励主导的场景下才适合把γ调低。6.3 同步更新被写成异步更新结果常常也能跑但解释要清楚价值迭代的经典写法是基于上一轮价值表v_old做快照然后统一更新所有状态得到v_new。但很多代码为了省一份数组会写成就地更新按顺序更新状态s时直接用邻居的最新值。这种异步更新通常收敛更快但数学上依赖的论证和同步版本不同。如果你在对比实验最好先确认自己写的是同步还是异步因为这两者的收敛曲线并不完全可比。6.4 随机转移下的max位置最常见的隐蔽错误如果环境是有随机性的比如智能体原本想向右走结果有0.2的概率滑到下方计算q(s,a)时必须把转移概率P(s|s,a)加权求期望。问题出在哪里有些新手会把max作用在单个后继状态上写成max_s[r γv(s)]这是错的。正确做法是先固定动作a对rγv(s)按所有后继s的概率做加权平均得到一个唯一的期望值再对所有动作a的期望值取max。顺序一旦颠倒策略会严重高估那些低概率高回报的路径实际表现会很差。顺手给一个Python风格的价值迭代核心循环方便复刻theta 1e-4 gamma 0.9 V {s: 0.0 for s in states} while True: delta 0.0 new_V dict(V) for s in non_terminal_states: max_q float(-inf) for a in actions: expected_value 0.0 for s_next, prob in trans_prob[s][a].items(): reward rewards[s][a][s_next] expected_value prob * (reward gamma * V[s_next]) max_q max(max_q, expected_value) new_V[s] max_q delta max(delta, abs(new_V[s] - V[s])) V new_V if delta theta: break这里在循环外建了一个new_V快照再做整体替换确保每一步基于上一轮价值表更新避免异步更新带来的语义混乱。6.5 无终止状态且γ1的组合永远等不到停止最后说一个最经典的死循环场景环境没有终止状态每个状态都能无限转移同时你把γ设成1。这种情况下累积回报会趋于无穷贝尔曼最优方程没有有限解价值迭代根本收敛不了。报错可能表现为δ值顽固地卡在一个水平下不去或价值表越刷越大。遇到这种异常第一反应就该检查环境里有没有终止状态以及γ是不是小于1。两者至少满足一个动态规划才有意义。把上面这些细节都处理掉一张价值表、一套策略也就真正能落到实际任务里了。理论上的Bellman最优方程和工程上的收敛判据说到底都是帮我们在有限计算资源和无限规划视野之间找平衡这恰恰是强化学习最需要动手体会的部分。