ICLR2026 学习理论学习增强算法在线算法决策论 CVaR 一致性-鲁棒性权衡在线决策

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms¶

会议: ICLR2026
OpenReview: https://openreview.net/forum?id=XGEZ9q02Ys
代码: 待确认
领域: 学习理论 / 学习增强算法 / 在线算法
关键词: 学习增强算法, 决策论, CVaR, 一致性-鲁棒性权衡, 在线决策

一句话总结¶

这篇论文把决策论里的"距离度量"和"风险度量"引入带预测的在线算法分析中，用一个相对"理想算法"的可量化指标，从一整族原本无法互相比较的 Pareto 最优/平滑算法里挑出"全局最好"的那一个，并在滑雪租赁、单峰搜索、契约调度三个经典问题上给出了可计算的最优阈值。

研究背景与动机¶

领域现状：学习增强算法（learning-augmented algorithms，又称带 ML 预测的算法）近年快速兴起。它的核心思路是：算法在运行时能拿到一个由历史数据训练出的机器学习预测（比如滑雪还要滑多少天、资产最高价是多少），用这个预测去突破传统在线算法在最坏情况下的悲观保证。衡量这类算法好坏，主流用三个指标：一致性（consistency，预测完全准确时的性能）、鲁棒性（robustness，预测任意糟糕时的性能），以及两者之间随预测误差平滑退化的能力。

现有痛点：因为一致性和鲁棒性天然冲突，不可能同时最优，于是出现了两条设计路线，各有硬伤。第一条是设计 Pareto 最优算法——在一致性-鲁棒性边界上取点。但 Pareto 最优算法往往脆弱（brittle）：哪怕预测只有一点点误差，性能也会断崖式下跌；而且即使避开脆弱，同一族 Pareto 最优算法的成员之间平滑性互不可比，根本分不出高下。第二条是强制平滑——引入一个容忍度参数 \(\delta\)（相当于对预测的信心），但这类 \(\delta\)-容忍算法在预测其实很准（误差很小）时反而表现糟糕，而且 \(\delta\) 要么得显式知道、要么只能拍脑袋选。

核心矛盾：面对无穷多个候选算法，每个都有自己的一条"性能曲线"（从一致性端点平滑过渡到鲁棒性端点），到底哪条曲线最好？传统的一致性/鲁棒性/平滑性都只看曲线上的某个点或某个局部，无法对整条曲线做有原则的全局比较。而"如何比较两条性能曲线"恰恰是决策论的看家本领。

本文目标：建立一套决策论度量，把"在一整类否则无法比较的算法里选出全局最优"这件事变成一个可量化、可计算的优化问题。

核心 idea：引入两类度量——确定性的距离度量（量化算法离一个"理想解"有多远）和随机性的风险度量（用 CVaR 刻画偏离完美预测的风险），用它们在整条预测误差谱上给每个算法打一个客观分数，从而挑出最优者。

方法详解¶

整体框架¶

论文搭建了一个统一的决策论框架，核心是先定义一个理想解 \(I_r\) 作为比较基准，然后用两类度量去衡量任意候选算法离这个理想解有多远，最后在满足鲁棒性约束的所有算法里求解使度量最优的那个。整个框架可以套到任何带单值预测的在线问题上，论文用三个经典问题（滑雪租赁、单峰搜索、契约调度）来演示。

先约定记号。对输入序列 \(\sigma\)，\(\mathrm{OPT}(\sigma)\) 是离线最优代价；算法 \(A\) 拿着预测 \(y\) 在 \(\sigma\) 上的代价记为 \(A(\sigma,y)\)，其性能比为 \(\mathrm{pr}(A,\sigma,y)=A(\sigma,y)/\mathrm{OPT}(\sigma)\)。一致性 \(\mathrm{cons}(A)=\sup_\sigma \mathrm{pr}(A,\sigma,x_\sigma)\)（预测无误差），鲁棒性 \(\mathrm{rob}(A)=\sup_{\sigma,y}\mathrm{pr}(A,\sigma,y)\)（预测对抗性）。预测误差 \(\eta=|x_\sigma-y|\)，预测范围 \(R_y=[\ell,u]\)（含真实值 \(x_\sigma\)）；当 \(R_y=[(1-\delta)y,(1+\delta)y]\) 时就是 \(\delta\)-容忍设定，但框架默认 \(R_y=[0,\infty)\)，并不强制需要这个上界。

