# The Sample Complexity of Online Contract Design

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 10 Nov 2022.

## Builds on (most cited first, 24 of 24)

- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Regret Minimization with Performative Feedback](https://mlsanity.com/paper/2202.00628/) (2022)
- [Simple versus Optimal Contracts](https://mlsanity.com/paper/1808.03713/) (2018)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses](https://mlsanity.com/paper/2107.05762/) (2021)
- [Contracts under Moral Hazard and Adverse Selection](https://mlsanity.com/paper/2010.06742/) (2020)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [The Complexity of Contracts](https://mlsanity.com/paper/2002.12034/) (2020)
- [Principal-Agent Hypothesis Testing](https://mlsanity.com/paper/2205.06812/) (2022)
- [Learning Approximately Optimal Contracts](https://mlsanity.com/paper/1811.06736/) (2018)
- [Bayesian Agency: Linear versus Tractable Contracts](https://mlsanity.com/paper/2106.00319/) (2021)
- [Combinatorial Contracts](https://mlsanity.com/paper/2109.14260/) (2021)
- [Contracts with Private Cost per Unit-of-Effort](https://mlsanity.com/paper/2111.09179/) (2021)
- [No-Regret Learning in Dynamic Stackelberg Games](https://mlsanity.com/paper/2202.04786/) (2022)
- [Designing Menus of Contracts Efficiently: The Power of Randomization](https://mlsanity.com/paper/2202.10966/) (2022)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Learning Strategy-Aware Linear Classifiers](https://mlsanity.com/paper/1911.04004/) (2019)

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

- [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)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [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)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (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)
- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Incentivizing High-Quality Content in Online Recommender Systems](https://mlsanity.com/paper/2306.07479/) (2023)
- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [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)
- [Learning in Online Principal-Agent Interactions: The Power of Menus](https://mlsanity.com/paper/2312.09869/) (2023)
- [Harnessing the Continuous Structure: Utilizing the First-order Approach in Online Contract Design](https://mlsanity.com/paper/2403.07143/) (2024)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Practical Performative Policy Learning with Strategic Agents](https://mlsanity.com/paper/2412.01344/) (2024)
- [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)
- [Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents](https://mlsanity.com/paper/2412.16318/) (2024)
- [Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals](https://mlsanity.com/paper/2505.23124/) (2025)
- [Learning to Play Multi-Follower Bayesian Stackelberg Games](https://mlsanity.com/paper/2510.01387/) (2025)
- [Learning in Bayesian Stackelberg Games With Unknown Follower's Types](https://mlsanity.com/paper/2602.00771/) (2026)
- [Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners](https://mlsanity.com/paper/2502.08597/) (2025)
- [Steering No-Regret Agents in MFGs under Model Uncertainty](https://mlsanity.com/paper/2503.09309/) (2025)
- [Learning Under Moral Hazard with Instrumental Regression and Generalized Method of Moments](https://mlsanity.com/paper/2405.20642/) (2024)

## Abstract (arXiv)

We study the hidden-action principal-agent problem in an online setting. In each round, the principal posts a contract that specifies the payment to the agent based on each outcome. The agent then makes a strategic choice of action that maximizes her own utility, but the action is not directly observable by the principal. The principal observes the outcome and receives utility from the agent's choice of action. Based on past observations, the principal dynamically adjusts the contracts with the goal of maximizing her utility. We introduce an online learning algorithm and provide an upper bound on its Stackelberg regret. We show that when the contract space is [0,1]m, the Stackelberg regret is upper bounded by widetilde O(√m · T1-1/(2m+1)), and lower bounded by Omega(T1-1/(m+2)), where widetilde O omits logarithmic factors. This result shows that exponential-in-m samples are sufficient and necessary to learn a near-optimal contract, resolving an open problem on the hardness of online contract design. Moreover, when contracts are restricted to some subset F subset [0,1]m, we define an intrinsic dimension of F that depends on the covering number of the spherical code in the space and bound the regret in terms of this intrinsic dimension. When F is the family of linear contracts, we show that the Stackelberg regret grows exactly as Theta(T2/3). The contract design problem is challenging because the utility function is discontinuous. Bounding the discretization error in this setting has been an open problem. In this paper, we identify a limited set of directions in which the utility function is continuous, allowing us to design a new discretization method and bound its error. This approach enables the first upper bound with no restrictions on the contract and action space.