23-08-10
强化学习4:蒙特卡洛(MonteCarlo)
概述
通过贝尔曼方程求解最优策略
简而言之,首先通过策略评估计算给定策略
在实际任务中,环境知识完备性这一先决条件较难满足,但是,也就是无法在现实世界同时知道MDP的5元组⟨S,A,P,R,γ⟩。也就意味着大量的强化学习任务难以直接采用动态规划法进行求解。对于环境知识不完备的MDP,即转移矩阵
虽然不知道状态转移概率 P \mathcal{P} P,但是这个概率真实存在。可以直接尝试,不断采样,然后会得到奖赏,通过奖赏来评估值函数。这与蒙特卡罗方法的思想一致。
蒙特卡洛 Monte Carlo
“蒙特卡洛”这一名字来源于摩纳哥的城市蒙特卡洛(MonteCarlo)。该方法由著名的美国计算机科学家冯·诺伊曼和S.M.乌拉姆在20世纪40年代第二次世界大战中研制原子弹(”曼哈顿计划”)时首先提出。 蒙特卡洛法是一种基于采样的算法名称,依靠重复随机抽样来获得数值结果的计算方法,其核心理念是使用随机性来解决原则上为确定性的问题。通俗而言,蒙特卡洛法采样越多,结果就越近似最优解,即通过多次采样逼近最优解。
举个简单的例子。
去蔬菜基地摘玉米,规则是每次只能摘一个玉米,并且手中只能留下一个玉米,最后走出蔬菜基地的时候也只能带走一个玉米,目标是使得最后拿出蔬菜基地的玉米最大。可以达成这样一个共识:进入蔬菜基地后每次摘一个大玉米,看到比该玉米更大的则替换原来的玉米。基于上述共识,可以保证每次摘到的玉米都至少不比上一次摘到的玉米小。如果摘玉米的次数越多,挑出来的玉米就越大,但无法确保最后摘到的玉米一定是最大的,除非把整个蔬菜基地的玉米都摘一遍。即尽量找较大的,但不保证是最大的。采样次数越多,结果就越近似最优解,这种方法就属于蒙特卡洛法。
蒙特卡洛法能够处理免模型的任务的究其原因是无须依赖环境的完备知识(Environment backup),只需收集从环境中进行采样得到的经验轨迹(Experience episode),基于经验轨迹集数据的计算,可求解最优策略。
- MC直接从Episode的经验中学习且必须从完整的Episode中学习:没有bootstrapping.
- MC不基于模型,是一种model-free方法,即没有MDP的转移概率
以及奖励 的先验知识。 - MC使用的方法是:价值=平均回报,即value = mean return。
比如,现评估某状态
的价值函数。我们采样了两个经验轨迹,从一个经验轨迹里面得到的回报是5,然后下一个经验轨迹里面的得到的回报是7,我们可以从起始状态来评估此状态的价值函数为:
其实从字面理解就是求均值的意思。就是状态
在每一个样本中收获的回报均值。 MC只能应用于episodic MDPs:所有的Episode都必须终止
Return不是针对于Episode的,而是针对于Episode的某一个状态,是从这个状态开始经历完Episode时得到的有衰减的即时奖励的总和。
从一个Episode中,我们可以得到该Episode内所有状态的收获。当一个状态在Episode内出现多次,该状态的收获有不同的计算方法:first visit和every visit
缺点在于只能应用于一定有终结点(termination point)的按幕(Episode)分的MDP过程。
每条Episode都是一条从起始状态到结束状态的经历(例如在走迷宫,一条episode就是从你开始进入迷宫,到最后走出迷宫的路径),完整的Episode(完整的Episode包含:状态的转移、使用的行为序列、中间状态的即时奖励、终止状态的即时奖励)不要求起始状态一定是某一个特定的状态,但是要求个体最终进入环境认可的某一个终止状态。
要得到的是某个状态
的平均收获,所以episode必须经过该状态 才能用于计算. 理论上完整的状态序列越多,结果越准确。
蒙特卡洛策略评估(MC Policy Evaluation)
特卡洛法采用时间步有限的、完整的经验轨迹,其所产生的经验信息可推导出每个状态的平均奖励,以此来代替奖励的期望(即目标状态值)。换言之,在给定的策略
计算Return的两种方法
首次访问蒙特卡洛策略评估(First-Visit Monte-Carlo Policy Evaluation)
在给定一个策略,使用一系列完整经验轨迹评估某一个状态
- 状态出现的次数加1:
- 总回报更新:
- 使用平均回报更新值函数:
- 由大数定理可以得到,当
趋于无穷大时:
每次访问蒙特卡洛策略评估(Every-Visit Monte-Carlo Policy Evaluation)
在给定一个策略,使用一系列完整经验轨迹评估某一个状态
- 状态出现的次数加1:
(每次访问状态 ) - 总回报更新:
(每次访问状态 ) - 使用平均回报更新值函数:
- 由大数定理可以得到,当
趋于无穷大时:
累进更新(增加)平均值 (Incremental Mean)
不论是First-Visit还是Every-Visit,在计算回报均值时,都是利用总回报除以状态s的总访问次数的,我们能否对均值进行增量式的求取?
这里假设每次的回报为
- 静态问题就是说我们的MDP是不变的,比如转移矩阵,比如奖励函数
- 非静态问题即随着时间的推移,MDP中的某些参数将会发生改变。
蒙特卡洛累进更新(Incremental Monte-Carlo Updates)
对于一系列经验轨迹:
按照更新平均值的方法可以进行如下累进更新响应的价值函数:
这里我们将MC方法变为增量式,我们可以扩展开改变
引入参数
About this Post
This post is written by Rui Xu, licensed under CC BY-NC 4.0.