The Optimal Sample Complexity of Linear Contracts

Mikael Møller Høgsgaard

Introduction

In algorithmic contract theory, determining the exact amount of data needed to design a near-optimal linear contract is a fundamental challenge. This paper settles this problem in the offline learning setting, where agent types are drawn from an unknown distribution and the principal's goal is to design a contract that maximizes their expected utility.

The authors prove that the simple Empirical Utility Maximization (EUM) algorithm is statistically optimal. It requires only $O(\ln(1/\delta) / \varepsilon^2)$ samples to yield an $\varepsilon$-approximation of the optimal linear contract with probability at least $1-\delta$. This result matches theoretical lower bounds up to constant factors, proving its optimality, and crucially remains independent of the number of possible actions or outcomes.

The Principal-Agent Problem in Offline Learning

In the classic "Principal-Agent" problem, a principal (such as a music platform) designs a contract (like a royalty agreement) to motivate an agent (a musician) to take actions that benefit the principal. The core challenge is information asymmetry: the agent’s "type"—their specific costs and the likelihood that their efforts will produce certain outcomes—is private and unknown to the principal.

In the offline learning setting, the principal has access to a finite dataset of agent types, perhaps gathered from a pilot study or historical data. The objective is to use this sample to select a contract that maximizes the principal's expected utility across the entire population.

Previous research established upper bounds on the required sample complexity, but these bounds were either "loose" (containing extra logarithmic factors) or dependent on the number of actions $n$ available to the agent. If $n$ is very large, these previous bounds become impractical. This paper successfully identifies the absolute minimum amount of data needed to guarantee a near-optimal contract.

Methodology and Technical Innovations

The authors focus specifically on linear contracts, where the principal and agent share the total reward based on a fixed percentage $\alpha$. Because this is a theoretical work in mathematical statistics and algorithmic game theory, it relies on mathematical proofs that hold for any distribution of agent types rather than empirical datasets.

The core of the paper's approach is proving uniform convergence. This requires demonstrating that for every possible linear contract, the utility measured on the sample data closely mirrors the true expected utility across the entire population.

To achieve this, the authors depart from standard combinatorial tools like the "pseudo-dimension" used in prior literature. Instead, they employ a "first-principles" chaining argument based on Rademacher complexity.

The Monotonicity Insight

The key technical innovation lies in exploiting a specific structural property of linear contracts. The principal’s utility function can be highly discontinuous—agents might abruptly switch actions as the contract parameter $\alpha$ changes. However, the expected reward of a linear contract is always non-decreasing. As the agent is given a larger share of the reward (higher $\alpha$), they are incentivized to exert more effort, generally increasing the expected total reward.

By building a "net" (a discretization) over the contract space that respects this monotonicity, the authors construct a highly efficient "cover" of the contract space, allowing them to prove much tighter bounds than general-purpose learning theory tools would permit.

Key Results

  • Optimal Bound: The paper proves a sample complexity of $O(\ln(1/\delta) / \varepsilon^2)$ to achieve an $\varepsilon$-approximation of the optimal contract with probability $1-\delta$. This matches the known lower bound, proving the result is "tight."
  • Uniform Convergence: The authors establish that $s \geq 3456 \ln(4/\delta)/\varepsilon^2$ samples are sufficient to ensure that the empirical utility of all linear contracts is within $\varepsilon$ of their true expectation.
  • Action-Space Independence: The required sample size does not depend on the number of actions ($n$) an agent can choose from. Whether an agent has two choices or two million, the sample complexity for learning a linear contract remains identical.
  • Algorithmic Efficiency: The optimal contract can be found by querying an empirical utility oracle only $O(1/\varepsilon)$ times. This validates that Empirical Utility Maximization (EUM)—picking the contract that performed best on the sample data—is not only the mathematically optimal way to learn, but is also computationally practical.

Limitations and Future Work

While the paper resolves a major theoretical question, the authors note a few limitations and avenues for future research:

  • Unoptimized Constants: The authors did not attempt to optimize the constant factors in their bounds (e.g., the 3456 in the uniform convergence theorem). While the asymptotic scaling is optimal, the specific constants are likely much higher than what is strictly necessary in practice.
  • Beyond Linear Contracts: The proof relies heavily on the specific monotonic structure of linear contracts. A major open question is whether similar "direct-cover" arguments can be developed for more complex, non-linear contract classes.
  • The "Sample Gap" Question: For more complex contract classes, it remains unknown if there is a genuine gap between the data needed for "uniform convergence" (knowing the value of all contracts) versus simply "learning the best" contract. This paper demonstrates that no such gap exists in the linear case.

Summary updated

Abstract

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-\delta$, using just $O(\ln(1/\delta) / \varepsilon^2)$ samples. This result improves upon previously known bounds and matches a lower bound from (Dütting 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 a $\varepsilon$-approximation of its true expectation with probability at least $1-\delta$, using the same optimal $O(\ln(1/\delta) / \varepsilon^2)$ sample complexity.
BibTeX
@inproceedings{hgsgaard2026optimal,
  author = {Mikael Møller Høgsgaard},
  title = {{The Optimal Sample Complexity of Linear Contracts}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=ry5HitnXzc},
}
Figure