Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts
The paper proves minimax-optimal regret of order T^(m/(m+1)) for repeated online contract design with unrestricted bounded contracts and arbitrary agent action spaces.
The study analyzes repeated contract design where a principal observes outcomes but not agent actions, allowing arbitrary bounded outcome-contingent payment vectors. For any fixed number m of outcomes with m>=2, minimax regret over T rounds is of order T^(m/(m+1)) up to logarithmic factors, matched by upper and lower bounds. The upper bound uses an effective-dimension reduction and revealed preference in payment-difference coordinates, without smoothness or monotone-surplus assumptions, while the lower bound shows each additional contractible outcome increases worst-case learning cost.
- Proves minimax regret of order T^(m/(m+1)) for any fixed number of contractible outcomes.
- Upper bound holds without smoothness or monotone-surplus assumptions, using revealed preference in payment-difference coordinates.
- Learning policy relies on a Lipschitz parametrization of the monotone response map using observed outcome categories.
- Lower bound shows each additional outcome dimension creates an unavoidable increase in worst-case learning cost.
From the original article
1 min read at arxiv.orgWe 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.
By Rui Ai · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.