🤖 machine learning

On Randomized Algorithms in Online Strategic Classification

本文通过建立实现设置下随机学习者的首个下界，并引入了一种在不可知设置下可达到最优 $O(\sqrt{T\log|\mathcal H|})$ 遗憾率的非适当随机化算法，推进了在线策略分类研究，从而证明了通过随机化和非适当性来克服确定性和适当学习方法局限性的必要性。

原作者： Chase Hutton, Adam Melrod, Han Shao

发布于 2026-06-17

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Chase Hutton, Adam Melrod, Han Shao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一名贷款审批员（学习者），正试图决定谁能获得贷款。你有一套用于判断申请人的规则（分类器），基于他们的信用历史。然而，申请人（智能体）非常聪明；他们了解你的规则，并会尝试微调自己的信用历史，只要稍微调整一点就能达到获批标准，即便他们的实际财务状况并未发生任何变化。这就是策略性分类（Strategic Classification）。

现在，想象这种情况每天都会发生，面对着新的申请人。你无法预知未来，必须在实战中不断学习并调整你的规则。这就是在线学习（Online Learning）。

Hutton、Melrod 和 Shao 的这篇论文提出了一个简单但棘手的问题：对于贷款审批员来说，带一点“随机性”会有帮助吗？ 与其固守一套僵化的规则，不如通过掷硬币的方式来决定每天使用哪条规则？

以下是他们研究结果的拆解，使用了日常类比。

背景设定：“操纵图”（The Manipulation Graph）

将申请人可能的行为想象成一张地图。

地图（图）： 想象一座城市，每一栋房子代表一个信用分。有些房子之间有道路相连。如果你住在 A 房子，如果有一条路通往 B 房子，你就可以通过移动到 B 房子来（操纵你的分数）。
度（ $\Delta$ ）： 这是任何单栋房子周围连接的最大道路数量。如果一栋房子有 10 条路，意味着申请人有 10 种微调分数的方法。
规则（假设类）： 这是贷款审批员判断申请人的不同方式。

核心问题：随机性 vs. 确定性

在正常的学习场景中（即人们不会试图欺骗你时），引入随机性并不会真正帮助你加快学习速度。你只需要一个优秀的确定性（固定）策略即可。

但在这种“棘手”的世界里（人们会试图钻空子），之前的研究表明，保持随机性可能有助于学习者躲避这些陷els。作者想要知道：随机性是一剂灵丹妙药，还是它也有局限性？

第一部分：“完美世界”场景（实现性设置/Realizable Setting）

想象一个存在完美规则的世界——如果申请人不撒谎，这套规则永远不会出错。

旧有的观点：
之前的研究表明，如果贷款审批员是刻板的（确定性的），他们可能会被诱导犯下许多错误。但如果他们是随机的，他们有时可以躲过这些陷阱。看起来随机性就像是一种超能力。

新的发现：
作者构建了一个特定的“陷阱”（数学构造）来测试这一点。

陷阱： 他们创造了一个场景，其中的申请人就像是在玩“捉迷藏”。申请人将真实的身份隐藏在众多可能性之中。
结果： 他们证明了即使贷款审批员是随机的，也无法永远逃脱这个陷阱。如果游戏持续足够长的时间，随机的审批员最终犯下的错误将与刻板的审批员一样多。
结论： 随机性不是一剂灵丹妙药。从长远来看，你无法仅仅通过掷硬币来战胜问题的本质难度。你所能达到的“最佳状态”仍然受限于规则的复杂程度以及申请人作弊的方式。

不过，也有转机：
虽然随机性在长期内没有帮助，但在短期内它是有效的。如果游戏很短（申请人数较少），随机策略比已知的最佳确定性策略犯错更少。这就像是一个在最初几轮能带来好运的护身符，但最终会失效。

第二部分：“混乱世界”场景（不可知设置/Agnostic Setting）

现在，想象一个不存在完美规则的世界。也许申请人非常狡猾，以至于任何规则最终都会在某些人身上失效。这就是“不可知”的设置。

问题所在：
之前针对这种混乱世界的最佳方法既缓慢又笨拙。这就像是在草堆里找针，你只能在极短的时间内检查一根稻草，然后就得换下一根。错误率很高。

新的解决方案：
作者发明了一种新的、略带“作弊”性质（非适当/improper）的算法。

技巧： 算法并不局限于从官方批准的规则列表中进行选择，它被允许偶尔说：“我不知道，干脆对所有人说 YES 吧。”
为什么有效： 通过偶尔对所有人说“是”，贷款审批员迫使申请人停止操纵。如果审批员对所有人说“是”，那么申请人就没有动力去改变自己的分数。这便揭示了申请人原始分数的真相。
结果： 这种“作弊”策略让学习者学得快得多。他们达到了理论上的“黄金标准”学习速度，匹配了在没有人试图欺骗时的学习速度。

代价：
作者证明了你必须使用这种“作弊”（非适当/improper）策略才能达到黄金标准的速度。如果你强迫学习者只能使用官方列表中的规则（即“适当/proper”的学习者），你会被困在较慢且笨拙的学习速度中。

论文结论摘要

随机性并非万能药： 在存在完美规则的世界里，保持随机性并不能让你永远逃避问题的本质限制。你仍然需要为问题的复杂性支付“成本”。
随机性在早期阶段有帮助： 如果申请人数较少，随机策略比确定性策略表现更好。
要在混乱的世界中快速学习，你必须“打破规则”： 要想在没有完美规则的情况下达到理论上尽可能快的学习速度，算法必须愿意使用那些不完全属于“规则”的策略（比如对所有人说“是”）。如果你严格遵守规则，你的学习速度会变慢。
“度”至关重要： 你的学习速度高度取决于申请人操纵数据的手段有多少（即地图上道路的数量）。他们作弊的方式越多，学习难度就越大。

简而言之：随机性是一个可以获得短期收益的有用工具，但要在充满陷阱的环境中赢得长期的胜利，有时你需要打破自己制定的游戏规则，才能看清真相。

技术摘要：关于在线随机策略分类的研究

1. 问题定义

本研究探讨了在线策略分类（Online Strategic Classification），在这种设定下，学习者与具有自我利益动机的代理人进行顺序交互，这些代理人会策略性地修改其可观测的特征向量，以获得有利的预测结果。学习者的目标是在这种操纵行为存在的情况下，最小化遗憾（regret）或错误界（mistake bounds）。

交互过程建模如下：

