在不可逆动态下通过求助实现安全学习

在错误不可恢复时，如何边学边接近导师，并逐渐不再求助。

• 场景：作者把医疗失误、自动驾驶碰撞、歧视性量刑、自主武器事故、生物恐怖、高风险网络攻击和失控称为不可弥补错误，即 catastrophe。在线学习要求过程中就表现好；途中已造成不可恢复损害，事后找到好策略也无意义。
• 现有不足：作者称学习理论几乎都假设错误可恢复，因而算法会尝试全部行为。重置、communicating MDP，或只在已经进入的状态上比较参考策略，都不适合这些场景。作者认为只在可恢复的实验室里训练，也挡不住部署后的新情境。
• 核心假设：不熟悉就向导师求助，并用状态距离做 local generalization：相近状态可迁移知识，距离越大越不可靠。这样不必亲自试可能不可逆的动作。
• 本文给出：在标准在线学习假设下，用三步归约得到算法，使无限状态、无重置的 multichain MDP 上，相对导师的累积遗憾和导师查询次数都是 o(T)。导师可以次优。
• 设定：
  • 比较同一初始状态下，智能体轨迹与导师轨迹的期望累积奖励之差。
  • 智能体起始无先验，不观察奖励；查询时只看到导师在当前状态会采取的动作。
  • 不允许重置。MDP 可以是 non-communicating。状态空间可无限，不能指望同一状态出现两次。
  • 无额外假设时，Figure 2 的 Heaven（每步奖励 1）与 Hell（每步奖励 0）无法区分。作者把导师访问视为对可逆性或周期性重置的补充，而不是使该问题消失。

作者用 Figure 3 的假设分类组织相关工作；除非另说，引用是代表性的而非穷尽。

错误都可恢复

• 重置或连通性：Azar et al. (2017) 周期性重置；Jaksch et al. (2010) 假设 communicating MDP。作者认为高风险领域里，有些错误无法靠以后表现好来抵消。
• 相对已犯错误：He et al. (2021)、Liu and Su (2021) 的一类遗憾，以及 Lattimore and Hutter (2011) 的 asymptotic optimality，在智能体自己的状态序列上与参考策略比较。作者指出 Figure 2 里进入 Hell 后所有动作等价，这种定义下仍算成功。
• 无限状态加 Lipschitz：Ortner and Ryabko (2012) 在可恢复假设和类似 local generalization 的 Lipschitz 假设下研究无限状态 MDP。作者指出其遗憾对度量维数的指数与本文相同，为 (2n+1)/(2n+2)。

先验知识

• 已知约束或安全策略：constrained MDP 见 Altman (1999)。Zhao et al. (2022, 2023) 假设事先知道哪些动作导致 catastrophe；Liu et al. (2021)、Stradi et al. (2024) 假设已知一条完全安全策略且周期性重置。作者对比称本文不假设对环境的先验。

外部帮助

• 安全或相对已犯错误的奖励：Cohen and Hutter (2020)、Cohen et al. (2021) 侧重安全；若给奖励保证，仍属相对已犯错误。Plaut et al. (2025) 提出 Figure 1 的避灾模型。作者称 Theorem 6 用更一般的证明恢复该文主要结果，适用于任何满足归约条件的算法，而该文只针对特定算法，且不考虑与效果相关的奖励。
• 有限状态上的奖励遗憾：作者称此前用外部帮助、在 multichain MDP 上给出奖励遗憾保证的，只有 Maillard et al. (2019) 与 Kosoy (2019)。二者都假设有限状态，时间够长就能查询每个状态，遗憾随状态数线性增长，且不需要状态相似度。作者还写道：Maillard 等的界含实例依赖参数 γ*，本文是满足假设的全体 MDP 上的 worst-case；Kosoy 要计算 Bayesian 后验，并假设可能假设只有有限个；与本文不同，Kosoy 在导师只采取安全动作且以非零概率采取最优动作时得到渐近最优奖励；其无限时域中 no-regret 指折扣因子趋于 1 时平均遗憾趋于 0。

其他工作

• 不确定时谨慎行动：代表性理论工作包括 Cortes et al. (2018)、Hadfield-Menell et al. (2017)、Li et al. (2008)。主动学习（Hanneke, 2014）和模仿学习（Osa et al., 2018）在主动求助、跟随导师上与本文相似。作者称未发现直接的技术蕴含。综述见 García and Fernández (2015)、Gu et al. (2024)、Krasowski et al. (2023)，以及 Cesa-Bianchi and Lugosi (2006)。

