Repeated contract design achieves near-best learning rates for multiple outcomes
Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts
Machine Learning
Summary
This paper looks at how a company or principal can design repeated contracts with an agent when they can only see the results, not the actions taken to get them. The authors find that when there are multiple possible outcomes, the difficulty of learning the best contract grows in a specific, predictable way over time. They show how to create payment rules that adapt effectively, without needing smooth or simple assumptions about agents. Their work defines the fundamental limits and rates for learning in these complex contract settings.
What this means in practice
- •For contract managers: Design adaptive payment schemes in repeated contracts when only outcomes are visible, improving contract terms with minimal regret over time.
- •For online marketplace operators: Optimize incentives for service providers based on observed outcome categories without full knowledge of their actions.
A theory result. No direct application yet.
Authors
Rui Ai, David Simchi-Levi, Han Zhong
Abstract
We study repeated contract design when a principal observes outcomes but not the actions that generate them. The principal may use any bounded outcome-contingent payment vector, and the agent's best response can make expected profit discontinuous in those payments. For every fixed number $m\ge2$ of outcomes, the minimax regret over $T$ rounds is of order $T^{m/(m+1)}$, up to logarithmic factors. The upper bound allows arbitrary action spaces and agent heterogeneity, without smoothness or monotone-surplus assumptions. Its key is an effective-dimension reduction that the benchmark can be normalized even when fixed tie-breaking is not shift invariant, after which revealed preference yields a monotone response map in payment-difference coordinates. A learning policy built on a Lipschitz parametrization of this map attains the rate using only observed outcome categories. The lower-bound construction accounts for how incentive losses accumulate across outcome dimensions. It shows that each additional contractible outcome creates a precise and unavoidable increase in the worst-case cost of learning.