# Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2014.

## Built on by (most cited first, 30 of 46)

- [Can large language models explore in-context?](https://mlsanity.com/paper/2403.15371/) (2024)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Principal-Agent Hypothesis Testing](https://mlsanity.com/paper/2205.06812/) (2022)
- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)
- [Deep Contract Design via Discontinuous Networks](https://mlsanity.com/paper/2307.02318/) (2023)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Delegated Classification](https://mlsanity.com/paper/2306.11475/) (2023)
- [Incentivizing Quality Text Generation via Statistical Contracts](https://mlsanity.com/paper/2406.11118/) (2024)
- [Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts](https://mlsanity.com/paper/2407.18074/) (2024)
- [Online Learning in a Creator Economy](https://mlsanity.com/paper/2305.11381/) (2023)
- [Delegating Data Collection in Decentralized Machine Learning](https://mlsanity.com/paper/2309.01837/) (2023)
- [Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents](https://mlsanity.com/paper/2304.07407/) (2023)
- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information](https://mlsanity.com/paper/2502.00204/) (2025)
- [Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards](https://mlsanity.com/paper/2308.06717/) (2023)
- [Learning Optimal Contracts: How to Exploit Small Action Spaces](https://mlsanity.com/paper/2309.09801/) (2023)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability](https://mlsanity.com/paper/2402.17108/) (2024)
- [Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts](https://mlsanity.com/paper/2307.00836/) (2023)
- [The Pseudo-Dimension of Contracts](https://mlsanity.com/paper/2501.14474/) (2025)
- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)
- [Goal Recognition Design for General Behavioral Agents using Machine Learning](https://mlsanity.com/paper/2404.03054/) (2024)
- [Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents](https://mlsanity.com/paper/2412.16318/) (2024)

## Abstract (arXiv)

Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the task's requester, and may be adjusted based on the quality of the completed work, for example, through the use of "bonus" payments. In this paper, we study the requester's problem of dynamically adjusting quality-contingent payments for tasks. We consider a multi-round version of the well-known principal-agent model, whereby in each round a worker makes a strategic choice of the effort level which is not directly observable by the requester. In particular, our formulation significantly generalizes the budget-free online task pricing problems studied in prior work. We treat this problem as a multi-armed bandit problem, with each "arm" representing a potential contract. To cope with the large (and in fact, infinite) number of arms, we propose a new algorithm, AgnosticZooming, which discretizes the contract space into a finite number of regions, effectively treating each region as a single arm. This discretization is adaptively refined, so that more promising regions of the contract space are eventually discretized more finely. We analyze this algorithm, showing that it achieves regret sublinear in the time horizon and substantially improves over non-adaptive discretization (which is the only competing approach in the literature). Our results advance the state of art on several different topics: the theory of crowdsourcing markets, principal-agent problems, multi-armed bandits, and dynamic pricing.