1. 从静态拟合到动态博弈：监督学习与在线学习的范式演进

在机器学习的工具箱里，监督学习无疑是最基础、最直观的范式。它的逻辑简单而强大：给你一堆“问题”和对应的“标准答案”，你从中学习规律，目标是当遇到新的“问题”时，能给出靠谱的“答案”。这就像我们小时候学认字，老师指着“苹果”的图片和文字，反复教我们，直到我们能把“苹果”这个词和那个红彤彤的水果对应起来。线性回归，作为监督学习的“元老级”成员，就是这种思想的典型代表。它试图用一条直线（或者在高维空间里是一个超平面）去拟合数据点，找到输入特征和输出目标之间最直接的线性关系。无论是预测房价、估算销售额，还是分析实验数据，线性回归都因其模型简单、解释性强而备受青睐。

然而，现实世界远比我们精心准备的训练集要复杂和善变。传统的批量学习，就像是一次性的期末考试：你集中复习（训练）所有知识点，然后参加考试（部署），考完就结束了，成绩不会因为考试中遇到的新题型而改变。它隐含了一个关键假设：未来的数据（考试题）和过去的数据（复习资料）来自同一个“题库”（分布）。一旦这个假设不成立，比如考试大纲突然改了，或者出题老师换人了，你那套基于旧题库的复习策略就可能失灵。更棘手的是，在很多场景下，你的“行动”本身就会改变“环境”。比如，一个推荐算法如果总是给用户推同类视频，用户可能会感到厌倦甚至卸载应用；一个交易算法如果暴露出某种固定的模式，就可能被市场上的其他参与者利用并导致亏损。这时，数据不再是静止、独立的，而是动态、交互甚至是对抗的。

这就引出了在线学习。它不再是一次性的“训练-部署”，而是一个持续的“感知-决策-学习”循环。想象一下玩一个你完全不了解的街机游戏：你投币（开始），面对几个按钮（行动），按下一个，屏幕给出分数（反馈），然后你根据这个分数决定下一局按哪个按钮。你没有游戏说明书（训练集），只能通过不断试错来学习哪个按钮可能带来更高分。这个过程就包含了在线学习的核心要素： 不完全反馈 （你只知道所选按钮的得分，不知道其他按钮的得分）、 探索与利用的权衡 （是继续按已知的高分按钮，还是试试别的按钮以防有更高分的？）、以及潜在的 环境对抗性 （如果游戏机偷偷调整了按钮的得分规则呢？）。从垃圾邮件过滤到在线广告竞价，从机器人控制到金融交易，在线学习为我们处理动态、交互甚至对抗的环境提供了一套强大的理论框架和算法工具。

本文将深入剖析这两个关键范式。我们将首先拆解线性回归，特别是最小二乘法的数学内核，理解它如何从几何和代数两个视角优雅地找到那条“最佳拟合线”。然后，我们将转向在线学习，探讨其基本模型、核心挑战（尤其是探索与利用的两难困境），并对比其在随机环境和对抗环境下的不同策略。我的目标是，不仅让你知道这些方法“是什么”和“怎么用”，更让你理解其背后的“为什么”，以及在实际项目中如何根据场景做出合适的选择。

2. 线性回归的基石：最小二乘法的双重视角

线性回归的目标是寻找一个线性函数 $h(\mathbf{x}) = \mathbf{w}^T \mathbf{x}$，使得对于给定的训练样本集 $S = {(\mathbf{x}_1, y_1), ..., (\mathbf{x}_n, y_n)}$，预测值 $h(\mathbf{x}_i)$ 与真实值 $y_i$ 之间的差距最小。这里，$\mathbf{x}_i \in \mathbb{R}^d$ 是特征向量，$y_i \in \mathbb{R}$ 是实数值标签，$\mathbf{w} \in \mathbb{R}^d$ 是我们需要学习的权重向量。

最常用的差距度量是平方损失函数：$\ell(\hat{y}, y) = (\hat{y} - y)^2$。因此，我们的优化目标是最小化经验风险（即所有样本的损失之和）： $$ \hat{L}(\mathbf{w}, S) = \sum_{i=1}^{n} (\mathbf{w}^T \mathbf{x}_i - y_i)^2 $$

