Search papers, labs, and topics across Lattice.
This paper establishes that the logarithmic factor in the regret bounds for the multi-secretary problem is indeed necessary, proving that optimal regret grows at least on the order of \((\log T)^2\) for a mixture of two separated uniform distributions at critical capacity. The results confirm that existing upper bounds for bounded-density gapped instances are tight, particularly in the context of network revenue management models with continuous rewards. The authors employ Bellman certificates to derive these lower bounds, providing insights into how support gaps contribute to increased regret.
The logarithmic factor in multi-secretary problem regret bounds is not just a technicality; it鈥檚 essential, revealing that optimal regret can grow quadratically under certain conditions.
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.
