1.5 扩展案例：tic-tac-toe（井字棋）& 1.6 总
1.5 扩展案例：tic-tac-toe
井字棋
回想一下孩子的井字棋游戏。两名玩家轮流在三乘三的棋盘上比赛。一个玩家打而另一个画⚪，直到一个玩家通过在水平、垂直或对角线上连续放置三个同样的标记而获胜，正如上图所示的游戏中的X玩家所做的那样。如果棋盘上没有一个玩家得到三个相连的标记，则游戏为平局。一个高手可以永远不输，所以假设我们是在与一个不完美的玩家比赛，这个玩家的动作有时是不正确的，从而允许我们获胜。现在，考虑平局和失败对我们同样不利。我们如何设计一个能够在对手的比赛中发现缺陷并学会最大化获胜机会的玩家？
这是一个简单的问题，但无法通过经典技术以令人满意的方式轻松解决。例如，来自博弈论的经典“极大极小”解在这里是不正确的，因为它假设对手用一种特殊的游戏方式，例如，一个极小极大的玩家永远不会达到一个可能失败的游戏状态，即使事实上它总是因为对手的错误游戏而从该状态中获胜。用于顺序决策问题的经典优化方法，如动态规划，可以计算任何对手的最优解，但需要输入该对手的完整说明信息，包括对手在每个棋盘状态下做出每一步的概率。我们假设这些信息对于这个问题来说是先验不可用的，因为它不适用于绝大多数实际感兴趣的问题。另一方面，这种信息可以通过经验来估计，在这种情况下，可以通过与对手进行多次博弈来估计。在这个问题上，人们能做的最好的事情是首先学习对手行为的模型，达到一定的置信度，然后应用动态规划来计算给定近似对手模型的最优解。最后，这与我们在本书后面讨论的一些强化学习方法并没有什么不同。
应用于该问题的进化方法将直接搜索可能策略的空间，以寻找一个有高概率战胜对手的策略。在这里，策略是一条规则，可以指导玩家在游戏期间的每个状态下，在三乘三的棋盘上，每种可能的X和⚪配置都应该采取什么移动。对于所考虑的每一项策略，其获胜概率的估计值将通过与对手进行一定数量的博弈获得。然后，该评估将指导下一步考虑哪些策略。一种典型的进化方法是在策略空间中爬山，依次生成和评估策略，试图获得增量改进。或者，也许可以使用遗传式算法来维护和评估一系列政策。实际上，可以应用数百种不同的优化方法。
使用值函数（value function）方法解决tic-tac-toe问题：建立数字表，每个数字对应游戏中的一个可能状态，每个数字都是我们关于在该状态下获胜概率的最新估计；将此估计值视为状态的价值，整个表是习得函数；如果从状态A获胜的概率大于状态B，则认为状态A有比状态B更大的价值或比B更好。假设我们是X玩家，那么所有可以连续成三个X的状态，获胜的概率都是1，因为已经赢了。类似的，对于另一种相反情况，获胜概率为0，因为已经无法获胜了。将其他状态的初始值设为0.5，表示获胜概率为50%。
和对手玩多场比赛，为了选择行动，检查每一种可能的移动会导致的状态（板上的每个空格对应一个），并查找它们在表里的值。多数情况下，以贪心策略进行移动，选择产生最大价值（具有获胜最大估计可能）的状态。不过偶尔也会随机从其他移动中进行选择，这种被称为探索性行动因为他们可能会引领我们到达我们可能从未到达的状态。在一场比赛中所做的和考虑的一系列行动可以用图1.1表示。
图1.1 一系列的井字棋行动。实线表示游戏中采取的动作；虚线表示我们（强化学习玩家）考虑过但没有采取的行动。我们的第二步是探索性的，这意味着即使是另一个孪生移动，也会导向当我们玩的时候，我们会改变我们在游戏中所处状态的价值。我们试图让他们更准确地估计获胜的可能性。为此，我们将每次贪婪移动后的状态值“备份”到移动前的状态，如图1.1中的箭头所示。更准确地说，更新前一个状态的当前值，使其更接近后一个状态的值。这可以通过将早期状态的值向后期状态的值移动一小部分来实现。如果我们让s表示贪婪移动之前的状态，而s’表示移动之后的状态，那么对s的估计值的更新，表示为V(s)，可以写成
，
其中α是一个称为步长参数的较小的正分数，它影响学习速度。此更新规则是一种时态差异学习方法的示例，之所以称为时态差异学习方法，因为它的变化基于一个是两个不同次估计之间的差。
上面描述的方法在这个任务上执行得相当好。例如，如果步长参数随时间适当减小，那么对于任何固定的对手，该方法都会收敛到在每个给定最佳游戏状态下获胜的真实概率。此外，随后采取的行动（探索性行动除外）实际上是针对这个（不完美的）对手的最佳行动。换言之，该方法收敛到一个最优策略，用于与该对手博弈。如果步长参数没有随着时间的推移一直减小到零，那么该玩家在对抗缓慢改变其游戏方式的对手时也会表现出色。
这个例子说明了进化方法和学习价值函数方法之间的区别。为了评估策略，进化方法会固定策略，并与对手进行多次博弈，或者使用对手的模型模拟多次博弈。获胜频率给出了该策略获胜概率的无偏估计，并可用于指导下一个策略选择。但每次策略改变都是在多次博弈之后才做出的，并且只使用每个博弈的最终结果：在博弈期间发生的事情被忽略。例如，如果玩家赢了，那么其在游戏中的所有行为都会得到认可，而与具体动作对赢的关键程度无关。甚至对从未发生过的动作也给予了赞扬！相反，值函数方法允许对单个状态进行评估。最后，进化方法和价值函数方法都会搜索策略空间，但学习价值函数会利用游戏过程中可用的信息。
这个简单的例子说明了强化学习方法的一些关键特性。首先，强调在与环境互动时学习，在这种情况下是与对手玩家互动。其次，有一个明确的目标，正确的行为需要计划或远见，考虑到个人选择的延迟效应。例如，简单强化学习玩家学习为那些没有远见的对手设置多移动陷阱。强化学习解决方案的一个显著特点是，它可以实现规划和前瞻的效果，而无需使用对手的模型，也无需对未来状态和动作的可能序列进行明确搜索。
虽然这个例子说明了强化学习的一些关键特征，但它非常简单，可能会给人一种印象，即强化学习比实际情况更加有限。虽然tic-tac-toe是一个双人游戏，但强化学习也适用于没有外部对手的情况，即“对抗自然的游戏”强化学习也不局限于将行为分解为单独的事件的问题，如单独的“井字游戏”，只在每个事件结束时才有奖励。当行为无限期地持续下去，并且在任何时候都可以收到各种程度的奖励时，它同样适用。强化学习也适用于那些甚至没有分解成离散时间步骤的问题，如tic-tac-toe的游戏。一般原则也适用于连续时间问题，尽管理论变得更加复杂，我们在介绍性的处理中省略了它。
Tic-tac-toe有一个相对较小的有限状态集，而强化学习可以在状态集非常大甚至无限大时使用。例如，Gerry Tesauro（1992、1995）将上述算法与人工神经网络相结合，学习双陆棋(backgammon)，双陆棋有大约个状态。这么多的状态下，甚至不可能历经超过一小部分的状态。Tesauro的程序比以前的任何程序都能更好地发挥作用，现在已经达到了世界上最好的人类玩家的水平（见第16章）。神经网络为程序提供了根据其经验进行概括的能力，因此在新的状态下，它根据其网络所确定的过去面临的类似状态所保存的信息来选择动作。强化学习系统在具有如此大的状态集的问题中能发挥多大的作用，与它能从过去的经验中进行适当的概括密切相关。正是在这个角色中，我们最需要有强化学习的监督学习方法。神经网络和深度学习（第9.6节）不是实现这一点的唯一方法，也不一定是最好的方法。
在这个tic-tac-toe的例子中，学习是在游戏规则之外没有任何先验知识的情况下开始的，但强化学习绝不意味着学习和智力的列表视图。相反，先前的信息可以通过多种方式融入强化学习中，这对于有效学习至关重要。我们还可以在tic-tac-toe示例中了解真实状态，而强化学习也可以在部分状态被隐藏时应用，或者在学习者看来不同的状态相同时应用。
最后，tic-tac-toe玩家能够向前看，并知道每一个可能的动作将导致的状态。要做到这一点，它必须有一个游戏模型，让它“思考”自己的环境将如何随着可能永远不会采取的行动而变化。许多问题都是这样的，但在另一些问题上，甚至缺乏行动效果的短期模型。强化学习可以应用于任何一种情况。不需要模型，但如果模型可用或可以学习，则可以轻松使用模型（第8章）。
另一方面，有一些强化学习方法根本不需要任何环境模型。无模型系统甚至不能考虑其环境将如何响应单个动作而改变。就其对手而言，tic-tac-toe玩家在这个意义上是无模型的：它没有任何类型的对手模型。由于模型必须相当精确才能发挥作用，因此当解决问题的真正瓶颈是难以构建足够精确的环境模型时，无模型方法可能比更复杂的方法具有优势。无模型方法也是基于模型方法的重要构建块。本书在讨论如何将无模型方法用作更复杂的基于模型的方法的组件之前，先用几章介绍无模型方法。
强化学习可以在系统的高层和底层使用。虽然tic-tac-toe玩家只学会了游戏的基本动作，但没有什么能阻止强化学习在更高层次上发挥作用，因为每一个“动作”本身都可能是一种复杂的问题解决方法的应用。在分层学习系统中，强化学习可以在多个层次上同时工作。
练习1.1：自我游戏 假设上面描述的强化学习算法不是针对随机对手，而是针对自身，双方都在学习。你认为在这种情况下会发生什么？它会学习不同的策略来选择动作吗？
练习1.2：对称性 许多tic-tac-toe位置看起来不同，但实际上是相同的，因为对称性。我们如何修改上述学习过程以利用这一点？这种变化将以何种方式改善学习过程？现在再想想。假设对手没有利用对称性。那样的话，我们应该这样做吗？那么，对称相等的位置必然具有相同的值，这是真的吗？
练习1.3：贪心玩法 假设强化学习玩家采用贪心策略，也就是说，它总是使用使其达到最佳位置的招式。它会学着比一个不灵巧的玩家玩得更好，还是更糟？可能会出现什么问题？
练习1.4：从探索中学习 假设学习更新发生在所有动作之后，包括探索动作。如果步长参数随时间适当减小（但不是探索的趋势），则状态值将收敛到一组概率。当我们从探索性动作中学习时，计算出的两组概率是什么？假设我们继续进行探索性的行动，那么哪一组概率更适合学习？哪一个会带来更多的胜利？
练习1.5：其他改进 你能想出其他方法来改进强化学习玩家吗？你能想出更好的方法来解决这个问题吗？
1.6 总结
强化学习是一种理解和自动化目标导向学习和决策的计算方法。它与其他计算方法的区别在于，它强调代理从与其环境的直接交互中学习，而不依赖于示范性的监督或环境的完整模型。在我们看来，强化学习是第一个认真解决计算从与环境交互学习以实现长期目标产生问题的领域。
强化学习使用马尔可夫决策过程的正式框架来定义学习代理与其环境之间的状态、动作和奖励的交互。该框架旨在成为表示人工智能问题基本特征的简单方法。这些特征包括因果感、不确定性和非确定性以及明确目标的存在。（ These features include a sense of cause and effect, a sense of uncertainty and nondeterminism, and the existence of explicit goals.）
价值和价值功能的概念是我们在本书中考虑的大多数强化学习方法的关键特征。我们认为，价值函数对于策略空间中的有效搜索非常重要。值函数的使用将强化学习方法与进化方法区别开来，后者直接在整个策略的标量评估指导下在策略空间中搜索。
