The Pareto Frontier of Randomized Learning-Augmented Online Bidding¶
会议: NeurIPS 2026
arXiv: 2605.06106
OpenReview: https://openreview.net/forum?id=ahakqyD1h0
代码: 待确认
领域: 学习理论
关键词: 在线出价、学习增强算法、帕累托最优、出价函数、增量中位数
一句话总结¶
提出了将离散随机出价序列连续化分析的“出价函数”（Bidding Function）全新理论框架，在学习增强在线出价问题中首次给出了紧致的随机化一致性-鲁棒性界限，并在 \(R \ge 2/\ln 2 \approx 2.885\) 的广泛区间内完全闭合了帕累托前沿。
研究背景与动机¶
在线出价（Online Bidding）是在线决策中的经典基础抽象，广泛应用于计算资源配额调整、层次聚类以及无界线搜索等序列决策场景。算法需要在未知真实阈值 \(u\) 的情况下逐次提交单调递增的出价序列，直至某个出价不低于 \(u\)，且必须为此前所有未成功的猜测付出累积成本。在经典的无预测竞争分析框架下，确定性算法的最优竞争比为 4，而随机化出价通过在几何级数上施加随机扰动可将竞争比降至 \(e \approx 2.718\)。随着机器学习在系统优化中的普及，学习增强算法（Learning-augmented Algorithms）力图引入来自历史数据或 ML 模型的预测阈值 \(\hat{u}\)：在预测准确时力求实现尽可能低的归一化成本（一致性 Consistency，记为 \(C\)），而在预测完全失效的最坏情况下仍能保证有界的竞争比上限（鲁棒性 Robustness，记为 \(R\)）。
然而，确定性在线出价的帕累托前沿（Pareto Frontier）早在几年前就已由 Angelopoulos 等人完全刻画，而随机化情形下的帕累托最优权衡却长期处于未解状态。此前的探索要么依赖分段线性的启发式构造，导致所得理论上下界存在显著鸿沟；要么因在离散随机序列上分析组合概率极其繁琐，难以构建全局一致的最优性证明。特别是在鲁棒性要求极高、逼近理论极限 \(e\) 的场景下，已知算法的一致性收益仅能达到 \(e - \Omega(\varepsilon)\) 的一阶衰减，随机化在学习增强在线出价中究竟能释放多大的潜力始终悬而未决。
面对离散随机序列分析维数灾难与连续极限性质的脱节，本文打破了基于离散序列概率差分的传统分析范式，将研究对象提升为定义在实数轴上的连续单调函数。核心 idea：引入将离散随机序列完备映射至连续域的“出价函数”（Bidding Function）抽象，利用归一化质量与时滞微分方程（Delay Differential Equation）精确构造连续出价策略，结合基于对偶线性规划的匹配下界，首次在 \(R \ge 2/\ln 2 \approx 2.885\) 的广阔区间上精确解析出 \(C = R - \overline{w}(R)\) 的帕累托最优前沿，并将 \(R \to e\) 邻域内的一致性增益指数级提升至 \(e - \Omega(\varepsilon^{1/4})\)。
方法详解¶
整体框架¶
本文的核心洞察在于：任意双向无限的随机递增出价序列，其期望归一化成本都可以由一个连续的单调非递减函数 \(B: \mathbb{R} \to \mathbb{R}_+\) 完美诱导并上界化。通过将时间轴上的连续质量积分与归一化阈值相除，原本离散序列中繁复的离散期望计算被转化为连续函数上的极值分析。系统基于这一数学对象构建了完整的出价策略设计、性能解析与匹配下界证明管线。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
In["输入：鲁棒性约束 R ≥ e 与阈值预测 û"] --> D1["出价函数理论化表示<br/>连续单调函数 B(t) 诱导随机出价 X_B"]
D1 --> D2["时滞微分方程策略构造<br/>分段多项式反向递归 + 确定性平移 + 指数上界延伸"]
D2 --> Branch{"鲁棒性区间划分"}
Branch -->|R ≥ 2/ln 2 ≈ 2.885| Opt["解析解 C = R - w̄(R)<br/>Lambert W 闭式解，闭合帕累托前沿"]
Branch -->|e ≤ R < 2/ln 2| NearOpt["连续伸缩解 C = R / (2-y)<br/>收敛速率 e - Ω(ε^(1/4))"]
Opt --> D3["对偶线性规划紧致下界证明<br/>网格离散化 LP 弱对偶构造，消除理论鸿沟"]
NearOpt --> D3
D3 --> Out["输出：帕累托最优随机出价序列与增量中位数聚类应用"]关键设计¶
1. 出价函数理论化表示：将离散序列离散期望转换为连续函数极值分析 以往对随机出价序列 \(X = (x_i)_{i\in\mathbb{Z}}\) 的分析必须显式处理每个出价落在各区间的离散概率。本文定义出价函数 \(B: \mathbb{R} \to \mathbb{R}_+\) 为单调非递减函数，满足 \(\lim_{t\to -\infty} B(t) = 0\)、\(\lim_{t\to +\infty} B(t) = +\infty\) 且负无穷积分收敛。从 \(B\) 诱导出的随机序列定义为 \(X_B := (B(i+\lambda))_{i\in\mathbb{Z}}\)，其中 \(\lambda \sim U[0, 1]\) 为均匀分布随机偏移。 为度量任意阈值下的代价，本文定义了归一化质量（Normalized Mass）\(\tilde{B}(t)\) 与功函数（Work Function）\(w_B(t)\)： $\(\tilde{B}(t) := \int_{-\infty}^{t+1} \frac{B(x)}{B(t)} \mathrm{d}x, \quad w_B(t) := \int_{-\infty}^t \frac{B(x)}{B(t)} \mathrm{d}x\)$ 通过广义反函数技巧，定理 1 与定理 2 严格证明了对任意随机序列 \(X\)，均存在出价函数 \(B\) 使得 \(\inf_u \operatorname{nc}(X, u) = \inf_t \tilde{B}(t)\) 且 \(\sup_u \operatorname{nc}(X, u) = \sup_t \tilde{B}(t)\)。由此，一致性与鲁棒性等价于研究标量函数 \(\tilde{B}(t)\) 的全局下确界与上确界，彻底摆脱了离散组合计数。
2. 时滞微分方程策略构造：解析确定性与随机化混合的最佳动态外推 为了使出价函数在 \(t=0\) 处取得最低归一化质量（对应预测准确时的一致性 \(C\)），同时在全局所有 \(t \in \mathbb{R}\) 上保持 \(\tilde{B}(t) \le R\)，本文揭示了 \(B(t)\) 在负半轴必须服从的一阶时滞微分方程（Delay Differential Equation）：\(R B'(t) = B(t+1)\)。满足该微分方程的连续函数在 \(t < 0\) 区域内恒有 \(\tilde{B}(t) = R\)。 对于 \(R \ge 2/\ln 2\)： - 在 \(t \ge 1\) 区间，函数采用最优指数扩张 \(A(t) = e^{(t-1)/\overline{w}}\)，其中 \(\overline{w} = -1/W_0(-1/R)\) 是方程 \(w e^{1/w} = R\) 的最大实根； - 在 \(t \in [0, 1]\) 区间，固定 \(A(t) = 1\)，诱导出集中于预测点附近的确定性出价； - 在 \(t \le 0\) 区间，定义 \(k = \lceil -t \rceil, s = [-t]\)，函数由分段多项式 \(p_k(s)\) 逆序归纳构造：\(p_0(s) = 1, p_1(s) = x(\mu - 1 + s)\)（其中 \(x = 1/R, \mu = R - \overline{w}\)），递推关系为 \(p_{k+1}(s) = p_k(0) - x \int_s^1 p_k(u) \mathrm{d}u\)。 作者利用形式幂级数展开，严谨证明了多项式系数全正性与负半轴积分收敛性，从而保证了出价策略的良定性，最终在 \(t=0\) 处实现严格的一致性 \(C = R - \overline{w}\)。
3. 对偶线性规划紧致下界证明：以网格离散化证明代数不可能界 为证明所提策略是真正的帕累托最优，本文建立了一族参数化线性规划 \(P_{a, N, M}^R\)：以步长 \(1/a\) 离散化出价函数参考点，变量 \(x_k\) 表示小区间内的累积出价积分。该 LP 以极小化 \(t=0\) 处的出价代价 \(C\) 为目标，施加所有参考点归一化质量不超过 \(R\) 的鲁棒性约束。 作者解析构造了其对偶问题 \(D_{a, N, M}^R\) 的可行解序列 \((\lambda, \beta_k, \gamma_k)\)。通过对特征方程 \(X^a - a R (X - 1) = 0\) 的唯一最小实根 \(\rho \in (1, 1+1/a)\) 进行渐近分析，证明当网格密度 \(a \to \infty\) 与截断边界 \(N \to \infty\) 时，对偶目标函数 \(\lambda_{a, N}\) 精确收敛于黎曼积分： $\(\lim_{a\to\infty} \lambda_a = \int_0^1 e^{\theta x} \mathrm{d}x = \frac{e^\theta - 1}{\theta} = R - \overline{w}\)$ 其中 \(\theta = 1/\overline{w}\)。该下界定理（定理 11）证明任何满足鲁棒性 \(R\) 的随机出价序列，其一致性均不可能低于 \(R - \overline{w} - \varepsilon\)，从而以完全代数的方式闭合了 \(R \ge 2/\ln 2\) 区间的理论上下界鸿沟。
实验关键数据¶
主实验¶
论文通过理论闭式推导、高斯预测误差下的数值模拟，以及经典增量中位数（Incremental Median）实际路网聚类实验，全方位对比了本文提出的最优算法 \(A\)、分段线性指数类最佳算法 \(I\)、以及此前发表于 NeurIPS 2025 的经典算法 \(D\)（Class \(\mathcal{D}\)）。
| 鲁棒性区间 / 评测设定 | 算法 / 理论界 | 一致性保证 \(C\) | 鲁棒性 \(R\) | 理论状态 / 核心结论 |
|---|---|---|---|---|
| 理论前沿 \(R \ge 2/\ln 2 \approx 2.885\) | 确定性翻倍策略 [3] | \(C = \frac{R - \sqrt{R(R-4)}}{2}\) | \(R \ge 4\) | 确定性最优界，缺乏随机化平滑性 |
| 理论前沿 \(R \ge 2/\ln 2 \approx 2.885\) | 算法 \(D\) (NeurIPS 2025 [5]) | 复杂隐式方程解 | \(R\) | 存在明显理论 Gap，未达到帕累托最优 |
| 理论前沿 \(R \ge 2/\ln 2 \approx 2.885\) | 下界 (Shin et al. [40]) | 松弛解析下界 | \(R\) | 非紧致下界 |
| 理论前沿 \(R \ge 2/\ln 2 \approx 2.885\) | 算法 \(A\) (本文) | \(R - \overline{w}(R)\) | \(R\) | 与对偶下界精确吻合，闭合帕累托前沿 |
| 渐进极限制 \(R \to e + \varepsilon\) | 算法 \(D\) [5] | \(e - \Omega(\varepsilon)\) | \(e + \varepsilon\) | 一阶线性衰减 |
| 渐进极限制 \(R \to e + \varepsilon\) | 算法 \(I\) (本文中间类) | \(e - O(\sqrt{\varepsilon})\) | \(e + \varepsilon\) | 平方根阶提升 |
| 渐进极限制 \(R \to e + \varepsilon\) | 算法 \(A\) (本文) | \(e - \Omega(\varepsilon^{1/4})\) | \(e + \varepsilon\) | 四次方根超快收益提升，理论最优 |
| 数值模拟高斯误差 (\(R=4, \sigma^2 \le 1.19\)) | 算法 \(A\) vs \(D\) / \(I\) | 归一化成本最低 | \(\le 4.0\) | 在中低预测噪声下平滑性与代价全面占优 |
| 增量中位数聚类 (Isle of Man, \(\hat{k}=2500\)) | 算法 \(A\) vs \(D\) / \(I\) | 经验近似比 \(\approx 2.45\) | \(\le 4.0\) | 对比 \(I\) (\(\approx 2.65\)) 与 \(D\) (\(\approx 3.10\)) 优势显著 |
消融实验¶
为了量化出价函数不同结构（确定性台阶、连续斜率、时滞微分多项式递推）对性能权衡的影响，论文针对不同出价函数族进行了细致对比。
| 函数类别 / 策略变体 | 核心数学结构 | 鲁棒性上限 \(R\) | 极小一致性 \(C\) | 性能特征与消融结论 |
|---|---|---|---|---|
| 纯指数类 \(\mathcal{E}\) | 全局单斜率 \(B(t) = e^{t/w}\) | \(R = w e^{1/w}\) | 恒等于 \(R\) | 无预测增强能力，归一化成本恒定 |
| 不连续分段类 \(\mathcal{D}\) | 分段离散跳变 \(B_{\ell, h}(t)\) | \(\frac{e^\ell - 1}{\ell} \frac{e^{\ell+2h}}{e^{\ell+h}-1}\) | \(\frac{e^\ell - 1}{\ell} \frac{e^{\ell+h}}{e^{\ell+h}-1}\) | 包含随机化程度不足，误差曲线呈锯齿状震荡 |
| 连续插值类 \(\mathcal{I}\) | 整数节点间指数连续插值 | 给定 \(R\) | \(w¯ + 1\) (\(R \ge 4.8\)) | 消除了不连续跳变，渐进增益达到 \(O(\varepsilon^{1/2})\) |
| 完整策略 \(A\) (\(R \ge 2.885\)) | 时滞微分方程 + 确定性台阶 | \(R\) | \(R - \overline{w}\) | 兼具单点极值与全局平滑，达到紧致最优 |
| 完整策略 \(A\) (\(R < 2.885\)) | 时滞微分方程 + 平滑伸缩 | \(R\) | \(R / (2-y)\) | 消除确定性硬台阶，以连续性换取微小鲁棒性 |
关键发现¶
- 大鲁棒性区间帕累托最优闭合：当 \(R \ge 2/\ln 2 \approx 2.885\) 时，算法 \(A\) 的上界与基于对偶规划的下界在数学上严格相等，一致性表达式精确为 \(R - \overline{w}(R)\)。这一结论彻底终结了关于该区间是否存在更优随机算法的学术悬念。
- 高鲁棒约束下的超平滑增益：在 \(R \to e\) 的窄区间内，一致性收益由传统算法的 \(\Omega(\varepsilon)\) 显著提升到 \(\Omega(\varepsilon^{1/4})\)。这意味着即便只对最坏情况容忍极小放宽（如 \(1\%\) 的扰动 \(\varepsilon\)），一致性也能换取多达近十倍于以往的期望性能改进。
- 实际应用容错弹性极高：在英国马恩岛真实路网（5,340 节点）的增量中位数聚类实验中，即使预测设施数 \(\hat{k} = 2,500\) 出现成倍的严重偏差（真实 \(k\) 在 \([2500, 5000]\) 范围），算法 \(A\) 的经验近似比仍持续稳定在极低水平，完全避免了离散或半确定性算法因预测失真导致的性能断崖式恶化。
亮点与洞察¶
- 出价函数（Bidding Function）的全新分析范式：将传统离散递增出价序列转化为实数轴上的连续单调函数，利用归一化质量与功函数表达在线代价，是自双向无限出价提出以来最具普适性的理论工具。这一框架可直接推广至在线单向交易、线搜索以及带中断机制的实时任务调度等领域。
- 时滞微分方程与连续多项式生成：将鲁棒性约束转化为负半轴的微分时滞方程 \(R B'(t) = B(t+1)\)，并通过形式幂级数建立多项式解的全正性与收敛性证明，数学构造精巧纯粹，展现了深厚的分析数学功底。
- 由连续 LP 对偶诱导的解析紧致下界：避免了以往在离散出价转移概率矩阵上列出无法求解的非凸条件，通过将网格密化过程与特征多项式根的极限性态挂钩，直接由黎曼和推导出 Lambert W 闭式下界，方法极具穿透力。
局限与展望¶
- 小鲁棒性区间的极微小残余 Gap：在 \(e \le R < 2/\ln 2 \approx 2.885\) 的极狭窄区间内，算法 \(A\) 给出的解析上界 \(R/(2-y)\) 与基于网格计算求得的数值 LP 下界之间仍保留着微小的未闭合间隙，期待后续借助更高精度的计算机辅助证明或全变分分析彻底解决。
- 仅限一维单阈值标量预测：当前模型假设预言机只给出一个标量阈值预测 \(\hat{u}\)。在更现实的复杂业务场景中，预测往往带有置信度区间或多峰分布，拓展至多预测或置信度自适应的出价框架是值得探索的未来方向。
相关工作与启发¶
- vs. Angelopoulos & Simon (NeurIPS 2025)：此前 SOTA 提出的分段线性指数算法（Class \(\mathcal{D}\)）本质上是在离散几何序列上叠加小范围随机扰动，理论上下界相差较大，且在误差增加时退化剧烈；本文通过出价函数建立连续时滞方程，完全闭合了 \(R \ge 2.885\) 时的 Gap，并实现了指数级的平滑性提升。
- vs. Shin et al. (TALG 2025)：Shin 等人基于离散出价转移概率建立了按键问题（Button Problem）的非紧致下界；本文通过出价函数的网格离散化 LP 及其对偶理论，给出了更为简洁且严格紧致的闭式下界证明。
- vs. Chrobak et al. (Algorithmica 2008)：Chrobak 等人通过复杂的原始-对偶拟合确立了经典无预测随机出价的极限竞争比 \(e\)；本文不仅统一了经典 \(e\) 与确定性 4 的结论，更将其完备拓展至全区间的学习增强帕累托前沿。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次提出出价函数连续化框架与时滞微分方程构造，开辟了随机化在线出价分析的新路径。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖完备的严格理论证明、渐近展开分析、数值噪声仿真以及真实地理路网上的增量聚类实验。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严密流畅，从概念直觉、形式化表述到引理证明逻辑紧凑，结构清晰。
- 价值: ⭐⭐⭐⭐⭐ 闭合了学习增强在线算法领域的经典开问题，技术工具具备广泛的理论迁移价值。