# Are Bounded Contracts Learnable and Approximately Optimal?

arXiv: https://arxiv.org/abs/2402.14486 · HTML: https://mlsanity.com/paper/2402.14486/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 22 Feb 2024.

## Builds on (most cited first, 18 of 18)

- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Simple versus Optimal Contracts](https://mlsanity.com/paper/1808.03713/) (2018)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [Contracts under Moral Hazard and Adverse Selection](https://mlsanity.com/paper/2010.06742/) (2020)
- [The Complexity of Contracts](https://mlsanity.com/paper/2002.12034/) (2020)
- [Multi-Agent Contracts](https://mlsanity.com/paper/2211.05434/) (2022)
- [Incentivizing High Quality Crowdwork](https://mlsanity.com/paper/1503.05897/) (2015)
- [Bayesian Agency: Linear versus Tractable Contracts](https://mlsanity.com/paper/2106.00319/) (2021)
- [Contracts with Private Cost per Unit-of-Effort](https://mlsanity.com/paper/2111.09179/) (2021)
- [Approximate Optimality of Linear Contracts Under Uncertainty](https://mlsanity.com/paper/2211.06850/) (2022)
- [On Supermodular Contracts and Dense Subgraphs](https://mlsanity.com/paper/2308.07473/) (2023)
- [Learning Optimal Contracts: How to Exploit Small Action Spaces](https://mlsanity.com/paper/2309.09801/) (2023)
- [Learning Reserve Prices in Second-Price Auctions](https://mlsanity.com/paper/1912.10069/) (2019)
- [On the (In)approximability of Combinatorial Contracts](https://mlsanity.com/paper/2311.18425/) (2023)
- [Strong Revenue (Non-)Monotonicity of Single-parameter Auctions](https://mlsanity.com/paper/2205.08062/) (2022)
- [Online Information Acquisition: Hiring Multiple Agents](https://mlsanity.com/paper/2307.06210/) (2023)

## Built on by (most cited first, 6 of 6)

- [Harnessing the Continuous Structure: Utilizing the First-order Approach in Online Contract Design](https://mlsanity.com/paper/2403.07143/) (2024)
- [The Pseudo-Dimension of Contracts](https://mlsanity.com/paper/2501.14474/) (2025)
- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)
- [Contracting With a Reinforcement Learning Agent by Playing Trick or Treat](https://mlsanity.com/paper/2410.13520/) (2024)
- [The Optimal Sample Complexity of Linear Contracts](https://mlsanity.com/paper/2601.01496/) (2026)
- [Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts](https://mlsanity.com/paper/2609.20353/) (2026)

## Abstract (arXiv)

This paper considers the hidden-action model of the principal-agent problem, in which a principal incentivizes an agent to work on a project using a contract. We investigate whether contracts with bounded payments are learnable and approximately optimal. Our main results are two learning algorithms that can find a nearly optimal bounded contract using a polynomial number of queries, under two standard assumptions in the literature: a costlier action for the agent leads to a better outcome distribution for the principal, and the agent's cost/effort has diminishing returns. Our polynomial query complexity upper bound shows that standard assumptions are sufficient for achieving an exponential improvement upon the known lower bound for general instances. Unlike the existing algorithms, which relied on discretizing the contract space, our algorithms directly learn the underlying outcome distributions. As for the approximate optimality of bounded contracts, we find that they could be far from optimal in terms of multiplicative or additive approximation, but satisfy a notion of mixed approximation.