arXiv:2605.22653cs.DScs.LG2026-05

时间信号本身就能提升决策成功率,无需内容信息。

The Secretary Problem with a Stochastic Precursor

论文配图:The Secretary Problem with a Stochastic Precursor
图 1 · 摘自论文原文
  • 用随机提前信号的到达时间作为决策依据
  • 随机顺序下成功率从1/e提升至至少1/2,越晚信号效果越好
  • 适用于缺乏强保证的对抗性场景,为在线决策提供新思路

在学习增强型在线算法中,预测通常因其内容价值而被重视:如数值估计、解决方案或算法建议。本文表明,预测的价值也可源于其到来的时间本身。我们研究了基础秘书问题的扩展模型——带有随机前置信号的版本:该信号内容为空,但保证在最优物品之前到达,其到达时间随机分布。尽管信号不携带额外信息,但其时间特性本身改变了最优停止策略的结构。我们刻画了随机序和对抗序下的最优策略。在随机顺序下,单个均匀分布的前置信号即可使成功概率达到至少1/2,优于经典1/e基准;随着信号趋于更晚,成功率趋近于1。在传统模型无法提供强保证的对抗序下,足够集中的前置信号可恢复常数级别的成功概率。结果表明,这种异步时间信息是一种独特且强大的在线决策辅助形式,可能也适用于其他问题。

原文摘要 · Abstract (English)

In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least $\frac12$, improving on the classic $\frac1e$ benchmark. With increasingly late precursors, the success probability approaches $1$. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.

在线算法最优停止预测随机信号

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