学习资料：bilibili 西湖大学赵世钰老师的【强化学习的数学原理】课程。链接：强化学习的数学原理 西湖大学 赵世钰

---

一、值迭代算法

值迭代算法主要包括两部分。

第一部分：policy update。给定 $v_k$ ，求解 $max$ 最优化问题，其实就是求 $\pi$ 。
第一部分：value update。根据求解出来的新的策略 $\pi$，即 ${\pi }_{k+1}$ ，把新策略代入到式子中，求出新的state value $v_{k+1}$。

下面详细看policy update的过程。首先要对每一个状态s，求出其 $q_k(s,a)$ 。因为各变量都是已知的，所以能很方便地求出结果。然后，对于每一个状态s的 $q_k(s,a)$ ： $q_k(s,a_1)$、 $q_k(s,a_2)$、 $q_k(s,a_3)$…找出其中最大的 $q_k$，选择对应的动作a作为策略 ${\pi }_{k+1}(a|s)$ 。所以这种策略是一个确定性的策略，且是一个贪婪的策略，只会寻求最大的 $q$ 值。

下面详细看value update的过程。类似地，要对每一个状态s，求出其 $q_k(s,a)$ 。因为各变量都是已知的，$v_k(s^{\prime })$也是已知的（要么是刚开始赋值的，要么是前一轮算出来的$v_{k+1}(s)$拿过来继续用），所以能很方便地求出结果。在上一步已经求出来最优的 ${\pi }_{k+1}(a|s)$ 了，所以直接代入相应的值，就能得出 $v_{k+1}(s)$。因为 ${\pi }_{k+1}(a|s)$ 只有在q值最大的情况下才等于1，在其他情况下都等于0，所以 $v_{k+1}(s)$直接就等于 $\underset{a}{\max }{q}_k(s,a)$。

下面是值迭代方法的伪代码。一开始有一个初值 $v_k$，当 $v_k$还没有收敛（ $v_k-v_{k-1}$的值不够小）的时候，就进行下面的步骤。对于第k次迭代，对于状态空间中的每一个状态s，算出其 $q_k(s,a)$ ，再选出这个s对应的最好策略（policy update）、更新值函数（value update）。

接下来将结合下面的例子来讲解该如何使用值迭代算法。用值迭代算法进行策略搜索的时候，需要能根据给出的 $v(s)$，求出对应的 $q(s,a)$。因此作者设计了下面这个表格q-table，这样方便我们去查找 $q(s,a)$。

当k=0时，设置 $v_0$都为0（这个值可以随意设置）。根据q-table值求出 $q(s,a)$。在step 1：policy value中，对每一个s，选出让其 $q(s,a)$ 最大的动作a，作为k=1的策略。然后，对于每一个状态s，根据式 $v_{k+1}(s)=\underset{a}{\max }{q}_k(s,a)$ ，求出新的state value $v_{k+1}(s)$。k=0时，解出来的策略如上图(b)所示，此时对于状态$s_2$、$s_3$都已经达到最优，对于状态$s_1$，还没有达到最优。

当k=1时，使用相似的方法进行计算，计算结果如上上图（c）所示，可以看出，此时已经是最优策略。还可以继续进行迭代，直至 $v_k$ 收敛为止。

二、策略迭代算法

1. 策略迭代算法介绍
算法起初有一个策略 ${\pi }_0$，后续将在step1、step2不断迭代的过程中优化这个策略。
step1：policy evaluation. 给定一个策略后，求解贝尔曼公式，得到状态的state value $v_{{\pi }_k}$。（在第2课中提到过求解方法，接下来也会继续讲到）
step2：policy improvement. 根据刚刚算出来的state value $v_{{\pi }_k}$，计算新的策略 ${\pi }_{k+1}$。
然后把新的策略 ${\pi }_{k+1}$ 再代入到step1中，计算新的state value，如此不断迭代。

策略迭代的过程可以用下面这个序列表示。初始策略 ${\pi }_0$，经策略评估后得到state value $v_{{\pi }_0}$，使用 $v_{{\pi }_0}$ 进行策略提升得到新的策略 ${\pi }_1$，随后使用新策略 ${\pi }_1$经策略评估后得到state value $v_{{\pi }_1}$……如此循环往复。下面，我们将针对策略迭代算法回答四个关键问题。

Q1：在策略评估（policy evaluation）中，如何通过解贝尔曼方程得到state value $v_{{\pi }_k}$？
在策略评估中，策略 ${\pi }_k$ 已知。给定策略 ${\pi }_k$ ，求解贝尔曼公式的方法在前面已经介绍过。方法一是closed-form solution，但因为该方法涉及到矩阵求解，所以很少使用。方法二是iterative solution，先初始化一个 $v_{{\pi }_k}^{(0)}$，根据当前的策略 ${\pi }_0$计算出 $v_{{\pi }_k}^{(1)}$，然后把 $v_{{\pi }_k}^{(1)}$拿到等式右边继续根据当前的策略 ${\pi }_0$计算 $v_{{\pi }_k}^{(2)}$，如此不断迭代。当j足够大的时候， $v_{{\pi }_k}^{(j)}$ 趋向于$v_{{\pi }_k}$。 所以，在policy evaluation中使用iterative solution，相当于在一个大迭代中嵌套了一个小迭代。

Q2：在策略提升（policy improvement）中，为什么新的策略 ${\pi }_{k+1}$ 一定比旧策略 ${\pi }_k$ 好？
这个问题可以证明，证明过程见书。

