arXiv cs.AI· Yuhe Sui, Yingzhi Tang·· 3 天前AI 评分26
认证决策而非每个评分：CAS 如何从少量评估中精确选出 Top-k
Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations
AI 导读
研究者提出 Certified Adaptive Selection（CAS），在剩余不确定性无法改变结果时即返回精确 top-k 集合，其停止检验比较最差可接受入选者与最优可接受落选者，对信息不相交的笛卡尔区间该单切检验充要。
正文 · AI 翻译
摘要：选择少数稳健的算法或调度方案，可能需要在许多不利场景下评估每个候选方案，尽管智能体只需识别出胜出者。预测器可以提示这些胜出者，但无法排除在未评估场景中出现意外。我们提出认证自适应选择（CAS），一旦剩余不确定性无法改变结果，就返回精确的 top-$k$ 集合。CAS 维护期望短缺（ES）的保证下界和上界，ES 即最差场景下的平均损失。其停止检验将最差可接受入选候选与最佳可接受排除候选进行比较；对于信息不相交的笛卡尔区间，这一单切检验是必要且充分的。预测有单独的作用：选择下一个要评估的结果，而绝不授权决策。对于具有精确单位成本查询的经验 ES，我们在多项式时间内计算出事后能够证明已实现决策的最少评估次数。我们的预测引导智能体 CAS-PG 对任何预测器都是精确的，包括对抗性预测器。在两个公开的算法选择矩阵上，CAS-PG 在重放的 3150 次查询中的 630 次和 2200 次查询中的 981 次之后认证出精确的前三名，分别是事后最小值的 $1.14$ 倍和 $1.18$ 倍。在没有历史结果的情况下，其仅用转录的变体需要最小值的 $1.28$ 倍和 $1.37$ 倍，优于所测试的非预测认证策略。另外，一种无预测的 CAS 策略在合成能源调度中避免了 $93.0\%$ 的精确追索求解。因此，一个证书支持多种采集策略，以及分别证明的风险/成本扩展：预测改变的是工作量，而不是有正当理由的选择。
| 主题： | 人工智能（cs.AI） |
| 引用为： | arXiv:2610.14996 [cs.AI] |
| （或 arXiv:2610.14996v1 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.14996 arXiv 颁发的 DOI 通过 DataCite（待注册） |
提交历史
来自：Yingzhi Tang [查看电子邮件]
[v1]
2026年10月10日星期六 15:23:10 UTC（98 KB）
来源：arXiv cs.AI · arxiv.org