这篇论文证明了多秘书问题中支撑有间隙时遗憾地的下界是(log T)^2，和之前的上界匹配，搞理论的值得一看。
该论文研究多秘书问题的加性遗憾，定义为离线先知期望奖励与最优在线策略奖励之差。此前工作对有界密度分布建立了O(log T)遗憾（连通支撑）和O((log T)^2)上界（支撑有间隙）。本文证明即使在单资源模型中，额外对数因子也是必要的：在临界容量处两个分离均匀分布的混合下，最优遗憾至少为(log T)^2量级。这一结果使得有界密度有间隙实例的O((log T)^2)上界在该最简单特例中是紧的。
Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates
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.