Multi-armed Bandits (1)

问题简述

带有不确定性的序贯决策问题：有 $N$ 种行为，每次选择一种，收到回报（reward）；目标是最大化 $T$ 轮的总回报。

根据历史回报选择下一步行为的方法称为算法。

应用场景：

• 在线广告投放：每次推荐给用户一个广告，用户点击则收到回报。
• 商品推荐：每次推荐给用户一件商品，用户点击或购买则收到回报。
• 资产投资：对多类资产进行配置，赚取收益。

问题分类：

• 根据 Feedback：
  • bandit feedback: 做出选择之后只能得到该行为回报的信息。
  • partial feedback. 做出选择之后能得到该行为回报的信息，和其它行为回报的部分信息。
  • full feedback. 做出选择之后能得到全部行为的信息。
• 根据 Rewards:
  • IID rewards: 不同行为的回报相互独立且服从一个固定的概率分布。
  • Adversarial rewards: 对手可以随意更改回报。
  • Constrained adversary: 对手每轮只能有限制地更改回报。
  • Stochastic rewards: 回报服从一个随机过程。比如，两个行为的回报服从一个二维的布朗运动。

Stochastic Bandits

这是最基本的 bandit 问题，其 reward 是 IID 的。

它假定有 $K$ 个 arm，每个 $a \in [K]$ 都有一个（事先未知的） reward distribution ${D}_a$，每次要求我们选择一个 arm 并得到 bandit feedback，目标是最大化 $T$ 轮的总收益。不妨假设 reward 可以被归一化到 $[0,1]$ 区间内。

Stochastic Bandit 的过程如下： $$ \begin{aligned} & \texttt{Stochastic bandit} \\ & \textbf{Given: } \; K \text{ arms, } T \text{ rounds.} \\ & \quad \text {In each round } t \in [T]: \\ & \qquad \text{1. Algorithm picks arm } a_t \in K . \\ & \qquad \text{2. Algorithm observes reward } r_t \in [0, 1] \text{ for the chosen arm}. \end{aligned} $$ 我们希望找到一个算法，来达到尽可能高的期望收益。因此我们自然会关注每个 arm 的期望收益，希望能尽快找到期望收益最高的 arm。

用来衡量一个算法效果的指标是 regret ，其定义是： $$ R(T)=\mu^{\ast} \cdot T-\sum_{t=1}^{T} \mu\left(a_{t}\right) $$ 这里 $a_t$ 是在第 $t$ 轮选择的 arm，$\mu(a_t)$ 是其期望收益，$\mu^\ast = \displaystyle\max_a \mu(a)$ .

因为 $a_t$ 的选择是随机的，所以 $R(T)$ 是一个随机变量，它被称为 pseudo-regret；我们更关注一个算法的期望效果，也就是 $\mathbb{E}[R(T)]$，即 expected regret.

Uniform exploration

一个简单的算法是这样的

1. Exploration phase: 对每个 $a \in [K]$，尝试 $K$ 次
2. Exploitation phase: 挑出样本均值最高的行为 $\hat{a}$，继续剩下的轮次

它清楚地划分了 exploration / exploitation 阶段。

记 arm $a$ 的样本均值为 $\bar{\mu}(a)$，真实的期望收益是 $\mu(a)$，根据 Hoeffding 不等式，二者的接近程度满足以下关系： $$ \mathrm{P}[|\bar{\mu}(a)-\mu(a)| \leq \operatorname{rad}] \geq 1-2 / T^{4}\quad \text { where } \operatorname{rad}:=\sqrt{2 \log (T) / N} $$ 也就是说真实的期望收益 $\mu(a)$ 以很高的概率位于 $[\bar{\mu}(a)] - \text{rad}, \bar{\mu}(a) + \text{rad}]$ 内。

记：

• clean event: $|\bar{\mu}(a)-\mu(a)| \leq \text{rad}$ （真实均值离样本均值很近）
• bad event: $|\bar{\mu}(a)-\mu(a)|>\text{rad}$ （真实均值离样本均值很远）

