Optimal Learning-Augmented Algorithm for Online Bidding¶

会议: NeurIPS 2026
arXiv: 2605.07349
OpenReview: https://openreview.net/forum?id=l10hVCrw4N
论文: https://arxiv.org/abs/2605.07349
领域: 优化/理论
关键词: 学习增强算法, 在线出价, 帕累托最优, 鲁棒性与一致性权衡, 线性搜索

一句话总结¶

提出了出价分布轮廓（Bidding Profile）分析框架，通过延迟微分方程彻底刻画并闭合了随机学习增强在线出价算法的鲁棒性-一致性理论间隙，给出了首个全范围严格帕累托最优算法，并成功推广至线性搜索问题。

研究背景与动机¶

在线出价（Online Bidding）是在线优化中的基石模型，算法在未知目标阈值 $T>0$ 下顺序提交递增出价直至不小于 $T$，目标是最小化累积出价之和。该问题直接抽象了诸如任意时间算法（Anytime Algorithm）与可中断任务调度中合同算法序列的最优时间分配权衡。经典无预测场景下，Chrobak 等人已确立了确定性 4-竞争比（倍增法）与随机 $e$-竞争比（随机平移底数几何递增）的理论紧界。然而在机器学习辅助决策的“学习增强（Learning-augmented）”范式下，如何在利用黑盒预测值 $P$ 提升无误差表现（一致性 $\chi$）的同时，防范极端误导性预测造成的灾难性损失（鲁棒性 $\rho$），成为该领域的核心研究课题。

对于确定性在线出价，已知通过在几何级数中显式嵌入预测点即可完美取得帕累托最优的鲁棒性与一致性权衡；然而随机化算法由于初始出价带有连续均匀平移，无法通过简单硬编码预测点来实现无损优化。先前由 Shin 等人提出的“预测跟随”机制与 Angelopoulos & Simon 提出的随机插值算法均在理论上留下未闭合的上下界鸿沟。核心矛盾在于：既有方法均局限于启发式拼凑特定出价序列或概率混合，缺乏能够连续统一表征任意随机出价概率测度且可对全局期望成本做精确变分分析的数学工具。

本文的核心切入点是跳出离散出价序列的显式构造局限，将其抽象为连续递增函数驱动的随机平移过程。核心 idea：引入出价轮廓（Bidding Profile）将任意随机出价策略无损转化为连续单调函数，借助延迟微分方程（DDE）与保序泛函算子求出紧致轮廓，彻底闭合随机在线出价的鲁棒性-一致性帕累托前沿。

方法详解¶

整体框架¶

算法首先通过尺度不变性将预测值标准化为 $P=1$。在线出价算法被形式化为双向无限出价策略，进而等价约化为一个定义在实数轴上的非降左连续函数——出价轮廓（Bidding Profile）$G: \mathbb{R} \to (0, \infty)$。算法在运行时仅需抽取一次标准均匀随机变量 $U \sim \mathrm{Unif}(0, 1]$，即可生成全套出价序列 $\{G(n+U)\}_{n \in \mathbb{Z}}$。通过推导出出价轮廓满足的边界偏移条件、鲁棒性积分约束与一致性积分约束，将离散对抗博弈转化为紧致泛函极值问题，并通过延迟微分方程系统构造出最优轮廓函数。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：黑盒目标预测值 P 及权衡参数 s"] --> B["测度等价约化与轮廓表达<br/>将任意随机策略无损投影为单调非降出价轮廓 G(x)"]
    B --> C["分段结构解析与边界匹配<br/>正半轴指数扩展与预测邻域常数平稳截断"]
    C --> D["延迟微分方程向后递推<br/>利用积分收缩算子 F 构建负半轴无穷历史序列"]
    D --> E["双向折返拓展与阻尼匹配<br/>正负侧双轮廓交替迭代求解非对称巡回搜索成本"]
    E --> F["随机平移采样与顺序出价<br/>抽取 U 均匀分布后按序列 G(n+U) 迭代竞价直至超过目标 T"]

