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 $O((\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.
Blogger's Review: This paper provides new tight lower bounds in the study of the multi-secretary problem using Bellman certificates, addressing a theoretical gap, especially regarding regret issues with support gaps. It offers important guidance for subsequent algorithm design and theoretical research, warranting further exploration.