这个框架的两类度量分别落在两条腿上：距离度量走确定性路线，不需要对预测质量做任何分布假设；风险度量走随机路线，引入一个分布式预测 \(\mu\)，用 CVaR 把"风险"形式化。两条腿都把目标统一成"在鲁棒性约束下最小化某个度量"，并且都能作为已有方法的严格推广——这是框架的关键卖点。

关键设计¶

1. 理想解 \(I_r\)：给"好坏"一个可对比的客观锚点

要量化一个算法"有多好"，必须先有个参照系。论文定义理想解 \(I_r\)：在"必须对所有输入都 \(r\)-竞争"这一鲁棒性约束下，针对输入 \(\sigma\) 能达到的最小代价；其性能比 \(\mathrm{pr}(I_r,\sigma)=I_r(\sigma)/\mathrm{OPT}(\sigma)\)。直观上 \(I_r\) 是一个"全知但同样被 \(r\)-鲁棒约束捆住手脚"的算法——它知道真实输入，却不能为此牺牲鲁棒性。任何 \(r\)-鲁棒的在线算法在任意输入上都不可能比 \(I_r\) 更好，即 \(\mathrm{pr}(A,\sigma,y)\ge \mathrm{pr}(I_r,\sigma)\)。

这个设计巧在：它把"和别的算法两两比"换成"统一和理想解比距离"。以前 Pareto 最优算法之间互不可比，正是因为没有共同的参照物；有了 \(I_r\)，每个算法都能算出一个"离理想还差多少"的绝对量，于是整族算法就能排序了。以滑雪租赁为例，\(I_r\) 的性能比是分段的：\(x<b\) 时为 \(1\)，\(x\in[b,\min\{br/(r-1),b(r-1)\}]\) 时为 \(x/b\)，再往后为 \(r/(r-1)\)——它精确刻画了"在 \(r\)-鲁棒约束下最好能做到什么"。

2. 加权距离度量：用用户指定的权重在误差谱上量"离理想多远"

有了理想解，第一类度量直接测量候选算法的性能曲线和理想曲线之间的"加权距离"。用户给一个权重函数 \(w_y:R_y\to[0,1]\)，用它表达"我在哪段预测误差上更在意"（要求 \(w_y\) 在 \([\ell,y]\) 上不减、在 \([y,u]\) 上不增，即越靠近预测点越受重视）。两个具体度量是最大加权距离

\[d_{\max}(A)=\sup_{\sigma,\,x\in R_y}\big\{(\mathrm{pr}(A,\sigma,x)-\mathrm{pr}(I_r,\sigma))\,w_y(x)\big\}\]

和平均加权距离

\[d_{\mathrm{avg}}(A)=\sup_\sigma \frac{1}{|R_y|}\int_{R_y}(\mathrm{pr}(A,\sigma,z)-\mathrm{pr}(I_r,\sigma))\,w_y(z)\,dz.\]

前者管"最坏那一点偏离理想多少"（保平滑），后者管"整段误差范围上平均偏离多少"。这套思路借鉴了分类器评估里的 ROC 曲线——人们正是用两条 ROC 曲线间的（加权）距离来比较分类器，权重能突出关心的临界区域。它的威力在于统一：把权重取成"只在预测点 \(x=y\) 处为 1、其余为 0"，\(d_{\max}\) 就退化回 Pareto 最优算法；换句话说 Pareto 最优只是这个框架的一个极端特例。论文还证明这些度量可高效优化——比如滑雪租赁的最优阈值 \(T^*_{\max}\) 能在与权重函数临界点数成线性的时间内算出（定理 2）。

3. CVaR 风险度量与 \(\alpha\)-一致性：把"对预测的信任风险"显式定价

距离度量是确定性的，但"风险"本质是随机概念，所以第二类度量先把预测改成一个分布 \(\mu\)（既可看作分布式预测，也可看作基于历史数据的先验），再引入决策论里成熟的条件风险价值 CVaR：

\[\mathrm{CVaR}_\alpha(X)=\inf_t\Big\{t+\tfrac{1}{1-\alpha}\,\mathbb{E}[(X-t)_+]\Big\},\]

它衡量损失 \(X\) 在最坏 \((1-\alpha)\) 尾部的期望，\(\alpha\in[0,1)\) 是用户的风险厌恶程度。据此定义算法的 \(\alpha\)-一致性

\[\alpha\text{-cons}(A)=\sup_{F\in\mathcal F}\frac{\mathrm{CVaR}_{\alpha,F}(A(\sigma))}{\mathbb{E}_{\sigma\sim F}[\mathrm{OPT}(\sigma)]},\]