关键设计¶

1. 测度等价约化与出价轮廓表示：消除算法离散形式的连续测度表征
先前工作分析随机算法时均需处理离散序列的截断概率，导致分析极度繁复且难以证明下界下确界。本文证明了任意 $\rho$-鲁棒、$\chi$-一致的随机出价策略均可通过其在实轴上的边际击中测度 $\mu$ 构造反函数，进而诱导出单调左连续的出价轮廓 $G(x)$。对于任意目标 $T$，期望出价总成本严格等价于积分 $\int_{-\infty}^{\tau(T)+1} G(t)\,\mathrm{d}t$（其中 $\tau(T) = \sup\{t : G(t) < T\}$）。从而，寻找最优在线策略完全等价于求解满足下述三项条件的最优函数 $G$：偏移条件（$x<0$ 时 $G(x)<1$，$x>0$ 时 $G(x)\ge 1$）、鲁棒性条件（对所有 $x \in \mathbb{R}$，$\int_{-\infty}^{x+1} G(t)\,\mathrm{d}t \le \rho G(x)$）以及一致性条件（$\int_{-\infty}^{1} G(t)\,\mathrm{d}t \le \chi$）。这一连续化转化不仅没有损失任何性能，更为严密证明逆向最优性提供了坚实的泛函分析基础。

2. 分段结构解析与边界紧致截断：处理预测击中阶段与大目标增长
为在预测准确（$T=1$）时耗费最小代价而在大目标（$T \gg 1$）时维持 $\rho(s) = e^s/s$ 的鲁棒性，出价轮廓在正半轴 $x>0$ 呈现特征性的两阶段构造： $$G(x) = \begin{cases} \max\left(1, s\chi \cdot e^{s(x-1)}\right), & 0 < x \le 1 \\ \max(1, s\chi) \cdot e^{s(x-1)}, & x > 1 \end{cases}$$ 当参数 $s \le \ln 2$ 时，$s\chi \le 1$，此时在区间 $(0, 1]$ 上 $G(x) \equiv 1$ 保持常数水平，确保在预测点附近进行精确探索而不产生冗余过高出价；当 $s > \ln 2$ 时，一致性要求相对宽松，常数平台在 $x_0 = 1 - \frac{\ln(s\chi)}{s} \in [0, 1)$ 处自然切换到连续指数增长。这一分段设计使得正半轴的鲁棒积分不等式在边界点严丝合缝地取等号。

3. 延迟微分方程逆向递推与积分算子不动点：严密确定负半轴衰减规律
确定了正半轴后，负半轴 $x \le 0$ 的轮廓必须满足紧致鲁棒条件，即延迟微分方程 $\rho G(x) = \int_{-\infty}^{x+1} G(t)\,\mathrm{d}t$（求导得 $\rho G'(x) = G(x+1)$）。为了从 $(0, 1]$ 向负无穷递归构造满足非负单调性的解，论文定义了函数保序算子 $\mathcal{F}$，并建立分段回溯差分： $$G(x) = G(k) - \frac{1}{\rho}\int_{x+1}^{k+1} G(t)\,\mathrm{d}t, \quad \forall x \in [k-1, k), \; k \in \mathbb{Z}_{\le 0}$$ 初值设定为 $G(0) = \chi/\rho$。论文通过构造指数上界函数 $H(x) = K e^{cx}$（其中 $c \in (s, 1)$）并利用单调收敛定理，严格证明了由 $\mathcal{F}^{(n)} G^{(0)}$ 迭代生成的不动点不仅全局非负、处处非降，而且在 $-\infty$ 处指数衰减至 0，从而以严格构造性方式给出了整条实轴上的紧致出价轮廓。