操纵图（Manipulation Graph）： 一个已知的图 $G = (X, E)$ 定义了可行的操纵行为。如果存在边 $(x, x') \in E$ ，则表示具有原始特征 $x$ 的代理人可以操纵至 $x'$ 。
代理人行为： 在观察到分类器 $h$ 后，代理人会移动到一个可达的特征向量 $z$ ，如果该向量能产生正向预测（即 $h(z)=+1$ ）；否则，他们将保持在 $x$ 。
反馈： 学习者观察到操纵后的特征 $z_t$ 和真实标签 $y_t$ ，但无法观察到原始特征 $x_t$ 。这导致了部分信息反馈。
随机算法模型（Randomized Model）： 本文在随机算法模型下运行，即学习者从一个分布中采样一个假设 $h_t$ ，向代理人展示该特定实现的具体情况，而代理人针对该实现做出最优响应。这不同于“分数模型（fractional model）”，在后者中，代理人是针对整个分布做出响应。

研究考虑了两种设定：

可实现（Realizable）： 在假设类 $H$ 中存在一个在序列上产生的策略损失为零的假设。
不可知（Agnostic）： 没有假设 $H$ 中的假设能保证零损失；目标是相对于事后最优的固定假设来最小化遗憾。

2. 研究方法

作者结合了新颖的下界构造方法和利用操纵图结构的随机算法设计。

下界构造

为了建立随机学习者的限制，作者构造了特定的操纵图和假设类，将学习问题简化为隐藏索引博弈（hidden index game）。

图结构： 他们构建了一个包含层级顶点（ $U, P$ ）和辅助节点（ $L, R, z$ ）的图，其中边的排列使得特定假设仅将 $P$ 中的一个节点标记为正。
对抗策略： 对抗者采样一个隐藏索引 $i^*$ ，并呈现代理人，迫使学习者识别出 $i^*$ 。对抗者根据学习者的分布 $D_t$ 自适应地选择代理人，通过惩罚“坏”分类器（那些在特定结构节点上出错的分类器）来惩罚学习者，同时迫使学习者在玩“好”分类器时必须猜出隐藏索引。
适当与不适当（Proper vs. Improper）： 该构造区分了适当学习者（必须输出来自 $H$ 的假设）和不适当学习者（可以输出 $H$ 之外的假设）。

算法方法

提出的算法采用一种“混合”策略，在探索（使用全正向分类器以获取完整信息）与利用（从加权专家分布中采样）之间进行随机选择。

可实现设定（有限与无限类）：
- 有限类： 算法在从一致假设集中均匀采样与使用全正向分类器之间进行混合。探索的概率经过调整，以平衡错误概率与假设集规模缩减之间的关系。
- 无限类： 算法维护一个加权专家系统，每个专家对应于输入到标准在线学习算法（如标准最优算法，SOA）中的一系列代理人。专家系统进行非对称更新，基于真实标签是正还是负，从而确保错误的专家总权重能够充分减少，同时保持一个可实现的专家。
不可知设定：
- 作者提出了一个基于指数加权 Hedge 算法的不适当随机算法（算法 3）。
- 核心创新： 该算法利用“揭示事件（reveal events）”。如果学习者使用了全正向分类器，或者采样的假设在操纵特征上预测为 $-1 $，则会发生揭示。在这些情况下，学习者可以证实没有发生操纵（即$ z_t = x_t$），并计算所有假设的策略损失。
- 估计器： 为了处理部分反馈，他们受到隐式探索技术启发，构造了一个无偏损失估计器。该估计器是有界的，且具有受控的偏差和方差，使得 Hedge 算法能够实现最优的遗憾率。

3. 主要贡献与结果

可实现设定

下界： 本文证明，对于任何随机学习者，期望错误数为 $\Omega(\min\{\sqrt{T \cdot L_{\text{dim}}(H)}, L_{\text{dim}}(H) \cdot \Delta\})$ $Ω (min {T \cdot L_{dim} (H), L_{dim} (H) \cdot Δ})$ ，其中 $L_{\text{dim}}(H)$ $L_{dim} (H)$ 是 Littlestone 维度， $\Delta$ $Δ$ 是操纵图的最大度。
- 意义： 这解决了一个开放性问题，即证明当 $T > L_{\text{dim}}(H)\Delta^2$ 时，随机化并不能改善确定性下界 $\Omega(L_{\text{dim}}(H)\Delta)$ 。
上界： 提出了一种随机算法，其期望错误界为 $O(\sqrt{T \cdot L_{\text{dim}}(H) \log \Delta})$ $O (T \cdot L_{dim} (H) lo g Δ)$ 。
- 意义： 当 $T$ 较小时（具体为 $T < L_{\text{dim}}(H) \Delta^2 \log \Delta$ ），它严格优于目前已知的最佳确定性上界 $O(L_{\text{dim}}(H) \cdot \Delta \log \Delta)$ 。

不可知设定

上界： 作者提供了一种针对自适应对抗者的不适当随机算法，其期望遗憾为 $O(\sqrt{T \log |H|})$ $O (T lo g ∣ H ∣)$ 。
- 意义： 这达到了非策略在线学习的标准最优速率，优于此前最佳的 $O(T^{3/4} \log^{1/4}(T|H|))$ 边界。
针对适当学习者的下界： 他们证明任何适当学习者必须承受至少 $\Omega(\min\{\sqrt{T \log |H| + |H|}, \sqrt{T|H| \log |H|}\})$ $Ω (min {T lo g ∣ H ∣ + ∣ H ∣, T ∣ H ∣ lo g ∣ H ∣})$ 的遗憾。
- 意义： 这表明，要实现最优的 $O(\sqrt{T \log |H|})$ 速率，不适当学习是必要的。当 $T < |H|^2 / \log |H|$ 时，适当学习者的遗憾率明显更高。

4. 本工作的意义

本文在策略分类理论方面做出了几项基础性贡献：

明确了随机化的作用： 它澄清了随机化在可实现设定中的极限，表明虽然在特定区间（较小的 $T$ ）内随机化可以带来改进，但在一般情况下，它无法克服基本的确定性下界。
最优不可知速率： 它确立了在线学习的标准最优遗憾速率在策略设定下也是可以实现的，但前提是允许学习者使用不适当假设。
不适当学习的必要性： 通过证明适当学习者的下界超过了最优速率，本文强调了策略环境下适当学习与不适当学习之间的严格分离。
精细化边界： 其结果首次提供了显式依赖于假设类 Littlestone 维度和操纵图最大度的边界，为理解策略学习的复杂性提供了更细致的视角。

该工作基于操纵图对学习者已知这一假设，这是基于图的策略分类文献中的标准假设。研究结果是理论性的，旨在提供精细的上界和下界，而非经验性评估。