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

arXiv: https://arxiv.org/abs/2505.17379 · HTML: https://mlsanity.com/paper/2505.17379/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 51 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 30 of 32)

- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Optimization of Scoring Rules](https://mlsanity.com/paper/2007.02905/) (2020)
- [Learning to Play Sequential Games versus Unknown Opponents](https://mlsanity.com/paper/2007.05271/) (2020)
- [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022)
- [Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion](https://mlsanity.com/paper/2303.01296/) (2023)
- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Learning Approximately Optimal Contracts](https://mlsanity.com/paper/1811.06736/) (2018)
- [Binary Scoring Rules that Incentivize Precision](https://mlsanity.com/paper/2002.10669/) (2020)
- [Bayesian Persuasion in Sequential Decision-Making](https://mlsanity.com/paper/2106.05137/) (2021)
- [Multi-Receiver Online Bayesian Persuasion](https://mlsanity.com/paper/2106.06480/) (2021)
- [Contracts with Private Cost per Unit-of-Effort](https://mlsanity.com/paper/2111.09179/) (2021)
- [Optimal Scoring Rules for Multi-dimensional Effort](https://mlsanity.com/paper/2211.03302/) (2022)
- [Sequential Information Design: Learning to Persuade in the Dark](https://mlsanity.com/paper/2209.03927/) (2022)
- [Contracts with Information Acquisition, via Scoring Rules](https://mlsanity.com/paper/2204.01773/) (2022)
- [Markov Persuasion Processes: Learning to Persuade from Scratch](https://mlsanity.com/paper/2402.03077/) (2024)
- [No-Regret Learning in Partially-Informed Auctions](https://mlsanity.com/paper/2202.10606/) (2022)
- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2309.02202/) (2023)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting](https://mlsanity.com/paper/2202.00605/) (2022)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Learning in Online Principal-Agent Interactions: The Power of Menus](https://mlsanity.com/paper/2312.09869/) (2023)

## Abstract (arXiv)

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.