本文研究了多秘书问题中的加性遗憾，即期望的离线先知奖励与最佳在线策略奖励之间的差距。先前的研究已经为具有连通支持的有界密度分布建立了 $O(\log T)$ 的遗憾界限，而对于具有支持间隙的有界密度分布则得到了 $O((\log T)^2)$ 的上界。尚不清楚即使在单资源模型中，额外的对数因子是否是必要的。我们证明了这是必要的。
对于在临界容量下的两个分离均匀分布的混合，最优遗憾至少增长到 $O((\log T)^2)$ 的量级。因此，现有的 $O((\log T)^2)$ 上界在最简单的特化中是紧的，包括那些由具有连续奖励的网络收益管理模型所暗示的。
相同的框架还为那些在支持边缘附近密度消失的间隙分布提供了匹配的下界；这一伴随结果在附录中给出。证明使用了贝尔曼证书：即精确贝尔曼递归的松弛可行解。该框架将下界转化为显式的证书构造，并识别出为何支持间隙允许更大的遗憾。
博主点评： 本文在多秘书问题的研究中，利用贝尔曼证书提供了新的紧致下界，填补了理论上的空白，特别是在处理支持间隙时的遗憾问题上。这为后续的算法设计和理论研究提供了重要的指导意义，值得深入探讨。