多臂老虎机算法（Multi-Armed Bandit, MAB）详解-编程实验室

多臂老虎机算法（Multi-Armed Bandit, MAB）详解

多臂老虎机算法是一类在线学习算法，核心解决 “探索 - 利用权衡”（Exploration-Exploitation Tradeoff）问题 —— 在不确定每个选项（“臂”）收益分布的情况下，通过动态选择策略最大化长期累积收益。它广泛应用于推荐系统、A/B 测试、路径优化、资源分配等场景，尤其适合数据稀疏、需要实时决策的场景（如你的运输路线规划中，动态选择最优路线 / 货运方式）。

本文将从 “基础概念→核心问题→经典算法→变种扩展→项目应用→代码实现” 逐步讲解，兼顾理论深度和工程实用性。

一、基础概念：什么是 “多臂老虎机”？

1.1 场景类比

想象你面前有 N 台老虎机（“多臂”），每台机器的中奖概率（或收益）不同，且你不知道具体分布。你的目标是通过多次拉杆（“决策”），最大化总收益 —— 这就是多臂老虎机的核心场景：

臂（Arm）：可选的决策选项（如运输路线规划中的 “路线 A”“路线 B”“路线 C”，货运方式中的 “公路”“铁路”“海运”）。
收益（Reward）：选择某臂后获得的反馈（如路线的 “运输时间”“成本”“准时率”，可转化为量化收益，例如：准时率 90% 对应收益 0.9，延迟对应负收益）。
探索（Exploration）：尝试未选过或选择次数少的臂，获取更多收益分布信息（如尝试一条新的运输路线，了解其实际耗时）。
利用（Exploitation）：选择当前已知收益最高的臂，最大化即时收益（如一直走已知最快的路线）。

1.2 数学建模

设共有 K 个臂，第 i 个臂的收益服从分布\(R_i \sim P_i(r)\)（如伯努利分布：中奖 / 未中奖；高斯分布：运输时间的波动）。
每个臂的 “真实价值” 为期望收益：\(\mu_i = E[R_i]\)。
算法目标：通过 T 次决策（T 轮拉杆），选择序列\(a_1, a_2, ..., a_T\)（\(a_t \in \{1,2,...,K\}\)），最大化累积收益：\(\sum_{t=1}^T R(a_t)\)，或最小化 “累积遗憾”（Regret）：\(Regret(T) = T \cdot \mu^* - \sum_{t=1}^T \mu_{a_t}\)（\(\mu^*\)是所有臂的最大真实价值）。

二、核心问题：探索与利用的权衡

这是多臂老虎机的本质矛盾：

只 “利用”：一直选当前最优臂，可能错过更优的未知臂（如一直走老路，却不知道新路线更快），长期收益受限。
只 “探索”：频繁尝试新臂，牺牲即时收益，导致短期损失过大（如每次都试新路线，多次遇到拥堵）。

所有多臂老虎机算法的差异，本质是探索策略的设计—— 如何在 “获取信息” 和 “获取收益” 之间找到最优平衡。

三、经典多臂老虎机算法

3.1 贪心算法（Greedy）：纯 “利用”，无探索

原理

初始化：对每个臂尝试 m 次（m≥1），计算各臂的平均收益\(\hat{\mu}_i = \frac{1}{m} \sum_{k=1}^m R_i^k\)。
决策：之后每一轮都选择当前平均收益最高的臂（若有多个，随机选一个）。
变种：“纯贪心”（m=1，仅尝试一次就固定选择）。

公式

\(a_t = \arg\max_{i \in \{1,..,K\}} \hat{\mu}_i(t-1)\)（\(\hat{\mu}_i(t-1)\)是前 t-1 轮中臂 i 的平均收益）

优缺点

优点：实现最简单，计算成本低，短期收益稳定。
缺点：完全没有探索，若初始尝试次数 m 不足，可能锁定次优臂（如初始尝试新路线时刚好遇到拥堵，误判为差路线），长期遗憾会随 T 线性增长（Regret(T) ∝ T）。

适用场景

收益分布稳定、初始数据充足，且不担心错过最优臂的场景（不推荐用于运输路线规划，因路线收益受路况、天气影响，需动态探索）。

3.2 ε- 贪心算法（ε-Greedy）：固定概率探索

原理

在贪心算法基础上引入 “探索概率 ε”（0<ε<1），平衡探索与利用：

每一轮决策时，以概率\(1-\varepsilon\)选择当前最优臂（利用）；
以概率\(\varepsilon\)随机选择一个臂（探索，不管当前收益高低）。
变种：衰减 ε- 贪心（\(\varepsilon(t) = \frac{1}{\sqrt{t}}\)或\(\varepsilon(t) = \frac{\varepsilon_0}{t}\)），随着轮次 t 增加，探索概率逐渐降低（符合 “初期多探索，后期多利用” 的直觉）。

公式

\(a_t = \begin{cases} \arg\max_{i} \hat{\mu}_i(t-1) & \text{with probability } 1-\varepsilon(t) \\ \text{random arm} & \text{with probability } \varepsilon(t) \end{cases}\)