Planning by Dynamic Programming
Dynamic Programming
- 具有某种时序关系的问题。
-
将复杂的问题分解为子问题，结合子问题的解决方案，即动态规划。
image.png
动态规划需要满足的两个要求
- 最优化结构，即将整合结构问题分解为两个或多个子问题。
- 重叠子问题，对于多次出现的子问题，子问题的最优解可以多次利用。
- MDP符合这两种特性和贝尔曼方程。
-
贝尔曼方程可以理解为，当前步采取最优的行动，余下的其他步骤也将采取最优的行动，从而获得整体最优值（value function）。
image.png
Planning 问题
- 预测问题：已知Policy，求得最多的奖励。
-
控制问题：寻找最好的Policy，使这个MDP获得最大奖励。
image.png
Dynamic Programming 适用
- 生物信息学中序列比对。
-
图论算法。
image.png
Policy Evaluation
- 贝尔曼方程评估Policy。
- 通过迭代更新 value function。
-
同步备份，每一次迭代，都将用到全部的MDP中的状态用于更新value function。
image.png
贝尔曼方程
-
叶子结点储存我们上一次迭代的 value function ， 通过动态规划方式，得到一个新的value function。
image.png
例子 评估一个已知的（random）Policy
-
采用最简单的Policy，即向四个方向移动的概率都是1/4.
image.png 使用动态规划的方法求解value function。
某位置当前时刻四个方向移动获得的reward + 上一步四个方向移动获得的reward 除以4得到当前value function 位置的值。
-
根据动态规划，更新value function，同时得到最优的Policy（右边）。
image.png -
value function 的值最终会稳定。
image.png
Policy Iteration
-
2- step
1.1 评估一个policy，就像上一步所做的，填数字，计算出policy能够得到的分数。
1.2 贪心算法，右边最后就是最有policy。
1.3 MDP中总是存在一个最优的Policy。
image.png -
向上的箭头表示评估（贝尔曼方程）， 向下的过程表示对value function 使用贪心算法更新Policy。最终收敛到最优Policy和真实的value function。
image.png
更精准的描述下 Policy Inprovement
每一步都取argmax，则更新后的policy至少和开始采取的policy得到的一样多。
-
所以更新后的policy只会获得更好的得分。
image.png -
最优解稳定
image.png
Modified Policy Iteration
-
基本思想：提前停止
1.1 观察贝尔曼方程 value function的更新幅度。
1.2 控制迭代次数。
image.png
Principle of Optimlity
- 将value function看作是对所有子问题的兑现方案，是后向传播算法，及知道最优解，更新非叶子结点value function。
-
通过循环整个状态空间，迭代找到最优贝尔曼方程，而不是通过反向传播。
image.png - 同上面的小方格计算不同，这是一种反向传播从而获得最短路径的方法。
- 基于已有的完备知识（我们知道这个结构是如何工作的），我们就不需要更新每一个状态，只需要从初始状态feedback就可以获得我们关心的状态。
-
没有终点状态，我们的算法依旧能够运行。
image.png
value iteration
- Policy iteraction 中迭代（value function + policy（greedy））。
-
每一步没有确定的policy，只有value function的迭代更新。没有创建新的policy，只是中间步骤。
image.png -
每次迭代将会返回根节点，利用贝尔曼方程最大化期望，从而更新value function，获得最优的value function。
image.png
动态规划算法
- 预测问题：已知policy，可以得到多少奖励。贝尔曼方程定义了约束方程，得到
.
- 控制问题： 如何从已知MDP中获得最大奖励，获得
， 最优policy。
2.1 policy iteration
2.2 value iteration： 使用贝尔曼最优方程，求解最大值，通过value function自我迭代求得最大值。
image.png
拓展
-
三种异步更新方法。
image.png
-
使用某个轨迹的真实样本。
image.png
总结
-
DP使用全尺寸 ，考虑所有的action和所有的后继状态。
image.png
