前言

如果你对这篇文章感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

本篇文章介绍一种针对「Stochastic Multi-armed Bandits (MAB)」问题的算法，即「Upper Confidence Bound (UCB)」，其通过估计摇臂的奖励区间，实现了探索与利用之间的平衡。

Stochastic Multi-armed Bandits

假设现在有一个赌博机，其上共有 KKK 个选项，即 KKK 个摇臂，玩家每轮只能选择拉动一个摇臂，每次拉动后，会得到一个奖励，MAB 关心的问题为「如何最大化玩家的收益」。

想要解决上述问题，必须要细化整个问题的设置。

在 Stochastic MAB（随机的 MAB）中，每一个摇臂在各轮中的奖励是独立同分布的，即摇臂 iii 在各轮中的奖励均从分布 PiP_iPi​ 中采样得到，将第 iii 个摇臂的奖励均值记为 μi\mu_iμi​。

假设一共有 TTT 轮，玩家每轮选择摇臂 iti_tit​，则我们希望设计一个算法来最小化下述遗憾 (regret)：
regret=Tmax⁡i∈[K]μi−∑t=1Tμit.\text{regret}=T\max_{i\in [K]} \mu_i-\sum_{t=1}^T\mu_{i_t}. regret=Ti∈[K]max​μi​−t=1∑T​μit​​.

除上述介绍的 Stochastic MAB 外，MAB 问题还有下述多种类型：

• Adversarial MAB（对抗的 MAB）：环境会发生变化，即每个摇臂的分布会发生变化；
  • Oblivious Adversary Setting（健忘的）：分布的变化会被事先定义好，不会随玩家的选择发生变化（算法 Exp3 在此场景取得 O(T)O(\sqrt T)O(T​) 遗憾界）；
  • Nonoblivious Adversary Setting（非健忘的）：摇臂第 ttt 轮的分布可以依赖于玩家前 t−1t-1t−1 轮的选择；
• Contextual MAB：每个摇臂在每一轮的奖励和该轮玩家的特征（即 context）有关，常出现于在线广告推送场景中；
• Nonstationary Stochastic MAB：可以视作 Stochastic 与 Adversarial 之间的折中，即每个摇臂的分布依然会发生变化，但相邻轮之间，分布的期望值变化量，会被 Variation Budget VT≥0V_T\geq 0VT​≥0 约束住（μit\mu_i^{t}μit​ 表示第 iii 个摇臂在第 ttt 轮时的期望奖励）：
  ∑t=1T−1sup⁡i∈[K]∣μit+1−μit∣≤VT.\sum_{t=1}^{T-1}\sup_{i\in[K]}\left|\mu_i^{t+1}-\mu_i^t\right|\leq V_T. t=1∑T−1​i∈[K]sup​​μit+1​−μit​​≤VT​.

Upper Confidence Bound

在 Stochastic MAB 中，玩家需要对「探索」与「利用」两方面进行权衡，其中「探索」指尝试更多的摇臂，而「利用」则为选择可能有更多收益的摇臂。

为解决「探索」和「利用」的折中，Upper Confidence Bound (UCB) 算法得到了提出，其思想是「为每一个摇臂 iii 维持一个置信上界 μ^i\hat{\mu}_iμ^​i​，使其高概率满足均值 μi≤μ^i\mu_i\leq \hat{\mu}_iμi​≤μ^​i​，随后算法每次选择具有最大置信上界 μ^i\hat{\mu}_iμ^​i​ 的摇臂，进而自动实现探索和利用之间的折中」。

考虑 Chernoff-Hoeffding Bound，即：

• 假设摇臂 iii 共摇了 nin_ini​ 次，对应 nin_ini​ 个独立随机变量 xt∈[0,1]x_t\in [0,1]xt​∈[0,1]，t∈[ni]t\in[n_i]t∈[ni​]，令 μˉi=1ni∑t=1nixt\bar{\mu}_i=\frac{1}{n_i}\sum_{t=1}^{n_i} x_tμˉ​i​=ni​1​∑t=1ni​​xt​，则有：
  P(∣μˉi−μi∣≤ϵ)≥1−2e−2niϵ2.P(\left|\bar{\mu}_i-\mu_i \right|\leq \epsilon)\geq 1-2e^{-2n_i\epsilon^2}. P(∣μˉ​i​−μi​∣≤ϵ)≥1−2e−2ni​ϵ2.

当 ϵ=2ln⁡α/ni\epsilon=\sqrt{2\ln \alpha / n_i}ϵ=2lnα/ni​​ 时，可以得到：
P(∣μˉi−μi∣≤2ln⁡αni)≥1−2α4,P\left(\left|\bar{\mu}_i-\mu_i \right|\leq \sqrt{\frac{2\ln \alpha}{n_i}}\right)\geq 1-\frac{2}{\alpha^4}, P(∣μˉ​i​−μi​∣≤ni​2lnα​​)≥1−α42​,

即以至少 1−2α−41-2\alpha^{-4}1−2α−4 的概率有 μi∈[μˉi−2ln⁡α/ni,μˉi+2ln⁡α/ni]\mu_i\in [\bar{\mu}_i-\sqrt{2\ln \alpha / n_i}, \bar{\mu}_i+\sqrt{2\ln \alpha / n_i}]μi​∈[μˉ​i​−2lnα/ni​​,μˉ​i​+2lnα/ni​​]，因此将置信上界定义为：
μ^i=μˉi+2ln⁡αni.\hat{\mu}_i=\bar{\mu}_i+\sqrt{\frac{2\ln \alpha}{n_i}}. μ^​i​=μˉ​i​+ni​2lnα​​.

由此可知，置信上界由样本均值 μˉi\bar{\mu}_iμˉ​i​ 与区间宽度 2ln⁡α/ni\sqrt{2\ln \alpha / n_i}2lnα/ni​​ 组成，其中样本均值为过去的经验，对应着利用；区间宽度为经验的不确定性，对应着探索。因此每一轮根据置信上界来选择摇臂，即可自动实现探索和利用之间的折中。

对于 Stochastic MAB 问题，UCB 算法在期望意义上的遗憾界为 O(Klog⁡T)O(K\log T)O(KlogT)。

参考资料

• 周志华，王魏，高尉，张利军. (2020). 机器学习理论导引. 机械工业出版社, 北京.