ε-greedy与UCB——多臂老虎机的探索利用困境
梯度Bandit与关联搜索——从多臂老虎机到上下文老虎机
探索利用困境统一序贯决策抽象
thompson-sampling-tutorial-russo
contextual-bandits-production
online-shortest-path-thompson
博弈论与网络科学的计算实验从囚徒困境锦标赛到Agent建模.md
决策科学Notebooks全集19个端到端行业实战从金融风控到安全ROI.md---

自适应实验与多臂老虎机——从固定样本检验到动态最优分配的范式转换¶

核心论点¶

传统的 A/B 测试在实验开始前就固定了样本量和分配比例。自适应实验（多臂老虎机）则将其反转：它根据已观察到的结果持续更新流量分配，在学习和优化的同时进行——每一步既消耗数据又产生数据。这一范式的核心张力是探索-利用困境：应该分配流量去了解那些还不确定但可能更好的臂（探索），还是集中流量在目前看起来最好的臂上（利用）。多臂老虎机不是「更好的 A/B 测试」——它是解决另一个优化问题的工具：不是最大化统计置信度，而是最小化累积遗憾（opportunity cost）。

Organize into layers:

第一层——k 臂老虎机问题的数学表述¶

动作价值与遗憾。k 臂老虎机中，每一步 Agent 从 k 个动作中选择一个，获得随机奖励 R_t。每个动作 a 有一个未知的真实期望价值 q(a) = E[R_t | A_t = a]——这是概率分布（奖励函数）的「真值」，Agent 通过试错来逼近它。最优动作 a 满足 q(a) = max_a q(a)。遗憾定义为选择了非最优动作时所损失的期望奖励：每一步的 regret = q(a) − q(a_t 实际选的那个)。累积遗憾是衡量探索策略质量的核心指标——它度量了「探索的机会成本」。

增量更新是通用学习模板。样本平均法 Q_{n+1} = Q_n + (1/n)(R_n − Q_n) 经代数重排可得增量形式——每一步只需 O(1) 内存和计算，无需存储所有历史奖励。更一般的式子 NewEstimate ← OldEstimate + StepSize × [Target − OldEstimate] 是贯穿强化学习的通用模板：它表达了一个学习过程——新估计朝「目标」（实际观测到的奖励）移动，误差随步数递减。在非平稳问题中，常数步长 α 替代 1/n 使近期奖励权重指数衰减（指数近因加权平均），避免样本平均对远期过时数据的等权对待——这本质上是对数据生成过程「可能随时间变化」这一假设的编码。

探索-利用困境的视界依赖性。最优探索策略取决于剩余时间：如果只剩最后一次决策，纯利用最优（没有时间享受探索的收益）；如果有无限步决策，应侵略性地探索（长期收益压倒短期损失）。ε-greedy 和 UCB 都是无限视界下的启发式——它们假设步数无限，因此永远保持一定探索量。但若视界有限（如只剩 100 步），最优策略会从「探索 + 利用」向「纯利用」逐渐收敛。Gittins index 和贝叶斯动态规划解决了有限视界的最优分配，但因状态空间爆炸在完整 RL 中不可行。这解释了一个务实立场：在完整 RL 中，这些简单方法作为更大算法子组件的「够好性」远重要于其在 bandit 设定中的精确最优性。

第二层——探索策略的四种哲学¶

探索策略的设计本质上是对「不确定性的价值」的不同定价方式。四种策略代表了四种不同的探索哲学：

ε-greedy——盲目均等的探索。以概率 1−ε 选择当前估计价值最高的动作，以概率 ε 从所有动作中均匀随机选择。它保证每个动作被无限次采样，但探索是盲目的——不区分「接近最优但不确定」和「明显更差」的动作，对两者分配相同的探索概率。这是最简单的策略，也是最浪费样本的策略。ε 可以取常数（非平稳环境）或随 t 衰减（平稳环境，如 ε_t = 1/t）——衰减 ε 在理论上可达到对数遗憾界，但衰减速率的选择又引入了新的超参数。

乐观初始值——通过初始偏见驱动探索。将动作的初始价值估计 Q_1(a) 设为远高于真实值的正数（如 +5）。即使使用纯贪婪策略（ε = 0），早期也会触发大量探索——因为 Agent 在任何动作上获得的实际奖励都远低于初始估计，每次都「失望」并尝试其他动作。这是一个巧妙但适用范围有限的技巧：它在平稳问题上有效（早期探索驱动天然的「试一轮就收敛」），但在非平稳问题上探索驱动力是暂时的——「时间的起点只发生一次」。乐观初始值可以视为一种特殊的先验信念——先假设所有动作都很好，让数据逐步修正。