4. 双向折返拓展与阻尼匹配：线性搜索巡回轮廓构建
作者进一步将该思想拓展至经典双向线性搜索（Linear Search / Cow-Path Problem），将正负方向的折返探索定义为双轮廓对 $G_\pm = (G_+, G_-)$。此时正向穿越预测点 $+1$ 的前序成本不仅包含单向积分，更累积了对侧探索消耗。通过耦合延迟微分系统 $\rho A'_+(x) = A_+(x) + A_-(x)$ 与 $\rho A'_-(x) = A_+(x+1) + A_-(x)$，成功导出了带有修正阻尼项的近最优双向巡回轮廓。

线性搜索拓展（Excursion Profile）¶

在线性搜索中，智能体需要在原点两侧折返搜索未知目标点。借助出价轮廓的连续化框架，论文将传统离散步长序列抽象为连续巡回长度累积函数。由于搜索必须在两侧交替推进，右侧出价点产生的滞后效应会与左侧出价点产生复杂的交叉耦合。通过求解耦合时滞微分系统的特征根分布，作者证明了即使在存在往返损耗的情况下，连续轮廓依然能够将渐近下界的常数差距缩小至微小的 $0.833$，展示了出价轮廓技术对更广泛探索性在线算法的通用普适性。

实验关键数据¶

主实验：理论边界与既有工作对比¶

论文在核心理论结果中量化对比了各随机学习增强算法在关键权衡点下的鲁棒性 $\rho$ 与一致性 $\chi$。

算法机制	鲁棒性保证 $\rho$	一致性保证 $\chi$ ($P=T$)	理论最优性
经典随机出价 (CKNY08)	$e \approx 2.718$	$e \approx 2.718$	无预测最优基线
预测跟随算法 (SLLA25 上界)	$e^s / s$ ($s \in (0, 1]$)	存在正间隙 (次优)	非紧上界
连续插值算法 (AS25 上界)	$\rho \in (e, 4]$ 范围受限	无法逼近极限下界	启发式随机化
SLLA25 理论下界	$e^s / s$ ($s \in (0, 1]$)	$s \le \ln 2$ 时重合，大 $s$ 存在下界间隙	理论不完全
本文 Bidding Profile (Ours)	$\mathbf{e^s / s}$	$s \le \ln 2$ 时 $(e^s-1)/s$；$s > \ln 2$ 时 $\xi(s)/s$	全局帕累托最优 (Pareto-Optimal)

注：$\xi(s)$ 为代数方程 $\xi(2-\ln\xi)=e^s$ 在 $[1, e]$ 内的唯一解。

消融与渐近性态分析：线性搜索的极限展开对比¶

在拓展的线性搜索问题中，对比了本文算法上界与基于 Yao 氏极小化极大原理构造的下界在一致性逼近理论极值 $\chi_{\mathrm{LS}} \to 1^+$ 时的渐近常数阶展开。

