该节内容摘自于《动手学强化学习》第2章 多臂老虎机问题。
1. 问题介绍
在多臂老虎机（MAB）问题中，有一个拥有$K$根拉杆的老虎机，拉动每一根拉杆都对应一个关于奖励的概率分布$R$。我们每次拉动其中一个拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励$r$。我们在各根拉杆的奖励概率分布位置的情况下，从头开始尝试，目标是在操作$T$次拉杆后获得尽可能高的累积奖励。由于奖励的概率分布未知，因此我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。就像人生的决策过程中，你是需要一直待在自己的舒适区内选择自己习惯的动作，还是在某些决策中跳出这种舒适区去探索未知。究竟采用怎样的操作策略能够使得累积的奖励最高呢？
形式化描述
多臂老虎机问题可以表示为一个元组$<A, R>$
- A为动作集合，其中每个动作表示拉动一根拉杆，$A={a_1, a_2, \cdots, a_K}$
- R为奖励概率分布，拉动每一根拉杆的动作$a$都对应了一个对应的奖励概率分布$R(r\vert a)$
假设每个时间步只能够拉动一根拉杆，因此我们的目标为
\[\max\sum_{t=1}^Tr_t,r_t\sim R(\cdot\vert a_t)\]累积懊悔
对于每一个动作$a$，我们定义其期望奖励为$Q(a)=E_{r\sim R(\cdot \vert a)}[r]$。因此，至少存在一根拉杆，它的期望奖励不少于拉动其他任意一根拉杆，我们将该最优期望奖励表示为$Q^\star=\max_{a\in A}Q(a)$。为了更加直观方便地观察拉动一根拉杆的期望奖励离最优拉杆期望奖励的差距，我们引入懊悔（regret）的概念。
懊悔被定义为拉动当前拉杆的动作$a$与最优拉杆的期望奖励差，即$R(a)=Q^\star-Q(a)$。累积懊悔（cumulative regret）即操作$T$次拉杆后累积的懊悔总量。对于一次完整的$T$步决策${a_1,\cdots, a_T}$，累积懊悔为$\sigma_R=\sum_{t=1}^TR(a_t)$。MAB问题的目标为最大化累积奖励，等价于最小化累积懊悔。
估计期望奖励
为了知道拉动哪一根拉杆能够获得更高的奖励，我们需要估计拉动这根拉杆的期望奖励。由于只拉动一次拉杆获得的奖励存在随机性，所以需要多次拉动一根拉杆，然后计算得到的多次奖励的期望。
这里之所以采用增量式的期望更新，是因为时间和空间复杂度均为O(1)。如果将所有数求和再除以次数，每次更新的时间和空间复杂度均为O(n)。
Solver基础类
为了解决多臂老虎机的求解方案，我们需要实现下列函数功能：
- 根据策略选择动作
- 根据动作获取奖励
- 更新期望奖励估值
- 更新累积懊悔和计数
探索与利用的平衡
在上述算法框架中，还没有一个策略告诉我们应该如何选取动作，即拉动哪一根拉杆，所以接下来我们将学习如何设计一个策略。
在MAB问题中，一个经典的问题就是探索与利用的平衡问题。探索（exploration）是指尝试拉动更多可能的拉杆，这根拉杆不一定会获得最大的奖励，但这种方案能够摸清所有拉杆的获奖情况。利用（exploitation）是指拉动已知期望奖励最大的那根拉杆，由于已知的信息仅仅来自有限次的交互观测，所以当前的最优拉杆不一定是全局最优的。因此，在MAB问题中，设计策略时需要平衡探索和利用的次数，使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的探索，在对每根拉杆都有比较准确的估计后，再进行利用。
2. 设计策略
$\epsilon$贪心算法
完全贪婪算法即是再每一个时刻采取期望奖励估值最大的动作（拉动拉杆），这就是纯粹的利用而没有探索。在此基础上，我们进行一些修改，比如在$\epsilon$-贪婪算法中，我们根据下述公式选择动作
\[a_t= \left\{ \begin{matrix} \argmax_{a\in A} \hat{Q}(a) & 采样概率：1-\epsilon\\ 从A中随机选择 & 采样概率：\epsilon \end{matrix} \right.\]随着探索次数的不断增加，我们对各个动作的奖励估计得越来越准，此时我们就没必要继续花大力气进行探索。所以在具体实现中，我们可以令$\epsilon$随时间衰减。
当$\epsilon$为固定值时，通过实验可以发现，$\epsilon$-贪婪算法的累积懊悔几乎是线性增长的，这是为什么呢？（因为如果选择利用，产生的懊悔是0；如果选择探索，产生的懊悔值是固定的）
而当$\epsilon$为反比例衰减时（$\epsilon=\frac{1}{t}$），累积懊悔是次线性增长的，这明显由于固定值。
上置信界算法
设想这样一种情况：对于一台双臂老虎机，其中第一根拉杆只被拉动过一次，得到的奖励为0；第二根拉杆被拉动过很多次，我们对它的奖励分布已经有了大致的把握。这时你应该怎么做？或许你会进一步尝试拉动第一根拉杆，从而更加确定其奖励分布。这种思路主要是基于不确定性，因为此时第一根拉杆只被拉动过一次，它的不确定性很高。一根拉杆的不确定性越大，它就越具有探索的价值。
我们在此引入不确定性度量$U(a)$，它会随着一个动作被尝试次数的增加而减少。我们可以使用一种基于不确定性的策略来综合考虑现有的期望奖励估值和不确定性，其核心问题是如何估计不确定性。
上置信界（upper confidence bound, UCB）算法是一种经典的基于不确定性的策略算法。它的思想用到了一个非常著名的数学原理：霍夫丁不等式（Hoeffding’s inequality）。在霍夫丁不等式中，令$X_1,\cdots,X_n$为n个独立同分布的随机变量，取值范围为[0, 1]，其经验期望为$\bar{x}n=\frac{1}{n}\sum{j=1}^nX_j$，则有
\[P\{E[X]\geq \bar{x}_n+u\} \leq e^{-2nu^2}\]现在我们将霍夫丁不等式运用于多臂老虎机问题中。将$\hat{Q}_t(a)$代入$\bar{x}_t$，不等式中的参数$u=\hat{U}_t(a)$代表不确定性度量。给定一个概率$p=e^{-2N_t(a)U_t(a)^2}$，根据上述不等式，$Q_t(a) < \hat{Q}_t(a) + \hat{U}_t(a)$至少以概率$1-p$成立。当$p$很小时，$\hat{Q}_t(a) + \hat{U}_t(a)$就是期望奖励上界。此时，上置信算法便选取期望奖励上界最大的动作，即
\[a = \argmax_{a\in A} [\hat{Q}_t(a) + \hat{U}_t(a)]\]其中，$\hat{U}_t(a)=\sqrt{\frac{-\log p}{2N_t(a)}}$。因此，设定一个概率$p$后，就可以计算得到不确定性度量。
汤普森采样算法
MAB中还有一种经典的算法——汤普森采样（Thompson sampling），先假设拉动每根拉杆的奖励服从一个特定的概率分布，然后根据拉动每根拉杆的期望奖励来进行选择。但是由于计算所有拉杆的期望奖励的代价比较高，汤普森采样算法使用采样的方式，即根据当前每个动作$a$的奖励概率分布进行一轮采样，得到一组各根拉杆的奖励样本，再选择样本中奖励最大的动作。
在这里，我们需要解决一个问题：怎样得到当前每个动作$a$的奖励概率分布并且在过程中更新？在实际情况中，通常用beta分布进行建模。比如某拉杆被拉动了$k$次，其中$m_1$次奖励为1，$m_2$次奖励为0，则该拉杆的奖励服从参数为$(m_1+1,m_2+1)$的beta分布。
3. 总结
探索与利用是与环境做交互学习的重要问题，是强化学习试错法中的必备技术，而多臂老虎机问题是研究探索与利用技术理论的最佳环境。了解多臂老虎机的探索与利用问题，对接下来我们学习强化学习环境探索有很重要的帮助。对于多臂老虎机各种算法的累积懊悔理论分析，有兴趣的同学可以自行查阅相关资料。$\epsilon$-贪婪算法、上置信界算法和汤普森采样算法在多臂老虎机问题中十分常用，其中上置信界算法和汤普森采样方法均能保证对数的渐进最优累积懊悔。
多臂老虎机问题与强化学习的一大区别在于其与环境的交互并不会改变环境，即多臂老虎机的每次交互的结果和以往的动作无关，所以可看作无状态的强化学习（stateless reinforcement learning）。接下来将开始在有状态的环境下讨论强化学习，即马尔可夫决策过程。