欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

强化学习(4)-动态规划

动态规划、蒙特卡洛、时序差分是三种解决有限马尔科夫决策的有效方法,方法各有优缺点,本文先介绍「动态规划」。

在数学上,动态规划方法比较优美,但是需要对环境建立一个完整且准确的模型;蒙特卡洛方法不需要一个模型,并且非常简单,但是不善于渐进计算;时序差分不需要模型并且是「渐进」的,但是分析难度大。在收敛速度和执行效率上,每种方式都有自己的特点。

iterative policy evaluation

上一章已经介绍过状态价值,公式如下:

QQ20170421-145403

如果状态个数可以穷举,如何得到每一个状态的价值呢?

可以发现,上式中 \(\pi(a|s)\)\(p(s'|s,a)\)\(r(s,a,s')\) 可以看做已知,相当于转移概率已知,熟悉MCMC的应该已经知道如何求解 \(v_{\pi}\) 的分布了,转移概率决定分布收敛位置。所以通过多轮迭代,就可以得到收敛的位置。

具体工程实现的时候,可以使用两个数组表示相邻两步的的分布;但是也可以只是用一个数组,即使存在「重叠」,反而可以做到更快速收敛,因为用到了最新的信息。

算法流程

QQ20170422-122447

 

Policy Improvement

上面通过迭代的方式确定策略在每个状态下的价值,目的是为了选择最优的策略。上面介绍的策略和策略评估都是站在多轮反馈的角度考虑, 一种直观的想法是,我可以通过略微修改当前步骤的策略,实现效果的提升。

那么就是寻找一个新的策略 \(\pi'\) 使得下面公式成立,

\(q_{\pi}(s,\pi'(s))=\sum_a \pi'(a|s) q_{\pi}(s,a) \ge \sum_a \pi'(a|s) q_{\pi}(s,a) = v_{\pi}(s)\)

 

最容易想到的一个策略就是贪心策略:

QQ20170423-102755

Policy Iteration

策略迭代可以如下图表示:

QQ20170423-113409

整体的算法流程可以表示为:

QQ20170426-105430

Value Iteration

公式为:

QQ20170428-154845

具体优化方式为:

QQ20170429-104624

 

Asynchronous Dynamic Programming

上面介绍的算法,都是基于状态个数有限的前提,如果状态太多这个方法就不能工作了。

这里的「异步」主要思想是,下一轮迭代的开始,不用等待上一轮的结束;更具体点就是,某一个状态可能更新了10次,另外一个状态才更新一次,更新的方式都是使用原地更新(in-place)的方式。

Generalized Policy Iteration

和「异步DP」类似,整个强化学习的过程,都是可以「异步」进行的,只要最终可以收敛到「最优解」即可,在工程实现的角度,其实就是可以支持「并发」。

QQ20170429-111531

 

 

 

未经允许不得转载:大数据算法 » 强化学习(4)-动态规划

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站