为了更紧凑地表示，我们引入设计矩阵 $\mathbf{X} \in \mathbb{R}^{n \times d}$，其第 $i$ 行是样本 $\mathbf{x}_i^T$，以及标签向量 $\mathbf{y} = (y_1, ..., y_n)^T$。这样，经验风险可以写成矩阵形式： $$ \hat{L}(\mathbf{w}, S) = |\mathbf{X}\mathbf{w} - \mathbf{y}|^2 $$ 这里 $|\cdot|$ 表示向量的 $L_2$ 范数（即欧几里得长度）。最小化 $|\mathbf{X}\mathbf{w} - \mathbf{y}|^2$ 就是寻找一个向量 $\mathbf{X}\mathbf{w}$（位于 $\mathbf{X}$ 的列空间内），使其与目标向量 $\mathbf{y}$ 的距离最短。

2.1 解析视角：通过求导寻找驻点

从解析的角度看，这是一个无约束的凸优化问题。我们将目标函数展开： $$ f(\mathbf{w}) = |\mathbf{X}\mathbf{w} - \mathbf{y}|^2 = (\mathbf{X}\mathbf{w} - \mathbf{y})^T (\mathbf{X}\mathbf{w} - \mathbf{y}) = \mathbf{w}^T\mathbf{X}^T\mathbf{X}\mathbf{w} - 2\mathbf{y}^T\mathbf{X}\mathbf{w} + \mathbf{y}^T\mathbf{y} $$ 为了找到最小值点，我们计算梯度并令其为零向量： $$ \nabla_{\mathbf{w}} f(\mathbf{w}) = 2\mathbf{X}^T\mathbf{X}\mathbf{w} - 2\mathbf{X}^T\mathbf{y} = 0 $$ 整理后得到著名的 正规方程 ： $$ \mathbf{X}^T\mathbf{X}\mathbf{w} = \mathbf{X}^T\mathbf{y} $$ 如果矩阵 $\mathbf{X}^T\mathbf{X}$ 是可逆的（这要求 $\mathbf{X}$ 的列是线性独立的，即特征之间没有完全的线性相关性，且样本数 $n$ 不小于特征数 $d$），那么我们可以得到唯一解： $$ \mathbf{w} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} $$ 这个解被称为最小二乘估计。矩阵 $(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T$ 有一个专门的名字——$\mathbf{X}$ 的 Moore-Penrose 伪逆 ，当 $\mathbf{X}$ 列满秩时，它给出了线性方程 $\mathbf{X}\mathbf{w} = \mathbf{y}$ 在最小二乘意义下的最佳近似解。

注意：数值稳定性问题 在实际计算中，直接对 $\mathbf{X}^T\mathbf{X}$ 求逆可能会遇到数值不稳定的问题，尤其是当 $\mathbf{X}$ 的列近似线性相关（即存在多重共线性）时，$\mathbf{X}^T\mathbf{X}$ 的条件数会变得很大，求逆会放大误差。更稳健的方法是使用 QR 分解 或 奇异值分解 。例如，对 $\mathbf{X}$ 进行 QR 分解（$\mathbf{X} = \mathbf{Q}\mathbf{R}$，其中 $\mathbf{Q}$ 是正交矩阵，$\mathbf{R}$ 是上三角矩阵），则正规方程变为 $\mathbf{R}^T\mathbf{Q}^T\mathbf{Q}\mathbf{R}\mathbf{w} = \mathbf{R}^T\mathbf{Q}^T\mathbf{y}$，简化后为 $\mathbf{R}\mathbf{w} = \mathbf{Q}^T\mathbf{y}$。由于 $\mathbf{R}$ 是上三角矩阵，可以通过回代法高效稳定地求解 $\mathbf{w}$。大多数科学计算库（如 NumPy 的 numpy.linalg.lstsq ）内部都采用这类数值稳定的方法。

2.2 几何视角：在列空间中的正交投影

代数视角为我们提供了另一种更直观的理解。方程 $\mathbf{X}\mathbf{w} = \mathbf{y}$ 在 $\mathbf{y}$ 不在 $\mathbf{X}$ 的列空间内时无解。我们的目标是找到列空间中的一个点 $\mathbf{X}\mathbf{w}$，使其尽可能接近 $\mathbf{y}$。在欧几里得空间中，一个点到一个子空间的最短距离，是通过该点向该子空间做 正交投影 得到的。

设 $\mathbf{y}^ $ 是 $\mathbf{y}$ 在 $\mathbf{X}$ 列空间上的投影。根据投影的定义，残差向量 $\mathbf{y} - \mathbf{y}^ $ 必须与列空间中的任何向量都正交。特别地，它必须与 $\mathbf{X}$ 的每一列正交。用矩阵表示，即： $$ \mathbf{X}^T (\mathbf{y} - \mathbf{y}^ ) = 0 $$ 由于 $\mathbf{y}^ $ 在列空间中，它可以表示为 $\mathbf{y}^* = \mathbf{X}\mathbf{w}$。代入上式得： $$ \mathbf{X}^T (\mathbf{y} - \mathbf{X}\mathbf{w}) = 0 \quad \Rightarrow \quad \mathbf{X}^T\mathbf{X}\mathbf{w} = \mathbf{X}^T\mathbf{y} $$ 这与我们通过求导得到的正规方程完全一致。因此，最小二乘解 $\mathbf{X}\mathbf{w}$ 恰好是 $\mathbf{y}$ 在 $\mathbf{X}$ 列空间上的正交投影。投影矩阵 $\mathbf{P} = \mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T$ 作用在 $\mathbf{y}$ 上即可得到投影：$\mathbf{y}^* = \mathbf{P}\mathbf{y}$。

这个几何解释非常有力。它告诉我们，线性回归本质上是在寻找一个“影子”，这个影子（$\mathbf{X}\mathbf{w}$）位于特征张成的“平面”（列空间）上，并且是真实目标 $\mathbf{y}$ 在这个平面上垂直落下的“影子”，因此距离最短。

2.3 从线性到非线性：特征映射的威力

线性回归的“线性”指的是相对于参数 $\mathbf{w}$ 是线性的，而不是相对于原始输入 $\mathbf{x}$。这是一个非常重要的扩展点。通过 特征映射 $\phi: \mathbb{R}^d \rightarrow \mathbb{R}^D$，我们可以将原始特征空间映射到一个更高维（甚至无限维）的空间，从而用线性模型来拟合非线性关系。

最经典的例子是多项式回归。假设我们想用 $d$ 次多项式拟合数据点 $(x_i, y_i)$，模型为 $y = a_d x^d + a_{d-1} x^{d-1} + ... + a_1 x + a_0$。我们可以定义特征映射 $\phi(x) = (x^d, x^{d-1}, ..., x, 1)^T$。这样，原始的一维特征 $x$ 被映射成了 $D=d+1$ 维的特征向量。然后，我们在这个新的特征空间上应用标准的线性回归，求解权重向量 $\mathbf{w} = (a_d, a_{d-1}, ..., a_1, a_0)^T$。

设计矩阵 $\mathbf{X}$ 变成了： $$ \mathbf{X} = \begin{pmatrix} x_1^d & x_1^{d-1} & \cdots & x_1 & 1 \ x_2^d & x_2^{d-1} & \cdots & x_2 & 1 \ \vdots & \vdots & \ddots & \vdots & \vdots \ x_n^d & x_n^{d-1} & \cdots & x_n & 1 \end{pmatrix} $$ 之后求解正规方程 $\mathbf{X}^T\mathbf{X}\mathbf{w} = \mathbf{X}^T\mathbf{y}$ 即可得到多项式系数。这种方法将非线性拟合问题巧妙地转化为了线性问题，展现了线性回归框架的灵活性。

实操心得：警惕过拟合与特征工程 虽然特征映射能力强大，但直接使用高阶多项式极易导致 过拟合 。模型会完美拟合训练数据中的噪声，而在未见数据上表现糟糕。解决之道包括：

1. 正则化 ：在损失函数中加入对权重大小的惩罚项，如岭回归（$L_2$ 正则化）：$\min_{\mathbf{w}} |\mathbf{X}\mathbf{w} - \mathbf{y}|^2 + \lambda |\mathbf{w}|^2$，或 LASSO（$L_1$ 正则化），后者还能产生稀疏解。
2. 交叉验证 ：使用交叉验证来选择合适的模型复杂度（例如多项式的阶数 $d$）。
3. 更智能的特征工程 ：与其盲目提高多项式阶数，不如基于领域知识构造更有意义的特征。例如，在预测房价时，使用“房间数/总面积”可能比单独使用“房间数”和“总面积”更有效。

3. 批量学习的局限与在线学习的兴起

尽管线性回归等批量学习方法非常成功，但其基础假设在现实世界中常常被打破。理解这些局限，正是我们转向在线学习的动机。

3.1 独立同分布假设的脆弱性

批量学习理论的核心基石是 独立同分布 假设：训练数据和未来的测试数据是从同一个未知分布中独立采样得到的。一旦这个假设不成立，基于训练集得到的泛化误差界就失效了。

违反该假设主要有两种情形：

1. 训练数据非独立 ：例如，时间序列数据中相邻的样本通常是相关的。如果忽略这种相关性，基于独立假设推导出的误差收敛速率可能过于乐观，甚至不收敛。
2. 数据分布漂移 ：未来的数据分布与训练时不同。这在动态系统中非常常见。例如，用户的兴趣会随时间变化，经济环境会发生波动，网络攻击模式会不断演变。更微妙的是，算法自身的部署可能会引发 反馈循环 ，从而改变它所要预测的环境。比如，一个预测交通拥堵的算法如果被用于动态调整路线推荐，司机会根据推荐改变行为，从而改变实际的交通流模式，使得算法最初的预测模型失效。

3.2 过拟合：选择的力量与陷阱

过拟合是机器学习中的核心挑战。从理论上看，泛化误差的控制依赖于 集中性 和 选择性 的平衡。对于一个大小为 $n$ 的样本集和一个大小为 $M$ 的有限假设集 $\mathcal{H}$，我们有如下形式的泛化界： $$ P\left( \exists h \in \mathcal{H}: L(h) \ge \hat{L}(h, S) + \epsilon \right) \le \underbrace{M} {\text{选择}} \times \underbrace{e^{-2n\epsilon^2}} {\text{集中性}} $$ 集中性项 $e^{-2n\epsilon^2}$ 随着样本量 $n$ 增大而指数级减小，这很好。但选择项 $M$ 衡量了假设类的丰富度。如果 $M$ 非常大（例如，随着 $n$ 超指数增长），那么即使 $n$ 很大，泛化风险也可能失控，导致过拟合。

这里有两个关键点常被忽视：

• “大数据”并非过拟合的万能解药 ：如果模型复杂度（有效选择的数量）的增长速度超过数据量提供的验证能力，过拟合依然会发生。现代深度学习模型拥有数十亿参数，其有效假设空间极其庞大，即使数据量巨大，过拟合风险依然存在，这凸显了正则化、dropout 等技术的重要性。
• 内部选择与外部选择 ：
  • 内部选择 ：指算法内部对预测规则的筛选，例如线性分类中选择最优超平面。算法可以直接控制其搜索的假设集 $\mathcal{H}$，从而控制过拟合。
  • 外部选择 ：指在算法外部发生的选择。例如，多个研究团队在同一个公开数据集上测试不同的算法，并只发表效果最好的那个。这种情况下，同一份有限的数据被用来从远多于单个算法内部假设集的规则中进行选择，极易导致过拟合。许多流行的公开数据集实际上已被严重“过拟合”。控制外部选择过拟合的唯一方法，是将其转化为内部选择，即记录所有应用于该数据集的假设类的并集，并基于这个更大的集合计算泛化界。

3.3 在线学习：一个动态交互的框架

在线学习放弃了“一次性学习，永久部署”的批量模式，转而采用一个持续的交互循环（如图7.1所示）：在每一个时间步 $t$，算法根据已有信息从一组 动作 （或称为“臂”）中选择一个 $A_t$，然后接收到一个 损失 $\ell_t$（或奖励），并可能观察到一些 反馈 ，最后更新其策略。这个过程不断重复。

在线学习适用于以下典型场景：

1. 交互式学习 ：环境持续提供新信息，算法需要即时适应。例如，与用户的每次交互（点击、购买）都提供了新数据，用于优化下一次的推荐。
2. 对抗性或博弈论环境 ：我们不能假设未来会与过去相似。例如，垃圾邮件发送者会不断调整策略以绕过过滤器；下棋时对手的走法不是随机的，而是针对你的。
3. 智能数据收集 ：在资源有限或探索成本高��时（如药物临床试验、在线广告），我们需要在收集数据（探索）和利用当前最佳知识（利用）之间做出明智的权衡。

4. 在线学习的核心问题与分类

在线学习问题的复杂性可以从三个维度来刻画，构成了一个丰富的“问题空��”（如图7.2所示）。

4.1 反馈类型：从全信息到老虎机

反馈决定了算法在每一步能获得多少信息。

• 全信息反馈 ：算法在做出选择后，可以观察到所有可能动作的损失。例如，在股票投资中，每天结束后你不仅知道自己投资组合的涨跌，也能看到所有未选股票的涨跌。这提供了完整的信息来评估所有策略。
• 老虎机反馈 ：算法只观察到所选动作的损失，对其他动作的损失一无所知。这就像赌场的老虎机（单臂强盗），你拉下摇臂后，只知道这次的结果，不知道其他摇臂的结果。医疗试验是经典例子：对一名患者施用一种药物后，你只能观察到该药物的效果，而不知道如果用了另一种药会怎样。在线广告也类似：展示一条广告后，你只知道这条广告是否被点击。

老虎机反馈引入了在线学习标志性的 探索-利用困境 。为了估计其他动作的好坏，你必须去尝试它们（探索），但尝试可能带来次优的损失（成本）。如果探索不足，你可能永远找不到真正的最佳动作；如果探索过度，你会在次优动作上浪费太多资源。算法的目标是在探索（收集信息）和利用（根据当前信息选择最佳动作）之间取得最优平衡。

4.2 环境抵抗性：从随机到对抗

环境抵抗性描述了环境对算法行为的“对抗”程度。

• 随机（i.i.d.）环境 ：每个动作的损失是从一个固定的（但未知的）概率分布中独立采样的。例如，患者的药物反应、天气变化（虽然复杂，但并非针对算法）。环境本身不“针对”算法。
• 对抗性环境 ：损失序列可以是任意的，甚至由一个试图最大化算法损失的对手生成。例如，垃圾邮件过滤中的垃圾邮件发送者、股票市场中的其他交易者（虽然不直接针对个人，但市场会因套利行为而消除任何可预测的规律）。在这种环境下，算法需要具备鲁棒性。

4.3 结构复杂性：从无状态到序列决策

结构复杂性描述了问题的状态依赖关系。

• 无状态问题 ：每一步的决策只依赖于历史损失序列，没有额外的“状态”信息。经典的多臂老虎机就是无状态的。
• 上下文老虎机 ：在每一步，算法会收到一个 上下文 （或状态）信息，然后基于此选择动作。例如，在医疗诊断中，上下文是患者的病历；在广告推荐中，上下文是用户的画像。动作的效果可能依赖于上下文。
• 马尔可夫决策过程 ：这是强化学习的核心领域。与上下文老虎机的关键区别在于，算法当前的动作会影响下一个时刻的状态。例如，机器人的移动、棋类游戏、连续治疗患者。这引入了 规划 的问题：即使知道每个状态-动作对的即时结果，要找到长期最优的策略也可能需要复杂的计算。

在线学习主要关注 不确定性估计 （探索-利用），而强化学习则同时关注 不确定性估计 和 规划 。规划问题即使在结果完全确定的情况下（如解迷宫）也可能非常复杂。

5. 基础在线学习算法：应对不确定性

让我们聚焦于在线学习中最基础的几个问题（图7.4中的红色叉号）：无状态、全信息/老虎机反馈、随机/对抗环境。我们从一个通用设定开始。

5.1 通用设定与性能度量

考虑一个 $K \times \infty$ 的损失矩阵 $\ell_{t,a}$，其中 $t=1,2,...$ 表示轮次，$a=1,...,K$ 表示动作（或“臂”）。损失值在 $[0,1]$ 区间内。游戏协议如下：

1. 算法 选择动作 $A_t$。
2. 算法 遭受损失 $\ell_{t, A_t}$。
3. 算法 根据游戏类型观察到一定的反馈（全信息或仅所选动作的损失）。

游戏类型由 损失生成方式 和 反馈类型 共同定义：

• 损失生成 ：
  • 随机 ：$\ell_{t,a}$ 独立采样，$\mathbb{E}[\ell_{t,a}] = \mu(a)$。
  • 对抗 ：$\ell_{t,a}$ 由对手任意选择（在游戏开始前或自适应地）。
• 反馈类型 ：
  • 全信息 ：观察到本轮所有动作的损失 $\ell_{t,1}, ..., \ell_{t,K}$。
  • 老虎机 ：仅观察到所选动作的损失 $\ell_{t,A_t}$。

组合起来得到四个基本问题：

1. 随机全信息 ：简单，最优策略是始终选择平均损失最小的动作（需先通过探索估计平均值）。
2. 对抗全信息 ： 专家建议预测 问题。
3. 随机老虎机 ： 随机多臂老虎机 问题。
4. 对抗老虎机 ： 对抗多臂老虎机 问题。

算法的目标是最小化 遗憾 ，即算法累积损失与 hindsight 中最优固定动作的累积损失之差： $$ R_T = \sum_{t=1}^{T} \ell_{t, A_t} - \min_{a} \sum_{t=1}^{T} \ell_{t,a} $$ 在对抗性环境中，我们通常分析 期望遗憾 $\mathbb{E}[R_T]$。在随机环境中，我们常分析 伪遗憾 ： $$ \bar{R} T = \mathbb{E}\left[\sum {t=1}^{T} \ell_{t, A_t}\right] - T \min_{a} \mu(a) $$ 伪遗憾比较的是算法的期望损失和最优动作的期望损失。由于 $\mathbb{E}[\min_a \sum_t \ell_{t,a}] \le \min_a \mathbb{E}[\sum_t \ell_{t,a}]$，伪遗憾 $\bar{R}_T$ 是期望遗憾 $\mathbb{E}[R_T]$ 的下界。在随机环境中，我们可以达到 $\bar{R}_T = O(\log T)$ 的界，而 $\mathbb{E}[R_T]$ 的下界通常是 $\Omega(\sqrt{T})$，因为最优动作有机会“幸运地”获得比期望更低的损失。因此，伪遗憾是随机环境下更合理、更可达成的性能指标。

5.2 随机多臂老虎机：置信上界算法

在随机多臂老虎机中，每个臂 $a$ 的损失（或奖励）从一个固定的分布中独立采样，其期望为 $\mu(a)$。算法不知道这些期望值，需要通过试错来学习。

一个直观但低效的策略是 $\epsilon$-贪心 ：以 $1-\epsilon$ 的概率选择当前估计平均奖励最高的臂（利用），以 $\epsilon$ 的概率随机选择一个臂（探索）。它的缺点是探索是盲目、低效的。

更聪明的方法是 置信上界 算法。其核心思想是：为每个臂 $a$ 的期望奖励 $\mu(a)$ 估计一个 置信区间 。算法总是选择 置信上界 最高的臂。这样，具有高不确定性（区间宽）或高平均估计值的臂会被优先探索。

UCB1 算法 是一个经典实现：

1. 初始化：每个臂都拉一次，更新其平均奖励估计 $\hat{\mu}_a$ 和尝试次数 $n_a$。
2. 对于每一轮 $t$，选择臂： $$A_t = \arg\max_{a} \left[ \hat{\mu}_a + \sqrt{\frac{2 \ln t}{n_a}} \right]$$
3. 观察到奖励 $r_t$，更新 $\hat{\mu} {A_t}$ 和 $n {A_t}$。

公式中，$\hat{\mu}_a$ 是 利用项 ，代表当前对该臂好坏的认知；$\sqrt{\frac{2 \ln t}{n_a}}$ 是 探索项 ，与总轮数 $t$ 的对数成正比，与该臂尝试次数 $n_a$ 的平方根成反比。尝试次数少的臂，探索项大，从而鼓励尝试；随着尝试次数增加，探索项减小，算法逐渐收敛到真正的最佳臂。

实操心得：UCB 的变体与超参数 UCB1 的探索项 $\sqrt{\frac{2 \ln t}{n_a}}$ 来源于霍夫丁不等式，假设奖励在 $[0,1]$ 区间。对于其他范围的奖励，需要进行缩放。实践中，有时会在探索项前加一个可调参数 $c$，即 $c \cdot \sqrt{\frac{\ln t}{n_a}}$，用于控制探索的强度。此外，还有考虑奖励方差的 UCB-V ，以及适用于非平稳环境的 Discounted UCB 或 Sliding-Window UCB 。选择哪种变体取决于你对问题特性的先验知识。

5.3 对抗性多臂老虎机：指数权重算法

在对抗性环境中，损失序列可以是任意的，甚至由对手针对你的策略生成。此时，我们无法假设某个臂一直是最优的。算法的目标是与 hindsight 中的最佳固定臂竞争。

指数权重（Exponential Weights） 或称 Hedge 算法是解决对抗性全信息（专家建议）问题的核心思想，其变体也能用于对抗性老虎机问题。

算法原理（全信息版） ：

1. 初始化：给每个臂（专家） $a$ 分配权重 $w_{1,a} = 1$。
2. 对于每一轮 $t$：
   • 根据权重分布选择臂：$P(A_t = a) = p_{t,a} = \frac{w_{t,a}}{\sum_{b=1}^{K} w_{t,b}}$。
   • 遭受损失 $\ell_{t, A_t}$，并观察到所有损失 $\ell_{t,1}, ..., \ell_{t,K}$。
   • 更新权重：$w_{t+1, a} = w_{t,a} \cdot \exp(-\eta \ell_{t,a})$，其中 $\eta > 0$ 是学习率。
3. 权重更新可以等价地写为：$w_{t+1, a} = \exp(-\eta \sum_{s=1}^{t} \ell_{s,a})$。权重与臂的累积损失成指数负相关。损失小的臂，权重衰减慢，相对权重变大，下次被选中的概率增加。

该算法的期望遗憾上界为 $O(\sqrt{T \ln K})$。通过精心设置学习率 $\eta \propto \sqrt{\frac{\ln K}{T}}$，可以达到最优的遗憾率。

对于对抗性老虎机问题，由于只观察到所选臂的损失，我们需要一个技巧来估计其他臂的损失。 EXP3 算法 是核心解决方案：

1. 类似地维护权重 $w_{t,a}$ 和选择概率 $p_{t,a}$。
2. 选择臂 $A_t \sim p_t$。
3. 遭受损失 $\ell_{t, A_t}$。
4. 构造 重要性采样 的损失估计量：$\hat{\ell} {t,a} = \frac{\ell {t,a}}{p_{t,a}} \cdot \mathbb{I}{A_t = a}$。这个估计量是无偏的：$\mathbb{E}[\hat{\ell} {t,a}] = \ell {t,a}$。
5. 用估计的损失更新权重：$w_{t+1, a} = w_{t,a} \cdot \exp(-\eta \hat{\ell}_{t,a})$。

EXP3 通过重要性采样解决了部分观测下的损失估计问题，其遗憾上界也是 $O(\sqrt{T K \ln K})$。

注意事项：探索的强制注入 在对抗性老虎机中，如果某个臂的概率 $p_{t,a}$ 变得非常小，那么重要性采样估计量 $\hat{\ell} {t,a}$ 的方差会变得极大，导致算法不稳定。因此，实践中常在概率分布 $p_t$ 上混合一个均匀分布，即 $p’ {t,a} = (1-\gamma) p_{t,a} + \frac{\gamma}{K}$，其中 $\gamma$ 是一个小的探索参数。这保证了每个臂都有至少 $\gamma/K$ 的概率被选中，控制了估计的方差，但会引入额外的 $O(\gamma T)$ 遗憾。需要权衡选择 $\gamma$。

6. 从理论到实践：关键考量与常见陷阱

理解了基础算法后，在实际应用中还需要注意以下几个关键点。

6.1 超参数调优：学习率与探索系数

无论是 UCB 中的置信区间宽度系数 $c$，还是 Hedge/EXP3 中的学习率 $\eta$ 和探索系数 $\gamma$，这些超参数对算法性能至关重要。理论上的最优设置通常依赖于时间范围 $T$，而 $T$ 在实践中往往是未知的。

• 加倍技巧 ：一种实用方法是使用“加倍”技巧。将时间划分为区间 $[1, 2], [3, 6], [7, 14], ...$，在每个新区间开始时，重置算法并将时间范围设置为当前区间的长度。这样，算法在“局部”总是针对一个已知的时间范围进行调参。
• 自适应学习率 ：使用随时间衰减的学习率，例如 $\eta_t \propto 1/\sqrt{t}$。许多理论界在假设已知 $T$ 的情况下给出固定 $\eta$，但自适应方案在实践中更鲁棒。
• 经验调参 ：在模拟环境或历史数据上运行网格搜索，选择在验证集上表现最好的参数组合。注意避免在最终测试集上过度调参导致“过拟合”。

6.2 非平稳环境：变化是永恒的

上述基础算法大多假设环境是平稳的（随机）或完全对抗的。但真实环境往往介于两者之间——缓慢变化。例如，用户的兴趣会漂移，市场热点会切换。

• 滑动窗口 ：只考虑最近 $W$ 轮的数据进行估计。这适用于变化相对较快的情景。
• 指数衰减 ：给历史数据赋予指数衰减的权重，越近的数据权重越高。例如，在更新平均奖励估计时：$\hat{\mu}_a \leftarrow (1-\alpha) \hat{\mu}_a + \alpha \cdot r_t$，其中 $\alpha$ 是学习率。UCB 的变体 Discount UCB 也基于此思想。
• 变化检测 ：更高级的方法会包含一个变化点检测机制。当检测到统计特性发生显著变化时，重置或大幅调整算法的内部状态。

6.3 上下文信息：从多臂老虎机到上下文老虎机

当每个决策回合都有额外的 上下文 信息 $x_t$ 时（例如用户特征、商品属性），问题就变成了上下文老虎机。目标是学习一个映射函数 $f: x \rightarrow a$，使得给定上下文 $x_t$ 时，选择的动作 $a$ 期望损失最小。

• 线性上下文老虎机 ：假设期望奖励是上下文和动作参数的线性函数：$\mathbb{E}[r|a, x] = \theta_a^T x$。可以使用 LinUCB 算法，它为每个臂维护一个岭回归模型，并计算奖励的置信上界。
• 神经网络与深度强化学习 ：对于复杂的非线性关系，可以使用神经网络来拟合奖励函数。 神经网络 + Thompson Sampling 或 深度 Q 网络 的变体可以处理此类问题。但这需要更多的数据和计算资源，并引入新的调参和稳定性挑战。

6.4 常见问题排查

1. 算法收敛慢，遗憾一直很高 ：

   • 检查探索是否足够 ：在随机环境中，可能是探索系数太小，算法陷入了一个次优臂。尝试增加 UCB 的 $c$ 或 $\epsilon$-贪心的 $\epsilon$。
   • 检查损失估计是否有偏 ：在对抗性老虎机中，确保重要性采样估计量计算正确，并检查探索系数 $\gamma$ 是否太小导致估计方差爆炸。
   • 环境是否非平稳 ？如果最佳臂会随时间变化，静态算法必然表现不佳。考虑引入滑动窗口或衰减机制。

2. 方差过大，性能不稳定 ：

   • 对抗性老虎机 ：这是重要性采样估计的固有特性。增大探索系数 $\gamma$ 可以降低方差，但会增加遗憾的偏差部分。需要寻找平衡点。
   • 奖励缩放 ：确保奖励/损失值在一个合理的范围内（如 $[0,1]$）。过大的值会放大梯度，导致不稳定。

3. 计算开销过大 ：

   • 臂的数量 $K$ 巨大 ：例如，在组合优化问题中，臂可能是所有可能的路径或子集。此时无法枚举所有臂。需要使用 组合老虎机 算法，利用问题的结构（如线性、单调性）来高效地探索和利用。
   • 考虑使用 Thompson Sampling ：对于某些复杂模型，Thompson Sampling（通过从后验分布采样参数来选择动作）在计算和性能上可能比基于置信上界的方法更有优势。

从静态的批量线性回归到动态的在线学习，我们看到了机器学习范式应对不同现实挑战的演进。线性回归为我们提供了从数据中寻找稳定规律的数学工具，而在线学习则为我们装备了在不确定、交互甚至对抗的环境中持续学习和优化的能力。理解最小二乘法的几何之美，能让我们更扎实地构建预测模型的基石；掌握探索与利用的权衡艺术，则能让我们设计的算法在真实世界的博弈中游刃有余。在实际项目中，没有银弹。你需要像一名经验丰富的工程师一样，仔细诊断问题的特性（反馈类型、环境抵抗性、结构复杂性），然后从算法工具箱中选择合适的工具，并做好调参、监控和迭代的准备。记住，最好的模型不是最复杂的那个，而是最贴合问题本质、并在部署后能持续学习和适应的那个。