多臂老虎机Bandit：试错中的最优选择

可视化演示

展示多臂老虎机问题中三种经典策略（ε-greedy、UCB、Thompson采样）的探索与利用权衡过程。

问题定义：站在一排老虎机前

小美把五款配方编成 1 到 5 号，在吧台上一字排开。每来一位顾客，就相当于她拉起其中一台“老虎机”的摇杆：推荐 1 号，顾客满意记 1 分，不满意记 0 分。机器背后各有一个固定的“中奖率”（被顾客喜爱的概率），但小美看不到，只能从每一次好评差评的反馈里慢慢猜。

在数学上，五款配方被称作五只“臂”（arm），一次推荐就是一轮“拉杆”，顾客的好评就是“奖励”（reward）。问题来了：是继续推荐目前好评率最高的那款，还是把机会分给还没被充分验证的配方？前者叫“利用”（exploitation），后者叫“探索”（exploration），两者互相争夺有限的顾客流量，这就是 Bandit 的核心矛盾。

为了比较不同策略谁更聪明，学者定义了“遗憾”（Regret）：假设存在一位“事后诸葛亮”，他永远知道每轮该推荐哪款才能拿到最优奖励，把他能拿到的总奖励减去我们实际策略拿到的总奖励，差值就是遗憾。遗憾越小，说明试错越高效。

想通这一点后，小美不再纠结“哪款一定最好”，而是把目标定为“让累计遗憾尽量小”：允许自己犯错，但错要错得值——每轮选择都要为未来收集信息和当下拿奖励做出最优权衡。这正是所有 Bandit 算法共同的设计哲学。

ε-greedy：大部分时候精明，偶尔犯傻

小美决定先试最简单的策略：定一个很小的概率 ε（比如 0.1）。营业时，她拿一枚“偏心骰子”做决定——骰子落在 10% 的区间，就随机推荐一款配方尝尝鲜；落在 90% 的区间，就推荐目前好评率最高的那款。这个方法叫“贪婪加强随机”，英文名 epsilon-greedy。

“greedy“（贪婪）指的是每次尽量选当前估计最佳的手臂，把流量集中给”赢家”；“epsilon“（ε）则给探索留了一扇小门，让没被充分验证的配方也有机会被选到。这个策略虽然简单，却精准地刻画了”大部分时候精明、偶尔犯傻”的决策风格。

从概率角度看，任意一轮中，当前最优臂 $\hat{a}$ 被选中的概率接近 $1-\epsilon$，其余每只臂也都有 $\tfrac{\epsilon}{K}$ 的机会被随机选中，其中 $K$ 是臂的总数。写成公式：

ε 的取值很有讲究：太小，冷门配方永远没机会证明自己；太大，流量大量浪费在明显差劲的配方上。小美发现 ε=0.1 是个不错的起点，而且实现只要十行代码——这也解释了为什么 epsilon-greedy 至今仍是工业界的标准“起跑线”基线。

UCB算法：给未知一点乐观的加分

用小美的话说，epsilon-greedy 的探索有点“闭着眼睛乱逛”：它可能反复去尝一款明显不好喝的配方，却对另一款“只试过两次、两次都好喝”的配方不够上心。问题出在它没有区分“信息量”——被尝试次数越少的配方，好评率估计越不可靠，越值得优先再试。

于是有了“置信上界”（Upper Confidence Bound, UCB）的思路：给每款配方算一个综合得分——目前平均好评率加上一个“未知奖励项”。这个奖励项跟配方被尝试的次数 $n_a$ 成反比：试得越少，加分越多。这样一来，没被充分验证的配方会持续获得额外加分，直到数据足够，加分数值自然变小，让真实水平“原形毕露”。

UCB 每轮选择得分最高的配方，公式如下：

