# Learning Optimal Contracts: How to Exploit Small Action Spaces

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 24 references that are in the map.
- First posted on arXiv 18 Sep 2023.

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

- [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)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Simple versus Optimal Contracts](https://mlsanity.com/paper/1808.03713/) (2018)
- [Contracts under Moral Hazard and Adverse Selection](https://mlsanity.com/paper/2010.06742/) (2020)
- [The Complexity of Contracts](https://mlsanity.com/paper/2002.12034/) (2020)
- [Multi-Agent Contracts](https://mlsanity.com/paper/2211.05434/) (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)
- [Approximate Optimality of Linear Contracts Under Uncertainty](https://mlsanity.com/paper/2211.06850/) (2022)
- [Multi-Agent Contract Design: How to Commission Multiple Agents with Individual Outcome](https://mlsanity.com/paper/2301.13654/) (2023)
- [The Power of Menus in Contract Design](https://mlsanity.com/paper/2306.12667/) (2023)
- [On Supermodular Contracts and Dense Subgraphs](https://mlsanity.com/paper/2308.07473/) (2023)

## Built on by (most cited first, 5 of 5)

- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)
- [Learning in Bayesian Stackelberg Games With Unknown Follower's Types](https://mlsanity.com/paper/2602.00771/) (2026)
- [Contracting With a Reinforcement Learning Agent by Playing Trick or Treat](https://mlsanity.com/paper/2410.13520/) (2024)
- [The Optimal Sample Complexity of Linear Contracts](https://mlsanity.com/paper/2601.01496/) (2026)

## Abstract (arXiv)

We study principal-agent problems in which a principal commits to an outcome-dependent payment scheme -- called contract -- in order to induce an agent to take a costly, unobservable action leading to favorable outcomes. We consider a generalization of the classical (single-round) version of the problem in which the principal interacts with the agent by committing to contracts over multiple rounds. The principal has no information about the agent, and they have to learn an optimal contract by only observing the outcome realized at each round. We focus on settings in which the size of the agent's action space is small. We design an algorithm that learns an approximately-optimal contract with high probability in a number of rounds polynomial in the size of the outcome space, when the number of actions is constant. Our algorithm solves an open problem by Zhu et al.[2022]. Moreover, it can also be employed to provide a tildeO(T4/5) regret bound in the related online learning setting in which the principal aims at maximizing their cumulative utility, thus considerably improving previously-known regret bounds.