Learning Optimal Contracts: How to Exploit Small Action Spaces
Authors: Francesco Bacchiocchi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: ICLR 2024 poster (2024)
Keywords: principal-agent problems
sample complexity
online learning
contract design
Primary area: reinforcement learning

Abstract: We study principal-agent problems in which a principal commits to an outcome-dependent payment scheme---called contract---in order to induce an agent to take a costly, unobservable action leading to favorable outcomes. We consider a generalization of the classical (single-round) version of the problem in which the principal interacts with the agent by committing to contracts over multiple rounds. The principal has no information about the agent, and they have to learn an optimal contract by only observing the outcome realized at each round. We focus on settings in which the size of the agent's action space is small. We design an algorithm that learns an approximately-optimal contract with high probability in a number of rounds polynomial in the size of the outcome space, when the number of actions is constant. Our algorithm solves an open problem by Zhu et al. [2022]. Moreover, it can also be employed to provide a $\widetilde{\mathcal{O}}(T^{4/5})$ regret bound in the related online learning setting in which the principal aims at maximizing their cumulative utility, thus considerably improving previously-known regret bounds.

Published as a conference paper at ICLR 2024
LEARNING OPTIMAL CONTRACTS: How TO EXPLOIT SMALL ACTION SPACES
Francesco Bacchioechi, Matteo Castiglioni, Alberto Marchesi & Nicola Gatti Politecnico di Milano, Milan, Italy (name. surname @po @po limm...... it
ABSTRACT
We study principul-agent problems in which a principal commits to an outcome- dependent payment scheme-called contract-in order to induce an agent to take a costly, unobservable action leading to favorable outcomes. We consider a generalization of the classical (single-round) version of the problem in which the principal interacts with the agent by committing to contracts over multiple rounds. The principal has no information about the agent, and they have to learn an optimal contract by only observing the outcome realized at each round. We focus settings in which the size of the agent's action space is small. We design an algorithm that learns an approximately-opimaal contract with high probability in a number of rounds polynomial in the size of the outcome space, when the number of actions is constant. Our algorithm solves an open problem by Zhu et al. (2023). Moreover, it can also be employed to provide a ((T4/5) regret bound in the related online learning setting in which the principal aims at maximizing their cumulative utility over rounds, considerably improving previously- known regret bounds.
INTRODUCTION
The computational aspects of principal-agent problems have recently received growing attention in
algorithmic game theory (Dütting et al. 2019 Alon et al. 2021 Guruganesh et al. [021 Dutting
al.] [021]] Dütting et al. 2022] Castiglion et al.) [022] Alon et al. 2023] Castiglion et al.] 2023a bj
Dütting et al.. 2023) Guruganesh et al. 2023 Deo-Campo Vuong et al. 2024 Dutting et al. (024).
Such problems model the interaction between a principal and an agent, where the latter takes costly action inducing some externalities on the former. In hidden-action models, the principal cannot observe the agent's 's action, but only an outcome that is stochastically obtained as an effect of such an action and determines a reward for the principal. The goal of the principal is to incentivize the agent to take an action leading to favorable outcomes. This is accomplished by committing to a contract, which is payment scheme defining payment from the principal to the agent for every outcome.
Nowadays, thanks to the flourishing of digital economies, principal-agen problems find applications in terrific number of real-world scenarios, such as, e.g., crowdsourcing platforms (Ho et al. 2014). blockchain- based smart contracts (Cong & He (019), and healthcare (Bastani et af. (016)). Most of the works on principal-agent problems focus on the classical model in which the principal knows everything about the agent, including costs and probability distributions over outcomes associated with agent's actions. Surprisingly, the study of settings in which the principal does not know all agent's 's features and has to learn them from experience has been neglected by almost all the previous works, with the exception of (Ho al. 2014 Zhu al. 2023 Cohen et al. 2022 Han et al. (023).
In this paper, we consider a generalization of the classical hidden-action principal-agent problem in which the principal repeatedly interacts with the agent over multiple rounds. At each round, the principal commits to a contract, the agent plays an action, and this results in an outcome that is observed by the principal. The principal has no prior information about the agent's actions. Thus, they have to learn optimal contract by only observing the outcome realized at each round. Our goal is to design algorithms which prescribe the principal a contract to commit to at each round, coproxxmateel-optinn
in order to learn possible number of rounds. This can be seen as the problem of establishing the sample complexity of learning optimal contracts in hidden-action principal-agent settings.
contract with high probability by using the minimum

---

Published as a conference paper at ICLR 2024
Ho et al. (2014) were the first to consider the problem of learning optimal contracts, though they focus on instances with a very specific structure, as the more recent work by [Chhen et al. (2022). Recently, Zhu et al. (2023) addressed the problem of learning optimal contracts in general principal- agent settings. They provide an algorithm whose cumulative regret with respect to playing an optimal contract is upper bounded by Olym T1=1/(2m+1)), with an mattosttmatching) lower bound of ((m+))/(m++),, where m is the number of outcomes and T the number of rounds. The result of Zhu et al. (2023) is very unpleasant when m large, since in such case the regret grows almost linearly in 7. Moreover, in the instances used in their lower bound, the number of agent's 's actions is exponential in m, leaving as an open problem establishing whether better guarantees can be obtained when the action space is small (see also the discussion in (Zuu et al. )
Original contributions We provide an algorithm that finds an "approximately-opiinee with high probability, requiring number of rounds that grows polynomially in the size of the problem instance (including the number of outcomes m) when the number of agent's ss actions is constant. The algorithm can be easily exploited to achieve cumulative regret (with respect to an optimal contract) upper bounded by Ö(m" T4/5), which polynomially depends on the instance size when the number of agent's 's actions is constant. This solves the open problem recently stated by Zhu et al. (2023). Our algorithm works by "approximately identifying" a covering of contracts into best-response regions, each one representing set of contracts in which given agent's action is a best response. The algorithm does so by progressively refining upper and lower bounds for such regions, until they coincide. One of the main challenges faced by our algorithm is that, after each round, the principal only observes an outcome stochastically determined by the agent's ' best response, rather than observing the action itself. This makes impossible identifying the action played by the agent. Our algorithm overcomes such an issue by working with meta-actions which group together agent's 's actions associated with "similar" distributions over outcomes. Such meta-actions need to be "discovered" online by the algorithm, which thus has to update the set of meta-actions on the basis of the observed feedbacks. As a result, our algorithm has to adopt a trial-and-crron approach which re-starts the covering procedure each time a new agent's 's meta-action is discovered.
contract
Relation to repeated Stackelberg games Our work is related to the problem of learning an optimal commitment in repeated Stackelherg games (Letchford et al., 2009; Peng et al., 2019). However, differently from Stackelberg games, in principal-agent problems the principal cannot observe the action undertaken by the agent. This prevents us from relying on existing techniques (see, e.g., PPng et al. 2019h) which identify the hyperplanes defining the best-response regions of the follower. As consequence, we have to work with meta-actions that only "approximate" the set of actions and we can only compute "approximate" separating hyperplanes. Such approximations the particular structure of principal- -agent problems, in which an approximately incentive compatible contract can be turned into an incentive compatible one by only suffering small utility loss (see, e.g., (Dutting et al. 2021 Zhu et al. 2023)). This is not the case for Stackelberg games.
made effective by
2 PRELIMINARIES ON HIDDEN-ACTION PRINCIPAL-AGENT PROBLEMS
An instance of the hidden-action principal-agent problem is characterized by tuple (A, where A is finite set of n := |A| actions available to the agent, while P is a finite set of m == [|t] possible outcomes. Each agent's 's action a E A determines probability distribution F. E An over outcomes, and it results in a cost Ca E [0, 1] for the agent] We denote by Fa.. the probability with which action results in outcome W Ω2 prescribed by F.. Thus, it must be the case that Σwen Fa, 1 for all A. Each outcome w Ω is characterized by reward Tw [0. 1] for the principal. Thus, when the agent selects action a E A, the principal's is expected reward is ΣwEn Feww
The principal commits to outcome-dependen payment scheme with the goal of steering the agent towards desirable actions. Such a payment scheme is called contract and it is encoded by a vector p E RT defining payment P. from the principal to the agent for each outcome . Given a contract E Rmm. the agent plays a best-response action that is: (i) incentive compatible (IC), i.e. it
'Given a finite set X, we denote by Ax the set of the probability distributions over the elements of X. 2As it is customary in contract theory (Carroll 20155). in this work we assume that the agent has limited liability, meaning that the payments can only be from the principal the agent, and viceversa.
2

---

