New paper settles optimal sample complexity for learning linear contracts

Researchers have long sought efficient algorithms for learning optimal contracts from data—a core problem in game theory with direct applications in AI-driven delegation and incentive design. Mikael Møller Høgsgaard's paper, "The Optimal Sample Complexity of Linear Contracts," settles this question in the offline setting where agent types are drawn from an unknown distribution. The principal's goal is to design a linear contract that maximizes expected utility. Høgsgaard proves that the simple Empirical Utility Maximization (EUM) algorithm yields an ε-approximation of the optimal linear contract with probability at least 1−δ, using only O(ln(1/δ)/ε²) samples.

This result improves upon previously known bounds and matches a lower bound from Dütting et al. 2025 up to constant factors, proving its optimality. Furthermore, the paper establishes the stronger guarantee of uniform convergence: the empirical utility of every linear contract is an ε-approximation of its true expectation with the same optimal sample complexity. The work spans computer science and game theory (cs.GT), artificial intelligence (cs.AI), and machine learning (cs.LG), offering a foundational benchmark for any system that must learn incentive structures from limited data—from automated negotiation agents to decentralized finance protocols.