UCB——定向乐观的探索。UCB (Upper Confidence Bound) 选择策略为 A_t = argmax_a [Q_t(a) + c√(ln t / N_t(a))]。其中平方根项是估计值不确定性的度量（来自 Chernoff-Hoeffding 界），c 控制置信水平——c 越大越乐观（探索越多）。UCB 的探索是定向的：当某个动作采样次数少（N_t(a) 小）时 bonus 项变大，将其推到前端；当某个动作长期不被选，不确定性项因 ln t 增长而积累，最终迫使其被重探。本质上，UCB 为每个动作构建一个置信上界，选择上界最高的动作——等价于一种「乐观面对不确定性」原则的形式化。在 10-armed testbed 上，调优后的 UCB 通常优于 ε-greedy，但更难推广到非平稳和大状态空间的完整 RL。

Thompson Sampling——贝叶斯全分布的探索。Thompson Sampling (1933) 走了一条完全不同的路：为每个动作维护奖励参数 θ_a 的后验分布 P(θ_a | data)（如在伯努利奖励下用 Beta 先验，每次观测到成功/失败后更新）。决策时，从每个动作的后验中采样一个 θ_a，选择采样值最大的动作。这使 Thompson Sampling 天然具备概率匹配属性：一个动作被选中的概率等于它是当前真正最优动作的概率。与 ε-greedy 和 UCB 不同的是，前者是频率学派点估计驱动的——基于 Q_t(a) 做确定性或半确定性选择；Thompson Sampling 是贝叶斯学派全分布驱动的——通过采样捕捉参数不确定性，高不确定性臂自然有更大被选中的概率但不必然每次都被选中。它不需要手动调探索参数（如 UCB 的 c），在非平稳和带结构先验的场景中有天然优势。

梯度 Bandit——策略梯度的始祖。梯度 bandit 不估计动作价值，而是为每个动作学习一个偏好值 H_t(a)，选择概率由 softmax 给出。更新规则为选中动作 H += α(R − ̄R)(1 − π)，未选动作 H −= α(R − ̄R)π。这个更新是 E[R_t] 的随机梯度上升的正确实现——baseline ̄R_t 不改变期望更新方向但显著降低方差。梯度 bandit 是 REINFORCE 算法和 actor-critic 方法的原型——代表了 RL 中直接优化策略参数而非通过价值函数间接选择的策略梯度学派，与动作价值方法（ε-greedy、UCB）形成 RL 的两条根本技术路线。

第三层——从上下文无关到上下文感知¶

关联搜索（上下文老虎机）。当 bandit 任务的奖励分布随观察到的上下文（用户特征、时段、设备类型）变化时，Agent 需要学习从上下文 s 到最优动作 a 的映射——即策略 π(s)。每条臂仍只影响即时奖励（不像完整 MDP 中动作还改变下一状态），但最优动作取决于上下文。有无上下文信息的差异是质的飞跃：无上下文时，Agent 只能对全体学一个固定最优动作（无条件平均最优）；有上下文时，Agent 可以学习在每种情境下的差异化最优动作——这使得期望收益可以超越无条件最优。

