强化学习(三)——MDP, 动态规划
source link: http://antkillerfarm.github.io/rl/2019/02/24/RL_3.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Q-learning(续)
Richard Ernest Bellman,1920~1984,美国应用数学家、控制论学家、数理生物学家。布鲁克林学院本科+威斯康星大学麦迪逊分校硕士+普林斯顿博士。二战期间曾在Los Alamos研究理论物理,后任职于美国智库RAND Corporation,南加州大学教授。美国艺术科学院院士,美国科学院院士。
Bellman–Ford算法的发明人之一。以他命名的奖项有Richard E. Bellman Control Heritage Award和Bellman Prize in Mathematical Biosciences。
在无监督的情况下,agent不断从一个状态转至另一状态进行探索,直到到达目标。我们将agent的每一次探索(从任意初始状态开始,经历若干action,直到到达目标状态的过程)称为一个episode。
Q-Learning算法的计算步骤如下:
Step 1:给定参数γ和reward矩阵R。
Step 2:初始化Q=0。
Step 3:For each episode:3.1 随机选择一个初始状态s。
3.2 若未达到目标状态,则:(1)在当前s的所有action中,随机选择一个行为a。
(2)利用a,得到下一个状态s~。
(3)利用公式1,计算Q(s,a)。
(4)令s=s~。
由马尔可夫过程的性质(参见《机器学习(二十六)》)可知,Q矩阵最终会趋于一个极限,如下所示:
上面的矩阵可用下图表示:
显然,沿着Q值最大的边走,就是这个探索问题的最佳答案。(如上图红线所示)即:
π(s)=argmaxa(Q(s,a))
http://blog.csdn.net/itplus/article/details/9361915
一个Q-learning算法的简明教程
http://blog.csdn.net/young_gy/article/details/73485518
强化学习之Q-learning简介
https://mp.weixin.qq.com/s/34E1tEQMZuaxvZA66_HRwA
通过Q-learning深入理解强化学习
https://mp.weixin.qq.com/s/kmk3mKASZPixA8VS9sipcA
走近流行强化学习算法:最优Q-Learning
https://mp.weixin.qq.com/s/o-IzYt62qaUhcTY33E0Ylg
基于强化学习Q-Learning模型构建算法交易策略
https://mp.weixin.qq.com/s/ePssT5BDb9KebCTehn0ugw
5分钟读懂强化学习之Q-learning
https://www.zhihu.com/question/26408259
如何用简单例子讲解Q-learning的具体过程?
Markov Decision Process
上边Q-Learning的例子中,由于action能够唯一确定状态的变换,因此又被称为Markov Reward Process:
<S,P,R,γ>
这个四元组依次代表:states、state transition probability matrix、reward function、discount factor。
实际中,执行特定的动作并不一定能得到特定的状态。
比如上图中,在状态S0,执行a0,只有0.5的机会,会到达S2。这也就是之前提到过的MDP。
标准MDP中的Bellman equation可改为如下形式:
v=R+γPv
其中,P,R均为已知。
这里的Bellman equation是线性方程,它的直接解法如下:
(I−γP)v=Rv=(I−γP)−1R
然而这个方法的复杂度是O(n3)(n是状态的个数),这对于大的MDP来说,并不好用。这种情况下,常用的解法有:Dynamic programming(动态规划)、Monte-Carlo evaluation和Temporal-Difference learning。
由于MDP对于RL任务进行了Markov假设,这属于一种建模行为,因此它也被归为一种model-based learning的算法。
MDP的扩展主要包括:
a) Observation部分可见的情况下,agent state ≠ environment state,这时一般叫做partially observable Markov decision process(POMDP)。
b) Infinite and continuous MDP
c) Undiscounted, average reward MDP
扩展MDP的Bellman equation都不是线性方程,没有解析解,只有迭代解。相关解法主要使用了概念图模型,这里不再详述。
https://mp.weixin.qq.com/s/G8zmooqhSKqcLv1u7uM0bw
AlphaGo等智能体是如何炼成的?你需要懂得马尔科夫链
https://mp.weixin.qq.com/s/KQmKb5NrjgxooCnbZaiTzw
强化学习中无处不在的贝尔曼最优性方程,背后的数学原理为何?
Dynamic programming(DP)用于解决那些可分解为重复子问题(overlapping subproblems)并具有最优子结构(optimal substructure)的问题。这里的programming和编程并无任何关系。
上世纪40年代,Richard Bellman最早使用动态规划这一概念表述通过遍历寻找最优决策解问题的求解过程。1953年,Richard Bellman将动态规划赋予现代意义,该领域被IEEE纳入系统分析和工程中。
除了Bellman之外,苏联的Lev Pontryagin也做出了很大的贡献,他和Bellman被并称为Optimal control之父。
Lev Semyonovich Pontryagin,1908~1988,苏联数学家。主要研究代数拓扑和微分拓扑。他14岁时,因为煤气爆炸事故成为盲人。苏联科学院院士,国际数学家联盟副主席。
最优子结构
最优子结构即可用来寻找整个问题最优解的子问题的最优解。举例来说,寻找图上某顶点到终点的最短路径,可先计算该顶点所有相邻顶点至终点的最短路径,然后以此来选择最佳整体路径,如下图所示:
一般而言,最优子结构通过如下三个步骤解决问题:
a) 将问题分解成较小的子问题;
b) 通过递归使用这三个步骤求出子问题的最优解;
c) 使用这些最优解构造初始问题的最优解。
子问题的求解是通过不断划分为更小的子问题实现的,直至我们可以在常数时间内求解。
重复子问题
重复子问题是指通过相同的子问题可以解决不同的较大问题。例如,在Fibonacci序列中,F3 = F1 + F2和F4 = F2 + F3都包含计算F2。由于计算F5需要计算F3和F4,一个比较笨的计算F5的方法可能会重复计算F2两次甚至两次以上。
为避免重复计算,可将已经得到的子问题的解保存起来,当我们要解决相同的子问题时,重用即可。该方法即所谓的缓存(memoization)。
动态规划通常采用以下两种方式中的一种:
自顶向下:将问题划分为若干子问题,求解这些子问题并保存结果以免重复计算。该方法将递归和缓存结合在一起。
自下而上:先行求解所有可能用到的子问题,然后用其构造更大问题的解。该方法在节省堆栈空间和减少函数调用数量上略有优势,但有时想找出给定问题的所有子问题并不那么直观。
需要注意的是:动态规划更多的看作是一种解决问题的方法论,而非具体的数值算法,因此,很多不同领域的算法都可看做是动态规划算法的实例。参考文献中,就列出了不少这样的算法。显然,动态规划是一种迭代(Iteration)算法。
由前文的描述可知,MDP正好具备overlapping subproblems和optimal substructure的特性,因此也可以通过DP求解。
在继续下文之前,推荐一波资源:
David Poole,加拿大不列颠哥伦比亚大学教授。加拿大AI协会终身成就奖(2013年)。
个人主页:
http://www.cs.ubc.ca/~poole/index.html
David Poole的主页上有很多好东西:
http://www.cs.ubc.ca/~poole/demos/
该网页上有一些RL方面的用java applet做的可视化demo。由于年代比较久远,这些demo无法在目前的浏览器上运行。所以,我对其做了一些改造,使之能够使用。相关代码参见:
https://github.com/antkillerfarm/antkillerfarm_crazy/tree/master/RL
2019.10
由于appletviewer在最新的JDK中已经被移除了,因此,这次选择JS作为目标语言,并对其中的Q-Learning做了移植。
代码:
https://github.com/antkillerfarm/antkillerfarm_crazy/tree/master/nodejs/js/RL/Q
David Poole还写了一本书《Artificial Intelligence: foundations of computational agents》,目前已经是第2版了。
其中的代码资源参见:
http://artint.info/AIPython/
从该书所用编程语言的变迁,亦可感受到Poole教授不断学习的脚步。要知道Poole教授刚进入学术界的时代(1985年前后),就连Java也还没被发明出来呢。
http://uhaweb.hartford.edu/compsci/ccli/samplep.htm
Hartford大学的这个网站也有些不错的资料,偏重RL、机器人、ML for Game等领域。
RL与DP
在继续讲述之前,我们首先来明确几个概念:
vπ和qπ的定义参见《强化学习(一)》。
v∗(s)=maxπvπ(s)q∗(s,a)=maxπqπ(s,a)
RL领域的DP算法的主要思想是:利用value function构建搜索Good Policy的方法。这里用v∗(s)或q∗(s,a)表示最优的value function。
RL DP主要包括以下算法:(为了抓住问题的本质,这里仅列出各算法最关键的Bellman equation,至于流程参照Q-learning算法即可。)
Policy Iteration
Policy Iteration包含如下两步:
Policy Evaluation:
vk+1(s)=∑a∈Aπ(a∣s)(Rsa+γ∑s′∈SPss′avk(s′))
Policy Improvement:
πk+1(s)=argmaxa∈A(Rsa+γ∑s′∈SPss′avk(s′))
由于q∗(s,a)对应的v(s)必是v∗(s),反之亦然,因此Policy Iteration的过程通常如下所示:
如果只需要Prediction,不需要Control的话,也可以只进行Policy Evaluation,这时也被称为Iterative Policy Evaluation。
Value Iteration
vk+1(s)=maxa∈A(Rsa+γ∑s′∈SPss′avk(s′))
state-value function迭代的复杂度是O(mn2),其中m为action的数量,n为state的数量。而action-value function迭代的复杂度是O(m2n2)
Policy Iteration与Value Iteration的区别在于:
1.Policy Iteration是在迭代过程中不断寻找最优策略。
2.Value Iteration是在迭代过程中寻找状态s下的最优value。如果所有状态的最优value都找到的话,则可通过寻找最大value路径的方式,找到最优策略。例如,之前提到的Q-Learning。
动态规划的主要局限在于:
1.它依赖于概率模型。
2.计算复杂度太高,只适合规模中等(<1M的状态数)的情况。
Recommend
-
126
在开始强化学习前,你所需要了解的知识。修改于2018-01-02 08:10:32阅读 1.7K0本译文自JOSHGREAVES发表在
-
119
强化学习是如何解决问题的? ...
-
124
前面经过David Silver的强化学习课程的布道,对强化学习有了系统的认知。但是实践是检验真理的唯一标准,所以后面开启强化学习实践系列,分享相关内容。
-
76
强化学习入门及其实现代码
-
105
撇开什么是动态规划不谈,我们先来看看题干: 有500只老虎,1只羊,一片草原。老虎和羊,都可以吃草活着,对,这个题中的老虎可以吃草。老虎呢,也能吃羊,不允许很多只老虎一起吃羊,只允许一只老虎吃一只羊,并且,吃完羊之后,这个老虎就会变成羊。那么问,老虎...
-
33
上一篇文章写了个爬楼梯的问题,没想到有很多人关注,趁热打铁,这次写背包问题(初级)。我的学习风格就是一步一步的实现,力求解释全面,可能会啰嗦。 1 背包问题 先举一个很通俗易懂的例子,也是图解算法中的例子,有一个只能装4kg的包,物品有音响3000元-重4k
-
16
【强化学习与最优控制】笔记(一)确定性问题的动态规划科研话题下的优秀回答者0 写在前面的最近在学动态规划和强化学习,主要采用的教材是这本书,Bertsekas D P. Reinf...
-
3
https://www.bilibili.com/vide...记忆化递归const fib = n => { if (n === 1 || n === 2) return 1 return fib(n - 1) + fib(n - 2) } console.log(fib(6)) console.log...
-
3
MDPs and Bellman Equations Learning Goals Understand the Agent-Environment interface Understand what MDPs (Markov Decision Processes) are and how to interpret transition diagrams Understand Value Funct...
-
5
强化学习,目的就是求解MDP(马尔科负决策过程),而MDP的求解有三种情况: 动态规划求解法:求解一个已知环境完整知识的MDP。有两种方法: Model free prediction:对于一个环境知识不完整的MDP, 估计状态值函数。有两种方法:...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK