# Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 2 Jul 2026.

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

- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Resource Allocation with Stochastic Resource Consumption](https://mlsanity.com/paper/2012.07933/) (2020)
- [Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations](https://mlsanity.com/paper/1912.08917/) (2019)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Greedy Algorithm for Multiway Matching with Bounded Regret](https://mlsanity.com/paper/2112.04622/) (2021)
- [Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards](https://mlsanity.com/paper/1809.02016/) (2018)
- [Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack](https://mlsanity.com/paper/2107.02058/) (2021)
- [Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances](https://mlsanity.com/paper/2205.09078/) (2022)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming](https://mlsanity.com/paper/2501.01716/) (2025)
- [Overbooking with bounded loss](https://mlsanity.com/paper/2204.11148/) (2022)
- [Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities](https://mlsanity.com/paper/2205.00588/) (2022)

## Abstract (arXiv)

This paper studies additive regret in the multi-secretary problem, defined as the gap between the expected offline prophet reward and the reward of the best online policy. Prior work established (O(log T)) regret for bounded-density distributions with connected support and (O((log T)2)) upper bounds for bounded-density distributions with support gaps. It was unknown whether the extra logarithmic factor is necessary even in the one-resource model. We prove that it is necessary. For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of ((log T)2). Thus the existing (O((log T)2)) upper bounds for bounded-density gapped instances, including those implied by network revenue management models with continuous rewards, are tight in this simplest specialization. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges; this companion result is given in the appendix. The proofs use Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion. This framework converts lower bounds into explicit certificate constructions and identifies why support gaps permit larger regret.