arXiv:2604.26349cs.DScs.LG2026-04

新算法让缓冲区管理在预测准时表现最优,不准时也能保持稳定性能。

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

  • 用输出结果反推预测误差,更真实评估预测质量
  • 预测错误时仍能保证约1.73的最坏情况性能
  • 适合需要兼顾预测精度与鲁棒性的在线系统

本文提出一种用于可抢占FIFO缓冲区管理的增强学习在线算法。在有限容量缓冲区中,数据包按到达顺序传输,算法可主动丢弃已缓存包以容纳后续到来。该算法同时实现1-一致性、η-平滑性与渐近√3-鲁棒性,其中η表示预测误差。当预测完美时,竞争比为1;预测误差增大时,性能平滑下降;即使预测极差,渐近竞争比仍保持√3,达到经典问题最优下界(Englert & Westermann, 2009)。核心创新在于引入基于输出的预测误差度量——因容量限制只有部分包被传输,故评估基于最优调度而非原始输入序列,避免人为惩罚。为保障鲁棒性,算法动态监控预测,触发最坏情况回退机制时执行缓冲清空策略,其竞争损失仅含一个随容量增长而消失的常数项。此外,本算法提供通用框架:替换回退模块为任意β-竞争算法,即可获得渐近β-鲁棒性。

原文摘要 · Abstract (English)

We present a learning-augmented online algorithm for the preemptive FIFO buffer management problem, where packets arrive online to a finite-capacity buffer, must be transmitted in FIFO order, and the algorithm may preemptively discard buffered packets to accommodate future arrivals. Our algorithm simultaneously achieves 1-consistency, η-smoothness, and asymptotic \sqrt{3}-robustness, where ηdenotes the prediction error. Specifically, it attains an optimal competitive ratio of 1 under perfect predictions, degrades smoothly as the prediction error increases, and maintains an asymptotic competitive ratio of \sqrt{3} under arbitrarily inaccurate predictions, matching the best-known worst-case guarantee for the classical online problem, established by Englert and Westermann in 2009 [Algorithmica 53(4): 523-548]. A key technical contribution of our work is the introduction of an \emph{output-based prediction error metric}. Because capacity constraints dictate that only a strictly bounded subset of arriving packets is ultimately transmitted, our metric assesses prediction quality over the resulting optimal schedules rather than the raw input sequences, avoiding artificial error penalties. To guarantee robustness, our algorithm dynamically monitors predictions and executes a \emph{buffer-clearing strategy} upon transitioning to a worst-case fallback mechanism. We prove that the competitive loss incurred by this clearing operation is bounded by an additive capacity constant that vanishes asymptotically. Finally, we show that our algorithm provides a generalized framework for learning-augmented buffer management: substituting the fallback module with any β-competitive online algorithm immediately yields asymptotic β-robustness.

在线算法缓冲区管理预测增强鲁棒性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。