注意到 bad event 发生的概率是 $O(T^{-4})$ 阶的，因此几乎可以忽略不计。如果对每个 arm 都是 clean event，那么即便我们在 exploration phase 没有找到最优的 arm，我们在 exploitation phase 每轮也至多累计 $2\text{rad}$ 的 regret，这说明此时 $$ R(T) \leq NK + 2 \text{rad} \cdot T $$ 取 $N = {(T/K)}^{2/3}(\log T)^{1/3}$，就有： $$ R(T) \leq T^{2/3} \times O(K \log T)^{1/3} $$ 最终我们可以得到 $$ \mathbb{E}[R(T)] \leq T^{2 / 3} \times O(K \log T)^{1 / 3} $$

Adaptive exploration

记 $n_t(a)$ 为 arm $a$ 的次数，则由 Hoeffding 不等式 $$ \mathrm{P}\left[\left|\bar{\mu}_{t}(a)-\mu(a)\right| \leq r_{t}(a)\right] \geq 1-\frac{2}{T^{4}}, \text { where } r_{t}(a)=\sqrt{2 \log (T) / n_{t}(a)} $$ 对每个 arm $a$ 和时刻 $t$，我们可以记录下上下置信界 $$ \begin{aligned} \mathrm{UCB}_{t}(a) &=\bar{\mu}_{t}(a)+r_{t}(a) \\ \mathrm{LCB}_{t}(a) &=\bar{\mu}_{t}(a)-r_{t}(a) \end{aligned} $$ 区间 $[\textrm{LCB}_t(a), \textrm{UCB}_t(a)]$ 是对 $a$ 的 reward 的一个高置信度的区间估计。

注意到 $r_t(a)$ 的选择是依赖 $T$ 的。

由此引出了 Successive Elimination algorithm

在 $K=2$ 的时候，算法如下：

1. 两个 arm 交替选择，直到某个时刻 $t$ 使得 $\textrm{UCB}_t(a) < \textrm{LCB}_t(a^\prime)$
2. 在余下的轮次均选择 $a^\prime$

对于 $K > 2$ 的情况

1. 可行的 arm 交替选择，直到某个时刻 $t$ ，存在 $a, a^\prime$，使得 $\textrm{UCB}_t(a) < \textrm{LCB}_t(a^\prime)$，此时舍弃 arm $a$
2. 如果只剩下一个 arm，则进入 exploitation phase.

此时的界为 $\mathbb{E}[R(t)] = O(\sqrt{K t \log T})$ .

Optimism under uncertainty

一种 UCB 算法的变种是，每次选取 $\text{UCB}_t(a)$ 最高的 arm。该算法也能达到和 UCB 算法相同的 regret 界。

Sub-exponential rewards

UCB 算法依赖于 Hoeffding 不等式提供的界，而 Hoeffding 不等式依赖于分布的次高斯性。

这篇文章提出了 reward 服从次指数分布情况下的 UCB-rad 算法及其变种。该算法依赖于次指数分布的 concentration inequality。

Thompson Sampling

Thompson Sampling 于 1933 年由 Thompson 提出^[1]。

It would be wrong to say that Thompson sampling was entirely ignored for the next eight decades, but it was definitely not popular until recently, when a large number of authors independently rediscovered the article/algorithm [Graepel et al., 2010, Granmo, 2010, Ortega and Braun, 2010, Chapelle and Li, 2011, May et al., 2012].

—— Bandit Algorithm

Example: Beta-Bernoulli Bandit

有 $K$ 个 bandit，每个 bandit 以概率 $\theta_i$ 返回 1 的 reward，$\theta = (\theta_1, \dots, \theta_K)$ 事先未知，但是其先验分布是参数为 $\alpha=(\alpha_1, \dots, \alpha_K)$ 和 $\beta=(\beta_1, \dots, \beta_K)$ 的 Beta 分布，对 $k \in [K]$ ：

$$ p\left(\theta_{k}\right)=\frac{\Gamma\left(\alpha_{k}+\beta_{k}\right)}{\Gamma\left(\alpha_{k}\right) \Gamma\left(\beta_{k}\right)} \theta_{k}^{\alpha_{k}-1}\left(1-\theta_{k}\right)^{\beta_{k}-1} $$

当 $\alpha_k = \beta_k=1$ 时，$p(\theta_k)$ 是 $[0, 1]$ 上的均匀分布。

