多臂老虎机基础

多臂老虎机（Multi-Armed Bandit, MAB）是强化学习中研究探索与利用权衡最经典的框架。¹

问题定义

K臂老虎机模型

设有一台拥有 $K$ 个臂的老虎机，每次拉动臂 $a\in \{1,2,...,K\}$ 会获得一个随机奖励 $r_a\sim p(r|a)$。目标是最大化累积奖励。

数学定义：

• 动作空间：$\mathcal{A}=\{1,2,...,K\}$
• 奖励分布：$r_t(a)\sim \mathcal{N}({\mu }_a,{\sigma }_a^2)$（或一般分布）
• 累积后悔：$C_T=T{\mu }^{\ast }-{\sum }_{t=1}^T\mathbb{E}[r_t]$

其中 ${\mu }^{\ast }={\max }_a{\mu }_a$ 是最优动作的期望奖励。

探索-利用权衡

问题	描述
利用 (Exploitation)	选择当前估计最优的动作
探索 (Exploration)	选择不确定的动作以获取更多信息

这是MAB问题的核心矛盾。

---

经典算法

ε-Greedy算法

最简单的探索策略：以概率 $ϵ$ 随机选择动作，否则选择当前估计最优的动作。

def epsilon_greedy(Q, epsilon, n_arms):
    if np.random.random() < epsilon:
        return np.random.randint(n_arms)  # 探索
    else:
        return np.argmax(Q)  # 利用

优点：实现简单
缺点：无法自适应调整探索程度

上置信界算法 (UCB)

UCB通过为每个动作添加一个置信上界来平衡探索与利用。²

UCB1公式：
$a_t=\arg {\max }_a\left[{\hat{\mu }}_a(t)+c\sqrt{\frac{\ln t}{N_a(t)}}\right]$

其中：

• ${\hat{\mu }}_a(t)$：动作 $a$ 的平均奖励估计
• $N_a(t)$：动作 $a$ 被选择的次数
• $c$：探索常数（通常取 $\sqrt{2}$）
• $\sqrt{\frac{\ln t}{N_a(t)}}$：置信项，次数越少则越大

UCB算法实现：

import numpy as np
 
class UCB:
    def __init__(self, n_arms, c=1.0):
        self.n_arms = n_arms
        self.c = c
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)
    
    def select_arm(self, t):
        # 首次选择每个臂一次
        for arm in range(self.n_arms):
            if self.counts[arm] == 0:
                return arm
        
        # UCB选择
        ucb_values = self.values + self.c * np.sqrt(
            np.log(t + 1) / (self.counts + 1e-10)
        )
        return np.argmax(ucb_values)
    
    def update(self, arm, reward):
        self.counts[arm] += 1
        n = self.counts[arm]
        self.values[arm] = (n - 1) / n * self.values[arm] + reward / n

Thompson Sampling

Thompson Sampling是一种贝叶斯方法，维护每个动作奖励的后验分布。³

算法步骤：

1. 对每个动作 $a$，维护Beta分布 $p({\theta }_a)=\text{Beta}({\alpha }_a,{\beta }_a)$
2. 从每个分布中采样 ${\tilde{\theta }}_a$
3. 选择 $\arg {\max }_a{\tilde{\theta }}_a$

实现：

import numpy as np
from scipy.stats import beta
 
class ThompsonSampling:
    def __init__(self, n_arms):
        self.n_arms = n_arms
        self.alpha = np.ones(n_arms)  # 成功次数 + 1
        self.beta = np.ones(n_arms)   # 失败次数 + 1
    
    def select_arm(self):
        # 从Beta分布采样
        samples = beta.rvs(self.alpha, self.beta)
        return np.argmax(samples)
    
    def update(self, arm, reward):
        if reward > 0:
            self.alpha[arm] += 1
        else:
            self.beta[arm] += 1

---

理论分析

UCB的后悔界

UCB的累积后悔上界为 $O(\sqrt{KT\ln T})$。²

定理（UCB后悔界）：对于任意 $T$，有：
$\mathbb{E}[C_T]\le {\sum }_{a:{\Delta }_a>0}\left[\frac{c\ln T}{{\Delta }_a}+(c+1){\Delta }_a\right]$

其中 ${\Delta }_a={\mu }^{\ast }-{\mu }_a$ 是动作 $a$ 与最优动作的奖励差距。

Thompson Sampling的后悔界

Thompson Sampling同样可以达到 $O(\sqrt{KT})$ 的后悔界。

直觉解释：Thompson Sampling的自然探索特性来自于其后验分布的不确定性。

---