这一招叫“乐观地看待未知”：假设还没被验证的配方可能比现在看起来更好。小美惊喜地发现，UCB 不再盲目随机探索，而是自动把试验机会优先分给“最值得被了解”的配方，累计遗憾的增长速度接近理论最优点 $\mathcal{O}(\ln T)$——比 epsilon-greedy 聪明得多。

汤普森采样：让概率分布自己说话

UCB 靠手动设计“加分公式”引导探索，Thompson 采样则换了一个思路：不为每款配方算一个分数，而是为它的“真实好评率”建立一个完整的概率分布，每轮从这个分布里随机抽一个数，谁抽到的数大就推荐谁。小美觉得这像在玩“抽签决定推荐”的游戏，但签筒的形状会随数据不断变化。

这个分布通常用 Beta 分布刻画。Beta 分布像一本带先验的小账本：$\alpha$ 记好评次数，$\beta$ 记差评次数（初始各加 1，表示“还没试过之前我们保持中立”）。好评越多，分布整体右移，抽到高值的概率变大；差评越多，分布左移；样本越多，分布越“尖”——说明我们对这款配方的真实评价越来越有把握。

每轮按如下方式决策：

Thompson 采样的妙处在于自动平衡探索与利用：当一款配方数据不足、分布宽而扁时，它抽到高值的概率很大，自然频繁被选中；当它被验证、分布变尖后，抽到低值的概率越来越多，被选中的机会也随之下降。小美发现它连 ε 都不用调，被业界称为“贝叶斯式的直觉决策”。

LinUCB：带上用户画像的决策

试了一段时间，小美隐约觉得不对劲：前面的算法都默认“同一款配方对所有顾客吸引力相同”，可现实是白领偏爱清爽果茶，学生偏爱浓郁奶茶。两款配方总体好评率接近，但各自的“粉丝”完全不同——把所有顾客的数据混在一起算平分，太粗糙了。

LinUCB 的解决方法是给决策引入“上下文”（context）：每位顾客的画像（年龄段、到店时段）和每款配方的类型组成一个特征向量 $x$，为每款配方单独拟合一个线性模型，预测“这类顾客对这款配方的满意概率”。预测不再是一个全局常数，而是随顾客特征变化。

选择配方时，LinUCB 沿用 UCB 的“均值 + 不确定项”结构：

LinUCB 让决策从“千人一面的平均最优”升级为“千人千面的个性化最优”。新顾客刚进店，没有历史反馈，但只要知道她的画像，模型就能借助相似顾客的经验给出不错的首推。小美的吧台上多了一本“顾客画像登记册”，推荐命中率肉眼可见地提升了。

上下文老虎机：千人千面的在线学习

把 LinUCB 放到更大的框架里看，它属于一个叫 Contextual Bandit（上下文老虎机）的算法家族。普通多臂老虎机只回答“哪只臂整体最好”，Contextual Bandit 则回答“在什么情境下哪只臂最好”。它的名字直白：每一轮都要先观察上下文 $x_t$（顾客是谁、什么场景），再决定推哪只臂，最后获得对应的奖励。

小美发现自己的经验总结方式也变了：以前她会说“3 号最好喝”，现在她会总结“晴天傍晚、结伴女性顾客，3 号好评率显著更高；雨天单人顾客，5 号表现更好”。这些“情境-动作-奖励”的对应关系，正是 Contextual Bandit 想在线学到的策略。

LinUCB 的参数更新也是典型的在线增量式写法：

对推荐冷启动来说，Contextual Bandit 尤其重要：新用户没有行为历史，协同过滤无从谈起，但只要存在画像特征，就能结合相似人群的经验给出个性化推荐，并随着用户行为不断修正。在线学习让模型“边接客、边学习”，永远跟得上变化。

应用与实战：从试错到放量

小美的奶茶店只是一个缩影。把“顾客”换成“广告曝光”、“配方”换成“素材”，就是广告系统的日常：新素材没有任何点击数据，要不要给它流量？给多少？如果把流量均匀分给所有素材，等于把一半以上的预算浪费在明显跑不动的创意上。

