# The Secretary Problem with a Stochastic Precursor

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 53 references that are in the map.
- First posted on arXiv 21 May 2026.

## Builds on (most cited first, 30 of 33)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Learning-Augmented Weighted Paging](https://mlsanity.com/paper/2011.09076/) (2020)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (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-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [Contract Scheduling with Distributional and Multiple Advice](https://mlsanity.com/paper/2404.12485/) (2024)
- [Online Ad Allocation with Predictions](https://mlsanity.com/paper/2302.01827/) (2023)
- [Predicting long-term publication impact through a combination of early citations and journal impact factor](https://mlsanity.com/paper/1909.08907/) (2019)
- [Recent Developments in Pandora's Box Problem: Variants and Applications](https://mlsanity.com/paper/2308.12242/) (2023)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [Fair Secretaries with Unfair Predictions](https://mlsanity.com/paper/2411.09854/) (2024)
- [Non-Clairvoyant Scheduling with Progress Bars](https://mlsanity.com/paper/2509.19662/) (2025)
- [The Secretary Problem with Independent Sampling](https://mlsanity.com/paper/2011.07869/) (2020)
- [Learning-Augmented Dynamic Submodular Maximization](https://mlsanity.com/paper/2311.13006/) (2023)
- [Prophets, Secretaries, and Maximizing the Probability of Choosing the Best](https://mlsanity.com/paper/1910.03798/) (2019)
- [The Secretary Problem with Predicted Additive Gap](https://mlsanity.com/paper/2409.20460/) (2024)
- [Robust Gittins for Stochastic Scheduling](https://mlsanity.com/paper/2504.10743/) (2025)
- [The Secretary Problem with Predictions and a Chosen Order](https://mlsanity.com/paper/2601.07482/) (2026)

## Abstract (arXiv)

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.