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.
Full article157 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.20353