假设现在有一个赌博机，其上共有
K
K
K 个选项，即
K
K
K 个摇臂，玩家每轮只能选择拉动一个摇臂，每次拉动后，会得到一个奖励，MAB 关心的问题为「如何最大化玩家的收益」。
想要解决上述问题，必须要细化整个问题的设置。
在 Stochastic MAB（随机的 MAB）中，每一个摇臂在各轮中的奖励是独立同分布的，即摇臂
i
i
i 在各轮中的奖励均从分布
P
i
P_i
Pi 中采样得到，将第
i
i
i 个摇臂的奖励均值记为
μ
i
\mu_i
μi。
假设一共有
T
T
T 轮，玩家每轮选择摇臂
i
t
i_t
it，则我们希望设计一个算法来最小化下述遗憾 (regret)：
regret
=
T
max
i
∈
[
K
]
μ
i
−
∑
t
=
1
T
μ
i
t
.
\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（非健忘的）：摇臂第
t
t
t 轮的分布可以依赖于玩家前
t
−
1
t-1
t−1 轮的选择；
Nonstationary Stochastic MAB：可以视作 Stochastic 与 Adversarial 之间的折中，即每个摇臂的分布依然会发生变化，但相邻轮之间，分布的期望值变化量，会被 Variation Budget
V
T
≥
0
V_T\geq 0
VT≥0 约束住（
μ
i
t
\mu_i^{t}
μit 表示第
i
i
i 个摇臂在第
t
t
t 轮时的期望奖励）：
∑
t
=
1
T
−
1
sup
i
∈
[
K
]
∣
μ
i
t
+
1
−
μ
i
t
∣
≤
V
T
.
\sum_{t=1}^{T-1}\sup_{i\in[K]}\left|\mu_i^{t+1}-\mu_i^t\right|\leq V_T.
t=1∑T−1i∈[K]supμit+1−μit≤VT.
Upper Confidence Bound
在 Stochastic MAB 中，玩家需要对「探索」与「利用」两方面进行权衡，其中「探索」指尝试更多的摇臂，而「利用」则为选择可能有更多收益的摇臂。
为解决「探索」和「利用」的折中，Upper Confidence Bound (UCB) 算法得到了提出，其思想是「为每一个摇臂
i
i
i 维持一个置信上界
μ
^
i
\hat{\mu}_i
μ^i，使其高概率满足均值
μ
i
≤
μ
^
i
\mu_i\leq \hat{\mu}_i
μi≤μ^i，随后算法每次选择具有最大置信上界
μ
^
i
\hat{\mu}_i
μ^i 的摇臂，进而自动实现探索和利用之间的折中」。
考虑 Chernoff-Hoeffding Bound，即：
假设摇臂
i
i
i 共摇了
n
i
n_i
ni 次，对应
n
i
n_i
ni 个独立随机变量
x
t
∈
[
0
,
1
]
x_t\in [0,1]
xt∈[0,1]，
t
∈
[
n
i
]
t\in[n_i]
t∈[ni]，令
μ
ˉ
i
=
1
n
i
∑
t
=
1
n
i
x
t
\bar{\mu}_i=\frac{1}{n_i}\sum_{t=1}^{n_i} x_t
μˉi=ni1∑t=1nixt，则有：
P
(
∣
μ
ˉ
i
−
μ
i
∣
≤
ϵ
)
≥
1
−
2
e
−
2
n
i
ϵ
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.
当
ϵ
=
2
ln
α
/
n
i
\epsilon=\sqrt{2\ln \alpha / n_i}
ϵ=2lnα/ni 时，可以得到：
P
(
∣
μ
ˉ
i
−
μ
i
∣
≤
2
ln
α
n
i
)
≥
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∣≤ni2lnα)≥1−α42,
即以至少
1
−
2
α
−
4
1-2\alpha^{-4}
1−2α−4 的概率有
μ
i
∈
[
μ
ˉ
i
−
2
ln
α
/
n
i
,
μ
ˉ
i
+
2
ln
α
/
n
i
]
\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
+
2
ln
α
n
i
.
\hat{\mu}_i=\bar{\mu}_i+\sqrt{\frac{2\ln \alpha}{n_i}}.
μ^i=μˉi+ni2lnα.
由此可知，置信上界由样本均值
μ
ˉ
i
\bar{\mu}_i
μˉi 与区间宽度
2
ln
α
/
n
i
\sqrt{2\ln \alpha / n_i}
2lnα/ni 组成，其中样本均值为过去的经验，对应着利用；区间宽度为经验的不确定性，对应着探索。因此每一轮根据置信上界来选择摇臂，即可自动实现探索和利用之间的折中。
对于 Stochastic MAB 问题，UCB 算法在期望意义上的遗憾界为
O
(
K
log
T
)
O(K\log T)
O(KlogT)。