上下文老虎机 (Contextual Bandits)

上下文老虎机扩展了标准MAB，每个时刻除了动作，还观测到一个上下文向量 $x_t$。⁴

LinUCB

LinUCB假设奖励是上下文的线性函数：

$r_t(a)=x_t^{\top }{\theta }_a^{\ast }+{ϵ}_t$

其中 ${\theta }_a^{\ast }$ 是动作 $a$ 的真实参数向量。

算法公式：
${\hat{\theta }}_a=A_a^{-1}{b}_a$
$a_t=\arg {\max }_a\left[x_t^{\top }{\hat{\theta }}_a+\alpha \sqrt{x_t^{\top }{A}_a^{-1}{x}_t}\right]$

其中 $A_a={\sum }_{\tau }{x}_{\tau }{x}_{\tau }^{\top }+I$，$b_a={\sum }_{\tau }{r}_{\tau }{x}_{\tau }$。

import numpy as np
 
class LinUCB:
    def __init__(self, n_arms, n_features, alpha=1.0):
        self.n_arms = n_arms
        self.alpha = alpha
        self.A = [np.eye(n_features) for _ in range(n_arms)]
        self.b = [np.zeros(n_features) for _ in range(n_arms)]
    
    def select_arm(self, x):
        p = np.zeros(self.n_arms)
        x = x.reshape(-1, 1)
        
        for a in range(self.n_arms):
            A_inv = np.linalg.inv(self.A[a])
            theta = A_inv @ self.b[a]
            p[a] = x.T @ theta + self.alpha * np.sqrt(x.T @ A_inv @ x)
        
        return np.argmax(p)
    
    def update(self, arm, x, reward):
        x = x.reshape(-1, 1)
        self.A[arm] += x @ x.T
        self.b[arm] += reward * x.flatten()

---

深度老虎机

深度老虎机使用神经网络来近似奖励函数或策略。⁵

DEED (Deep Exploration via Ethically Decoupled)

DEED结合了深度网络和UCB风格的探索：

class DeepBandit:
    def __init__(self, n_arms, feature_dim):
        self.n_arms = n_arms
        # 共享特征编码器
        self.encoder = nn.Sequential(
            nn.Linear(feature_dim, 128),
            nn.ReLU(),
            nn.Linear(128, 64)
        )
        # 每个臂的价值头
        self.value_heads = nn.ModuleList([
            nn.Linear(64, 1) for _ in range(n_arms)
        ])
        # 探索头 - 预测不确定性
        self.uncertainty_heads = nn.ModuleList([
            nn.Linear(64, 1) for _ in range(n_arms)
        ])
    
    def forward(self, x):
        features = self.encoder(x)
        values = torch.stack([head(features) for head in self.value_heads])
        uncertainties = torch.stack([head(features) for head in self.uncertainty_heads])
        return values.squeeze(-1), uncertainties.squeeze(-1)
    
    def select_arm(self, x):
        with torch.no_grad():
            values, uncertainties = self.forward(x)
            scores = values + self.exploration_weight * uncertainties
        return torch.argmax(scores).item()

---

应用场景

推荐系统

问题	方法
新闻推荐	LinUCB、深度老虎机
广告投放	Thompson Sampling
搜索排序	Bandit排序学习

临床试验

• 适应性临床试验设计
• 个性化治疗选择

其他应用

• 网络路由
• 动态定价
• 机器人探索

---

算法对比

算法	后悔界	优点	缺点
ε-Greedy	$O(\sqrt{T})$	简单	需要手动调参ε
UCB	$O(\sqrt{KT\ln T})$	有理论保证	过度探索
Thompson Sampling	$O(\sqrt{KT})$	适应性强	需维护后验
LinUCB	$O(\sqrt{dT\ln T})$	利用上下文	假设线性

---

参考资料

---

相关链接

• 探索-利用权衡 — RL中的探索策略
• 在线学习理论 — 更一般的在线学习框架
• 分布式RL算法 — 分布式环境下的老虎机算法

Footnotes

1. Sutton & Barto, “Reinforcement Learning: An Introduction”, Chapter 2 ↩

2. Auer et al., “Finite-time Analysis of the Multiarmed Bandit Problem”, Machine Learning, 2002 ↩ ↩²

3. Russo et al., “A Tutorial on Thompson Sampling”, Foundations and Trends in Machine Learning, 2018 ↩

4. Li et al., “A Contextual-Bandit Approach to Personalized News Article Recommendation”, WWW, 2010 ↩

5. Riquelme et al., “Deep Bayesian Bandits Showdown”, ICLR, 2018 ↩