CC-AOS：面向有限时限最优停止的代价与时限条件摊销反向归纳

# CC-AOS：面向有限时域最优停止的代价与水平条件化摊销反向归纳
来源：https://arxiv.org/html/2607.22774
\(Draft v1 – July 23, 2026\)

###### 摘要

有限时域最优停止是早期时间序列分类中的核心问题，系统必须在每个序列前缀处决定，继续观测的预期收益是否足以证明其采集成本是合理的。现有的数据驱动反向归纳方法通常为每个代价-水平工作点单独求解，因此当工作条件变化时需要重复优化并维护独立的模型堆栈，使得连续代价适应和多水平部署效率低下。我们提出CC-AOS（代价与水平条件化摊销最优停止），这是一种结构化的摊销求解器，适用于具有连续代价和多个水平的有限时域停止问题族。CC-AOS学习一个共享的继续值模型，该模型以当前状态、绝对时间、剩余水平及采集成本为条件，通过联合摊销拟合反向归纳进行训练。我们证明了精确值函数和继续函数在代价方面是非递减、凹的且随水平依赖的Lipschitz性质，在模型架构中编码这些性质，并推导了基于残差的值与策略误差界。在受控高斯和时变非高斯过程以及FordA发动机噪声时间序列基准上的实验，将CC-AOS与代表性的每工作点反向归纳求解器及调优后的静态停止规则进行了比较。在六个未见过的FordA代价-水平对上，单个CC-AOS检查点在所有六对上实现了比独立拟合的凸函数学习更低的终端风险加采样成本目标，平均降低15.75%，同时平均与调优后的静态阈值相当。

关键词：最优停止；早期时间序列分类；反向归纳；摊销优化；形状约束神经网络。

## 1 引言

### 1.1 多工作点下的有限时域停止

