Preliminary of RL Ⅱ:DP, MC & TD
这篇post主要讲一下 MDP 问题的求解方法。上文讲过,MDP问题是具有延迟回报性质的,即当前状态下的最优动作不一定具有长远利益。在序列决策问题中,必须要求智能体具有长远的眼光。
MDP基本的解法有三种:
- 动态规划法(dynamic programming methods)
- 蒙特卡罗方法(Monte Carlo methods)
- 时间差分法(temporal difference)
上图是很经典的三种方法的差异图,即使现在还完全不知道他们的定义,也可以总结出它们的特性。
- 是否需要执行到本轮结束决定了算法的更新频率,这当然是越快越好
- 是否需要遍历所有可能动作决定了是否需要预先知道系统模型,否则不可能获取所有可能的动作已经对应的结果
先下个结论
综上可知,TD综合了MC和DP的优点,因此这也是我们在RL中常用的方法。
Dynamic Programming 动态规划
那么,什么是动态规划?
什么是动态规划(Dynamic Programming)?动态规划的意义是什么? - 阮行止的回答 - 知乎
知道你们懒得看,毕竟这篇文章已经够长了。帮你们总结一下精髓:
将 复杂问题的最优解 划分为 多个小问题的最优解 的求解问题,就像递归一样,且子问题的最优解会被储存起来重复利用。
(有疑惑还是建议看一下上面链接,答主的例子很简明)
对于无后效性且需要长远眼光的 MDP 问题来说,DP 确实很合适。下面所述的贝尔曼方程就是递归结构,值函数可以储存子问题的解。
一、贝尔曼方程 (Bellman Equation)
和 的表达式总结如下:
在动态规划中,上面两个式子称为贝尔曼方程,它表明了当前状态的值函数与下个状态的值函数的关系 。
优化目标 可以表示为:
分别记最优策略对应的状态值函数和动作值函数为 和 .
状态值函数和行为值函数分别满足如下贝尔曼最优性方程(Bellman optimality equation),定义了最优解满足的条件:
故可知, 和 .存在如下关系:
Reference
[1] Kintoki's blog
[2] 强化学习 - 动态规划(Dynamic Programming)
未完待续。。。
强烈吐槽知乎专栏,公式输入好麻烦,好不容易写完了动态规划,结果一更新没了??没了???一夜回到解放前,现在毫无心情更新,等我心情好点再弄吧。大家快给个赞鼓励鼓励我吧。
不支持tex公式的 $$ 格式简直是知识传播的阻碍!!!!(╯`д′)╯︵ ┻━┻
评论(0)
您还未登录,请登录后发表或查看评论