多臂老虎机简介

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

入门

多臂老虎机（Multi-Armed Bandit，MAB）是一种机器学习框架，智能体（agent）必须通过选择动作（臂）来最大化其长期的累积奖励。在每一轮中，智能体都会接收到关于当前状态（上下文）的一些信息，然后根据这些信息和在先前回合中积累的经验来选择一个动作。在每一轮结束时，智能体将获得与所选动作相关的奖励。

最纯粹的例子或许就是这个名字的由来：想象一下，我们面前有 k 台老虎机（单臂老虎机），我们需要弄清楚哪一台的赔率最高，同时又不能损失太多的金钱。

Multi-Armed Bandits

每台机器试一次然后选择赔率最高的那台，这并不是一个好的策略：智能体可能会陷入选择一台刚开始运气好但总体表现并不理想的机器。相反，智能体应该反复回头选择那些看起来表现一般的机器，以便收集关于它们的更多信息。这就是多臂老虎机的主要挑战：智能体必须在利用先验知识（exploitation）和探索（exploration）之间找到合适的平衡，以避免忽略最优动作。

MAB 更实际的情况涉及学习者在每次做出决策时都会获得一段辅助信息。我们将这种辅助信息称为“上下文”（context）或“观察”（observation）。

多臂老虎机与强化学习

为什么 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 中存在的所有概念。

  • 环境（environment） 输出观测值，并以奖励响应动作。
  • 策略（policy） 根据观测值输出动作，并且
  • 智能体（agent） 根据先前的观测-动作-奖励元组重复更新策略。

蘑菇环境

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

mushroom

蘑菇数据集就像所有监督学习数据集一样，可以转化为上下文 MAB 问题。我们使用 Riquelme et al. (2018) 所使用的方法。在这种转换中，智能体接收蘑菇的特征，并决定是否食用它。食用可食用的蘑菇会得到 +5 的奖励，而食用有毒的蘑菇则有等概率获得 +5 或 -35。不食用蘑菇则获得 0 奖励，这与蘑菇的种类无关。下表总结了奖励分配情况：

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

LinUCB 智能体

在上下文老虎机环境中表现良好，需要对给定观测值下每个动作的奖励函数进行良好的估计。一种可能性是用线性函数估计奖励函数。也就是说，对于每个动作 \(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\) 来获得最高的预期奖励。

如上所述，简单地选择估计奖励最好的臂并不能带来好的策略。在线性估计器智能体中，混合利用和探索的方法有很多种，其中最著名的是线性置信上限（Linear Upper Confidence Bound，LinUCB）算法（参见 Li et al. 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 的蘑菇环境示例这里。