论文没有实证基线或基准分数。理论子程序包括 Littlestone (1988) 的全反馈算法，以及 Cesa-Bianchi and Lugosi (2006) Corollary 2.3 的 exponentially weighted average forecaster。

作者把本文定位为：导师查询加上 local generalization，在无限状态、无重置的 multichain MDP 上同时得到 no-regret 与 o(T) 查询。第一步的想法来自 Cesa-Bianchi et al. (2005)，但该文只针对单一算法；作者称后两步归约在技术上是新的，并称据其所知先前工作推不出这一结论。

整体是三步归约：全反馈在线预测先变成有查询预算的主动学习，再在不熟悉状态求助以避灾，最后说明避灾算法自动在 multichain MDP 上有次线性遗憾。Figure 1 把四类模型连到 Section 4/Theorem 1、Section 5/Theorem 5、Section 6/Theorem 8。

共享协议与目标模型

• 交互：每步对手给出状态 s_t 与正确动作 a^m_t。算法决定 q_t，仅当 q_t=1 时看到 a^m_t，再选 a_t。T 已知；Algorithm 1 和 2 对 T 的依赖可用标准 doubling trick 去掉。状态空间为方便设为可数，作者称连续空间没有根本障碍。
• 对手：V 把历史映到下一状态与正确动作的分布。σ-smooth 要求状态边际相对固定基准分布 β 满足 p(X)≤β(X)/σ；按作者约定，σ=0 是完全对抗。σ^+ 在 σ>0 时为 1/σ，在 σ=0 时为 0。
• 三个目标：Table 1 中，标准对抗主动学习假设不会灾难，遗憾次线性，查询结果在选动作之后看到，且该节算法是 query-agnostic。避灾模型只要求避开灾难，总遗憾要随 T 趋于 0，查询结果在选动作之前看到。MDP 要高奖励，因而必须避灾，并分开比较智能体状态 s 与导师状态 s^m。
• 策略类与损失：在已知 Π 上优化。可实现性指存在策略使动作与正确动作一致，不表示导师对 MDP 奖励最优。有限 VC 或 Littlestone 维在本文意味着 |A|=2。Section 4.3 用 one versus rest：每个动作一个二分类副本，总遗憾和查询不超过各副本之和。

第一步：全反馈变成主动学习

• 构造：Algorithm 1 给定总是查询的 Γ_FF 和期望预算 k。每步以 Bernoulli(k/T) 独立查询，只把已查询步的历史交给 Γ_FF。当步动作不使用当步查询结果。
• 界：Theorem 1 要求全反馈上界 R(T,σ) 对 T 凹。则期望查询数恰为 k，Reg_SA≤(T/k)R(k,σ)。
• 可实现时的全反馈：损失是 0-1 损失。Lemma 2：Littlestone 维 d 且 σ=0 时，存在算法使 Reg_SA≤d。Lemma 3：VC 维 d 且 σ∈(0,1] 时，Reg_SA∈O(d log T+σ^+)。其证明用大小至多 (41T)^d 的 1/T-cover，再跑指数加权平均预测器。
• 为何要可实现性：Corollary 4 得到 Reg_SA∈O((T/k)(d log k+σ^+)) 且 Q=k。作者称把典型平方根级全反馈界直接套进 Theorem 1，不足以让后面的 MDP 归约得到次线性遗憾。

第二步：不熟悉就求助

• 避灾目标：对手事先选定 π^m∈Π。μ_t(s,a) 是此前未灾难的条件下，第 t 步避开灾难的概率；全程避开的概率是这些项的乘积。乘性遗憾比较对数乘积，加性遗憾比较概率和，作者把后者解释为不可逆损害总量。两者都要求总遗憾随时间范围 T 趋于 0。μ_0>0 时乘性遗憾有定义；最终 MDP 结果不需要它。智能体看不到 μ。
• 局部泛化：S⊆R^n。L-local generalization 写为 |μ^m_t(s)−μ_t(s,π^m(s′))|≤ L||s−s′||，即把在 s' 学到的导师动作用到 s 时，避灾概率差距不超过欧氏距离的 L 倍。智能体不必知道 L 或显式编码，只需对特定已查询子集算最近邻距离。作者称没有该假设时，即使 VC 维有限且对手 σ-smooth，避灾也不可能。
• 算法：Algorithm 2 先在模拟历史上看默认算法会选的动作。若该动作在已记录查询中的最近邻距离大于 ε，则查询并执行导师动作，把该状态–动作对加入集合；否则跟随默认算法。作者称 ε 要平衡安全与自足。最终取 ε 为 T 的 -1/(n+1) 次；Theorem 5 先对一般 ε 给界。
• 界：默认算法查询≤k 且 0-1 遗憾≤R(k,T,σ) 时，加性避灾遗憾≤LεR；μ_0>0 时乘性遗憾≤LεR/μ_0；查询∈O(k+R+|A|E[diam(s)^n]/ε^n)。Theorem 6 取 k 为 T 的 (2n+1)/(2n+2) 次，得到次常数避灾遗憾和次线性查询。作者称这些界在略松后做了简化。Remark 7：轨迹分布不依赖 μ，同一分布对所有允许的 μ 同时满足这些界。

