制作网站软件网站,上海市建设干部学校网站,东莞app下载安装,财务公司网站模板一、蒙特卡洛方法 这里将介绍一个学习方法和发现最优策略的方法#xff0c;用于估计价值函数。与前文不同#xff0c;这里我们不假设完全了解环境。蒙特卡罗方法只需要经验——来自实际或模拟与环境的交互的样本序列的状态、动作和奖励。从实际经验中学习是引人注目的#x…一、蒙特卡洛方法 这里将介绍一个学习方法和发现最优策略的方法用于估计价值函数。与前文不同这里我们不假设完全了解环境。蒙特卡罗方法只需要经验——来自实际或模拟与环境的交互的样本序列的状态、动作和奖励。从实际经验中学习是引人注目的因为它不需要任何关于环境动态的先验知识但仍然可以实现最优行为。从模拟经验中学习也很强大。尽管需要一个模型但该模型只需要生成样本转换而不是动态规划所需的完整概率分布的所有可能转换。令人惊讶的是在很多情况下根据所需概率分布生成经验样本很容易但获得分布的显式形式是不可行的。 蒙特卡罗方法是解决强化学习问题的方法它基于平均样本回报。为了确保可定义回报可用在这里我们将蒙特卡罗方法仅定义为针对离散任务的方法。即我们假设经验分为回合并且所有回合最终都会终止无论选择什么动作。只有在完成回合后才会更改价值估计和策略。因此蒙特卡罗方法可以是逐回合的增量但不能是逐步在线的增量。术语“蒙特卡罗”通常更广泛地用于任何涉及大量随机组件的估计方法。在这里我们将其专门用于基于平均完整回报而不是从部分回报中学习的方法的方法。 蒙特卡罗方法对每个状态-动作对进行采样和平均回报就像我们在前文对每个动作进行采样和平均奖励一样。主要的区别在于现在有多个状态每个状态都像不同的问题如联想搜索或上下文一样而且这些不同的问题是相互关联的。也就是说在一个状态下采取一个行动后的回报取决于在同一回合中后来采取的行动。因为所有的行动选择都在进行学习所以从更早的状态来看这个问题就变成了非平稳的。 为了处理非平稳性我们采用了通用策略迭代GPI的想法。在那里我们从MDP的知识中计算值函数在这里我们从样本回报中学习值函数与相应的策略仍然以相同的方式相互作用以获得最优性GPI。与DP一样我们首先考虑预测问题计算固定任意策略π的vπ和qπ然后进行政策改进最后是控制问题以及通过GPI解决。这些来自DP的想法都被扩展到了只有样本经验可用的蒙特卡罗情况下。
二、蒙特卡洛预测 我们首先考虑使用蒙特卡罗方法学习给定策略的状态值函数。注意一个状态的值是期望的回报也就是从该状态开始的期望累积未来折扣奖励。那么从经验中估计它的一个明显方法就是简单地将该状态后观察到的回报进行平均。随着更多的回报被观察到平均值应该收敛到期望值。这个想法是所有蒙特卡罗方法的基础。 特别是假设我们希望估计π策略下状态s的值vπ(s)给定一组遵循π并通过s获得的状态转移序列。在每个回合中状态s的每次出现称为对s的一次。当然在同一个回合中s可能被多次让我们称在回合中对s的第一次为s的第一次。第一次蒙特卡罗方法估计vπ(s)为在第一次s后的回报的平均值而每次蒙特卡罗方法则将所有s后的回报进行平均。这两种蒙特卡罗方法非常相似但具有稍微不同的理论性质。蒙特卡罗方法是研究很广泛以程序形式显示在图1中。 图1
图1中我们使用大写字母V表示近似值函数因为在初始化之后它很快就会变成一个随机变量。 对于首次使用蒙特卡罗方法和每次使用蒙特卡罗方法当次数或首次次数趋于无穷时它们都会收敛到vπ(s)。对于首次蒙特卡罗方法的情况这一点很容易理解。在这种情况下每次返回都是vπ(s)的独立、相同分布的估计具有有限方差。根据大数定律这些估计的平均值序列收敛到它们的期望值。每个平均值本身都是一个无偏估计其误差的标准偏差为1/√n其中n是平均值的数量。每次蒙特卡罗方法不太直观但其估计也渐近收敛到vπ(s)Singh和Sutton1996。蒙特卡罗方法的使用最好通过一个例子来说明。
三、典型例子 21点又称黑杰克是一种广受欢迎的赌场牌戏。游戏的目标是在不超出21点的情况下尽可能获得高数值的牌。所有花牌都算作10点而一张A可以算作1点或11点。我们考虑的是每个玩家独立与庄家对抗的版本。游戏开始时庄家和玩家都会得到两张牌。庄家的一张牌是明牌另一张是暗牌。如果玩家立即得到21点一张A和一张10那么就称为“自然”除非庄家也有自然否则玩家获胜。如果玩家没有自然那么他可以要求额外的牌一张一张地要继续要牌直到他停止停牌或超过21点爆牌。如果他爆牌他就输了如果他停牌那么就轮到庄家。庄家根据固定的策略决定是否要牌或停牌没有选择他在任何总和为17点或更高的情况下停牌否则就继续要牌。如果庄家爆牌那么玩家就赢了否则结果赢、输或平局由谁的最终总和最接近21点决定。 图2 图2中黑杰克策略的近似状态值函数只在20或21点停牌通过蒙特卡洛策略评估计算。玩二十一点被自然地制定为一段有限的MDP。 每一局二十一点是一个情节。 对于赢、输和平局分别给予1、-1和0的奖励。 在一局比赛中所有的奖励都是零我们不进行贴现γ 1因此这些末端奖励也是回报。 玩家的行动是击打或停牌。 状态依赖于玩家的牌和庄家的明牌。 我们假设卡片是从一个无限的套牌即替换中发出的因此没有必要追踪已经发出的卡片。 如果玩家持有一张可以计为11的A牌而不会爆牌那么这张A牌被称为可用。 在这种情况下它总是被计为11因为把它计为1会使总和小于或等于11在这种情况下没有做出决定因为显然玩家应该一直击打。 因此玩家根据三个变量做出决定他当前的总和12-21庄家的一个明牌A-10以及他是否持有一张可用的A牌。 这总共有200个状态。 考虑如果在玩家总和为20或21时停牌否则就击打的策略。 通过蒙特卡罗方法找到此策略的状态值函数模拟许多二十一点游戏并平均每个状态后的回报。 请注意在此任务中相同的状态在同一情节中永远不会重复发生因此没有首次访问和每次访问的MC方法之间的区别。 通过这种方式我们获得了图2中所示的状态值函数的估计值。具有可用A牌的状态的估计值不太确定也不太规律因为这些状态不太常见。 无论如何经过50万场比赛后价值函数被很好地逼近。