其中 \(\mathcal F\) 是"预测信息分布与 \(\mu\) 一致"的那一类输入分布。优化目标就是：给定鲁棒性 \(r\) 和风险参数 \(\alpha\)，找 \(\alpha\)-一致性最小的 \(r\)-鲁棒算法。

这个设计的洞察在于它一个参数 \(\alpha\) 串起了两个极端：\(\alpha=0\) 时算法纯求期望最优（风险偏好型，等价于 Diakonikolas 等人分布式预测模型里的一致性）；\(\alpha\to 1\) 时算法假设概率全压在预测范围内的最坏点上（风险厌恶型，退化为对抗分析）。论文一针见血地指出，Pareto 最优算法其实是在"最大化风险"（所以脆弱），\(\delta\)-容忍算法是在"最小化风险"（所以预测准时反而吃亏），而 CVaR 让你在两者之间连续调节。\(\alpha\)-一致性因此是分布式一致性的"含风险版"推广。

三个问题上的落地¶

把上面的框架套到三个经典问题，本质都是"在无穷多个同样最优鲁棒的算法里，用度量挑出最好的阈值/调度"：

滑雪租赁：连续版，买价 \(b\)，未知滑雪天数 \(x\)，算法 \(A_T\) 在 \(T\) 时刻买。对 \(r\ge 2\)，\(A_T\) 是 \(r\)-鲁棒当且仅当 \(T\in[b/(r-1),b(r-1)]\)。论文在这区间里分别求出最小化 \(d_{\max}\)、\(d_{\mathrm{avg}}\)、CVaR 的最优阈值 \(T^*_{\max},T^*_{\mathrm{avg}},T^*_{\mathrm{CVaR}}\)（定理 2、定理 3），CVaR 版给出了 \(\mathrm{CVaR}_{\alpha,\mu}[A_T(x)]\) 的显式表达。
单峰搜索：价格序列 \(\sigma\in[1,M]\)，阈值算法接受第一个 \(\ge T\) 的价。最优竞争比 \(\sqrt M\)，对 \(r\ge\sqrt M\) 时 \(A_T\) 是 \(r\)-鲁棒当且仅当 \(T\in[M/r,r]\)。论文给出均匀权重下 \(T^*_{\max}\) 的解析解；一般权重下把它建模成算法（选 \(T\)）与对手（选 \(x\)）的二人零和博弈，对线性权重等简单情形可解析求解；CVaR 版证明 \(\alpha=0\) 恢复分布式最优一致性、\(\alpha\to1\) 恢复 \(\delta\)-容忍算法（定理 7）。
契约调度：实时系统里用可中断执行逼近不可中断算法，最优鲁棒性（加速比）为 4。论文同样在所有 4-鲁棒调度里，按最大距离（临界点法）、平均距离（闭式+数值优化）、CVaR（基于预测分布的精确公式）分别求最优调度。

实验关键数据¶

实验对比的不是"谁的预测更准"，而是在相同鲁棒性约束下，本文的距离/风险算法（MAX、AVG、CVAR\(_\alpha\)）相比现有 SOTA 的 Pareto 最优 / \(\delta\)-容忍算法能不能拿到更好的平均性能比和期望代价/收益。每个设定跑 1000 次重复，报告 95% 置信区间。

滑雪租赁（b=10, r=5）¶

对比基线是 Benomar & Perchet (2025) 的 BP\(_\rho\) 族（\(\rho\in\{b,\,b+br/2,\,b(r-1)\}\)）。

算法	平均性能比	期望代价
MAX	1.344	11.241
AVG	1.337	11.187
CVAR\(_{\alpha=0.1}\)	1.340	11.173
CVAR\(_{\alpha=0.5}\)	1.349	11.215
CVAR\(_{\alpha=0.9}\)	1.367	11.316
BP\(_{\rho=b}\)	1.677	16.987
BP\(_{\rho=b+br/2}\)	2.187	21.234
BP\(_{\rho=b(r-1)}\)	2.219	20.958

本文三类算法在所有 \(\rho\) 取值上都全面优于 BP\(_\rho\)：平均性能比从基线的 1.68–2.22 压到 1.34 附近。CVAR 的性能比和代价都随 \(\alpha\) 单调上升——符合预期，\(\alpha\) 越大越对冲不利结果、越保守。

单峰搜索（M=1000, r=100）¶

