在重复最优停止问题中,同时保证每轮表现和总体低损失,提出新算法实现高概率保障与近最优后悔值。
Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
- 设计新框架,在完全反馈下高概率满足每轮性能基准
- 在独立同分布模型中实现约√T的后悔值,接近理论下界
- 适用于预言家不等式、秘书问题等经典场景,适合在线决策研究者
我们研究重复最优停止问题:一个未知分布的最优停止实例在 T 轮中反复出现。目标是同时实现相对于给定基线的强单轮性能保证和全局亚线性后悔。主要贡献是理论刻画这两项目标是否兼容。首先,在标准半监督反馈下,维持单轮保证导致后悔为 Ω(T / log T)。其次,即使在完全反馈下,要求每轮几乎必然满足单轮保证也与亚线性后悔不兼容。第三,在完全反馈下,提出一种通用算法框架,可高概率同时实现子线性后悔和单轮保证。该框架适用于经典问题,包括预言家不等式、秘书问题及其对抗、随机、i.i.d. 输入模型的变体。例如,在重复预言家不等式问题中,该方法在每轮以高概率保证期望收益不低于经典单样本算法(1/2 竞争比),同时实现 Õ(√T) 后悔。此外,我们在 i.i.d. 模型中建立了 Ω(√T) 的后悔下界,与轮数的理论上限近乎紧致。
原文摘要 · Abstract (English)
We study the repeated optimal stopping problem, in which the same optimal stopping instance with an unknown distribution is solved repeatedly over $T$ rounds. We aim to simultaneously achieve strong per-round performance guarantees relative to a given baseline and sublinear regret across all rounds. Our primary contribution is a comprehensive theoretical characterization of whether and when these two objectives are compatible. First, under standard semi-bandit feedback, we prove that maintaining the per-round guarantee forces regret of $Ω(T / \log T)$. Second, even under full feedback, we show that requiring almost-sure satisfaction of the per-round guarantee in every round is incompatible with sublinear regret. Third, under full feedback, we propose a general algorithmic framework that achieves both sublinear regret and the per-round guarantee with high probability. Our framework applies to canonical problems, including the prophet inequality, the secretary problem, and their variants under adversarial, random, and i.i.d. input models. For example, in the repeated prophet inequality problem, our method guarantees that, with high probability in each round, its expected reward is at least that of the classical single-sample algorithm, which achieves a $1/2$ competitive ratio, while simultaneously ensuring $\tilde{O}(\sqrt{T})$ regret. Furthermore, we establish a regret lower bound of $Ω(\sqrt{T})$ even in the i.i.d. model, which is nearly tight with respect to the number of rounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。