Published as a conference paper at ICLR 2024
maximizes their expected utility;; and (ii) individually rational (IR), i.e., it has non-negative expected utility. We assume w.l.o.g. that there always exists an action a E A with ca = 0. Such an assumption ensures that there is action providing the agent with positive utility. This guarantees that any IC action is also IR and allows us to focus w.l.o.g. on IC only.
Whenever the principal commits to p E RTT, the agent's s expected utility by playing an action a E A is equal to Ewea Fa.uP.. - Ca. where the first term is the expected payment from the principal to the agent when selecting action a. Then, the set A(p) C A of agent's ' best-response actions in a given contract p RT is formally defined as follows: A(p) = arg m Ewen Fa,wPw Ca. Given an action a E A. we denote with Pa C RTT the best-nsse set of action o, which is the set of all the contracts that induce action a as agent's best response. Formally, Pa == {pe RT a E A(p)} }.
As it is customary in the literature (see, e.g., (Dütting al. 2019 ) we assume that the agent breaks
ties in favor of the principal when having multiple best responses available. We let a a'(p) E A(p) be the action played by the agent in a given p E Rr, which is an action a A(p) maximizing the principal's ss expected utility Ewen Fa. (r_- P.). For ease of notation, we introduce the function expected u R - R to encode the exppetd utility under all the possible contracts; formally, the function u is defined so that u(p) = Ewen Fa- (p)()) (Tw Pw) for every p E RRT-
In the classical Single-round) bidden-action a contract E I that maximizes the expected utility u(p). By letting OPT := maxpeRt u(p), we say that contract p E BT is optimal if u(p) = OPT. Moreover, given additive approximation error > 0, we say that p is p-optimal whenever u(p) 2 OPT -
sanncipl-agentt problem, the goal of the principal is find
LEARNING OPTIMAL CONTRACTS
We study settings in which the principal and the agent interact over multiple rounds, with each round involving a repetition of the same instance of hidden-action principal-agent problem. The principal has no knowledge about the agent, and their goal is to learn optimal contract. At each round, the principal-agent interaction goes as follows: (i) The principal commits to a contract E RT. (ii) The agent plays a" (p), which is not observed by the principal. (iii) The principal observes the outcome w ~ Fa- (p) realized by the agent's ' action. The principal only knows the set f2 of possible outcomes and their associated rewards Tw. while they do not know anything about agent's actions A, their associated distributions Fa, and their costs Ca.
The goal is design algorithms for the principal that prescribe how to select a contract each round in order to learn an optimal contract. Ideally, we would like an algorithm that, given an additive approximation error p and a probability 5 E (0, 1). guaranteed to identify p-optimal contract with probability at least 1 - 8 by using the minimum possible number of rounds 3) The number of rounds required by such an algorithm can be seen as the sample complexity of learning optimal contracts in hidden-action acttinn crincppl-aggnn problems (see (Zhu et al., (203)))
The following theorem shows that the goal defined above is too demanding.
Theorem 1. For any number of rounds N E N, there is no algorithm that is guaranteed to find k-optimal contract with probability greater than or equal 1-6 5 by using less than N rounds, where K, 5 0 are some suitable absolute constants.
Theorem I follows by observing that there exist instances which an upproximately-opting contract may prescribe a large payment on some outcome. Thus, for any algorithm and number of rounds N, the payments used up to round N may not be large enough to learn such an approximately-optine contract. To circumvent Theorem 1 in the rest of the paper we focus on designing algorithms for the problem introduced in the following Definition [ Such a problem relaxes the one introduced above by asking to find contract whose seller's s expected utility is "approximately" close to that of contract among those with bounded payments.
Definition (Learning an optimal bounded contract). The problem of learning optimal bounded contract reads as follows: Given a bound B 2 on payments, an additive approximation error >> O,
Such learning goal can be seen as instantiating the PAC-learning framework into principal-agent settings.
3

---

Published as a conference paper at ICLR 2024
and a probability 8 E (0, 1), find contract p E [0, such that the following holds:
u(pp) 2 max u(p') - 0 2 21-8. B'E(
Let us remark that the problem introduced in Definition T does not substantially hinder the generality of the problem of learning an optimal contract. Indeed, since a contract achieving principal 's expected utility OPT can be found by means of linear programming (Dutting et al.) (021), it is always the case that an optimal contract uses payments which can be bounded above terms of the number of bits required to represent the probability distributions over outcomes. Moreover, all the previous works that study the sample complexity of learning optimal contracts focus on settings with bounded payments; see, e.g., (Zhu et al. ). The latter only considers contracts in [0, 1|mh. while we address the more general case in which the payments are bounded above by a given 2 1.
4 THE DISCOVER-AND AND-COVER ALGORITHM
In this section, we provide an algorithm for the problem introduced in Definition I which we call riscover-and-Cove algorithm (Algorithm [ Our main result (Theorem 2
is an upper bound on the number of rounds required by the algorithm, which we show to grow polynomially in the size of the problem instance when the number of agent's actions n. is constant.
The core idea behind Algorithm to learn an optimal bounded contract p [0, B) by "ap- proximately" identifying the best-response regions Pa. Notice that, since at the end of each round the principal only observes the outcome realized by the agent's action, rather than the action itself, identifying such best-response regions exactly is not possible. Moreover, the principal does not even know the set of actions available to the agent, which makes the task even more challenging.
Algorithm I buildss set D of meta-actions, where each meta-action d E D identifies a set A(d) S A of one or more (unknown) agent's actions. A meta-action groups together "similar" actions, in the sense that they induce similar distributions over outcomes. The algorithm incre- mentally discovers new elements of 'D by trying to cover a suitably-defined set P of contracts (see Line by means
Algorithm Discover and Cover
Require: E (0, 1), 8 E (),
Set c, a. q. and n) as Appendix C.J C.I
2: P + { RT Ipp| S mB)
3: D F Ø
4: do
of approximate best-response regions Lu, one for each
5:
{LaldeD + Try-ore)))
D. particular, Ca is suitably-defined polytope that "approximately describes" the union of all the best- response regions Pa actions a E A(d) associated with
6: while {La) =
7:
return Findtiiidddoo Find
d. Each time D is updated, the algorithm calls the Try-Cover procedure (Algorithm whose aim is to cover P with approximate best-response regions. Try-Cover works by iteratively finding hyperplanes that separate such regions, by "testing" suitable contracts through the Act i aetion-Oracll procedure (A (Algorithm 2). Given a contract p E P, Action-Oracle checks whether it is possible to safely map the agent's best response a (p) an the latter case, Act i on -nnacc e refines the set 'D by either adding a new meta-action or merging a group of meta-actions if their associated actions can be considered "similar". Whenever the set DD changes, Try-Cover is terminated (returning Ø). The algorithm continues trying to cover P until satisfactory cover is found. Finally, such cover is used to compute a contract p [0, B)"h to be returned, by means of the procedure F' Find-Cont ract (Algorithm
-iscoveedd meta-action d E D or not. In
In the rest of this section, we describe the details of all the procedures used by Algorithm | In particular, Section 4.1 is concerned with Action-Oracle, Section 4.2 with Try-Cover, and Section 4.3 with And-Cont
Finally, Section 4.4 concluoss the analysis of Algorithm 1 by putting everything together so as to prove the guarantees of the algorithm.
4.1 ACTION-ORACIA
Given contract E P as input, the Act Act procedure (Algorithm) 2 determines whether it is possible safely map the agent's best response a (p) some meta-action d D. If this is the case, then the procedure returns such a meta-action. Otherwise, the procedure has to properly refine the set D of meta-actions, as we describe in the rest of this subsection.
4

---

Published as a conference paper at ICLR 2024
In the first phase (Lines I Algorithm 2 prescribes the principal to commit to the contract p E P given as input for E N consecutive rounds (see Appendix C.1 for the definition of q). This is done to build an empirical distribution F E An that estimates the (true) distribution over outcomes Fa induced by the agent's best response a "()). In the second phase (Lines 7 21 such an empirical distribution is compared with those previously computed, in order to decide whether a" (p) can be safely mapped to some d E 'D or not. To perform such a comparison, all the empirical distributions computed by the algorithm are stored in dictionary F (initialized in Line Algorithm D. where Fid] contains all the F An associated with d E.
6).
The first phase of Algorithm Algorithmmennsures that (FF I holds with sufficiently high probability, For ease of presentation, we introduce clean event that allows us to factor out from our analysis the "with high probability" statements. In Section 4.4, we will show that such an event holds with sufficiently high probability given how the value of q chosen.
Definition 2 (Clean event). Given any > O, we let &g be the event in which Algorithm Pawways computes some F An such that [F (p) I e, where p P is the input to the algorithm.
In the second phase, Algorithm 2 searches for all the 'D such that F(d] contains al least one empirical distribution which is "sufficiently close" to the that has just been computed by the algorithm. Formally, the algorithm looks for all the meta-actions d E 'D such that || Fl S 2c for at least one F E F(d.. Then, three cases are possible: (i) If the algorithm finds a unique d E D with such property (case IDo| = 1), then d is returned since a" (p) can be safely mapped to d. (ii) If the algorithm does not find any d E D with such a property (case Do = Ø), then a new meta- action de is added to D. (iii) If the algorithm finds more than one d E 'D with such a property ((2) > 1), then all the meta-actions in Do are merged into single (new) meta-action dº. In Algorithm 2 the last two cases above are jointly managed by Lines [7-21 and in both cases the algorithm returns the special value
Algorithm PAction-Orace
Require: p E P
1: J_ < 0 for all w E fi Phase 1: Estimate
2: for l....... do
3: Commit to p and observe w E
4: In 4- In +
5: end for
6: Build F E
An : Fu Iw/q tw Ω b Phase 2: Compare
7: D + Ø
8: for d E D do
9:
if irar
|F- | S 2e then D D (d)
E Fld
10:
11: end if
12: end for
13: if [D9] - then
14: F[d] +- Fld U {F} unique d e D
15: return d
16: end if
I. This alerts the calling procedure that the set D has changed, and, thus, the Try-Cover procedure needs to be re-started. Notice that Algorithm also takes care of properly updating the dictionary F. which is done in Lines 14 and 20 Moreover, whenever Algorithm 2 adds a new meta-action d' into D. this is also associated with particular empirical distribution Fas, which is set to be equal to F (Line 19
17: D (D(D))
P d is new
18: F [T]
19: Let Fae be equal F
20: Clear F(d] for all d E D
21: return
We remark that the symbols Fa for d E 'D have only been introduced for ease of exposition, and they do not reference actual variables declared in the algorithm. Operationally, one can replace each appearance of F in the algorithms with any fixed empirical distribution contained in the dictionary entry F(d].
The first crucial property that Algorithm 2 guaarantees is that only "similar" agent's 's best-response actions are mapped to the same meta-action. In order to formally state such property, we first need to introduce the definition of set of agent's 'ss actions associated with a meta-action in DD
Definition 3 (Associated actions). Given a set DD of meta-actions and a dictionary F of empirical distributions computed by means of Algorithm 2 we let A D + 2 be a function such that A(d) represents the set of actions associated with the meta-action E D. defined as follows:
A(d) = {a E A F Fallos 5cn Ep P P a0))
The set A(d) encompasses all the agent's actions a A whose distributions over outcomes Fa are "similar" to the empirical distribution Fa associated with the meta-action d E D, where the entity of the similarity is defined in suitable way depending on and the number of agent's 's actions Moreover, notice that the set A(d) only contains agent's 's actions that can be induced as best response for at least one contract p E P. This is needed in order simplify the analysis of the algorithm. Let
5

---

Published as a conference paper at ICLR 2024
us also remark that agent's action may be associated with more than meta-action. Equipped with Definition 3, the property introduced above can be formally stated as follows:
Lemma 1. Given a set D of meta- and a dictionary of empirical distributions computed by means of Algorithm 2] under the event & if Algorithm returns a meta- d E 'D for a contract p E P given as inpus, then it holds that a* (p) E A(d).
Lemma follows from the observation that, under the event E.. the empirical distributions computed by Algorithm 2 are "close" " to the true ones, and, thus, the distributions over outcomes of all the actions associated with d sufficiently "close" to each other. A non-trivial part of the proof of Lemma 1 is to show that Algorithm 2 does not put in the same entry F[d] empirical distributions that form "chain" growing arbitrarily terms of II- norm, but instead the length of such "chains" is always bounded by 5en. The second crucial property is made formal by the following lemma:
Lemma 2. Under the event &,, Algorithm returns at most 2n times.
Intuitively, Lemma 2 follows from the fact that Algorithm 2 iinreases the cardinality of the set D by one only when || Fl > 2e for all F F[d] and E D. In such case, under the event & the agent's 's best response is an action that has never been played before. Thus, the cardinality of D can be increased at most n times. Moreover, in the worst case the cardinality of D is reduced by one for times, resulting in 2n being the maximum number of times Algorithm Algorithmrretuuns I. In the following. we formally introduce the definition of cost of a meta-action.
Definition 4 (Cost of meta-action). Given a set D of meta-actions and a dictionary F of empirical distributions computed by means of Algorithm [ we let e 'D - [0, 1] be a function such that c(d) represents the cost of meta-action E DD defined as c(d) mid) Ca-
Then, by Holder's inequality, we can prove that the two following lemmas hold:
Lemma 3. Given a set D of metaaeaciiionn and a dictionary F of empirical distributions computed by means of Algorithm 2 under the event E,, for every meta-action d E D and associated action a E A(d) it holds that (c(d) - cal S 4Bemn.
Lemma 4. Given a set D of meta-actions and a dictionary F of empirical distributions computed by means of Algorithm 2 under the event Ee, for every meta-action d E D. associated action A(d), and contract p E holds Ewen Fd, Pw c(d) EwER Faa Pw + cal S Bemm.
4.2 TRV-COVER
In this section, we present key component of Algorithm 1 which is the Try-Cover procedure (Algorithm 3). builds a cover [Ca Pf made of approximate best-response regions for the meta-actions in the current set D. The approximate best-response region Ca for a meta-action d E D must be such that: (i) all the best-response regions Pa of actions a E A(d) associated with d are contained in La; and (ii) for every contract in La there must be action E A(d) that is induced as an "approximate best response" by that contract. Notice that working with approximate best-response regions is unavoidable since the algorithm has only access to estimates of the (true) distributions over outcomes induced by agent's 's actions.
The core idea of the algorithm is to progressively build two polytopes Uu and ca-called, respectively, upper bound and lower bound-for each meta-action d E D. During the execution, the upper bound Ua is continuously shrunk in such way that a suitable approximate best-response region for is guaranteed to be contained in Udz while the lower bound La is progressively expanded so that it is contained in such a region. The algorithm may terminate in two different ways. The first one when La = Ua for every d E 'D. In such a case, the lower bounds {La)deD constitutes cover of P made of suitable approximate best-response regions for the meta-actions in D, and, thus, is returned by the algorithm. The second way of terminating occurs any time a call to the Action-Oc oonooo procedure is not able to safely map the agent's is best response under the contract given as input to a meta-action (i.e., Act on-Oracle returns 1). In such a case, the algorithm gives back control to Algorithm by returning Ø, and the latter in turn re-starts the Try procedure from scratch since the last call to Action-Orace
has updated D. This happens in Lines 5
14 and 22
The ultimate goal of Algorithm 3 is to reach termination with C, = U2 for every d E D. Intuitively, the algorithm tries to "close the gap" between the lower bound L. and the upper bound La for each d E

---

Published as a conference paper at ICLR 2024
D by discovering suitable approximate halfspaces whose intersections define the desired approximate best-response regions. Such halfspaces are found in Line 21 by means of the Find-HS procedure (Algorithm()) whose description and amalysis is deferred to Appendix B Intuitively, such procedure searches for an hyperplane that defines a suitable approximate halfspace by performing a binary search (with parameter 1)) on the line connecting two given contracts, by calling on the contract representing the middle point of the line at each iteration.
The halfsspaces that define the approximate best-response regions computed by Algorithm 3 intuitively identify areas of P in which one meta-action is "supposedly better" than another one. In particular, Algorithm B uses
Algorithm 3
1: Ca + 2. Va <- for all d
2: Da + {d} for all d E D
the variable Hij to store the approximate halfspacce in which d, E "D is "supposedly better" than d, E D. in the sense that, for every contract in such a halfspace, each action associated with d, provides (approximately) higher utility to the agent than all the actions associated with dj. Then, the approximate best-response region
3: Hij + Ø, Aūg 4 0 for all de, E
4: d - Action-Oracla
> For any p
5: ifd =1 Lthen return Ø
6: L. (p).CC [d]
7: while C C 2 do
8:
Take any d, EC
9:
while La, $ Ma, do
for dj D is built by intersecting suitably-defined group of Haj. for some d, E with j # i. In order to ease the construction of the approximate halfspaces in the Find-HS HS procedure, Algorithm 3 also keeps
10:
Va. < v(Ua.) & Vertexes of Ua. do
11:
12:
Take any p E Va, d, + Act MactionOOraceffy if d = 1 then return Ø if L.j = 2 then
13:
some variables Acj which represent estimates of the difference between the costs c(d,) and c(d,) of de and d,. respectively. These are needed to easily compute the intercept values of the hyperplanes defining Hiy.
14:
15:
16:
Ld, + +
17:
end if
18:
if d, E Da; then
19:
Ld, t co La, p)
Next, we describe the procedure used by Algorithm 3
20:
else
to reach the desired termination. In the following.
21:
(H, de) - F Pind-Hs(dd. p)
for clarity of exposition, we omit all the cases in which the algorithm ends prematurely after a call to Act Action-Oracll the d E D that still need to be processed, i.e., those
22:
if de 1 then return Ø
23:
His H
Algorithm 3 works by tracking all
24:
Ua, +- Ua, n NHe
25:
Da, + Da: U Ufd
such that La f Ua, into set C. At the beginning of
26:
end if
the algorithm (Lines T all the variables are properly
27:
Va, Vv, \ {pp
initialized. In particular, all the upper bounds are initial-
28:
while Va, # 2 A dj E Da.
ized to the set P. while all the lower bounds are set to Ø.
29:
end while
30:
C C. {d.}
The set C is initialized to contain d E DD obtained by calling Act i on-Oracle le for any contract p E PP with the lower bound La being updated to the singleton {p]. Moreover, Algorithm alsso maintains some subsets Da C D of meta-actions, one for each d E D. For any de DD the set Da, is updated as to contain all the d; E CD such that the halfspace H. has already been computed. Each set Da is initialized to be equal to {d], as this is useful to simplify the pseudocode of the algorithm. The main loop of the algorithm (Line iterates over the meta-actions in C' until such a set becomes empty. For every de E C, the algorithm tries to "close the gap" between the lower bound Ld, and the upper bound Udg by using the loop in Line 9 In particular, the algorithm does so by iterating over all the vertices V V(lla, ) of the polytope defining the upper bound Uda, (see Line 10). For every p E V V(la,) ). the algorithm first calls Action-Oracla with p as input. Then:
31:
end while
32: return (CaJaed
If the returned d, belongs to Dd., then the algorithm takes the convex hull between the current lower bound La, and p as new lower bound for d;. This may happen when either d, = d, (recall that d; E DD. by construction) or d, * d;. Intuitively, in the former case the lower bound can be "safely expanded" to match the upper bound at the aurrently-considers vertex p. while in the latter case such "matching" the upper bound may introduce additional errors in the definition of Ca.- Nevertheless, such an operation is done in both cases, since this not hinders the guarantees of the algorithm,
formally show in Lemma o Notice that handling the case dj + d; in Algorithm 3 is crucial to avoid that multiple versions of the approximate halispace H. are created during the execution of the algorithm.
the returned d, does not belong to Da,, the algorithm calls the Sind-HS procedure to find a new approximate halfspace. Whenever the procedure is successful, it returns approximate
7

---

Published as a conference paper at ICLR 2024
halfspace H that identifies area of P in which d; is "supposedly better" than another meta-action dg E D Da, which is returned by the Find-HS procedure as well. Then, the returned halfspace H is copied into the variable Has (Line 23). and the upper bound Ma, is intersected with the latter (Line 24.. Moreover, dg is added to Da, (Line 25). in order to record that the halfspace H has been found. After that, the loop over vertexes is re-started, as the upper bound has been updated.
Whenever the loop in Line 9 terminates, Ld, Ld, for the current meta-action de and, thus, d, is removed from C. Moreover, if call to Action-Oracl. returns a meta-action dj E D such that d & C and Ld = Ø, then d, added and Ld, is set {p). where p E P is the contract given to Actions Action-Oracle (see Lines] 16). This ensures that all the meta-actions are eventually considered, Next, we prove two crucial properties which are satisfied by Algorithm [ whenever returns (Ca)aED. The first one is formally stated in the following lemma:
Lemma 5. Under the event &, when Algorithm 3 returns {La] ded, it holds that USED Ca = PP.
Intuitively, ( that Algorithm tterminates with a correct cover of P, and it follows from the fact that, the end of the algorithm, Udepll== = and La Ua for every E 'D The second crucial lemma states the following:
Lemma 6. Under the event E., when Algorithm 3 returns {Ca]dED. for every meta-action d D, contract p E Lad and action a' E A(d),, there exists that polynomially depends on m, n, 6, and B such that:
Fa WER
Fo,w Ca- -Y Va A. WESt
Ca'
Lemma 6 states that (Ca defines cover of P made of suitable approximate best-response regions for the meta-actions in D. Indeed, for every meta-action E and contract p E La playing any E A(d) associated with d is "approximate best response" for the agent, in the sense that the agent's 's utility only decreases by a small amount with respect to playing the (true) best response a" (p). Finally, the following lemma bounds the number of rounds required by Algorithm
Lemma 7. Under event E,, Algorithm requires at most O (n²g (log (Bm/n) + +*****)) ))) rounds.
Lemma follows from the observation that the main cost, terms of number of rounds, incurred by Algorithm 3 is to check all the vertexes of the upper bounds Ua. The number of such vertexes
can be bound by (*+*=+)) )), thanks to the fact that the set P being covered by Algorithm has m + 1 tM is necessary, since the latter has a number vertexes which is exponential in m. Nevertheless, Algorithm [ returns contract p E [0, B]" by means of the F Find-Contract procedure, which we are going to describe in the following subsection.
vertexes. Notice that, using P instead of [0. 3)
4.3 CON-TACNT
The Find-Contract procedure (Algorithm 4 finds a contract p E [0, Bl that approximately maximizes the principal's I's expected utility over [0, BlTh by using the cover {Lalde of P made by approximate best-response regions given as input (obtained by running Try-Cover)
First, for every d E D. Algorithm 4 computes Pa which maximizes an empirical estimate of the princi- pal's expected utility over the polytope La [0, "h This is done in Line 2 by solving a linear program with constraints defined by the hyperplanes identify- ing Can [o, B) and objective function defined by the principal's 's expected utility when outcomes gener- ated by Fa. Then, A ttkes the best contract (according to the empirical distributions Fx) among all the r/. which is the contract p" defined in Line and it returns a suitable convex combination of such contract and vector whose components are defined by principal's rewards (see Line (). The following lemma formally proves the guarantees in terms of principal's 's expected utility provided by Algorithm
Algorithm 4 Find-Contract
Require: [Ca]ded while d do
2: På + arg max Ewea Faww (rw Pw)
PEJO.D]''
end while
4: d" +- arg max Ewer Fawlrs - paw)
dED
5: p² < P..
6: p. (1 Vept + Serw for all w Ω
return p
Lemma 8. Under the event &,, if (CaTdeD is a cover P computed by Try-Cover, Algorithm returns contract p E B such that u(p) 2 maaxy'/jo.B) (lpp)(p))) p.
8

---

Published as a conference paper at ICLR 2024
The main challenge in proving Lemma [ is that, for the pontract computed in Line 3 the agent's best response may not be associated with any meta-action in D. namely a a"(p") ) & A(d) ) for every d E D. Nevertheless, by means of Lemma 6 we can show that a=tpp= (p") is an approximate best response to p². Moreover, the algorithm returns the contract defined in Line ie., a convex combination of p* and the principal's 's reward vector. Intuitively, paying the agent based on the principal's rewards aligns the agent's 's interests with those of the principal. This converts the approximate incentive compatibility of a" (p*) for the contract pd into loss in terms of principal's i's expected utility.
4.4 PUTTING IT ALL TOGETHER
We conclude the section by putting all the results related to the procedures involved in Algorithm ! together, in order to derive the guarantees of the algorithm.
First, by Lemma 2 the number of calls to the Cover procedure is at most 2n. Moreover, by Lemma and by definition of q and 17. the number of rounds required by each call to Tzy-Cover is at most O (mm - 1/p" log(+/a) under the event &c, where I is a term that depends polynomially in m, n, and B. Finally, by Lemma [ the contract returned by Algorithm -he result of a call the F Find-Coor Canttact procedure- has expected utility at most p less than the best contact in [0, BJmm, while the probability of the clean event & can be bounded below by means of a concentration argument. All the observations above allow us to state the following main result.
Theorem 2. Given E (0, 6 (0, 1), and B > 1 as inputs, with probability at least 1 - the algorithm (Algorithm 7 is guaranteed to return a contract p [0, B) such that u(p) 2 max//e(0.B u(p')= in at most Ö(m" I 1/00 log(1/8) rounds, where I is a term that depends polynomially in m, n,, and B.
Discover
Notice that the number of rounds required by Algorithm Is polynomial in the instance size (including the number of outcomes m) when the number of agent' actions constant.
CONNECTION WITH ONLINE LEARNING IN PRINCIPAL- AGENT PROBLEMS
In this section, we show that our Di scover dovv--Coverr algorithm can be exploited to derive no-regret algorithm for the related online learning setting in which the principal aims at maximizing their cumulative utility. such a setting, the principal and the agent interact repeatedly over a given number of rounds T, described in Section 3
At each t I,.... T, the principal commits to a contract p² E Imm the agent plays best re- sponse a² (p'), and the principal observes the re- alized outcome wt Fa-(x") with reward rwe. Then, the performance in terms of cumulative ex- pected utility by employing the contracts (r' [= is measured by the cumulative (Stackelberg) regret
Algorithm 5 No-regret algorithm
Require: 8 E (0, 1), B 2
1: Set P in proof of Theorem
2: for = 1,..., do
3:
if Algorithm noo terminated yet then
4:
p² +- p E prescribed by Alg.
5:
else
RT = T maxpe(0.B]- u(p) - E. ET "(p')
6:
p' p'+ *+pE pe [0, B|Th returned by Alg.
7:
end if
where the expectation is over the randomness of the environment. As shown in Section 4 Algorithm
8: end for
learns an approximately-optinn
bounded contract with high probability by using the number of rounds prescribed by Theorem 2 Thus, by exploiting Algorithm [ it is possible to design an explore-then ciatere-thn-ccoomin commit algorithm ensuring sublinear regret RT with high probability; see Algorithm
Theorem 3. Given E (0, 1), Algorithm 5 achieves R < Ô (mm I log(1/s) T4/5) with probability at least 8, where I is a term that depends polynomially on m, n, and B.
Notice that, even for a small number of outcomes m (i.e., any m 2 3), our algorithm achieves better regret guarantees than those obtained by Zhu et al. (203)) in terms of the dependency on the number of rounds T. Specifically. Zhu et al. (2023) provide O(T1-1/(2++1) regret bound, which exhibits a very unpleasant dependency on the number of outcomes m at the exponent T.. Conversely, our algorithm always achieves a ( dependency on T, when the number of agent's actions n is small. This solves problem left open in the very recent paper by Zhuu et al. (203)).
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This paper is 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 NextGenerationEU 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 Al for Sustainability, No. 101 100277).
REFERENCES
Tal Alon, Paul Dütting, and Inbal Talgam-Cohle Cohen. Contracts with private cost per unit-of-effort, In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 52-69, 2021.
Tal Alon, Paul Duetting, Yingkai Li, and Inbal Talgam-Cohen. Bayesian analysis of linear contracts. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, pp. 66,
2023.
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances Neural Information Processing Systems, 34:25799-2588 2021.
Hamsa Bastani, Mohsen Bayati, Mark Braverman, Ramki Gummadi, and Ramesh Johari. Analysis of medicare
contracts. Available at SSRN 2839143, 2016.
Gabriel Carroll. Robustness and linear contracts. American Economic Review, 105(2):536-563, 2015.
Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian agency: Linear versus tractable contracts. Artificial Intelligence, 307:103684, 2022.
Matteo Castiglioni, Alherto Marchesi, and Nicola Gatti. Designing menus of contracts efficiently: The power of randomization. Artificial Intelligence, 31 318:103881, 2023a.
Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Multi-agent contract design: How to commission multiple agents with individual outcomes. Proceedings of the 24th ACM Conference on Economics and Computation, pp. 412-448, 2023b.
Alon Cohen, Argyrios Deligkas, and Moran Koren. Learning approximately optimal contracts. In Algorithmic Game Theory: 15th International Symposium, SAGT 2022, Colchester, UK, September 12-15, 2022, Proceedings, pp. 331-346. Springer, 2022.
Lin William Cong and Zhiguo He. Blockchain disruption and smart contracts. The Review of Financial Studies, 32(5): 754-1797, 2019.
Ramiro Deo-Campo Vuong. Shaddin Dughmi, Neel Patel, and Aditya Prasad. On supermodular contracts and dense subgraphs. In Proceedings of the 2024 Annual ACM-SIAN Symposium Discrete Algorithms (SODA), pp. 109-132. SIAM, 2024.
Paul Dütting, Tim Roughgarden, and Inbal Falgam-Coher Simple versus optimal contracts. In Proceedings of the 2019 ACM Conference Economics and Computation, pp. 369-387, 2019.
Paul Dutting, Tim Roughgarden, and Inbal Talgam-Cohen. The complexity of contracts. SIAM Journal on Computing, 50(1):211-254 2021.
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 815-826. IEEE, 2022.
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pp. 1311-1322 2023.
Paul Dutting, Michal Feldman, and Yoav Gal Tzur. Combinatorial contracts beyond gross substitutes. In Proceedings of the 2024 Annual SCM-SIAM Symposium on Discrete Algorithms (SODA), pp. 92-108. SIAM, 2024.
10

---

Published as a conference paper at ICLR 2024
Guru Guruganesh, Jon Schneider, and Joshua R Wang. Contracts under moral hazard and adverse selection. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 563-582, 2021.
Guru Guruganesh, Jon Schneider, Joshua Wang, and Junyao Zhao. The power of menus in contract design. In Proceedings of the 24th ACM Conference on Economics and Computation, EC '23, pp. 818-848, 2023.
Minbiao Han, Michael Albert, and Haifeng Xu. Learning in online principle-agent interactions: The power of menus. arXiv preprint urXiv:2312.0986) 2023.
Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. Proceedings of the Fifteenth ACM Conference Economics and Computation, pp. 359-376, 2014.
Niklas Lauffer, Mahsa Ghasemi. Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu. No-regret learning in dynamic stackelberg games. IEEE Transactions on Automatic Control, 2023.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009. Proceedings 2, pp. 250-262. Springer, 2009.
Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies commit to. In AAAI Conference on Artificial Intelligence, volume 33, pp. 2149-2156, 2019.
Banghua Zhu Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. In Proceedings of the 24th ACM Conference on Economics and Computation, pp. 1188, 2023.

---

Published as a conference paper at ICLR 2024
APPENDIX
The appendixes are organized as follows:
Appendix A provides a detailed discussion of the previous works most related to ours.
Appendix B provides all the details about the Find-HS procedure which is employed by the Lussoover-and-oovee algorithm, including all the technical lemmas (and their proofs) related to such a procedure.
Appendix C provides all the details about the Discover- and Cover algorithm that are omitted from the main body of the paper, including the definitions of the parameters required by the algorithm and the proofs of all the results related to it.
Appendix D provides all the other proofs omitted from the main body of the paper.
A RELATED WORKS
In this section, we survey all the previous works that are most related to ours. Among the works addressing principal-agent problems, we only discuss those focusing on learning aspects. Notice that there are several works studying computational properties of principal-agen problems which are not
concerned with learning aspects, such as, e.g., (Dütting et al.) 2019 Alon et al. 2021] Guruganeshi
ict al. 2021| Dutting et al. 2021: Dütting et al. 2022; Castiglioni et al. 1,022,2033
Learning in principal-agent problems The work that is most related to ours is (Zhu et al. 2023 which investigate a setting very similar to ours, though from an online learning perspective (see also our Section 5) /hhu et al. (2023) study general hidden-action principal-agent problem instances in which the principal faces multiple agent's types. They provide a regret bound of the order of O(ym T 1rl--1/C0 1/1=11((++1)) when the principal is restricted to contracts in [0, 11m". where m is the number of outcomes. They also show that their regret bound can be improved to D(T1-1/(m+3) by making additional structural assumptions on the problem instances, including the first-order stochastic dominance (FOSD) condition. Moreover, Zhu et al. (2023) provide an (almost-matching lower that holds even with a single agent's 's type, thus showing that the dependence
bound of 12 on the number of outcomes m the exponent of T is necessary in their setting. Notice that the regret bound by /Zuu et al. (2023) is "close" to a linear dependence on T, even when m is very small. In contrast, in Section 5 we show how our algorithm can be exploited to achieve a regret bound whose dependence on T is of the order of (TT4/5) (independent of m). when the number of agent's 's actions is constant. Another work that is closely related to ours is the one by Ho et al. (2014), who focus on designing no-regret algorithm for a particular repeated principal-agen problem. However, their approach relies heavily on stringent structural assumptions, such as the FOSD condition. Finally, Cohen et al. (2022) study a repeated principal-agen interaction with a risk-averse agent, providing a no-regret algorithm that relies on the FOSD condition too.
Learning in Stackelberg games The learning problem faced in this paper is closely related to the problem of learning an optimal strategy to commit to in Stackelberg games, where the leader repeatedly interacts with a follower by observing the follower's best-response action at each iteration. Letchford et al. (2009) propose an algorithm for the problem requiring the leader randomly sample a set of available strategies in order to determine agent's 's best-response regions. The performances of such an algorithm depend on the volume of the smallest best-response region, and this considerably limits its generality. |Peg et al.] (2019) build upon the work by Letchford et al. (2009) by proposing an algorithm with more robust performances, being them independent of the volume of the smallest best-response region. The algorithm proposed in this paper borrows some ideas from that Peng et al. (2019). However, it requires considerable additional machinery to circumvent the challenge posed by the fact that the principal does not observe agent's 's best-response actions, but only outcomes randomly sampled according to them. Other related works in the Stackelberg setting are (Bai et al.) 2021). which proposes model where both the leader and the follower learn through repeated interaction, and (Lauffer et al., 2023), j which considers a scenario where the follower's utility is unknown to the leader, but it can be linearly parametrized.
12

---

Published as a conference paper at ICLR 2024
Assumptions relaxed compared to Stackelberg games In work, relax several limiting assumptions made in repeated Stackelber games (see, e.g., (Letchford et al. 2009) Peng et al. 2019) to learn optimal commitment. Specifically, in repeated Stackelberg games either the best response regions have at least constant volume or they are empty. Thanks to Lemma g we effectively address this limitation, showing that even when optimal contract belongs zero-measured best-response region, we can still compute an approximately optimal solution. Furthermore, in Stackelberg games is assumed that in cases where there multiple best responses for the follower, any of them can be arbitrarily chosen. In contrast, we assume that the agent always breaks ties in favor of the leader as it customary the Stackelberg literature. Finally, our approach does not require the knowledge of the number of actions of the agent, differently from previously proposed algorithms.
B DETAILS ABOUT THE FIND-HS PROCEDURE
In this section, we describe in details the F iind-HS procedure (Algorithm 6). The procedure takes as inputs meta-action d; E DD and a contract P, and it tries find one the approximate halfspaces defining suitable approximate best-response region for the meta-action d,. It may terminate either with pair (H, dx) such that H is an approximate halfspace in which d, is "supposedly better" than the meta-action dg E DD or with pair (0, 1). whenever a call to Act ieriiinnrren Gracle returned L. Let us recall that, for case of presentation,
assume that Algorithm 6 has access to all the variables declared in the Cover procedure (Algorithm namely La Ud Da, Hij. and Adiz.
Algorithm Find-HS
Require: d;; P
1: p' any contract in Ld,
2: p² t
3: dj Actionn Act.ion-Oracle(p) Oracle(p") 5: y + 18Bemn" + 2mmym
4: d
6: while l|p - p2212 -p² n do
7:
p'_ t (p_ + //2 for all w Q
D Middle point of the current line segment
8:
d
9:
d = then return (0),
b. Force termination of Try-Cover Add to to-be-processed meta-actions in Cover
if C. then
11:
L. + t
end
13:
if d E Da then
Pu plu for all w E Ω
15:
dj + d
else
17:
p p'u for all w e Ω du +
18:
19: end if
20: end while
21: pla + (pl + /2 for all w Ω
22: if d, = d; then
The approximate halfspace H2s is the first one for La.
AdSk Σ (Fay.w Fesrer) plo
23:
wEn
24: else
The approximate halfspace Hy has already been computed
25: AOik Aij Σ
Fdj,. Felees) p/u
wel
26: end if
27: H
PERT
P Rm
Σ
Far Ferras) ) Pe Aoik y
28: return (H,d4)
13

---

Published as a conference paper at ICLR 2024
Algorithm works by performing binary search the line segment connecting p with any contract in the (current) lower bound Ld, of d, (computed by the Try-Cover procedure). At each iteration of the search, by letting p', p² E P be the two extremes of the (current) line segment, the algorithm calls the Act action--e arannorrcee procedure on the contract p' E p defined as the middle point of the segment. Then, if the procedure returns meta-action d 'D that belongs to Da, (meaning that the approximate halfspace Hsg has already been computed), the algorithm sets p² to p', while it sets y² to otherwise. The binary search terminates when the length of the line segment is below a suitable threshold 1) 2 O.
After the search has terminated, the algorithm computes an approximate halfspacc. First, the algorithm computes the estimate Ada of the cost difference between the meta-actions dj and dg- where the latter is the last meta-action returned by Act ActionOOracle that does not belong to the set Da:- Such an estimate computed by using the two empirical distributions Fa; and Fd, that the Act In particular, Ačck is computed as the sum of - estimate of the cost difference between meta-actions d; and d that has been computed during a previous call to Algorithm o and an estimate of the cost difference between the meta-actions dj and de, which can be computed by using the middle point of the line segment found by the binary search procedure (see Lines 23 and 25 Then, the desired approximate halfspace the one defined by the hyperplane passing through the middle point p' E P of the line segment computed by the binary search with coefficients given by the (m + 1) J-dimensional vector [F] FJ. Ačea y (see Line 27). where y 2 0 is suitably- defined value chosen so as to ensure that the approximate best-response regions satisfy the desired properties (see Lemma 10
procedure associated with the meta-actions dj E Da, and d2. respectively.
Notice that Algorithn also needs some additional elements in order to ensure that the (calling) Try-Cover procedure properly working. In particular, any time the Action-Orace
proce- dure returns I, Algorithm 6 terminates with (Ø. L) as return value (Line 9 This is needed to force the termination of the Try-Cover procedure (see Line in Algorithm 3 Moreover, any time the Act i on-Oracle procedure returns a meta-action d E C such that La Ø, Algorithm 6 adds such a meta-action to C' and it initializes its lower bound to the singleton {r'), where p' the contract given input to Action -Oracle (see Lines IT. This is needed to ensure that all the meta-actions in D are eventually considered by the (calling) Try Cover procedure.
Before proving the main properties of Algorithni we introduce the following useful definition:
Definition 5. Given y 2 O, a set of meta-actions DD and dictionary F of empirical distributions computed by means of Algorithm 2 for every pair of meta-actions di, dj E D, we let H P be the set of contracts defined as follows:
H = PEP
2 Σ Fareaes - -c(4)
Σ WED
Fd - -(dd) V
WElt
Furthermore, we let Hij H.-
Next, we prove some technical lemmas related to Algorithm 6 Lemma 9 provides bound on the gap between the cost difference Ač₃z estimated by Algorithm and the "true" cost difference between the meta-actions d; and de (see Defintion 4. Lemma shows that the approximate halfspace computed by the algorithm always included in the halfspace introduced in Definition [5) for suitably- value of the parameter y 2 O. Finally, Lemma 11 provides a bound on the number of rounds required by the algorithm in order to terminate.
Lemma 9. Under the event &,, Algorithm Algorithmmmsatiifiece A - c(d,) + c(d+) < 18Bemn2 + 22n m
Proof. We start by proving that, during any execution of Algorithm 6 the following holds:
Σ
Pa Fel ) -c(dd,, c(dx) < 18Bamn + 2
WER
where dy. de D are the meta-actions resulting from the binary search procedure and p' E P is the middle point point of the segment after the binary search stopped. In order to prove Equation [[] we first let a² = a" (p²) and a² a* (p²), where p ,p² P are the two extremes of the line segment
14

---

Published as a conference paper at ICLR 2024
resulting from the binary search procedure. By Lemma under the event &,, it holds that a' E A(d)) and a² E A(dx) by definition. Moreover, we let p" E P be the contract that belongs to the line segment connecting p' to p² and such that the agent indifferent between actions at and a² i,e,
(Fat wo) P = Cat - ca2- Wen
Then, prove the following:
Σ WER
Fdje= FA pl - c(d,) + cde)
Σ
Felya - Fdle)) p'u c(dj) + Cai Cat + cuz cca + c(d))
WE
Fddsa Fdhnw) Pu Cai Caa
8Bemn
WE
Σ WED
Fagsor - Fdnno) p'u p
Σ (Fat Fae,w) pw
&
WEl
Par + Fat Fat Pho Po
WER
Fares P'o + Fa Fa - Far Pi)) + 8Bemn
WE
Pa
Fat Ta=1looll'11 + [|F,, - Paelloolll11 + (11 1 M1 p"112 + Bemm
18Bemn + m.
The first inequality above is direct consequence of Lemma and application of the triangular
inequality, since a² E A(dy) and a² E A(dx) under the event & The second inequality follows by employing Holder's inequality. The third inequality holds by employing Lemma and Definition [3] by observing that [|p]] < Bm and ||all < /m for all E A. Moreover, due to the definitions of
and p" and given how the binary search performed by Algorithm works, is guaranteed that lpp' p" 2| I 1).
Next, we prove that, after any call to Algorithm 6 the following holds:
ACo c(G) + cl (dx)) I s |Da, (18Bemn + 2n/mm,,
where di. dg 'D are the meta-actions defined by the binary search procedure in Algorithm 6 We prove the statement by induction on the calls to Algorithm with the meta-action d, as input. The base case is the first time Algorithm is called with d; as input. In that case, the statement is trivially satisfied by Equation and the fact that Da, = {d+}- Let us now consider generic call to Algorithm 6 with the meta-action d, as input. Then,
write the following:
AC - c(s)) + c(da)l
Adj +
Σ wEf2
Fd Fdrm - c(ds) + c(dx)
< |B c((c)) + c(dd)] +
Σ
(Fa, - Ferew)) pls - c(d,) + c(dx)
WER
(1Pa,1 1) (18Bemn 2n/mm m)
18Bemn 2m/mm
DDa, (18Bemn + 2m/m)).
where the first inequality holds by applying the triangular inequality and the second one by using the inductive hypothesis.
n
15

---

Published as a conference paper at ICLR 2024
Lemma 10. Let (H, dz) be the pair returned by Algorithm 6 when given as inputs Ld, and p E P for some ieta-accioo d, E D. Then, under the event & it holds:
His H
with = 18Bemm2 + 2m
Proof. We start by showing that His is subset of Ha.. Let be contract belonging to Hikk then
according to Definition D the following inequality holds:
Σ WEl
Fw
Σ
Fae
2 A.sk y/
WE
with - 18 + 2mnym m as prescribed by Lemma
This shows that E H according to We now consider the case in which Hike Using the definition of Ha and Lemma 9
Definition 5
we have:
Σ Pd Fde Adsk c(dc) - c(dk) y.
WEN
WER
showing that p 1% with y 18Bemn2 + 2mnym.
Lemma 11. Under the event E,, the number of rounds required by Algorithm 2 to terminate with an approximate separating hyperplane is at most O (q log (Bm/nn).
Proof. The lemma be proven by observing that the number of rounds required by the binary search performed in Line of Algorithm is at most (log(P)))) where D represents the distance over which the binary search is performed. In our case, we have D < V2Bm, which represents the maximum distance between two contracts in P. Additionally, noticing that we invoke the Act i ion-Oracle algorithm at each iteration, the total number of rounds required by Find-HS is Og log( /28m )), the number of rounds required by Action-Orace is bounded by q. 7
C ADDITIONAL DETAILS ABOUT THE DISCOVER
ALGORITHM
In this section, provide all the details about the Di siscove--add-coom (Algorithm) D algo- rithm that are omitted from the main body of the paper. In particular:
Appendix C.I
gives summary of the definitions of the parameters required by Algorithm ! which are set as needed in the proofs provided the rest of this section.
Appendix C.2
provides the proofs of the lemmas related the Action-Orace proce-
dure.
Appendix
provides the proofs of the lemmas related the Try-Cover procedure.
Appendix 4.4
provides the proofs of the lemmas related to the Find-Contract proce-
dure.
Appendix
provides the proof of the final result related Algorithm
(Theorem)
C.1 DEFINITIONS THE PARAMETERS IN ALGORITHM
The parameters required by Algorithm are defined as follows:
6 := 32 2m?
mm
7)
8
2n
log
2Bm
+
(m+++1)
1
2m
=
log
2
16

---

Published as a conference paper at ICLR 2024
C.2 PROOFS OF THE LEMMAS RELATED TO THE ACTION-ORACLA PROCEDURE
Lemma 1. Given a sei D of meta-actions and a dictionary F of empirical distributions computed by means of Algorithm 2 under the event &., if Algorithm 2 returns a meta-action d 'D for a contract E P given as input, then it holds that a" (p) E A(d).
Proof. For case of presentation, in this proof we adopt the following additional notation. Given set DD of meta-actions and a dictionary F of empirical distributions computed by means of Algorithm 2 for every meta-action d E D, we let Pa P be the set of all the contracts that have been provided as input to A during an execution in which it computed an empirical distribution that belongs to F[d]. Moreover, we let (d) S A be the set of all the agent's actions that have been played as a best response by the agent during at least one of such executions of Algorithm 2 Formally, by exploiting the definition of Pa, we can write I (dd) Upep, (p).
First, we prove the following crucial property of Algorithm 2
Property 4. Given a sel D of meta-actions and dictionary F of empirical distributions computed by means of Algorithm 2 under the event &,, ti holds that I(d) n I(d") = Ø for every pair of (different) meta-actions d + d' E D.
In order to show that Property 4 holds, we assume by contradiction that there exist two different meta-actions d + d' E 'D such that a E I(d) and a E ((d") for some agent's action a E A, namely that T(d) n [(d))= * Ø. This implies that there exist two contracts p E Pa and p' E Par such that a" (p) = a" (p/) = a. Let F E Fid] and F' E Fid") be the empirical distributions over outcomes computed by Algorithm 2 when given inputs the contracts p and p', respectively. Then, under the event &c, have that |
2e, since the two empirical distributions are generated by sampling from the same (true) distribution Fg. Clearly, the way in which Algorithm Aasorithm@works works implies that such empirical distributions are associated with the same meta-action and put the same entry of the dictionary F. This contradicts the assumption that d + d', proving that Property 4 holds.
Next, we show the following additional crucial property of Algorithm 2
Property 5. Let D be set of meta- meta-actions and F be dictionary of empirical distributions computed by means of Algorithm 2 Suppose that the following holds for every d E 'D and a, a' E I(d):
Fa F S 4
(2)
Then, if Algorithm 2 is run again, under the event & the same condition continues to hold for the set of meta-actions and the dictionary obtained after the execution of Algorithm
For ease of presentation, in the following we call Doold and Fold the set of meta-actions and the dictionary of empirical distributions, respectively, before the last execution of Algorithm while we call Deew and J.new those obtained after the last run of Algorithm 2 Moreover, in order avoid any confusion, given Dolld and Frold, we write jold (d) in place of [d) for any meta-action d E Dold
Similarly, given Deww and _ene, we write new (d) in place of I (dd for any d Dnew
In order to show that Property Property/SJoolds, let p P be the contract given as input to Algorithm D during its last run. Next, we prove that, no matter how Algorithm 2 updates Dold and Foold in order to obtain Dnew and Frew, the condition in Property continues to hold. We split the proof in three cases.
1. IF DDI = O, then Dnew = Dold U {d'). where d' is a new meta-action. Since Jenew is
built by adding a new entry FFhe [d'] = {F) to Foldd while leaving all the other entries unchanged, it holds that nnw (do
aa (p)) and (d) = (d) for all d E Dold, As a result, the condition in Equation 2 continues hold for all the meta-actions d E DDew {dd).
Moreover, for the meta-action d", the following holds:
0 = Fo (p) Far(m) bloo I (((T = 0,
meu (d
1. This proves that the condition in Equation 2 also holds for d!.
2. If [D| = 1, then Daow Dold, We distinguish between two cases.
17

---

Published as a conference paper at ICLR 2024
(a) In the case in which (p) UaEDiN Ioll Property immediately implies that yoom (d) Told for all d E Dnew Doold Indeed, if this is not the case, then there would be two different meta-actions d + d' E -Dnw = Duuia such that _ (d) = (d) U (p)) (since f [d] [d] U (FF) and a" a'(p) E -raew(d (d") = (d'), contradicting Property E As a result, the condition in Equation 2 continues to holds for all the meta-actions after the execution of Algorithm 2
(b) In the case in which a" a²()) & UdE (d), the proof is more involved. Let d
Dnow Dool be the (unique) meta-action in the set 'Do computed by Algorithm 2
Notice that 1nee(d = 1 (d) U {p) by how Algorithm 2 works. As a first step.
we show that, for every pair of actions a, a' E _new (d) with a = a a=)), Equation 2
holds. Under the event E,, it holds that (p) Fl S c, where F' is the empirical Moreover, since the meta-action d has been added to DD by Algorithm 2 there exists an empirical distribution F E Fid] such that IF- Fllox 2e, and, under the event E,, there exists action a" (d) such that F -PP-Faa loo S e. Then, by applying the triangular inequality we can show that:
distribution computed by Algorithm 2
(a Far 10x0
())
Fllx + F| Fl + | Fa S 4e.
By using the fact that the condition in Equation 2 hholds for Drew and Free for every action a' E Inow (d) it holds that:
(PFa - Foo
$ (|aa - Fa + 1a
- (e - 1) + 4e
- 4e rold
4e (e (d) 1);
where the last equality holds since (d)) = =dood as a" (p) & UsEDu (d). This proves that Equation 2 holds for every pair of actions a, a E paew (d) with a" (p). For all the other pairs of actions a, a' /now(d), the equation holds since it was already satisfied before the last execution of Algorithm
[ Analogously, given that gnew (d) = o (d) for all the meta-actions in Deow \ {d], we can conclude that the condition in Equation continues to holds for such meta-actions as well.
3. If [D > 1, then Deew (Dold \ 'Do) U {d)), where de is a new meta-action. Clearly, the condition in Equation 2 continues to hold for all the meta-actions in Dold \ DD. We only need to show that the condition holds for d' We distinguish between two cases.
(a) In the case in which (p) E UdeDue (uld(d), let us first notice that a" a"(p) E [old(d) for some d E Do, otherwise Property 4 would be violated (as a" (p) E m (d') by definition). Moreover, it is easy to see that I (dP) Use Iold (d) and, additionally,
(dl) n rold (d') = Ø for all d + d' DO, given how Algorithm 2 works and thanks to Property 4 In the following, for ease of presentation, we assume w.l.o.g. that the meta-actions in D are indexed by natural numbers so that D = (di,... d.p..] and a" (p) E Told (dr). Next, we show that Equation 2 hollds for every pair a, a' E 7 (do). First, by employing an argument similar to the used to prove Point 2.2, we can show that, for every d, E DD with j > 1, there exists an action a" E yold (old such that [[Fa-(p)) - For 1100 I 4e. Then, for every pair of actions a, a' E m [new(dd) such that
a E yold (d1) and a' E (d,) for some d, E Do with j > 1, the following holds:
||4a Pa < 114a Fo + |4a (p) - Far 11 + I|Fa" F& S 4e((1o)d())) - 1) + 4e + 4< /o (d,)) (,)1-11 11)
= 4e((1"")()1) (1dd (d))
< 4e((1nom(dd)) 1),
where the first inequality follows from application of the triangular inequality, the second one from the fact that Equation while the last inequality holds since nhw (d)) EdeDo (old (d)) given that rold (d)
( holds before the last execution of Algorithm 2
18

---

Published as a conference paper at ICLR 2024
(d") 8 for all d + d' DD thanks to Property 4 As a final step, we show that
Equation 2 holds for every pair of actions a, a' E I (d²) such that a E Iold (d.) and a' E Ioll (d)) for some d,, dj E Do with i i j > 1. By the fact that di, d, E Do and triangular inequality, it follows that there exist a" E (d;) and a" E 1 (d,) such that Fa - f I 3e and || Fa" - pl S 3e under &c. Then, with steps similar to those undertaken above, we can prove the following:
F. loo = 11. Fa alc + Fl Fllx
-I -iaFFa + FaF Fa - 4e(11 /01 (di) - 1) + 3E - 3E + 4e(1 (d))) -1)
= 4c (d:) + 17 (d,)) - 1) + 2c
S 4c(1 mew
1);
2 is satisfied for all the pairs of actions a' E new (d)). (b) In the case in which a" a"(p) & UAED (d). let us first observe that nnw (d)) =
which shows that Equation
Ø for all d & d' E Do, given how 2 works and thanks to Property [ Next, we show that Equation 2 holds for every pair of actions a, a' E mne (d"). As first step, we consider the case in which a = a (p), and we show that Equation holdss for every a' E _ne (d") such that a' E (d) for some d Do In order to show this, we first observe that, given how Algorithm works, there exists F [dlldd]] such that ||F Fl| S 2e, and, under the
USEDo (d) U {a" (v)) and (d) n rold
Algorithm
event e,, there exists action a" E (d) such that FFa Fl| S e. Then:
(pFaa()) Fac S (1Fa)()) -Flloe + ||F Fl + ||F Foo IIFa" For
S 4e + 4e(1 (d) 1)
< 4e(1100w (d²) 1),
where the last incquality holds since | Edepo (d)) as 1 (dd) = 2 for all d f d' E DD. As a second step, we consider the case which a E rold (d) and a' E (dd) ) for some pair d & d' E DD. Given how Algorithm 2 works, there exist F E Froll [d] and f² Frul [d') such that | S 2e and || Fll S 2e. Moreover, by the fact that d, d' E Do and the triangular inequality, it follows that there exist a" E (d) and a" E (ol) such that F|F,, - Fllox S 3e and ||Fa"! Fllxo S 3e under the event &.. Then, the following holds:
Fra - Faol I |F, Far + Fa" - Flloo + 1| - Fa + +lFa" - Forllo
I 4c((7oll (d) - 1) + 3c + 3 + (c(( 11)
= 4c([TTb (d)) + [dd
2c
S 4e(( (d))) 1).
Finally, by observing that the size of [(d) for each possible set of meta-actions D is bounded by the number agent's ' actions n, for each a, E [(d) and d E 'D we have that:
||aa - F&ll S 4ne.
Then, under the event &,, by letting a' E ((d) be the action leading to the empirical distribution F, computed at Line 19 in Algorithm 2 we have ||Fa Far lloo c. Finally, combining the two inequalities, we get:
Fa For Fa S 1| Farlox + Fa Faillll S 4en + e S 5en.
This implies that a" (p) E A(d).
To conclude the proof we show that I(d) S A(d). Let a' I(d) be arbitrary action, and let Fa be the empirical distribution computed by Algorithm 2 by sampling from F.. Then for each a" E (d) we have:
|Paa llo < I1 - For oloe + || - Fa S 4en + tes S 5en.
Since the latter argument holds for all the actions E I(d) this hows that
F.aa Fa 11o0 < 4ne,
(4)
for all the actions a, al A(d).
19

---

Published as a conference paper at ICLR 2024
Lemma 2. Under the event & Algorithm returns 1. most 2n times.
Proof. As first step, we observe that under the event &c, the size of 'D increases whenever the principal observes an empirical distribution F that satisfies || Fo 2 2c for every F E F. This condition holds when the agent chooses an action that has not been selected before. This is because, if the principal commits to contract implementing the resulting estimated empirical distribution F must satisfy || Fl 2e for some F E Fed. as guaranteed by the event &.. Consequently, the cardinality of DD can increase at most times, which corresponds the total number of actions. Furthermore, we observe that the cardinality of "D can decrease by merging one or more meta-actions into single one, with the condition [D] 2 1. Therefore, in the worst case cardinality of reduced by one n times, resulting in 2n being the maximum number of times Algorithm returns 1.
action the agent has already played,
and
L
Lemma 3. Given set D of meta-actions and dictionary F of empirical distributions computed by means of Algorithm 2 under the event for every mela-action d E and associated action E A(d) it holds that (cld) -cl 4Bemn.
Proof. Let d E D be a meta-action and assume that the event & holds. Let a' E arg minl aEA(() So and let pf be contract such that a" (p') a'. By employing Definition 3 we know that for any such that a' a. Then the following inequalities
action a E A(d), there exists a contract hold:
4Bemn 2 |Fa - Fa Fa 11lll 2 Σ
(Faw Fe' Pu 2 co - Cal'
(5)
WEl
and, similarly,
4Bemn 2 Fa Fal Fallolll'11 3 Σ (Far Fa,)) Pha 2 Co. Ca.
(6)
WEn
In particular, in the chains of inequalities above, the first '>' holds since F - Far < 4en by ||- ||х of contracts in P upper bounded by Bm. Finally, by applying Equations aandd 6 we have that:
Lemmal [ and the fact that the norm
Ica- - Cal mer==ca (c(d) < 4Bemn,
for every possible action a E A(d) since Ca' = c(d) by definition, concluding the proof.
Lemma 4. Given a set D of meta-actions and a dictionary of empirical distributions computed by means of Algorithm 2 under the event & for every mela-action d E DD associated action E A(d), and contract p it holds Ewen Fd, Pw c(d) Ewen Fa, Pw cal Bemn.
Proof. To prove the lemma we observe that for each action a E A(d) it holds:
Σ
Pawppo - -(()) - Σ PauPu + Ca
S R Falloolell + [c(d) - cal
WER
WElt
S 5Bemn + 4Bemn = 9
where the first inequality holds by applying the triangular inequality and Holder's inequality. The second inequality holds by employing Lemma and leveraging Definition 3 that guarantees || Fa Falloo S 5en for every action E A(d). Additionally, we observe that the || norm of contracts in PP is upper bounded by Bm, which concludes the proof.
We conclude the subsection by providing an auxiliary lemmas related to the Action-Oracle procedure that will be employed to bound the probability of the clean event &, in the proof of Theorem
Lemma 12. Given a, E (0. 1), let F Ag be the empirical distribution computed by Algorithm
with = 222 log (2m) for contract E given as input. Then, it holds that E3 F[]] Far())
for all w Z and, with probability of at least a, it also holds that || For S
20

---

Published as a conference paper at ICLR 2024
Proof. By construction, the empirical distribution F E Ag is computed from q ii.d. samples drawn according to F (p): (p); with each w E being drawn with probability (r).... Therefore, the empirical distribution F is random vector supported on An. whose expectation such that B[Fw] Fa (p).as for all w E Ω2 Moreover, by Hoeffding's s inequality, for every w E S2, we have that:
P P[IE E[F.] = [ Far (p).ea 2 20 2
2e 2gc²
(7)
Then, by employing a union bound and Equation ( /e have that:
p - Selcseefj = { Farl)) seelseee se] 21- 2im 240²
-2me 2 21-6
WEE
where the last inequality holds by definition of
C.3 PROOFS OF THE LEMMAS RELATED TO THE TRY-COVER PROCEDURE
To prove Lemma we first introduce Definition 6 for a given a set of meta-actions D. This definition associates to each mela-acxxtion d the set of contracts in which the agent's 's utility, computed employing the empirical distribution over outcomes returned by the Action-Orace and the cost of a meta-action introduced in Definition 4 is greater or equal to the utility computed with the same quantities for the remaining meta-actions in D. Formally we have that:
procedure
Definition 6. Given a set of meta- D. we let Pa, (D) S P the set defined as follows:
(D) = p PEPI Σ WEn
Far - c(d:) Fd c(d)) fdj E ED
WES
is important to notice that we can equivalently formulate Definition by means of Definition 5 More specifically, given of met actions D, for each d, D we let Pa, (D) = Njjpllig be the intersection of subset of the halfspaces introduced in Definition 5
As second step, we introduce D. the union of the sets Pa(D) over all d E DD is equal to P. On the other hand, Lemma 14 shows that the (D( is subset of the upper bounds Uy computed by the Try-Cover procedure.
useful lemmas. Lemma 13 shows that for any of meta-actions
Lemma 13. Given a set of meta-actions DD it always holds UdeDPa(D) P.
Proof. The lemma follows observing that, for each p P. there always exits a d, E D such that:
Fa.wp c(d:) 2 Σ WER
FajwPw - cdj) Vdy E D. WES
This is due to the fact that the cardinality of D always ensured to be greater than or equal to one. Therefore, for each contract p P, there exists meta-action d such that p Pa(D), thus ensuring that (a() P. This concludes the proof.
Lemma 14. Under the event & it always holds Pa(D) S Ua for each meta-action E
Proof. To prove the lemma we observe that, for any meta-action d; DD the following inclusions hold:
Ua. = NjeDa, H. G Oyep,, Hij 5 HieDH = Pa)
The first inclusion holds thanks to the definition the halfspace H.s and employing Lemma which entails under the event &s. The second inclusion holds because Da, is subset of ' for each d, E D. Finally, the last equality holds because of the definition of Pa,
Lemma 5. Under the event &c, when Algorithm 3 returns {La) it holds that USED Ca
21

---

Published as a conference paper at ICLR 2024
Proof. As first step notice that, if Algorithm 3 returns {La) then the set D has not been updated during its execution and, thus, we must have La = Ld for all d E D. In addition, we notice that, under the event E,, thanks to Lemma 1 and Lemma 14 the following inclusion holds:
U Ud 2 d,ED
U deD
Pa, (D) P.
Then, by putting all together we get:
U d
Cd.
U d,ED
Us. Ua.
U P.(D) = d
concluding the proof.
Lemma 6. Under the event & when Algorithm 3 returns {La]deD. for every meta-action DD contract p La and action a' E A(d), there exists a that polynomially depends m, n, and B such that:
Fa Cal
Σ
Fa. Pa
Ca - Va E A.
WEQ
Proof. In order to prove the lemma, we rely on the crucial observation that, for any vertex p E ((.... of the lower bound of a meta-action d; E 'D the Act on-Oracle procedure called by Algorithm with p as input either returned d, or another meta-action dj such that p E Hi with dj E Da.
First, we consider the case in which the meta-action returned by Action-Oracle in the vertex equal dy. In such a case. a" (p(p) E A(d,) thanks Lemma and the following holds:
Σ Fa Pw c(d:)
Σ Far()) Pw (p) 9Bcmm, WEn
by means of Lemma 4 Next, we consider the case which the meta-action returned by Algorithm P is equal to dy with that belongs to Hij. In such case the following inequalities hold:
Σ WER
Farm Pw - c(d:)) 2
Σ Fay. Pw - c(dj)=
WER
Fa Car 9-Bmmn y:
WER
where the first inequality follows by Lemma 10 that guarantees that p belongs to Hij Hy with y 18Bemn2 + 2mny/m, while the second inequality holds because of Lemma since a" (p) E A(d,) thanks to Lemma
Finally, by putting together the inequalities for the two cases considered above and employing Lemma 4 we can conclude that, for every vertex (La) of the lower bound of meta-action E D, it holds:
Σ Faw Pw Ca 2
Σ well
Faw Pa c(d) 99Bmm
Σ
(p) Pw CCr - 7
(8)
for each action E A(d) by setting = Bemmn + 2nmymm
Moreover, by noticing that each lower bound La a convex polytope, we can employ the Carathéodory's theorem to decompose each contract p La convex combination of the vertices of Ca. Formally:
Σ
((v') Pw
Yo E Ω
(9)
('EV(C.)
where a(p') 2 0 the weight given vertex p' V(Ca), so that holds Epevice) a(p))
Finally, for every p E La and action a E A(d) we have:
Far Pw -ca(p)
Fa
(a)
Σ
a(p')r' Cc)
WEn
weR
('EV((C)
22

---

Published as a conference paper at ICLR 2024
E alv') VEE((C))
Σ
For ca-(r)
WED
< E
alp')
Fow
Fow Plu - Ca +
# (EV(
Wee
Σ Faw
Σ ('EV(Ca)
a(p') Pw
Ca +Y
WER
= Σ
Faw Pw - Co +
WE
where the first and the last equalities hold thanks of Equation 9 equalities hold since Spev((ca) a(p')= =1 Finally, the inequality holds thanks to Inequality by setting == Bemn² + 22nym.
while the second and the third
Lemma 7. Under event E,, Algorithm requires at most O (n²q (log (Bm/n) + + (m***t))) rounds.
Proof. As a first step, we observe that Algorithm terminates in a finite number of rounds. By the way which Algorithm 3 interseets the upper bounds with the halfspaces computed with the help of the nd procedure, the algorithm terminates with La = Ma for all d E 'D after a finite number of rounds as long as, for each meta-action d, E 'D, the halfspaces H,; with dj 'D are computed at most once. is easy to see that this indeed the case. Specifically, for every meta-actions d, D, Algorithm
6 is called to build the halfspace Hij only when Algorithm returns d, with d, & Da. for vertex p E V(Ha;) ) of the upper bound Ma, If the halfspace has already been computed, then d, E Da, by the way in which the set Da, is updated. As a result, if Algorithm called on a vertex of the upper bound Ud, returns the meta-action dj E Da. then Algorithm does not compute the halfspace again.
For every d, E D, the number of vertices of the upper bound Ud, is at most (m++++) = O (mm)) since the halfspaces defining the polytope Ma, are subset of the + halfspaces defining P and the halfspaces H., with dj E DD The number of halfspaces Hly is at most for every meta-action d; E 'D. Consequently, since each vertex lies at the intersection of at most m linearly independent hyperplanes, the total number of vertices of the upper bound U4, is bounded by (m+t*f)) = (mm)) for every d, D
We also observe that, for every d, E DD the while loop in Line 28 terminates with at most V V(aa)) = (m++*+1) O(m") iterations. This is because, during each iteration, either the algorithm finds a new halfspace or it exits from the loop. At each iteration of the loop, the algorithm invokes Algorithm 2 which requires rounds. Moreover, finding a new halfspace requires a number of rounds of the order of O (q log ( (Bm/n)), . as stated in Lemma 11 Therefore, the total number of rounds required by the execution of the while loop Line 28 at most O (q (log (Bm/n) + (m-n+1))).
yn
Let us also notice that, during each iteration of the while loop in Line new halfspace or it exits from the loop. This is because, if no halfspace computed, the algorithm does not update the boundaries of Ua, meaning that the meta-action implemented in each vertex of La. is either d, or some d, belonging Da.- Moreover, since the number of halfspaces Hyg is bounded by n for each Ud, the while loop in Line Ieerminatss in at most n steps. As a result, the number of rounds required by the execution of the while loop in Line 9 is of the order of O (ng (Iog( Bm)xx) + (m=+n+)))). being the while loop in Lines 28 nested within the one Line g m
D either the algorithm finds
Finally, we observe that the while loop in Line 7 iterates over the set of meta-actions actions D, which has cardinality most n. Therefore, the total number of rounds required to execute the entire algorithm is of the order of O (n²q (log (Bm/n) (m+++11)), which concludes the proof. n
23

---

Published as a conference paper at ICLR 2024
C.4 PROOFS OF THE LEMMAS RELATED TO THE FIND-CONTRACT PROCEDURE
Lemma 8. Under the event & if (aaaaED is a cover of computed by Try-Cover, Algorithm relurns contruct p E [0, mlth such that u(p) 2 ma.,/' u(p') p.
Proof. In the following, we define p" E [0, BlTh as the optimal contract, while we let p' == (1 vT)p" + v/r, where y is defined as in Lemma 6 Additionally,
define d" D as of the meta-actions such that p" La.. Similarly, we let d' D be one of the meta-actions such that p' E Lge. It is important to note that p E [0, Blm since ||rll S 1. Furthermore, Lemma ensures that there exists least one d' D such that p Cae.
As first step, we prove that, for each Og E A(d"), it holds:
Σ (Fa Fayw)Dl Coi (p²)
well
Σ (Pa (p") - ParwwPf + Cas (a*
WEn
-E well
(Fa (p") Farw)D +Ca, (ar( Vr ((Fater) For -Va)
wEll
(Faa(p))) (Tw -Pa),
WED
where the first incquality holds because of Lemma 6 since p E Lge, while the second and the third inequalities hold because of the definition of best-response and the equality holds because of the definition of p² E Lyi.
Then, by rearranging the latter inequality, we can show that for each action a, E A(d') the following holds:
Σ (r. p&) 2
Σ
For - -pb) V7.
(10)
WER
WER
Furthermore, for each action 0; A(d'), we have that:
Σ Pagus (rw - -p'))=
Σ Fayeo (rw ((1- VV)' + vFrw))
Fer (Nw -P%) V Σ
Far. (Tw P2)
WER
Far (Tw - -Pa) Vi
(a pL) 2/5
where the first equality holds because of the definition of of Ed,- while the first inequality holds since || < and the latter inequality because of Equation 10 Putting all together we get:
Σ WER
Farws (rw pL.)
F. (pr)) -p)) 2/7
WEB
OPT 2/7,
(11)
for each a, A(d') with of L.p.
Now, we show that the principal's utility in the contract returned by Algorithm 4 is close to optimal one. To do that we let (FaTaeD be the set of empirical distributions employed by Algorithm 4
Furthermore, we let pf == VT)p" + Vor be the final contract the principal commits to. Then, for each
let p² E La be the contract computed in Line Algorithm 4 Analogously,
ag A(d*), we have:
u(p')
Far (rw - vit) 2
WEN
24

---

Published as a conference paper at ICLR 2024
a (Tw -Pw) 2/7 5emn, wEl
where the first inequality follows from Proposition A.4 by Dutting et al. (2021) and u(p") I 1, while the second inequality holds by means of Definition as a, A(d"). Analogously, for each E A(d"). ) we have:
Σ WER
Far (r- -Pb) 2
Fe (rw - -Ps)
WER
Σ
Fac, (Tw = -Pw) 5emm
WE?
OPT
2 5emn,
where the first inequality holds because of the optimality of p", the second inequality holds because of Definition since a E A(d),, while the third inequality holds because of Equation 11 Finally, by putting all together get:
u(p')
OPT 4 27 - 200ymm 10emn
OPT 32V Bem?n?,
where employ the definition of prescrihed by Lemma 6. As result, in order to achieve p-optimal solution we set:
é
323 Bm?
while 77 = e//mm/2.
C.5 PROOF OF THEOREM 2
Theorem 2. Given p (0, 8 (0, 1), and B 1 as inputs, with probability least 1 - 8 the Discover-and-Cove algorithm (Algorithm)) [ is guaranteed to return a contract E [0, B) such that u(p) 2 max u(p') in at most O(m" I. 1/0" log(//)) rounds, where I is term that depends polynomially in m, n, and B.
Proof. First, we notice that to achieve p-optimal solution under the event & observed in Lemma we must set:
P²
and := e:=em/nn2
(12)
322 Bm
To ensure that Algorithm| Teturns a p-optimal solution with probability of least 1 8, we need to set the remaining parameters a and in a way that IP(E.) > 1 5. Intuitively, the probability of the event & corresponds to the probability that, whenever Algorithm returns empirical distribution sufficiently close to the actual onc.
2 is invoked by Algorithm
First, we observe that given E, a and a distribution over outcomes F, Algorithm computes an empirical distribution satisfying | - Fl S with a probability of at least - o, in a number of rounds q [1/2/² log (2m/a)] prescribed by Lemma 12
To ensure that Algorithm returns an empirical distribution that closely approximates the true distri- bution each time it is called, we need to bound the number of times the Discover-and-Cover
procedure invokes Algorithm 2. By applying Lemma 7 we have that the maximum number of times the iatioon-en oitiinn-racle algorithm called by the Fry-Cover algorithm is bounded by n² (log (2Bm/)) + (m+++))). Additionally, according Lemma 2 the Try-Cover procedure is algorithm. Conse- (tm0//++++++++++++++ (m**+))).
invoked at most 2n times during the execution of the wascover-and-oeee
quently, the number of times Algorithm is invoked is bounded by 2n3 (log (2Bm/n) +
By applying union bound over all the times Algorithm is invoked and considering that each time it returns an empirical distribution that is within e distance in the || Ileo norm from the actual distribution with probability at least at conclude that the event &, occurs with probability at least:
TP(E.) 2 2on"3 (1og)
2Bm
m + n + 1)
+
17
25

---

Published as a conference paper at ICLR 2024
As result, by setting:
a 2n (log (28m/n) + (m+t++1))
(13)
with 7) defined above guarantees that P(E,) d. 6. Thus, the number of rounds q required by Algorithm is equal to:
2m
log
2
with e, a defined in Equations 12 and 13 Then, by employing Lemma and Lemma 7 the number
of rounds to execute Algorithm is of the order of O (gn (log (28m/u) + (m++++1)
m
Finally, by definition of the parameters a, e, and the total number of rounds required by Algorithm return a p-optimal solution with probability least is most:
m log )
m
pr
which concludes the proof.
D OTHER OMITTED PROOFS
In this section, we provide all the remaining omitted proofs.
Theorem 1. For any number of rounds N N, there is algorithm that is guaranteed to find k-optimal contract with probability greater than or equal to - ô by using less than N rounds, where K. 6 are some suitable absolute constants.
Proof. We consider group of instances parametrized by a parameter (0, 1/sa). In each instance, we let A = {a, 42 } be the set of actions while we let Ω = {wi, W2, waa/ be the set of outcomes. Furthermore, the distributions (1/2,0 0, 1/2) and Fa, (0, e, e) with associated cost of Ca2 = and Ca2 = 1/4, respectively. In all the instances the principal's 's reward given by (0, 0, 1) while the optimal contract is equal to p" (0, 1/1e, 0), resulting in a principal's expected utility of u(p") = 8/1- -
the outcomes of the two actions
defined follows: Fa,
As first step, show that if Pw2 I 1/8c, then the principal's utility is most 9/s0-optimal. To show that, we first consider the case in which the agent selects action 01. In such a case, the highest expected utility achieved by the principal is at most 1/2, which occurs when they commit to the null contract (0, 0, 0). Clearly, the utility achieved in p (0, 0, 0) is not 9/80-optimal, for each possible E 1/so).
Then, we consider the case in which the agent selects action 02 and pwg < 1/8r. In this scenario, the highest principal's expected utility attained in the contract p' (0, 1/8c, sc)). Thus, the resulting principal's is expected utility is at most:
3
5
u(p') = Σ F (rw pww + (1-c)
<
8c
8
8"
WER
which not 9/sa-optimal, for any value of (0. 1/80. Consequently, for each possible action selected by the agent, if Pws. < 1/sc, then the expected utility of the principal's 's utility cannot be o/stmmp
To conclude the proof, we consider two instances characterized by 1/(SON log(2N)) and !/(ON?", for an arbitrary fixed > In the following, we let P,, and Pe,, be the probability measures induced by the N-rounds interconnection of an arbitrary algorithm executed in the first and the second instances. respectively. Furthermore, we denote with KCL P.g)) ) the Kullback-Leible divergence between these two measures. Then, by applying the Kullback-Leine decomposition, with simple calculation we can show that:
N Σ
KC(P,,,Pe)) < E,
(C Fea)
26

---

Published as a conference paper at ICLR 2024
leg1o)/(%/)) (1 log (1-(((/)/)))
2 2/79,
where we let FX and FXe be the distributions over outcomes of action a, A in the first and the second instances, respectively.
We now introduce the event I, defined as the event in which the final contract returned by given algorithm satisfies the condition Pws 2 1/8cg. We observe that if the event I holds in the first instance, then the learned contract provides negative principal's utility. On the contrary, if such an event does not hold in the second instance, the final contract is not 9/80-optimal, previously observed. Then, by the Pinsker's inequality we have that:
Per (I*) P.
(-x((KC(P,,; exp (-2/79))
(14)
Consequently, there exists no algorithm returning a 9/80-optimml with a probability greater or equal to exp (-2/79), thus concluding the proof.
Theorem Given probability at least - 8. where I is term that depends polynomially on m, n, and B.
10, Algorithm 5 achieves RD < Ō I I-- log(1/)) ( T4/5) with
Proof. Thanks to Theorem 2 we know that by employing an appropriate number of rounds, the solution returned by Algorithm T is p-optimal with probability at least - 6, for given values of and 6 greater than zero. Furthermore, we notice that the per-round regret suffered by Algorithm bounded by mB 1 during the execution of Algorithm [ and it most p for the remaining rounds. Formally, we have that:
TT) )
RT S
m
log
p
Thus, by setting p m/a B3/5 mm the cumulative regret is bounded by:
mm 8/57 1/5 input Algorithm 1 with probability least 1
Rr 5 mm B3/58/ log
T4/5)
concluding the proof.
27


Reviews:
[{"review_id": "dzgY2MfPS7", "reviewer": "Reviewer_Mt7g", "summary": "This paper studies the problem of learning optimal contracts in a principal-agent setting with focus on the setup where the size of the agent's action space is small.", "questions": "- Do we know any lower bounds for the sample complexity of learning optimal contracts when the action size is small? Do you think it is possible to improve the current method beyond the constant action size case (possibly under other assumptions)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper improves the previous sample complexity bounds for learning optimal contracts in the case when the number of actions is constant.", "weaknesses": "- It seems to me that the approach of this paper seems to be mostly based on the work of [Letchford et al., 2009; Peng et al., 2019], but this is not explicitly mentioned in the paper. This is acceptable to me, but I expect the authors to discuss and summarize the challenges of extending the previous approach to the current setting.\n\nsome minor comments:\n\n- Theorem 1 should rather be an observation or proposition than a theorem, since it is a quite obvious fact in learning optimal contracts, even though it might be mentioned explicitly in previous work.\n\n- Definition 1 should rather be an assumption than a definition. I also do not see any benefit of treating this condition as a high probability event. I think you are essentially restricting the learning problem to a subclass of instances where the approximately optimal contract has bounded payment.\n\n- The current notation is not very readable to me, and I would suggest the authors make some efforts on simplifying them. For example, you could use dot product instead of element-wise product over the outcomes spaces in many places.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "C7uj4GF4cB", "reviewer": "Reviewer_GCN2", "summary": "This paper studies the principal-agent problem where a principal seeks to induce an agent to take a beneficial but unobservable action through contracts. They aim to learn an optimal contract by observing outcomes. The paper proposes an algorithm that can learn an approximately optimal contract within a polynomial number of rounds related to the outcome space size. Specifically, they showed an algorithm with a sample complexity result of O(m^n T^4/5) and also converted it to an explore-then-commit online learning algorithm with sublinear regret.", "questions": "Could you provide some application domains where your honest-responding agent behavior holds?     \n    \n   \nHow is your Lemma 8 different from Lemma 4 by Zhu et al. [2022]? I feel like your results can be directly implied from their result about the Continuity of the principal’s utility function.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Learning the optimal principal’s strategy in principal-agent problems when the agent’s type is unknown has become an important problem in those kinds of games with sequential movements. Existing works mainly focused on Stackelberg (security) games. This paper introduced meta-actions to group together the agent’s actions associated with “similar” distributions over outcomes for the specific contract design problem where the agent’s action is unobservable. Then this paper demonstrates how to utilize this idea to learn the approximately optimal contract. The results seem well-executed and the characterization is interesting.", "weaknesses": "One major modeling concern I have is the assumption that the agent will honestly best respond to the principal’s queries, especially if they know that the principal is learning to play against him. This problem is particularly an issue in contract design — if the principal does not know the agent’s utility and wants to learn to play against the agent, then the agent would have strong incentives to manipulate their responses to mislead the principal to learn some non-optimal contracts and would like to do so to benefit himself. Could you elaborate a bit about the validity of the honest agent best response assumption, and some application domains where this assumption holds?\n\nOn the technical side, I feel like the contribution of this paper might be limited given Peng et al., [2019] and Zhu et al., [2022]. “The core idea of the algorithm is to progressively build two polytopes Ud and Ld” is highly similar to the algorithm proposed by Peng et al. [2019], except that here the agent’s action is not observable, so the authors replace it with some meta action, which is realized by the Action-Oracle and does not seem to be enough contribution for ICLR. As for the relaxed assumption regarding the constant volume, which seems to be highly dependent on the result Lemma 4 by Zhu et al. [2022], which shows the Continuity of the principal’s utility function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "JpsNkHQZhB", "reviewer": "Reviewer_NM4o", "summary": "This paper study the sample complexity (and its implication in online learning) of learning the optimal contract in the principal-agent problem. Specifically, they consider the setting where the principal, who does not know the forecast matrix of the agent, offers the agent a contract, and the agent performs the action that maximizes the agent's own utility, and then the principal observes the outcome as a result of the action performed by the agent but not the action itself. The principal may choose different contracts and repeat the above process to figure out the optimal non-negative and bounded contract that maximizes the principal's utility, and the number of repetitions is the sample complexity of this problem.\n\nThe main result of this paper is an algorithm that has $\\tilde{O}(m^n)$ sample complexity, where $m$ is the number of the outcomes, and $n$ is the number of the actions of the agent. In particular, the sample complexity is polynomial in $m$ when $n$ is a constant.\n\nThe key observation underlying this result is that the polytope $\\mathcal{P}_i$ containing exactly all the contracts to which the best response of the agent is the same action $i\\in[n]$, is defined by $m+n$ inequalities ($m+1$ inequalities that force the contract to be non-negative and bounded, and $n - 1$ inequalities that force the action $i$ to be better than other actions for the agent). Hence, $\\mathcal{P}_i$ has at most $\\binom{m+n}{m}=\\binom{m+n}{n}\\le (m+n)^n$ vertices.\n\nThe algorithm starts with an outer approximation $\\mathcal{P}_i'$ of $\\mathcal{P}_i$ ($\\mathcal{P}_i'$ is initially defined by the $m+1$ inequalities that force the contract to be non-negative and bounded), and as long as there is some vertex $v$ of $\\mathcal{P}_i'$ that is not in $\\mathcal{P}_i$ (in other words, the agent's best response to the contract $v$ is some $j\\neq i$), it can easily find an inequality (using the structure of the principal-agent problem) that approximately corresponds to the constraint ``action $i$ is better than action $j$ for the agent'', and then it adds this inequality to $\\mathcal{P}_i'$. After the algorithm iteratively finds $n-1$ such inequalities, $\\mathcal{P}_i'$ will be approximately same as $\\mathcal{P}_i$. Moreover, to find one such constraint for the current iterate $\\mathcal{P}_i'$, the algorithm only needs to evaluate at most all the contracts corresponding to all the vertices of $\\mathcal{P}_i'$, the number of which is bounded $(m+n)^n$ by the key observation above.", "questions": "Could you address the comments in the weakness section?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The result is original, and the idea is simple and nice.\n* The writing is good overall.", "weaknesses": "I think the biggest weakness of this paper is that it studies the setting without prior distribution of the agent's type.\n* First of all, I feel that the sample complexity problem is not well-motivated in this setting -- If I'm the principal, when an agent comes, I won't try to find my optimal contract merely for this agent by signing the agent multiple times with different contracts and observing the outcomes. I would only use this approach, when there is a large candidate pool, and I do not know the prior distribution of the candidates' skills.\n* Moreover, the previous work of [Zhu et al. 2022] studies the setting with prior distribution of the agent's type. Their open question is also posed in that setting, so I think ``solves an open problem by Zhu et al.'' is an overclaim.\n\nOn a separate note, the space of contract considered in this paper is different from that in [Zhu et al. 2022]. In this paper, the contract is bounded in the sense that the sum of the payments for all outcomes is bounded by some number $B$, but in [Zhu et al. 2022], the contract is bounded in the sense that the payment of each outcome is bounded by some number $B$. That is, even in the narrow setting without prior distribution, the problem studied by this paper is not quite the same as the original one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (poster)