Cold Start & Long-Tail Distribution: 解释 Bandit 算法（ε-greedy / UCB / Thompson Sampling）的取舍。

Core Concept: ε-greedy 简单但探索盲目；UCB 用'乐观上界'驱动探索（regret O(log T)）；Thompson 用后验采样，实践常最优。

数学机理：<strong>三种经典 bandit 算法</strong>——(1) <strong>ε-greedy</strong>——以概率 ε <strong>随机</strong>选择（探索）、以 1−ε 选'当前最优'（利用）；<strong>优点</strong>——极简（一行代码）；<strong>缺点</strong>——(a) <strong>盲目探索</strong>（不区分'哪些更值得探索'——所有臂等概率）；(b) <strong>regret 线性</strong>（O(εT)——探索成本随时间线性增长）；(c) ε 需调（太大则浪费、太小则探索不足）；(d) 固定 ε 时探索永不停止。<strong>改进</strong>——ε 随时间衰减（ε_t ∝ 1/t）可使 regret 降到 O(log T)。(2) <strong>UCB（Upper Confidence Bound）</strong>——<strong>乐观原则</strong>：选'收益上界最高'的臂：UCB_i = μ̂_i + c·√(ln t / n_i)，其中 (a) <strong>μ̂_i</strong>——臂 i 的经验平均收益；(b) <strong>n_i</strong>——臂 i 被选择的次数；(c) <strong>√(ln t / n_i)</strong>——'不确定性项'（n_i 小则大、t 大则大）。<strong>直觉</strong>——(a) 尝试少的臂（n_i 小）→ 不确定性大 → 上界高 → <strong>自动获得探索</strong>；(b) 随着 n_i 增大，上界收紧（'不确定性被消除'）；(c) 故探索会<strong>自然收敛</strong>。<strong>理论</strong>——UCB1 的 regret 是 <strong>O(log T)</strong>（对数级，远优于 ε-greedy 的线性）；<strong>代价</strong>——需'收益有界（[0,1]）'的假设（用于推导上界）。(3) <strong>Thompson Sampling（TS）</strong>——<strong>贝叶斯方法</strong>：对每个臂维护'收益分布的后验'（如 Beta 分布）；每步<strong>从后验采样</strong> θ_i，选 θ_i 最大的臂；观察收益后<strong>更新后验</strong>。<strong>直觉</strong>——(a) '后验采样'自然实现了'按不确定性探索'（不确定的臂采样值波动大 → 有时最高 → 被选中）；(b) 这是'概率匹配（probability matching）'原则。<strong>优点</strong>——(a) 理论 regret 与 UCB 同阶（O(log T)）；(b) <strong>实践中常优于 UCB</strong>（尤其'收益分布非平稳'或'先验信息可用'时）；(c) 实现相对简单（用共轭先验）；<strong>缺点</strong>——需后验计算（复杂模型时成本高）。<strong>三者的对比</strong>——(a) <strong>简单性</strong>：ε-greedy > TS ≈ UCB；(b) <strong>理论保证</strong>：UCB ≈ TS > ε-greedy；(c) <strong>实践表现</strong>：TS ≥ UCB > ε-greedy（多数报告）；(d) <strong>先验利用</strong>：TS 可（UCB 不可）；(e) <strong>非平稳</strong>：TS 更易适应（UCB 需滑动窗口）。<strong>推荐系统的扩展</strong>——(a) <strong>上下文 bandit（contextual bandit）</strong>——引入上下文 x（用户/场景），用模型预测'给定 x 下各臂收益'；<strong>这是推荐系统的标准形式</strong>（因为推荐天然是'个性化'的）；(b) <strong>LinUCB</strong>——线性模型 + UCB；(c) <strong>LinTS</strong>——线性模型 + TS；(d) <strong>神经 bandit</strong>（用深度模型）；(e) <strong>离线策略评估（OPE）</strong>——评估 bandit 策略（见离线评估题）。<strong>实践建议</strong>——(a) <strong>小规模/简单场景</strong> → ε-greedy（快速上手）；(b) <strong>需要理论保证</strong> → UCB；(c) <strong>实践最优</strong> → Thompson Sampling；(d) <strong>推荐系统</strong> → 上下文 bandit（LinUCB/LinTS）；(e) <strong>非平稳</strong> → TS + 滑动窗口；(f) <strong>评估</strong> → regret + 长期指标。<strong>度量</strong>——(a) <strong>regret</strong>（累积遗憾）；(b) 长期指标（留存/生态）；(c) 探索成本；(d) 收敛速度（多久找到最优臂）。

深度剖析与工程权衡：① <strong>'UCB 的不确定性驱动探索'是优雅的核心</strong>——n_i 小则上界高 → 自动探索；面试中能解释这一点是深度理解的标志。② <strong>'Thompson 实践常优于 UCB'</strong>——虽然理论同阶；这是'理论 vs 实践'的经典案例。③ <strong>'上下文 bandit 是推荐的标准形式'</strong>——因为推荐天然个性化；故 LinUCB/LinTS 更实用。④ <strong>'ε-greedy 的 regret 是线性'</strong>——故不推荐用于长期系统（除非 ε 衰减）。⑤ <strong>'非平稳需滑动窗口'</strong>——用户兴趣/物品质量会变；故需'遗忘'旧数据。⑥ <strong>面试要点</strong>——被问'bandit 算法怎么选'，应给出'<strong>ε-greedy（简单、线性 regret）/ UCB（乐观上界、log regret）/ Thompson（后验采样、实践最优）+ 上下文 bandit（推荐标准）</strong>'；能解释'UCB 为何自动探索'是深度理解的标志。