Q3：为什么迭代算法能最后求出一个最优策略？
在上个问题中已经提到，策略提升过程中，得到的新的策略 ${\pi }_{k+1}$ 一定比旧策略 ${\pi }_k$ 好。所以直观上来看，策略一定会被优化得越来越好。具体证明见书。

Q4：值迭代算法和策略迭代算法的关系是什么？
值迭代算法和策略迭代算法是truncated policy iteration算法的两个极端。下一节会讲。

2. 策略迭代算法的具体实现
在policy evalutaion过程中，从贝尔曼公式的elementwise form可以看到，${\pi }_k(a|s)$ 是一开始给定的，$v_{{\pi }_k}^{(j)}(s^{\prime })$表示在某一次policy evalutaion中估计出来的第j次迭代时的state value，其他变量也都是已知的。所以可以算出 $v_{{\pi }_k}^{(j+1)}(s^{\prime })$，然后把算出来的 $v_{{\pi }_k}^{(j+1)}(s^{\prime })$再代入到等式右边算出 $v_{{\pi }_k}^{(j+2)}(s^{\prime })$……如此循环迭代，最终求出这次policy evaluation过程中的 $v_{{\pi }_k}(s^{\prime })$。

在policy improvement过程中，根据刚刚算出的 $v_{{\pi }_k}(s^{\prime })$ ，可以求出 $q_{{\pi }_k}(s,a)$，然后再从 $q_{{\pi }_k}(s,a)$ 选择一个最大的q对应的动作作为下一个策略。

下面是策略迭代的伪代码。

下面是一个简单的例子，阐述了策略迭代算法的计算过程。下图中蓝色方格表示target area，初始策略：白格往左走，蓝格往左走。

首先进行第0次迭代。在策略评估过程中，有两种方法可以求出 $v_{{\pi }_0}(s)$。第一种方法，当情况比较简单时，先根据最初给定的${\pi }_0$列出贝尔曼公式，求出最开始的state value $v_{{\pi }_0}(s)$。第二种方法，当情况比较复杂时，使用迭代的方法求解。假设 $v_{{\pi }_0}^{(0)}(s)$都等于0，然后根据贝尔曼公式写出相应的式子求解，一步步迭代，直至得到最终结果。

下面进行策略提升过程。本质上是要计算 $q_{{\pi }_k}(s,a)$ 。对于每一个状态s，从 $q_{{\pi }_k}(s,a)$ 中选择值最大的q，找到其对应的动作值a，作为下一个策略。可以发现，经过一次迭代，该策略已经达到最优了。

下面是一个更加复杂的例子。下图绘制的是，从一开始一个随便给的策略${\pi }_0$逐渐优化到${\pi }_{1}0$。可以发现策略从很差，逐渐变化到最优。从中还可以发现，接近目标的状态，其策略会先变好。比如：forbidden area都比较接近target area，可以发现它们在${\pi }_1$就变好了，但是此时有的白色格子的策略还是很差。

三、截断策略迭代算法

下图展示了policy iteration和value iteration的简单思路。如果有遗忘，可以复习一下前面的笔记。

这两个策略实际上非常类似，都是在$\pi$和$v$之间不断迭代。但两者之间也存在重要差异。

下面这个表格比较了policy iteration和value iteration。
在第（1）步中，policy iteration指定了一个初始策略${\pi }_0$，value iteration暂时还没有任何操作。
在第（2）步中，policy iteration根据初始策略${\pi }_0$计算出state value $v_{{\pi }_0}$。value iteration初始化了一个state value，不过为了比较两个算法，这里强行让初始化的state value $v_0=v_{{\pi }_0}$。
在第（3）步中，policy iteration根据刚刚算出的state value $v_{{\pi }_0}$进行策略提升，算出来一个新的策略。value iteration根据刚刚初始化的$v_0$，也求解出一个新的策略。截止到目前，value iteration和policy iteration所执行的操作都是完全一样的。
在第（4）步中，两个算法出现了不同。policy iteration在求得新策略 ${\pi }_1$的基础上，计算state value $v_1$。value iteration 在已知 $v_0$ 和 ${\pi }_1$ 的基础上，仅仅求解一步，就得到了 $v_1$，并且用这个 $v_1$再去下一步算新的策略。

下面我们来详细看一看第（4）步中的不同。对于policy iteration而言，需要求解贝尔曼公式 $v_{{\pi }_1}=r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}$。这个求解过程是一个迭代的过程，需要先初始化一个 $v_{{\pi }_1}^{(0)}$，计算出 $v_{{\pi }_1}^{(1)}$，然后把 $v_{{\pi }_1}^{(1)}$代入到等式右边，继续算出 $v_{{\pi }_1}^{(2)}$……理论上，一直迭代无穷多步，才能算出 $v_{{\pi }_1}$，随后进入到第5步的计算。然而，对于value iteration，只需要在第（4）步中算1次，就能进入到第5步的计算中了。

所以，可以很自然地想到，可以设计一个中间步骤j，使得在迭代到第j次就停止。这就是truncated policy iteration。所以说，policy iteration和value iteration是truncated policy iteration的两个极端。一般来说，在实际实现中，是不会用policy iteration的，因为需要迭代无穷多步。我们经常做的就是判断$v_{{\pi }_1}^{(j)}$和$v_{{\pi }_1}^{(j+1)}$的差是否小于一个给定的阈值。

下图是truncated policy iteration算法的伪代码。和policy iteration的实现几乎一致，区别在于，truncated policy iteration并未判断state value是否收敛，而是判断迭代的次数j，j是否小于 $j_{truncate}$。

四、本节课内容summary