多臂老虎机简介

在 TensorFlow.org 上查看 在 Google Colab 中运行 在 GitHub 上查看源代码 下载笔记本

简介

多臂老虎机 (MAB) 是一种机器学习框架，其中代理必须选择动作（臂）以最大限度地提高其长期累积奖励。在每一轮中，代理都会收到有关当前状态（上下文）的一些信息，然后它根据这些信息以及之前轮次中积累的经验选择一个动作。在每一轮结束时，代理会收到与所选动作相关的奖励。

也许最纯粹的例子是给 MAB 命名的问题：想象一下，我们面临着 k 台老虎机（单臂老虎机），我们需要弄清楚哪一台老虎机的支出最高，同时又不损失太多钱。

Multi-Armed Bandits

尝试每台机器一次，然后选择支出最多的机器，这不是一个好策略：代理可能会陷入选择一台一开始很幸运但总体上不是最佳的机器。相反，代理应该反复回到选择看起来不太好的机器，以便收集更多关于它们的 information。这是多臂老虎机的主要挑战：代理必须找到在利用先验知识和探索之间的正确平衡，以避免忽视最佳动作。

MAB 的更实际实例涉及每次学习者做出决策时的一段辅助信息。我们称这种辅助信息为“上下文”或“观察”。

多臂老虎机和强化学习

为什么 TF-Agents 库中有一个 MAB 套件？RL 和 MAB 之间有什么联系？多臂老虎机可以看作是强化学习的特例。引用 强化学习简介

在每个时间步长，代理根据其策略 \(\pi(a_t|s_t)\) 对环境采取行动，其中 \(s_t\) 是来自环境的当前观察结果，并从环境中接收奖励 \(r_{t+1}\) 和下一个观察结果 \(s_{t+1}\)。目标是改进策略，以最大限度地提高奖励总和（回报）。

在一般 RL 案例中，下一个观察结果 \(s_{t+1}\) 取决于先前状态 \(s_t\) 和策略采取的动作 \(a_t\)。最后这一部分是将 MAB 与 RL 区分开来的部分：在 MAB 中，下一个状态（即观察结果）不依赖于代理选择的动作。

这种相似性使我们能够重用 TF-Agents 中存在的所有概念。

  • 一个 环境 输出观察结果，并通过奖励对动作做出响应。
  • 一个 策略 根据观察结果输出动作，并且
  • 一个 代理 反复根据先前的观察结果-动作-奖励元组更新策略。

蘑菇环境

为了说明目的，我们使用一个名为“蘑菇环境”的玩具示例。蘑菇数据集 (Schlimmer, 1981) 包含可食用和有毒蘑菇的标记示例。特征包括蘑菇不同部位的形状、颜色、大小，以及气味等等。

mushroom

蘑菇数据集，就像所有监督学习数据集一样，可以转化为上下文 MAB 问题。我们使用 Riquelme 等人 (2018) 也使用的方法。在这个转换中，代理会收到蘑菇的特征，决定吃它还是不吃。吃可食用蘑菇会获得 +5 的奖励，而吃有毒蘑菇会以相等的概率获得 +5 或 -35 的奖励。不吃蘑菇会获得 0 的奖励，与蘑菇的类型无关。下表总结了奖励分配

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

LinUCB 代理

在上下文 bandit 环境中表现良好需要对每个动作的奖励函数进行良好的估计，前提是观察结果。一种可能性是使用线性函数估计奖励函数。也就是说，对于每个动作 \(i\)，我们试图找到参数 \(\theta_i\in\mathbb R^d\)，使得估计

\(r_{t, i} \sim \langle v_t, \theta_i\rangle\)

尽可能接近现实。这里 \(v_t\in\mathbb R^d\) 是在时间步长 \(t\) 接收到的上下文。然后，如果代理对其估计非常有信心，它可以选择 \(\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle\) 以获得最高的预期奖励。

如上所述，仅仅选择估计奖励最高的臂并不能带来好的策略。在线性估计器代理中，有许多不同的方法可以混合利用和探索，其中最著名的之一是线性置信上限 (LinUCB) 算法（参见例如 Li 等人，2010）。LinUCB 具有两个主要构建块（省略了一些细节）

  1. 它使用线性最小二乘法维护每个臂参数的估计值：\(\hat\theta_i\sim X^+_i r_i\)，其中 \(X_i\) 和 \(r_i\) 是选择臂 \(i\) 的回合的堆叠上下文和奖励，而 \(()^+\) 是伪逆。
  2. 它维护由上述估计值的逆协方差 \(X_i^\top X_i\) 定义的置信椭球。

LinUCB 的主要思想是“面对不确定性的乐观”。代理通过将估计值提升一个与这些估计值方差相对应的量来整合探索。这就是置信椭球发挥作用的地方：对于每个臂，乐观估计是 \(\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle\)，其中 \(E_i\) 是围绕 \(\hat\theta_i\) 的椭球。代理选择看起来最好的臂 \(\arg\max_i\hat r_i\)。

当然，以上描述只是对 LinUCB 做了什么的一个直观但肤浅的总结。可以在我们的代码库中找到实现 这里

下一步？

如果您想详细了解我们的 Bandits 库，请查看我们的 Bandits 教程。如果您想立即开始探索我们的库，您可以在 这里 找到它。如果您更渴望开始训练，请查看我们的一些端到端示例 这里，包括上面描述的带有 LinUCB 的蘑菇环境 这里。