动态规划
- 动态规划给出了求解强化学习的一种方式
使用条件
- 使用动态规划需要两个条件
- 总问题可以分解成一系列相互重叠的子问题
- 子问题的求解结果被存储下来并且可以重复使用
- 强化学习对应以上两个条件
- 贝尔曼等式满足了重叠子问题的分解，每个状态的值求解从当前状态到下一状态。
- 值函数用于存储和复用子问题的求解结果
分类
- 对于预测问题，动态规划方法输出的是每一状态的值
- 对于控制问题，动态规划方法输出的是每一状态的策略
求解方法
- 迭代策略：基于贝尔曼等式，每个状态值的求解从当前状态St到下一状态St+1，按此递推方法迭代。
- 策略的改进方法：迭代，根据值选择最佳策略，每次更新通过贪婪法选择最大的值替换原先的值。
- 异步动态规划：
- 每次使用新的状态值更新旧的状态值In-place
- 使用贝尔曼误差引导状态的选择，优先更新误差最大的状态
- 更新状态值都使用状态的参数
- 全状态的动态规划存储搜索每个状态空间，基于采样的动态规划和近似的动态规划减少了部分状态空间的使用
Real-time dynamic programming
参考
david siver 课程