Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts Rui Ai∗
David Simchi-Levi†
Han Zhong‡
arXiv:2609.20353v1 [cs.LG] 17 Sep 2026
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 ≥ 2 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.
Keywords: online contract design; principal-agent problem; minimax regret.
1
Introduction
Outcome-contingent pay is most useful when effort is hidden. A platform may pay a provider by customer-rating category, or a buyer may condition procurement payments on a quality grade. When the environment is unknown, the payment schedule must both create incentives and generate information. This learning problem is unusually irregular in that a small payment change can switch the agent’s hidden action and discontinuously change the principal’s profit, so neither smooth optimization nor a naive discretization of payment space provides a general solution. We characterize the minimax regret of this unrestricted finite-outcome problem up to logarithmic factors. For every fixed number of outcome categories, the sharp exponent is the number of outcomes divided by one plus that number, while with one outcome, optimal regret is zero. The upper bound permits heterogeneous agents, arbitrary action spaces, and discontinuous responses. The matching lower bound already holds with one type, finitely many actions, bounded nonnegative costs, and a common deterministic tie-breaking rule. Thus, richer outcome classifications have a precise worst-case learning cost even though they may make contracts more expressive. The ∗
Massachusetts Institute of Technology. Email: [email protected]. Massachusetts Institute of Technology. Email: [email protected]. ‡ Shanghai Jiao Tong University. Email: [email protected]. †
1
improvement is quantitative even in the smallest nontrivial case. For two outcomes, the closest e 4/5 ), whereas our sharp rate is Θ(T e 2/3 ). For general upper bound of Zhu et al. (2023) scales as O(T general fixed m, the upper exponent improves from 1 − 1/(2m + 1) to 1 − 1/(m + 1) = m/(m + 1). The gain comes without restricting the number of actions or imposing response regularity. Three contributions deliver this characterization. First, we close the upper-lower gap for the unrestricted fixed-dimensional model under a single convention in which m counts all outcomes, including any null outcome. Second, we expose a reduced monotone geometry and turn it into an outcome-feedback policy that does not know the action set, costs, type distribution, outcome laws, or response map. Third, we give an aggregate-response lower-bound construction that works in every outcome dimension and uses one common deterministic tie-breaking rule across all hard instances. Together, these results identify both the optimal statistical rate and the mechanism that determines it. The upper bound rests on an effective-dimension reduction. A common shift of all payments preserves every agent’s best-response set but may change which tied action a fixed selector chooses. We therefore cannot simply quotient the selected response by common shifts. A perturbation argument instead shows that the benchmark supremum can be restricted to contracts with minimum payment zero without assuming shift-invariant selection. In the resulting payment-difference coordinates, revealed preference makes the selected outcome law monotone. Adding the contract coordinate to this law produces a Minty coordinate that parametrizes the selected-response graph in a Lipschitz way, even though the contract-to-profit map can jump. This geometry changes what the learner discretizes. Rather than cover the discontinuous profit function, the policy covers a known ambient cube of Minty coordinates. Each grid point drives a projected stochastic-approximation simulator using only the realized outcome category, and a rested upper-confidence master allocates rounds among simulators. A simulator near the optimal graph coordinate has uniformly small prefix regret, and the master competes with it. Balancing graph approximation with statistical allocation yields the upper rate. The distinction between contract space and graph space is central. An ordinary payment grid can approach a near-optimal contract yet induce a different action and profit. Our grid instead approximates Minty coordinates of reduced contracts and their selected outcome laws. Stochastic approximation of the strongly monotone residual yields a uniform prefix-regret certificate that survives the rested master’s adaptive allocation. This is why discontinuity of the original profit function does not prevent learning at the sharp rate. For the lower bound, we build many finite-action alternatives that differ from a baseline only through one action cost. The distinguished action is selected according to its aggregate payoff deficit across coordinates. These aggregate response regions are disjoint, contain contracts with a controlled profit improvement, and localize the statistical information about their associated alternatives. A change-of-measure argument then gives the same exponent as the upper bound. This construction also resolves a dimension issue in the closest unrestricted benchmark. Zhu et al. (2023) establish the binary lower bound and a general upper bound, but their multidimensional appendix uses more outcome coordinates than the main text’s dimension convention and a product response cell that treats coordinatewise losses separately even though those losses accumulate while
2
the distinguished action receives its cost reduction only once. That calculation therefore does not establish the stated multidimensional exponent when dimension counts total outcomes. Our self-contained aggregate-region construction avoids this step and we give the exact comparison in Section 7. The selected response in our model is fixed before learning and need not be known to the principal. This assumption is automatic under a unique best response and is implemented by any predetermined priority rule under ties. It excludes only history-dependent adversarial tie-breaking, which would make the response law itself nonstationary. The policy observes the outcome category used to settle the contract, not hidden actions, types, costs, or outcome distributions. It requires neither ordered outcomes, monotone effort, smooth behavior, nor a parametric response model. The operational message is two-sided. Refining a performance classification can enlarge the set of incentives a principal can express, but without behavioral structure it also raises the worst-case cost of finding a good contract. On the other hand, our normalization reduces the m payment coordinates to m − 1 independent payment differences. The minimax rate quantifies how this dimension affects worst-case learning, while the contracting benefit of finer outcome classifications depends on the application. Related work. Classical hidden-action theory studies known primitives (Holmstrom, 1979; Grossman and Hart, 1983), whereas algorithmic contract design asks how actions, outcomes, and private types affect computation, approximation, and statistical complexity. Guruganesh et al. (2021) study moral hazard together with adverse selection, while Dütting et al. (2025) characterize statistical complexity through the pseudo-dimension of contract classes. Online contract design instead requires the principal to learn from repeated outcomes. Ho et al. (2016) use bandit methods and adaptive discretization in crowdsourcing markets. Cohen et al. (2023) study how to learn monotone-smooth contracts for identical agents under stochastic dominance and bounded risk aversion. The closest unrestricted benchmark is Zhu et al. (2023). We retain its finite-outcome model, and our improvement comes from reduced monotone geometry rather than additional response regularity. Complementary results also exploit structure absent here, e.g., Bacchiocchi et al. (2025a) obtain polynomial sample complexity and improved regret when the number of actions is fixed, while Zuo (2024) studies continuous actions under first-order or Lipschitz regularity. Chen et al. (2024) learn near-optimal bounded contracts using polynomially many queries under first-order stochastic dominance and diminishing returns to effort. Bacchiocchi et al. (2025b) study contract learning with approximate best responses and evaluate each contract by the principal’s worst expected payoff among those responses. Our fresh-agent stationaryresponse model is also distinct from repeated contracting with a persistent no-regret learning agent (Guruganesh et al., 2024). Methodologically, we combine monotone-operator ideas (Minty, 1962; Rockafellar, 1976), stochastic approximation (Robbins and Monro, 1951), martingale concentration (Freedman, 1975), and upper-confidence allocation (Auer et al., 2002). The paper proceeds as follows. Sections 2-6 give the model, geometry, algorithm, and upper bound. Section 7 develops the lower bound, and we defer all remaining proofs to the appendices.
3
2
Model and Learning Objective
We assume there are m < ∞ outcomes. The principal’s public value vector is v ∈ [0, 1]m , and a P contract is a payment vector f ∈ [0, 1]m . Write ∆m = {p ∈ Rm + : j pj = 1}. Assumption 2.1 (Selected best responses). At each round, a type θ is drawn independently from a fixed distribution. Type θ has an action set Aθ . Action a has outcome law pθ,a ∈ ∆m and cost cθ,a ∈ R. For every θ and f , a selected response aθ (f ) ∈ argmax{pθ,a · f − cθ,a } a∈Aθ
exists, is fixed independently of the learner’s history, and induces a measurable map (θ, f ) 7→ pθ,aθ (f ) . Assumption 2.1 is mild in practice in that, for instance, any finite action set with a fixed measurable priority rule satisfies it. The assumption imposes no stochastic ordering, smoothness, response continuity, or separate participation constraint. For finite action sets, fixing an action priority before learning makes the selected response automatic. For infinite action spaces, the assumption records only the existence of a maximizer and the measurability of the induced outcome law. In particular, it does not require the selection to be invariant when the same constant is added to every payment. That distinction matters for normalization and is handled explicitly in Lemma 4.2. Let P (f ) = Eθ [pθ,aθ (f ) ] ∈ ∆m . After posting f given history H, the principal observes the realized outcome as a one-hot vector X satisfying E[X | f, H] = P (f ).
(2.1)
This is outcome-category feedback, as in Zhu et al. (2023) where the learner does not observe P (f ), the type, or the action. Fresh types and outcomes make (2.1) valid under adaptive policies. The feedback is economically natural as the outcome category must be observed in order to settle an outcome-contingent contract. It is nevertheless stronger than observing only the realized scalar profit. The algorithm uses the one-hot vector as an unbiased estimate of the selected outcome law, so the result should not be read as a scalar bandit-feedback guarantee. The principal’s expected one-period utility is u(f ) = P (f ) · (v − f ). A policy chooses ft from past contracts and outcomes, and its expected Stackelberg regret is " T # X RT = T sup u(f ) − E u(ft ) . f ∈[0,1]m
t=1
The learner knows m, v, and the protocol, but none of the remaining primitives or the induced map P . Let Im be the class of instances above and define R⋆T (m) = inf π supI∈Im RT (π, I) over adaptive outcome-feedback policies. When m = 1, P (f ) = 1 and u(f ) = v1 − f , so posting f = 0 gives zero regret. Henceforth we study m ≥ 2 different outcomes. The upper bound applies to the full class Im , including heterogeneous types and infinite action spaces, whereas the lower bound uses one type, finitely many actions, bounded nonnegative costs, 4
and common deterministic tie-breaking. Constants Cm < ∞ may change from line to line and depend only on fixed m. Throughout, a subscript m on asymptotic notation allows the hidden constant to depend on the fixed number of outcomes m. A tilde additionally suppresses factors polylogarithmic in T . The dimension-only algorithm constant Bm is fixed before learning and chosen sufficiently large for the concentration certificates below. This asymmetry between the two theorem classes is intentional. The upper bound is robust to essentially all hidden primitives once the selected response is stationary, whereas the lower bound shows that neither heterogeneity, infinite action spaces, nor instance-dependent tie-breaking is responsible for the difficulty. The common hard-family structure will also make the information comparison transparent.
3
Main Results
The headline result is an exact fixed-dimension minimax exponent. The two theorems below use the same convention that m is the total number of outcomes, including any null outcome. The upper theorem states the finite-scale guarantee needed to see every source of regret, while the lower theorem shows that the leading exponent survives on a sharply restricted subclass. For a resolution parameter ε ∈ (0, 1), the upper-bound policy uses a grid of Kε candidate contract-response coordinates. Section 5 defines this grid formally. Theorem 3.1 (Fixed-scale upper bound for unrestricted contracts). For every fixed m ≥ 2, there exists a finite constant Bm , depending only on m, such that, for every T ≥ 2 and ε ∈ (0, 1), Algorithms 1-2 with confidence δ = T −2 use only m, v, T , and ε and satisfy, on every instance in Im , p RT ≤ Cm T ε + LT T Kε + Kε , √ where Kε ≤ (1 + 3 m − 1/ε)m−1 and LT = 1 + log3 (16Kε T 3 ). Consequently, ε ≍ T −1/(m+1) up to em (T m/(m+1) ). logarithmic factors gives RT ≤ O Proof sketch. The upper bound proof has three ingredients. 1. Normalization without response invariance. A common payment shift preserves each bestresponse set but can change the action chosen from a tie. A perturbation toward the value vector normalizes the benchmark supremum without assuming that selected responses themselves are shift invariant. 2. Regularizing the selected-response graph. Revealed preference makes the reduced outcome law monotone. The Minty transformation adds the contract coordinate to that law, making both components Lipschitz functions of the transformed graph coordinate despite discontinuity in payments. 3. Learning an unknown graph. The policy covers a known ambient cube, assigns a projected stochastic-approximation simulator to every grid point, and uses a rested-UCB master. One 5
near-graph simulator has a uniform prefix certificate, and the master can find it without knowing its identity. The three terms have separate roles. The term T ε is the price of approximating the optimal √ selected-response graph point, LT T Kε is the cost of allocating observations across rested simulators, and Kε activates the grid. Since a grid of resolution ε has√order ε−(m−1) points, balancing em ( T ε−(m−1) ) gives ε ≍ T −1/(m+1) the approximation cost T ε and the statistical allocation cost O and regret T m/(m+1) . See Sections 4-6 and the appendices for the detailed proof. Theorem 3.2 (Matching finite-outcome lower bound). For every fixed m ≥ 2, there is cm > 0 such that every adaptive outcome-feedback policy and every T ≥ 1 incur RT ≥ cm T m/(m+1) on some finite-action, single-type instance in Im . The hard family has public value (1, . . . , 1, 0), nonnegative costs bounded by one, the same finite action set and action-level outcome laws, and one common deterministic action-priority rule while each alternative changes only one action cost from a common baseline. Proof sketch. Each lower-bound alternative discounts one action, whose selection depends on its aggregate payoff deficit across coordinates. The construction packs Θ(ε−(m−1) ) disjoint aggregate response regions, and a visit to one region reveals only O(ε2 ) information about its associated alternative. Averaged across the packing, the information scale is Om (T εm+1 ). Keeping it bounded forces ε ≍ T −1/(m+1) and produces regret Ωm (T ε) = Ωm (T m/(m+1) ). See Section 7 and Appendix D for the detailed proof. The lower bound is witnessed by a deliberately parsimonious hard family. Every instance has one agent type and uses the same finite action set, action-level outcome laws, and deterministic tie-breaking priority. All costs are bounded and nonnegative, and each alternative changes only one action cost relative to a common baseline. The construction therefore pins the sharp T m/(m+1) exponent on the statistical difficulty of learning how a localized incentive perturbation changes contract-induced behavior from outcome feedback. Combining Theorems 3.1 and 3.2, we obtain, for every fixed m ≥ 2, e m (T m/(m+1) ). R⋆T (m) = Θ We next discuss how the result improves the existing bounds and the scope of its operational interpretation. What closes the previous gap? For unrestricted contracts, Zhu et al. (2023) give the valid gene √m T 1−1/(2m+1) ). Their discretization covers directions and radii in payment eral upper bound O( space, whereas our policy covers the reduced selected-response graph. After normalization, this graph has m − 1 effective coordinates, and the Minty transformation makes graph approximation control utility even though payment-space approximation does not. The resulting cover contributes order ε−(m−1) , rather than the larger payment-space discretization that drives the previous exponent. This yields T m/(m+1) and, together with our aggregate-region multidimensional lower bound, closes the minimax exponent.
6
The improved upper bound requires both normalization and Minty regularization. Normalization alone removes the common-payment direction but leaves a discontinuous objective, while Minty regularization alone, without normalization, would retain an unnecessary dimension and miss the sharp exponent. On the lower side, a coordinatewise product cell would not match this reduced geometry because payoff deficits add across coordinates. The aggregate-response regions repair that accumulation and make the same m − 1 dimensions appear in the testing bound. Thus the upper and lower constructions identify one common geometric obstruction rather than producing coincidentally matching powers. Operational interpretation and scope. Operationally, the rate prices the number of independently contractible outcome differences, not payment levels. The policy observes only the outcome category and is information-theoretic rather than dimension-free computationally that its grid is polynomial in T for fixed m but exponential in m. Structured responses or contract families may permit faster rates, but scalar reward-only feedback does not provide the outcome signal used here. For an organization choosing how finely to classify performance, our theorems isolate a worstcase cost of granularity. Splitting an outcome category may improve the best contract when primitives are known, but it also adds a payment-difference direction that must be learned. The result quantifies the second effect and deliberately leaves the first, application-specific benefit to a separate model-selection problem.
4
Normalization and Reduced Minty Geometry
The principal’s utility may jump at response boundaries, so proximity of two contracts alone says little about proximity of their profits. The optimizing behavior nevertheless restricts the direction of these jumps. We first extract that revealed-preference restriction, then remove the economically redundant common-payment direction, and finally use a Minty coordinate to turn graph proximity into utility proximity. Lemma 4.1 (Revealed-preference monotonicity). For any f, g ∈ [0, 1]m , (P (f )−P (g))·(f −g) ≥ 0. Proof. For a fixed type, let (pf , cf ) and (pg , cg ) be the outcome-cost pairs selected under f and g. Optimality gives pf · f − cf ≥ pg · f − cg and pg · g − cg ≥ pf · g − cf . Adding and averaging over types proves the claim. Lemma 4.1 does not assert continuity. It says that response jumps are ordered in aggregate. The Minty transformation below converts precisely this weak order into metric control. Lemma 4.2 (Benchmark normalization). For every instance satisfying Assumption 2.1, sup u(f ) = f ∈[0,1]m
sup
u(f ),
f ∈[0,1]m : minj fj =0
without requiring the selected response to be invariant under common payment shifts.
7
Proof. Fix f , let c = mini fi , and set g = f −c1. Choose j ∈ argmin{vi : gi = 0} and, for sufficiently small η > 0, set hη = (1 − η)g + η(v − vj 1). Then hη ∈ [0, 1]m and mini hη,i = 0, coordinate j is zero, other zero coordinates of g are nonnegative by the choice of j, and positive coordinates remain nonnegative. For each type, let pθ be the law selected at f and qθ the law selected at hη . The action selected at f remains optimal at g because f − g = c1. Comparing it with the action selected at hη in both directions gives (qθ − pθ ) · (hη − g) ≥ 0, hence qθ · (v − g) ≥ pθ · (v − g) because both laws have unit mass. Therefore, u(hη ) = (1 − η)Eθ [qθ · (v − g)] + ηvj ≥ (1 − η)(u(f ) + c) + ηvj . Letting η ↓ 0 and then taking the supremum over f proves the nontrivial direction, and we immediately obtain the reverse. The perturbation is needed because subtracting c1 preserves the set of best responses but need not preserve the action selected from that set. The proof compares optimizers at two different contracts and takes a limit, so no shift-invariance property of the selector is used. For y ∈ Rm , we write y−m = (y1 , . . . , ym−1 ). For each contract f , define its payment-difference vector relative to outcome m by x(f ) = f−m − fm 1. Thus xi (f ) = fi − fm is the payment for outcome i minus the payment for the reference outcome m. The range of x(f ) over contracts f ∈ [0, 1]m is D = x ∈ Rm−1 : max(0, x1 , . . . , xm−1 ) − min(0, x1 , . . . , xm−1 ) ≤ 1 .
(4.1)
For x ∈ D, let λ(x) = − min(0, x1 , . . . , xm−1 ) and define f¯(x) = (x + λ(x)1, λ(x)),
v̄ = v−m − vm 1,
Q(x) = P (f¯(x)) −m .
(4.2)
The shift λ(x) subtracts the smallest entry of (x, 0) from every coordinate. By (4.1), the resulting contract f¯(x) lies in [0, 1]m , has minimum payment zero, and satisfies x(f¯(x)) = x. It is therefore the unique normalized contract realizing the payment differences x. The vector v̄ expresses the principal’s values relative to the same reference outcome m, and Q(x) records the first m − 1 outcome probabilities induced by f¯(x). The remaining probability is determined by P (f¯(x)) m = 1 − 1 · Q(x). Lemma 4.3 (Canonical reduction). D is compact and convex. The map f 7→ x(f ) restricts to a bijection from the normalized contracts onto D, with inverse f¯(·). Moreover, v̄ ∈ D, λ is 1-Lipschitz, and for all x, y ∈ D, (Q(x) − Q(y)) · (x − y) ≥ 0, (4.3) while u(f¯(x)) = vm − λ(x) + Q(x) · (v̄ − x).
(4.4)
Proof. Equivalently, D = {x : −1 ≤ xi ≤ 1, xi − xj ≤ 1 ∀i, j}, so it is a compact convex polytope. For every x ∈ D, the contract f¯(x) is normalized and x(f¯(x)) = x. Conversely, if f is normalized, 8
(a) Payment-difference coordinate
(b) Reduced Minty coordinate z(x) = x + Q(x) Nearby graph points in z control both contract and response.
z(x)
Q(x)
Nearby contracts can induce widely separated outcome laws.
large |Q(x+ ) − Q(x− )|
response jump creates a z-gap
small |x+ − x− |
x− x+
x
x− x+
x
|∆x|, |∆Q| ≤ |∆z| =⇒ |∆u| ≤ Cm |∆z|
Figure 1: Binary illustration of the reduced selected-response graph and its Minty coordinate z = x + Q(x). then fm = λ(x(f )) and f¯(x(f )) = f . Because f¯(x) − f¯(y) = (x − y, 0) + (λ(x) − λ(y))1 and outcome laws have unit mass, Lemma 4.1 yields (4.3). The coordinate range of v is at most one, giving v̄ ∈ D, and it holds that the minimum function is 1-Lipschitz in ℓ∞ . Finally, substituting P (f¯(x)) m = 1 − 1 · Q(x) gives (4.4). Define the reduced Minty coordinate z(x) = x + Q(x) ∈ [−1, 2]m−1 and residual Fz (x) = x + Q(x) − z. Lemma 4.4 (Reduced Minty geometry). For every z and x, y ∈ D, (Fz (x) − Fz (y)) · (x − y) ≥ ∥x − y∥22 . Moreover, ∥x − y∥2 ≤ ∥z(x) − z(y)∥2 ,
∥Q(x) − Q(y)∥2 ≤ ∥z(x) − z(y)∥2 ,
and |u(f¯(x)) − u(f¯(y))| ≤ Cm ∥z(x) − z(y)∥2 . Proof. The first claim follows from Fz (x) − Fz (y) = (x − y) + (Q(x) − Q(y)) and (4.3). Expanding ∥z(x) − z(y)∥22 = ∥x − y∥22 + ∥Q(x) − Q(y)∥22 + 2(Q(x) − Q(y)) · (x − y) proves both distance inequalities and injectivity of z(·) on the selected-response graph. Finally, (4.4), Lipschitzness of λ, √ ∥v̄ − x∥2 ≤ 2 m − 1, and ∥Q(y)∥2 ≤ 1 give |u(f¯(x)) − u(f¯(y))| ≤ Cm (∥x − y∥2 + ∥Q(x) − Q(y)∥2 ) and applying the distance bounds finishes the proof. The lemma controls utility along the selected-response graph shown in Figure 1, not as a continuous function of the posted contract. The next section learns this graph without observing it.
5
The Minty-Coordinate Algorithm
Lemma 4.4 shows that proximity in Minty coordinates controls utility differences along the selectedresponse graph. However, the outcome response map P , and hence the reduced map Q, is unknown. 9
The learner therefore cannot directly determine which Minty coordinates are attained or recover the corresponding contracts. The algorithm has two levels. At the first level, a simulator posts contracts for a fixed candidate Minty coordinate z and updates its payment differences using observed outcomes. If the Minty coordinate of a near-optimal normalized contract were known, a single simulator would suffice. To search for such a coordinate, the algorithm discretizes the known cube [−1, 2]m−1 and maintains one simulator for each grid point. At the second level, the master allocates rounds among these simulators, selecting one in each round based on the rewards observed so far. √ We fix ε ∈ (0, 1), partition each coordinate interval [−1, 2] into ⌈3 m − 1/ε⌉ equal cells, and let Zε be the Cartesian product of their centers. Every point in [−1, 2]m−1 is within distance ε/2 of this grid, and √ m−1 3 m−1 Kε := |Zε | ≤ 1 + . ε The grid can be constructed without knowing Q. It approximates every attained Minty coordinate, although some grid points may not equal x + Q(x) for any x ∈ D. Fix a grid point z ∈ Zε and consider its simulator. The superscript z identifies the simulator, and the subscript n indexes its calls. Let xzn ∈ D be its payment-difference vector used on its n-th call. Each simulator starts at xz1 = 0, corresponding to the feasible zero-payment contract f¯(0) = 0. On call n, it posts the normalized contract f¯(xzn ) defined in (4.2) and records the observed outcome z as the one-hot vector Xnz . We denote the first m − 1 entries of Xnz as Xn,−m . By (2.1) and the z definition of Q in (4.2), this vector has conditional mean Q(xn ). Hence, z E[xzn + Xn,−m − z | xzn ] = xzn + Q(xzn ) − z = Fz (xzn ).
When z is attained, strong monotonicity (Lemma 4.4) makes the negative residual point toward its corresponding payment-difference vector. Algorithm 1 subtracts this residual estimate, scaled by 1/(n + 1), from xzn . It then applies the Euclidean projection ΠD onto D to keep the next payment-difference vector feasible. The master in Algorithm 2 selects a simulator using an upper confidence bound (UCB) index. For a simulator that has been called nz ≥ 1 times, the index is its average observed reward plus a bonus. An uncalled simulator is assigned index +∞. In each global round, the master calls the simulator with the largest index. The simulators are rested, so only the selected simulator advances its call count, updates its contract, and records a new reward. All other simulators remain paused. A simulator’s expected reward can change as its contract is updated. For a grid point close to a normalized contract’s Minty coordinate, Section 6 bounds the simulator’s average utility loss relative to that contract with high probability. The bound consists of a grid approximation error and a term that decreases with the number of calls. The bonus covers the decreasing term and sampling noise. A direct implementation stores O(mKε ) numbers. Projection onto D is a convex quadratic program over a known fixed-dimensional polytope and requires no instance-specific information. The master can select the largest index by scanning the Kε simulators. 10
Algorithm 1 Minty-coordinate simulator for grid point z Input: public value vector v and grid point z ∈ Zε . Initialization: xz1 = 0 ∈ D. State: internal call count n and current difference coordinate xzn . Output on each call: posted contract, realized reward, and updated simulator state. On the n-th call to simulator z: 1. Post the canonical contract f¯(xzn ). 2. Observe one-hot outcome Xnz ∈ {0, 1}m with
P
z j Xn,j = 1.
3. Receive reward Ynz = Xnz · (v − f¯(xzn )). 4. Update xzn+1 = ΠD
6
xzn −
1 z z (x + Xn,−m − z) . n+1 n
Proof of Theorem 3.1
We prove the theorem using two lemmas. Lemma 6.1 bounds a simulator’s cumulative utility loss relative to a normalized contract in terms of the distance between their Minty coordinates. Lemma 6.2 combines this bound with reward concentration to control the master’s total regret. We apply these lemmas to a near-optimal normalized contract and then choose the grid resolution. Lemma 6.1 (Prefix regret of a Minty simulator). Fix a candidate Minty coordinate z ∈ [−1, 2]m−1 and a comparator x⋆ ∈ D. Let z ⋆ = x⋆ + Q(x⋆ ). Run the update in Algorithm 1 with this candidate z, and write xn for xzn , the payment-difference vector used on its n-th call. For every T ≥ 2 and δ ∈ (0, 1), with probability at least 1 − δ, N X
√ u(f¯(x⋆ )) − u(f¯(xn )) ≤ Cm N ∥z − z ⋆ ∥2 + N ι
n=1
simultaneously for all 1 ≤ N ≤ T , where ι = 1 + log3 (8T /δ). The bound separates the error induced by approximating z ⋆ with z from the error accumulated while updating the contract. For the analysis, we generate a sequence of T calls for each simulator, with outcomes drawn according to its posted contracts. Whenever the master selects a simulator, it reveals the next outcome in that sequence. Since unselected simulators remain paused, this construction has the same distribution as the original interaction. The bounds below therefore apply to every prefix, including those that the master does not observe. Lemma 6.2 (Rested-UCB accounting for the master). Run Algorithm 2 on a finite grid Z of size K for T rounds. Fix a comparator x⋆ ∈ D, an approximation scale ε ≥ 0, and an error scale ι ≥ 1. Suppose that, on some event, the following two certificates hold. 11
Algorithm 2 Rested-UCB master Input: value vector v, scale ε, grid Zε , horizon T , confidence level δ ∈ (0, 1), and the fixed dimension-only design constant Bm . Output: the sequence of T posted contracts generated by selected simulators. Let ι = 1 + log3 (16Kε T /δ). Initialize nz = 0 for every z ∈ Zε . For rounds t = 1, . . . , T : 1. For each z ∈ Zε , if nz = 0 set Iz = +∞. If nz ≥ 1, set n
z 1 X Ykz , µ bz (nz ) = nz
ι Iz = µ bz (nz ) + Bm √ . nz
k=1
2. Let zt be the lexicographically first element of argmaxz∈Zε Iz . 3. Call simulator zt once according to Algorithm 1, using internal call index nzt + 1. 4. Set nzt ← nzt + 1, leaving all other simulator states unchanged.
1. There is a special simulator z ◦ such that, for every 1 ≤ n ≤ T , n 1 X ¯ z◦ ι ⋆ ¯ √ u(f (xk )) ≥ u(f (x )) − Cm ε + . n n k=1
2. For every simulator z and every 1 ≤ n ≤ T , n
µ bz (n) −
ι 1X ¯ z u(f (xk )) ≤ Cm √ . n n k=1
Let β(n) be the actual bonus in the index Iz (n) = µ bz (n) + β(n) for a simulator with n ≥ 1 previous calls. Suppose the design constant in Algorithm 2 is chosen so that, for every 1 ≤ n ≤ T , this bonus dominates the sum of the two n−1/2 error terms in the certificates above and also satisfies √ β(n) ≤ Cm ι/ n. Then, on the same event, T X
√ u(f¯(x⋆ )) − u(ft ) ≤ Cm T ε + ι KT + K .
t=1
The complete proofs of Lemmas 6.1 and 6.2 are in Appendices B and C. We first combine their conclusions to prove the theorem. Proof of Theorem 3.1. Fix an arbitrary instance I ∈ Im and write u for its utility map. Fix ε ∈ (0, 1) and run Algorithms 1 and 2 with confidence parameter δ ∈ (0, 1), which will be set to T −2 at the end. Let ι = 1 + log3 (16Kε T /δ). This factor dominates the simulator factor in Lemma 6.1 when that lemma is invoked with confidence δ/2, since we have Kε ≥ 1. 12
Because u may be discontinuous, the supremum need not be attained. For any fixed α > 0, Lemmas 4.2 and 4.3 allow us to choose an α-optimal comparator x⋆ ∈ D satisfying u(f¯(x⋆ )) ≥ supf ∈[0,1]m u(f ) − α. Let z ⋆ = x⋆ + Q(x⋆ ). Since Zε is an ε-net of [−1, 2]m−1 , we can choose z ◦ ∈ Zε such that ∥z ◦ − z ⋆ ∥2 ≤ ε. Lemma 6.1, applied to simulator z ◦ with confidence δ/2, gives an event of probability at least 1 − δ/2 on which, for all 1 ≤ n ≤ T , n ι 1 X ¯ z◦ ⋆ . (6.1) u(f (xk )) ≥ u(f¯(x )) − Cm ε + √ n n k=1
Lemma A.2 gives the uniform reward concentration event that with probability at least 1 − δ/2, for all z ∈ Zε and all 1 ≤ n ≤ T , r n 1X ¯ z log(16Kε T /δ) µ bz (n) − u(f (xk )) ≤ C . (6.2) n n k=1
On the intersection of (6.1) and (6.2), the hypotheses of Lemma 6.2 hold with K = Kε and p error scale ι. Indeed, we know ι ≥ 1 and it dominates log(16Kε T /δ). By the fixed choice of the dimension-only constant Bm , the actual bonus β(n) dominates the sum of the two n−1/2 error √ terms while remaining at most Cm ι/ n. Therefore, at this intersection,
T
sup u(f ) − f ∈[0,1]m
T X
u(ft ) ≤ T α + T u(f¯(x⋆ )) −
t=1
T X
p u(ft ) ≤ T α + Cm T ε + ι T Kε + Kε .
t=1
On the complement of the high-probability event, the per-round regret relative to the optimal one-period value is at most 2 because u(f ) ∈ [−1, 1]. Hence " T # X p u(ft ) ≤ Cm T ε + ι T Kε + Kε + 2T δ + T α. T sup u(f ) − E f ∈[0,1]m
t=1
Setting δ = T −2 yields ι = 1 + log3 (16Kε T 3 ) = LT , and 2T δ = 2/T ≤ 1 ≤ Kε for T ≥ 2. Letting α ↓ 0 proves the fixed-scale bound for RT . Since I ∈ Im was arbitrary, the same bound holds for every instance in the class as well. For the optimized rate, we substitute the bound on Kε . In fixed-m notation, we have p em T ε + T 1/2 ε−(m−1)/2 + ε−(m−1) . T ε + LT T Kε + Kε = O Taking ε ≍ T −1/(m+1) balances the first two terms at T m/(m+1) , while the third term is T (m−1)/(m+1) and has lower order. This proves the optimized rate.
7
A Matching Lower Bound
The lower bound uses one type, the public value vector v = (1, . . . , 1, 0), and a finite product family of actions. For a contract f , write xi = fi − fm for i < m. At scalar level k, we choose a non-null outcome probability ρk and a cost contribution κk so that ϕk (x) = ρk x − κk 13
and adjacent lines cross at kε. A joint action selects one level in each of the m − 1 non-null coordinates, making the baseline agent payoff a sum of scalar envelopes. The probabilities are calibrated so that the principal’s baseline utility is at most 1/2 under every contract. For each even multi-index l in a packing set L, the alternative Il lowers only the cost of joint action al by ∆=
ε2 . 16(m − 1)
The action al can be selected only in the aggregate response region ( m−1 ) X Rl = x : max ϕk (xi ) − ϕli (xi ) ≤ ∆ . i=1
k
(7.1)
This region need not be a Cartesian product. Neighbor comparisons place it inside a narrow coordinate box, so even multi-indices make the regions pairwise disjoint. A small displacement in one coordinate gives a contract at which al is the unique best response and the principal gains a constant multiple of ε over the baseline ceiling. Outside Rl , the alternative and baseline responses coincide. Relation to the earlier lower-bound construction. Theorem 5 of Zhu et al. (2023) denotes the total number of outcomes by m, whereas its Appendix D indexes an action by m non-null coordinates and then adds a null-outcome coordinate to the production vector. Under the totaloutcome convention used here, the construction therefore has m − 1 non-null coordinates. This bookkeeping issue alone can be repaired by relabeling the dimension, but the displayed Cartesian response cell has a separate multidimensional problem. At its simultaneous lower corner, each nonnull coordinate incurs an unperturbed agent-payoff loss equal to the full cost reduction assigned to the distinguished action. Those losses sum to m − 1 times the reduction, while the distinguished action receives the reduction only once. Relative to the action obtained by lowering every coordinate by one level, its payoff difference is therefore −(m − 2) times the reduction. For m > 2, the difference is strictly negative, so the displayed corner does not induce the distinguished action and the associated principal-payoff calculation does not follow. The binary case m = 2 is unaffected. Our proof replaces the Cartesian characterization with the aggregate condition (7.1) and no product response cell is needed. A query in Rl contributes O(ε2 ) to the one-period baseline-to-alternative KL divergence, whereas a query outside Rl contributes zero. Region disjointness bounds the total baseline visit count across alternatives by T . A uniformly sampled round and the Bretagnolle-Huber inequality then reduce the problem to testing among |L| ≍ ε−(m−1) alternatives. Averaging the resulting KL bounds over l gives Om (T εm+1 ) average divergence. Choosing ε ≍ T −1/(m+1) keeps the testing error bounded away from zero and yields regret Ωm (T ε). Appendix D details the construction, response regions, profitable contract, and adaptive information bounds.
14
8
Conclusion
We characterize the minimax difficulty of learning an unrestricted bounded contract from repeated outcome feedback. With m total outcomes, the exact fixed-dimensional regret exponent is m/(m+1) up to logarithmic factors. The upper bound allows arbitrary action spaces, heterogeneity, and discontinuous selected responses, while the lower bound already holds for one type, finitely many actions, bounded nonnegative costs, and a common deterministic priority rule. Thus the rate is not driven by a rich hard instance class. The raw payment vector overstates the dimension of the incentive problem by one, and we find that the benchmark can be normalized even when the fixed selection among best responses is not invariant to common payment shifts. In payment-difference coordinates, revealed preference supplies enough monotone structure to obtain the sharp upper rate without assuming continuity. A matching family of aggregate response regions shows that this dependence on the number of outcomes is unavoidable. The result separates three modeling choices that are sometimes bundled together. Unrestricted contracts do not by themselves make learning impossible, outcome categories provide the vector feedback needed to exploit revealed preference, and a response selection fixed before learning makes the induced environment stationary. Relaxing the feedback or stationarity conditions leads to different problems, while adding behavioral structure may permit faster learning. A particularly natural next step is to combine the present learning cost with the economic benefit of refining or coarsening the set of contractible performance categories.
A
Concentration Lemmas
Lemma A.1 (Uniform Freedman bound). Let (Zn )Tn=1 be martingale differences with |Zn | ≤ b, and P 3 2 put VN = N n=1 E[Zn | Fn−1 ] and ι = 1 + log (8T /δ). With probability at least 1 − δ, simultaneously for all N ≤ T , it holds that N X
Zn ≤ C
p ιVN + bι .
n=1
Proof. Freedman’s maximal inequality (Freedman, 1975, Theorem 1.6) bounds P(∃N ≤ T : P 2 n≤N Zn ≥ s, VN ≤ v) by exp{−s /[2(v + bs/3)]}. We apply it to the dyadic variance ranges 2 2 j−1 2 j VN ≤ b and b 2 < VN ≤ b 2 and assign failure probability 6δ/[π 2 (j + 1)2 ] to range j. There are at most 1 + ⌈log2 T ⌉ nonempty ranges, and their Freedman thresholds are bounded by √ C( ιVN + bι). A union bound proves the claim. For adaptive allocation, we can use the standard call-time coupling that independently seeds every simulator-call pair, reveals a seed only when that simulator is selected, and extends each virtual stream to T calls. This leaves the observed interaction unchanged and makes every simulator prefix available in its own filtration.
15
Lemma A.2 (Uniform reward concentration). For any adaptive master over a grid Z of size K, with probability at least 1 − δ, simultaneously for all z ∈ Z and n ≤ T , it holds that r n 1X ¯ z log(8KT /δ) µ bz (n) − u(f (xk )) ≤ C . n n k=1
Proof. In simulator call time, f¯(xzk ) is predictable and Ykz = Xkz ·(v− f¯(xzk )) ∈ [−1, 1] has conditional mean u(f¯(xzk )). Hoeffding-Azuma (Lattimore and Szepesvári, 2020, Exercise 20.6) for each (z, n), followed by a union bound over the KT pairs, proves the claim. Because the event holds for all virtual prefixes, restricting it to prefixes revealed by the adaptive master needs no optional-stopping argument.
B
Proof of the Simulator Prefix Bound
The proof has two logically distinct stages. First, strong monotonicity of the Minty residual yields pathwise tracking of the comparator up to the grid mismatch ∆. Second, a projection inequality against the value coordinate v̄ converts that tracking statement into utility regret. The second stage is necessary because contract distance by itself cannot control utility across a discontinuous response boundary. Proof of Lemma 6.1. Let’s suppress the simulator superscript and write qn = Q(xn ), q ⋆ = Q(x⋆ ), P ⋆ 2 ⋆ ⋆ ⋆ z ⋆ = x⋆ +q ⋆ , ∆ = ∥z−z ⋆ ∥2 , and SN = N n=1 ∥xn −x ∥2 . Since Fz (xn ) = (xn −x )+(qn −q )−(z−z ), monotonicity (4.3) and Young’s inequality (Young, 1912) give Fz (xn ) · (xn − x⋆ ) ≥ 21 ∥xn − x⋆ ∥22 − 21 ∆2 .
(B.1)
Let ξn = Xn,−m − qn . In simulator call time, ξn is a bounded martingale difference, and the update direction is bounded by Cm . With ηn = 1/(n + 1), projection nonexpansiveness and (B.1) yield ∥xn+1 − x⋆ ∥22 ≤ (1 − ηn )∥xn − x⋆ ∥22 + ηn ∆2 + Cm ηn2 − 2ηn ξn · (xn − x⋆ ). (B.2) The last scalar increment is bounded by Cm and has conditional variance at most Cm ∥xn − x⋆ ∥22 . Multiplying (B.2) by n + 1, summing, and applying Lemma A.1 with confidence δ/2 therefore gives, simultaneously for N ≤ T , √ Cm ι Cm ιSN ⋆ 2 2 ∥xN +1 − x ∥2 ≤ ∆ + + , ι = 1 + log3 (8T /δ). (B.3) N +1 N +1 √ Indeed, the telescoped noise sum is at most Cm ( ιSN + ι) as the harmonic deterministic term is absorbed by Cm ι. Replacing δ by δ/2 changes ι only by a universal factor, absorbed into Cm . The variance is self-normalizing. As the simulator approaches the comparator, the martingale term becomes correspondingly smaller. (B.3) therefore closes through a bootstrap rather than the √ cruder O( N ) noise bound, which would lose the required uniform prefix rate.
16
Summing (B.3) for N < r and using monotonicity of SN gives Sr ≤ Cm + r∆2 + Cm ι log(r + √ 1) + Cm ιSr log(r + 1). Solving this quadratic inequality and using log2 (r + 1) ≤ Cι yields 2
2
Sr ≤ Cm (r∆ + ι ),
N X
∥xn − x⋆ ∥2 ≤ Cm (N ∆ +
√ N ι).
(B.4)
n=1
Substituting back into (B.3), with Young’s inequality for the cross term, also gives ∥xN +1 − x⋆ ∥2 ≤ √ Cm (∆ + ι/ N + 1). It remains to convert tracking into utility. Substituting q ⋆ − qn = −Fz (xn ) + (xn − x⋆ ) − (z − z ⋆ ) into the reduced utility identity (4.4), and then using (B.1), Lipschitzness of λ, and boundedness of D and the Minty cube (so ∆2 ≤ Cm ∆), gives u(f¯(x⋆ )) − u(f¯(xn )) ≤ Fz (xn ) · (xn − v̄) + Cm ∥xn − x⋆ ∥2 + Cm ∆.
(B.5)
This is the only point at which utility enters the tracking argument. The residual term in (B.5) is not bounded pointwise. Instead, we test the same projected update against v̄, which is feasible by Lemma 4.3. Its prefix sum then telescopes with the increasing weights generated by ηn−1 = n + 1. Because v̄ ∈ D, projection nonexpansiveness also gives, with an = ∥xn − v̄∥22 , Fz (xn ) · (xn − v̄) ≤
an − an+1 + Cm ηn − ξn · (xn − v̄). 2ηn
The last terms are bounded martingale differences, so Lemma A.1 with confidence δ/2 bounds their √ prefixes by Cm N ι. For the weighted telescope, we set a⋆ = ∥x⋆ − v̄∥22 . Summation by parts gives N X
(n + 1)(an − an+1 ) = 2(a1 − a⋆ ) − (N + 1)(aN +1 − a⋆ ) +
n=1
N X
(an − a⋆ ).
n=2
Since |an − a⋆ | ≤ Cm ∥xn − x⋆ ∥2 , the pointwise bound above and (B.4) show that the absolute √ P contribution of the right-hand side is at most Cm (N ∆+ N ι). Hence, using n≤N ηn ≤ C log(N + √ 1) ≤ C N ι, we know that N X
Fz (xn ) · (xn − v̄) ≤ Cm (N ∆ +
√ N ι).
n=1
Summing (B.5) and applying (B.4) proves the claimed prefix bound for every N ≤ T . The two concentration events have joint probability at least 1 − δ.
C
Proof of the Rested-UCB Accounting Lemma
Proof of Lemma 6.2. Write Iz (n) = µ bz (n) + β(n) for n ≥ 1 and Iz (0) = +∞. The two certificates and the lower bound on β(n) imply Iz ◦ (n) ≥ u(f¯(x⋆ )) − Cm ε for every n, including n = 0. Thus every simulator selected by the master has index at least this value. 17
Let Nz be the final number of calls to z. The cases with Nz ≤ 1 cost at most two and are absorbed by the final K term. If Nz ≥ 2, inspect the index just before its last call. At prefix √ Nz − 1, index optimality, reward concentration, and β(n) ≤ Cm ι/ n give N −1
z X 1 ι . u(f¯(xzk )) ≥ u(f¯(x⋆ )) − Cm ε − Cm √ Nz − 1 Nz − 1
k=1
The final call costs at most two because utilities lie in [−1, 1]. Hence simulator z contributes at most √ P Cm Nz ε + Cm ι Nz + C pseudo-regret. Summing over z, using z Nz = T and Cauchy-Schwarz √ √ P √ inequality, z Nz ≤ KT , gives Cm (T ε + ι KT + K). The rested prefixes partition the global rounds and prove the lemma. For unit-bounded contracts, our upper-bound theorem extends the outcome-feedback model of Bacchiocchi et al. (2025a) from finite-action, single-type environments to a substantially broader e 4/5 ). class. For a constant number of actions, they obtain a high-probability regret bound of O(T We remove the finite-action and principal-favoring tie-breaking restrictions, permit fresh heterogeneous types and arbitrary, possibly infinite, action sets, and use a policy that neither enumerates nor identifies actions. For this broader class, our theorems guarantee a sharp expected regret e m (T m/(m+1) ) under any fixed deterministic selected-response convention. Θ
D
Proof of the Matching Lower Bound
Let’s fix m ≥ 2 and 0 < ε ≤ 1/64, and choose v = (1, . . . , 1, 0), J = ⌊(4ε)−1 ⌋, and ρk = [2(m − P 1)(1−kε)]−1 for 0 ≤ k ≤ J. We also set κ0 = 0 and κk = ks=1 sε(ρs −ρs−1 ). For every multi-index P k ∈ {0, . . . , J}m−1 , we can introduce an action ak with pi (k) = ρki for i < m, pm (k) = 1− i<m ρki , P and c(k) = i<m κki . A null action produces outcome m at zero cost. We then fix one deterministic priority order for this common action set and all instances. For a contract f , write xi = fi − fm and ϕk (x) = ρk x − κk . The agent utilities of ak and the P null action are fm + i<m ϕki (xi ) and fm , respectively. Lemma D.1 (Baseline instance). The baseline is a valid finite-action instance with nonnegative costs bounded by one. Adjacent lines ϕk−1 and ϕk cross at kε and a baseline best response using level ki ≥ 1 satisfies xi ≥ ki ε. Its principal utility obeys supf u0 (f ) ≤ 1/2. Proof. Because Jε ≤ 1/4, ρ0 = 1/[2(m − 1)] ≤ ρk ≤ 2/[3(m − 1)], it holds that pm (k) ≥ 1/3. We also have 0 ≤ κk ≤ kε(ρk − ρ0 ) ≤ kερk ≤ 1/[6(m − 1)], whence c(k) ≤ 1/6. The identity ϕk (x) − ϕk−1 (x) = (ρk − ρk−1 )(x − kε) gives the ordered crossings, so level k maximizes the scalar envelope only on [kε, (k + 1)ε], with the natural boundary modifications. Because the action set contains every multi-index and agent utility is additive across coordinates, any non-null best response ak must satisfy ki ∈ argmax0≤s≤J ϕs (xi ) for every i < m. Otherwise, replacing only coordinate ki by a better level would strictly increase the utility. Hence ki ≥ 1 implies xi ≥ ki ε, proving the stated coordinate condition.
18
If the null action is selected, principal utility is −fm ≤ 0. Otherwise, for the selected ak , it holds P that u0 (f ) = i<m ρki (1 − xi ) − fm . When ki ≥ 1, the coordinate condition and ρki (1 − ki ε) = ρ0 give ρki (1−xi ) ≤ ρ0 and when ki = 0, feasibility gives ρ0 (1−xi ) ≤ ρ0 (1+fm ). Since (m−1)ρ0 = 1/2, we obtain u0 (f ) ≤ 1/2 − fm /2 ≤ 1/2. Let L = {2, 4, . . . , 2⌊(J − 1)/2⌋}m−1 . Since ⌊(J − 1)/2⌋ ≥ (16ε)−1 , it holds that |L| ≥ (16ε)−(m−1) .
(D.1)
For l ∈ L, alternative Il lowers only the cost of al by ∆ = ρ0 ε2 /8 = ε2 /[16(m − 1)]. This preserves nonnegativity because ρs − ρs−1 ≥ ρ0 ε implies c(l) ≥ 3(m − 1)ρ0 ε2 > ∆. Let’s now define ( ) X max ϕk (xi ) − ϕli (xi ) ≤ ∆ . Rl = x : (D.2) i<m
0≤k≤J
Q Lemma D.2 (Separated alternatives). If Il selects al , then x ∈ Rl . Moreover, Rl ⊆ i<m [(li − 1/8)ε, (li + 1 + 1/8)ε] and these regions hence are pairwise disjoint. Outside Rl , the alternative selects the baseline response and gives principal utility at most 1/2. Some feasible contract uniquely induces al and gives utility at least 1/2 + γm ε, where γm = 3/[128(m − 1)]. P Proof. The baseline joint-action envelope is fm + i<m maxk ϕk (xi ), whereas the cost reduction raises only al by ∆. Thus selecting al requires (D.2). Note that every deficit in that condition is nonnegative. If xi < li ε, the comparison with level li −1 and ρli −ρli −1 ≥ ρ0 ε gives ρ0 ε(li ε−xi ) ≤ ∆, hence xi ≥ (li − 1/8)ε. Comparison with li + 1 similarly gives the upper endpoint, and this neighbor exists because li ≤ J − 1. Distinct even multi-indices differ by at least two in some coordinate, so their boxes, and therefore their regions, are disjoint. Outside Rl , al lies strictly below the unchanged baseline envelope, so the common priority rule then selects the baseline response, whose utility is at most 1/2 by Lemma D.1. For profitability, let s = ∆/[2(ρl1 − ρl1 −1 )] ≤ ε/16, and choose fm = 0, f1 = l1 ε − s and fi = li ε for 2 ≤ i < m. This contract is feasible. The baseline deficit of al is exactly ∆/2, so after perturbation it uniquely beats every joint action, and the positive scalar envelope also beats the null action. Its principal utility is X
ρli (1 − fi ) = 21 + ρl1 s ≥ 12 +
i<m
3∆ = 12 + γm ε, 8ε
where ρl1 /(ρl1 − ρl1 −1 ) = [1 − (l1 − 1)ε]/ε ≥ 3/(4ε). Lemma D.3 (Adaptive information bound). For any adaptive policy, let PT0 , PTl be its full interP action laws under the baseline and Il , and let Nl = t≤T 1{x(ft ) ∈ Rl } and nl = E0 Nl . Then, it holds that X DKL (PT0 ∥PTl ) ≤ 5ε2 nl , nl ≤ T. (D.3) l∈L
19
Proof. Inside Rl , its positive lower box endpoint ensures that the baseline selects a joint action ak . Scalar optimality and the box imply ki ∈ {li − 1, li , li + 1}. Adjacent slopes then satisfy 0 < ρj − ρj−1 ≤ 2ρ0 ε. If the alternative response differs, it is al . Using DKL (p∥q) ≤ χ2 (p, q), ρli ≥ ρ0 , and pm (l) ≥ 1/3 gives P 2 X (ρk − ρl )2 [ i<m (ρki − ρli )] i i DKL (p(k)∥p(l)) ≤ + ≤ 2ε2 + 3ε2 . ρli pm (l) i<m
Outside Rl , the response laws coincide. The adaptive KL chain rule (Lattimore and Szepesvári, 2020, Lemma 15.1 and Exercise 15.8) now proves the first inequality in (D.3) and policy kernels P cancel. Region disjointness gives l Nl ≤ T pathwise under the baseline and finishes the proof. Proof of Theorem 3.2. By Lemma D.2, we know RT (π, Il ) ≥ γm ε(T − El Nl ). We independently sample a uniform round τ . The Bretagnolle-Huber inequality (Lattimore and Szepesvári, 2020, Theorem 14.2) and Lemma D.3 then imply nl El Nl 2 / Rl ) ≥ 21 e−5ε nl . +1− = PT0 (x(fτ ) ∈ Rl ) + PTl (x(fτ ) ∈ T T 2
Consequently, it holds that RT (π, Il ) ≥ γm ε[(T /2)e−5ε nl −nl ]. Averaging over l and using convexity P together with l nl ≤ T , we obtain 5T ε2 1 1 max RT (π, Il ) ≥ γm εT 2 exp − − . l∈L |L| |L| We set ε = 64−1 T −1/(m+1) . By (D.1), we have 5T ε2 /|L| ≤ 1/4 and 1/|L| ≤ 1/4. Since 12 e−1/4 − 41 > 0, the last display is at least cm T m/(m+1) . Because π is arbitrary and every Il belongs to Im , we have R⋆T (m) = inf sup RT (π, I) ≥ inf max RT (π, Il ) ≥ cm T m/(m+1) , π I∈Im
π
which ends the proof.
20
l∈L
References Auer, P., Cesa-Bianchi, N. and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47 235–256. Bacchiocchi, F., Castiglioni, M., Gatti, N. and Marchesi, A. (2025a). Learning optimal contracts with small action spaces. Artificial Intelligence, 344 104334. Bacchiocchi, F., Gan, J., Castiglioni, M., Marchesi, A. and Gatti, N. (2025b). Contract design under approximate best responses. In Proceedings of the 42nd International Conference on Machine Learning, vol. 267 of Proceedings of Machine Learning Research. PMLR. Chen, Y., Chen, Z., Deng, X. and Huang, Z. (2024). Are bounded contracts learnable and approximately optimal? In Proceedings of the 25th ACM Conference on Economics and Computation. Cohen, A., Deligkas, A. and Koren, M. (2023). Learning approximately optimal contracts. Theoretical Computer Science, 980 114219. Dütting, P., Feldman, M., Ponitka, T. and Soumalias, E. (2025). The pseudo-dimension of contracts. In Proceedings of the 26th ACM Conference on Economics and Computation. EC ’25. Freedman, D. A. (1975). On tail probabilities for martingales. The Annals of Probability, 3 100–118. Grossman, S. J. and Hart, O. D. (1983). An analysis of the principal-agent problem. Econometrica, 51 7–45. Guruganesh, G., Kolumbus, Y., Schneider, J., Talgam-Cohen, I., Vlatakis-Gkaragkounis, E.-V., Wang, J. R. and Weinberg, S. M. (2024). Contracting with a learning agent. In Advances in Neural Information Processing Systems, vol. 37. Guruganesh, G., Schneider, J. and Wang, J. R. (2021). Contracts under moral hazard and adverse selection. In Proceedings of the 22nd ACM Conference on Economics and Computation. Ho, C.-J., Slivkins, A. and Vaughan, J. W. (2016). Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. Journal of Artificial Intelligence Research, 55 317–359. Holmstrom, B. R. (1979). Moral hazard and observability. The Bell Journal of Economics, 10 74–91. Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. Minty, G. J. (1962). Monotone (nonlinear) operators in Hilbert space. Duke Mathematical Journal, 29 341–346. Robbins, H. and Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics, 22 400–407.
21
Rockafellar, R. T. (1976). Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14 877–898. Young, W. H. (1912). On classes of summable functions and their Fourier series. Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 87 225–229. Zhu, B., Bates, S., Yang, Z., Wang, Y., Jiao, J. and Jordan, M. I. (2023). The sample complexity of online contract design. In Proceedings of the 24th ACM Conference on Economics and Computation (EC 2023). Zuo, S. (2024). Harnessing the continuous structure: Utilizing the first-order approach in online contract design. arXiv preprint arXiv:2403.07143.
22