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公式的 $$ 格式简直是知识传播的阻碍!!!!(╯`д′)╯︵ ┻━┻