# Competitive Analysis with a Sample and the Secretary Problem

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2019.

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

- [Fair Secretaries with Unfair Predictions](https://mlsanity.com/paper/2411.09854/) (2024)
- [Online Adversarial Attacks](https://mlsanity.com/paper/2103.02014/) (2021)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [The Secretary Problem with Predictions and a Chosen Order](https://mlsanity.com/paper/2601.07482/) (2026)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [Learning in Prophet Inequalities with Noisy Observations](https://mlsanity.com/paper/2604.01789/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Adversarial Online Classification with a Preview](https://mlsanity.com/paper/2608.29503/) (2026)

## Abstract (arXiv)

We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal both in the worst-cast and random-order models.