如果 $r_t \in \{0, 1\}$ 是时刻 $t$ 的 reward，那么参数的更新规则是： $$ \begin{equation} \left(\alpha_{k}, \beta_{k}\right) \longleftarrow \begin{cases}\left(\alpha_{k}, \beta_{k}\right) & \text { if } x_{t} \neq k \\ \left(\alpha_{k}, \beta_{k}\right)+\left(r_{t}, 1-r_{t}\right) & \text { if } x_{t}=k\end{cases} \label{mab1-ts-updating} \end{equation} $$ 也就是说，如果 $t$ 时刻 pull 第 $k$ 个 bandit 获得了 1 的 reward，就给 $\alpha_k$ 加 1，否则给 $\beta_k$ 加 1。

TS 算法分为以下三步：

1. 从 $\theta \sim p(\theta)$ 中采样 $\hat{\theta}$
2. $x_t = {\arg\max}_{i \in [K]} \;\hat{\theta}_i$
3. 得到 $x_t$ 的 reward $r_t$，按式 $\eqref{mab1-ts-updating}$ 更新 $\theta$ 的后验分布

我们在 step 1 从后验分布中采样获得了一个样本点，在 step 2，我们基于这个参数的样本点选择收益期望最大的行为。

Regret Analysis

这时候的 Bayesian regret 服从如下的渐进式： $$ \lim _{T \rightarrow \infty} \frac{\mathbb{E}[\operatorname{Regret}(T) \mid \theta]}{\log (T)}=\sum_{k \neq k^\ast} \frac{\theta_{k^\ast}-\theta_k}{d_{\mathrm{KL}}\left(\theta_{k^\ast} \| \theta_k\right)} $$ 其中 $d_{\mathrm{KL}}\left(\theta \| \theta^{\prime}\right)= \theta \log \left(\frac{\theta}{\theta^{\prime}}\right)+(1-\theta) \log \left(\frac{1-\theta}{1-\theta^{\prime}}\right)$ 是两个 Bernoulli 分布的 KL 散度。这个 bound 是与实例相关的。

当使用 uniform prior 时，一个 instance-independent 的界是： $$ \max _{\theta^{\prime}} \mathbb{E}\left[\operatorname{Regret}(T) \mid \theta=\theta^{\prime}\right]=O(\sqrt{K T \log (T)}) $$

General Thompson Sampling

一般的 TS 算法也分为三步，其前提假设是给定行为 $x_t$，获得的 reward 服从一个参数 $\theta$ 的概率分布 $q_\theta(\cdot \mid x_t)$，此外参数 $\theta$ 有先验分布 $p(\theta)$

1. 从分布 $p(\theta)$ 中采样 $\hat{\theta}$
2. 此时假定参数 $\theta = \hat{\theta}$，取 $x_t = \arg\max_{i\in [K]} \mathrm{E}_{\theta}[q_{\theta}(\cdot \mid i)]$，即期望收益最大的行为
3. 更新 $\theta$ 的后验分布

如果参数的后验分布不能简便计算的话，可以使用近似方法来估计后验分布。

Thompson Sampling for general stochastic bandits

对于一般的 bandit，也可以应用 TS 算法 ^[2]。

将 reward 归一化到 $[0, 1]$ 上，每个 arm 的 reward 可以是任意的概率分布。我们还是关心其均值 $\theta_i$ 。

1. 从 $\theta \sim p(\theta)$ 中采样 $\hat{\theta}$
2. $x_t = {\arg\max}_{i \in [K]} \;\hat{\theta}_i$
3. 得到 $x_t$ 的 reward $\tilde{r}_t$，以 $\tilde{r}_t$ 为参数生成 Bernoulli 分布的随机数 $r_t$
4. 对 $r_t$ 按式 $\eqref{mab1-ts-updating}$ 更新 $\theta$ 的后验分布

不妨设第一个 arm 是最优的。该算法的 regret 界是： $$ \mathbb{E}[\mathcal{R}(T)] \leq O\left(\left(\sum_{a=2}^N \frac{1}{\Delta_a^2}\right)^2 \ln T\right) $$

Laplace method

假如说 $g$ 是一个连续型随机向量，且其密度函数是单峰 (unimodal) 和对数凹 (log-concave) 的，那么我们可以用一个 Gaussian 分布来近似它。

