Poiani et al. achieve tight regret bounds in online contract design
New algorithm learns optimal contracts without seeing agent actions, achieving Θ(T^{2/3}) regret.
The paper from Poiani, Bernasconi, and Celli addresses the online extension of the classic principal-agent contract design problem. In each round, a principal offers a payment scheme (contract) to an agent, who then chooses a costly action affecting the outcome. The principal observes only the outcome, not the action. The agent's private type (cost per unit effort) is unknown and may vary adversarially or be fixed.
The authors provide tight regret bounds: for adversarial-type sequences, they achieve Θ(T^{2/3}) regret, remarkably independent of the number of outcomes m. This is accomplished via a reduction to one-dimensional threshold optimization and a non-uniform discretization to handle non-Lipschitzness. For a single fixed hidden type, they improve to Θ̃(√T) using an explore-then-commit algorithm that first approximately learns the type via stochastic binary search, then commits to a robustified near-optimal contract. This work advances online learning in mechanism design, with implications for automated contracting, algorithmic fairness, and AI agent coordination.
- Tight Θ(T^{2/3}) regret for adversarial agent types, independent of outcome count m
- Improved Θ̃(√T) regret for fixed hidden type using stochastic binary search and explore-then-commit
- Reduction to one-dimensional threshold optimization with non-uniform discretization
Why It Matters
Enables AI systems to learn optimal incentive structures from outcome data alone, crucial for automated contracting and delegation.