第 1–2 章 · 试错学习与多臂老虎机

强化学习的本质是试错 + 延迟奖励：没有标准答案（监督信号），只有环境给的评分。第一章用 k 臂老虎机这个最小问题把"探索 vs 利用"的根本权衡讲透——它是 RL 一切方法的心跳。

k 臂老虎机与探索-利用困境

每台老虎机有未知奖励分布，选一台拉一次得一份奖励。目标是最大化总奖励。贪婪法（永远选当前平均最高的）会锁死在早期幸运的选择上；$\varepsilon$-贪婪以概率 $\varepsilon$ 随机探索。核心账本：遗憾（regret）= 最优臂期望奖励 × 次数 − 实得。理论答案：UCB（置信上界）动作选择

不确定性大（拉得少）就加探索分——对数级遗憾的最优标度。贝叶斯版（Thompson 采样：按后验抽样动作）是工程常用替代。

动作价值的估计

增量式更新（免去存全部历史）：

通式 $Q \leftarrow Q + \alpha[R - Q]$（步长 $\alpha$）——"目标 − 现值"的误差驱动更新是全书（乃至 TD 学习）的原型句式。非平稳问题用常数 $\alpha$（指数遗忘最近样本）；乐观初始化（初值设得高于可能值）逼系统先探索后收敛。

RL 与其他学习范式的关系

监督学习有标签、无监督找结构、RL 学行为：奖励延迟（当前动作的好坏要到很多步后才显现）、数据由自己的行为生成（策略影响数据分布）、目标是在线表现（探索的成本真金白银）。这三点差异决定了 RL 不能照搬监督学习的工具箱。

老师的提醒

• 探索-利用权衡的直觉版：吃饭选老店（利用）还是新店（探索）——UCB 的做法是"没去过的店加好奇心分"。
• 增量更新公式是全书的"一句真言"：$Q \leftarrow Q + \alpha(\text{目标} - Q)$——往后每一章都在改"目标"是什么。

自检

• $\varepsilon$-贪婪与 UCB 的动作选择公式及动机？
• 增量更新的推导（从均值定义出发）。
• 为什么非平稳问题要用常数步长？

更深一层：探索-利用权衡是"序贯决策的元问题"

k 臂老虎机是"探索 vs 利用"的最小标本，但这个权衡是一切序贯决策的元问题——临床试验（试新药 vs 用现有药）、推荐系统（推已知偏好 vs 试探新兴趣）、自适应实验（A/B 测试的在线分配）。三条解决路线的性格：ε-贪婪（简单粗暴，$\varepsilon$ 比例随机探索——够用但浪费）；UCB（置信上界——"不确定性大就加分"，对数级遗憾的理论最优标度）；Thompson 采样（按后验抽样——贝叶斯优雅，工程常用）。探索策略的选择 = 对"不确定性"的定价方式——UCB 给它定 bonus，Thompson 给它定后验，ε-贪婪给它定固定概率。

增量式更新 $Q \leftarrow Q + \alpha(R - Q)$ 是全书的"一句真言"——往后每一章都在改"目标"是什么。误差驱动更新（目标减现值的差）是 RL 与神经网络的共同语法。

推导细读：UCB 的"不确定性 bonus"推导

UCB 公式 $Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}}$ 的两部分值得分别读出：$Q_t(a)$ 是当前估计（利用）、$c\sqrt{\ln t / N_t(a)}$ 是不确定性 bonus（拉动次数越少 bonus 越大，随时间对数增长）。这个 bonus 的推导来自 Hoeffding 不等式（次高斯变量的置信区间）——不确定性量化在这里变成了探索的定价公式。对数级遗憾（最优标度）的证明线路： bonus 恰好让"探索错误的代价"按对数增长——UCB 是"乐观的理性"（optimism in the face of uncertainty 的字面实现）。

在真实世界里：多臂老虎机的"产业分身"

老虎机算法的产业分身：在线广告（广告投放 = 多臂老虎机，UCB/Thompson 是点击率预估的探索策略）、临床自适应试验（Thompson 采样的患者分配——减少受试者暴露于劣疗法）、超参数调优（贝叶斯优化的采集函数 = 老虎机的探索策略推广）、内容推荐（探索新内容 vs 推荐已知偏好——用户疲劳与新颖性的平衡）。"试错 + 延迟反馈"的决策框架是互联网时代最赚钱的算法思想之一。

专题深入：探索-利用困境的"完整谱系"完整版

Sutton 第一章-第二章的核心资产是探索-利用困境的算法谱系：ε-greedy（最简但次优——探索比例恒定导致悔恨对数发散系数偏大）；乐观初始化（给所有动作价值乐观初值——每个动作先被"骗"一次才被放弃，探索由高估驱动）；UCB1（$\arg\max\left[Q(a) + c\sqrt{\frac{\ln t}{N(a)}}\right]$——"不确定性加成"：被试得少的动作置信区间宽，上界更大；悔恨界 $O(\ln T)$ 最优）；Thompson 采样（从后验采样参数、选最优动作、按观测更新——贝叶斯 A/B 的天然最优分配，工业流量分发的默认算法）。梯度老虎机算法（偏好向量的 softmax 策略 + 随机梯度上升——策略梯度思想的前哨）。十臂老虎机的实验方法论（2000 步 × 2000 次独立实验取平均——"平均学习曲线"是 RL 论文的标准图：单次轨迹噪声大到无法读结论）。非平稳环境（指数加权平均 $Q \leftarrow Q + \alpha(R - Q)$ 固定 α 追踪漂移——"平稳用 1/N、非平稳用常数 α"是估计器的分水岭）。

推导细读：试错学习的"要素表"完整版

第一章的要素表值得逐项工程化：策略 π（状态到动作的映射或分布——行为主体）；奖励信号（标量反馈、目标定义——"奖励设计是 RL 的功耗预算表"：稀疏奖励难学、密集奖励易出"奖励黑客"）；价值函数（长期回报的预期——"价值 = 未来的折扣奖励总和"是 RL 的核心记账单位）；环境模型（可选：预测下一状态与奖励——有无模型划分算法谱系）。回报 $G_t = \sum_k \gamma^k R_{t+k+1}$ 的折扣因子双重身份（数学上保证无穷和收敛 + 认知上编码"未来的折现率"——γ → 0 短视、γ → 1 远见但方差大）；episodic vs continuing 任务（有终局 vs 无终局——信用分配的时间结构不同）。"状态的设计"是被低估的工程（马尔可夫性靠状态表示担保：部分可观测（POMDP）时需要历史/循环网络补状态——环境建模的失真最先在状态表示上翻车）。

工程案例细节：老虎机思想的产业出口工程版

一-二章的工程出口：在线流量分配（Thompson/UCB 的 A/B 自动化——新版灰度、推荐排序实验、广告创意轮换的通用引擎；比固定 50/50 早获全量收益）；推荐系统的探索位（ε-greedy 的新内容曝光配额——冷启动 item 的探索预算管理）；动态定价与库存（老虎机 + 上下文（contextual bandit）——价格实验的悔恨最小化：每个价格试探都是真金白银）；神经架构与超参搜索（bandit 式早停（Hyperband/ASHA）——"资源按前景分配"的老虎机思想）；点击模型的 contextual bandit（特征上下文 + 线性 UCB（LinUCB）——新闻推荐的经典系统（Yahoo 的论文是教科书案例））。"多臂老虎机 = 贵实验的分配学"——凡是实验本身有成本的领域，它都是默认框架。