本篇文章介绍一种针对「Stochastic Multi-armed Bandits (MAB)」问题的算法，即「Upper Confidence Bound (UCB)」，其通过估计摇臂的奖励区间，实现了探索与利用之间的平衡。
Stochastic Multi-armed Bandits
假设现在有一个赌博机，其上共有 $K$ 个选项，即 $K$ 个摇臂，玩家每轮只能选择拉动一个摇臂，每次拉动后，会得到一个奖励，MAB 关心的问题为「如何最大化玩家的收益」。
想要解决上述问题，必须要细化整个问题的设置。
在 Stochastic MAB（随机的 MAB）中，每一个摇臂在各轮中的奖励是独立同分布的，即摇臂 $i$ 在各轮中的奖励均从分布 $P_i$ 中采样得到，将第 $i$ 个摇臂的奖励均值记为 $\mu_i$。
假设一共有 $T$ 轮，玩家每轮选择摇臂 $i_t$，则我们希望设计一个算法来最小化下述遗憾 (regret)：
除上述介绍的 Stochastic MAB 外，MAB 问题还有下述多种类型：
Adversarial MAB（对抗的 MAB）：环境会发生变化，即每个摇臂的分布会发生变化；- Oblivious Adversary Setting（健忘的）：分布的变化会被事先定义好，不会随玩家的选择发生变化（算法 Exp3 在此场景取得 $O(\sqrt T)$ 遗憾界）；
- Nonoblivious Adversary Setting（非健忘的）：摇臂第 $t$ 轮的分布可以依赖于玩家前 $t-1$ 轮的选择；
-
Contextual MAB：每个摇臂在每一轮的奖励和该轮玩家的特征（即 context）有关，常出现于在线广告推送场景中； Nonstationary Stochastic MAB：可以视作 Stochastic 与 Adversarial 之间的折中，即每个摇臂的分布依然会发生变化，但相邻轮之间，分布的期望值变化量，会被 Variation Budget $V_T\geq 0$ 约束住（$\mu_i^{t}$ 表示第 $i$ 个摇臂在第 $t$ 轮时的期望奖励）：
Upper Confidence Bound
在 Stochastic MAB 中，玩家需要对「探索」与「利用」两方面进行权衡，其中「探索」指尝试更多的摇臂，而「利用」则为选择可能有更多收益的摇臂。
为解决「探索」和「利用」的折中，Upper Confidence Bound (UCB) 算法得到了提出，其思想是「为每一个摇臂 $i$ 维持一个置信上界 $\hat{\mu}_i$，使其高概率满足均值 $\mu_i\leq \hat{\mu}_i$，随后算法每次选择具有最大置信上界 $\hat{\mu}_i$ 的摇臂，进而自动实现探索和利用之间的折中」。
考虑 Chernoff-Hoeffding Bound，即：
-
假设摇臂 $i$ 共摇了 $n_i$ 次，对应 $n_i$ 个独立随机变量 $x_t\in [0,1]$，$t\in[n_i]$，令 $\bar{\mu}_i=\frac{1}{n_i}\sum_{t=1}^{n_i} x_t$，则有：
当 $\epsilon=\sqrt{2\ln \alpha / n_i}$ 时，可以得到：
即以至少 $1-2\alpha^{-4}$ 的概率有 $\mu_i\in [\bar{\mu}_i-\sqrt{2\ln \alpha / n_i}, \bar{\mu}_i+\sqrt{2\ln \alpha / n_i}]$，因此将置信上界定义为：
由此可知，置信上界由样本均值 $\bar{\mu}_i$ 与区间宽度 $\sqrt{2\ln \alpha / n_i}$ 组成，其中样本均值为过去的经验，对应着利用；区间宽度为经验的不确定性，对应着探索。因此每一轮根据置信上界来选择摇臂，即可自动实现探索和利用之间的折中。
对于 Stochastic MAB 问题，UCB 算法在期望意义上的遗憾界为 $O(K\log T)$。
参考资料
- 周志华，王魏，高尉，张利军. (2020). 机器学习理论导引. 机械工业出版社, 北京.