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

arXiv: https://arxiv.org/abs/2511.04484 · HTML: https://mlsanity.com/paper/2511.04484/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 33 references that are in the map.
- First posted on arXiv 6 Nov 2025.

## Builds on (most cited first, 17 of 17)

- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Sample Complexity of Posted Pricing for a Single Item](https://mlsanity.com/paper/2406.00819/) (2024)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [Optimal Single-Choice Prophet Inequalities from Samples](https://mlsanity.com/paper/1911.07945/) (2019)
- [Learning Utilities and Equilibria in Non-Truthful Auctions](https://mlsanity.com/paper/2007.01722/) (2020)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Best of Both Worlds in Online Control: Competitive Ratio and Policy Regret](https://mlsanity.com/paper/2211.11219/) (2022)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Prophet Inequalities Require Only a Constant Number of Samples](https://mlsanity.com/paper/2311.09141/) (2023)
- [Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality](https://mlsanity.com/paper/2011.06516/) (2020)
- [Sequential Ski Rental Problem](https://mlsanity.com/paper/2104.06050/) (2021)
- [The Two-Sided Game of Googol and Sample-Based Prophet Inequalities](https://mlsanity.com/paper/1907.06001/) (2019)
- [Secretary Problems: The Power of a Single Sample](https://mlsanity.com/paper/2208.09159/) (2022)

## Built on by (most cited first, 1 of 1)

- [Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment](https://mlsanity.com/paper/2610.13571/) (2026)

## Abstract (arXiv)

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 Omega(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 tildeO(√T) regret. Furthermore, we establish a regret lower bound of Omega(√T) even in the i.i.d. model, which is nearly tight with respect to the number of rounds.