1. 简介
在本教程中，我们将学习 
臂老虎机及其与强化学习的关系。然后我们将检查探索和利用这两个方面，并了解平衡它们的需求，通过研究探索与利用的权衡来理解。
最后，我们将研究不同的策略，以从 臂老虎机设置中获得最大回报，以及如何使用遗憾值比较不同的算法。
2. 强化学习与 K 臂老虎机
单臂老虎机是老虎机的一种俗称。虽然获胜的机会很小，但我们知道拉动单臂老虎机有获胜的概率。这意味着，经过足够多的尝试，我们最终会赢。我们只是不知道概率分布，并且无法在有限的尝试次数内发现它。
现在想象一下我们身处一个赌场，坐在 10 台不同的老虎机前。每台老虎机都有获胜的概率。如果我们有一些硬币可以玩，我们选择哪一台？我们是否把所有的机会都花在一台机器上，或者我们在不同的机器上玩一些组合？
找到最佳的游戏策略以赢得最高的可能回报并非易事。我们将在以下章节中学习解决 
臂老虎机的策略。
在 强化学习 中，一个智能体正在与环境交互。它试图找出可用动作的结果。它的最终目标是在最后最大化回报。
臂老虎机问题是一个简化的强化学习设置。只有一个状态；我们（智能体）坐在 k 台老虎机前。有 个动作：拉动其中一个 个不同的臂。动作的奖励值在采取行动后立即可用。
臂老虎机是一个简单而强大的表示。然而，它无法模拟复杂的问题，忽略之前采取的行动的后果。
为了更好地模拟现实生活中的问题，我们引入了“上下文”的概念。 智能体根据上下文选择一个动作。换句话说，智能体拥有一个状态，采取行动会使智能体在状态之间转换，并产生奖励。简单来说，上下文是之前采取的行动的结果。
然而，在上下文bandit模型中，选择动作后奖励是即时的，这与现实世界的问题不同。有时我们需要经过一段时间或采取一系列行动后才能获得奖励。例如，即使是在井字棋这样简单的游戏中，我们也在游戏结束时完成一系列移动后获得奖励。因此，上下文bandit对于模拟某些问题来说过于简化了。
3. 探索 vs. 利用
在 -臂bandit设置中，智能体最初对环境没有或只有有限的了解。因此，它通过试错来发现环境。
让我们考虑 -臂bandit设置。在这里，我们知道每个 台老虎机都会根据概率分布产生即时奖励。奖励将是一个实数，可以是负数也可以是正数。下图展示了一个具有 = 10的示例设置。
虽然在这个设置中，每台老虎机的奖励分布是确定的，但我们并不知道它们。所以，我们将通过试错来发现。 在结果未知时选择任意动作被称为探索。
假设我们在这个未知的设置中选择随机行动（探索）。结果是，经过一段时间后，我们对每台老虎机的奖励有一个初步的了解。通过少量尝试，我们无法确信期望值。但此时我们对环境有所了解。
在我们的示例设置中，蓝色点标示了智能体认为从老虎机获得的期望奖励。浅蓝色标记显示真实的分布，此时智能体仍然不知道。对于某些机器，智能体的期望接近平均值，而对于另一些机器，在有限的探索后，它却在极端值附近。
根据期望采取行动并利用先验知识获得即时奖励被称为利用。 在我们的例子中，智能体会选择第 5 台机器进行利用，因为它认为这将产生正向奖励，这将是一个不错的选择。然而，智能体会以相似的信念尝试第 6 台机器，但这并不能满足它的期望。
根据问题的大小，经过足够的尝试后，智能体对老虎机的期望奖励值有了更好的估计。探索的结果是，现在智能体的期望与实际奖励高度匹配。
在具有许多状态和动作的现实强化学习问题中，实际学习环境并准确预测期望奖励需要无限多次的尝试。有时，环境甚至可能在变化（非平稳）。因此，坚持我们已经学到的东西不是一个好主意。在某些情况下，这样做既危险又冒险，因为智能体可能会陷入次优选择。
另一方面，不断探索环境意味着只采取随机行动。不利用好的奖励机会，这与获得最大总体奖励的整体目标背道而驰。
在包含不完整信息的情况下，我们需要保持平衡。最佳的长期策略可能需要在短期内承担风险。探索可能导致从长远来看获得更高的回报，但会牺牲短期回报。相反，利用可以确保短期内的即时回报，但长期回报存在不确定性。代理选择其已知信息与获得更多知识之间的困境被称为探索与利用的权衡。
多臂老虎机环境包含不确定性。探索与利用的权衡是由于信息不完整造成的。如果我们了解环境的一切，那么我们就可以找到最优解。然而，现实世界的问题包含许多未知因素。
4. K-臂老虎机行动选择策略
评估 K-臂老虎机策略的一种方法是衡量期望后悔值。顾名思义，较低的后悔值更好。
我们衡量每个行动的期望后悔值。当采取一个行动时，我们对最佳可能行动的期望回报有一个近似值。此外，我们立即获得所采取行动的回报。最佳期望回报与实际回报之间的差异给出期望后悔值。它表示我们通过探索而不是采取最佳行动所失去的东西。
我们可以通过累加不同策略在给定问题上的后悔值并比较结果来比较不同的策略。
现在让我们探讨一些为 K-臂老虎机问题逼近一个良好解决方案的策略。
4.1. 先探索
先探索（或 ε-先探索，ε-first）策略由两个阶段组成：探索和利用。
顾名思义，在探索阶段，代理会尝试所有选项几次。然后，它会根据这些试验选择最佳行动。最后，在利用阶段，它只是采取结果最好的行动。
该算法的利用阶段在最小化后悔方面工作得很好。然而，效率低下在于探索阶段。对于大多数应用程序而言，总体性能并不令人满意。
4.2. ε-贪婪
在 ε-贪婪（ε-greedy）方法中，我们不是拥有纯粹的探索阶段，而是在时间上分散探索。
最初，我们选择一个小 ε 值 （通常，我们选择 ε ≈ 0.1）。然后，以 ε 的概率，即使我们对预期的结果充满信心，我们也会选择一个随机行动。在剩余的时间（1 – ε）内，我们只是贪婪地行动并利用最佳行动。我们对整个期间应用这个简单的算法。
ε-贪婪算法易于理解和实现。它是基本的强化学习增强算法之一，与 Q-learning 相关。
4.3. 衰减 ε-贪婪（ε 递减策略）
epsilon-贪婪策略的一个缺点是探索阶段在时间上均匀分布。 我们可以通过在开始时进行更多探索来改进这一点，因为我们对环境的了解有限。然后，随着我们学习，我们可以做出更明智的决定并减少探索。
这个想法实现起来非常简单。我们引入一个衰减因子（通常约为0.95）。每次采取行动后，我们将epsilon更新为epsilon*衰减。因此，epsilon值会随着时间的推移逐渐降低。与epsilon-贪婪算法相比，这会降低遗憾值。
4.4. Softmax (Boltzmann)
Softmax方法使我们能够根据其期望值来选择一个动作的概率。 请记住，epsilon-贪婪方法在探索时会选择均匀随机动作。因此，第二好的选项和最坏的选项具有相同的被选中的概率。
在softmax探索中，agent仍然会选择最佳动作大部分时间。 然而，其他动作会被排序并相应地选择。 结果，它的表现会比epsilon-贪婪算法更好。 尽管如此，遗憾值仍然没有界限。
4.5. 追逐方法
追逐方法维护当前状态下的动作-价值估计和动作偏好。 它们的偏好不断“追逐”根据当前估计的最佳（贪婪）动作。
在选择动作之前，更新动作偏好概率。 增加选择最佳动作的概率，并降低其他动作的概率。
4.6. 上置信界
上置信界 (UCB) 是一系列试图平衡探索和利用的算法。
首先，我们确保每个动作对于每个状态至少被执行一次。 然后，当我们再次面临选择时，我们选择使上置信界最大化的动作。
UCB 改进迅速并且收敛速度快于其他方法。 随着试验次数增加到无穷大，该算法会选择最优动作。
其总体遗憾值呈对数增长，并且有界。 因此，从理论上讲，从长远来看，它将是表现最佳的策略。
4.7. Thompson 采样（贝叶斯强盗）
到目前为止，我们讨论的算法使用先前试验的平均值来更新每个动作的期望奖励。 Thompson 采样算法采用不同的方法。
它假设每个动作都提供基于 beta 概率分布的奖励，并尝试在置信区间内估计该分布。 在采取动作后更新动作的优先级分布。 然后该算法选择使期望奖励最大化的动作。
从这个意义上说，Thompson 采样算法采用贝叶斯推理方法，其中随着更多证据的出现而更新设置。
5. 动作选择策略的遗憾值比较
下图比较了一些算法的worst-case界限
在大多数情况下，epsilon-贪婪很难超越。 UCB 和 Thompson 采样方法更有效地利用探索。 给定足够的试验，Thompson 采样将更加稳定。 但是，UCB 更能容忍噪声数据并收敛更快。
根据具体问题，一种策略的表现可能比理论上的worst-case好得多。 绘制不同算法的实际遗憾图可能会提供不同的见解。
6. 结论
在本教程中，我们探讨了 -臂老虎机问题及其与强化学习的关系。然后我们学习了探索和利用。最后，我们研究了各种近似技术来解决 -臂老虎机问题，以及如何使用后悔值来评估和比较它们。