顺序决策系统通常需要在所有可能信息收集完毕之前采取行动。例如，在早期时间序列分类中，可以从当前前缀做出预测，或推迟到获取另一个观测值后再做决定。提前行动可以节省时间、能量、计算或测量开销，但可能增加终端决策错误；等待可以改善预测，但其收益必须证明额外采集成本和延迟的合理性[25 (https://arxiv.org/html/2607.22774#bib.bib1),27 (https://arxiv.org/html/2607.22774#bib.bib5)]。这种权衡使得停止规则（而非仅分类准确率）成为决策问题的核心。

在有限观测预算下，问题变得更加尖锐。在序列开始时，未来仍有多个观测可用，而接近截止期限时，相同的当前证据可能意味着不同的行动。反向归纳通过将停止状态\(s\)处的终端风险\(g(s)\)与完整继续风险\(\lambda + C_h(s; \lambda)\)进行比较来捕捉这种阶段依赖性。这里，\(\lambda\)是下一观测的成本，\(C_h\)是该观测后未来期望最优风险，剩余\(h\)次采集。因此，继续值及由此产生的停止边界共同依赖于当前状态、剩余水平和采样成本[6 (https://arxiv.org/html/2607.22774#bib.bib3),17 (https://arxiv.org/html/2607.22774#bib.bib4)]。

然而，在许多应用中，成本和可用水平并非一成不变。资源可用性可能发生变化，可能需要支持多个延迟预算，或者部署的系统可能需要在不同工作条件下权衡准确性与延迟。因此，相关对象并非单一的停止策略，而是由采样成本和水平索引的有限时域问题族。相应地，本研究研究了一个统一模型，该模型能够连贯地学习该问题族，并可在训练过程中未单独求解的代价-水平对上进行查询。

### 1.2 每工作点求解器的局限性

一旦指定了工作点，反向归纳提供了一种原则性解决方案。在数据驱动设置中，其条件期望可以通过回归估计，从而得到继续值的逐阶段近似[14 (https://arxiv.org/html/2607.22774#bib.bib15),23 (https://arxiv.org/html/2607.22774#bib.bib16)]。最近的早期分类方法（包括FIRMBOUND）将学习到的顺序统计量与此有限时域递归相结合[10 (https://arxiv.org/html/2607.22774#bib.bib14)]。尽管估计器有所不同，这类求解器通常将采样成本和最大水平视为固定的问题参数：为请求的工作点拟合一个继续模型。

当仅需一种设置时，这种表述是有效的，但在面对变化的多组设置时扩展性很差。每个新的成本或水平都可能需要新的递归目标、另一次优化运行以及另一堆逐阶段模型。更重要的是，一组独立拟合的求解器仅提供明确求解的工作点处的值。它既没有定义继续值在这些点之间的行为，也未确保其近似形成一致的Bellman族。

参数条件化似乎提供了直接的补救措施，但无约束的共享网络忽略了停止问题的重要部分。对于固定的状态和剩余水平，精确最优值在采样成本变化时具有特定的几何形状：它是非递减、凹的，并且Lipschitz常数由剩余采集次数决定。因此，有用的摊销求解器应做的不仅仅是压缩几个独立训练的模型。它应该通过共享的Bellman学习过程耦合各个工作点，同时保留底层有限时域问题的成本结构。

### 1.3 结构化摊销最优停止

这些需求促使我们提出代价与水平条件化摊销最优停止（CC-AOS）。出发点在于：不同成本和水平下的停止问题并非无关的任务——它们共享相同的状态过程、终端风险和有限时域递归。CC-AOS通过将代价和剩余水平作为单个继续模型\(C_\theta(s,t,h,\lambda)\)的条件变量（而非优化前选定的固定设置）来揭示这种共同结构。

该模型通过联合摊销拟合反向归纳进行学习。在连续采样的成本和来自多个训练水平的转换上构建递归目标，因此所有工作点都贡献到一个条件值曲面。为了使学习到的曲面沿连续代价轴可靠，一个归一化的soft-min仿射头编码了已证明的精确问题所具有的单调性、凹性和剩余水平依赖的Lipschitz结构。

由此产生的表述将表示、学习和分析围绕相同的继续值族联系起来。我们推导了基于残差的界，将Bellman近似误差与值函数误差及诱导停止策略的性能损失联系起来，并评估单个检查点是否能够迁移到未见过的代价-水平对。实验涵盖受控高斯、时变非高斯过程以及FordA发动机噪声基准（采用因果前缀仅归一化）。在FordA上，CC-AOS在所有六个未见工作点上均优于独立拟合的凸函数学习，其中五个配对置信区间完全低于零，同时平均与强验证调优的静态阈值基本持平。

### 1.4 贡献

本文的主要贡献是CC-AOS，一种针对具有连续采样成本和多个水平的有限时域停止问题族的结构化摊销求解器。该求解器基于三个相互关联的贡献构建：

1. \(1\) 共享代价-水平继续模型。CC-AOS通过一个单一的继续模型\(C_\theta(s,t,h,\lambda)\)来表示停止问题族，该模型以当前状态、绝对时间、剩余水平和采样成本为条件。因此，单个训练好的检查点可以直接用于在多个以及未见的代价-水平对上构建停止策略。
2. \(2\) 联合摊销训练方法。我们开发了一种联合摊销拟合反向归纳方法，该方法在连续采样的成本和多个训练水平上构建递归Bellman目标。该方法在一个优化过程中学习共享的继续族，同时保留跨决策阶段和操作条件的递归耦合。
3. \(3\) 结构保持架构与理论分析。我们建立了精确值函数和继续函数关于采样成本的单调性、凹性和剩余水平依赖的Lipschitz性质。我们在归一化的soft-min仿射继续头中编码这些性质，并推导了值函数误差和停止策略次优性的基于残差的界。

## 2 相关工作

CC-AOS处于三条相互关联的研究线的交汇处。有限时域最优停止和早期时间序列分类定义了潜在的风险-采集权衡。数据驱动继续学习和顺序密度比估计提供了从轨迹中学习有限时域停止决策的基础。参数条件化学习和形状约束近似随后提供了在共享模型跨操作条件时，不丢弃已知价值函数结构所需的工具。

### 2.1 有限时域最优停止与早期时间序列分类

经典序贯分析形式化了决策前证据应如何累积[25 (https://arxiv.org/html/2607.22774#bib.bib1)]。对于简单假设检验，序贯概率比检验提供了具有既定最优性性质的规范停止规则[24 (https://arxiv.org/html/2607.22774#bib.bib2)]。然而，当观察受限于有限截止期限时，决策变得依赖于阶段：另一个观察的价值随着剩余时间而变化。动态规划和反向归纳为此有限时域设置提供了标准形式化[6 (https://arxiv.org/html/2607.22774#bib.bib3),17 (https://arxiv.org/html/2607.22774#bib.bib4)]。

早期时间序列分类将相同的停止问题置于预测设置中。基础形式化旨在从短序列前缀中获得准确决策[27 (https://arxiv.org/html/2607.22774#bib.bib5),28 (https://arxiv.org/html/2607.22774#bib.bib6)]。非贪心方法明确考虑了未来观测的可能收益[8 (https://arxiv.org/html/2607.22774#bib.bib7)]，而后续工作则联合优化准确性和提前性，或学习自适应停止策略[16 (https://arxiv.org/html/2607.22774#bib.bib8),12 (https://arxiv.org/html/2607.22774#bib.bib9)]。其他方法通过集成一致性或明确控制累积准确度差距来强调可靠的早期决策[20 (https://arxiv.org/html/2607.22774#bib.bib10),18 (https://arxiv.org/html/2607.22774#bib.bib13)]。CC-AOS遵循这种代价敏感的有限时域观点：停止会产生终端预测风险，而继续则会产生采集成本并保留稍后决策的选择权。

### 2.2 数据驱动反向归纳与摊销价值学习

有限时域反向归纳需要未来最优值的条件期望。最小二乘蒙特卡洛和基于回归的动态规划逐阶段从模拟轨迹中估计这些继续值[14 (https://arxiv.org/html/2607.22774#bib.bib15),23 (https://arxiv.org/html/2607.22774#bib.bib16)]。统计学习分析进一步将继续回归与最优停止近似联系起来[11 (https://arxiv.org/html/2607.22774#bib.bib17)]。神经方法将数据驱动停止扩展到高维状态空间[5 (https://arxiv.org/html/2607.22774#bib.bib18),4 (https://arxiv.org/html/2607.22774#bib.bib19)]，而可解释的策略类与随机神经特征提供了替代近似[7 (https://arxiv.org/html/2607.22774#bib.bib20),13 (https://arxiv.org/html/2607.22774#bib.bib21)]。

对于早期分类，顺序密度比估计直接从序列前缀学习类别证据并优化速度-准确率权衡[9 (https://arxiv.org/html/2607.22774#bib.bib11),15 (https://arxiv.org/html/2607.22774#bib.bib12)]。最近的工作进一步结合了数据导出的顺序统计量、后验终端风险和拟合的有限时域反向归纳[10 (https://arxiv.org/html/2607.22774#bib.bib14)]。在这个数据驱动停止框架内，CC-AOS将求解器的粒度从一个预设代价和水平的继续堆栈，转变为一个由两者联合索引的继续族。

这一扩展借鉴了更广泛的摊销优化原理，该原理学习一个参数到解的映射，以便相关问题实例共享计算[3 (https://arxiv.org/html/2607.22774#bib.bib25)]。通用价值函数近似器同样将价值模型条件化为任务变量[21 (https://arxiv.org/html/2607.22774#bib.bib22)]，多目标强化学习将策略条件化为变化的偏好权重[1 (https://arxiv.org/html/2607.22774#bib.bib23),29 (https://arxiv.org/html/2607.22774#bib.bib24)]。这些工作为将代价和水平视为模型输入提供了概念基础。CC-AOS将该原理专门化到有限时域继续学习，通过在一个拟合反向归纳方法中联合地在连续成本和多个训练水平上构建递归目标。

### 2.3 继续值的形状约束近似

形状约束神经网络提供了将已知函数结构纳入学习近似的机制。单调网络强制执行规定的坐标响应[22 (https://arxiv.org/html/2607.22774#bib.bib26)]，而输入凸神经网络编码对选定输入的凸性[2 (https://arxiv.org/html/2607.22774#bib.bib27)]。后续架构拓宽了单调近似的设计空间并改进了其灵活性[26 (https://arxiv.org/html/2607.22774#bib.bib28),19 (https://arxiv.org/html/2607.22774#bib.bib29)]。

CC-AOS基于这些架构思想，使用从有限时域Bellman问题本身导出的约束。当剩余\(h\)次采集时，精确值在采样成本方面是非递减、凹的且\(h\)-Lipschitz；相应的继续值是\((h-1)\)-Lipschitz。归一化的soft-min仿射头施加了这种依赖于水平的成本几何形状，同时允许状态、时间和剩余水平决定仿射分量。通过这种方式，数据驱动反向归纳、摊销参数条件化和形状约束近似被结合在单个继续值族中。

## 3 问题形式化

### 3.1 顺序信息与停止风险

设\(Y \in \{1,\ldots,K\}\)为类别标签，设\(X_{1:t} = (X_1,\ldots,X_t)\)为序列前缀。