在有限反馈下高效选择低代价方案,确保成功率达标。
Efficient Online Conformal Selection with Limited Feedback

- 用边界动作替代投影更新,保持算法有效性
- 对独立同分布输入,效率遗憾为次线性
- 适合资源受限的在线决策场景
我们研究约束选择问题,即代理需选出一个低成本选项子集,以保证在预设目标率ϕ下至少识别出一个成功项。传统在线共形预测关注观测序列的保真性,但如何在有限反馈下最小化资源消耗仍具挑战。本文考虑高度受限的“赌博机”反馈:仅能获得所选子集的反馈,无法获知未选选项的真实标签或结果。我们证明,当自适应共形推断(ACI)更新规则作用于适当控制参数或对偶变量,并结合显式边界动作时,该方法兼具对抗有效性(对任意输入序列平均满足成功率目标,包括分布偏移情形)与随机高效性(对独立同分布输入,相对于最优随机基准实现次线性效率遗憾)。核心思想是避免约束赌博机中常见的投影更新——投影会破坏ACI有效性的精确望远镜恒等式,而边界动作通过实际决策稳定非投影更新。我们在统一算法框架与基于李雅普诺夫的分析下,于典型模型中建立这些保证。相比先前工作,本方法处理更一般设定且所需反馈显著减少,为有限反馈下的高效在线学习与分布无关不确定性量化之间建立了新理论桥梁。
原文摘要 · Abstract (English)
We address the problem of conformal selection, where an agent must select a low-cost subset of options to ensure that at least one "success" is identified at a pre-specified target rate $ϕ$. While traditional online conformal prediction focuses on maintaining validity for the observed sequence, minimizing the resource cost (efficiency) of such selections, especially under limited feedback, remains a significant challenge. In this work, we consider highly restricted "bandit" feedback, where the agent only observes feedback about the subset it selected, and not the true label, point, or outcomes of unchosen options. We demonstrate that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable and paired with explicit boundary actions, is both adversarially valid, ensuring the success target is met on average for any input sequence (and hence under distribution shifts), and stochastically efficient, achieving sublinear efficiency regret for i.i.d. inputs against an optimal stochastic benchmark. The key algorithmic idea is to avoid the projected updates standard in constrained bandits: projections break the exact telescoping identity behind ACI validity, whereas boundary actions stabilize the unprojected update through actual decisions. We show these guarantees under canonical models capturing bandit feedback via a unified algorithmic technique and Lyapunov-based analysis. Our approach handles more general settings than prior work, while requiring significantly less feedback, and provides a new theoretical bridge between efficient online learning with limited feedback and distribution-free uncertainty quantification.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。