第三步：不改算法抬到 MDP

• MDP 对手：只选转移 P、导师策略和初始分布。导师轨迹独立演化，每步在自己的状态上执行 π^m。Reg_MDP 比较两条轨迹的期望奖励和。若导师去 Heaven、智能体去 Hell，该定义给出遗憾 T-1。
• 转移假设：对全变差距离，导师动作下的下一步分布随状态距离以常数 L 变化。P 与 r 的 L 不同则取较大者。奖励同样不直接观察；算法不用奖励观察。
• 归约本身：Theorem 8 不修改算法。凡 Reg^+_AC≤R(T,σ) 的算法，在 P 和 r 都满足 local generalization 时，Reg_MDP≤(T+1)R(T,σ)。作者称这不是“在某一个 MDP 里避灾就足以获得高奖励”（作者称这一般不成立），而是能在一般环境避灾的算法必有也保证高奖励的性质。
• 分解：遗憾拆成状态项与动作项，中间插入导师动作在智能体状态上的奖励。作者称证明主要部分是用 P 的 local generalization 说明状态项≤T 倍 Reg^+_AC。若还有 Reg_SA 界，Theorem 9 不再要求 r 的 local generalization，上界为 R_1+T R_2。Lemma 24 说明 Algorithm 2 同时有这两类界。作者认为该分解是新的，并与使用 Q 函数或价值函数的 reference-advantage 分解（Zhang et al., 2020）区分：本文每项只含短期奖励，长期效果留在隐含处。

拼成最终算法

• 参数：Theorem 10 使用与 Theorem 6 相同的 Algorithm 2。对转移满足 L-local generalization 的 σ-smooth 或完全对抗 multichain MDP，遗憾为 O(L T 的 (2n+1)/(2n+2) 次，再乘 (d log T+σ^+))，查询为 O(T 的同一指数，再乘 (d+σ^++E[diam(s)^n]))。
• 一个实例：Algorithm 3 与 Corollary 11 在 σ∈(0,1]、VC 维 d、A={0,1} 时，于 1/T-cover 上跑指数加权平均。即使落在不熟悉轮，仍以概率 k/T 查询并更新权重。界中 σ^+ 写成 σ^{-1}。作者称归约较一般，这只是一种足够说明问题的算法。

实验设置

• 无实证运行：论文未报告被测模型、数值模拟、基准分数、样本量或重复次数。结果是定理上界。
• 策略类：要么 Π 的 VC 维为 d 且 σ∈(0,1]，要么 Littlestone 维为 d 且 σ=0。两种情形都要求可实现：正确动作由 Π 中某策略给出。有限维在本文写法下对应 |A|=2。
• 环境：multichain MDP，无重置，状态可无限。转移对导师动作满足 L-local generalization（全变差距离）。奖励映到 [0,1]。Theorem 8 还要求奖励满足同一假设；Theorem 9 与 Theorem 10 不要求。
• 指标：标准模型用 Reg_SA（0-1 预测损失）；避灾模型用 Reg^×_AC 与 Reg^+_AC；MDP 用 Reg_MDP，即同一初始分布下导师轨迹与智能体轨迹的期望奖励差。查询用期望次数 Q。
• 参数：Theorem 6 与 Theorem 10 取 k 为 T 的 (2n+1)/(2n+2) 次，熟悉度阈值 ε 为 T 的 -1/(n+1) 次。n 是 S⊆R^n 的维数。
• 具体子程序：Corollary 11 把归约套到 Cesa-Bianchi and Lugosi (2006) Corollary 2.3 的 exponentially weighted average forecaster，作用在 Π 的 1/T-cover 上，并假设 A={0,1}。

