强化学习数学基础（2）

回顾

在上一章节贝尔曼最优等式章节中，我们引入contraction mapping theorem证明了贝尔曼最优等式中解的存在性、唯一性以及求解算法；

其求解为迭代式算法： ，在上一章节中我们也给出了求解步骤如下：

1、对于任一 ，估计

2、对于任一 ，计算

3、根据 greedy policy，得到 ，其中

4、计算

其实以上求解步骤，就属于我们接下来将的Value Iteration求解算法；

Value Iteration

下面以一种更术语的方式描述该算法，其matrix-vector形式如下：

能够分解为如下两步：

Step 1: policy update.这一步用于求解：

，其中 是我们给的一个初始值， 使用贪心策略求解；

Step 2: value update.

（需要注意 并不是state value，因为其并不一定满足bellman equation，为什么强调这点？这也是value iteraion与我们接下来要讲的policy iteration的主要区别，此处按下不表）

matrix-vector更数学，其具体求解，我们可以看下其elementwise form：

Step 1: Policy Update

求解得到 ，其中 ，其也被称为贪婪策略；

Step 2: Valule Update

即:

Policy Iteration

我们在上文中提到 并不是state value，因为它不保证满足bellman equation；

在Policy Iteration中，我们先给出求解步骤：

Step 1: policy evaluation

选择个初始策略

（为什么叫policy evaluation？因为我们之前提到，如何评价一个policy好坏呢？看其对应的state value，而上式就是在求解一个贝尔曼等式，因此与value iteration不同， 是真正的state value）

对于该式的求解，在前文中有介绍，我们既有closed-form方案也有iterative solution。

关于iterative solution：

Step 2: policy improvement

具体求解，可以进行elementwise推导；

通过state value评价一个policy的好坏，我们在value iteraion中，能够确定在迭代过程中 ；在policy improvement步骤中，怎么证明 呢？

Lemma（Policy Improvement）：

If ，then for any $；

Prove：

有：

此外，由于存在 ，因此可推：

因此可得：

所以：

因此 ，所以 得证；

从上面的证明，我们可以看到随着迭代的进行， 的值在增加，但仍需要证明其是否会收敛至 ，即最优state value。

证明：

最优state value是怎么产生的？根据contraction mapping theorem，我们采用迭代式的算法： ，其最终会收敛至最优值；

我们如果想要证明 的收敛性，只需要证明 即可，这样伴随着 的收敛至最优值， 最终也会收敛；下面开始证明

对于 ，因为 和 都是我们赋予的初始值，因此容易满足 ，所以对于任意 ，都存在 。

（题外话：观察我们上面的两个证明方法，都是在试图构造序列，然后利用序列的收敛性进行证明，这个方法在RL中应用普遍；）

我们已经证明了policy iteration的收敛性，以及能获得最优的state value和对应最优的policy(最优贝尔曼等式)

具体的elementwise form仿照value iteraion，先通过ietration algorithm求解贝尔曼等式，获得state value；在policy improvement步骤，再得到greedy policy；

所以，可以看出policy iteration中还嵌入了求解state value的iteration。因此，可以盲目猜测，它相比于value iteration算法计算量大，但会更稳定，而且收敛的更快，这正是policy iteration的优势；

Truncated Policy Iteration

回顾value iteration和policy iteration，在每轮迭代中（对于value iteration是policy update和value update环节，对于policy iteration是policy evaluation和policy improvement环节），主要区别在于针对 ，二者有不同的处理方式；

value iteration只计算一步，其并不能够保证满足贝尔曼等式，而policy iteration却在policy evaluation环节，能够求解得到真正的state value。但这也会引入问题，因为在求解state value时，理论上需要迭代无穷步；

而本节所介绍的Truncated Policy Iteration则是介于两者之间，在policy evaluation中迭代 步。