mlsanityData to 14 Oct 2026

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

arXiv 2505.17379 ↗First posted 23 May 2025cs.LG cs.AIcited by 0

Not on the map. Why?

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.

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

32 of 51 references.

References · 32

  1. 2014Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problemscited by 46
  2. 2013Learning Prices for Repeated Auctions with Strategic Buyerscited by 37
  3. 2022The Sample Complexity of Online Contract Designcited by 35
  4. 2017Learning to Bid Without Knowing your Valuecited by 34
  5. 2020Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctionscited by 34
  6. 2021Learning Equilibria in Matching Markets from Bandit Feedbackcited by 34
  7. 2016Towards Instance Optimal Bounds for Best Arm Identificationcited by 30
  8. 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
  9. 2020Optimization of Scoring Rulescited by 28
  10. 2020Learning to Play Sequential Games versus Unknown Opponentscited by 18
  11. 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
  12. 2023Optimal Rates and Efficient Algorithms for Online Bayesian Persuasioncited by 16
20 more
  1. 2023Principal-Agent Reward Shaping in MDPscited by 13
  2. 2024Incentivized Learning in Principal-Agent Bandit Gamescited by 13
  3. 2018Learning Approximately Optimal Contractscited by 12
  4. 2020Binary Scoring Rules that Incentivize Precisioncited by 12
  5. 2021Bayesian Persuasion in Sequential Decision-Makingcited by 12
  6. 2021Multi-Receiver Online Bayesian Persuasioncited by 12
  7. 2021Contracts with Private Cost per Unit-of-Effortcited by 12
  8. 2022Optimal Scoring Rules for Multi-dimensional Effortcited by 12
  9. 2022Sequential Information Design: Learning to Persuade in the Darkcited by 9
  10. 2022Contracts with Information Acquisition, via Scoring Rulescited by 8
  11. 2024Markov Persuasion Processes: Learning to Persuade from Scratchcited by 8
  12. 2022No-Regret Learning in Partially-Informed Auctionscited by 7
  13. 2023Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Modelcited by 7
  14. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  15. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  16. 2022Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reportingcited by 5
  17. 2024Contractual Reinforcement Learning: Pulling Arms with Invisible Handscited by 5
  18. 2023Learning in Online Principal-Agent Interactions: The Power of Menuscited by 4
  19. 2024Harnessing the Continuous Structure: Utilizing the First-order Approach in Online Contract Designcited by 4
  20. 2023Online Information Acquisition: Hiring Multiple Agentscited by 3

Built on by

Not cited yet.