基于动态规划的强化学习算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了基于动态规划的强化学习算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基于动态规划的强化学习算法

学习「强化学习」（基于这本教材，强烈推荐）时的一些总结，在此记录一下。

在马尔可夫决策过程 环境模型已知（也就是状态转移函数P、奖励函数r已知）的情况下，我们可以通过 「动态规划」 求得马尔可夫决策过程的最优策略 $\pi^*$ 。

1. 动态规划

对于做过算法题目的同学而言，这个词应该并不陌生，比较经典的「背包问题」就是需要利用「动态规划」。动态规划的思想是：将当前问题分解为子问题，求解并记录子问题的答案，最后从中获得目标解。它通常用于求解「最优」性质的问题。

而求解马尔可夫决策过程最优策略的动态规划算法主要有两种：

策略迭代
价值迭代

2. 策略迭代

「策略迭代」 分为「策略评估」和「策略提升」两部分。

策略评估

策略评估会先设定一个初始状态价值函数 $V^0$，再通过「动态规划」不断更新策略的状态价值函数 $V^{k+1} \leftarrow V^k$，当最大的「 $V^{k+1}(s)$ 与上次的 $V^k(s)$ 的差距」非常小（ $<\theta$）时，就结束迭代。

策略评估的迭代公式可以看作是「贝尔曼期望方程」+「动态规划」。我们可以看看两者的不同：

光说这些还是不容易理解的，我们用实例演示一遍吧。同样以教材中的「悬崖环境」为例：

假设现在有这么一个 $5 \times 4$ 区域的悬崖，我们的目标是要找出从起点到终点的最优策略。我们把每个格子都当成一个状态，也就是说，只要智能体移动了一个格子，就转换了一次状态；并且智能体只能「上下左右」地走（如果将走出范围，就当作原地踏步，即「走到自身格子」），每走一步都是一个动作且往不同方向走的概率是相同的。走到悬崖的奖励我们设为-100，走到正常位置的奖励设为-1，走到终点就直接结束（相当于奖励是0），那么我们可以整理出奖励函数 $r(s, a)$：

可能会有的疑惑：$r(s, a)$ 不是 由状态与动作一起决定 的吗，这里怎么把 $r(s, a)$ 直接放在状态上了？
答：这其实是种简化的表达方式，我们应该这么看：这里的 $r(s, a)$ 指从其它状态（格子）以任意方向走到当前状态（格子）的 $r(s, a)$，只不过因为它们都相同（因为设置的这个环境比较特殊），所以写在了一起。比如下面这个红色小旗所在格子位置上的 $r(s, a)$ 其实是它周围格子走到该格子的 $r(s, a)$：

我们先让初始 $V^0$ 全为0，判定迭代结束的小阈值 $\theta = 0.01$，为了方便，让折扣因子 $\gamma = 1$，而且由于走一步仅能到达一个状态，所以让所有的状态转移概率都为1 ：

根据迭代公式，开始迭代 $V^1$，先以起点的 $V$ 开始：

\[ \begin{aligned} V^1(起) &= \frac{1}{4} \times ((-1) + 1 \times 1 \times(V^0(起上))) + \frac{1}{4} \times ((-1) + 1 \times 1 \times(V^0(起下))) \\ &+ \frac{1}{4} \times ((-1) + 1 \times 1 \times(V^0(起左))) + \frac{1}{4} \times ((-100) + 1 \times 1 \times(V^0(起右))) \\ &= \frac{1}{4} \times ((-1) + 1 \times 1 \times(0)) + \frac{1}{4} \times ((-1) + 1 \times 1 \times(0)) \\ &+ \frac{1}{4} \times ((-1) + 1 \times 1 \times(0)) + \frac{1}{4} \times ((-100) + 1 \times 1 \times(0)) \\ & = -25.75\\ \end{aligned} \]

每个状态（格子）都计算完后，就得到了完整的新的 $V^1$:
然后进行评估，发现 $max\{|V^1(s) - V^0(s)|\} = 25.75 > \theta$，还得继续迭代
重复与2相同的步骤，根据 $V^1$ 求出 $V^2$，又可以得到：
……

总之，在经过多轮的重复迭代后，我们取得了收敛的 $V$，这时就进入到了 「策略提升」 环节。

策略提升

接下来就是调整策略 $\pi$ 了，我们可以直接贪心地在每一个状态选择动作价值最大的动作，也就是：

根据这个调整方式，来看看最终策略提升得到的新的 $\pi^1$:

然而，这还没有结束，如果不满足 $\pi^{k-1} = \pi^k$，那么还需要继续进行策略迭代。如果满足了，那么此时的 $\pi^k$ 就是最优策略、 $V^k$ 就是最优价值。在这里显然 $ \pi^0 \neq \pi^1$，所以要继续。

总结

最后，综合「策略评估」和「策略提升」，得到策略迭代算法（教材中的）：

3. 价值迭代

「策略迭代算法」似乎计算量大了些，既要进行不断迭代 $V$ ，还要迭代 $\pi$，有计算量比较小的算法吗？ 「价值迭代算法」 可能可以满足你的需求，它虽说也要进行 $V$ 迭代，但却只用一轮，而后就直接「盖棺定论」将更改后得到的 $\pi$ 作为「最优策略」了。

它可以看作是：「贝尔曼最优方程」+ 「动态规划」。

可以直接来对比下「策略迭代」与「价值迭代」：

红色框表示的是「$V$迭代」，在这部分不同的是，「价值迭代」直接选取最大状态价值而不是「策略迭代」的期望状态价值；蓝色框表示的是「$\pi$迭代」，「价值迭代」没有对「策略」进一步进行迭代 ~~（所以才叫「价值迭代」嘛~~

虽然很简单，但同样我们也来实操一遍「价值迭代」，同样用到刚刚的「悬崖」环境：

初始化就不提了，直接根据迭代公式，开始迭代 $V^1$，先以起点的 $V$ 开始：

\[ \begin{aligned} V^1(起) &= max\{((-1) + 1 \times 1 \times(V^0(起上)))，((-1) + 1 \times 1 \times(V^0(起下)))， \\ & ((-1) + 1 \times 1 \times(V^0(起左)))，((-100) + 1 \times 1 \times(V^0(起右)))\}\\ &= max\{((-1) + 1 \times 1 \times(0))，((-1) + 1 \times 1 \times(0))， \\ & ((-1) + 1 \times 1 \times(0))，((-100) + 1 \times 1 \times(0))\} \\ & = max\{-1, -1, -1, -100\}\\ & = -1\\ \end{aligned} \]

每个状态（格子）都计算完后，就得到了完整的新的 $V^1$:
同样评估一下是否 $max\{|V^1(s) - V^0(s)|\} > \theta$ ，如有则继续迭代。这里经过7次迭代就达到判定阈值了：
最后同样选取最大动作价值，来更新策略即可。如果动作中有多个「最大动作价值」的动作，则给予等概率。

4. 总结

策略迭代在理论上能更好地收敛到最优策略，但有着比较大的计算量；价值迭代可以通过较少的计算就收敛，但不像策略迭代那样有严格的收敛性保证（可以看看这个数学证明）。只能说各有优劣，具体用哪个还得看实际情况。文章来源地址https://www.toymoban.com/news/detail-837696.html

到了这里，关于基于动态规划的强化学习算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！