Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition

Zichen Wang, Chuanhao Li, Huazheng Wang
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:63439-63466, 2025.

Abstract

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 $(\epsilon, \delta)$-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-wang25bc, title = {Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition}, author = {Wang, Zichen and Li, Chuanhao and Wang, Huazheng}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {63439--63466}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/wang25bc/wang25bc.pdf}, url = {https://proceedings.mlr.press/v267/wang25bc.html}, abstract = {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 $(\epsilon, \delta)$-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.} }
Endnote
%0 Conference Paper %T Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition %A Zichen Wang %A Chuanhao Li %A Huazheng Wang %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-wang25bc %I PMLR %P 63439--63466 %U https://proceedings.mlr.press/v267/wang25bc.html %V 267 %X 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 $(\epsilon, \delta)$-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.
APA
Wang, Z., Li, C. & Wang, H.. (2025). Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:63439-63466 Available from https://proceedings.mlr.press/v267/wang25bc.html.

Related Material