主结果

论文没有实验结果表。下表转写定理正文里的上界，不是测量值。条件均为：可实现，且 (1) VC 维 d、σ∈(0,1] 或 (2) Littlestone 维 d、σ=0；转移满足 L-local generalization。

对象	上界形式	出处
Reg_MDP	O(L T 的 (2n+1)/(2n+2) 次，乘 (d log T+σ^+))	Theorem 10
Q	O(T 的 (2n+1)/(2n+2) 次，乘 (d+σ^++E[diam(s)^n]))	Theorem 10
Reg^+_AC	O(L T 的 -1/(2n+2) 次，乘 (d log T+σ^+))	Theorem 6
Reg^×_AC（仅 μ_0>0）	上式再乘 1/μ_0	Theorem 6

• 作者称 Theorem 10 是对所有满足假设的 multichain MDP 的 worst-case，查询为 o(T)，因而查询率趋于 0；no-regret 指累积遗憾为 o(T)。
• 作者称据其所知，这是无限状态空间 multichain MDP 的首个 no-regret 保证，并认为这可能是如下陈述的首次形式化证明：智能体可在未知、无界、高风险且无重置的环境中获得高回报并变得自足。
• 比较对象是导师，不是最优策略。Corollary 11 在 A={0,1}、σ∈(0,1] 时把 σ^+ 写成 σ^{-1}，T 的指数与 Theorem 10 相同。

避灾模型上的保证

• 测的是什么：把 Corollary 4 的主动学习算法作为 Algorithm 2 的默认算法，在避灾模型上给界，而不是在某个命名 MDP 上模拟。
• 结果：Theorem 6 的加性总遗憾随 T 的负幂趋于 0；查询仍是上表中的次线性形式。乘性遗憾只在 μ_0>0 时写出，并多一个 1/μ_0。
• 作者的解读：这里要的是次常数遗憾，不是平均每步遗憾趋于 0；作者称按 T 选择参数是得到次常数遗憾的关键。Remark 7 称轨迹分布不依赖 μ，因此第三步可以在轨迹之后再选择用来编码转移概率的 μ。

遗憾分解给出的 MDP 界

• 拆分：Section 6.3 在 Reg_MDP 中插入导师动作在智能体状态上的奖励，分成状态项与动作项。
• 结果：作者称状态项至多 T 倍 Reg^+_AC。若奖励也满足 local generalization，动作项至多 Reg^+_AC，于是 Theorem 8 为 (T+1) 倍。若不假设奖励的 local generalization，动作项改由 Reg_SA 控制，Theorem 9 为 R_1+T R_2。
• 与最终定理的关系：Theorem 10 走 Theorem 9 这条路，所以最终 MDP 界不要求奖励函数的 local generalization。Lemma 24 给出 Algorithm 2 的 Reg_SA 为 O(T 的 1/(2n+2) 次，乘 (d log T+σ^+))。

概念上的反例与范围

• Heaven or Hell：Figure 2 中 Action 1 进入 Heaven，此后每步奖励 1；Action 2 进入 Hell，此后每步奖励 0。作者称无额外假设时无法分辨二者，因而不能保证高奖励。若导师走 Heaven、智能体走 Hell，本文遗憾定义为 T-1。
• 无局部泛化：作者称此时即使策略类 VC 维有限且对手 σ-smooth，避灾也不可能；该陈述指向 Plaut et al. (2025) 的 Theorem E.2，不是本文新实验。
• 完全对抗更强：Appendix D 指出有限 Littlestone 维很强，例如 [0,1] 上的阈值类可以有无限 Littlestone 维。此时本文的对数级全反馈界需要 σ∈(0,1] 和有限 VC 维。

其他消融与分析

论文未报告消融、参数扫描或实例曲线。中间界如下，变量是定理所改变的查询预算、阈值或遗憾类型。

• Theorem 1：Q=k；若 R 对第一自变量凹，则 Reg_SA≤(T/k)R(k,σ)。
• Lemma 2：Littlestone 维 d、可实现、σ=0 时，Reg_SA≤d。
• Lemma 3：VC 维 d、σ∈(0,1]、可实现时，Reg_SA∈O(d log T+σ^+)。
• Theorem 5：Reg^+_AC≤LεR(k,T,σ)；μ_0>0 时 Reg^×_AC≤LεR/μ_0；查询另含 |A|E[diam(s)^n]/ε^n。
• Theorem 8：P 与 r 都满足 local generalization 时，Reg_MDP≤(T+1)R(T,σ)。
• Theorem 9：有 Reg_SA≤R_1 且 Reg^+_AC≤R_2 时，Reg_MDP≤R_1+T R_2，不要求 r 的 local generalization。

