M7-073M7: 检索、排序与推荐系统冷启动与长尾Hard
⚡闪卡盲测➔掌握度:

解释 Bandit 算法(ε-greedy / UCB / Thompson Sampling)的取舍

🎯 深度面试自测闭环(先口述或草拟,再核对解析)
免登录记录进度:核心结论回忆 → 避坑清单自查 → 标记掌握或加入错题队列。
Step 1 · 尝试用 1–2 句话回答这道题的核心结论与适用边界
Step 2 · 勾选已覆盖的陷阱与追问思考
下一题: M7-074 →
📐 核心数学机理公式
UCB: μ^i+cln⁡tni;TS: θi∼posterior, arg⁡max⁡iθi\text{UCB}:\ \hat\mu_i+c\sqrt{\frac{\ln t}{n_i}};\qquad \text{TS}:\ \theta_i\sim\text{posterior},\ \arg\max_i\theta_i
⚡ 一句话直击要害答案
ε-greedy 简单但探索盲目;UCB 用'乐观上界'驱动探索(regret O(log T));Thompson 用后验采样,实践常最优。

📌 核心要点提炼

  • •
    ε-greedy:以 ε 概率随机(盲目探索);regret 线性
  • •
    UCB:乐观上界(不确定性驱动);regret O(log T);需收益有界
  • •
    Thompson:从后验采样;实践常最优;需后验计算

📐 数学机理与严密推导

数学机理:三种经典 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) 收敛速度(多久找到最优臂)。

🏭 深度剖析与工业落地权衡

深度剖析与工程权衡:① 'UCB 的不确定性驱动探索'是优雅的核心——n_i 小则上界高 → 自动探索;面试中能解释这一点是深度理解的标志。② 'Thompson 实践常优于 UCB'——虽然理论同阶;这是'理论 vs 实践'的经典案例。③ '上下文 bandit 是推荐的标准形式'——因为推荐天然个性化;故 LinUCB/LinTS 更实用。④ 'ε-greedy 的 regret 是线性'——故不推荐用于长期系统(除非 ε 衰减)。⑤ '非平稳需滑动窗口'——用户兴趣/物品质量会变;故需'遗忘'旧数据。⑥ 面试要点——被问'bandit 算法怎么选',应给出'ε-greedy(简单、线性 regret)/ UCB(乐观上界、log regret)/ Thompson(后验采样、实践最优)+ 上下文 bandit(推荐标准)';能解释'UCB 为何自动探索'是深度理解的标志。
⚠️ 常见面试陷阱与高频失分点
  • ✕
    用固定 ε 的 ε-greedy(探索永不停止)
  • ✕
    用 UCB 但收益无界(理论假设不满足)
🎯 面试官连环追问与延伸考察
  • ?
    为什么 UCB 的 regret 是对数级?
  • ?
    三者如何选?
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!
🎯 立即在闪卡中盲测此题➔
📚

关联知识库专题与交互式导图

← 上一题M7-072: 解释冷启动的'内容/侧信息'方法📋 返回题库下一题 →M7-074: 解释长尾内容的'重排与多样性'策略