Chapter 2 Multi-armed Bandits
强化学习与其他类型学习的区别最重要的特征是它使用训练信息来评估所采取的行动，而不是通过给出正确的行动来指导。这就是为什么需要积极探索，明确地寻找良好的行为。纯粹的评价性反馈表明所采取的行动有多好，但不是可能的最好还是最坏的行动。另一方面，纯粹的指导性反馈表明要采取的正确行动，而不是实际采取的行动。这种反馈是监督学习的基础，监督学习包括模式分类、人工神经网络和系统辨识的大部分内容。在纯粹的形式上，这两种反馈是截然不同的：评价性反馈完全依赖于所采取的行动，而指导性反馈则独立于所采取的行动。
在本章中，我们将在一个简化的环境中研究强化学习的评估方面，即不涉及学习在多个情况下采取行动。这种非关联性的设置是在这种情况下，大多数涉及评价性反馈的前期工作已经完成，它避免了完全强化学习问题的复杂性。通过研究这个案例，我们可以更清楚地看到评价性反馈是如何从指导性反馈中产生的，并且可以与指导性反馈相结合。
我们所探讨的特定的非关联的、评价性反馈问题是k臂**机问题的一个简单版本。我们用这个问题来介绍一些基本的学习方法，我们在后面的章节中扩展这些方法来应用于完全强化学习问题。在本章的最后，我们通过讨论当**机问题变得关联时，即当最佳操作取决于情况时，会发生什么，从而向完全强化学习问题更进一步。
2.1 A k-armed Bandit Problem
考虑以下学习问题。您会反复面临在不同的选项或操作中进行选择。每次选择之后，你都会从一个平稳的概率分布中得到一个数字奖励，这个概率分布取决于你选择的行动。你的目标是在一段时间内最大限度地获得预期的总回报，例如，超过1000个动作选择，或时间步骤。
这是k臂**机问题的原始形式，因此被比喻为*，或“单臂**机”，只是它有k杆而不是一杆。每一个动作选择就像*的一个杠杆的游戏，奖励就是中大奖的奖金。通过反复的行动选择，你将通过集中你的行动在最好的杠杆上获得最大的收益。另一个类比是医生在一系列重病患者的实验治疗中进行选择。每一次行动都是对治疗的选择，每一次奖励都是患者的生存或幸福。今天，“**机问题”一词有时被用来概括上述问题，但在本书中，我们用它来指代这个简单的例子。
在我们的k臂**机问题中，每一个k行动都有一个预期的或平均的回报，只要这个行动被选中；让我们称之为该行动的价值。我们将在时间步骤t上选择的动作表示为At，相应的奖励表示为Rt。任意动作a的值，q（a）是假定选择a的预期回报：
如果你知道每一个动作的价值，那么解决k臂**机问题将是微不足道的：你总是选择价值最高的行动。我们假设您不一定知道操作值，尽管您可能有估计值。我们将时间步骤t处动作a的估计值表示为Qt（a）。我们希望Qt（a）接近q（a）。
如果您维护操作值的估计值，则在任何时间步中至少有一个操作的估计值最大。我们称之为贪婪行为。当你选择其中一个行动时，我们说你是在利用你目前对这些行动价值的认识。如果您选择了一个nongreedy操作，那么我们称您正在开发，因为这使您能够改进对nongreedy操作价值的估计。开发是正确的做法，以最大限度的预期回报在一个步骤，但从长远来看，开发可能会产生更大的总回报。例如，假设一个贪婪行为的价值是确定的，而其他几个行为被估计为几乎一样好，但有很大的不确定性。至少你不知道其中一个比贪婪的行为更好。如果你在前面有很多时间步骤来选择动作，那么最好去探索一下nongreedy的动作，找出其中哪一个比贪婪的动作更好。在探索过程中，短期回报较低，但长期回报较高，因为在你发现了更好的行动之后，你可以多次利用它们。由于任何单一的行动选择不可能同时进行勘探和开发，人们常常提到勘探和开发之间的“冲突”。
在任何特定的情况下，探索或开发 更好的方法都取决于估计值的精确值、不确定性和剩余步骤的数量。有许多复杂的方法，以平衡探索和开发的特殊数学公式的k-臂**机和相关问题。然而，这些方法大多对平稳性和先验知识做了很强的假设，这些假设在大多数应用程序和我们在后面章节中考虑的完全强化学习问题中都是违反或不可能验证的。当这些方法的理论假设不适用时，这些方法的最优性或有界损失的保证就不那么令人满意了。
在这本书中，我们并不担心以复杂的方式平衡探索和开采；我们只关心如何平衡两者。在这一章中，我们提出了几种简单的平衡方法来解决k臂**机问题，并表明它们比通常利用的方法更有效。平衡探索和开发的需要是强化学习中出现的一个独特挑战；我们对k臂**机问题的简单解释使我们能够以一种特别明确的形式表明这一点。
2.2 Action-value Methods
首先，我们将更仔细地研究用于估计操作值的方法，以及使用这些估计值来做出操作选择决策的方法，我们将这些方法统称为操作值方法。回想一下，一个行动的真正价值是选择该行动时的平均回报。估计这一点的一种自然方法是平均实际获得的奖励：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NiRYS99C-1596449775714)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803181056.png)]
其中，predicatedent表示随机变量，如果predicate为真，则为1，否则为0。如果分母为零，那么我们将Qt（a）定义为某个默认值，例如0。当分母变为无穷大时，根据大数定律，Qt（a）收敛到q（a）。我们称之为估计行动价值的样本平均法，因为每次评估都是相关奖励样本的平均值。当然，这只是估计动作值的一种方法，不一定是最好的方法。然而，现在让我们继续使用这个简单的估计方法，并转向如何使用估计来选择操作的问题。
最简单的动作选择规则是选择一个估计值最高的动作，也就是上一节定义的贪心动作之一。如果有一个以上的贪婪行为，那么将以某种任意的方式在其中进行选择，也许是随机的。我们把这个贪婪的动作选择方法写成
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mAyc8ks6-1596449775717)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803181025.png)]
其中，argmax a表示下面的表达式最大化（任意断开连接）。贪婪的行为选择总是利用现有的知识来最大限度地获得即时的回报；它根本不花时间去抽样明显较差的行为，看看它们是否真的更好。一个简单的选择是在大多数时间里贪婪行事，但每隔一段时间，比如说以小概率”，而不是从所有概率相等的动作中随机选择，而不依赖于动作值的估计值。我们将使用这种近乎贪婪的行为选择规则的方法称为“贪婪方法”。这些方法的一个优点是，随着步数的增加，每个动作将被采样无限次，从而确保所有Qt（a）收敛到各自的q（a）。这当然意味着选择最佳行动的概率收敛到大于1-e“，也就是说，接近确定性。然而，这些仅仅是渐进式的保证，对方法的实用性几乎没有提及。
练习2.1 在贪心行为选择，对于两个动作且“e=0.5”的情况，选择贪心动作的概率是多少？
2.3 The 10-armed Testbed
为了粗略地评估贪婪和贪婪行为值方法的相对有效性，我们在一组测试问题上对它们进行了数值比较。这是一组随机产生的2000个k武装强盗问题，k=10。对于每一个bandit问题，如图2.1所示，动作值，q（a），a=1，…，10，
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X21oqOn8-1596449775719)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803181129.png)]
图2.1:10臂试验台上的一个**机问题示例。根据均值为零和单位方差的正态分布，选择十个行动中每个行动的真实值q（a），然后根据这些灰色分布的平均值q（a），单位方差正态分布来选择实际奖励。
根据均值为0和方差为1的正态（高斯）分布进行选择。然后，当应用于该问题的学习方法在时间步长t处选择动作时，实际奖励Rt从平均q（At）和方差为1的正态分布中选择。这些分布在图2.1中以灰色显示。我们称这组测试任务为10个武装的测试台。对于任何一种学习方法，我们都可以衡量它的性能和行为，因为它在应用于一个**机问题时，经过1000多个时间步的经验改进。这就是一次跑步。在2000次独立运行中重复此过程，每次运行都有不同的**机问题，我们获得了学习算法平均行为的度量。
图2.2比较了贪婪方法和两个“-greedy方法（=0.01和”=0.1），如上所述，在10个武装的试验台上。所有的方法都使用样本平均技术（初始估计值为0）形成它们的动作值估计值。上图显示的是经验带来的预期回报的增加。贪心法一开始比其他方法进步稍快，但后来降到了一个较低的水平。它的每一步只获得了大约1美元的回报，而在这个试验台上，最好的可能是1.55美元。从长远来看，贪婪的方法表现得更差，因为它经常被困在执行次优操作上。
图2.2：在10个臂的试验台上“e-greedy action-value方法的平均性能。这些数据是平均超过2000次运行，并存在不同的bandit问题。所有的方法都使用样本平均值作为他们的行动值估计。
下面的图表明，贪心法只在大约三分之一的任务中找到了最优动作。在另外三分之二的人中，其最佳行动的初始样本令人失望，而且再也没有回归。贪婪的方法最终表现得更好，因为他们继续探索并提高识别最佳行为的机会。“e=0.1方法探索的更多，通常更早地找到最佳操作，但从未在超过91%的时间内选择该操作。“e=0.01方法改进得比较慢，但最终在图中所示的两个性能度量上都会比“e=0.1”方法更好。也可以随着时间的推移减少e以尽量获得高值和低值的最佳值。
与greedy方法相比，e-greedy方法的优势取决于任务。例如，假设奖励方差更大，比如说10而不是1。有了噪声奖励，就需要更多的探索才能找到最佳的行动，而且“-贪婪的方法应该比贪婪的方法表现得更好。另一方面，如果奖励方差为零，那么贪心方法在尝试一次后就会知道每个动作的真实值。在这种情况下，贪婪的方法实际上可能表现得最好，因为它很快就会找到最佳的动作，然后再也不会去探索。但即使是在确定性的情况下，如果我们削弱其他一些假设，也有很大的优势。例如，假设bandit任务是非平稳的，也就是说，动作的真实值随着时间的推移而改变。在这种情况下，即使是在确定性的情况下，也需要进行探索，以确保其中一个非理性行为没有变为比贪婪行为更好的行为。我们将在接下来的几章中看到，非平稳性是强化学习中最常见的情况。即使底层任务是固定的和确定的，学习者也会面对一组类似bandit的决策任务，每一个任务都会随着学习的进行和agent的决策策略的改变而变化。强化学习需要在探索和开发之间取得平衡。
练习2.2：Bandit示例考虑一个k武装的Bandit问题，k=4个动作，表示为1、2、3和4。考虑将bandit算法应用到这个问题中，使用“-贪心行动选择，样本平均行动值估计，以及Q1（a）=0的初始估计值。假设行动和奖励的初始序列为A1=1，R1=1，A2=2，R2=1，A3=2，R3=2，A4=2，R4=2，A5=3，R5=0。在这些时间步骤中，有些“案例可能已经发生，导致随机选择一个操作。这肯定发生在哪个时间段？这可能发生在哪个时间点？
练习2.3在图2.2所示的比较中，从长期来看，哪种方法在累积回报和选择最佳行动的概率方面表现最好？会好多少？定量地表达你的答案。
2.4 Incremental Implementation
到目前为止，我们讨论过的行动价值评估方法都是将行动价值作为观察到的奖励的样本平均值。现在我们来讨论如何以计算效率高的方式来计算这些平均值，特别是使用常数内存和常数每时间步计算。
为了简化符号，我们把注意力集中在单个动作上。现在让Ri表示第i次选择这个动作后得到的奖励，让Qn表示它被选择n-1次后对其动作值的估计，我们现在可以简单地写为
最明显的实现是保持所有奖励的记录，然后在需要估计值时执行此计算。然而，如果这样做了，那么内存和计算需求将随着时间的推移而增长，因为会看到更多的回报。每一个额外的奖励都需要额外的内存来存储它，并需要额外的计算来计算分子的总和。
正如你可能怀疑的那样，这不是真的必要。很容易设计出增 量公式来更新平均值，处理每个新的奖励所需的计算量很小。给定Qn和第n个奖励，Rn，所有n个奖励的新平均值可以通过
即使n=1，也可以得到任意Q1的Q2=R1。这个实现只需要Qn和n的内存，每个新的奖励只需要很小的计算量（2.3）。
这个更新规则（2.3）的形式在本书中经常出现。一般形式是
表达式[Target — OldEstimate]是估计中的错误。它是通过向“目标”迈出一步来降低的。目标被假定指示了一个理想的移动方向，尽管它可能有噪音。例如，在上面的例子中，目标是第n个奖励。
请注意，增量方法（2.3）中使用的步长参数（StepSize）随时间步长而变化。在处理动作a的第n个奖励时，该方法使用步长参数1/n。在本书中，我们用或更一般地用at（a）表示步长参数。
使用递增计算的样本平均值和“e-贪心操作选择的完整bandit算法的伪代码如下框所示。假定函数bandit（a）执行一个操作并返回相应的奖励。
2.5 Tracking a Nonstationary Problem
到目前为止讨论的平均方法适用于平稳bandit问题，即奖励概率不随时间变化的bandit问题。如前所述，我们经常遇到强化学习问题，这些问题往往是非平稳的。在这种情况下，对最近的奖励给予更多的重视，而不是过去很久的奖励，这是有意义的。最常用的方法之一是使用恒定步长参数。例如，用于更新n-1个过去奖励的平均Qn的增量更新规则（2.3）修改为
其中步长参数a（0,1）为常数。这导致Qn+1是过去奖励和初步估计Q1的加权平均值：
我们称其为加权平均是因为权重的和
注意，给予奖励的权重α（1−α）n−i取决于观察到的奖励数量n−i。数量1−α小于1，因此，给予骑乘的权重随着干预奖励数量的增加而减少。实际上，权重根据1−α上的指数呈指数衰减。（如果1−α=0，那么所有的权重都会在最后一个奖励Rn上，因为惯例是00=1。）因此，这有时被称为指数近因加权平均数。
有时，根据步长改变步长参数是很方便的。让αn（a）表示用于处理第n次选择动作a后获得的奖励的步长参数。如前所述，选择αn（a）=1是样本平均法的结果，根据大数定律，该方法保证收敛到真实的动作值。当然，对于{αn（a）}序列的所有选择，并不能保证收敛。随机逼近理论中的一个著名结果为我们提供了保证概率1收敛所需的条件：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ecdwztvw-1596449775733)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803164201.png)]
第一个条件是要保证步长足够大，以最终克服任何初始条件或随机波动。第二个条件保证最终步骤变小，以确保收敛。
注意，对于样本平均情况，αn（a）=1/n，这两个收敛条件都满足，但对于步长参数恒定的情况，αn（a）=α，则不满足这两个条件。在后一种情况下，第二个条件不满足，这表明估计值从未完全收敛，而是根据最近收到的奖励继续变化。如前所述，在非平稳环境中，这实际上是理想的，而实际上非平稳的问题在强化学习中最常见。此外，满足条件（2.7）的步长参数序列通常收敛速度非常慢，或需要进行大量调整才能获得满意的收敛速度。虽然满足这些收敛条件的步长参数序列通常用于理论工作，但在实际应用和实证研究中却很少使用。
练习2.4:如果步长参数αn不是常数，则估计值Qn是先前收到的奖励的加权平均值，其权重与（2.6）中给出的不同。对于一般情况，类似于（2.6），在步长参数序列方面，每个先前奖励的权重是多少？
练习2.5（编程）设计并进行一个实验，以演示样本平均法在处理非平稳问题时的困难。使用10臂试验台的改进版，其中所有q∗（a）开始相等，然后进行独立的随机行走（例如，在每个步骤中为所有q∗（a）添加一个平均零和标准偏差为0.01的正态分布增量）。使用递增计算的样本平均值和另一个使用恒定步长参数α=0.1的动作值方法绘制图，如图2.2所示。使用ε=0.1及更长的行程，例如10000步。
2.6 Optimistic Initial Values
到目前为止，我们所讨论的方法都在一定程度上依赖于初始作用值估计，Q1（a）。在统计学的语言中，这些方法因其初始估计而有偏差。对于样本平均法，一旦至少选择了一次所有操作，偏差就会消失，但对于常数α的方法，偏差是永久性的，尽管会随着时间的推移而减小，如（2.6）所示。在实践中，这种偏见通常不是问题，有时会很有帮助。缺点是，初始估计值实际上变成了一组必须由用户选择的参数，如果只是将它们全部设置为零。好的一面是，它们提供了一种简单的方法来提供关于预期回报水平的一些先验知识。
初始动作值也可以作为鼓励探索的简单方法。假设我们没有像在10个臂的试验台上那样将初始动作值设置为零，而是将它们全部设置为+5。回想一下，这个问题中的q∗（a）是从均值为0，方差为1的正态分布中选取的。因此，+5的初步估计是非常乐观的。但这种乐观主义鼓励人们去探索行动价值观方法。学习者选择的“其他动作”比“开始接受奖励”要少。结果是，在值估计收敛之前，所有操作都要尝试多次。即使贪婪的行为总是被选中，系统也会进行大量的探索。
图2.3显示了贪婪方法在10个武装bandit试验台上的性能，使用Q1（a）=+5，所有a。为了比较，还显示了Q1（a）=0的ε-贪婪方法。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DCmrVEdC-1596449775734)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803170056.png)]
图2.3：优化初始行动值估计对10臂试验台的影响。两种方法都使用恒定步长参数，α=0.1。
最初，优化的方法表现得更差，因为它探索得更多，但最终它表现得更好，因为它的探索随着时间的推移而减少。我们称这种技术为鼓励勘探优化初始值。我们认为这是一个简单的技巧，可以相当有效地解决平稳问题，但它远远不是鼓励探索的普遍有用的方法。例如，它不太适合处理非平稳问题，因为它的勘探动力本质上是暂时的。如果需要一个新的探索方法来帮助创建一个新的任务。实际上，任何以特殊方式关注初始条件的方法都不可能对一般的非平稳情况有所帮助。时间的开始只发生一次，因此我们不应过分关注它。这种批评同样适用于样本平均法，它也将时间的开始视为一个特殊事件，以相等的权重平均所有随后的奖励。然而，所有这些方法都是非常简单的，其中一种或几种简单的组合在实践中往往是足够的。在本书的其余部分中，我们经常使用这些简单的探索技巧。
练习2.6：神秘的峰值 图2.3所示的结果应该是非常可靠的，因为他们平均超过2000个人，随机选择10个臂**机任务。那么，为什么优化方法的曲线早期会出现振荡和尖峰呢？换句话说，是什么使得这种方法在特定的早期步骤中表现得特别好或更差？
2.7 Upper-Confidence-Bound Action Selection
需要探索，因为行动价值估计的准确性总是存在不确定性。贪婪的行为是目前看起来最好的行为，但其他一些行为实际上可能更好。ε-贪婪行为选择迫使非贪婪行为被尝试，但不加选择，不偏爱那些几乎贪婪或特别不确定的行为。更好的做法是根据非贪婪行为的实际最优潜力，同时考虑到它们的估计值接近最大值的程度以及这些估计值中的不确定性。一种有效的方法是根据
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9Dk6KjKw-1596449775735)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803171218.png)]
式中，lnt表示t的自然对数（e≈2.71828必须提高到等于t的数字），Nt（a）表示在时间t之前选择动作a的次数（2.1中的分母），数字c>0控制勘探程度。如果Nt（a）=0，则a被认为是最大化作用。
这种上置信限（UCB）动作选择的思想是平方根项是对a值估计中的不确定性或方差的度量。因此，被最大化的量是作用a可能真值的一个上界，c决定了置信水平。每次选择a时，不确定度大概会减少：Nt（a）增加，并且，当它出现在分母中时，不确定项减少。另一方面，每次选择a以外的动作时，t增加，但Nt（a）不增加；因为t出现在分子中，不确定度估计增加。使用自然对数意味着，随着时间的推移，增加的量会变小，但是是无限的；最终将选择所有的动作，但是值估计值较低的动作，或者已经频繁选择的动作，将随着时间的推移，频率逐渐降低。
UCB在10臂试验台上的结果如图2.4所示。UCB通常表现良好，如这里所示，但比ε-贪婪更难扩展到本书其余部分考虑的更一般的强化学习设置。一个困难是处理非平稳问题；需要比第2.5节中介绍的方法更复杂的方法。另一个困难是处理大的状态空间，特别是当使用本书第二部分开发的函数近似时。在这些更高级的设置中，UCB动作选择的想法通常是不实际的。
2.8 Gradient Bandit Algorithms
到目前为止，在本章中，我们已经考虑了估计动作值并使用这些估计值来选择动作的方法。这通常是一个很好的方法，但不是唯一可能的方法。在本节中，我们考虑学习每个动作a的数值偏好，我们表示Ht（a）。偏好越大，采取行动的频率就越高，但偏好对回报没有解释力。只有一种行为相对于另一种行为的相对偏好才是重要的；如果我们在所有偏好中增加1000个，则对根据软最大分布（即吉布斯或玻尔兹曼分布）确定的行动概率没有影响，如下所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kUSCrvkI-1596449775736)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803172237.png)]
图2.4:10臂试验台上UCB动作选择的平均性能。如图所示，UCB通常比ε-贪心行为选择更好，除了在前k个步骤中，当它在尚未试验的动作中随机选择时。
在这里，我们还引入了一个有用的新符号，πt（a），表示在时间t时采取行动的概率。最初，所有偏好都是相同的（例如，H1（a）=0，对于所有a），因此所有行动都有相同的被选择概率。
练习2.7表明，在两个动作的情况下，软最大分布与统计学和人工神经网络中常用的logistic函数或sigmoid函数给出的分布相同。
有一种基于随机梯度上升思想的自然学习算法。在每个步骤中，在选择操作并收到奖励Rt后，首选项将通过以下方式更新：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ia1Lupoh-1596449775737)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803172506.png)]
其中α>0是一个步长参数，而Rt∈R是直到时间t（包括时间t）的所有奖励的平均值，可以按照第2.4节（或第2.5节，如果问题是非平稳的）进行增量计算。Rtterm作为比较奖励的基线。如果奖励高于基线，那么未来服用的概率增加，如果奖励低于基线，则概率降低。未选定的动作将朝相反的方向移动。
图2.5显示了梯度bandit算法在10臂试验台的一个变体上的结果，其中真实的期望回报是根据正态分布（平均值为+4而不是零）来选择的（与之前一样，单位方差相同）。所有奖励的上移对梯度bandit算法没有任何影响，因为奖励基线项可以瞬间适应新的水平。但是，如果忽略基线（即，如果在（2.10）中¦Μrt取为常数零），则性能将显著降低，如图所示。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2thDYrPP-1596449775738)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803172949.png)]
图2.5：当q∗（a）被选为接近+4而不是接近零时，在10个武装试验台上，梯度bandit算法有无奖励基线的平均性能。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L6a4C1dk-1596449775739)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803172931.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V5Cg4fxR-1596449775741)(https://raw.githubusercontent.com/wangyifan2018/cloudimg/master/data20200803173333.png)]
2.9 Associative Search (Contextual Bandits)
到目前为止，在本章中，我们只考虑了非关联任务，即不需要将不同的行为与不同的情况相关联的任务。在这些任务中，学习者要么试图在任务静止时找到一个最佳动作，要么在任务不稳定时试图跟踪随时间变化的最佳动作。然而，在一般的强化学习任务中，有不止一种情况，其目标是学习一种策略：从各种情况映射到在这些情况下最好的行动。为了为整个问题做好准备，我们简要讨论了非关联任务扩展到关联设置的最简单方法。
举个例子，假设有几个不同的k臂**机任务，并且在每一步中你都会随机选择其中一个。因此，**机任务一步一步地随机变化。在你看来，这是一个单一的、非平稳的k武装强盗任务，其真实动作值在一步一步地随机变化。您可以尝试使用本章中描述的可以处理非平稳性的方法之一，但是除非真正的操作值变化缓慢，否则这些方法将无法很好地工作。但是，现在假设，当为您选择一个bandit任务时，您会得到一些关于其身份的独特线索（但不是它的动作值）。也许你面对的是一台真正的*，它会随着动作值的变化而改变显示器的颜色。现在，您可以学习一个策略，将每个任务（由您看到的颜色表示）与面对该任务时要采取的最佳操作相关联，例如，如果是红色，请选择arm 1；如果是绿色，则选择arm 2。有了正确的策略，您通常可以做得比没有任何信息来区分一个**机任务和另一个**机任务要好得多。
这是一个关联搜索任务的例子，之所以称之为关联搜索任务，是因为它包括尝试和错误学习来搜索最佳操作，并将这些操作与最佳操作的情况相关联。在文献中，联想搜索任务通常被称为上下文**机。联想搜索任务介于k臂**机问题和完全强化学习问题之间。它们就像是完全强化学习问题，因为它们涉及到学习一项政策，但像我们的k臂**机问题，因为每一个行动只影响直接的回报。如果允许行动影响下一个情境以及奖励，那么我们就有了完全强化学习问题。我们将在下一章提出这个问题，并在本书的其余部分考虑其影响。
练习2.8假设你面对一个双臂强盗任务，其真实动作值随时间的推移而随机变化。具体地说，假设对于任何时间步，动作1和动作2的真值分别为0.1和0.2，概率为0.5（情况A），0.9和0.8（概率0.5）（情况B）。如果你在任何一步都不知道自己面临的是哪一种情况，那么你能达到的最佳成功预期是什么？你应该如何表现才能实现它？现在假设在每一步中，你都被告知你面对的是案例A还是案例B（尽管你仍然不知道真正的行动价值）。这是一个关联搜索任务。在这项任务中，你对成功的最大期望是什么？你应该如何行动来实现它？
2.10 Summary
在本章中，我们介绍了几种平衡勘探和开采的简单方法。ε-贪心方法随机选择一小部分时间，而UCB方法则是确定性地选择，但通过在每一步都微妙地偏爱迄今为止接收到较少样本的行为来实现探索。梯度bandit算法估计的不是动作值，而是动作偏好，并使用软最大分布以分级、概率的方式偏好更优先的动作。乐观地初始化估计值的简单权宜之计甚至会导致贪婪的方法进行大量的探索。
很自然地会问这些方法中哪一种是最好的。尽管这是一个很难回答的问题，但我们可以在本章中使用的10臂的试验台上运行它们，并比较它们的性能。复杂的是它们都有一个参数；为了进行有意义的比较，我们必须将它们的性能视为参数的函数。到目前为止，我们的图表显示了每种算法和参数设置随时间的学习过程，以生成该算法和参数设置的学习曲线。如果我们为所有算法和所有参数设置绘制学习曲线，那么图形将过于复杂和拥挤，无法进行清晰的比较。相反，我们用1000步的平均值来总结一条完整的学习曲线；这个值与学习曲线下的面积成正比。图2.6显示了本章中各种bandit算法的测量值，每种算法都是其自身参数的函数，在x轴上以单一比例显示。这种图叫做参数研究。请注意，参数值随系数2而变化，并以对数刻度表示。注意每种算法性能的特征倒U形；所有的算法在中间的参数值表现的最好，既不太大也不太小。在评估一种方法时，我们不仅要注意它在最佳参数设置下的表现如何，而且还要注意它对参数值的敏感程度。所有这些算法都相当不敏感，在大约一个数量级变化的参数值范围内表现良好。总的来说，在这个问题上，UCB似乎表现最好。
尽管这些方法简单，但在我们看来，本章中介绍的方法可以被认为是最先进的。有更复杂的方法，但它们的复杂性和假设使它们不适用于我们真正关注的全面强化学习问题。从第五章开始，我们提出了解决完全强化学习问题的学习方法，其中部分使用了本章探讨的简单方法。
虽然本章探讨的简单方法可能是我们目前所能做的最好的方法，但它们远不能完全令人满意地解决勘探与开采之间的平衡问题。
在k臂**机问题中，平衡勘探和开发的一个经过充分研究的方法是计算称为Gittins指数的特殊函数。这些方法为一类比本文所考虑的更一般的bandit问题提供了一个最优解，但是这种方法假设可能问题的先验分布是已知的。不幸的是，这种方法的理论和计算的可处理性似乎都不能推广到我们在本书其余部分中考虑的完全强化学习问题。
在贝叶斯环境下，人们甚至可以计算出勘探和开采之间的最佳平衡。我们可以计算任何可能的行动，每一个可能的即时回报的概率，以及行动价值的后验分布。这种不断变化的分布成为问题的信息状态。给定一个地平线，比如1000步，你可以考虑所有可能的行动，所有可能的结果奖励，所有可能的下一步行动，所有下一步的所有奖励，等等。在假设的前提下，每一个可能的事件链的回报和概率都是可以确定的，人们只需要选择最好的。但是可能性之树增长得非常快；
即使只有两次行动和两次奖励，这棵树也会有2^2000片叶子。一般来说，精确地进行这种庞大的计算是不可行的，但也许可以有效地近似计算。这种方法可以有效地将bandit问题转化为完全强化学习问题的一个实例。最后，我们可以使用近似的强化学习方法，例如本书第二部分中介绍的方法来接近这个最优解。但这是一个研究的主题，超出了这本介绍性书籍的范围。
练习2.9（编程）为练习2.5中概述的非平稳情况制作一个类似于图2.6的图。包括常数步长ε-贪心算法，α=0.1。使用200000个步骤的运行，作为每个算法和参数设置的性能度量，使用最后100000个步骤的平均奖励。
Bibliographical and Historical Remarks
2.1 强盗问题在统计学、工程学和心理学中都有研究。在统计学中，bandit问题属于“实验的顺序设计”的标题，由Thompson（1933，1934）和Robbins（1952）提出，并由Bellman（1956）研究。Berry和Fristedt（1985）从统计学的角度对强盗问题进行了广泛的研究。Narendra和Thathachar（1989）从工程学的角度来处理bandit问题，提供了关于这些问题的各种理论传统的很好的讨论。在心理学中，班迪特问题在统计学习理论中扮演了重要角色（例如，Bush和Mosteller，1955；Estes，1950）。
在启发式搜索文献中经常使用贪婪这个词（例如，Pearl，1984）。勘探与开发之间的冲突在控制工程中被称为识别（或估计）与控制之间的冲突（如Witten，1976）。Feldbaum（1965）称之为双重控制问题，指的是当试图在不确定性下控制系统时，需要同时解决辨识和控制这两个问题。在讨论遗传算法的各个方面时，Holland（1975）强调了这种冲突的重要性，将其称为开发需求和新信息需求之间的冲突。
2.2 我们的k臂**机问题的行动价值方法是由Thathachar和Sastry（1985）首先提出的。在学习自动机文献中，这些算法通常被称为估计器算法。沃特金斯的价值（1989年）。第一个使用ε-贪心方法的人可能也是沃特金斯（1989年，第187页），但这个想法非常简单，似乎有可能在早期使用。
2.4-2.5 本材料属于随机迭代算法的总标题，Bertsekas和Tsitsiklis（1996）对此有很好的介绍。
2.6 Sutton（1996）将优化初始化用于强化学习
2.7 Lai和Robbins（1985年）、Kaelbling（1993b）和Agrawal（1995年）在使用上置信界估计值来选择行动方面进行了早期工作。本文提出的UCB算法在文献中称为UCB1，它首先由Auer、Cesa Bianchi和Fischer（2002）开发。
2.8 梯度bandit算法是Williams（1992）提出的基于梯度的强化学习算法的一个特例，后来发展成了我们在本书后面讨论的actor-critic和policy梯度算法。我们在这里的发展受到了巴拉拉曼·拉文德兰（Balaraman Ravindran，个人通信）的影响。Greensmith、Bartlett和Baxter（2001年、2004年）和Dick（2015年）提供了关于基线选择的进一步讨论。动作选择规则（2.9）中的“软最大”一词来自Bridle（1990）。这个规则似乎是由Luce（1959）首先提出的。
2.9 Barto、Sutton和Brouwer（1981）提出了术语关联搜索及其相应的问题。术语联想强化学习也被用于联想搜索（Barto and Anandan，1985），但我们更愿意保留该术语作为完全强化学习问题的同义词（如Sutton，1984）。（而且，正如我们所注意到的，现代文献也使用了“语境强盗”这个词来解决这个问题。）我们注意到桑代克的效果定律（引用于第1章）描述了情境（状态）和行动之间的联想联系的形成。根据操作性或工具性条件作用的术语（例如，Skinner，1938），区分性刺激是一种表示存在特定强化偶然性的刺激。用我们的术语来说，不同的辨别性刺激对应于不同的状态。
2.10 Bellman（1956）第一个展示了如何使用动态规划来计算问题的贝叶斯公式中勘探和开采之间的最佳平衡。Gittins索引方法源于Gittins和Jones（1974）。达夫（1995）展示了如何通过强化学习来学习土匪问题的Gittins指数。Kumar（1985）的调查对这些问题的贝叶斯和非贝叶斯方法进行了很好的讨论。信息状态一词来源于部分可观测mdp的文献；参见，例如Lovejoy（1991）。
的辨别性刺激对应于不同的状态。
2.10 Bellman（1956）第一个展示了如何使用动态规划来计算问题的贝叶斯公式中勘探和开采之间的最佳平衡。Gittins索引方法源于Gittins和Jones（1974）。达夫（1995）展示了如何通过强化学习来学习土匪问题的Gittins指数。Kumar（1985）的调查对这些问题的贝叶斯和非贝叶斯方法进行了很好的讨论。信息状态一词来源于部分可观测mdp的文献；参见，例如Lovejoy（1991）。
其他的理论研究集中在探索的效率上，通常表现为一个算法能够以多快的速度接近一个最优策略。形式化探索效率的一种方法是通过适应强化学习，监督学习算法的样本复杂度的概念，即算法在学习目标函数时所需的训练样本数。强化学习算法探索样本复杂度的定义是算法没有选择接近最优动作的时间步数（Kakade，2003）。Li（2012）在强化学习中探索效率的理论方法调查中讨论了这一方法和其他几种方法。