仅需少量样本即可学习最优线性合约，且理论上已达到极限效率。
The Optimal Sample Complexity of Linear Contracts
- 采用经验效用最大化算法，直接从数据中学习合约。
- 只需 $O(\ln(1/δ)/\varepsilon^2)$ 个样本即能逼近最优合约。
- 首次证明该样本复杂度在理论上最优，适用于机制设计研究者。
本文解决了离线设置下从数据中学习最优线性合约的难题：当代理人类型来自未知分布时，委托人目标是设计使自身期望效用最大化的合约。分析表明，简单的经验效用最大化（EUM）算法以至少 $1-δ$ 的概率，仅需 $O(\ln(1/δ) / \varepsilon^2)$ 个样本，即可实现对最优线性合约的 $\varepsilon$-近似。该结果优于先前已知界，并与 Dütting 等人（2025）给出的下界在常数因子上一致，从而证明其最优性。此外，本结果建立了更强的统一收敛性保证：所有线性合约的样本效用均以至少 $1-δ$ 的概率在 $\varepsilon$ 内逼近其真实期望，样本复杂度仍为 $O(\ln(1/δ) / \varepsilon^2)$。
原文摘要 · Abstract (English)
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/δ) / \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 an $\varepsilon$-approximation of its true expectation with probability at least $1-δ$, using the same optimal $O(\ln(1/δ) / \varepsilon^2)$ sample complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。