当前位置：首页 > news >正文

RL 基础（CH3，动态规划）

news 2025/7/4 18:00:53

注：本文仅用于自学习笔记备忘，不做任何分享和商业用途。

主要参考资料：

蘑菇书EasyRL
A (Long) Peek into Reinforcement Learning | Lil'Logs
David Silver Curse

1 Introduction
2 Policy Evaluation
3 Policy Iteration
4 Value Iteration
5 Extensions to Dynamic Programming
6 Contraction Mapping

3.1 动态规划

动态规划的基本特点：最优子问题的递归和重复利用。MDP问题动态规划问题的特征。

用动态规划来做规划planning，一般有预测和控制两种：预测就是基于一个策略π去输出未来的回报（value function，可以是state value，也可以是state-action value），一般来说我们希望回报越高越好。控制就是输出最优的value function，根据上一节课的内容，我们可以得到最优的控制策略。

3.2 Iterative Policy Evaluation

如果我们想要评估一个给定的policy π（根据ch2中，policy的定义，我们现在可以知道在任何state下，采取action a的概率），就去评估基于该策略下的state value，来看这个策略好不好。

3.2.1 一个Grid World的例子，用policy evaluation来评估一个random policy

注意，这个例子中，用的policy是random policy，我们可以看到，在random policy下，通过policy evaluation方法，左侧的values会逐步收敛。实际上，基于这个收敛的values，我们很容易得到一个比random policy更好的policy，就是在右侧显示的箭头（注意看，实际上，并不需要等values完全收敛后才能得到optimal policy，迭代几步以后的策略就已经变好了）

3.3 Policy Iteration

上文中我们已经提到了如何改进一个policy，现在来正式看一下：只需要循环进行evaluate和Improve，就可以确保策略收到连一个最优值。

从一个π开始，首先我们用3.2 Policy Evaluation方法，去评估处这个策略π的Value function V，然后基于V，用greedy的方法来Improve π，什么是greedy的方法呢？就在任何一个state下，用最优的状态value来决定action，更新policy（比如前面gridworld例子中，就是前后左右移动，或者保持不动等。），在当前value state评估下，这样π' 一定比π要更好一些。

3.3.1 租车调度的简单例子：

右下角是V4的value function，实际上在每一个状态下，都有这样一个value function。题目大致是说有2个租车点，最多可以放20辆车用于租用；两个地点A/B之间可以进行夜间调度，最多可以调度5辆车，A给B或者B给A。一开始的策略就是不调度，然后用policy Evaluation算一个V0，基于这个V0，可以greedy imporve policy，得到新的policy π1，再用policy Evaluation算V1，以此类推。最后当π*不再变化时，就是收敛到optimal policy。

接下来讨论一下如何优化policy Evaluation？是不是每次都需要收敛呢？其实并不一定，如果k=1，也就是说每Evaluation Iteration一次就停止，然后马上进行policy Improve，就和我们后面要讲的value iteration方法一样了。

3.4 Value Iteration

回顾一下前面提到的policy Evaluation方法中，我们更新V函数用的是期望，就是用上一个k时刻的我所有的后继状态s’的values+reward的期望，代表平均的return估计，来作为我下一个k+1时刻的value。

在Value Iteration方法中，我们采用one-step lookahead方法，这个是核心的不同点，用后继节点的最优value来代替我的最优value，所以叫lookahead，往前看一看。

正式定义Value Iteration如下：和policy Iteration的另一个区别是，中间并不需要显式地有policy，只需要一直value迭代下去，就能得到V*（state value function），然后就可以得到最优的policy，（见前面3.1）

3.4.1 一个例子：计算网格中的最短路径。

V1是初始状态，终点是左上角，每走一步R=-1。用value Iteration，去刷新V 。从结果上看，就好像是一步一步从终点倒着去刷新最短路径，因为离终点1步的state只需要1步，2步的state需要2步，以此类推。最后就可以刷新出每一个state的shortest path。

3.5 总结

其中提到可以用于action-value function，我们回顾一下ch2中学到的Bellman Optimality Equation for Q∗ ，和上面的Value Iteration对比下，就也在等式右边加上max就好了，one-step lookahead，看下k时刻我下后继节点的最优情况，然后作为k+1时候我的value。