多臂老虎机问题 问题定义 多臂老虎机问题（Multi-Armed Bandit Problem, MAB）是概率论与决策理论中的经典模型，用于描述在不确定性下的资源分配问题。假设一个赌场中有多台老虎机（即“臂”），每台老虎机每次被拉动时以一定概率提供奖励，但玩家不知道每台机器的奖励概率分布。目标是通过有限次数的尝试，最大化累计奖励。该问题本质上是 探索（尝试新机器） 与 利用（选择当前已知收益最高的机器） 之间的权衡。 核心挑战：探索-利用困境 若只利用当前最优选择，可能错过潜在更高奖励的臂；若过度探索，则会浪费机会在低收益臂上。例如，假设有3台老虎机，其真实奖励概率分别为0.3、0.5、0.7，但玩家初始未知。需设计策略以动态平衡探索与利用。 数学建模 设共有 \(K\) 个臂，每个臂 \(i\) 的奖励服从未知分布 \(P_ i\)，期望奖励为 \(\mu_ i\)。 在时间 \(t=1,2,\dots,T\)，玩家选择一个臂 \(a_ t\)，获得奖励 \(r_ t \sim P_ {a_ t}\)。 目标是最小化 遗憾 ： \[ R(T) = T \cdot \max_ i \mu_ i - \sum_ {t=1}^T \mathbb{E}[ r_ t ], \] 即与始终选择最优臂的累积奖励差距。 经典策略：ε-贪心算法 以概率 \(\varepsilon\) 随机选择一个臂（探索），以概率 \(1-\varepsilon\) 选择当前平均奖励最高的臂（利用）。 缺点：探索频率固定，可能无法自适应调整。 改进策略：上置信界算法 UCB（Upper Confidence Bound）算法为每个臂计算一个置信上界： \[ \text{UCB}_ i(t) = \bar{\mu}_ i(t) + \sqrt{\frac{2 \ln t}{n_ i(t)}}, \] 其中 \(\bar{\mu}_ i(t)\) 是臂 \(i\) 到时间 \(t\) 的平均奖励，\(n_ i(t)\) 是拉动次数。 选择具有最大UCB值的臂，平衡当前收益（第一项）和不确定性（第二项）。 理论保证：UCB的遗憾增长率为 \(O(\sqrt{T \ln T})\)，优于ε-贪心。 贝叶斯方法：汤普森采样 为每个臂的奖励分布设定先验（如Beta分布），每次根据后验分布采样一个奖励估计值，选择采样值最大的臂。 通过不断更新后验分布，自适应调整探索与利用，适用于非平稳环境（奖励分布随时间变化）。 应用场景 在线广告 ：选择点击率最高的广告位。 医疗试验 ：在疗效不确定时分配治疗方案。 推荐系统 ：动态优化内容展示策略。 扩展模型 上下文老虎机 ：引入用户特征等上下文信息。 非平稳老虎机 ：奖励分布随时间变化，需使用滑动窗口或加权更新。 组合老虎机 ：一次选择多个臂（如推荐多个商品）。 通过以上步骤，多臂老虎机问题从基础定义逐步深入到高级策略与应用，体现了运筹学在不确定性决策中的核心思想。