多臂老虎机
Published:
多臂老虎机算法的遗憾界推导，包括ETC、ε-贪婪、以及UCB算法，整理自 Chi Jin’s RL course, vidoe 8.
问题设定如下图所示：
玩家与$A$ 臂老虎机交互，没拉一个臂i就会得到对应的奖励，而每个臂的奖励为一个有界随机变量 $R_i \in [0,1]$, 记其期望值为 $r_i = \mathbb{E}[R_i]$. 玩家的目的是选择每轮要拉的臂$i_t$使得尽可能获得最大的奖励。这可以用最小化遗憾来定义，其中 $T$ 次交互的遗憾定义为 ${\rm Regret}(T) = \sum_{t=1}^T \max_{ i \in [A]}r_i - r_{i_t}$.
ETC 算法
ETC算法，全称为 Explore-Then-Commit, 算法首先对每个臂都拉 $n$ 次，然后计算每个臂的经验奖励 $\hat r_i = \frac{1}{n} \sum_{j=1}^n R_i^{(j)}$, 然后在剩余的时间内，都只选择拉经验奖励最大的臂，也即 $\hat i = \arg \max_{i \in [A]} \hat r_i$.
根据 Hoeffding集中不等式， 我们知道对于给定的 $i \in [A]$ 奖励的经验估计以概率 $1-\delta$ 满足
\[\begin{align*} \vert \hat r_i - r_i \vert \le \sqrt{\log(1/\delta) / n}. \end{align*}\]那么对于所有的 $i \in [A]$ 取联合界，可以得到对于任意的 $i \in [A]$ 以概率 $1-\delta$ 满足
\[\begin{align*} \vert \hat r_i - r_i \vert \le \sqrt{\log(A/\delta) / n}. \end{align*}\]我们考虑两个阶段分别的遗憾界，在第一阶段的遗憾可以简单地用 $nA$ 作为上界， 而算法在第二个阶段的遗憾界可以如下控制：
\[\begin{align*} &\quad \sum_{t=nA+1}^T r_{i^\ast} - r_{\hat i} \\ &= \sum_{t=nA+1}^T r_{i^\ast} - \hat r_{i^\ast} + \hat r_{i^\ast} - r_{\hat i} \\ &\le \sum_{t=nA+1}^T r_{i^\ast} - \hat r_{i^\ast} + \hat r_{\hat i} - r_{\hat i} \\ &\le 2 (T - nA) \sqrt{ \log (1/\delta) / n} \\ &\le 2 T \sqrt{ \log (1/\delta) / n}. \end{align*}\]综合两个阶段，我们知道遗憾界满足
\[\begin{align*} &\quad {\rm Regret}(T) \le n A + 2 T \sqrt{\log(1/ \delta)/n}. \end{align*}\]选择最优的 $n$ 极小化上式的右端项，可以得到遗憾界为 $\tilde{\mathcal{O}}(A^{1/3} T^{2/3})$.
$\epsilon$-贪婪算法
我们进而分析另外一个实际中很常用的算法，$\epsilon$-贪婪算法. 该算法以 $\epsilon$ 的概率随机选择一个臂进行探索，而以 $1-\epsilon$ 的概率使用贪婪策略利用已经探索得到的信息，算法流程如下：
下面我们来分析算法的遗憾界。我们用 $N_t(a)$ 来表示臂 $a$ 在 $t$ 轮交互后被拉的次数，我们希望使用集中不等式来刻画 $\vert \hat r_t(a) - r(a) \vert$ 的大小，其中 $\hat r_t(a)$ 是 $N_t(a)$ 个随机变量的和。 但注意到求和的项数也是一个随机变量，我们并不能直接使用Hoeffding不等式。为此，我们先考虑固定 $N_t = N$ 下的集中不等式，然后对所有可能的 $N_t(a)$ 的取值取联合界。根据Hoeffding不等式，并且对所有的 $a \in [A]$ 以及 $ t \in [T]$ 取联合界，可以知道对于任意的 $a \in [A]$以及 $t \in [T]$ 在给定 $N_t (a) = N$ 的前提下，至少以 $1-\delta$ 的概率成立
\[\begin{align*} \vert \hat r_t(a) - r_t(a) \vert \le \sqrt{\log(AT/\delta) /N}. \end{align*}\]接着我们对所有可能的 $N_t(a)$ 的取值取联合界，就得到了以概率 $1-\delta$ 成立着
\[\begin{align*} \vert \hat r_t(a) - r_t(a) \vert \le \sqrt{\log(AT^2/\delta) /N_t(a)}. \end{align*}\]对于 $N_t(a)$， 我们考虑他的一个下界，这可以通过只考虑探索的时候拉臂 $a$ 的次数，容易看出这是 $t$ 个均值为 $\epsilon / A$ 的随机变量的求和，根据Hoeffding不等式，并且对所有的 $a \in [A]$ 以及 $t \in [T]$ 取联合界，可以知道对于任意的 $a \in [A]$以及 $t \in [T]$，以 $1-\delta$ 的概率成立着
\[\begin{align*} N_t(a) \ge \epsilon t /A - \sqrt{\log(A T/\delta)}. \end{align*}\]那么忽略所有可能的对数因子 $\iota$ 的前提下，我们知道以 $1-\delta$ 的概率成立着
\[\begin{align*} \vert \hat r_t(a) - r_t(a) \vert \le \sqrt{\iota A / (\epsilon t) } \end{align*}\]下面我们从 $\sum_{t=1}^T r_t(a)$ 开始接着分析。根据Hoeffding不等式，我们知道以$1-\delta$ 成立着
\[\begin{align*} \left \vert \sum_{t=1}^T r_t(a_t) - (1- \epsilon) \sum_{t=1}^T r_t(\hat a_t) \right \vert \le \epsilon T + \sqrt{\log(1/\delta) T}. \end{align*}\]那么对于遗憾界，我们知道以概率 $1-\delta$ 成立着
\[\begin{align*} {\rm Regret}(T) &= \sum_{t=1}^T [r_t(a^\ast) - r_t(a_t)] \\ &\le \sum_{t=1}^T [r_t(a^\ast) - r_t(\hat a_t)] + \epsilon T + \sqrt{ \log(1/\delta) T} \\ &= \sum_{t=1}^T [r_t(a^\ast) - \hat r_t(a^\ast) + \hat r_t(a^\ast) - r_t(\hat a_t)] + \epsilon T + \sqrt{ \log(1/\delta) T} \\ & \le \sum_{t=1}^T [r_t(a^\ast) - \hat r_t(\hat a_t) + \hat r_t(a^\ast) - r_t(\hat a_t)] + \epsilon T + \sqrt{ \log(1/\delta) T}. \end{align*}\]回顾我们已经推导得到的关于 $\vert \hat r_t(a) - r_t(a) \vert$ 的集中性质刻画。我们知道以概率 $1-2\delta$ 成立着
\[\begin{align*} {\rm Regret}(T) &\le 2 \sum_{t=1}^T \sqrt{\iota A / (\epsilon t)} + \epsilon T + \sqrt{\log(1/\delta) T} \\ &\le 2 \sqrt{\iota A T / \epsilon} + \epsilon T + \sqrt{\log(1/\delta) T}. \end{align*}\]选择最优的 $\epsilon$ 来极小化上述的右端项，可以得到对于 （另外一个不同的）对数因子 $\iota$ 以概率 $1-2\delta$ 成立着
\[\begin{align*} {\rm Regret}(T) \le \iota A^{1/3} T^{2/3} + \sqrt{\log(1/\delta) T} = \tilde{\mathcal{O}} (A^{1/3} T^{2/3}). \end{align*}\]可以发现，上述算法实际上与 ETC 算法具有相同的遗憾界。
UCB 算法
经过上述分析，我们发现 ETC算法和 $\epsilon$-贪婪算法的遗憾界都为 $\tilde{\mathcal{O}}(A^{1/3} T^{2/3})$. 事实上，存在着更高效的算法，称为 Upper Confidence Bound (UCB) 算法，本节进行着重介绍。UCB算法的核心思想是除了经验奖励估计值 $\hat r_t(a)$ 以外，额外加上一个由集中不等式导出的bonus项，也即设定 $\tilde r_t(a) = \hat r_t(a) + {\rm bonus}(N_t(a))$. 根据和之前完全一致的集中不等式分析，我们知道对于所有的 $t \in [T]$ 以及 $a \in [A]$, 设置 ${\rm bonus}(n) = \sqrt{\log(AT^2/\delta) /n}$ 那么都以概率 $1-\delta$ 成立 $\tilde r_t(a) \ge r_t(a)$, 也就是说 $\tilde r_t(a)$ 是 $r_t(a)$ 的一个上界。算法每次会选择 $\tilde r_t(a)$ 最大的臂 $a$, 然后拉去该臂后得到对应的奖励，然后不断维护 $\tilde r_t(a)$ 的取值。
性质 $\tilde r_t(a) \ge r_t(a)$ 可以使得遗憾界的推导非常方便，如下所示：
\[\begin{align*} {\rm Regret}(T) &= \sum_{t=1}^T r_t(a^\ast) - r_t(a_t) \\ &= \sum_{t=1}^T [r_t(a^\ast) - \tilde r_t(a^\ast) + \tilde r_t(a^\ast) - r_t(a_t)] \\ &\le \sum_{t=1}^T [r_t(a^\ast) - \tilde r_t(a^\ast) + \tilde r_t(a_t) - r_t(a_t)] \\ &\le 4 \sum_{t=1}^T \sqrt{ \log(AT^2 / \delta) / N_t(a_t)} \\ &= 4 \sum_{a=1}^A \sum_{n=1}^{N_T(a)} \sqrt{ \log(AT^2 / \delta) / n} \\ &\le 8 \sum_{a=1}^A \sqrt{ \log(AT^2 / \delta) N_t(a) } \\ &\le 8 \sqrt{ \log(AT^2 / \delta) A \sum_{a=1}^A N_t(a) } \\ &\le 8 \sqrt{ \log(AT^2 / \delta) A T}. \end{align*}\]上述推导说明 UCB算法的遗憾界为 $\tilde{\mathcal{O}}(\sqrt{AT})$， 优于 ETC以及 $\epsilon$-贪婪算法，说明UCB算法这种方式更好的平衡了探索与利用。