分析配置 / 边界来源	主导奇异项	次级常数项	渐近余项阶数	说明
前人已知最优界 (AS25)	$\frac{2}{\chi_{\mathrm{LS}}-1}$	$> 3.5$	$O(\chi_{\mathrm{LS}}-1)$	较松弛的插值界
本文理论下界 (Yao's Lemma)	$\frac{2}{\chi_{\mathrm{LS}}-1}$	$\mathbf{+\frac{3}{2} = +1.500}$	$\Theta(\chi_{\mathrm{LS}}-1)$	基于截断反比例分布的严格下界
本文 Excursion Profile (Ours)	$\frac{2}{\chi_{\mathrm{LS}}-1}$	$\mathbf{+\frac{7}{3} \approx +2.333}$	$O(\chi_{\mathrm{LS}}-1)$	差距缩小至仅 $0.833$ 的常数差

关键发现¶

在在线出价问题中，鲁棒性-一致性前沿在 $s = \ln 2 \approx 0.6931$ 处出现一阶导数连续但形态转变的分界点：当 $s \le \ln 2$ 时，出价轮廓在预测邻域具备完全平坦的平台（$G(x)=1$），一致性呈现简单解析形式 $(e^s-1)/s$；当 $s > \ln 2$ 时，指数截断点移动至区间内部，一致性由隐式超越方程完全约束。
本文通过构造测度映射证明，任何复杂的自适应随机出价算法均无法突破 DDE 给出的积分下限，从而在整个参数域 $s \in (0, 1]$ 上严格闭合了随机在线出价的理论鸿沟。

亮点与洞察¶

将离散博弈连续泛函化：突破了以往对离散出价序列硬编码分类讨论的局限，巧妙通过单调函数与均匀平移量构造“出价轮廓”，使复杂的随机期望和转化为光滑的勒贝格积分与延迟微分方程，为在线算法的连续化分析树立了极具美感的新范式。
正反方向双向闭合：利用不动点算子保序收敛严谨构造上界存在性，同时利用概率累积测度下推与极小化打包不等式直接证明任意随机策略的下界等价性，论证逻辑严丝合缝。

局限与展望¶

平滑性（Smoothness）未予覆盖：本文专注于纯粹的极端情况（无误差 $P=T$ 与最坏极端误导误差）权衡，未深入刻画当预测误差 $|P-T|$ 处于中等连续变化时算法竞争比的光滑退化曲面。
线性搜索未达完全帕累托最优：在线性搜索的推广中，尽管大幅刷新了先前的上下界，但其构造的次级常数（$7/3$）与下界（$3/2$）之间仍有约 $0.833$ 的微小常数间距，未来若能将测度无损投影定理拓展至带符号双向跳跃系统，有望彻底攻克线性搜索的帕累托前沿。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出出价轮廓框架并建立了基于延迟微分方程的最优构造理论，极具开创性。
理论完备度: ⭐⭐⭐⭐⭐ 数学推导无懈可击，严格建立了等价约化、单调收敛、微分递推与严格下确界证明。
写作质量: ⭐⭐⭐⭐⭐ 符号体系严谨自洽，论证脉络清晰，图表与数学说明对照精准。
价值: ⭐⭐⭐⭐⭐ 彻底解决了随机学习增强在线出价这一经典开放问题，为探索类在线优化算法提供了通用泛函分析工具箱。

算法机制	鲁棒性保证 \(\rho\)	一致性保证 \(\chi\) (\(P=T\))	理论最优性
经典随机出价 (CKNY08)	\(e \approx 2.718\)	\(e \approx 2.718\)	无预测最优基线
预测跟随算法 (SLLA25 上界)	\(e^s / s\) (\(s \in (0, 1]\))	存在正间隙 (次优)	非紧上界
连续插值算法 (AS25 上界)	\(\rho \in (e, 4]\) 范围受限	无法逼近极限下界	启发式随机化
SLLA25 理论下界	\(e^s / s\) (\(s \in (0, 1]\))	\(s \le \ln 2\) 时重合，大 \(s\) 存在下界间隙	理论不完全
本文 Bidding Profile (Ours)	\(\mathbf{e^s / s}\)	\(s \le \ln 2\) 时 \((e^s-1)/s\)；\(s > \ln 2\) 时 \(\xi(s)/s\)	全局帕累托最优 (Pareto-Optimal)

分析配置 / 边界来源	主导奇异项	次级常数项	渐近余项阶数	说明
前人已知最优界 (AS25)	\(\frac{2}{\chi_{\mathrm{LS}}-1}\)	\(> 3.5\)	\(O(\chi_{\mathrm{LS}}-1)\)	较松弛的插值界
本文理论下界 (Yao's Lemma)	\(\frac{2}{\chi_{\mathrm{LS}}-1}\)	\(\mathbf{+\frac{3}{2} = +1.500}\)	\(\Theta(\chi_{\mathrm{LS}}-1)\)	基于截断反比例分布的严格下界
本文 Excursion Profile (Ours)	\(\frac{2}{\chi_{\mathrm{LS}}-1}\)	\(\mathbf{+\frac{7}{3} \approx +2.333}\)	\(O(\chi_{\mathrm{LS}}-1)\)	差距缩小至仅 \(0.833\) 的常数差