gridworld.py

Policy Evaluation.ipynb

5. 策略提升(Policy Improvement)

策略提升定理

6. 策略迭代(Policy Iteration)

7. 策略迭代代码示例

8. 价值迭代(Value Iteration)

9. 价值迭代代码示例

10. 通用策略迭代(Generalized Policy Iteration/GPI)

简介

动态规划是一种算法，对于简单的 MDP 问题可以用它来求解最优解。但是实际问题很少能用到这种算法，因为它的假设很难满足以及它计算复杂度太高了。不过学习这种算法依然很有用处，因为后面介绍的方法都想达到动态规划一样的效果，只不过它们能降低计算复杂度并且在非理想的环境下也可以使用。

这一节我们假设 MDP 是有限的，包括状态、行为和 Reward，并且环境完全由 (′,|,) 确定。如果读者学习过计算机的算法课程，可能也会学到动态规划算法，它的基本思想是：一个"大"的问题的最优解，可以分解成一些小的问题，并且把小问题的的最优解的组合起来得到大问题的最优解。本书后文很多算法都是动态规划算法。

使用动态规划来解决强化学习问题的核心是使用价值函数来搜索好的策略。如果有了最优价值函数（不管是状态价值函数还是状态价值函数），我们就可以用它来计算最优的策略。最优价值函数满足如下的贝尔曼方程：

我们来理解一下这个公式，在状态 s 下最优的价值是什么呢？我们遍历所有可能的行为 a，得到Reward 值 +1 然后进入新的状态 +1 。这个过程由 (′,|,) 确定，所以加一个 。当 t+1 时刻我们处于 +1 时，我们仍然要遵循最优的策略，所以第二项是 ∗(+1) 。把 根据期望的定义展开成求和就得到第二个等号。Q 的贝尔曼方程也是类似的：

我们同样可以这样解读：在状态 s 采取 a，Agent 会得到 +1 和进入状态 +1 ，在这个状态时我们有很多选择，但是我们要选择最大的那个 a’。而动态规划就是根据上面的贝尔曼方程来得到迭代更新的算法。

策略评估(Policy Evaluation)

首先我们来计算一个给定的策略的价值函数 () ，这叫策略评估(Policy Evaltuion)，有时我们也把这个问题叫做预测(Prediction)问题。

其中 (|) 是给定策略 时，在状态 s 下采取行为 a 的概率。公式的期望 说明是在策略 下变量 +1 和 +1 的概率。

如果环境的动力系统 ((′,|,) )是完全已知的，而策略 (|) 也是已知的情况下，我们可以通过线性方程直接解出 () 。因为假设状态 s 有 n 种可能，那么就是 n 个变量，n 个等式的线性方程，可以证明，如果 <1 ，则方程有唯一解。这是一个线性代数的问题，但是这里我们会介绍一种迭代算法，这和梯度下降的思路有一些类似。因为迭代算法更容易推广到动态规划之外的算法，所以我们需要学习这种方法。下图是算法的伪代码：

图：策略评估算法伪代码

这个算法过程如下：首先把所有的 0() 都初始化成0，然后根据 0 计算 1 ，…，一直继续下去直到收敛。根据 () 计算 +1() 的公式如下：

这个迭代算法的证明本书从略，有兴趣的读者可以参考这里。我们可以看一下收敛的时候，+1=，Δ=0 ，那么上面的迭代公式正好就是贝尔曼方程！有了上面的迭代算法，任何给定的策略 ，我们都可以计算出它的价值函数。

策略评估代码示例

接下来我们用代码来实现上面的算法，在介绍具体算法之前，先介绍Grid World。

图：Grid World