{"ID":5675371,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-07T01:06:03.009715918Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.02150","arxiv_id":"2607.02150","title":"Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates","abstract":"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.","short_abstract":"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-...","url_abs":"https://arxiv.org/abs/2607.02150","url_pdf":"https://arxiv.org/pdf/2607.02150v1","authors":"[\"Jiawei Zhang\"]","published":"2026-07-02T13:26:29Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\"]","methods":"[\"Large Language Model\"]","has_code":false}