The Optimal Sample Complexity of Linear Contracts

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.

How do you maximize revenue by compensating workers when you don't know exactly what motivates them? This is a classic economic challenge. The goal is to find a "sweet spot"—a payment rule that motivates the worker while maximizing the revenue of the business. A popular approach for such payment schemes is a linear contract, where the worker simply gets a fixed percentage of the value they generate, for instance, used in sales commissions, music royalties, or gig economy platforms. But how much historical data on the worker's motivation do we need to figure out the percentage to offer such that the business revenue is maximized? Our research shows that a simple data-driven approach, picking the percentage that performed best in past samples, is optimal.