Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret

ArXi:2511.04484v2 Announce Type: replace-cross 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.