Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts

This paper investigates the statistical complexity of repeated contract design in environments where the principal observes outcome categories but not the agent's hidden actions. The core challenge is that the principal's expected profit can be discontinuous in the payment vector, making standard smooth optimization techniques inapplicable. The authors seek to characterize the minimax regret—the worst-case performance loss—as a function of the number of outcomes and the time horizon.

The authors establish a sharp minimax rate by combining three key techniques. First, they normalize the benchmark supremum to payment-difference coordinates, which allows them to handle the principal-agent problem without assuming that the agent's response is invariant to common payment shifts. Second, they utilize a reduced Minty geometry, which transforms the discontinuous profit function into a Lipschitz-continuous structure in Minty coordinates. This allows the learner to approximate the optimal contract by covering a known ambient cube rather than the discontinuous profit landscape. Third, they develop a two-level learning policy: a set of stochastic-approximation simulators for grid points in the Minty space, and a rested-UCB master algorithm that adaptively allocates rounds to these simulators.

The study proves that for any fixed number of outcomes m, the minimax regret is of order T^(m/(m+1)). This result closes the gap between previous upper and lower bounds. The upper bound is robust, applying to heterogeneous agents and arbitrary action spaces without requiring smoothness or monotone-surplus assumptions. The matching lower bound demonstrates that the T^(m/(m+1)) rate is unavoidable, as each additional contractible outcome creates a precise increase in the worst-case cost of learning. The findings imply that while finer performance classification can increase the set of expressible incentives, it also imposes a quantifiable statistical penalty on the principal's ability to learn the optimal contract.