标题： 合同的伪维数 显示英文标题

标题： The Pseudo-Dimension of Contracts

摘要： 算法合同设计研究的是委托人激励代理人代表自己努力工作的场景。 在本工作中，我们关注代理人的类型是从未知分布中抽取的设置，并将一个离线学习框架形式化，以从样本代理类型中学习接近最优的合同。 我们的分析中的核心工具是统计学习理论中的伪维数概念。 除了在建立样本复杂度上界中的作用外，伪维数衡量了合同类的内在复杂性，为合同设计中简单性和最优性之间的权衡提供了新的视角。 我们的主要结果在伪维数和表示误差（定义为委托人效用的损失）之间提供了基本最优的权衡，针对线性和有界合同。 利用这些权衡，我们推导出样本和时间高效的学习算法，并通过提供几乎匹配的样本复杂度下界来证明它们的近似最优性。 相反，对于无界合同，我们证明了一个不可能性结果，表明不存在这样的学习算法。 最后，我们在三个方面扩展了我们的技术。 首先，我们为组合动作模型提供了更精细的伪维数和样本复杂度保证，揭示了关键值的数量与样本复杂度之间的新联系。 其次，我们将我们的结果扩展到合同菜单，表明其伪维数随菜单大小线性增长。 第三，我们将我们的算法适应到在线学习设置，在此我们表明，多项式数量的类型样本足以学习接近最优的有界合同。 结合之前的工作，这在这个设置中建立了专家建议和置信区间反馈之间的形式化区别。 显示英文摘要

摘要： Algorithmic contract design studies scenarios where a principal incentivizes an agent to exert effort on her behalf. In this work, we focus on settings where the agent's type is drawn from an unknown distribution, and formalize an offline learning framework for learning near-optimal contracts from sample agent types. A central tool in our analysis is the notion of pseudo-dimension from statistical learning theory. Beyond its role in establishing upper bounds on the sample complexity, pseudo-dimension measures the intrinsic complexity of a class of contracts, offering a new perspective on the tradeoffs between simplicity and optimality in contract design. Our main results provide essentially optimal tradeoffs between pseudo-dimension and representation error (defined as the loss in principal's utility) with respect to linear and bounded contracts. Using these tradeoffs, we derive sample- and time-efficient learning algorithms, and demonstrate their near-optimality by providing almost matching lower bounds on the sample complexity. Conversely, for unbounded contracts, we prove an impossibility result showing that no learning algorithm exists. Finally, we extend our techniques in three important ways. First, we provide refined pseudo-dimension and sample complexity guarantees for the combinatorial actions model, revealing a novel connection between the number of critical values and sample complexity. Second, we extend our results to menus of contracts, showing that their pseudo-dimension scales linearly with the menu size. Third, we adapt our algorithms to the online learning setting, where we show that, a polynomial number of type samples suffice to learn near-optimal bounded contracts. Combined with prior work, this establishes a formal separation between expert advice and bandit feedback for this setting.