本文共 11952 字,大约阅读时间需要 39 分钟。
强化学习入门论文
对机器学习这个主题非常感兴趣的大多数人都认为它与神经网络是同义词。 在目前的化身中,神经网络似乎是通用的工具。 通过选择正确的神经网络类型,相同的工具(变化很小)也许能够解决大多数问题。 但是,这并不意味着神经网络是用于给定问题的最佳(甚至是正确的)工具。
在本文中,我们将讨论一种问题,以小游戏为例,可以通过另一种称为强化学习的技术轻松解决。 我们将研究需求,实现和模型的优势。
该游戏可以用铅笔和纸玩,在解决程序问题之前获得第一手经验是一件好事。 这是一种赛车游戏,其中在使“汽车”保持在轨道上的同时尽可能快地穿越轨道。 汽车的轨道和位置在正方形网格上指定。 在游戏中的任何时候,汽车都有位置和速度。 速度包括(与物理学中速度的定义一致)的方向。 运动规则最容易以图形方式说明。
在这两种不同情况下,汽车的当前位置由红色正方形表示,其先前位置由橙色正方形表示。 这两个正方形之间的距离定义了汽车的速度(一种情况下为(4,-1),另一种情况下为(4,0)),其坐标系的第一个维度是从左到右,第二个维度是从下到上。
通过将以下两个值的绝对值相加来测量速度: :| 4 | + | -1 | = 5和| 4 | + | 0 | = 4。
下一步的规则是:速度矢量的长度最多必须向上或向下改变一个,并且速度矢量的分量值每个最多只能变化一个。 结果,汽车最多可以在下一步中移动到七个位置,在图中以绿色方块表示。 如果当前速度为1,则汽车可能会停下来,但这没有用,因为目标是尽快完成路线。 可以通过禁止速度为零来避免这种情况,在这种情况下,这会减少可能的新位置的数量。
轨道是另一个限制。 汽车一定不能离开赛道,鉴于汽车的速度,某些(或全部)可能的新位置可能无效。 轨迹不必由直线和规则曲线定义,它看起来像下面的图片(甚至更复杂)。
对于此练习,我们必须在轨道上定义起点/终点线。 汽车在此直线上的某个位置处开始,初始速度为1(即,水平或垂直方向上为一步),并且必须从另一侧越过直线。 在示例代码中,轨迹和起始行位置被编码为无损图像文件。 起始位置在起始线上以一条线单独给出。
任何成功的比赛都会越过起跑/结束线而不会离开赛道。 最好的解决方案是需要最少步骤的解决方案。 在大多数情况下,可能有不止一种解决方案,但这取决于赛道和起跑条件。
如果我们考虑传统方法,即在一开始就从给定状态确定解决方案,那么我们很快就会遇到问题。 可能性太多了。
问题在于,要计算下一步,必须考虑所有可能的未来步骤。 某种封闭式可能无法制定。 这就留下了递归搜索,除非轨道很短,否则这是非常不实用的。 联合努力将是禁止的。
因此,对于非平凡的曲目,可能有必要解决概率结果。
从理论上讲,可以在进行中的所有步骤中提供有关所有未来步骤的信息。 如前一节所述,这样做的成本过高。 为了做出下一步决定,我们应该将自己限制在该信息的一个子集上,最好是很小的一个子集。 显然,这不能保证我们可以立即找到最佳的解决方案,但这就是机器学习技术应运而生的地方。
在这里,我们正在研究一种称为的机器学习技术,这是一种特殊的强化学习技术。 它允许学习一个动作值功能,这正是我们在这里想要的:在任何情况下,我们都想知道如何改变速度,而移动的质量就是价值。 决定使用Q学习本身并不能确定如何计算该值。 由数据科学家决定。
我们在这里不讨论Q学习背后的理论细节。 可以说,它可以为大量问题找到最佳函数(对于那些感兴趣的人,可以对所有的马尔可夫决策过程进行建模)。 不必具有环境模型(即,在这种情况下,不必对整个轨道进行建模)。 我们可以仅查看步骤前后汽车的紧邻区域,并确定每个步骤的代表值或奖励。
该算法需要表示当前状态:汽车的位置和速度。 我们要确定每种状态下的动作,即新的速度和新位置的结果。 如上所述,我们需要为此分配一个值,用一个数字表示。 我们得到的是所谓的Q函数:
我们在一开始对该函数一无所知,我们可以为所有输入初始返回一个固定的,任意选择的值。 根据稍后在学习阶段中使用的值,初始值可能会影响学习速度。
迭代确定更好的Q值。 该迭代步骤从给定状态开始,确定动作(如何进行此操作将在下面讨论),并确定奖励。 然后,此信息用于更新Q函数:
翻译成单词,这意味着,Q被用于状态s t与动作由奖励的总和乘以旧值与1-α,以及添加到其α倍的步骤R t与γ倍的最大未来叔更新Q的值(或其估计值)。 对于最终状态,我们不必(也不必)更新Q ; 我们只是适当地设置了奖励。 分别与1-α和α相乘可确保Q的值受到初始值和最终状态奖励的限制。
值γ是学习算法的所谓超参数 。 在这种情况下,它是折扣因子,是在类似情况(例如金融数学)中使用的术语。 这意味着,如果将来状态下的奖励为r ,则必须折现当前状态下的价值,因为只能在一个或多个其他步骤之后才能收集奖励。 每一步折现系数0 <γ<1 。 找到正确的γ值是模型开发的一部分。
通过此描述,应该已经有可能看到如何进行模型学习。 我们从给定状态开始,选择一个动作,计算奖励,并确定从新状态开始的动作的最佳奖励。 使用所有这些信息,我们更新当前状态的Q函数,然后从那里开始。 有几件事要注意:
还有一个需要考虑的细节:在学习阶段如何选择下一步。 由于可能需要许多步骤才能实现目标,因此不希望随机选择下一步,这将降低实现目标的可能性。
高Q值可用于指导选择。 但是,始终选择奖励最高的动作可能意味着永远不会探索更好的选择。 因此,我们需要混合:以给定的概率ε ,我们选择一个随机的(有效的)下一个状态。 否则,我们从Q值最高的可能状态中选择一种。 ε成为算法的另一个超参数,它选择发生探索的次数与遵循已知良好路径的距离。
或者,可以使用Q的初始值来鼓励探索。 使用较高的值将确保最终探索状态,而未导致目标的状态将随着时间的推移而降低其Q值。 初始值的选择在这里至关重要,因为它一定不能与奖励值相提并论。
一旦对模型进行了充分的训练,我们可以通过寻找具有最高奖励的动作来确定任何状态下的最佳步骤,然后继续执行相同的操作,直到达到目标为止。 该算法可以保证最终找到最优解,但是这可能会花费一些时间,过早测试解决方案可能不会得出正确的结果:即,链s 1 →s 2 →…→s n可能不会导致每次选择具有最佳Q值的动作a t时的最终状态。 使用模型时要牢记这一点。
现在,我们准备将Q学习应用于在轨道上赛车的问题。 要应用该算法,我们需要一种计算奖励的方法。
奖励的后两个方面旨在提供更高的价值,以防由于目标越近,速度越快或两者兼而有之,就可以更快地达到目标。 到球门的距离和速度的好处应该是可加的。
定义功能仍然有很大的灵活性。 以下是一种可能的方法。
def getr ( d1 , d2 , va , Qgoal ) : if d1 < 0 or d2 < 0 or d1 - d2 > va: return None if d1 < d2: if d1 <= va and d2 > 5 * va: return Qgoal return ( d1 - d2 ) - ( va >> 1 ) / ( d1 - d2 ) else : return ( 1 + d1 - d2 ) * va应该能够理解代码。 参数 d1和 d2是当前位置和下一位置到目标的距离,而 va是当前速度。 除了检查无效位置外,不使用绝对值。 仅使用差异来计算奖励的价值,因此如何定义这些价值并不重要。 他们只能使用本地信息。 知道球门线的方向是因为您知道最后一个位置,并且您可以计算在正确方向上采取了多少步。
对于轨道外部的所有位置, d1和d2的值为负。 如果检测到此错误(或在其他无效情况下),则返回值None ,表明此举是不可能的,无需进一步调查。 该公式说明了新位置离目标更远的情况,但是如果速度足够高,则仍然值得。 主要规则是最后一条规则,该规则通过减少与目标线的距离和速度来缩放奖励。 这种评分方式绝非理想,也不是唯一。 这只是一个例子。 该模型开发过程的一部分是尝试该功能的更多不同版本。
针对汽车所处的不同状态调用此函数。现在,我们必须讨论如何确定这些不同的状态。
在内部循环中,我们必须通过确定汽车在下一步中可能具有的七个速度中的哪一个来确定下一个状态,并基于该位置和当前位置确定轨道上的可接受位置。 然后,我们使用上面讨论的算法来选择可能的后续步骤之一。 结果代码如下所示:
co = ( start [ 0 ] + startspeed [ 0 ] , start [ 1 ] + startspeed [ 1 ] ) speed = startspeed aspeed = absspeed ( speed ) nextspeeds = possible_speeds ( speed ) curdist = dist [ co [ 0 ] ] [ co [ 1 ] ] scores = score [ co [ 0 ] ] [ co [ 1 ] ] known = known_speeds ( scores , nextspeeds ) bestscore = Qfail bestspeeds = [ ] for s in known: thisscore = scores [ s ] if thisscore == bestscore: bestspeeds. append ( s ) elif thisscore > bestscore: bestscore = thisscore bestspeeds = [ s ] if bestscore < Q0 and len ( known ) != len ( nextspeeds ) : bestscore = Q0 bestspeeds = set ( nextspeeds ) - set ( known ) path = [ ] reached_goal = False while True : path. append ( ( speed , co ) ) if random . random ( ) < epsilon: nextspeed = random . sample ( nextspeeds , 1 ) [ 0 ] else : # Pick according to current score nextspeed = random . sample ( bestspeeds , 1 ) [ 0 ] nextco = ( co [ 0 ] + nextspeed [ 0 ] , co [ 1 ] + nextspeed [ 1 ] ) nextdist = dist [ nextco [ 0 ] ] [ nextco [ 1 ] ] nextaspeed = absspeed ( nextspeed ) r = getr ( curdist , nextdist , nextaspeed , Qgoal ) if not r: # crash score [ co [ 0 ] ] [ co [ 1 ] ] [ nextspeed ] = Qfail break if curdist <= aspeed and nextdist > 10 * aspeed: nextbestscore = Qgoal reached_goal = True else : scores = score [ nextco [ 0 ] ] [ nextco [ 1 ] ] speedspp = possible_speeds ( nextspeed ) known = known_speeds ( scores , speedspp ) bestscore = Qfail bestspeeds = [ ] for s in known: thisscore = scores [ s ] if thisscore == bestscore: bestspeeds. append ( s ) elif thisscore > bestscore: bestscore = thisscore bestspeeds = [ s ] if bestscore < Q0 and len ( known ) != len ( speedspp ) : bestscore = Q0 bestspeeds = set ( speedspp ) - set ( known ) oldval = score [ co [ 0 ] ] [ co [ 1 ] ] [ nextspeed ] if nextspeed in score [ co [ 0 ] ] [ co [ 1 ] ] else Q0 score [ co [ 0 ] ] [ co [ 1 ] ] [ nextspeed ] = ( 1 - alpha ) * oldval + alpha * ( r + gamma * bestscore ) if reached_goal or len ( path ) > 5 * tracklen: break co = nextco speed = nextspeed aspeed = nextaspeed nextspeeds = speedspp curdist = nextdist
这就是所有从固定起点( start )和起始速度( startspeed )直至目标线越过或汽车离开赛道的路径的代码。 在准备循环时,将计算一组完整的变量。 发生这种情况的原因是,在循环的第二部分中,这些变量是为下一步计算的。 我们可以重复使用工作。
变量nextspeeds是下一步的可能速度列表,而bestspeeds是导致得分最高的状态的速度列表,它们是主要的初始化操作。
在循环中,首先将新位置记录在path中 。 它遵循游戏规则确定可能的速度,确保速度不会降为零。 所有可能的新速度都存储在nextspeeds列表中。
从该列表中选择一种速度。 以epsilon表示的概率选择一个随机值。 否则,选择得分最高的下一个状态之一。 如果存在具有相同分数的多个状态,这也是在多种可能性之间进行选择。
epsilon值必须足够小,以允许尝试改善以前发现的良好序列。 紧接着,前n个最佳分数(因为没有做出随机选择)具有(1-ε) n的概率,对于ε= 5% ,这意味着在1000次尝试中有6个一直成功。 如果必须发现长路径,这可能还不够。 ε是重要的超参数。
选择新速度后,将在newco中计算汽车的下一个坐标。
之后,将更新当前位置的分数。 分数变量由坐标和所选速度索引。 通过调用getr来计算奖励,这在上一节中已经看到。 如果坐标不在轨道范围内,我们将分配负分数并终止循环。 用于负奖励的值也是一个超参数。
接下来是我们在上面看到的Q功能更新的实现。 我们从所有可能的下一个状态中确定得分最高的那个,然后使用超参数α和γ更新得分。 唯一的麻烦是分数数组中尚未知道速度值,然后我们必须使用值Q0 。
就这些。 无需编码即可解决问题。 将实现与问题联系起来的唯一细节是getr函数的实现,该函数提供环境信息。 正如我们所看到的,所使用的信息是本地信息。 没有使用有关该问题的全局信息。 该实现使用以下事实:在每种状态下只能执行少量操作,因此该实现可以依赖于字典实现。 对于您可能希望使用此机器学习算法解决的所有可能的问题,情况可能并非如此。 除此之外,该实现可以重用。
以下是经过四百万次运行后的实现输出。
轨道轮廓清晰可见。 在内部,使用不同的灰度等级,显示了轨道上各个位置之间的最佳得分。 由于在轨道的每个位置上的动作可能包含许多不同的速度,并且仅显示一个值,因此该表示方式会省略很多信息。 该图形仍然有用。
红点(在这里几乎看不到,但是您可以在该项目的放大图像)构成了我们所寻找的“解决方案”的最佳途径。 除非算法运行无限长的时间,否则不能保证它是最佳解决方案。 随着时间的推移,该解决方案必定会变得越来越好-示例中的解决方案看起来还不错。 编写特定的算法来更好地解决该问题并不容易。 要查看算法取得的进展,我们可以查看运行较少后的程序状态,例如下面仅运行20,000次的情况。
我们可以看到找到了一个解决方案,但这并不是很好。 所采取的步骤不是直线或规则曲线。 而是用红线绘制各种曲线。 这是可以理解的,因为在开始时该算法基本上执行随机游走,并且如果某些步骤没有立即导致崩溃,则它们将获得正分数。 完成此操作后,该算法大部分(由ε确定)遵循已知良好的路径。 该算法仅偶尔会跳出这些“好的”路径并尝试其他方法。 如果这些步骤都朝着正确的方向前进,那么它们很容易超越以前的良好道路,而汽车所走的整个道路将变得越来越笔直。
有很多方法可以影响学习算法,从ε , α , γ等超参数,到getr函数的不同实现。 您可以从本文中显示的代码开始自己尝试,可以从GitHub上的下载该代码
翻译自:
强化学习入门论文
转载地址:http://trbzd.baihongyu.com/