强化学习笔记3：动态规划 planning by dynamic programming（DP）

规划，适用于MDP模型参数已知 学习，适用于Env未知或部分未知

概述

动态规划分为两步，Prediction、Control

方法：

例子

然后最简单的策略，greedy，往v值高的地方走。

Policy iteration：\(O(mn^2)\)

Value iteration：\(O(m^2n^2)\)

值迭代和policy迭代的区别

• policy iteration每次迭代v(s)都会变大；而value iteration则不是。
• 价值迭代不需要策略参与，依据MDP 模型，直接迭代，需要P矩阵、r 等已知
  • policy iteration： policy->value->policy
  • value iteration：value->value

Trick:

三种值迭代方法: 常规的值迭代，要遍历过所有s之后，才进行一次迭代，因此存在old、new两个v(s)

• in-place DP：新值直接替换旧值，只存储一个v(s)，
  • 异步更新，提高效率
  • 缺点：更新顺序影响收敛性
• Prioritised sweeping：state的影响力排序
  • 比较贝尔曼误差绝对值，大的更新，小的忽略
• Real-time DP：遍历过的才更新
  • 省去了agent 未遍历的状态s，对于稀疏任务效率提升极大