arXiv cs.AI· Nicholas Teh, Paul W. Goldberg·· 13 小时前AI 评分18
从成员查询中学习 Stakeholder 违规最少的抽签方案
Learning Lotteries with Minimal Stakeholder Violations from Membership Queries
AI 导读
研究将请求随机分配给 m 个候选系统版本的抽签问题：每个 stakeholder 只在期望性能满足其未知半空间标准时接受该抽签，目标是最小化拒绝的 stakeholder 数量。
正文 · AI 翻译
摘要：AI 开发者通常拥有系统的多个候选版本，并可以部署它们的混合体，将每个请求发送给随机选择的版本，如同 A/B 测试。每个利益相关方（例如安全团队、监管机构或拥有私有测试数据的客户）恰好在其期望性能（例如有害回复率）满足该利益相关方自身标准时接受某个混合体，而开发者只能通过询问所提议的混合体是否可接受来了解该标准。我们将此建模为为 $n$ 个代理在 $m$ 个备选方案中选择一个彩票，每个代理恰好接受未知半空间中的彩票，并回答此类二元成员查询。虽然 Choo 等人（ICML 2026）寻求一种每个代理都接受的彩票，但当安全性与有用性要求冲突时，可能不存在这样的彩票，因此我们最小化拒绝代理的数量。我们证明，即使所有半空间已知且所有效用为 $0$ 或 $1$，该问题也是 APX 难的。然后我们给出精确算法：当 $m$ 为常数时在多项式时间内运行；当对于常数 $\eta$，某个最优彩票没有接受代理位于其阈值 $\eta$ 范围内时，在准多项式时间内运行。当只能查询部分代理时，在代理的均匀样本上进行优化可为整个群体提供加性和相对保证，样本量不依赖于 $n$，并且线性规划为任意 $m$ 提供了多项式时间方法。另一方面，对于 $m\ge 3$，仅查询 $K$ 个不同代理的确定性算法无法保证少于 $n-K$ 次额外拒绝，且这是可实现的；换言之，对于未询问的代理，它无法保证任何结果。小型合成实验表明，我们的最坏情况界限在随机实例上是保守的。
| 评论： | 31 页，论文完整版发表于 NeurIPS 2026 |
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI） |
| 引用为： | arXiv:2610.37828 [cs.LG] |
| （或 arXiv:2610.37828v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.37828 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Paul Goldberg [查看电子邮件]
[v1]
2026 年 10 月 27 日星期二 18:40:50 UTC（52 KB）
来源：arXiv cs.AI · arxiv.org