从上下文老虎机到完整 RL 的断层。上下文老虎机是 bandit 和完整 RL 之间的中间形态。在上下文老虎机中，动作只影响即时奖励——动作之间没有状态转移。完整 RL 中，动作还影响下一个状态 P(s' | s, a)，引入了两个额外复杂度：(1) 信用分配——当前动作的奖励后果可能在 N 步后才显现；(2) 长期规划——需要权衡即时奖励和未来奖励。这使得「探索」在完整 RL 中更复杂——不仅需要探索动作的即时奖励，还需要探索状态转移结构以规划长期路径。

现实应用。上下文老虎机的商业应用远比完整 RL 成熟——在大多数推荐和定价场景中，即时奖励假设是合理近似（用户点击的回报几乎是即时的），而完整 MDP 的转移模型往往被时间带来的分布漂移破坏。个性化推荐、动态定价、临床试验中的自适应分配，都是上下文老虎机的典型战场。

第四层——与固定样本实验的关系¶

A/B 测试与 bandits 是两种不同的决策框架。固定样本 A/B 测试解决的是因果推断问题——以指定的统计置信度（通常 95%）判断 B 是否确实优于 A。Bandits 解决的是优化问题——在实验过程中持续调整分配以最大化累积奖励。两者的核心差异不在「是否自适应」，而在目标函数不同：A/B 测试最小化假阳性/假阴性率（type I/II errors）；bandits 最小化遗憾（分配次优臂的累计损失）。

Bandits 的代价。Bandits 比 A/B 测试更「高效」（减少遗憾），但也带来新的风险：(1) 时间趋势会与分配变化混淆——如果外部环境在实验期间改善，bandits 会将更多流量分配给后期才变好的臂，但无法区分「臂变好了」还是「环境变好了」；(2) bandit 数据是「on-policy」的观测数据——分配概率取决于历史结果，打破了 i.i.d. 假设。因此 A/B 测试在需要严格因果推断（如药物审批、政策评估）时不可替代，bandits 在损失敏感且因果推断非首要目标（如网站优化、广告投放）时是更优选择。

遗憾预算 vs 学习预算。A/B 测试可以理解为「先花遗憾预算来学习，学完了再纯利用」；bandits 则是「边学边利用，随时都在尝试缩小遗憾」。选择哪个框架取决于：(1) 对因果结论的需求强度；(2) 实验的样本量和时间约束；(3) 错误分配流量的实际代价（机会成本）；(4) 是否可以承受 bandit 数据的时间混杂。

跨域链接¶

→ 概念笔记「博弈论基础——策略互动的数学语法」：Thompson Sampling 在竞争环境中的扩展（如多 Agent bandit、博弈论 bandit）将探索-利用困境从单人优化推入策略互动的世界。混合策略的无差异原则与 Thompson Sampling 的概率匹配属性共享底层逻辑——都是通过随机化消除信息劣势。在竞争环境中的 A/B 测试，纯策略（确定性地使用最优变体）使竞争对手可观测并优化应对；bandit 策略保留了策略模糊性。
→ 概念笔记「机器学习项目失败原因金字塔」：强化学习是 ML 三范式中唯一内嵌决策的范式——监督学习假设正确答案已知，无监督学习没有反馈目标，只有 RL 假设 Agent 通过试错主动收集反馈。Bandits 是 RL 的最简形态（一步 MDP），而 bandits 的失败模式直接映射到失败金字塔：如果将 bandits 当作「不需要统计学家」的魔法而忽视时间趋势和置信区间，则属于数据和评估层的失败。
→ 概念笔记「因果推断方法阵营的分歧不在数学」：上下文老虎机本质上是一个基于观测数据的动态处理分配问题——在每个上下文中学习哪个动作（处理）能最大化期望奖励（结果）。它与因果推断中 policy learning 的联系是直接的：如果数据来自随机化实验或满足无混淆假设，就可以用 IPW 或 doubly robust 估计器学习最优策略。区别在于因果推断通常从一批历史数据中学习固定策略，而 bandits 在线交互学习——每一步既消耗数据又产生数据。
→ 概念笔记「关联不等于因果——可交换性是分界线」：Bandit 数据在实验内部是观察性的——分配概率随历史结果变化，打破了 i.i.d. 假设。时间趋势（如季节性、用户成熟度）会与分配变化混淆——当外部环境改善时，bandits 将更多流量分配给后期流量暴增的臂，但无法区分因果。可交换性在自适应实验中不再是「是否随机分配」的二元属性，而是在不同时间点的分配机制是否可比。
→ 概念笔记「频率学派推断框架的核心张力」：频率学派 bandits（UCB）的核心产出是遗憾界（regret bound）——频率统计的自然延伸：「如果在同样条件下重复这个实验无数次，累积遗憾的上界是多少」。UCB 的 bonus 项 √(ln t / N_t(a)) 来自 Chernoff-Hoeffding 浓度不等式——这是频率学派「构造置信区间」的思维方式直接映射到决策中。
→ 概念笔记「概率分布的选择不是数学偏好」：Bandits 的奖励分布假设是方法选择的核心分水岭。Thompson Sampling 要求对奖励分布有完整的概率模型（如 Beta-Bernoulli 用于二值奖励、Gaussian-Gaussian 用于连续奖励），而 UCB 只需要有界的奖励支持——前者通过分布形状编码先验知识，后者通过浓度不等式构造探索 bonus。分布假设的选择不是数学技术偏好——它直接决定了在有限样本下探索效率的高低。
→ 概念笔记「度量选择是元决策」：Bandits 中奖励函数的设计就是度量选择。如果你把「用户点击」作为奖励，你优化的是点击率；如果以「长期留存」为奖励，你优化的是用户质量。Bandits 让这个选择变得更具操作性——但更加危险，因为系统会自动朝你定义的「好」优化，而你定义的「好」可能不是真正的「好」。
→ 概念笔记「决策理论的三张面孔」：探索-利用困境是元决策——不是「选 A 还是 B」，而是「我是现在做最好的选择，还是为了以后能做更好的选择而牺牲现在」。这与决策理论中「不决策本身就是一种决策」（不做实验也是一种选择——选择保持当前的不确定性）一致。探索-利用的视界敏感性是时间折现在元决策中的体现：剩余时间越长，信息（从探索中获得的）价值越高。
→ 概念笔记「贝叶斯与频率学派的分歧不是方法偏好」：Thompson Sampling (Bayesian) 与 UCB (frequentist) 在探索策略上的分歧是贝叶斯-频率学派分歧在决策层的完美投射。贝叶斯路线通过全后验分布维护不确定性并将其注入决策（采样），频率学派路线通过点估计加置信界的方式捕获不确定性（UCB bonus）。Thompson Sampling 的概率匹配属性是贝叶斯框架的本质优势——后验分布自然地编码了「我应该以多大的概率选这个臂」，而频率学派必须人工构造 bonus 项来近似这个行为。
→ 概念笔记「网络科学——从个体交互到集体涌现的结构性规律」：当 Bandit 的动作间存在图结构约束时（最短路径、社交网络影响最大化），网络拓扑定义了探索的信息结构。图的加性分解结构是 Thompson 采样规避组合爆炸的关键——边级后验采样 + 图算法（Dijkstra）求解最优路径，将指数动作空间降维为多项式边数。
→ 概念笔记「实验设计与在线对照实验——从统计显著性到组织可信度」：Bandits 和 A/B 测试是同一光谱的两极——前者通过动态分配最小化遗憾，后者通过固定样本最大化置信度。Crawl→Walk→Run→Fly 组织成熟度框架定义了从标准 A/B 测试过渡到自适应实验的路径，而 Bandit 在线评估和离线策略评估的统计陷阱（选择偏差、非平稳奖励）直接映射到实验设计的核心挑战（SRM、多重比较、p-hacking）。
→ 桥接笔记「贝叶斯决策理论——从概率信念到最优行动」：Thompson Sampling 是贝叶斯决策理论在序贯决策中的一次一步近似——每一步根据后验信念做当前的期望效用最大化（通过采样实现的隐式积分），但不显式规划未来的信息获取。贝叶斯最优实验设计（如 Gittins index）在每一步决策时会考虑「这次探索对未来决策信息增益的价值」，Thompson Sampling 是它的随机近似。
→ 桥接笔记「因果推断的每个诊断检验都是一次假设检验」：Bandits 在部署后的 offline policy evaluation（离线策略评估）面临与因果诊断检验相同的根本困难——你只能评估实际被选择的策略路径，无法看到反事实路径。IPW、doubly robust 估计器等因果工具在这里与 bandit 估计器合流。
→ 桥接笔记「信用分配问题是时序因果推断与强化学习的共同根」：Bandits 和 RL 共享信用分配的根本问题——「这次成功/失败应该归结于哪个动作？」。在 bandits 中，信用分配是直接的（奖励紧接动作），但在梯度 bandit 和上下文老虎机中，当多个动作交互或奖励延迟时，信用分配重新浮现。Bandits 是一步 RL——没有状态转移，信用分配退化为标量回归。
→ 桥接笔记「预测、因果、决策是三个不同的技术层」：Bandits 将预测和决策压缩到一个循环里——你不需要先建一个预测模型、再做因果分析、再做优化；bandits 直接将「选哪个动作」视为在线优化问题，用即时反馈迭代改进。这在结构上是三层模型的短路——高效但有代价：你放弃了独立验证因果效应和预测准确性的机会。

实践启示¶

A/B 测试和 bandits 是同一光谱上的两极。在纯 randomize-then-test 和纯 bandit 之间有丰富的中间形态——比如先固定烧一段「学习预算」做均匀分配，然后切换到 bandit 做自适应优化。关键问题是：你需要的是因果结论还是损失最小化？如果是前者（药物审批、政策效果评估），必须保留固定样本设计的统计纯净性；如果是后者（网站优化、广告投放、推荐系统），bandits 通过减少遗憾产生直接的商业价值。

Bandits 的三个实践陷阱：(1) 把点击当奖励可能优化错了东西——短期指标 vs 长期指标就是 bandit 的「度量选择」问题；(2) 时间趋势（季节性、用户疲劳、竞争对手反应）会与自适应分配产生混淆——bandit 无法区分「臂变好了」还是「环境变好了」，需要 A/A 测试或 holdout 做检验；(3) 所有 bandit 方法都在平稳性假设下最优，现实几乎从不平稳——需要常数步长 α 和定期重置后验来保持对漂移的敏感。

从策略的视角理解 bandits：Bandits 不只是一类算法——它是一种思维方式。每当你在做「我应该多试试这个还是专注于那个」的抉择时，你就在做一个 bandit 决策。把它视为一个 bandit 问题，你能更清晰地看到：(1) 探索的机会成本（遗憾）；(2) 信息的衰减速率（你需要持续探索多久才能学到足够的信息）；(3) 决策的视界依赖性（你的 horizon 是多长——决定了该多激进地探索）。

追加——从独立臂到结构化动作空间（2026-07-02 常青化）¶

第二轮追加将 Bandit 的视野从独立臂扩展到结构化动作空间（网络约束下的 Bandit）和对抗环境（博弈论视角），并补全了 Thompson 采样的贝叶斯推理深链：

Thompson 采样的贝叶斯推理链（Russo 教程三部曲）： - Russo 等三篇顶刊综述（2018-2022）建立了 Thompson 采样从原理到实践的完整路径：贝叶斯后验更新→按后验概率随机采样→采样即决策，一步完成探索与利用的平衡。与传统方法（ε-greedy 确定性地交替、UCB 用置信上限决定）不同，Thompson 采样的探索量自然取决于后验不确定性——不确定的臂被采样的概率更高，且随着数据积累自动收敛到纯利用。 - 核心数学：如果先验是 \(\text{Beta}(\alpha, \beta)\)（对每个臂的奖励概率），观测到 \(S\) 次成功和 \(F\) 次失败后，后验是 \(\text{Beta}(\alpha+S, \beta+F)\)。每轮从每个臂的后验中随机采样一个 \(\theta_i\)，选 \(\theta_i\) 最大的臂——这个简单的规则竟然能同时实现亚线性遗憾（\(\tilde{O}(\sqrt{T})\)）和渐进最优。

在线最短路径——从独立臂到组合 Bandit： - 在线最短路径问题（online shortest-path）是将 Bandit 扩展到结构化动作空间的桥——动作不再是独立的臂，而是图中的一条路径。每个边有一个随机的延迟分布（未知），agent 每轮选一条路径，观察到总延迟，然后需要推理每条边的延迟。这本质上是一个在指数级动作空间（路径数） 上进行 Thompson 采样的组合 Bandit 问题。 - 启示：网络结构约束下的 Bandit 比无结构 Bandit 实际上更容易——不是因为有更多的臂，而是因为结构切分了动作空间为共享的参数空间（边的延迟 vs 独立臂的奖励率），共享意味着观测一条路径就学到了关于多条边（因而很多条其他路径）的信息。在推荐系统中，物品-物品的相似性网络起着同样的作用——推荐一个物品学到的不只是该物品的奖励，还有与之相似物品的部分信息。

博弈论视角下的 Bandit——对抗环境： - Axelrod 囚徒困境锦标赛和 Mesa ABM 框架从博弈论侧提供了 Bandit 的另一关键方向：当臂的环境不是固定的自然反馈，而是其他也在学习和适应的 agent 时，传统的平稳性假设完全崩溃。这引出了对抗 Bandit（adversarial bandits）和策略学习（policy learning in multi-agent settings）的数学框架。 - 实践含义：在拍卖竞价、实时定价和竞争性推荐中，你的 bandit 决策不仅影响你的奖励——还通过改变对手的行为，改变整个环境的奖励分布。在这一刻，bandit 问题坍缩为策略演化问题——Thompson 采样从个体优化算法变成了博弈论中的策略（strategy），需要分析的已不仅是遗憾，还有均衡属性（纳什均衡、演化稳定策略）。

这些追加使自适应实验完成了闭环：独立臂（ε-greedy / UCB / Thompson）→ 结构化动作空间（在线最短路径 / 组合 Bandit）→ 对抗环境（博弈论 / 策略演化）。从独立的静态环境到网络约束的共享环境，再到多 agent 的竞争环境——Bandit 的数学框架逐层扩展，但核心直觉不变：在探索与利用之间，通过观测到的数据动态调整信念和行动。