作者指出的局限与后续方向

• 还不能实用，cover 计算贵：作者称算法尚未达到可实用；计算 1/T-cover 的计算代价高。已有避免显式计算 cover 的技术（如 Block et al., 2022），作者称这可以是未来工作。（Section 7）
• 高维时只是勉强次线性：最终查询与遗憾界为 Õ(T 的 (2n+1)/(2n+2) 次）。作者称 n 大时这只是勉强次线性；指数来自覆盖 n 维空间所需查询，即维度灾难。智能体只从查询中学习。作者称给出初始离线数据集就不必用导师查询覆盖整个空间，并可能改进界。（Section 7；引言脚注亦把离线数据列为未来工作并指向 Section 7）
• 完美距离：作者称另一项局限是算法依赖完美计算状态距离才能利用 local generalization，并将其类比为完美的分布外检测器，称这仍是开放问题（Yang et al., 2024）。未来工作可考虑更现实的分布外检测，和/或更不严格的 local generalization。（Section 7）
• 全可观测与已知策略类：作者称本文还使用了全可观测和已知策略类这些标准但具有限制性的假设，未来可以放松。（Section 7）
• 没有导师时的谨慎学习：作者关心导师并非总是可用的情形。一个可能方向是从糟糕但非灾难的经历中学习，例如非致命的食物中毒会让人以后更谨慎；作者称当前模型没有刻画这一现象。（Section 7）

实验覆盖范围

• 定量结果是 Theorem 1、5、6、8、9、10 与 Corollary 4、11 的上界，对象是可实现、转移满足 L-local generalization，且具有 VC 维（σ∈(0,1]）或 Littlestone 维（σ=0）的策略类。
• Theorem 10 的 MDP 遗憾界不要求奖励 r 的 local generalization；Theorem 8 的 (T+1) 倍界要求 (r,π^m)∈R(L)。
• Algorithm 3 假设 A={0,1}。Section 4.3 用 one versus rest 把 |A|>2 时的遗憾与查询写成各副本之和，并称 multiclass 的 VC 或 Littlestone 变体超出本文范围。
• 查询结果的观察时机按 Table 1：标准对抗主动学习在选动作之后，避灾模型与 multichain MDP 在选动作之前。状态空间在 Section 3.1 设为可数；界依赖维数 n 与 E[diam(s)^n]。
• 论文未报告数值模拟、具体转移核上的遗憾值、查询次数的实测值、重复次数，以及具体的 n、d、L 或基准分布 β。

作者用在线学习归约处理无重置、状态不必重复出现、部分错误不可恢复的学习。

• 问题：智能体要从零开始，在学习过程中接近导师的累积奖励，同时让求助率趋于 0。导师可以次优。比较的是同一初始状态下各自轨迹的期望奖励，不是只在智能体已经进入的状态上比较。
• 方法：全反馈预测先按预算 Bernoulli(k/T) 随机查询，并只在被查询步上更新。默认算法只在最近邻距离不超过阈值时被跟随；否则执行导师演示的动作。避灾阶段控制的是总损害随时间范围趋于 0。该保证不改算法即可转移到 MDP：状态分布偏差主要由转移的 local generalization 控制，动作差距由预测遗憾控制。
• 结果：在 VC 维配平滑对手，或 Littlestone 维配完全对抗，并且转移对导师动作满足 L-local generalization 时，Theorem 10 的 Reg_MDP 为 O(L T 的 (2n+1)/(2n+2) 次，再乘 (d log T+σ^+))，查询为 O(T 的同一指数，再乘 (d+σ^++E[diam(s)^n]))。避灾模型上，Theorem 6 的加性总遗憾带负指数 -1/(2n+2)。Figure 2 中走错永久低奖励路径时，本文遗憾为 T-1。论文没有模拟数值。
• 作者的结论：作者称据其所知，这是无限状态 multichain MDP 的首个 no-regret 保证，并认为这可能是如下陈述的首次形式化证明：智能体可在未知、无界、高风险且无重置的环境中获得高回报并变得自足。作者同时称算法还不能实用：cover 计算代价高，维数高时界只是勉强次线性，而且依赖完美的状态距离。