对比 \(\delta\)-容忍（δ-TOL）和两个 Pareto 最优算法 PO1（Sun et al. 2021a）、PO2（阈值取 \(\min\{t_2,\max\{t_1,y\}\}\)）。这是利润最大化问题，性能比越小越好、期望利润越大越好。

算法	平均性能比	期望利润
MAX	4.394	15.614
AVG	4.447	20.528
CVAR\(_{\alpha=0.1}\)	9.771	35.795
CVAR\(_{\alpha=0.5}\)	8.144	34.402
CVAR\(_{\alpha=0.9}\)	6.022	27.500
δ-TOL	10.009	5.475
PO1	4.630	13.904
PO2	15.685	27.986

MAX、AVG 的性能比优于除"极度脆弱的 PO2"外的所有基线，期望利润也更高。CVAR 族里，利润随 \(\alpha\) 减小、性能比随 \(\alpha\) 增大而改善；CVAR 在两个指标上都大幅超过 δ-TOL 和 PO2，平均利润也优于 PO1（代价是性能比略逊）。

关键发现¶

即便只用线性、对称这类最简单的权重函数和距离度量，距离类算法也能显著超过 SOTA——说明框架的收益不靠精巧调参。
CVaR 通过 \(\alpha\) 在"期望代价/收益"和"性能比"之间给出平滑可调的权衡：想稳就调大 \(\alpha\)，想冲期望就调小，多数情形整体性能都更好。
附录补充实验显示：预测范围越小、或权重越集中在预测点附近，本文算法表现越好——这与理论一致，因为它们能更好地利用"预测质量高"这一信息，而这正是 Pareto 最优/\(\delta\)-容忍算法做不好的地方。

亮点与洞察¶

把决策论搬进竞争分析是真正的新角度：CVaR 此前只在"无预测的随机算法"里被用过（Christianson et al. 2024），本文第一次把它接到学习增强算法的竞争分析上，并由此定义出 \(\alpha\)-一致性这个含风险的新量。
"理想解 \(I_r\)"是整个框架的支点：它把"算法两两不可比"这个老大难，转成"统一和一个客观锚点比距离"，一下子让无穷族算法可排序、可优化。这个把"相对比较"换成"绝对基准"的思路，可迁移到任何存在一整族同优算法、却分不出高下的场景。
一个统一框架同时解释了两类老方法为什么不好：Pareto 最优=最大化风险→脆弱，\(\delta\)-容忍=最小化风险→预测准时吃亏。能用同一套语言讲清两个看似无关缺陷的根因，本身就很有解释力。
"权重退化即恢复旧方法"做得很干净：距离度量权重取单点峰恢复 Pareto 最优，风险度量 \(\alpha=0/\alpha\to1\) 恢复分布式一致性/对抗分析——新框架严格包含旧结果，不是另起炉灶。

局限与展望¶

目前只验证了三个"单值预测、阈值型"的经典问题（滑雪租赁、单峰搜索、契约调度），它们的算法空间都是一维阈值/调度。框架能否扩展到多维预测、组合优化（图、调度、装箱等）这类算法空间复杂得多的问题，还是开放问题。
风险分析依赖一个给定的预测分布 \(\mu\)，并对其形状（单峰、\([\ell,y]\) 上不减等）有结构假设；现实中如何获得可靠的 \(\mu\)、\(\mu\) 设定有偏时结论是否稳健，论文未深入。
权重函数 \(w_y\) 和风险参数 \(\alpha\) 仍需用户指定：框架把"选 \(\delta\)"换成了"选 \(w_y\)/\(\alpha\)"，虽更有原则，但并没有完全消除"得有人来表达偏好"这一负担；一般权重下连解析解都拿不到（要解零和博弈或数值积分）。
实验都是合成/最坏情况输入为主（单峰搜索用了少量真实数据），真实工作负载下的收益规模仍待检验。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统地把决策论的距离度量与 CVaR 风险度量引入学习增强算法，并统一了 Pareto/容忍两条旧路线。
实验充分度: ⭐⭐⭐⭐ 三个经典问题 + 置信区间 + 参数敏感性附录，但仍以合成/最坏情况输入为主，真实负载验证有限。
写作质量: ⭐⭐⭐⭐⭐ 动机层层递进、定义清晰、"恢复旧方法"的论证干净利落，理论与直觉穿插得当。
价值: ⭐⭐⭐⭐ 提供了一个可量化、可计算、可推广的算法选择框架，对学习增强算法的分析方法论有奠基意义，落地范围目前仍偏理论。