Bandit 在工业界的三大典型战场：广告投放中用 UCB/LinUCB 动态分配合适曝光给新旧素材；推荐冷启动中用 Thompson 采样快速建立新用户兴趣画像；实验分流中用 Bandit 替代固定的五五开 A/B test，让流量实时流向表现更好的版本。三者共享同一句口诀——探索要趁早，利用要跟上。

实战中一个重要调参是让探索率随时间衰减。早期对一切好奇，多尝试；后期资源有限，偏向利用已知最优。常见做法：

上线前还要做离线评估：用历史日志“重放”（replay）各策略，看看如果当初用了 Thompson 或 LinUCB，累计收益会不会更高。小美的奶茶店也遵循同样的流程——先小范围试跑、看真实反馈、再决定全量推广。试错不是乱试，而是每步都有衡量、有边界、有节奏。

AI 应用场景

Python 演示

import mathimport random  class BanditSim:    """多臂老虎机模拟器: 维护每只手臂的尝试次数与累计奖励"""     def __init__(self, true_probs):        self.true_probs = true_probs        self.count_list = [0] * len(true_probs)        self.reward_sum = [0.0] * len(true_probs)     def pull(self, arm):        return 1.0 if random.random() < self.true_probs[arm] else 0.0     def play_epsilon_greedy(self, rounds, epsilon):        total = 0.0        for _ in range(rounds):            if random.random() < epsilon:                arm = random.randint(0, len(self.true_probs) - 1)            else:                arm = max(                    range(len(self.true_probs)),                    key=lambda i: self.reward_sum[i] / max(self.count_list[i], 1)                )            reward = self.pull(arm)            self.count_list[arm] += 1            self.reward_sum[arm] += reward            total += reward        return total / rounds     def play_ucb(self, rounds):        total = 0.0        for t in range(1, rounds + 1):            best_val = -1.0            arm = 0            for i in range(len(self.true_probs)):                if self.count_list[i] == 0:                    ucb = float("inf")                else:                    avg = self.reward_sum[i] / self.count_list[i]                    ucb = avg + math.sqrt(2.0 * math.log(t) / self.count_list[i])                if ucb > best_val:                    best_val = ucb                    arm = i            reward = self.pull(arm)            self.count_list[arm] += 1            self.reward_sum[arm] += reward            total += reward        return total / rounds  def main():    random.seed(42)    true_probs = [0.30, 0.50, 0.70, 0.55, 0.42]     eg_sim = BanditSim(true_probs)    eg_avg = eg_sim.play_epsilon_greedy(3000, 0.1)     ucb_sim = BanditSim(true_probs)    ucb_avg = ucb_sim.play_ucb(3000)     print("epsilon-greedy 平均奖励: %.4f" % eg_avg)    print("UCB          平均奖励: %.4f" % ucb_avg)    print("最优手臂真实概率  : %.2f" % max(true_probs))    print("UCB 相比 epsilon-greedy 提升: %.2f%%"          % ((ucb_avg - eg_avg) / eg_avg * 100))  if __name__ == "__main__":    main()

1. self.count_list = [0] * len(self.true_probs)初始化每只手臂的尝试次数，供后面算平均和探索加分。
2. if random.random() < epsilon:以 ε=0.1 的概率随机探索一只臂。
3. key=lambda i: self.reward_sum[i] / max(self.count_list[i], 1)否则选出平均奖励最高的臂，max 防止除以 0。
4. reward = self.pull(arm)模拟拉杆：按真实概率返回 1（好评）或 0（差评）。
5. if self.count_list[i] == 0: ucb = float("inf")没试过的臂给无穷大上界，保证每只臂至少先体验一次。
6. ucb = avg + math.sqrt(2.0 * math.log(t) / self.count_list[i])实现 UCB 的“均值 + 探索加分”公式。
7. random.seed(42)固定随机种子，让两次实验在完全相同的随机序列下对比，结论更公平。

常见误区

面试题