提出高效算法，自动识别在线信息获取中的最优评分规则。
Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition
- 设计两种算法，分别适配固定置信度与固定预算场景。
- 理论证明算法样本复杂度高效，可精准识别(ε, δ)规则。
- 适用于需要可靠激励机制的在线决策系统研究者。
我们研究在主从框架下，针对在线信息获取问题识别最优评分规则。从主方视角出发，通过与代理方交互来确定期望的评分规则。为此，我们提出两种算法：OIAFC 和 OIAFB，分别适用于固定置信度和固定预算设置。理论分析表明，OIAFC 可以以高效的实例相关或实例无关样本复杂度提取出所需的 (ε, δ)-评分规则。同时分析显示，OIAFB 在实例无关性能上达到与 OIAFC 相同的下界，且两种算法在固定置信度与固定预算设置下的复杂度一致。
原文摘要 · Abstract (English)
We investigate the problem of identifying the optimal scoring rule within the principal-agent framework for online information acquisition problem. We focus on the principal's perspective, seeking to determine the desired scoring rule through interactions with the agent. To address this challenge, we propose two algorithms: OIAFC and OIAFB, tailored for fixed confidence and fixed budget settings, respectively. Our theoretical analysis demonstrates that OIAFC can extract the desired $(ε, δ)$-scoring rule with a efficient instance-dependent sample complexity or an instance-independent sample complexity. Our analysis also shows that OIAFB matches the instance-independent performance bound of OIAFC, while both algorithms share the same complexity across fixed confidence and fixed budget settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。