1.5 扩展实例：井字棋

为了阐明强化学习的中心思想并与其他方法做出对比，下面我们将更加详尽的解读一个实例。 考虑一个大家都很熟悉的儿童游戏--井字棋。在这个游戏中，两位玩家轮流在一个3X3的格子板上画标记，一位画X另一位画O，当一方在格子板中的三个标记构成了横、竖或对角形式的无折连线，即告该方获得游戏胜利；如果格子板填满且无人胜利，则游戏为平局。由于一些熟练玩家在玩这个游戏的时候可以保证不输，为了能够让我们有机会获胜，我们在此将假想对手设定为那些偶尔会犯错误并给予对手获胜机会的不完美玩家。现在假设在游戏中我们既不愿输也不愿平，那么我们如何构建一个可以发现对手失误并且最大化获胜几率的玩家呢？ 尽管这看似一个简单问题，我们也很难通过传统方法轻易地获得令人满意的解决办法。比如，博弈论中经典的minimax算法在此并不适用，因为该算法需假设对手以特定策略下棋，并会因此错失一些获胜机会，举例来讲，一个使用minimax策略的玩家在下井字棋时永远不会主动把自己置于有可能输的境地，即便事实上在这个看似会输的境地下我们经常因为对手的失误而获胜。除minimax方法外，还有一些针对序贯决策的经典优化方法，如动态规划方法，可以对所有类型的对手做出优化的应对方法，但代价是需要获得该对手的全部有用信息，包括对手在所有可能游戏状态下的可能动作的概率集。如同在实际问题中有很大可能出现的情况，假设在下棋时，这些不同环境状态下的落子位置概率，我们预先并不了解，但却可以通过多次与对手对战的经验来建立，那么在解决井字棋问题时，最好的办法就是先建立达到了一定置信度的对手的下棋策略模型，然后通过动态规划演算最优对战策略。上述过程的思想，与本书中后面将会介绍的很多强化学习方法并无很大的区别。 如果针对井字棋问题采用进化方法（evolutionary method），那么进化方法将直接在可选策略空间中选择获胜概率最大的策略（policy），这里的策略是指针对当前棋盘状态（包含3X3格子板中所有可能的X和O配置情况）所应选取的动作，也就是下一步落子的位置。对于所有的策略，我们可以通过进行一定数量的棋局游戏来估计该策略的获胜概率，进而根据估计结果决定接下来要采取的策略。一个典型的进化方法的策略空间将出现逐渐增大的情况，为了实现策略优化改进，进化方法会接连不断地产生并评估策略。或者为了回避策略空间膨胀，也可以采用遗传算法，该算法将维持一定数量的策略并加以评估。事实上，我们还有数百种不同的优化方法可供使用。 下面我们将介绍一种利用价值函数解决井字棋问题的方法。首先，我们建立一个数字表，其中每一个数字对应一个状态，该数字的值表示对对应状态下获胜概率的估计，我们将这种估计视为该状态的价值（value），并将整张表格视为通过学习得到的价值函数。假如处于状态A时的获胜概率估计高于处于状态B时的概率估计，那么我们就认为状态A的价值高于状态B，或者说状态A“优于”状态B。假设我们总是下棋时画X的一方，那么所有出现了三个X排成一排（横、竖或斜）的状态的获胜概率都为1，因为此时我们已经获胜了。同样的，对于所有出现了三个O排成一排的状态，或者棋盘填满的状态，获胜概率都为0，因为在这个状态下我们已经不可能获胜。除了包含上述情况的状态，将所有其他状态的初始值设定为0.5，代表假想处于当前状态获胜的机会是50%。 在初始设定了价值表后，我们与对手进行多局井字棋游戏。在选择动作的过程中，我们在价值表中查找所有可能采取的动作会进入的下一个状态的价值估计，并以此为据选择将要采取的动作。大多数时候我们将采用贪婪的动作策略，也就是选择能使我们进入价值最大的状态的动作，该最大价值也就意味着最大的获胜概率。然而，我们偶尔也将随机选择一些动作，这种非贪婪的行为叫做探索（exploratory），因为它使我们经历一些我们可能以贪婪策略永远无法达到的状态，一局游戏期间我们考虑或采取的行动可以被绘制成如图1.1的形式。 P8图1.1 图1.1：井字棋动作序列。实线代表游戏时采取的动作；虚线代表我们（强化学习玩家）考虑但未采取的动作。第二个动作是一个探索动作，意味着尽管存在另一个优先级更高的动作（通向e星）,该仍然动作被选择。探索动作不会产生学习过程，但是其他动作将产生学习过程，正如文中诉述，学习过程使估计的价值从树的后节点传递至前节点，实现价值的更新， 如图中曲线箭头所示。 在进行游戏的过程中，我们不断改变状态的价值，力求使其成为更加精确的获胜概率估计，为了做到这一点，我们将采取贪婪动作后的状态的价值“回溯”给采取动作前的状态，如图1.1中箭头所示。更精确的讲，前状态当前的价值被更新为更接近后状态的价值的值，这种更新可以通过将前状态价值向着后状态价值的方向做一定的微调实现。如果我们用s表示贪婪动作前的状态，用s‘表示贪婪动作后的状态，那么对于s的价值估计，表示为V(s)，的更新可以表示为V(s)←V(s)+alpha[V(s’)-V(s)],其中alpha是一个称为步长参数（step-size parameter）的正小数，它影响着学习的速率。这种价值更新方式是时序差分（temporal-difference）学习法的一个例子，这么称呼它的原因是由于他通过差分V(s’)-V(s)，也就是两个时间步的估计值的差，来更新价值。 上边描述的方法在解决井字棋任务时有很好的表现，比如，在步长参数随时间合理递减的情况下，针对确定的对手，这种方法最终会收敛至各状态下采取最优策略的获胜概率真值，此外，后续采取的动作（除探索动作）事实上将是有利于战胜对手的最优动作，换言之，时序差分学习法会收敛至战胜某确定对手的最优策略。即使步长参数不是一直递减至0，那么该方法也将取得良好表现，只是动作策略的改变会比较缓慢。 井字棋的例子说明了进化方法与学习价值函数算法的区别。进化方法通过选定一个策略然后进行多次实际对战或基于对手模型的仿真模拟来评估一个策略，根据该过程中获胜的频率，可得出关于被评估策略的无偏获胜概率估计，从而用来指导下一个策略的选择；但进化方法仅在多次游戏后更新一次策略，且只用到了每局游戏的结果信息：游戏过程信息被忽略。为什么说进化方法只利用结果信息，具体来讲，当采用该方法时如果玩家获胜，那么该局游戏中所有玩家行为均被正向更新，而游戏中某个特定行为对于获胜是否有利将被忽视，甚至游戏中未发生的动作同样会被正向更新！与此相反，在价值函数算法中，允许对单独的状态进行评估。总结来讲，进化方法与价值函数算法在策略优化过程中都会搜索策略空间，但学习价值函数算法有效的利用了游戏过程信息，而进化方法仅利用了游戏结果信息。 这个简单的井字棋例子阐明了一些强化学习方法的关键特征。首先，该例子强调了与环境交互时的学习过程，在本例中为与对手的棋局博弈；第二，该例子有明确的目标，以及需要规划或预见才能进行正确选择的有反馈延迟的动作，比如，一个简单的强化学习玩家将会为一个短视的对手建立一个多步的圈套，这是强化学习一个惊人的特点，该方法可以实现规划和前瞻的效果而不依靠对手的模型或对未来可能状态和动作的完全搜索。 尽管这个例子阐明了一些强化学习的关键特征，但它过于简单可能会给人留下强化学习适用问题很局限的印象，虽然本例中应用强化学习方法解决的井字棋任务是一个双人游戏问题，但强化学习同样可以应用于没有外部对手的情况下，譬如说，在“与自然对抗的游戏”中。强化学习同样不止局限于解决可分割为段的执行有限动作的问题，如井字棋，只在每一段有限动作结束后获得奖励，它同样适用于随时可能获得不同量级奖励的连续无限动作问题。尽管理论会更加复杂，但强化学习还可以应用于无法分割为时间步的问题中，其一般原理同样适用于连续时间问题，在本章介绍性内容中我们忽略该部分的详细阐述。 虽然上文仅将强化学习的思想应用于状态有限且较少的井字棋实例中，但强化学习同样可以应用在状态集非常大甚至无限的情况。比如Gerry Tesauro (1992, 1995)使用强化学习与人工神经网络相结合的方法，训练机器进行西洋双陆棋游戏，该游戏约有10的20次方个状态，对于如此之多的状态，想遍历其中的一小部分几乎都是不可能完成的任务。 Tesauro采用该方法运行的程序实现了比之前所有程序都好的双陆棋游戏结果，目前该机器的双陆棋水平甚至可以和全世界最强大的双陆棋选手比肩（详见16章）。该算法中的神经网络为程序提供了从游戏经验中归纳推演的能力，所以在面对新的未知的状态时，它可以利用网络，根据过去经历过的与未知状态相似的状态的经验，得到应该执行的动作。对于强化学习系统来讲，一个算法可以在解决大状态集问题时有多好的表现，与其能从过去经验中总结归纳出多恰当的模型密切相关。因此为了解决此类大状态集问题，迫切的需要将监督学习和强化学习相结合的算法，在实现这一目标的过程中，神经网络和深度学习（9.6节）并不是唯一的或必然最佳的实现方式。 在这个井字棋的游戏中，除游戏规则外，学习过程不具备任何先验性经验，但这绝不意味着强化学习在整个学习过程中都是白纸一张，正相反，先验信息可以通过很多方式被获得和采用，而且可能对高效的学习过程中起到非常重要的作用。在井字棋例子中我们可以获得系统所处的真实完整状态，但即便在系统部分状态被隐藏或状态迷惑性很强的问题上，我们同样可以采用强化学习的方法。 最后，在井字棋游戏中，玩家是可以预测所采取的动作将到达的棋盘状态的，为了实现这一点，玩家必须具备关于游戏的模型，该模型可以帮助他“考虑”环境对那些实际未发生的动作将会做出的反应。实际情况中有很多类似的具备模型的问题，但在另一些问题中，即便是短期的动作-效果模型也是不具备的，而强化学习方法在这些情况中都可以自如的被运用，也就是说模型对于强化学习方法来讲并不是必须的，但模型可以轻易的被使用来提升算法的表现（第8章）。 另一方面，还有一些根本不需要任何环境模型的强化学习方法。无模型系统甚至无法估计一个简单动作将会对环境带来的变化，在这个角度讲，考虑到对弈中的对手，井字棋就是一种无模型系统：没有对手的任何模型。因为模型必须具备一定的精度才能对解决问题变得有用，因此当建立足够精度的环境模型成为解决问题的瓶颈时，不需要模型的方法较一些复杂方法更有优势。此外，不需要模型的方法也是基于模型方法的重要组成部分。本书将用很多章节介绍无模型方法，而后将介绍如何将这些方法引入到复杂的基于模型方法中。 强化学习既可用于系统的较高决策层，也可应用于较低的决策层。尽管井字棋玩家只是对下棋策略进行学习，但是这并不妨碍强化学习方法应用于较高的决策层，在这些决策中，所执行的动作本身可能就是对解决问题方法的选择。在分层学习系统中，可以同时在几个层级中使用强化学习方法。 练习1.1:自我对局 假设，在游戏过程中不选取随机的对手，而使用强化学习算法与自身对抗并学习。在这种情况下你认为会发生什么？这会导致强化学习最终得到不同的动作选择策略吗？ 练习1.2:对称性 由于对称性的缘故，尽管一些井字棋布局位置看似不同但实际上是相同的。假如我们考虑到上面这点，我们如何修正学习过程？这种变化会以什么方式改进学习过程？再来考虑，假设对手未利用对称性的这一优点，那么我们应该考虑吗？并且对称的位置是否必定具备相同的价值？ 练习1.3:贪婪策略 假设采用强化学习算法的玩家是贪婪的，也就是说它总会选择价值最高的位置落子，他会比非贪婪的玩家表现的更好吗？还是更坏？这会引发什么问题？ 练习1.4:从探索中学习 假设在包括探索动作的所有动作后都进行学习更新，如果补偿参数一直恰当的递减（探索概率不以相同趋势变化），那么状态价值会收敛到一组概率值。当我们在探索动作结束后，进行学习或不进行学习时两组的概率都是怎样的？假设我们一直会做探索动作，哪一组概率值更有利于学习？哪组的学习结果会带来更多的胜利？ 练习1.5:其他改进 你能想出其他改进强化学习算法玩家的方法吗？你能想出其他更好的解决井字棋的办法吗？