# Uniformly bounded regret in the multi-secretary problem

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2017.

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

- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization](https://mlsanity.com/paper/2505.21692/) (2025)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model](https://mlsanity.com/paper/2402.13530/) (2024)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Cross-Epoch Adaptive Rollout Optimization for RL Post-Training](https://mlsanity.com/paper/2606.05606/) (2026)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning](https://mlsanity.com/paper/2302.00997/) (2023)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints](https://mlsanity.com/paper/2608.11383/) (2026)

## Abstract (arXiv)

In the secretary problem of Cayley (1875) and Moser (1956), n non-negative, independent, random variables with common distribution are sequentially presented to a decision maker who decides when to stop and collect the most recent realization. The goal is to maximize the expected value of the collected element. In the k-choice variant, the decision maker is allowed to make k ≤ n selections to maximize the expected total value of the selected elements. Assuming that the values are drawn from a known distribution with finite support, we prove that the best regret---the expected gap between the optimal online policy and its offline counterpart in which all n values are made visible at time 0---is uniformly bounded in the the number of candidates n and the budget k. Our proof is constructive: we develop an adaptive Budget-Ratio policy that achieves this performance. The policy selects or skips values depending on where the ratio of the residual budget to the remaining time stands relative to multiple thresholds that correspond to middle points of the distribution. We also prove that being adaptive is crucial: in general, the minimal regret among non-adaptive policies grows like the square root of n. The difference is the value of adaptiveness.