设 $g$ 的最高点（众数）是 $\bar{\phi}$，那么 $g(\phi) = e^{\ln (g(\phi))}$ 可以用在 $\bar{\phi}$ 处的 Taylor 展开来近似： $$ \ln (g(\phi)) \approx \ln (g(\bar{\phi}))-\frac{1}{2}(\phi-\bar{\phi})^{\top} C(\phi-\bar{\phi}) $$ 其中 $$ C=-\nabla^{2} \ln (g(\bar{\phi})) $$ 于是我们可以找到一个 Gaussian distribution $\tilde{g}$ 来近似 $g$ 了 $$ \tilde{g}(\phi) \propto e^{-\frac{1}{2}(\phi-\bar{\phi})^{\top} C(\phi-\bar{\phi})} $$

$f(x)=\displaystyle\frac{\sin (x)}{x}$ has a global maximum at 0. $e^{M f(x)}$ is shown on top for $M=0.5$, and at the bottom for $M=3$ (both in blue). As $M$ grows the approximation of this function by a Gaussian function (shown in red) improves. This observation underlies Laplace's method.

Langevin Monte Carlo

https://abdulfatir.com/blog/2020/Langevin-Monte-Carlo/

Limitations

Problems that do not Require Exploration

当问题不需要 exploration 的时候，如 contextual bandit 问题，尽管 action 会影响 observation，但实际上 context 的随机性使得再额外的主动 exploration 是不必要的。

In contextual bandit problems, even when actions influence observations, randomness of context can give rise to sufficient exploration so that additional active exploration incurs unnecessary cost.

Contextual Linear Bandit

行为集 $\mathcal{X} = \{1, 2\}$，参数 $\theta_1, \theta_2$ . 每个时刻 $t$，有一个 context $z_t$，reward $r_t = z_t \theta_{x_t} + w_t$，其中 $w_t$ 是一个 i.i.d 零均值的噪声。

Mostly Exploration-Free Algorithms for Contextual Bandits

Problems that do not Require Exploitation

Simple bayesian algorithms for best arm identification

Time Sensitivity

Satisficing in Time-Sensitive Bandit Learning

Problems Requiring Careful Assessment of Information Gain

Learning to optimize via informationdirected sampling

Python Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

import numpy as np
import matplotlib.pyplot as plt
from scipy import stats

# Bernoulli bandit
T = 1000
probs = [0.1, 0.4, 0.65, 0.5, 0.2, 0.78]
K = len(probs)
best_arm = np.argmax(probs)

############ UCB ############

# Initialize, pick each arm once.
arms = list(range(K))
avg_rewards = [stats.bernoulli.rvs(p=prob) for prob in probs]
counter = [1] * K
UCB = [r + np.sqrt(2 * np.log(T)) for r in avg_rewards]

# pseudo-regret
acc_regret = probs[best_arm] * np.arange(1, K + 1) - np.cumsum(probs)
acc_regret = acc_regret.tolist()

# T-K iterations
for _ in range(T-K):
    a = np.argmax(UCB)
    arms.append(a)
    
    reward = stats.bernoulli.rvs(p=probs[a])
    avg_rewards[a] = (avg_rewards[a] * counter[a] + reward) / (counter[a] + 1)
    counter[a] += 1
    
    UCB[a] = avg_rewards[a] + np.sqrt(2 * np.log(T) / counter[a])
    
    acc_regret.append(acc_regret[-1] + probs[best_arm] - probs[a])

plt.plot(acc_regret)

plt.figure()
for i in range(K):
    plt.plot(list(range(1, T + 1)), 
             [arms[:t].count(i) for t in range(1, T + 1)], label=f"arm {i}")
plt.legend()
plt.title("# of arms picked across time $t$")
plt.suptitle("UCB");


######## Thompson sampling #########

# Initialize
alpha, beta = [1] * K, [1] * K
arms = []

# pseudo-regret
acc_regret = [0]

for _ in range(T):
    sample_probs = [stats.beta.rvs(a, b) for a, b in zip(alpha, beta)]
    a = np.argmax(sample_probs)
    arms.append(a)
    
    reward = stats.bernoulli.rvs(probs[a])
    alpha[a] += reward
    beta[a] += 1 - reward
    
    acc_regret.append(acc_regret[-1] + probs[best_arm] - probs[a])

plt.plot(acc_regret)

plt.figure()
for i in range(K):
    plt.plot(list(range(1, T + 1)), 
             [arms[:t].count(i) for t in range(1, T + 1)], label=f"arm {i}")
plt.legend()
plt.title("# of arms picked across time $t$")
plt.suptitle("TS");