本文研究了多秘书问题，重点关注加性遗憾值，该值衡量最优离线奖励与在线策略奖励之间的差异。研究人员为某些分布建立了对数遗憾界，为其他分布建立了二次遗憾界。研究证明，对于两个分离均匀分布的混合，二次下界是必需的，这表明现有对有间隙分布的上界是严格的。证明利用了Bellman证书，这有助于构建明确的证书，并解释了支撑间隙为何会导致更大的遗憾值。 AI
排序理由 学术论文发表在arXiv上，详细介绍了理论计算机科学研究。[lever_c_demoted from research: ic=1 ai=0.1]
AI 生成摘要 · Google Gemini · 来自 2 个来源。 我们如何撰写摘要 →
arXiv:2607.02150v1 Announce Type: cross 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-de…
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…