# Contracting with a Learning Agent

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 61 references that are in the map.
- First posted on arXiv 29 Jan 2024.

## Builds on (most cited first, 30 of 37)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [How Do Classifiers Induce Agents To Invest Effort Strategically?](https://mlsanity.com/paper/1807.05307/) (2018)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Strategizing against Learners in Bayesian Games](https://mlsanity.com/paper/2205.08562/) (2022)
- [Simple versus Optimal Contracts](https://mlsanity.com/paper/1808.03713/) (2018)
- [Optimization of Scoring Rules](https://mlsanity.com/paper/2007.02905/) (2020)
- [Econometrics for Learning Agents](https://mlsanity.com/paper/1505.00720/) (2015)
- [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015)
- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [Contracts under Moral Hazard and Adverse Selection](https://mlsanity.com/paper/2010.06742/) (2020)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Selling to Multiple No-Regret Buyers](https://mlsanity.com/paper/2307.04175/) (2023)
- [Mechanisms for a No-Regret Agent: Beyond the Common Prior](https://mlsanity.com/paper/2009.05518/) (2020)
- [How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents](https://mlsanity.com/paper/2112.07640/) (2021)
- [The Complexity of Contracts](https://mlsanity.com/paper/2002.12034/) (2020)
- [Bid Prediction in Repeated Auctions with Learning](https://mlsanity.com/paper/2007.13193/) (2020)
- [Multi-Agent Contracts](https://mlsanity.com/paper/2211.05434/) (2022)
- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Learning Approximately Optimal Contracts](https://mlsanity.com/paper/1811.06736/) (2018)
- [Bayesian Agency: Linear versus Tractable Contracts](https://mlsanity.com/paper/2106.00319/) (2021)
- [Combinatorial Contracts](https://mlsanity.com/paper/2109.14260/) (2021)
- [Learning and Efficiency in Games with Dynamic Population](https://mlsanity.com/paper/1505.00391/) (2015)
- [Correlated and Coarse equilibria of Single-item auctions](https://mlsanity.com/paper/1601.07702/) (2016)
- [Contracts with Information Acquisition, via Scoring Rules](https://mlsanity.com/paper/2204.01773/) (2022)

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

- [Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts](https://mlsanity.com/paper/2407.18074/) (2024)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions](https://mlsanity.com/paper/2402.07363/) (2024)
- [Generalized Principal-Agent Problem with a Learning Agent](https://mlsanity.com/paper/2402.09721/) (2024)
- [Impact of Decentralized Learning on Player Utilities in Stackelberg Games](https://mlsanity.com/paper/2403.00188/) (2024)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [Emergent Risk Awareness in Rational Agents under Resource Constraints](https://mlsanity.com/paper/2505.23436/) (2025)
- [Should Decision-Makers Reveal Classifiers in Online Strategic Classification?](https://mlsanity.com/paper/2506.01936/) (2025)
- [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Learning to Play Against Unknown Opponents](https://mlsanity.com/paper/2412.18297/) (2024)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)
- [Computational Intractability of Strategizing against Online Learners](https://mlsanity.com/paper/2503.04202/) (2025)
- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners](https://mlsanity.com/paper/2502.08597/) (2025)
- [Learning Under Moral Hazard with Instrumental Regression and Generalized Method of Moments](https://mlsanity.com/paper/2405.20642/) (2024)
- [Is Online Linear Optimization Sufficient for Strategic Robustness?](https://mlsanity.com/paper/2602.12253/) (2026)
- [Learning Safely Without Knowing the World:COMPASS-Hedge](https://mlsanity.com/paper/2603.22348/) (2026)
- [No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics](https://mlsanity.com/paper/2604.05129/) (2026)
- [Mean-based algorithms: A lower bound and regret](https://mlsanity.com/paper/2606.04931/) (2026)
- [Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts](https://mlsanity.com/paper/2609.20353/) (2026)

## Abstract (arXiv)

Many real-life contractual relations differ completely from the clean, static model at the heart of principal-agent theory. Typically, they involve repeated strategic interactions of the principal and agent, taking place under uncertainty and over time. While appealing in theory, players seldom use complex dynamic strategies in practice, often preferring to circumvent complexity and approach uncertainty through learning. We initiate the study of repeated contracts with a learning agent, focusing on agents who achieve no-regret outcomes. Optimizing against a no-regret agent is a known open problem in general games; we achieve an optimal solution to this problem for a canonical contract setting, in which the agent's choice among multiple actions leads to success/failure. The solution has a surprisingly simple structure: for some α > 0, initially offer the agent a linear contract with scalar α, then switch to offering a linear contract with scalar 0. This switch causes the agent to ``free-fall'' through their action space and during this time provides the principal with non-zero reward at zero cost. Despite apparent exploitation of the agent, this dynamic contract can leave both players better off compared to the best static contract. Our results generalize beyond success/failure, to arbitrary non-linear contracts which the principal rescales dynamically. Finally, we quantify the dependence of our results on knowledge of the time horizon, and are the first to address this consideration in the study of strategizing against learning agents.