# The Optimal Sample Complexity of Linear Contracts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 40 references that are in the map.
- First posted on arXiv 4 Jan 2026.

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

- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [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)
- [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)
- [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)
- [Designing Menus of Contracts Efficiently: The Power of Randomization](https://mlsanity.com/paper/2202.10966/) (2022)
- [Algorithmic Contract Theory: A Survey](https://mlsanity.com/paper/2412.16384/) (2024)
- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [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)
- [Learning Optimal Contracts: How to Exploit Small Action Spaces](https://mlsanity.com/paper/2309.09801/) (2023)
- [Multi-Agent Combinatorial Contracts](https://mlsanity.com/paper/2405.08260/) (2024)
- [Optimal Common Contract with Heterogeneous Agents](https://mlsanity.com/paper/1911.04146/) (2019)
- [On the (In)approximability of Combinatorial Contracts](https://mlsanity.com/paper/2311.18425/) (2023)
- [The Pseudo-Dimension of Contracts](https://mlsanity.com/paper/2501.14474/) (2025)
- [Combinatorial Contracts Beyond Gross Substitutes](https://mlsanity.com/paper/2309.10766/) (2023)
- [A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design](https://mlsanity.com/paper/2404.03476/) (2024)

## Abstract (arXiv)

In this paper, we settle the problem of learning optimal linear contracts from data in the offline setting, where agent types are drawn from an unknown distribution and the principal's goal is to design a contract that maximizes her expected utility. Specifically, our analysis shows that the simple Empirical Utility Maximization (EUM) algorithm yields an varepsilon-approximation of the optimal linear contract with probability at least 1-δ, using just O(ln(1/δ) / varepsilon2) samples. This result improves upon previously known bounds and matches a lower bound from D"utting et al. 2025 up to constant factors, thereby proving its optimality. Furthermore, our result establishes the stronger guarantee of uniform convergence: the empirical utility of every linear contract is an varepsilon-approximation of its true expectation with probability at least 1-δ, using the same optimal O(ln(1/δ) / varepsilon2) sample complexity.