欢迎转载，作者：Ling，注明出处：强化学习教程: 03-Policy Iteration and Value Iteration

本章主要内容：

• 动态规划：Dynamic Programming
• 迭代策略评估：Iterative Policy Evaluation，Prediction
• 策略迭代: Policy Iteration，Control
• 值迭代: Value Iteration，Control

概述：

前一章我们讲到，所有强化学习，都可以转化成MDP问题，而解MDP问题，就是要解Bellman最优方程，它可以通过Policy Iteration和Value Iteration获得，所以本章主要内容将围绕这两个问题展开。

动态规划：

动态规划是一种很重要的算法了，它可以解决很多的问题，包括矩阵连乘问题，最长公共子序列问题等等。

要想使用动态规划来解决问题，首先问题得先具备几个特点：

• 最优子问题。也就是说问题可以分解成很多的子问题
• 重叠子问题。要求不仅可以分解为子问题，而且子问题重复出现很多次，解决方法因此可以被保存和重复利用

对于一般得Bellman最优方程，很难直接求解， 比如矩阵求逆之类的，因此我们采用动态规划来求解。MDP正好满足线性规划的要求：

• 最优子问题。MDP可以用贝尔曼方程来表示，而贝尔曼方程就是一种递归的分解
• 重叠子问题。价值函数正好存储了解决方法，而且可以重复使用

迭代策略评估：Iterative Policy Evaluation

也就是Prediction，求值函数

举例：我们先从要给例子出发，看看如何通过该方法求得值函数

迷宫：

状态和Reward：

• 1-14状态是非终点，向每个方向的Reward都是-1
• 两个阴影是终点，到了就停止，所有没有下一步，Reward都是0

Action：Action可以向四个方向

γ：γ值为1，即没有Discount

Π：Agent采用uniform random policy

迭代策略评估：即告诉你如何更新v(s)

先看左边列：

• k表示第几次迭代
• 每次迭代在每个非终点状态，采取的策略都是四个方向等概率1/4
• 在终点状态，到了它就停止，所以没有下一步，该点的v(0,0)=v(3,3)= reward = 0，切始终为0
• 当k=0时每个状态的v都是0
• 当k=1时，

坐标为(0,1)状态value从0->-1

公式：

计算：

其他值和不同迭代值变化都类似

再看右边列：

• 右边是在第k次迭代时，已经更新v值情况下，每个状态的最佳策略更新情况
• K=0时，任何状态向任何一个方向走，获得的value都一样，所以每个状态最佳策略四个方向都一样
• k=1时，s(0,1)向西走可以获得最佳value，所以最佳策略仅剩下向西的策略

其他同理

总结：

• 再策略评估中，每次value更新，都是采取四个方向概率一样的策略，不会将学习得到的最优策略，应用于V更新中
• 经过多次迭代后，最优策略不再改变

问题：

现在我们每次value更新，采用策略都一样，假如我们将最优策略更新也考虑进来，是否可以加快value值更新，从而更快得到最优策略

策略迭代: Policy Iteration，将策略更新加入value迭代，每次选择最佳策略对value进行更新，然后真正按你选的策略进行迭代

• 通过随机策略，更新value
• 根据更新的value，计算最佳策略
• 根据最佳策略，更新value
• 根据更新value，计算最佳策略
• 如此反复，直到策略或者value不再更新，都到达最佳状态

图示：

关于收敛性证明：了解即可

问题：

value是否有必要更新到value收敛的最优值？

没必要，因为再value更新到最优值之前，策略已经到了最优，如图中的k=3的时候已经到了最新

扩展策略迭代：

引入一个带阈值的value function，只要两次更新，value变化足够小了就停止

k次迭代之后就停止

值迭代: Value Iteration，每次以让值最大为目标，通过不同策略，选择值最大的更新当前值，但是下一步是否采取最大值对应的策略，不一定，而是根据你选择策略的的方式决定，比如：ε-greed策略选择法，一般大概率选择最大值对应的策略，小概率会选择其他策略

举例：我们通过一个例子，看看如何通过值迭代找到最佳策略

s(0,0) 是终点，其他是非终点状态

终点Reward是0，其他非终点Reward是-1

k=1时，就是v1，所有状态都是0

k=4时，就是v4

v(1,1)计算：

总结：

value迭代就是根据上次迭代的value，选择分值最高的value，求本次的value，直到value值不再更新

依据时Bellman等式：

同步动态规划迭代更新算法总结：

注: 无论Policy iteration还是Value iteration都可以对v或者q进行更新，如果是对v更新，叫v policy iteration和v value iteration，如果是对q进行更新，则q policy iteration和q value iteration

其他动态规划更新方法：

Asynchronous Dynamic Programming

• In-place dynamic programming
• Prioritised sweeping
• Real-time dynamic programming

Full-Width Backups

Sample Backups

Approximate Dynamic Programming