所属模块：
M7 · 检索、排序与推荐系统 (Retrieval, Ranking & RecSys)| 专题分类：冷启动与长尾 (Cold Start & Long-Tail Distribution)| 难度等级：Hard
一、核心一句话结论 (One-Sentence Summary)
ε-greedy 简单但探索盲目；UCB 用’乐观上界’驱动探索（regret O(log T)）；Thompson 用后验采样，实践常最优。
Epsilon-greedy explores uniformly at random with linear regret, UCB explores deterministically via upper confidence bounds with O(log T) regret, and Thompson Sampling samples from Bayesian posteriors, providing the premier empirical performance in production.
二、核心考点要义 (Key Insights)
- 📌 ε-greedy：以 ε 概率随机（盲目探索）；regret 线性
- 📌 UCB：乐观上界（不确定性驱动）；regret O(log T)；需收益有界
- 📌 Thompson：从后验采样；实践常最优；需后验计算
English Insights:
– Epsilon-greedy simplicity vs. blind exploration: Easy to implement, but explores uniformly across all arms regardless of how poorly they have performed.
– Upper Confidence Bound (UCB): Deterministic optimism under uncertainty; prioritizes arms with either high empirical mean or high variance.
– Thompson Sampling (Bayesian): Probability matching; samples parameters from posterior distributions, offering superior empirical regret and natural handling of delayed feedback.
三、核心数学原理与机理推导 (Mathematical Principles & Derivation)
$$text{UCB}: hatmu_i+csqrt{frac{ln t}{n_i}};qquad text{TS}: theta_isimtext{posterior}, argmax_itheta_i$$
数学机理：三种经典 bandit 算法——(1) ε-greedy——以概率 ε 随机选择（探索）、以 1−ε 选’当前最优’（利用）；优点——极简（一行代码）；缺点——(a) 盲目探索（不区分’哪些更值得探索’——所有臂等概率）；(b) regret 线性（O(εT)——探索成本随时间线性增长）；(c) ε 需调（太大则浪费、太小则探索不足）；(d) 固定 ε 时探索永不停止。改进——ε 随时间衰减（ε_t ∝ 1/t）可使 regret 降到 O(log T)。(2) UCB（Upper Confidence Bound）——乐观原则：选’收益上界最高’的臂：UCB_i = μ̂_i + c·√(ln t / n_i)，其中 (a) μ̂_i——臂 i 的经验平均收益；(b) n_i——臂 i 被选择的次数；(c) √(ln t / n_i)——’不确定性项’（n_i 小则大、t 大则大）。直觉——(a) 尝试少的臂（n_i 小）→ 不确定性大 → 上界高 → 自动获得探索；(b) 随着 n_i 增大，上界收紧（’不确定性被消除’）；(c) 故探索会自然收敛。理论——UCB1 的 regret 是 O(log T)（对数级，远优于 ε-greedy 的线性）；代价——需’收益有界（[0,1]）’的假设（用于推导上界）。(3) Thompson Sampling（TS）——贝叶斯方法：对每个臂维护’收益分布的后验’（如 Beta 分布）；每步从后验采样 θ_i，选 θ_i 最大的臂；观察收益后更新后验。直觉——(a) ‘后验采样’自然实现了’按不确定性探索’（不确定的臂采样值波动大 → 有时最高 → 被选中）；(b) 这是’概率匹配（probability matching）’原则。优点——(a) 理论 regret 与 UCB 同阶（O(log T)）；(b) 实践中常优于 UCB（尤其’收益分布非平稳’或’先验信息可用’时）；(c) 实现相对简单（用共轭先验）；缺点——需后验计算（复杂模型时成本高）。三者的对比——(a) 简单性：ε-greedy > TS ≈ UCB；(b) 理论保证：UCB ≈ TS > ε-greedy；(c) 实践表现：TS ≥ UCB > ε-greedy（多数报告）；(d) 先验利用：TS 可（UCB 不可）；(e) 非平稳：TS 更易适应（UCB 需滑动窗口）。推荐系统的扩展——(a) 上下文 bandit（contextual bandit）——引入上下文 x（用户/场景），用模型预测’给定 x 下各臂收益’；这是推荐系统的标准形式（因为推荐天然是’个性化’的）；(b) LinUCB——线性模型 + UCB；(c) LinTS——线性模型 + TS；(d) 神经 bandit（用深度模型）；(e) 离线策略评估（OPE）——评估 bandit 策略（见离线评估题）。实践建议——(a) 小规模/简单场景 → ε-greedy（快速上手）；(b) 需要理论保证 → UCB；(c) 实践最优 → Thompson Sampling；(d) 推荐系统 → 上下文 bandit（LinUCB/LinTS）；(e) 非平稳 → TS + 滑动窗口；(f) 评估 → regret + 长期指标。度量——(a) regret（累积遗憾）；(b) 长期指标（留存/生态）；(c) 探索成本；(d) 收敛速度（多久找到最优臂）。
📖 查看英文严格数学推导 (English Mathematical Derivation)
Mathematical & Algorithmic Formulation: Multi-Armed Bandit Comparison.
(1) $epsilon$-Greedy Algorithm:
Let $hat{mu}_k = frac{S_k}{N_k}$ be the sample average reward of arm $k$. Policy:
$$a_t = begin{cases} argmax_k hat{mu}_k & text{with probability } 1 – epsilon \ text{Uniform Random}({1, dots, K}) & text{with probability } epsilon end{cases}$$
Theoretical Regret: Cumulative regret scales linearly: $R(T) = O(epsilon T Delta)$. If $epsilon$ decays as $epsilon_t = min(1, cK / d^2 t)$, regret achieves $O(ln T)$, but tuning decay parameters $c, d$ in production is brittle.
(2) Upper Confidence Bound (UCB1):
Applies Hoeffding’s Inequality to construct an upper confidence bound containing the true mean with probability $ge 1 – t^{-4}$:
$$text{UCB}_k(t) = hat{mu}_k + sqrt{frac{2 ln t}{N_k(t)}}$$$$a_t = argmax_k left( hat{mu}_k + c cdot sqrt{frac{2 ln t}{N_k(t)}} right)$$
– Theoretical Regret: Strictly bounded logarithmically: $R(T) le 8 sum_{k : Delta_k > 0} frac{ln T}{Delta_k} + O(1) = O(ln T)$.
– Limitation: Assumes bounded rewards ($r in [0, 1]$), deterministic policy (cannot sample diverse slates), and requires tuning hyperparameter $c$.
(3) Thompson Sampling (Posterior Sampling):
For binary click rewards ($r in {0, 1}$), assumes conjugate prior $theta_k sim text{Beta}(alpha_k, beta_k)$ initialized to $text{Beta}(1, 1)$:
– At each round $t$, sample realization $tilde{theta}_k sim text{Beta}(alpha_k, beta_k)$ for all $k in [1, K]$.
– Select arm with highest sampled probability: $a_t = argmax_k tilde{theta}_k$.
– Observe reward $r_t in {0, 1}$, update posterior parameters:
$$alpha_{a_t} leftarrow alpha_{a_t} + r_t, quad beta_{a_t} leftarrow beta_{a_t} + (1 – r_t)$$
– Theoretical Regret: Matches the asymptotic lower bound of Lai & Robbins: $R(T) le (1 + epsilon) sum_{k} frac{ln T}{D_{text{KL}}(mu_k parallel mu^*)} = O(ln T)$.
四、工业级落地权衡与工程考量 (Industrial Trade-offs)
深度剖析与工程权衡：① ‘UCB 的不确定性驱动探索’是优雅的核心——n_i 小则上界高 → 自动探索；面试中能解释这一点是深度理解的标志。② ‘Thompson 实践常优于 UCB’——虽然理论同阶；这是’理论 vs 实践’的经典案例。③ ‘上下文 bandit 是推荐的标准形式’——因为推荐天然个性化；故 LinUCB/LinTS 更实用。④ ‘ε-greedy 的 regret 是线性’——故不推荐用于长期系统（除非 ε 衰减）。⑤ ‘非平稳需滑动窗口’——用户兴趣/物品质量会变；故需’遗忘’旧数据。⑥ 面试要点——被问’bandit 算法怎么选’，应给出’ε-greedy（简单、线性 regret）/ UCB（乐观上界、log regret）/ Thompson（后验采样、实践最优）+ 上下文 bandit（推荐标准）‘；能解释’UCB 为何自动探索’是深度理解的标志。
⚙️ 查看英文落地权衡分析 (English Systems & Trade-offs)
In-Depth Analysis & Engineering Trade-offs: ① Why Thompson Sampling beats UCB in production—UCB is deterministic and conservative, frequently over-exploring mediocre arms until their confidence intervals shrink; Thompson Sampling naturally explores proportional to the probability that an arm is truly optimal; across empirical benchmarks, Thompson Sampling achieves 30–50% lower cumulative regret. ② Handling delayed feedback—in real-world e-commerce, user conversion $r_t$ arrives 2 hours after impression; UCB stalls or over-samples because $N_k$ increments while $hat{mu}_k$ remains zero; Thompson Sampling easily accommodates batch posterior updates via asynchronous queuing. ③ Batch serving & slate recommendation—recommending a slate of 10 items at once: Thompson Sampling naturally generates a diverse slate by simply drawing 10 independent samples from the joint posteriors; UCB produces identical items unless forced through artificial penalization. ④ Non-stationary environments (Drifting preferences)—user tastes drift over time; classic bandits assume static arm reward distributions; production systems employ Discounted Thompson Sampling or Sliding-Window Bandits: $alpha_k leftarrow gamma alpha_k + r_t, , beta_k leftarrow gamma beta_k + (1-r_t)$ with discount factor $gamma in [0.95, 0.999]$. ⑤ Contextual expansion (LinUCB vs. LinTS)—when contextual features $x$ (user demographics) are present, bandits must condition on $x$; LinUCB and Linear Thompson Sampling scale to contextual personalization via Bayesian linear regression. ⑥ Interview takeaway—compare the three algorithms across exploration style (random vs. deterministic bound vs. Bayesian sampling), regret bounds (linear vs. $O(log T)$), detail Thompson Sampling’s Beta-Binomial update loop, and explain why Thompson Sampling dominates production slate recommendation.
五、常见面试避坑陷阱 (Common Pitfalls & Traps)
- ⚠️ 用固定 ε 的 ε-greedy（探索永不停止）
- ⚠️ 用 UCB 但收益无界（理论假设不满足）
English Pitfalls:
– Using standard UCB in delayed-feedback conversion settings, causing severe over-exploration of un-converted items before conversion attribution completes.
– Using static epsilon-greedy without decaying epsilon, accumulating continuous linear regret and degrading long-term platform revenue.
– Failing to incorporate a decay factor (gamma) in non-stationary production environments, allowing stale historical counts to prevent adaptation to new trends.
六、高频深度面试追问与预测 (Follow-Up Questions)
- 为什么 UCB 的 regret 是对数级？
- Why does Thompson Sampling naturally support slate recommendation (generating top-k distinct items) while UCB requires ad-hoc penalties?
- 三者如何选？
- How does Discounted Thompson Sampling adapt to non-stationary click distributions where item popularity decays over time?
七、知识图谱对齐 (Knowledge Graph Anchor)
- 🔗 关联底层卡片：
推荐系统冷启动策略：Multi-Armed Bandits (MAB)、汤普森采样与内容元数据(Cold Start & Long-Tail: Bandits, Thompson Sampling & Meta Features) - 🗺️ 知识图谱模块：
工业级系统设计导图
🔬 算法科学家与机器学习深度考察全量题库 (Science Depth)
本题收录于 TalentMe 算法科学家深度考察真题库 (Science Depth)。全库共 856 道硬核考点，深度覆盖数学统计、经典ML、深度学习、Transformer、大语言模型、多模态、推荐系统与 MLOps。支持 Jev 面经智能匹配、一键离线单文件 HTML 手册导出并直连 Obsidian 本地记忆。