09:02
官方账号arXiv cs.LG@Jiawei Zhang
推荐理由：这篇论文证明了多秘书问题中支撑有间隙时遗憾地的下界是(log T)^2，和之前的上界匹配，搞理论的值得一看。
概率论
共 1 条相关 AI 资讯
7月3日
09:02
该论文研究多秘书问题的加性遗憾，定义为离线先知期望奖励与最优在线策略奖励之差。此前工作对有界密度分布建立了O(log T)遗憾（连通支撑）和O((log T)^2)上界（支撑有间隙）。本文证明即使在单资源模型中，额外对数因子也是必要的：在临界容量处两个分离均匀分布的混合下，最优遗憾至少为(log T)^2量级。这一结果使得有界密度有间隙实例的O((log T)^2)上界在该最简单特例中是紧的。