Contract Design Under Approximate Best Responses
Authors: Francesco Bacchiocchi
Jiarui Gan
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: ICML 2025 poster (2025)
Keywords: Principal-Agent
Contract Design
Robustness
Primary area: theory->game_theory

Abstract: Principal-agent problems model scenarios where a principal aims at incentivizing an agent to take costly, unobservable actions through the provision of payments. Such interactions are ubiquitous in several real-world applications, ranging from blockchain to the delegation of machine learning tasks. In this paper, we initiate the study of hidden-action principal-agent problems under approximate best responses, in which the agent may select any action that is not too much suboptimal given the principal's payment scheme (a.k.a. contract). Our main result is a polynomial-time algorithm to compute an optimal contract under approximate best responses. This is perhaps surprising, as computing an optimal commitment under approximate best responses is known to be computationally intractable in Stackelberg games. We also investigate the learnability of contracts under approximate best responses, by providing a no-regret learning algorithm for a natural application scenario where the principal does not know anything about the environment.

Contract Design Under Approximate Best Responses
Francesco Bacchiocchi'
Jiarui Gan Matteo Castiglioni
Alberto Marchesi! Nicola Gatti"
Abstract
Nowadays, principal-agent problems find application in terrific number of real-world settings, such as, e.g., crowd- sourcing (Ho et al., 2014), online labor platforms (Kaynar & Siddiq, 2023), blockchain (Cong & He, 2019), delegation of machine learning tasks (Cai et al., 2015), and pay-for- performance healthcare (Bastani et al., 2016; 2019). More- over, algorithmic contract design is playing a erucial role in today's 's world, which increasingly relies on AI agents to perform complex tasks (see, e.g., (Hadfield-Menell & Hadfield, 2019; Saig et al., 2024)).
Principal-agent problems model scenarios where a principal incentivizes an agent to take costly, un- observable actions through the provision of pay- ments. Such problems are ubiquitous in several real-world applications, ranging from blockchain to the delegation of machine learning tasks. In this paper, we initiate the study of aidden-action principal-agent problems under approximate best responses, in which the agent may select any ac- tion that is not too much suboptimal given the principal's payment scheme (a. contract). Our main result is polynomial-time algorithm compute optimal contract under approximate best responses. This positive result is perhaps surprising, since, in Stackelberg games, comput- ing an optimal commitment under approximate best responses is computationally intractable. We also investigate the learnability of contracts un- der approximate best responses, by providing a no-regret learning algorithm for a natural appli- cation scenario where the principal has no prior knowledge about the environment.
Previous works on algorithmic contract design assume that the agent always plays best-response action to the princi- pal's contract. However, if the agent actually responds (even slightly) suboptimally the principal. then the principal's utility may substantially deteriorate. This may be the case in most of the real-worke applications of interest, for several different reasons. For instance, the principal may not per- fectly know agent's 's features and account for the wrong best response, the agent may not be powerful enough to compute an (exact) best-response action, or they may inaccurately interpret the principal's 's contract.
In this paper, we initiate the study of hidden-action principal- agent problems under approximate agent's 's best responses. Specifically, we consider settings in which the agent may take actions that are up to ó E (0, 1) suboptimal under the principal's contract. We do not make any assumption on the specific 8-best response selected by the agent, but we allow them to take any of such actions. Thus, we take worst-case approach and consider the problem of designing contracts under the assumption that the agent selects the worst å-best response for the principal. Contracts designed in such a way are said to be robust, as they guard the principal against any possible (conceivable) suboptimal behavior of the agent.
1. Introduction
In hidden-action principal-agent problems, a principal tries to steer the behavior of self-interested agent toward favor- able outcomes. The agent has to take a costly action that stochastically determines an outcome resulting in a reward for the principal. The main challenge is that the agent's action is hidden to the principal, who can only observe the realized outcome. Thus, the principal influences the agent's s behavior by committing to a contract, which is an outcome- dependent payment scheme whose aim is to induce the agent to take a high-cost action leading to high principal's rewards. The principal's goal is design an optimal contract, namely one maximizing their utility, i.e., rewards minus payments.
1.1. Results and Techniques
In this paper, we provide an extensive treatment of the com- putational and learnability aspects of the design of robust contracts. The results presented in the paper are organized into three main parts as summarized below.
PPliieenicco di Milano UUniversity of Oxford. Correspondence bacchiocchi @ itl
to: Francesco Bacchiocchi <francesco.bacchocchhi
The Price of Robustness In the first part of the paper, as a preliminary analysis, we provide characterization of the maximum utility that the principal can achieve by means of
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Contract Design Under Approximate Best Responses
robust contracts. Specifically, we provide upper and lower bounds on this utility, function of a parameter å E (0, quantifying the agent's 's best response suboptimality. These bounds give insights on the price (in terms of utility) that the principal incurs for being robust, as the parameter 5 can be seen as a measure of the robustness level of the principal's contracts. Interestingly, our results show that, differently from what happens in general Stackelberg games (see, e.g., (Gan et al., 2023)), upper/lower bounds do not depend on the inducibility gap A > 0 characterizing the problem instance. In order to derive the bounds, we prove that it is possible to convert any non-robust contract into a robust one by properly moving its payments in the direction of principal's rewards, and that, an optimal robust con- tract, which provides the principal with a utility greater than zero, the agent's utility should be at least 8.
contract. Additionally, we show that when the parameter 8 (0, 1) measuring the suboptimality of agent's actions is sufficiently small with respect to the time horizon, our algorithm also achieves sublinear regret with respect to al- ways playing an optimal non-robust contract. Our approach presents some advantages compared to the state-of-the-ar proposed by Zhu et al. (2023) for the non-robust version of the problem, while achieving similar regret guarantees. Indeed, our algorithm employs a simpler discretization of the set of contracts employed by the principal, which does not require that the principal knows its rewards beforehand. This is made possible by the fact that we rely on novel "continuity" argument for the principal's expected utility (see Lemma 3), which is different from the one originally proposed by Zhu et al. (2023).
1.2. Related Works
Computing Robust Contracts The second part of the paper addresses the problem of computing a robust contract that is optimal for the principal. Our main contribution is a polynomial-time algorithm for this problem. This perhaps surprising, since analogous problems in Stackelberg and Bayesian persuasion settings are known to be computation- ally intractable (Gan et al., 2023; Yang & Zhang, 2024), despite having more amenable solution spaces (Am in these problems vs. RT in contract design). At high level, our algorithm cleverly exploits a particular structure that we discover in the robustness constraints (which ensure that the agent plays the worst approximate best response for the principal). Intuitively, we show that, when the agent's best response and their (worst) approximate best response are fixed to two arbitrarily-selected actions, the problem robust contract can be
Robustness to Approximate Best Responses Two works that are closely related to ours are (Gan al., 2023; Yang & Zhang, 2024), which consider robustness notions analogous to ours, though in different settings. Specifically, Gan et al. (2023) initiate this research line, by studying th problem of computing robust leader's s commitments in Stackelberg games where the follower plays an approximate best re- sponse. They show that it is NP-hard to approximate an optimal robust commitment of the leader and, in accordance to this hardness result, they provide approximation scheme (QPTAS). Yang & Zhang (2024) ex- tend the study initiated by Gan et al. (2023) to Bayesian persuasion, with the goal of computing robust signaling schemes under approximate best responses of the receiver. Similarly to Gan et al. (2023), they show that computing an approximately-optimn robust signaling scheme NP-hard and provide a QPTAS. In sharp contrast with these works, we show that, in hidden-action principal-agent problems, an optimal robust contract can be computed efficiently.
cousi-polynomial-tin
of computing a formulated by means of a union of + 1 different linear programs (LPs). Therefore, by taking the maximum over all these LPs, one can compute a utility-maximiiing robust contract once the agent's 's best response and their (worst) approximate best response are fixed. By further iterating this procedure for all the possible choices of the action pair, we then determine an optimal robust contract.
Contract Design Contract theory has been extensively studied in economics (Holmstrom & Milgrom, 1991). How- ever, the interest in its computational aspects is more re- cent. Dütting et al. (2019) analyze linear contracts, prov- ing approximation bounds. Guruganesh et al. (2021); Cas- tiglioni et al. (2022a;b) study the computational aspects of contract design in Bayesian settings. Alon et al. (2023) study Bayesian linear contracts, proving near-optimality under sufficient uncertainty. Other works explore combina- torial principal problems (Babaioff et al., 2006; 2009) and multi-agent extensions of hidden-action problems (Cas- tiglioni et al., 2023; Ductting et al., 2024).
Learning Robust Contracts In the third and last part of the paper, we investigate the learnability of robust contracts. Specifically, we study an online learning framework simi- lar to the one analyzed by Zhu et al. (2023), in which the features of agent's 's actions, i.e., costs and probabilities over outcomes, depend on an agent's type that is sampled at each round from some (fixed) unknown probability distribution. At each round, after committing to some contract, the prin- cipal only observes the outcome (and its associated reward) realized as an effect of the approximate best response played by the agent. Our main result within this online learning framework is the design of an algorithm that achieves sublin- ear regret with respect to always playing an optimal robust
Other Forms of Robustness in Contract Design Our work is also related to other research lines addressing differ- ent concepts of robustness in contract design. For instance,
2

---

Contract Design Under Approximate Best Responses
Carroll (2015) studies settings where the principal only knows a superset of agents' actions, while Dütting et al. (2019) introduce different notion of uncertainty in which the principal has partial knowledge of the distributions over outcomes associated with agent's actions. Both these works show that linear contracts are a sufficient class of contracts to determine the min-max robust optimal contract. Notice that these two frameworks differ from ours, as within our frame- work, when the robustness parameter 5 E (0. 1) is arbitrarily small, the problem becomes very close to the classical ver- sion of the hidden-action principal-agent problem, in which it is known that linear contracts are not generally optimal (see, e.g., (Dütting et al., 2019)). Recently, Bernasconi et al. (2024) study settings where uncertainty lies in the costs of agent's actions. In this framework, the principal only knows a set containing the true cost vectors, and computing an optimal min-max robust contract is APr-hard.
representing the effects of agent's action, r E [0, 1] is reward vector for the principal, and E [0. 1|" is vector of agent's costs. Each agent's action a E A determines a probability distribution over outcomes, encoded by a column Fa E A of the matrix F, and it results in a cost for the agent, encoded by a component Ca E [0, 1] of vector c.' We denote by Fe, E [o, 1] the probability with which action a results in outcome w 52, as prescribed by Fa. Thus, must be the case that Ewer Fu,.-
for all A. Each outcome E Q is associated with a reward for the principal, encoded by component To E [0, 1] of the vector r. Thus, whenever the agent selects an action a E A, the principal's expected reward can be computed as Ra == Fa rr.
The principal commits to an outcome- dependent payment scheme called contract, which is vector p RT defining payment Pa 2 0 from the principal to the agent for every outcome E 22.3 Given a contract E RT. the agent plays best-response action that is: (i) incentive compatible (IC), which means that it maximizes their expected utility; and (ii) individually rational (IR), meaning that it has non-negative expected utility. We assume w.l.o.g. that there always exists at least one opt-out action a E AA with null cost, i.e. Co O. and for which the principal's expected reward is equal to zero, i.e., Fa T O. Since the agent's 's utility is at least zero when playing the opt-out action, any IC action is also IR, allowing us to focus on incentive compatibility only.
Learning in Principal-Agent Problems Our work is also related to online learning problems in hidden-action principal-agent problems. Zhu et al. (2023) study general hidden-action principal-agent problem instances in which the principal faces multiple agent's 's types. They show that it is possible to design an algorithm that achieves a regret bound of the order of Ō( /mm 71-1/(2++1) when the prin- cipal selects contracts from the hypercube [0, 1]mm. where m is the number of outcomes. In our work, we show that it is possible design an algorithm achieving similar re- gret guarantees even when the different agent's types select approximate best responses. Our algorithm presents some advantages compared to the one proposed by Zhu et al. (2023). Specifically, our approach employs a simpler dis- cretization of the dypereube-usee during the execution of the algorithm- comppredd to (Zhu et al., 2023), and it does not require prior knowledge of the principal's 's rewards. Fur- thermore, Zhu al. (2023) provide (almost- mattongg lower bound of ((T=21/(m+2),, ). which holds even with single agent's 's type. Some recent works have introduced additional hypothesis to overcome this negative result (see, e.g., (Bacchiocchi et al., 2024; Chen et al., 2024)).
Whenever the principal commits to a contract E ET and the agent responds by playing an action a E A, the agent's and the principal's 's expected utilities are, respectively,
u (A( a) == Fa p Ca: and u (p, a) == F. (r - p).
The set A(p) S. A of agent's best responses in a contract p E RT is defined as follows:
A(p) arg max (Fo PF.-p-C ca)- aEA
In classical (non-robust) aaddennaction principal-agent prob- lems, the agent breaks ties in favor of the principal when having multiple best responses available (see, e.g., (Dütting et al., 2019)). We denote by a(p) E A(p) the action played by the agent in a given contract E IRT This is an action a E A(p) that maximizes the principal's 's utility Fa (r - p). Formally, a(p) E arg max Fa (r - p). Then, the goal of the principal is to design a contract p E IR that max- imizes their expected utility u? (p, a(p)). We say that con- tract p" E RT is a (non-robust) optimal contract if it holds p* E arg maXpeRp u((p, a(p)). In the following, we define
2. Preliminaries
In this section, we first introduce the classical codden-action principal-agent problems (Section 2.1), and then the vari- ation studied in this paper, in which the agent plays an approximate best response (Section 2.2).
2.1. Hidden-Action Principal-Agent Problems
'We denote by Ax the set of all prohability distributions over the set X. Giienn n E Nso. we write [n] == {1,...,n) n...
An instance of hidden-action principal-agen problem is characterized by a tuple (A, S, F,r, r, c), where A is a finite set of n = |A| actions available to the agent, 2 a finite set of mm= = [ possible outcomes, F E [0, 1] [ is a matrix
"We denote by x: y the dot product of two vectors J. y E Rd. "As customary in contract theory (Carroll, 2015), we assume that the agent has limited liability, meaning that the payments can only he from the principal to the agent, and not viceversa.
3

---

Contract Design Under Approximate Best Responses
the principal's utility in an optimal (non-robust) contract as OPT maxperT uP (p, a(p)), while we let the value of the social welfare be SW == m {Fa r- C
measure of the robustness level of the principal's contract, with higher d values indicating higher levels of robustness.
We first establish upper and lower bounds that identify a suitable region in which the values of (6) are contained. Such bounds only depend on the parameter 5 E (0, 1), the value of an optimal non-robust contract OPT, and the social welfare SW achievable with non non-robust contracts.
2.2. Robust Contracts and Approximate Best Responses
In this paper, we study a variation of the classical hidden- action prineppal-aget problem, where the agent plays an ac- tion that is an approximate best response. Given å (0, 1), we define the set A S A of agent's ô-best responses in a given contract E T as follows:
Proposition 1 (Upper and lower bounds). Given an instance of hidden-action principal- agent problem:
1. For every 8 E (0, 1), it holds:
1 (0))) = a a Ca max a'EA
(00==(aE
(Fa Cxr )
OPT(6) 2 (6) = -PT-2V0
2V8 +
We adopt an adversarial robust approach, in the sense that, whenever the principal commits contract p E RT the agent selects a ō-best response that minimizes principal's expected utility, namely action a (p) E (p) such that a (p) E arg min (p) Fa (r p). We refer to the utility of 5-robust contract p as uP (p)).
2. For every 8 E (0, it holds:
(6) S (P) == max {0, SW 53.
In order to prove the first point in Proposition 1, we show that it always possible to convert non-robust contract into robust one by suitably moving it towards the direction of the principal's reward vector. In order to prove the second point of Proposition 1, we observe that, if an optimal 8- robust contract p" provides the principal with an expected utility strictly larger than zero, then the opt-out action does not belong to the set of 8-best responses for such a contract. Therefore, in an optimal 5-robust contract that provides the principal with an expected utility strictly larger than zero, the agent's 's utility is at least ō > 0, and thus the principal's expected utility is at most SW 5.
Given ò E (0, 1), the principal's goal is to design an optimal 5-robust contract p" E RT, which is formally defined as:
p¹ E arg max min u (p, = arg max (p), PER" ap)*(p)
PERT
where (p) = minae o (p,a) denotes the principal's expected utility in a 5-robust contract E TeT. Notice that analogous "ő-robust solution concepts" have been al- ready introduced in similar settings, namely Stackelberg games (Gan et al., 2023) and Bayesian persuasion ( (Yang& & Zhang, 2024). Our 6-robust contracts are their analogous in the context of hidden-action principal-agent problems.
The following proposition shows that the upper and lower bounds in Proposition 1 are tight. Formally:
Proposition 2. Given 8 (0, 1), for every integer n > n(6), there is an instance of fidden-action principal- agent problem (parametrized by 8) with 2n 1 actions, where:
In the following, given 8 E (0, 1), we denote the expected utility of the principal in an optimal d-robust contract p* as OPT( == u (p", a (p*)). We remark that OPT(a) is always well defined, as an optimal d-robust contract, accord- ing to the definition in Eq. (I), always exists. Intuitively, this is due the strict inequality in the definition of the set A (p), as observed by Gan et al. (2023) for Stackelherg games. Thus, in order to prove the existence of an optimal 5-robust contract, it is possible to employ the same argument used to prove Proposition 1 in (Gan et al., 2023).
OPT(6) - (0) S (
Furthermore, for any d E (0, 1), there exists an instance of Aidden-action principal- aggnt problem in which it holds:
OPT(6) = OPTuB(().
Proposition 2 shows that our upper bound OPTUB is (strictly) tight, while our lower bound OPT (8) is tight up to an additive term that linearly goes to zero as the number of agent's 's actions n increases.
3. The Price of Robustness
We start by providing a characterization of how the value OpT()) of an optimal 8-robust contract varies as a function of the parameter 5 E (0, 1), which controls the suboptimal- ity of the agent's 's best response. The goal of our analysis is to quantify how much is the price (in terms of utility) that the principal incurs for being robust to agent's 's approximate best responses. Indeed, the parameter 8 can be interpreted as
Finally, thanks to the previous propositions, we can show the following property about the value of optimal 8-robust contracts as function of 5 E (0, 1).
Proposition 3. The function (0,1) 3 8 + OPT(8) is continuous and non inniiccreasing in 6. Moreover, lim6-20 OPT(8) = OPT and lim OPT(8)

---

Contract Design Under Approximate Best Responses
optimal 8-robust contract y", as well as two arbitrary ac- tions a² E A(p') and a arg min u (p", a). By fixing a" and a", we show that the following optimization problem, over the variable p E RR,, characterizes an optimal 8-robust contract
())
SW = 0.9
OPT = 0.7
max
u <p(pa')
(2)
PERT
1 6
subject to the following disjunctive constraints, which must hold for every agent's action E A:
Figure 1. The blue area corresponds to the region in which (6)
is bounded as function of 5 E (0, 1) in instance of hidden-
(2a)
action principal-aged agent problem with SW = 0.9 and OPT = 0.7.
Intuitively, Eq. (2a) requires that each action a is either not ô-best response (first inequality) or no worse than a for the principal (second inequality). This ensures that the objective function u (p, a²) captures the principal's is utility in a 8-robust contract p. More formally, we establish the following lemma (recall that (p) = minae (p)) u (p, a) denotes the principal's 's utility in a 8-robust contract p).
Figure I shows an example of the region in which the value of OPT(5) is bounded, as defined by the lower and upper bounds in Propositions and as functions of 8.
The characteri- zation results derived in this section exhibit some crucial differences compared analogous results derived for Stack- elberg games by Gan et al. (2023). Indeed, in such settings, Gan et al. (2023) show that the value of an optimal 8-robust commitment crucially depends on a parameter A > 0 that represents the inducibility gap of the problem instance. In- tuitively, the inducibility gap encodes how easy it is for the leader to induce the follower to play any action; see (Gan al., 2023) for formal definition. Specifically, in Stack- elberg games, the leader's ss expected utility OPT()) in optimal 6-robust commitment is a Lipschitz function lower bounded by OPT - / if 8 < A, whereas OP)()) may not be even a continuous function if ó > A. In contrast, in hidden-action principal-agent problems, the value of an optimal 6-robust contract is a continuous function with re- spect to 8 E (0, 1), regardless of the inducibility gap of the instance. Furthermore, the value of (ō) )) is either zero or it is upper bounded by SW - 8, showing that for large val- ues of 6, the maximum utility that the principal can achieve may be particularly small. Intuitively, this is because the principal must provide the agent with a large expected pay- ment to induce them to take desirable actions rather than the opt-out one. This upper bound does not generally hold in Stackelberg games in which the principal may achieve large utility even for large values of 6.
Comparison With Stackelherg Games
Lemma 1. Every optimal solution E I to Problem (2)
is an optimal 5-robust contract, i.e., (p) = (p").
Proof. First, observe that p" is a feasible solution to Prob- lem (2). Indeed, if an action a not a 8-best response to p", then by definition this means (p"p, a) S. u "p"p a²) 8; otherwise, it must be that uP (p", aa) 2 up (p", a²) as a is by definition the worst 5-best response in p". As a result, Eq. (2a) holds for p for every E A.
Furthermore, notice that, according to the definition of a
V (ip') = min u ((",a) = u (p", a²) aEAs(p")
In order complete the proof, it is sufficient to show that uP (p,a²) < (p)) for every feasible solution p E RT to Problem (2). Indeed, if the condition above holds, for any arbitrary optimal solution p' E TRT to Problem (2), we have:
(F") =u
up (v", a²) Su V' a²) S (ppp)) S (pp'),
where u up d²) S up(p,, a²) since p* is a feasible solu- tion to Problem (2) and p' is optimal, while V S (pp") since p" is an optimal d-robust contract by definition. Then, it must be the case that V(z') (y(').
4. Computing Optimal Robust Contracts
Now, to complete the proof, consider any feasible solution p E RT to Problem (2). We show that u (p, a²) < (p)). Pick an arbitrary best-response action a' E A(p) and con- sider any a E A (p). By definition,
Now, we present our main result: a polynomial-timg algo- rithm to compute an optimal 8-robust contract.
4.1. Characterizing an Optimal Contract
" ^ (p. > u a')- 8
We begin by presenting an optimization problem that char- acterizes an optimal 8-robust contract. Consider an arbitrary
= max v (p. - ö 52 u"(ppa""- -8. .EA
5

---

Contract Design Under Approximate Best Responses
Hence, for Eq. (2a) to hold for action a, it must be that u (p. a) 2 uP (p, ).). Since the choice of a is arbitrary, this holds for every E (p). Consequently,
well-structured, since the hyperplanes corresponding the inequalities are parallel, as the coefficients of p in Eq. (4)
are invariant with respect space into only (n) subspaces.
As a result, they partition the
(p) min n (p, 2 u (p,aa) (E)
Next, we show how to exploit the above observation to solve Problem (2), by solving (n) suitable subproblems instead.
The above lemma implies that we can effectively "guess" at and a", fixing these actions in Problem (2) and solving the optimization problem to obtain p* (or possibly a different, but still optimal, å-robust contract). Since there are only Onn²) possible combinations of the values of a* and a², the approach is efficient as long as Problem (2) can be solved efficiently. A correct guess yields a contract p such that (p) (p"), whereas (p) < (p") for incorrect guesses. Thus, by comparing the V values, can identify correct guess and a corresponding optimal 6-robust contract. It remains to show how to efficiently solve Problem (2).
4.3. Formulating the Subproblems
Let us first rearrange Eq. (4) as follows:
(p, a²) + u (p, (n,aa) 5 S un =a Ca:
(5)
where v. is exactly the social welfare generated by action (which is independent of the specific contract adopted).
Then, we can re-order agent's 's actions d,,..., On in such a way that Vaz S VVag S ... S Va., For simplicity, we write Vj = Vay, and we let Vu = -00 and Vn+1 = toc. Then, the following lemma straightforward.
4.2. Solving Problem (2)
Lemma 2. For every contruct p E RT, if it holds that Vj-1 S u (p, a²) + u (p, - S Vj, then:
Problem (2) does not directly admit any efficient solution algorithm due to the non-convex constraint in Eq. (2a). To deal with this issue, we rewrite Eq. (2a) as follows:
Fa PappS S Fa . r u (p.a²) = Eq. (3) holds for all actions a E {ae l S 1}: and
(F. + (p, t
- -6)
Fo p S ca + (p,
+ Eg. (3) holds for all (p. a²
actions a E fae 1i E..
(Fo Fo r
r F (p.aa))
(3)
In other words, the condition in the lemma defines a suitable subspace of contracts P, for each E fl..... n + 1}. The following LP solves for ap E RTT that optimal within P,.
by expanding the utilities as (p, a) Fa p- Cu and u (p. a) Fa (r- p) and rearranging the terms.
Hence, Eq. (2a) is satisfied for action E A if and only if Fa p is smaller than the maximum of the right-hand sides of the two inequalities in Eq. (3). The constraint effectively reduces to the second inequality for all p E RT such that
max PER
u dp,aa)
(6)
subject to the following constraints:
Ca u a²) - 8 F. . u (p,aa)
(4)
"j- S (p, (p,aa") ( -85
(6a)
Fa Fa r ap, V far l S j-1 (6b)
while for the other E IR,,, reduces to the first inequality.
Fa.p S co + (p,
- aa (ar 1j < f). (6c)
Consequently, can partition the contract space based the satisfiability of Eq. (4), considering all A. Within each subspace in the partition, only one inequality in Eq. (3) is active for every a E A. So, effectively, Eq. (3) reduces to a linear constraint for each action a, and the optimiza- tion problem to an LP. then suffices to solve an LP for every subspace, each generating an optimal contract within its corresponding subspace. Among these contracts, the one providing the highest utility is optimal solution to Problem (2).
Since U P3 RT. solving the LP in Problem (6) for all
n f1....,, 11 and picking the best among the obtained solutions gives an optimal solution to Problem (2).
Remark 1. The left- hend side of Eq. (5) is roughly (up to 5 difference) the social welfare of an optimal contract. Thus, Lemma 2 can be interpreted as follows. For low- soeial-welfare actions aI,..., Uj- yielding sufficiently high utility for the principal automatically provides a low utility for the agent. This fulfills the first inequality in Eq. (3) (and Eq. (2a)). Conversely, for high-social-welfare actions aj.... ... On,, sufficiently low utility for the agent automatically gives high utility for the principal. This fulfills the second inequality in Eq. (3) (and Eq. (2a)).
Now, if the linear inequalities in Eq. (4) (one for each action a E .) were n arbitrary inequalities, the above partition may consist of exponentially many subspaces, making the approach inefficient. Fortunately, the partition is much more
6

---

Contract Design Under Approximate Best Responses
Algorithm 1 Compute an optimal 8-robust contract
Fe.a and cg.a denote the probability distribution over out- comes and the cost, respectively, of action E A, when the agent has type 0 E O. The agent's s type is drawn from an unknown probability distribution À E Ae, with Ag E [0, 1] being the probability of type E θ. We extend all the notation introduced in Section to account for agent's types. Specifically, given 5 E (0, 1), we let A (p))pp) C A be the set of ô-best responses to contract p E RT for type O. Moreover, we denote by (p) the 5-best response that is played by the agent under a d-robust con- tract, namely the worst one for the principal. Formally, a (p) E arg minee Feja (r p). Similarly, we use (p) and (p) for (exact) best responses. Finally, the principal's is expected utility when committing to contract E FT against an agent of type E θ playing an action a E A is uP (p, a, 0) = Fe.a (r pr-p) p).
1: p" f- null, 1² f- -0
2: for all (a* a²)
E A x do
3: for all j 1, ................................ n+1 do
4:
Solve Problem (6) instantiated with (a",a") s.t.
Eqs. (6a) to (6c), and let an optimal solution be p'
5:
if (p') > 2b* then
6:
pd + p'
7:
66* < (p')
8: return p*
4.4. Putting All Together
We summarize our results this section into Algorithm and the following main theorem.
Theorem 1. Algorithm/ I computes an optimal 5-robust contract in polynomial time.
We study an online learning framework in which the prin- cipal and the agent repeatedly interact over T 0 rounds. Each round involves repetition of the same instance of hidden-action principal-agent problem, with only the agent's s type changing from round to round. Specifically, at each round L E [T]. the principal-agent interaction is as follows:
Proof Sketch. The polynomial runtime of Algorithm 1 is obvious as it enumerates (nn)) value combinations and solves an LP for each of them. To see the correctness of the algorithm, note that the inner for-loop of Algorithm effec- tively solves Problem (2), for the pair (a* ,a²) enumerated in the outer for-loop. Now, if a and a happen to be the agent's 's exact and 5-best responses, respectively, under some optimal contract, then according to Lemma 1, the outer loop produces an optimal contract p'. with (p') 2 (p)) for all p E I.T. By comparing the values, the algorithm identifies and outputs such an optimal contract.
1. The agent's type H E θ is sampled from the distribu- tion A. Notice that 6* is not observed by the principal.
2. The principal commits to contract p¹ C = [0, 1]mh.
3. After observing the contract p', the agent plays a d-best response a' = a 'pp).. Notice that the action af is not observed by the principal.
5. Learning Robust Contracts
4. The principal observes the outcome wf ~ Fat that is realized as an effect of the agent's action a².
The algorithm in Section 4 works under the assumption that the principal has full knowledge of all the payoff-relevant information about the agent and, thus, they can compute an optimal 5-robust contract. In this section, we address the case in which the principal has no such knowledge, and, thus, they have to learn an optimal 6-robust contract in online fashion, by repeatedly interacting with the agent.
We remark that, in the interaction described above, the prin- cipal's I's contract design space is assumed to be limited to the hypereube C [0. 11mh. Restricting the contract space to a bounded set is standard in the literature online learning in contract design (sce, e.g., (Ho et al., 2014; Zhu et al., 2023; Chen et al., 2024)) and it is motivated by the negative result proved in Theorem in (Bacchiocchi et al.. 2024). Therefore, we need to introduce a formal definition of the principal's s expected utility when committing to an optimal 8-robust contract restricted such a space. Formally:
5.1. Learning Interaction
We consider an online learning framework similar to the one studied by Zhu et al. (2023), in which the features of agent's s actions, i.e., costs and probabilities over outcomes, depend on an agent's type that is sampled at each round from some (fixed) unknown probability distribution. Before formally defining the online learning framework, we introduce some notation that is needed to deal with hidden-action principal- agent problems in which the agent can be of different types.
OPT 8) == max Σ OEG
dau (p, a 0.6 (p).)))
PEC
The goal of the principal is to minimize the (cumulative) pseudo-regret, or simply regret, which can be defined as:
Hidden-Action Principal-Agent Problems With Types We let θ be the finite set of possible agent's 's types, while
Rr(C.,)=T
Exou
[E(T),
7

---

Contract Design Under Approximate Best Responses
Algorithm 2 Regret minimizer for d-robust contracts
Require: T> 0
where the expectation is over the randomness of the al- gorithm and the environment that generates the feedback received by the learner at each round. Our goal is to design no-regret algorithm for the principal, namely one achieving Rr(C, 5) = (T))
1: Set e <- T m41
2: Be t {p E [0, Pa E (0, .c,,,.... 1) vu E 22
3: Run UCB1 with B, as set of arms
similar to those obtained by Zhu et al. (2023) in the non- robust version of the problem. Indeed, they achieve an upper bound of the order of (mm wtt.mmmm//////// 1) on the regret.
5.2. A No-Regret Algorithm
Before introducing our no-regret learning algorithm (Algo- rithm 2), we need to prove a key lemma about the "continu- ity" of the principal's s expected utility over the hypercube. In particular, given a 8-robust contract p E R7, we show that is possible build another contract p' T& that is (6 + c)-oouust and provides the principal with utility at most 2/2 worse than the one of contract p. Formally:
Finally, we also show that, when the parameter 8 (0, is sufficiently small (with respect to the time horizon T > 0), Algorithm 2 achieves sublinear regret with respect to an optimal non-robust contract within C. Formally, we define the value of such a contract as follows:
OPT(C) == max Σ PEC
sou (p. a (p).
Lemma 3. Given any 8, E (0, 1) and contract p E RR., the following holds for every 0 E O:
AE
Furthermore, when OPT(C) is chosen as baseline, the regret definition becomes the following:
"''', a 2..5+..p)) (''s++(p'))))) u (p -2VE,
where p' = (1- Ver.
= TOPT() -E
Non'rr a [EE(T)
We observe that the idea of shifting payments towards the principal's reward vector, as in Lemma 3, was first adopted by Dutting et al. (2021) in non-robust settings, in order to deal with approximately incentive-compatibe contracts.
where the expectation is over the randomness of the al- gorithm and the environment that generates the feedback received by the learner each round. We observe that the baseline in the regret definition above coincides with the one introduced by Zhu et al. (2023). Then, we can prove that the following corollary of Theorem 2 holds.
Thanks to Lemma 3, it is possible to show that there always exists a contract p E B. that satisfies the following condition, where B, C C is a uniform grid of the hypercube C, built with step size > 0 (see also Algorithm 2).
Corollary 1. The regret suffered by Algorithm can be upper bounded as follows:
Σ Xou'(n (p. 1o.a" (p) > A
RT(C) S SO (TTT + 2V8T.
Consequently, by suitably choosing 0 as a function of the time horizon T, and by instantiating no-regret algo- rithm with set of arms Be, we can upper bound the regret suffered by Algorithm 2 as follows.
We remark that, if we set 8 = 1/2"d with > 0 in Corol- lary 1, then the regret with respect to an optimal non-robust contract within the hypercube C is sublinear.
Theorem 2. The regret suffered by Algorithm 2 can be upper bounded as follows:
Remark 2. Our algorithm can be extended to deal with settings in which the agent can play any 5-best response within the set A & (p'). In such setting, the principal's utility is not fully stochastic. However, our Algorithm can be easily extended by instantiating an adversarial no-regret algorithm instead of UCB1 (Auer et al., 2002).
Rr(C, 5) S 5 )(ल.))) (TTT))))))
We remark that the regret lower bound introduced by Zhu al. (2023) also holds in our setting. This is because, when the parameter is arbitrarily small, if we consider the same instances used by Zhu et al. (2023) in their lower bound, the principal is still required to enumerate an exponential number of regions, thus suffering (2(T11/(m+2) regret. This confirms that an exponential dependence on the number of outcomes is unavoidable in the regret suffered by any algorithm. Furthermore, Theorem shows regret guarantees
Comparison With (Zhu et al., 2023) We observe that our algorithm provides some advantages compared to the state- of-the-art algorithm proposed by Zhu et al. (2023). First, our approach employs as set of contracts a simple discretization of the hypercube, while the approach by Zhu et al. (2023) requires determining the minimum set of contracts VC for some suitable 6 > 0 such that, for every p E C, there
8

---

Contract Design Under Approximate Best Responses
exists p' E Ve (C) that satisfies (r-p) .p' cos(e). How- ever, the need of designing such of contracts makes the approach by Zhu al. (2023) challenging to be employed in practice compared to ours. Second, our algorithm does not require apriori knowledge the principal's reward, which instead required by the algorithm of Zhu et al. (2023).
in pay-for-performance programs. Management Science, 65(3):1042-1060, 2019.
Bernasconi, M., Castiglioni, M., and Marchesi, A. Regret- minimizing contracts: Agency under uncertainty, 2024, URL httph::t/////.
Cai, Y., Daskalakis, C., and Papadimitriou, C. Optimum statistical estimation with strategic data sources. In Con- ference on Learning Theory, pp. 280-296. PMLR, 2015.
Acknowledgments
This work was supported by the Italian MIUR PRIN 2022 Project "Targeted Learning Dynamics: Computing Efficient and Fair Equilibria through No-Regret Algorithms", by the FAIR (Future Artificial Intelligence Research) project, funded by the NexIGenerationFUU program within the PNRR-PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101120237).
Carroll, G. Robustness and linear contracts. American
Economic Review, (05(2):536-56)) 2015.
Castiglioni, M., Marchesi, A., and Gatti, N. Bayesian agency: Linear versus tractable contracts. Artificial Intel- ligence, 307:103684, 2022a.
Castiglioni, M., Marchesi, A., and Gatti, N. Designing menus of contracts efficiently: The power of randomiza- tion. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 705-735, 20222..
Impact Statement
Castiglioni, M., Marchesi. A., and Gatti, N. Multi-agent contract design: How to commission multiple agents with individual outcomes. In Proceedings of the 24th ACM Conference on Economics and Computation, pp. 412-448, 2023.
This paper presents theoretical results and has the goal of advancing the field of Machine Learning. There are no potential societal consequences of work which feel must be highlighted here.
Chen, Y., Chen, Z., Deng, X., and Huang, Z. Are bounded contracts learnable and approximately optimal? arXiv preprint arXiv:2402. 14486, 2024.
References
Alon, T., Duetting, P., Li, Y., and Talgam-Cohent I. Bayesian analysis of linear contracts. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, pp. 66, 2023.
Cong. L. W. and He. Blockchain disruption and smart contracts. The Review of Financial Studies, 32(5): 1754 1797, 2019.
Auer, P., Cesa-Bianchi, N., and Fischer, Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-255 2002.
Duetting, P., Ezra, T., Feldman, M., and Kesselheim, T. Multi-agent combinatorial contracts, 2024.
Dütting, P., Roughgarden, T., and Talgam-Cohent I. Simple versus optimal contracts. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 369-387, 2019.
Babaioff, M., Feldman, M.. and Nisan, N. Combinatorial agency. In Proceedings of the 7th ACM Conference on Electronic Commerce, pp. 18 18-28, 2006.
Babaioff, M., Feldman, M., and Nisan, N. Free-riding and free-labor in combinatorial agency. In International Symposium on Algorithmic Game Theory, pp. 109-121. Springer, 2009.
Dutting, P., Roughgarden, T., and Talgam-Cohen, I. The complexity of contracts. SIAM Journal on Computing, 50(1):211-255 2021.
Dütting, P., Feldman, M., Talgam-Cohen, I., et al. Algorith- mic contract theory: survey. Foundations and Trends@ in Theoretical Computer Science, 16(3-4):211 13:211-412,,, 2024.
Bacchiocchi, F., Castiglioni, M., Marchesi, A., and Gatti, N. Learning optimal contracts: How to exploit small action spaces. In The Twelfth International Conference on Learning Representations, 2024.
Gan, J., Han, M., Wu, J., and Xu, H. Robust stackel- berg equilibria. In Proceedings of the 24th ACM Con- ference Economics and Computation, EC '23, pp. 735, New York, NY, USA, 2023, Association for Com- puting Machinery. ISBN 9798400701047. doi: 10. 1145/380000733397660,, URL https: httt://oooo/////// 10. 05.11455/380507..00
Bastani, H., Bayati, M., Braverman, M., Gummadi, R., and Johari, R. Analysis of medicare sor--foorpeffrmance contracts. Available at SSRN 2839/43, 2016.
Bastani, H., Goh, J., and Bayati, M. Evidence of upcoding
9

---

Contract Design Under Approximate Best Responses
Guruganesh, G., Schneider, J., and Wang, J. R. Contracts under moral hazard and adverse selection. In Proceed- ings of the 22nd ACM Conference Economics and Computation, pp. 563-582, 2021.
Hadfield-Menell, D. and Hadfield, G. K. Incomplete con- tracting and ai alignment. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 417-422, 2019.
Ho, C.-.,, Slivkins, A., and Vaughan, J. W. Adaptive con- tract design for crowdsourcing markets: Bandit algo- rithms for repeated principal-agent problems. In Pro- ceedings of the Fifteenth ACM Conference on Economics and Computation, EC 14, pp. 359-376, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450325653, doi: 10. (01111660000077222288888
Holmstrom, B. and Milgrom, P. Multitask principal-agent analyses: Incentive contracts, asset ownership, and job de- sign. The Journal of Law, Economics, and Organization, (ispecial.issue)22444 1991.
Kaynar, N. and Siddiq, A. Estimating effects of incentive contracts in online labor platforms. Management Science, 69(4):2106-2126, 2023.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Saig, E., Einav, O., and Talgam- Talgam-Cohen Cohen, Incentivizing quality text generation via statistical contracts, arXiv preprint arXiv:2406.1 18, 2024.
Yang, K. and Zhang, H. Computational aspects of bayesian persuasion under approximate best response. arXiv preprint arXiv:2402.07426, 2024.
Zhu, B., Bates, S., Yang, Z., Wang, Y., Jiao, J., and Jordan, M. The sample complexity of online con- tract design. In Proceedings of the 24th ACM Con- ference on Economics and Computation, EC '23, pp. 1188, New York, NY, USA, 2023. Association for Com- puting Machinery. ISBN 9798400701047.
doi: 10. 1145/358050733397773. URL https: orgg/ 10. 10.1445/350007.335777
10

---

Contract Design Under Approximate Best Responses
Appendix
Proposition 1 (Upper and lower bounds). Given an instance of hidden-action aggnn problem:
1. For every (0,1), it holds:
OPT(O) 2 ( = OPT -
2. For every (0,1), it holds:
OPT(6) OPT max {0, SW -8..
Proof. We prove the two points separately.
1. Let = (1 - (1-v + Vör for any contract E R We start by observing that the following inequality holds:
E PP - cu(p)
Fat (ad(p))
because app) E A(p). Furthermore, we have:
Σ Fot Fo Cof(p") > max Σ
Far - Co' -
Σ
Fa(p Ca(p) 6,
a' A' WER
WER
wEl
thanks to the definition of A (p'). Then, by employing the two above inequalities and the definition of p', we have:
6 m Σ Palp Calp)
Σ
Fat cad(rr)
WEB
wEn
Σ
Pa Ca(p) Σ
Fat Cal(or) v8
Σ (Falp) Fal(r) (rw Dw)
2 v Σ
(Falp). - (p)( (rw Pw)
WEn
Thus, by rearranging the latter inequality we get:
Σ (Fale) Pw)( (ru pu) n.))
Vo
Finally, we can show that:
u' (p, - = Σ (rw -Pw) - Σ
Fo - Plo)
wen
wen
Σ (rw -pw) - vá-
E Earerss Pw)
wen
Wen
$ (1-V8)
Σ (Fa(p)as Fattrr), - pu)) + v8 wen
255- - 8,
where the second equality holds thanks to the definition of p', the first inequality because u (p, a(p)) < 1 for each E I and the second inequality because of Eq. (7). Finally, let E IR be an optimal (non-robust) contract, then we have:
OPT - - 8 a''''a'' (p') OPT()),
concluding the first part of the proof.

---

Contract Design Under Approximate Best Responses
2. We split the proof into two parts.
(a) if (PT 0. Then, we trivially have:
0 OPT()) S max (0, max aEA
Σ WER
Fa Ca - max (0, SW - 6)
(b) OPT(5) > O. We define p" _ as an optimal d-robust contract. Then, we notice that an & (p"), where 01 is the opt-out action. Indeed, if a1 E A (p*), then the agent may select the action 01 as a d-robust best-response, which provides zero or negative utility to the principal and contradicts the fact that OPT(5) Therefore, in an optimal robust contract p", must have:
F - Ca' 2 Σ
Fay Caj +82
Σ WEQ
Fa + + 6,
WER
WEl
for some d' E (p*) Thus, have:
OPT(O)
Σ Fael -P')
WER
Fee (Tw - -P-)
WE
Fal Tw Ccl -
WER
max
Fa,uT Ca -
WEl
max
0, max
Σ
Fa,TTu Co -6) max (0, SW - 8).
aEA
WER
The first inequality above follows from the fact that d' Ap"))), while the second inequality holds due to the previous observation.
The two above points conclude the proof.
Proposition 2. Given 6 E (0, 1), for every integer n > n()), there is an instance of hidden-action principal-agent problem (parametrized by 8) with 2n + 1 actions, where:
- OPT
Furthermore, for any 8 E (0, 1), there exists instance of hidden-action principal-agent problem in which it holds:
OPT(5) OPTun (8).
Proof. We prove the two points separately.
1. We consider an instance parametrized by 8 0, with [S]] = and |A| 2n + for some n N, be defined below. We let:
min i E N V8 i
Furthermore, we introduce the following decreasing sequence:
K. .....
2n 2n42
= 72 + ..... 2n.
12

---

Contract Design Under Approximate Best Responses
with 7++1 and 72n+1 O, where N is such that k. The distributions over the set of outcomes for the different actions and their corresponding costs are given by:
Fay,or
Ca. 0, ....... 1.
F Farw = 1 7V8 Fazntiing =1
= 0, i = R. n.
Cozn+1
and the principal's reward is r = (1, Notice that the distribution over outcomes of the different actions are always well defined because of the definition of O. Furthermore, since all the agent's actions a, with i are coincident, we assume for the sake of presentation that the agent always selects di It is easy to verify that the value of optimal (non-robust) contract is OPT = 1 since the agent breaks ties optimistically and C2n+1 = 0.
With similar argument to the one proposed by (Dütting et al., 2024) in Proposition 3.9, optimal 6-robust contract is such that p² = (0, a) for some a E Rt. Consequently, in the rest of the proof, we focus on determining the maximum utility achievable in a linear, 8-robust contract.
For every a; E A. with x < i 2n + 1, E R4, is such that a² = a,, then the two following conditions hold.
All the actions aj & (ar) for each j i. This is because u (a, ay) S u va a,) for each E R4 since {7i [E))+1))11) is decreasing sequence. Thus, the latter observation implies that:
u (a, az) S ua ua (a,a alaa-1 Cai
I max u ua [E[2n+1]
= =n (ax, (2,402n+1 -
aRagai1
Caza11 5
= a
Therefore, have that:
aR:-1 Sa- 8,
and, thus, 2 V8/-i-1
The action a, A (ar).. Thus,
aBa Co. > max u (a, - = 5, ([[2n+1]
which implies that < V8/m..
The two observation above shows that a;, with > K, is a 8-best response for all the values of a such that:
V8/T-1 S v8/Tt.
Thus, the smallest value of a E R4 such that a² (ar) = is = V8/ui1, when i > K. With the same argument above, it is possible to show that ai (ar) for all a E [ai, ax) and ax = (ar) for all a E [aw, ax+1), with
01 and Ox
We also observe that the principal's utility in each o, with i E {16 11, 1,...,20 2n + 1}. such that:
vo
u (a;, a:) (1 -a:)
(1 (1-
7/-1
v
(1 (1- 1V-
7-11
7/s + 7-
v8 +
74 8.
%/-1
Therefore, using the latter formula, we have that the following holds.
13

---

Contract Design Under Approximate Best Responses
i ,,.., n,, have:
5( 51 -1-28- 21 5 2V
76-1
since (7e is a decreasing sequence.
If = n + 1, 2, we have:
u(a;) $ 1+ n-1
1) V8+
n- - 2
v6
n
n
7
= = 2n + 1, we have:
u(a,) 51 2v8
"i 8 85 - 2v8
Y--1
since {7 is a decreasing sequence.
We also observe that the principal's utility in ax such that:
u(ax)) = (1 - 8) - 1x-1%xx0 Vo).
since 7k and 8 > 0. Thanks to the definition of with simple calculation, it possible to show that:
if I-V8 N
V6
+1
1-v3 N.
1- v8
Thus, when 1/(1 - V0) & N. we have:
u(ax) = (1 0)(1
Va Vo)
1
- 6)
1
V8
1- V8
$ (1 d) (1 2
+
Similarly, it is possible to show that the same relation holds even when 1/(1 V8) E N. Finally, by putting all together, we have that:
OPT( - (5) < max u(au) - (1 225 + +
iE(2n+1]
V8
u((a++) - -1-2288+ < n
concluding the first part of the proof.
2. We consider an instance with [ = |A| = 2 and r = (0, 1). The distributions over the set of outcomes for the different
actions and their corresponding costs are given by:
Faz (1,0)
Ca
Faz (0, Caz
0.
It is easy to verify that SW Ra, - Co. 1. Furthermore, with a similar argument to the one proposed by (Düttiing et al., 2024) in Proposition 3.9, an optimal 8-robust contract is such that p* (0, a) for some a E IR.. We show that OPT(5) = Let an E AA be the opt-out action. We observe that a g A (ar) for all the RR that satisfy:
a = a aR, - Caj + 8 d.
Thus, aj & A (ar) for all a 2 8. Therefore, the smallest a E R4 such that the agent selects the action dg coincides with 8 > O. Thus, the largest utility the principal can achieve satisfies OPT(8)
SW
14

---

Contract Design Under Approximate Best Responses
The points above conclude the proof.
Proposition The The function (0, 1) (5)(5) is continuous and con-increasing Moreover, limg- OPT(6) OPT and lim OPT( O.
Proof. We prove the claims separately.
We first show that (O is a continuous function. Let p' E R be a d-robust and p' = -1- -1-v()pp + Ver. Then, by Lemma 3, we have:
OPT(6 + 2 u a
(p"",'(("))) 2V 2
Thus, rewriting the latter inequality and taking the limit, we have that:
0 lim (2VE- - E) z lim OPT(O) - OPT(6 + + -00
e-0
with 8' = - Then, by Lemma 3, we have: Let E IR be a robust and p' = (1 - Vc)p* + ver with
OPT( = OPT(8' + +c) 2 (p', a 8' + +v())) 2 u u'(p", a a (p')) + - c) - -Ve
Thus, by taking the limit, we have that:
0 lim -2 c-+
c) 2 lim OP - -c) - (8)()). c-0
Since the latter considerations hold for every 5 E (0, 1), we can easily show that OPT()) is continuous in 5 1).
We now prove that (8)()) is non-increasing, Let 8, 8 E (0,1) such that 8' < 8. Furthermore, let p" 1 be an optimal 5-robust contract. Therefore, have:
OPT(O) = (p".)"""))))) S u(a" (x').p") s OPT(('),
since, for each p E RT, we have A (p) S (p).
By Proposition 1, we have:
lim OPT(O) > lim OPT 6 OPT, 6++0+
and,
lim OPT()) < lim 1 - d=0. 0. 1-1-
6-1-
The points above conclude the proof.
Lemma 3. Given any e E (0, 1) and contract p E RT, the following holds for every 0 θ:
u (v', a. 0,5 0,55+ (.'5))(p'))))) 0) 2 up up(p, (p, 0.5 (p), -
where p' == (1 Ve)p + Ver.
Proof. For the sake of the presentation, we avoid the dependence on the type A E e. We split the proof in two cases:
1. If 8+ (pp''p))) & Ap), then a *t'(p') is not b-best-response in p. Therefore, we have that:
Σ Po - cor(m) 2 Σ
Fat - Cos1e(1)) +
WEFt
wEN
and,
Σ
FaltrigyyuPl - -cottr())) 2
Σ
FarG)) - Co((p) -
WED
wEn
15

---

Contract Design Under Approximate Best Responses
Then, by taking the summation of the above quantities and employing the definition of p' we get:
Vi 2
Σ - (o) - Pw).
WED
Therefore, we can prove that the following holds:
(p, (p)) v (p'. a = Σ
Paterillra - Pw)
-Pw)-
Σ
Fac-o Plu))
WES
= Σ (T - - (1-vo Σ
Fatrret - Pw)
WEN
WER
$ (1 - vt)
Σ ((aotp) - (ot Bw)) + vo
WED
I 22EE-E
2. if (x(+e(/) E (p), then one of the following hold. (a) if (p) (p)) then either (p) a (p') or a (p) provides the same principal's utility aptc(p') in p'. Indeed, suppose by contradiction that the following holds:
Σ Fa -Pb) E ER
(a pLu).
WER
Then, we have:
Σ Fatts(p) -pb) = (1 VE)
F Fatte Dw)
2 (1 Ve)
Fat( -Pw)
Σ Fa pl))
where the inequality a consequence of the fact that both a (p) and ap+e(p') belongs A²))). This, reaches contradiction with the initial assumption. Thus, we have that:
u (p', 6+ (
= Σ Fa Fatt (r) - Plw)
WER
Σ (a - plw)
wEn
(1
Parcp) Pw) WEl
Σ (a - Pw) Ve
WEN
2 u (p (p)) Ve.
(b) if (p) & Ap)) then the following holds:
Σ Pa ca((m) 2 Σ Fasterr - -adtrr()) 6,
wEn
well
and,
Σ Fatteeg - -cpte())) 2 Faro)al'' col(() + +c
WES
went
16

---

Contract Design Under Approximate Best Responses
Then, by taking the summation of the above quantities and employing the definition of o' get:
Σ (F) (p) Pw)-
Then, using the same argument employed at point (a) we can show that:
u (p) u (p'. - (D')) s vc,
concluding the proof.
Theorem 2. The regret suffered by Algorithm 2 can be upper bounded as follows:
Rr 8) $ ① (I" I
Proof. In the following, we let:
1. p" be such that Eoce Ap" ap", (p),) OPT(C,
2. p' = -1- 22)pp" + 2er. Notice that p' [0, 1 since both p, E C and C is convex.
3. E B, be such that || oo S Notice that there always exists at least once contract p satisfying the latter condition because of the definition of B, and the fact that p' E [0, 1)
We start by observing that, for each 0 E O, it holds ( E A0.6+2e(p)) Indeed, we have:
Σ WE
Fo c0,00.(p))
2
Σ (0 c0,09.5(p)
weft
Fe FoawDa - C0.0 - δ
WE
Fo.awPs - C0.0 - 22 - 8,
wEn
for every actions A. The above inequalities follows since:
Σ Fo plm) S |l olo S e,
for every actions a E A and 0 E O.
Therefore, we can prove that the following holds:
Σ
Apu (p, 0.6 0.6 (p),0) Σ Dou (p',a 0.6 (.)) -
o
Agu (p', 0,622 -c Σ
OE0
AouP (p",a"
0, (v")))), 2/2c
OE
OPT(C, 8) 2/2
(8)
where the first inequality above holds because Ewen Fo (p_ - -P')) < F 1| p'lloo S for every actions a E A and type 0 θ The second incquality holds because of the definition of 8-best response, while the third inequality follows from Lemma
At this point, we decompose the cumulative regret follows:
T
(C, = T - OCT(C,
-E
Σ
Aou (p', (
[=1
BEE
17

---

Contract Design Under Approximate Best Responses
S T OPT(C, T max Exou (p, 9.
(p,a".00) (p). 0)
PEB.
BEB
(a)
+ T max PEB.
Edou (p, a (p).0) - E
Σ
dou' (a))
*E(T),
(b)
We focus on bounding term (a) in Eq. (9). Let p E [0, m) be the contract defined at point 3. Then, we have:
TOOP(CC, 6) - max PEB.
Σ
Yav (p', a (v') 0) T- OPT(C, o) - -T) - dan (ū. a (p),
Age
BEB
s 2V22
where the last inequality holds because of Eq. (8). We focus on bounding term (b) in Eq. (9). By employing the same analysis to prove the regret bound in UCB1 (see, e.g., (Lattimore Szepesvári, 2020)), we obtain:
T max PEB,
d (p, 8:5 (p).
E
Σ (E(T] AE6
Aau (p', ".0 (D').)) s ( log(1))
(10)
OE6
Finally, observing that [B,] S (({/a))) by putting (a) and (b) in Eq. (9) together and setting T m+1, we have:
RT 8) s θ ( (tmp))))))
concluding the proof.
Corollary 1. The regret suffered by Algorithm 2 can be upper bounded as follows:
(C) S H (T' smmt-)) 2V8T.
Proof. Let p" be an optimal non-robust contract inside C. Then we have:
T
(C = T OPT(C) - Σ
dou (0', " (p'), 0)
1=1
OPT(C, TTP(OPT(C) - 8)) +T OPT(C, E
Σ Σ
Nou YouP('' ('',a'''')) 0)
22 T E
Agu (pt a (1')))))))
1=1 AEO
< 2 δ (T' (
Xwily
where the first inequality holds by employing the argument needed to prove Proposition 1, and the second inequality holds thanks to Theorem 2, concluding the proof.
18


Reviews:
[{"review_id": "5WKDvHpNXE", "reviewer": "Reviewer_LMBs", "summary": "This paper explores hidden-action principal-agent problems where the agent follows approximate best responses rather than exact optimal strategies. The authors propose a polynomial-time algorithm for computing optimal contracts under these conditions and introduce a no-regret learning algorithm for scenarios where the principal lacks prior knowledge.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Re**: *\"Challenges in Our Setting and Technical Novelty.”*\n\nWe believe that the computational results presented in Section 4 are rather “surprising”. Indeed, such positive results are unexpected, as very similar problems are computationally intractable. In particular, computing an optimal $\\delta$-robust commitment in Bayesian persuasion and Stackelberg game settings is known to be computationally intractable (see Gan et al. (2023), Yang & Zhang (2024)). Our case actually appears even more challenging because the strategy space, $\\mathbb{R}_+^m$ is much less amenable compared with $\\Dleta_m$ in Bayesian persuaison and Stackelberg games. And because of this, the quasi-polynomial-time approximation schemes (QPTAS) developed in the previous works do not apply to our setting. We initially conjectured that our setting was harder and attempted to prove that it was inapproximable.\n\nIt was only after a series of attemps and very careful analysis, we discovered that contract design scenarios are actually more structured and allow for efficient computation. Based on these unique structures, our method works entirely different from previous approaches to computing robust equilibria. It revolves around fixing the $\\delta$-robust best response and the actual best response, then computing an optimal robust contract for such a scenario. By iterating this process for each pair of actions and solving an LP at each step, we prove that it is possible to recover an optimal robust contract. Our algorithm is guaranteed to work in contract design due to the particular structure of the principal’s and agent’s utilities. This approach is entirely new compared to existing ones, which, for example, require solving an exponential number of LPs. Indeed, notice that a similar approach cannot be employed in the settings studied in previous works.\n\nWe agree with the Reviewer that some of the techniques we adopted are common in algorithmic game theory, such as solving a set of LPs. However, the main contribution and most challenging step of our work is determining which LPs need to be solved to recover an optimal robust contract. (Indeed, a naive approach would require solving exponentially many LPs!) Hence, while the algorithmic approach may appear standard, this is in fact not the case for the analysis, which, as highlighted above, is entirely disjoint from previous works on the topic and requires non-trivial arguments.", "claims_and_evidence": "yes.", "methods_and_evaluation_criteria": "yes.", "theoretical_claims": "In the first 8 pages", "experimental_designs_or_analyses": "N.A.", "relation_to_broader_scientific_literature": "n.a.", "essential_references_not_discussed": "n.a.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper addresses a novel aspect of contract design in principal-agent problems, considering realistic scenarios where agents do not always act optimally. The introduction of approximation in an agent's action is new, though the idea is similar to Gan et al., 2023.\n2. The authors provide a thorough analysis, rigorously establishing bounds on contract robustness, demonstrating the existence of optimal solutions, and introducing polynomial-time algorithms that improve upon prior intractability results in similar settings.\n\nWeaknesses:\n1. The techniques presented in this paper do not appear particularly novel. Both the analysis of the algorithm 1 and 2 are relatively standard. The novelty of the technical results should be further clarified.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "1. Could the authors specify the unique and new challenges in their proposed model and clarify how their techniques effectively address these challenges?\n2. Is there any new technique developed during this process?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QWMv8UFJI0", "reviewer": "Reviewer_XkgL", "summary": "The paper studies hidden-action principal‐agent problems where a principal designs a contract (an outcome‐dependent payment scheme) to incentivize an agent to take actions that are in favor of the principal. Unlike traditional models assuming the agent always plays an exact best response, here the agent may choose any action that is within a $\\delta\\in(0, 1)$ suboptimal range.\n\n- The authors derive upper and lower bounds on the maximum utility the principal can achieve with robust contracts, characterizing the \"price\" the principal pays (in terms of utility loss) for robustness as a function of $\\delta$. Notably, these bounds do not depend on the inducibility gap (a parameter common in Stackelberg games). \n- The paper presents a polynomial-time algorithm to compute an optimal $\\delta$-robust contract by first fixing the optimal arm and a $\\delta$-robust arm, and solve the induced LP. \n- The work extends to an online learning framework where the principal does not know the agent’s underlying parameters (costs, types) and shows an $T^{1-1/2(m+1)}$ regret.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Re**: *\"The online learning setting assumes the follower's action to be invisible, rendering the follower's response model a \"black box\" and thus an exponential dependency is unavoidable. My question is, If the follower consistently takes the worst -suboptimal action (from the leader's perspective), and the leader can observe the follower's taken action. Can the leader leverage this adversarial behavior to gain more information about the follower's cost structure? If so, could this lead to an improved regret bound compared to the standard setting?\"*\n\nWe thank the Reviewer for the question. Learning an optimal contract with observable actions in a polynomial number of queries (with respect to the parameters of the problem instance) remains an open problem, even in the non-robust case. Exponential lower bounds exist in Stackelberg games, but it is unclear whether they extend to contract design due to the particular structure of the utilities. However, we do not believe that the adversarial behavior of the follower would benefit the principal, since when $\\delta$ is close to zero, the problem nearly reduces to the classical one (see Proposition 1).", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper addresses an interesting problem of how to learn a $\\delta$-robust contract from both computational and online learning perspectives. Previous work Zhu et al. 2023 focuses on more general Stackelberg game setting, where many of the results can be further refined for the problem of contract design due to the specialty of the (linear) problem structure. \n\n\nZhu, Banghua, et al. \"The sample complexity of online contract design.\" arXiv preprint arXiv:2211.05732 (2022).", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The analysis is novel and the paper is well written and easy to follow.", "other_comments_or_suggestions": "No further suggestions", "questions_for_authors": "The online learning setting assumes the follower's action to be invisible, rendering the follower's response model a \"black box\" and thus an exponential dependency is unavoidable. My question is, If the follower consistently takes the worst $\\delta$-suboptimal action (from the leader's perspective), and the leader can observe the follower's taken action. Can the leader leverage this adversarial behavior to gain more information about the follower's cost structure? If so, could this lead to an improved regret bound compared to the standard setting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iQCtiFgvtT", "reviewer": "Reviewer_MN5P", "summary": "This paper studies optimal contract design under approximate best response agents in hidden-action principal-agent games.  First, they propose an efficient algorithm to compute an optimal contract.  They also show that the principal's utility is $\\delta$ close to the optimal contract under best response agents.  Finally, the paper relaxes the full knowledge assumption and devises a no-regret learning algorithm.\n\nTo design an efficient algorithm, they first show that the parameter space of optimal $\\delta$ robust contracts can be formulated by a collection of disjunctive constraints (2a) and use linear programming to solve it.  The proof idea of $\\delta$-closeness in Proposition 1 is similar to Zhu et al. 2023.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Re**:*\"Can the simple discretization apply to non-robust settings? \"*\n\n Yes, the simple discretization can be employed in the non-robust version of the problem. Intuitively, it is sufficient to follow the same steps as in the proof of Theorem 2, with $\\delta$ going to zero.\n\n**Re**: *\"Can algorithm 2 take $\\delta=0$?\"*\n\nNo, when $\\delta=0$ the $\\delta$-best responses are not well defined. (Please refer to the first equation in Section 2.2.)\n\n**Re**: *\"Why does the regret definition $\\mathcal{R}_T(\\mathcal{C})$ coincide with Zhu et al's? ….\"*\n\nThe Reviewer is right; we will fix this in the final version. Only the baseline (i.e., OPT) in that regret definition coincides with that considered by Zhu et al. (2023). However, when $\\delta$ is approximately zero, the two regret definitions essentially coincide. Indeed, as $\\delta$ tends to zero, the problem nearly reduces to the non-robust one (see Proposition 1). ** \n\n**Re**: *\"Can you elaborate more on which part of the results in section 5 can be applied to the non-robust setting?\"*\n\n“As previously discussed, when $\\delta$ is approximately zero, our problem essentially coincides with that of Zhu et al. (2023). Thus, our results can be extended to the non-robust problem. However, this requires addressing some technical details, since when $\\delta = 0$, the agent's best response regions do not coincide with those in the non-robust case due to the strict inequality “>” in the definition of $A^\\delta(p)$.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Mostly", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper considers optimal contract design under approximate best response agents. If the agent is best responding, the optimal contract can be solved by a simple LP.  Approximate best response introduces additional layer of complexity.", "essential_references_not_discussed": "Nothing I am aware of.", "other_strengths_and_weaknesses": "## Strength\n- The results are interesting in the context of principal agent game under approximate best response, e.g., Gan et al. 2023 where the paper should hidden action principal-agent games is *smooth* in the principal's objective and also admit efficient algorithm\n- The writing is good.\n\n## Miner issue\nThe comparison to Zhu et al is not very clear to me.  \n- Can the simple discretization apply to non-robust setting? \n- Can algorithm 2 take $\\delta=0$? \n- Why does the regret definition $\\mathcal{R}_T(\\mathcal{C})$ coincide with Zhu et al's? If $\\delta\\neq 0$, the second part is approx best response.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Can you elaborate more on which part of the results in section 5 can be applied to the non-robust setting ($\\delta = 0$)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5o2WVs1H1C", "reviewer": "Reviewer_bX9Z", "summary": "This paper studies a repeated contracting game between a principal and an agent. The principal offers contracts to the agents who has the choice to accept the contract or not. The paper assumes a hidden action on which the outcome (to which are related the principal's and the agent's utilities) depends. Instead of the classic setup where the agent best responds to the contract, the agent here deviates by a quantity $\\delta$ from his best action. In that setup, algorithm 1 gives a way to compute the \"optimal $\\delta$-robust contract\". Then, it is assumed that the agent's type changes over time in a repeated game. For that scenario, the principal discretizes the space of contracts as an $\\epsilon$-grid of the dimension m hypercube. The UCB bandit algorithm is used, the set of actions being the grid of the hypercube.\n\nFrom my understanding, $\\delta$ is known to the principal (otherwise algorithm 1 cannot run because of equations (6a), (6b), (6c)). Thus, since it is assumed that the agent picks the worst action for the principal within the set $A^\\delta$, the term \"robustness\" seems an abuse of language. The principal knows the agent's deviation, which makes it way easier to tackle and not very far from analyzing a best response.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We believe there is misunderstanding on the main contributions of our paper and the challenges in obtaining efficient optimization algorithms.\n\n- **Computing robust equilibria is much harder than standard one**. The Reviewer claims: “The principal knows the agent's deviation, which makes it way easier to tackle and not very far from analyzing a best response.” We disagree with this statement, as it contradicts known results for similar bilevel problems, such as Stackelberg games and Bayesian persuasion, where computing an equilibrium in the best-response case is computationally easy, but hard for worst-case robust approximate best-response.\n\n- **Main contribution of our paper**. The Review seems mostly focused on the learning part, while it seems to ignore the more “surprising” computational results. As should be clear from our writing (see, e.g., the abstract), the learning part is not the main contribution but rather a valuable addition. While we agree with the Reviewer that the learning part alone is not enough for ICML, we hope the Reviewer would agree that it includes nice extensions and simplifications with respect to the approach by Zhu et al. \n\n- **On agent’s behavior**. The Reviewer claims: “The paper assumes that the agent picks the principal's worst action within the set $A^\\delta(p)$. This assumption does not make any sense from a rational agent's perspective, does not exist in the literature and seems to be there only to allow the proofs to work.” **We respectfully, but strongly, disagree on this statement.** First, the assumption is not intended to be predictive of the agent's behavior: rather, it is a worst-case perspective based on the fact that **the agent's behavior is unpredictable within a small $\\delta$ utility difference** (e.g., due to noise in the model parameters or the agent's perception of their own utility). In such a scenario, the principal adopts a worst-case approach by computing a robust contract. In this way, the utility the principal secures, OPT($\\delta$), is a lower bound on the actual utility the principal will obtain. Indeed, **this robust equilibrium model is not our own invention**, it has been previously proposed and studied in both Stackelberg and Bayesian persuasion settings (Gan et al., 2023; Yang & Zhang 2024).\n\n**Re**: *\"I am concerned about Remark 2..\"*\n\nThe Reviewer’s observation is right, if the agent is allowed to break ties in any way when indifferent among multiple $\\delta$-best response, then an optimal contract for the principal may *not* exist. However, Remark 2 is concerned with the learning part, where the goal is *not* to compute an optimal contract, but rather to attain no-regret against an optimal $\\delta$-robust contract. Notice that such a contract always exists, given the correctness of Algorithm 1. Thus, non-existence is *not* an issue. Intuitively, the extension of Algorithm 2 informally described in Remark 2 has to deal with the fact that the feedback actually observed by the algorithm is *not* about the $\\delta$-best response that minimizes principal’s utility, but about some other $\\delta$-best response instead. This requires the adoption of an adversarial regret-minimization algorithm, but it intuitively does *not* detriment the regret against an optimal $\\delta$-robust contract, since the observed $\\delta$-best responses cannot be worse than the one played under a $\\delta$-robust contract. Due to space constraints, we cannot provide a complete formal proof of this to the Reviewer, but we will certainly add it in the final version of the paper.\n\n**Re**: *\"Comparison with Zhu et al. (2023)\"*\n\nAs we have already highlighted, the learning part is not our main contribution. However, our algorithm builds on Zhu et al. to deal with $\\delta$-best responses of the agent. In doing so, it provides a simple algorithmic approach and analysis. While we agree that our approach is still far from practical applications, it should be acknowledged that a simpler approach and analysis are always beneficial.\n\n**Re**: *\"Could you explain how it makes a difference to assume that the agent picks the worst action for the principal in  as long as $\\delta$ is known? I am not sure it makes it a harder problem as compared to a best-responsive agent.\"*\n\nComputing a robust contract when $\\delta$ is known still poses several challenges. For instance, in Stackelberg games, computing a robust commitment is computationally intractable even when $\\delta$ is known. This is because, unlike the non-robust case, the principal’s utility function is piecewise linear over an exponential number of regions (see, for instance, the hard instances in the reduction of Gan et al. (2023)). This contrasts with classical contract design, where the utility is piecewise linear over $n$ regions (one per action). It is only thanks to our analysis, which exploits the particular structure of contract design (not available in other bilevel problems), that we obtain a polynomial-time algorithm.", "claims_and_evidence": "I am concerned about Remark 2, which states the following:\n\n\"Our algorithm can be extended to deal with settings in which the agent can play any δ-best response within the set Aθt,δ(pt). In such a setting, the principal’s utility is not fully stochastic. However, our Algorithm 2 can be easily extended by instantiating an adversarial no-regret algorithm instead of UCB1.\"\n\nAn important difficulty would come from dealing with agents who potentially play any action in the set $A^\\delta$ (for $\\delta$ being not close to $0$, I am not even sure that a solution exists). I would appreciate a clear algorithm and a proof for this remark, which seems overclaimed to me.\n\nAs I mention it above, the term \"robustness\" for this setup is also overclaimed.", "methods_and_evaluation_criteria": "There are no experiments in this paper, which is absolutely not a concern for me. The paper is theoretical and is more about proposing a framework to study contract design than about offering possibly practical implementations.", "theoretical_claims": "I checked the proofs for the theoretical claims and they seem correct to me. My concern is on one side about the lack of mathematical precisions. Typically, UCB1 is called without any reference. Of course, I can understand that it is a reference to the Upper Confidence Bound algorithm but I would appreciate to see it written down, especially when it comes to analyze it.\n\nI feel like the proofs and techniques are very close to Zhu et al. 2023, except that they are made easier. The fact that the agent chooses the worst action for the principal within the set $A^\\delta$ does not change the way the analysis can be done. At the end of the day, it is equivalent in the analysis (at least for the learning part) to an agent choosing the best action. I am not convinced by the technical novelty of the theoretical claims.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "I am concerned about the novelty of the paper as compared to Zhu et al. 2023. The claimed advantages are the following:\n- apparently the method by Zhu et al. 2023 needs a more complex discretization, which makes \"the approach by Zhu et al. (2023) challenging to be employed in practice compared to ours\". The current state of this line of work with a UCB having an action set of size $T^{1/m+1}$ seems to me a sufficient burden to make it stay a very theoretical field right now. If the authors believe that the practical implementation is a significant advantage of their method, then I would have appreciated experiments or at least straight applications clearly stated.\n- second, the method in the paper \"does not require apriori knowledge of the principal’s reward, which is instead required by the algorithm of Zhu et al. (2023).\" I agree that it can be of some interest but to me, it is a very marginal advantage.", "essential_references_not_discussed": "Yes. The very classic reference in contract theory could be mentioned:\n- Laffont and Martimort, The theory of incentives: the principal-agent model.\n\nThere exists a literature on robust contract design, such as\n- Yu and Kong, Robust Contract Designs: Linear Contracts and Moral Hazard\n- Miao and Rivera, Robust contracts in continuous time\nbut the only reference given is:\n- Carroll, Robustness and linear contracts.", "other_strengths_and_weaknesses": "My first concern is the assumption on the agent's behavior. The paper assumes that the agent picks the principal's worst action within the set $A^\\delta$. This assumption does not make any sense from a rational agent's perspective, does not exist in the literature and seems to be there only to allow the proofs to work.\n\nThe learning part of the paper seems very weak to me. It does not go beyond running UCB on a discretized hypercube to approximate a very specific notion of regret. Also, the last section does not provide anything more than reminding the hidden type setup of Zhu et al. 2023, then proposing a discretization of the hypercube and running an UCB on it (similar techniques were already proposed). Hence, despite the pros and cons one could find in the paper, I do not believe that it is a good fit for ICML, which is a machine learning conference.\n\nThe capacity of the method to handle any $\\delta$ best-response seems overclaimed.\n\nI appreciate the problem of designing robust contracts, which seems very interesting to me. However, I believe that the setup and the approach are poorly formulated and do not bring additional value as compared to the existing state-of-the-art.", "other_comments_or_suggestions": "The regret definition in part 5 should me more discussed since it is not obvious.", "questions_for_authors": "Could you compare the technical novelty of your approach to Zhu, B., Bates, S., Yang, Z., Wang, Y., Jiao, J., and Jordan, M. I. The sample complexity of online con- tract design?\n\nCould you explain how it makes a difference to assume that the agent picks the worst action for the principal in $A^\\delta$ as long as $\\delta$ is known? I am not sure it makes it a harder problem as compared to a best-responsive agent.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies a robust version of contract design where the agent may take any action that is close enough to the optimal one.  Overall, all reviewers find the (high-level) model reasonable, and the contributions valuable.  There were questions concerning the technical novelty compared to prior work on robustness in game-theoretic settings, as well as whether the specific notion of robustness in this paper is *the* right notion.  Accordingly, we encourage the authors to take this chance to improve their paper and address the specific concerns raised by the reviewers, regardless of the outcome.
Decision: Accept (poster)