爱喝兽奶帝天荒

这个屌丝很懒，什么也没留下！

热门标签

model-free 方法：动态规划法DP(dynamic programing)_model-free统计推断

作者：爱喝兽奶帝天荒 | 2024-08-04 09:38:37

踩

model-free统计推断

的基于模型的强化学习方法需要对模型有完全的认知，也就是：对于强化与学习的五个要素：有限的状态集、动作集、转移函数、奖励函数、衰减折扣都是已知的。在这种情况下，贝尔曼期望方程就可以写成具体的形式。

$V_{\pi}(s)=\sum_{a}\pi(a|s) \left ( R^a_s+\gamma\sum_sp(s'|s,a)V_{\pi}(s')\right )$

$Q_{\pi}(s,a)=R^a_s+\gamma\sum_sp(s'|s,a)\sum_a\pi(a'|s')Q_{\pi}(s',a')$

动态规划法（DP）

1.策略优化构成

当我们要对一个策略进行优化的时候（无论是查表法还是直接改进策略），首先要对当前的策略进行评估，然后根据评估结果改进表格或直接调整策略。

所谓策略评估，就是利用当前策略，求出在当前策略指导下的价值函数。策略改进就是一句某种规律根据评估出的结果对策略进行改进。往复循环直到达到最优策略。

2.贝尔曼最优方程

在训练过程中，什么情况下意味着我们已经得到了最优策略？

我们定义最优价值函数： $V_*=max_{\pi}V_{\pi}(s),Q_{*}=max_{\pi}Q_{\pi}(s,a)$

最优策略（能让价值函数达到最大的策略，且可能不止一个 $\pi_*=argmax_{\pi}V_{\pi}(s)=argmax_{\pi}Q_{\pi}(s,a)$

关于为什么能够使两种价值函数同时达到最大，我的理解是通过之前讲过的公式中线性关系 $Q_{\pi}(s,a)=R^a_s+\gamma \sum_ap(s'|s,a)V_{\pi}(s')$

so， $V_*=max_{\pi}V_{\pi}(s)=V_{\pi _*}(s),Q_{*}=max_{\pi}Q_{\pi}(s,a)=Q_{\pi _*}(s,a)$ ,可以比较容易的推到： $V_{\pi_*}(s)\leq \begin{matrix}max \\ a \end{matrix}Q_{\pi_*}(s,a)$ 。即：只有在某状态下选择最优的动作时，动作价值函数才会与状态价值函数相等，其余小于。在这篇文章中写的比较好：贝尔曼最优方程

最后我们得出最优状态下的贝尔曼期望方程，即贝尔曼最优方程：

此时，我们无论再怎么进行评估与改进，价值函数不会发生变化。此时的策略就是最优策略。

3.策略评估

（1）*矩阵法直接求解策略评估

策略评估任务中，我们的目标就是求给定策略下的价值，即所有状态下，所有动作的动作价值函数已知就完成任务。在贝尔曼期望方程的帮助下，这个问题看起来很容易解决，因为方程描述了状态与状态间的状态价值函数关系，动作与动作间动作价值函数的关系，且价值函数间的关系是线性的。我们可以通过这种关系列出足够解出价值函数的多元一次方程，也就是可以用线性代数的方法求解。以价值函数为例，将价值函数的贝尔曼期望方程写成矩阵形式：

例如方程中的V可以改写为 $V_{\pi}=\begin{bmatrix}V_{\pi}(s^1) \\ V_{\pi}(s^2) \\ V_{\pi}(s^3) \\ ...... \\ V_{\pi}(s^n) \end{bmatrix}$ ,R可以改写为 $R=\begin{bmatrix}R_{s1} \\ R_{s2} \\ R_{s3} \\ ...... \\ R_{sn} \end{bmatrix}$ ,状态转移也写成转移矩阵

通过矩阵计算 $V_{\pi}=\pi(R+\gamma PV_{\pi})$ ,可得解析解 $V_{\pi}=(1-\gamma P)^{-1}R$ 。

但这种方法不适用于具有较多状态的问题，因为涉及到矩阵求逆，这会导致复杂度为 $O(n^3)$ 在状态个数n过大是复杂度过高，计算成本大，所以我们一般不采用这种方法求解MDP的价值函数。

（2）自举法策略评估（bootstrapping）

解析解过于复杂，我们试图创建一个数列，逼近真实的解，获得我们近似的数值解还是根据贝尔曼期望方程，但是是利用自举迭代的方法。

bootstrapping，自举法也称拔靴法，是一种统计工具，具体内容可自行了解。我们要使用的思想就是 用一个估算去更新同类的估算。在贝尔曼期望方程中，我们可以利用迭代前价值函数更新价值函数：

左侧就是本次迭代需要进行更新的价值函数，右侧的价值函数就是在本次迭代前的，上一个版本的价值函数。

下面举一个简单的算例：

在4*4格子中，共有16种状态，如图所示。

给定策略，欲求在策略的指导下每个状态的状态价值函数根据五元组：

状态空间S：s0-s15 ，终止状态为0，15，已知且有限
行为空间A：上下左右（规定如果突破边线则保持原状）已知且有限
转移概率P：一定会转移到我们前进方向下一个格子上已知
奖励函数R：每走一步都会给予-1的奖励已知
衰减系数γ：γ=1 方便计算
而且我们给定策略：每个状态下上下左右走概率相同，都为0.25

求解：根据已知条件，我们的贝尔曼期望方程 $V_{\pi}(s)=\sum_{a}\pi(a|s) \left ( R^a_s+\gamma\sum_sp(s'|s,a)V_{\pi}(s')\right )$

就可以改写为 $V_{\pi}(s)=\sum _a 0.25\times(R(s)+1\times V_{\pi}(s(a)))$ 这里的s(a)指的是在本状态做动作a能够到达的状态。

接下来，我们就需要利用公式对每个状态的v进行迭代。方便展示，我们关注第二行第一列的状态。

在未进行迭代时，依据当前的状态价值无法得出比随机策略更好的策略。

此时进行第一次迭代，具体的做法就是看当前格子（4号状态）在选择不同动作时能够到达的状态，和该状态的奖励R(s)与上一次迭代的状态价值函数V(s)：

向上->state0,R(s)=-1,V(s)=0（k=0表格中获取）
向右->state4,R(s)=-1,V(s)=0
向下->state8,R(s)=-1,V(s)=0
向左->state4,R(s)=-1,V(s)=0

获得更新所用数据后，紧接着利用公式更新： $V_{\pi}(state4)=0.25\times(-1+0)+0.25\times(-1+0)+0.25\times(-1+0)+0.25\times(-1+0)=-1.0$

对每一个状态都进行如下操作后，我们得到更新后的价值函数表格：

类似于上一次迭代，进行第二次迭代，利用的是第一次迭代后得出的数据：

向上->state0,R(s)=-1,V(s)=-1(V(s))从上一个k=1表格中获取）
向右->state4,R(s)=-1,V(s)=-1
向下->state8,R(s)=-1,V(s)=-1
向左->state4,R(s)=-1,V(s)=-1

更新： $V_{\pi}(state4)=0.25\times(-1+0)+0.25\times(-1+(-1)+0.25\times(-1+(-1)+0.25\times(-1+(-1))=-1.7$

以此类推，直到收敛后得到该策略（每个方向走的概率都是0.25）所对应的状态价值函数

我们就利用自举法完成了一次策略评估。

4.策略改进

如何参考评估的结果，改进自己的策略，从而获得一个相比原策略更加优秀的策略是这一部分研究的内容。

我们考虑确定性策略，即在每个状态下只有一种动作是最优的。凭借这个，就可以利用贪婪算法，选择状态下动作价值函数最高的一个动作作为新的策略。

当对于所有状态s来说，有 $v_{\pi}(s) = v_{*}(s)$ 时，策略就是最优策略。

5.策略迭代：策略优化的全过程

策略优化往往是策略评估与策略改进的重复迭代直到达到终止条件。

1.传统的策略迭代

先进行策略评估直到每次评估迭代价值函数的变化量小于一个定值

再通过贪婪策略改变原先的策略，再对新的策略进行策略评估……循环直到策略不再发生改变

传统的策略评估很容易理解，但是在策略迭代中还嵌套着策略评估的迭代，导致过于复杂。大佬们发现：在任意时刻终止策略评估的迭代，然后根据终止时的价值函数更新策略在进行同样操作，结果不变。根据这一种特性，提出改良策略迭代和价值迭代。

2.改良策略迭代和价值迭代

当我们提前终止策略评估，传统策略迭代就变成改良策略迭代。

尤其是我们只进行一次策略迭代后就进行策略改进时，这种方式我们称作价值迭代。在价值迭代中，过程中出现的价值不与策略对应，显示策略没有出现，但是策略收敛后得出的结果和传统价值迭代的策略与价值相差不大。

策略评估模拟：

REINFORCEjs: Gridworld with Dynamic Programming (stanford.edu)

斯坦福大学的方块世界可以用来进行仿真。

可以自行调节奖励函数

得到每个状态的最优动作。

小结：本章讲解了model-based方法的动态规划法，可以进行策略评估（可提前终止）与策略改进（贪婪策略）直到策略收敛。

还有很多DP的变种，比如异步动态规划，优先骚婊，实时动态规划，采样备份等等技巧，就不一一展开了，感兴趣可自行搜索。model-based方法还有很多，我了解不多，就不多说

因为基于模型的强化学习算法对于模型的已知要求很高，在现实应用中能够达到的条件苛刻。从下一章开始，我将介绍model-free方法——无需知道环境，需要探索获得信息的强化学习方法。

大家也可以关注bilibili：极乐寺大住持，里面有相关的视频讲解。如果对大家有帮助的话还请点赞。感谢鼓励。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/927206