首个兼顾鲁棒性与一致性的在线买价算法，实现最优权衡。
Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
- 设计新算法，同时优化最坏情况与预测一致性能。
- 首次在随机预测场景下实现平滑分析，保持理论保障。
- 适合需要稳定性能的金融交易或数据流决策场景。
一最大搜索是在线决策中的经典问题，交易者需在陆续披露的价格中选择一个不可撤销地接受，以最大化收益。该问题已在概率和最坏情况设定下被广泛研究，尤其通过竞争分析，并且最近在学习增强设定中受到关注，此时交易者可获得序列的预测。然而，现有方法要么缺乏平滑性，要么无法达到最优最坏情况保证：未能实现算法一致性与鲁棒性之间的最佳权衡。本文提出首个同时达成这两项目标的新算法。此外，我们利用所得平滑性，对包含价格观测与预测随机性的随机学习增强设定下的问题进行了分析。
原文摘要 · Abstract (English)
One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. The problem has been studied both in probabilistic and in worst-case settings, notably through competitive analysis, and more recently in learning-augmented settings in which the trader has access to a prediction on the sequence. However, existing approaches either lack smoothness, or do not achieve optimal worst-case guarantees: they do not attain the best possible trade-off between the consistency and the robustness of the algorithm. We close this gap by presenting the first algorithm that simultaneously achieves both of these important objectives. Furthermore, we show how to leverage the obtained smoothness to provide an analysis of one-max search in stochastic learning-augmented settings which capture randomness in both the observed prices and the prediction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。