Contracting with a Learning Agent
Authors: Guru Guruganesh
Yoav Kolumbus
Jon Schneider
Inbal Talgam-Cohen
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Joshua Ruizhi Wang
S. Matthew Weinberg
Venue: NeurIPS 2024 poster (2024)
Keywords: Contract Theory
Learning
No-Regret Learning
Mean-Based Learners
Primary area: algorithmic_game_theory
TL;DR: Optimal contract design for principals interacting with no-regret learning agents

Abstract: Real-life contractual relations typically involve repeated interactions between the principal and agent, where, despite theoretical appeal, players rarely use complex dynamic strategies and instead manage uncertainty through learning algorithms.

In this paper, we initiate the study of repeated contracts with learning agents, focusing on those achieving no-regret outcomes. For the canonical setting where the agent’s actions result in success or failure, we present a simple, optimal solution for the principal: Initially provide a linear contract with scalar $\alpha > 0$, then switch to a zero-scalar contract. This shift causes the agent to “free-fall” through their action space, yielding non-zero rewards for the principal at zero cost. Interestingly, despite the apparent exploitation, there are instances where our dynamic contract can make \emph{both} players better off compared to the best static contract. 

We then broaden the scope of our results to general linearly-scaled contracts, and, finally, to the best of our knowledge, we provide the first analysis of optimization against learning agents with uncertainty about the time horizon.

Contracting with a Learning Agent
Guru Guruganesh"
Yoav Kolumbus
Jon Schneider'
Inbal Talgam-Cohen'
Emmanouil-
Samaanuul-Vasileios Vasileios Vlatakis-Gkaragkoumi
Joshua R. Wang"
S. Matthew Weinberg
Abstract
Real-life contractual relations typically involve repeated interactions between the principal and agent, where, despite theoretical appeal, players rarely use complex dynamic strategies and instead manage uncertainty through learning algorithms.
In this paper, we initiate the study of repeated contracts with learning agents, focusing on those achieving no-regret outcomes. For the canonical setting where the agent's 's actions result in success or failure, we present a simple, optimal solution for the principal: Initially provide a linear contract with scalar 0, then switch to zero-scalar contract. This shift causes the agent to "free-fall" through their action space, yielding non-zero rewards for the principal zero cost. Interestingly, despite the apparent exploitation, there are instances where our dynamic contract can make both players better off compared to the best static contract.
We then broaden the scope of our results to general linearly-scaled contracts, and, finally, to the best of knowledge, we provide the first analysis of optimization against learning agents with uncertainty about the time horizon.
Introduction
In the classic contract setting, principal (she) incentivizes agent (he) to invest effort in project. The project's 's success depends stochastically on the effort invested. The incentive scheme, a.k.a. contract, is performance-based outcome, rather than directly on the agent's effort. This gap between the agent's costly effort and the stochastic outcome creates moral hazard, and makes contract design a challenging problem.
it determines the agent's 's payment based the project's
Due to their immense importance in practice, the design of contracts has long been studied in Economics, forming rich body of literature that was recognized by Nobel prize in 2016. Recently, there has been a surge of interest in computational aspects of contract design, leading to the ongoing development of
algorithmic theory of contracts (see, c.g., [1. 7, 8. 20, 21, 28, 29, 33, 30, 42, 43, 34, 51, 57, 62, 67]). Much the computational research has focused on the classic, one-shor contract setting the principal and agent share single interaction, in which the principal offers contract and the agent chooses best-response action.' Yet, this overlooks the fact that in reality, "most principal-agent relationships are repeated or long-term," " i.e., the same agent exerts effort for the principal repeatedly over time [14]. The goal of this paper is to extend algorithmic contract
Google Research, gurugggoogle com, www.eeeioooogglee...oooooo
joshuavangggoogle.comm
CConell University. yoav. kollubbss@correll. edu
'Tll Aviv University, inballalggmmgmail.ccom
BBerkeley University, amylatakkis@eerkell.y edu
1 Princeton University, smeeiinberg@princetoon. edu
Another setting that has been considered is series of one-shot interactions with multiple agents, enabling the principal to learn the best contract for the agent population (see, e.g., [32, 23, 47, 69]). An exception is the work [56], which studies a novel long-term principal-agent model tailored afforestation. Their principal
pays whenever tree's state Markov chain progresses; their agent responds based on state (not on learning).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

theory beyond the basic single-shot setting and into the realm of repeated contracts, applying fresh perspective to contract design for repeated interactions.
Repeated contracts have heen studied extensively in Economics. The literature explores many possible variations of how outcomes, actions, and contracts may evolve over time the principal and agent interact (see, c.g., [64] and references therein; for surveys, see [24]] [14, Chapter 10], and [55, Chapter 8).. The main theme of this literature is that the incentive problem grows significantly in complexity with repetition. First, the agent's action set becomes extremely rich, and optimizing over it is highly non-trivial. Second, the optimal contract itself typically becomes excessively complex - "too complex to be descriptive or prescriptive for incentive contracting in reality" [14]. Given this complexity, agents typically respond to repeated strategic interactions in practice in a manner consistent with no-regret learning [60, 61] (see Appendix A for a more detailed overview).
Building this, we revisit the classic question of optimal contract design in repeated setting, this time considering a no-regret learning agent. Hence, the main question we address in this work, referring to the optimal dynamic contract, is:
If the principal knows that the agent is a no-regret learner, what contract sequence should she offer?
1.1 Our Model and Contribution
Optimizing against no-regret learner. We study the optimal dynamic contract in the following setting: A principal and agent interact over T time steps for some large T. In each step t E [T], the agent takes costly action as recommended by the no-regret learning algorithm, and the principal pays the agent according to the current contract and the action's 's outcome. The contracts can be modified by the principal over time dynamically (and adaptively). A simple benchmark is achieved by not modifying them, that is, simply repeating the optimal one-shot contract in each round. We refer to this as the optimal static contract. It is not hard see that the principal's ''s revenue in this case against a no-regret agent will essentially be the optimal static revenue (Observation I.I in Appendix I).
Our main focus is "mean-based' learning agents, who apply simple, natural and common learning algorithms, such as multiplicative weights [4], follow the perturbed leader [45, 50], or EXP3 [6]. Intuitively, mean- based algorithms consider the cumulative payoffs from each of the actions, and play actions which performed uub-optimally in the past with a low probability (see Section 2 for a precise definition, taken from [15]).
We also briefly consider more sophisticated agents who utilize no-swap-regret, rather than mean- based, learning (e.g., [13]). Against such agents, crisp optimal strategy is immediate from previous work on general repeated games against learners [27, 59]: known that the best static solution is also the best dynamic one. In our context this means that dynamic contract can achieve better than the optimal static contract (Observation I.2 in Appendix 1). Since no-swap-regret learning also counts as particular type of no-regret learning, this result also explains why focusing on mean-based learning is necessary for a separation result. Interestingly, we show that both players can be better off if the agent applies more naive, mean- baand learning (although, expected, there are also many cases where the agent winds up worse off due to this interaction). Due to space constraints, we defer more extended discussion of related work Appendix A and highlight here contributions.
Our contribution. In this paper, we give a clean, tractable answer to our main question as follows. When the agent's choice among n actions can lead to success/failure of the project, the principal's s optimal dynamic contract surprisingly simple (especially compared to the optimal dynamic auction (15)): offer the agent one carefully-designed contract for a certain fraction of the T rounds (both contract and fraction are poly-time computable). then switch to the zero contract (that is, pay the agent nothing) for the remaining rounds. In this setting, simple linear single-parameted contracts are optimal, and this is actually the only property required for our result. Our analysis thus generalizes to any setting where the principal utilizes only linear contracts. Note that much of the previous literature on algorithmic contract design has focused on the canonical contract setting with success/failure outcomes and/or on the ubiquitous class of linear contracts (see, e.g., [1, 7, 28, 29, 56]).
Unlike the optimal dynamic auction, the optimal dynamic contract divides the welfare among the principal and agent. In fact, it can increase the utility of both players (and thus also the total welfare) in comparison to the optimal static contract. One interpretation of this result is the following. While no-swap-regret algorithm is better for the agent against an adversarial player, agent who commits to

---

using a mean- of common interest. A similar advantage of simple no-regret learning over no-swap-regret was noted in different context by [16].
mean-basee based algorithm allows the principal more freedom to dynamically implement outcomes
Our main result also generalizes to settings with rich set of outcomes beyond success/failure, as scaling"). scaling restriction, there exist principal- agent instances where the optimal dynamic contract does not take this form.
long as the principal changes the contract dynamically by scaling it ( ("single-dimenss However, we also show that absent this dingle-dimensiones
Equivalently, with non-linear contracts it possible for the principal to do strictly better than offering the same contract for several rounds and then switching to the zero contract.
As our second main result, we identify and address the following gap in the current literature on optimizing against no-regret learners: Implicit in all our positive results, as well as in all known results in this literature (see Appendix A), is the assumption that the optimizer knows the time horizon T. We show that when there is (even limited) uncertainty about T, the principal's ability to use dynamic contracts to guarantee more revenue than the optimal static contract diminishes. We achieve this by characterizing the optimal dynamic contract under uncertainty of T, and showing that the principal's added value from being dynamic sharply degrades with an appropriate measure of uncertainty.
1.2 Illustrative Example
Actions
"Failure"
"Success" 0
A canonical contract setting in which simple dynamic contract extracts higher expected revenue than the best static contract. The table entries show the outcome probabilities given the actions.
Figure I:
01: (ci 0/6)
02: (ea 1/6)
1/2
1/2
0g: (cg 3/6)
0
To demonstrate our model and findings, we give an example where a simple dynamic contract yields higher revenue than the best static contract. The analysis requires some familiarity with the basics of contract settings, which appear in the first paragraphs of Section for completeness. Consider the setting in Figure 1. There are three actions with costs C1, C2 C2 for the agent, leading, with the probabilitics shown in the figure, to two outcomes- "ffiluur""" and "success" " with rewards O and 1 for the principal. Since there are two outcomes, w.l.o.g. can consider linear contracts, which pay the agent a for success (leaving the principal with a payoff of 1 - a.).
Under an optimal static linear contract, the agent must be indifferent either between actions 1 and 2 or between actions 2 and 3 (otherwise, the principal is overpaying for incentivizing an action). The indifference contracts are denoted by ar12 = 1/3 and a2,3 = 2/3, respectively. These lead to the same expected utility for the principal, where the expectation over the probability of success:
(1,4 _/2 (1-a2,3) (22,3) 1 3.2 That is, both 0122 and 0223 are optimal static contracts.
Now consider a principal interacting with a mean-based learning agent. The principal initially offers the contract a + for 2/2 time steps, with some small >> O. The agent follows his mean-based strategy and plays action 3 (in I
o(T) fraction of the time with high probability), which yields a utility of roughly a 1 C3 6 per step for the agent and per step for the principal. Subsequently, the principal switches to the zero contract for the remaining time steps. From the perspective of the agent, at the time of the switch the cumulative utilities of actions 2 and 3 are roughly To (compared to zero from action 1). But in every step of the subsequent stage, the cumulative utility of action is degraded by an amount of 2 and the cumulative utility of action 2 is degraded by amount of 6. Thus the agent "falls" to action 2 and plays it until the last period T. The overall utility for the agent is approximately zero, and for the principal xs - 1 = I > JT. The principal thus improves her utility by a factor of compared to the optimal static contract.
Figure 2 shows graphical representation of the above dynamic contract. It turns out that this simple "free-fall" contract (see Definition 2.1) is also an optimal dynamic strategy for the principal, and in fact, this is not special property of the current example. In Section 3 we show that for any linear contract game, there exists an optimal strategy with this form: offer a fixed contract for a period of XT' steps and then switch to the zero contract. Moreover, we show that, surprisingly, this simple structure remains optimal also for general non-linear contracts, as long as their dynamics are characterized by single scalar parameter. For details, see Appendix D.
3

---

1.0
a=1
Curulattiv contract:
0.6
Average contract:
0.6
0,,1
03,3
012
01.1%
0.2
0.2
t/T
t/7
Two representations of the same dynamic contract, as applied to the contract setting described in Figure and repeated for 7 steps. The dotted red curve on the left describes the cumulative contract at time t function of f, with both axes normalized by T. The shaded areas represent the mean-hased best-response regions for the agent. The lines 01,2 and 02,3 the indifference curves between these regions. The right diagram depicts the same dynamic contract as function the fraction axis represents the average contract at time I. Pictorially, after steadily building the agent's incentives until time T/2, the principal cuts payments. During the remaining time, the agent "free-falls" through action regions.
Figure 2:
time i/T, where here vertical
1.3 Summary Results and Roadmap
We initiate the study of repeated principal-agent problems with a learning agent; the key takeaways from work are as follows:
Theorem (See Theorem 3.1 in Section 3.1). In success/failure settings, well as in arbitrary contruct settings where the principul restricts to linear contracts, the optimal dynamic contract against mean-based agent free-ffll contract. This optimal dynamic contract can be efficiently computed.
Theorem (See Theorem 3.2 in Section 3.2). Consider the space of repeated principal agent problems: in subset of this space of positive measure, both the principal and agent achieve unboundedly better expected utilities from the principal's 's optimal dynamic contract compared the optimal static contract.
One takeaway from the previous theorem that the principal and agent can both benefit when the agent commits to mean-based rather than no-swap-regret learning, in stark contrast to auctions (where buyer committing to mean-based strategy is left with zero payoff, because the auctioneer can extract the full surplus). We generalize our findings on the optimality of free-fall contracts to any dynamic contract with single-dimensional scaling.
Theorem (See Theorem D.I in Appendix D). In arbitrary contract settings, there is a free-fall contract that is optimal among dynamic contracts with single-dimensional scaling. A dynamic contract has single-dimensional scaling if starts from an arbitrary contract p mi and every time step E (T) plays o' d'p for some scalar a² 2 0.
In Section 3.3 and Appendix G, we demonstrate that in absence of single-dimensional scaling, there may not exist a free-fall contract that is optimal among dynamic contracts.
Finally, we investigate the impact of an unknown time horizon when optimizing against a no-regret learner. To the best of our knowledge, we the first that explore this aspect. Of course, there are standard techniques to help a learning agent can guarantee no-regret without knowing the time horizon (see e.g., [22, Section 2.3]). Typically, this agent manages to achieve with the same asymptotic (albeit with larger constant factor) additive regret term when moving from the known to unknown time horizon setting. We show that the situation is different on the other side; uncertainty on the part the principal regarding the time horizon significantly degrades her ability to outperform the best static contract. Whereas the agent's uncertainty was affecting their o(T) factors, the principal's uncertainty degrades their ((T) factor; although some slight ad advantage is still always possible.

---

Theorem (See Theorems 4.2-4.3 in Section 4), For any contract problem and error-tolerance parameter E >> O, there exists is some minimum time uncertainty ? so that for any minimum time horizon T, no randomized dynamic contract can guarantee the principal a (1 E) multiplicative advantage over the optimal static contract simultaneously for every time horizon T in the range [T. T. Conversely, for any contract problem and time uncertainty " 1, there is some nonzero error-tolerance parameter & >> O such that for a sufficiently large time horizon minimum L, there is a randomized dynamic contract that can guarantee the principal a (1 + 2) multiplicative advantage over the optimal static contract simultaneously for every time horizon T in the range [T,]].
2 Model
We first present basic (non-repeated) contracts, and the class of linear contracts; a familiar reader may wish to skip Sections 2. repeated contract settings (discrete and continuous).
Single-shot contract setting. There are two players, a principal and an agent. The agent has a finite set [n]] of n > actions, among which it chooses an action a and incurs a corresponding cost Ca 2 0 (in addition to a we will use to index actions). W.l.o.g. the actions are sorted by cost (cI C2 ... c.) and the cost of the first (mull) action is zero (c1 = 0). There is finite set [m] of m possible outcomes, and every action a is associated with a probability distribution Fa E Å m over the outcomes. The null action leads with probability 1 to the first (nall) outcome. Every outcome o is associated with a finite reward ro 2 0 for the principal (in addition to o we will use j to index rewards). We assume w.l.o.g. that T1 72 ... I'm and r1 = O. We denote the expected reward by Rs, = FEo=F, [ro] for action a. As is standard we assume no dominated actions: i) if Ca < Ca' then R., Ra and ti) for every action there exists contract that uniquely incentivizes it. The contract setting (a.k.a. principal-agent problem) (c, F, = (fCa, Fa {ro)==) is known to both players.
The game. The game in the basic (non-repeated) setting has the following steps:
(1) The principal commits to a contract p = (p;) Pj 2 O, where p3 S Pmax is the non- negative amount the principal will pay the agent if outcome j is realized. In particular, can be the zero contract in which p; = 0 for all j.
(2) The agent selects an action a E [n]. unobservable to the principal. and incurs a cost Ca.
(3) An observable outcome o realized according to distribution Fg. The principal receives reward ra and pays the agent Pa- The principal thus derives a utility (payoff) of ro - Po. and the agent of po Ca-
Expected utilities and optimality. In expectation over the outcomes, the utilities from contract and action are up(p,a) a) R. Eg [Po] for the principal, and u. (p, a) R. [po] ca for the agent. Summing these up we get the expected welfare R. Ca from the agent's chosen action a. For given contract p. let BR(p)
arg max, A (P, a) be the set of actions incentivized by this contract, i.e., maximizing the agent's 'ss expected utility (usually this will be a single element, but in the case of ties we include all actions in BR()).. The goal of the contract designer to maximize the principal's 's expected utility, also known as revenue. Such a contract is referred to as optimal.
Linear contracts. In a linear contract with parameter E [0, 1]. the principal commits to paying the agent a fixed fraction (commission) a of any obtained reward. Thus by choosing action a, the agent gets expected utility aR, Cu. and the principal gets (1 a) Ra. As a is raised from 0 to 1, the agent's 's expected utility is affected less by the action cost, and the agent's 's incentives align more with the principal's and with social welfare. This intuition is formalized by [33], showing that as increases, the agent responds with actions that have increasing costs, increasing expected rewards, and increasing expected welfares. 4 The critical a at which the agent switches from action i 1 to action i (for i > 1) is denoted by 04-1,i = (G (t-1)/(R, indifference point or breakpoint. For i we define 0k0,1 = O. Using this notation, for every linear contract a E (at-1,45 i;,++)), ). the agent plays action i. In the linear contract setting, the focus is on linear contracts and only such contracts are allowed.
R;-1), and is also referred to as an
'The non non-tegativvty of the contractual payments is known as limited liability [49]. Without it or some other form of risk aversion the principal could simply "sell the project" to the agent, trivializing the problem.
'The standard tie breakkinn assumption, according to which the agent breaks ties in favor of the principal, is less relevant here since we want to analyze all learning algorithms, regardless of how they break ties.
"We assume w.l.o.g. that for every action there is a linear contract a which uniquely incentivizes it (otherwise when focusing linear contracts we may omit this action from the setting).
5

---

2.1 Repeated Contract Setting: Discrete Version
We study a repeated contract setting (c, F, T), in which the above game (c. F,r) is repeated for T discrete rounds between the same principal and agent. The number of rounds T is called the time horizon. The setting is known to both players,' who update the contracts and actions in each round. The outcomes of the actions are drawn independently per round (past outcomes affect future outcomes only through learning). Denote the contract, action, realized outcome and reward at time t E [T] by p', a', o², r", respectively. The agent's 's payoff at time is P Cal. The sequence (p') of contracts is called a dynamic contract, and the T pairs {(p' aa aa))== form the trajectory of play. We define the following class:
Definition 2.1. A free-fall contract is dynamic contract in which the principal offers a (single-sho) contract p for the first T' < T rounds, and then offers the zero contract for the remaining rounds.
Learning agent. The agent's approach to choosing an action is learning-based, by applying no-regret algorithm (rather than based on myopic best-responding, as in the one-shot setting). Our analysis applies with full feedback on the performance of each action, where the agent observes the expected payoff's of all actions (whether taken or not - c.g. by observing someone else take that action), or with bandit feedback, where the agent observes only the achieved payoff' of the action taken. A delicate issue is that, unlike the standard scenario of learning in games, the payments for each action are stochastic. Thus, the agent must not only learn which action to take, but also the expected payment from each action. When T is large enough, the extra learning has a vanishing impact, and does not affect the analysis of players' utilities and strategies.
Our main focus is on the prominent family of mean-based algorithms. The idea behind mean-based algorithms is that they rarely pick action whose current mean is significantly worse than the current best mean. There exist such algorithms with both full and bandit feedback that are mean-based and achieve no-regret. In our setting, let ut be the expected utility the agent would achieve from taking action at round t, and let of = Ex= uf represent the cumulative utility achievable from action i up to time & given the principal's I's trajectory of play. Then:
Definition 2.2 ((15). A learning algorithm is "(T')-man--base if whenever of < o - (T)) T, then the probability that the algorithm takes action i in round is at most (()). We say algorithm is mean- based if it is (T)--aan- based for some (T) = o11).
Optimal dynamic contract. The design goal in the repeated setting is to find an optimal dynamic contract: a sequence (p") Y== that maximizes the total expected revenue against a lcarning agent (whether mean-based
no-swap-regret, where in either case we assume the worst-case such learning algorithm). In the linear contract setting, the sequence (a "a')== is composed of linear contracts. If maximizes the total expected revenue among all linear contract sequences, we say it is the optimal dynamic linear contract. We remark that it is without loss of generality to consider only linear contracts with < 1.
Note that, as described here, the contract sequence is fixed by the principal at the beginning of the game. We refer to such principal as oblivious. If the principal can choose p' as function of the agent's 's previous actions, we say the principal is adaptive. Our positive results (showing the principal can guarantec at least some amount of utility) hold even for oblivious principals, and our negative results hold even for adaptive principals.
Optimal static contract. In repeated setting, a static contract is sequence of contracts in which the same one-shot contract is played repeatedly. The repeated game with a static contract and a regret-minimziing agent is, in the limit T - 0o, equivalent to the classic one-shot contract game with best-responding agent (Observation I.1). A natural benchmark for dynamic contracts is thus the optimal static contract, in which the optimal one-shot contract is played repeatedly.
'In Section 4 we consider what happens when is unknown to the principal. The other parameters of the setting. if unknown, can be easily learned via sampling. No-regret learning is possible also with unknown 2'. 'Some small changes need to be made to this definition for the partial- feedback (bandits) setting Definition H.5 in Appendix H.3.
'This is non toiviaivial consequence of our proof machinery. The proof appears as Observation 1.3 in Appendix I for completeness.

---

2.2 Repeated Contract Setting: Continuous Version
To simplify the technical analysis, we now present a continuous version of our repeated contract setting. For the remainder of the paper we will primarily work in the continuous- timou model. We emphasize that the reduction to continuous time is for simplicity, and that the key ideas of our proofs are unrelated to it and can be applied to the discrete version of our setting as well.
Reduction to continuous time. In [27], the authors consider the problem of strategizing against mean-based learner in a repeated bi-matrix game, and show it reduces to designing dynamic strategies for simplified continuous-time analogue (note that the choice of continuous-tine analogue is tailored to mean-based learning it is not intended to be a special case of a general discrete-continun reduction against any learner). We pursue a similar reduction here, and show (in Theorem 2.4) how to reduce the problem of designing dynamic contracts in the discrete-ting setting (Section 2.1), to simpler problem in continuous-time setting, We later extend the reduction settings with an unknown time horizon (see Theorem H.3 in Section 4).
Trajectories of continuous play. In the continuous setting, rather than specifying the trajectory of play by a sequence of T contracts and responses, we instead specify it by a finite sequence π of tuples {(p", -", a²) )²"]]= each representing "segment" of play where the principal plays constant contract and the agent responds with constant action. Here, each pa 7 represents an arbitrary contract, each 7 E R20 represents the (fractional) amount of time that the principal presents this contract to the agent, and each a E [mi] represents the action the agent takes during this time. In the linear contract setting, we use the notation a instead of p* We sometimes refer to π as a contract, by which we mean the dynamic contract composed of p' ....... for segments of length T ...., .',..,, T
To form what call valid trajectory of play against mean-based learner, the responses a of the agent must satisfy certain constraints. Let
k
k (p W //T
===1
be the total duration the first segments, and the average contract offered by the principal for the first l segments, respectively. Then each a (for > 1) must satisfy at BR(p*-1) and at E BR(p"). In words, a must be a best-response to the historical average contract both the beginning and end of segment & (and therefore also throughout segment k))
The following is continuous analogue of Definition 2.1.
Definition 2.3. A free-fall trajectory is game trajectory in which p* 0 for all k >> 1.
Optimal trajectory. The expected utility of the principal along trajectory æ is given by
Util(TT Ek rurppp" at)
TK
Let U* =us, Util(T), where the sup runs over all valid trajectories of arbitrary finite length. We think of U* as the maximum possible expected utility of the principal in the continuous setting game. The following theorem (a direct analogue of Theorem in [27]) connects U* to what is achievable by the principal in our original discrete-time game.
Theorem 2.4. Fix any repeated principal-agent problem with T rounds, and let U* denote the optimal expected utility of a principal in the continuous analogue. Then:
1. For any 0, there exists oblivious strategy for the principal that gets at least (U* <)T - oT) expected utility for the principal against an agent running any mean-based algorithm A.
2. For any ε > 0, there exists a mean-based algorithm A such that no (even adaptive*) principal can get more than (U* + +6T + o(T) expected utility against an agent running A.
The proof of Theorem 2.4 closely follows the proof in [27] and is deferred to Appendix H.
In the feetbal-eeebbck (bandit) setting. this result only holds for deterministic adaptive principals and not for randomized adaptive principals (with full hell-feebback it holds for either); see Appendix H.3 for further discussion.
7

---

One important thing to note about Theorem 4 is that the first part is constructive. In fact, the discrete- time strategy for the principal corresponding to a trajectory π is essentially the straightforward extrapolation, which plays each contract p for =t T rounds (although a slight perturbation is Tx
necessary to account for segments with non-unique best-response). This means that when we show, in Theorem 3.1, that the -uliti--ppimizing æ for U** takes the form of a free-fall trajectory, we are simultaneously showing that free-fall dynamic contract is asymptotically optimal in the original discrete- time setting.
Note that all the above definitions (and the reduction of Theorem 2.4) extend to the specific case where the learner is only allowed to use linear contracts. In this setting, we will write a = Σx== ax Tk/ /Ei=1 7k in place of p*
3 Linear Contracts
In this section we focus on the case where the principal restricts to using only linear contracts in every step of the interaction with the agent (one example is when there are = 2 outcomes, such as success and failure; in this case, arbitrary contracts can be described as linear contracts). We begin, in Section 3.1, by showing that without loss of generality, optimal dynamic contracts take the form of free-fall contracts, and in Appendix D we generalize this result to a broader class of general contracts with single-dimensional scaling. Then, in Section 3.2, we analyze the implications of optimal free-fall contracts on the welfare and on the agent's utility. In particular, we show that dynamic contracts that are optimal for the principal can improve the utilities for both players compared to their utilities under the best static contract. Finally, in Section 3.3, we show that for unrestricted dynamic contracts, free-fall contracts may no longer be optimal.
3.1 Free-Fall Contracts are Optimal Linear Contracts
The following theorem shows that free-fall contracts are optimal dynamic linear contracts. Theorem 3.1. Let x be any linear dynamic contract. Then, there exists a free linear contract x! where Util(T²) Util(T), and which can be computed in time polynomial in the problem size.
The proof is deferred to Appendix B and hinges on applying sequence of "rewriting" rules which allow us to gradually transform any given linear dynamic contract π with a free-fall linear contract T'. At high level, the crux of the proof is that any segment of the trajectory can be thought of as a combination of "stalling" at the current action and "falling" to the action below. Under linear contracts, the principal prefers to stall when higher action is being induced. Grouping together all the stall at the highest action used exactly results in a free-fall contract.
3.2 Implication to Welfare and Agent's Utility
In the example shown in Section 1.2, the free-fall dynamic manipulation that the principal made degraded the overall welfare, and all the added profits for the principal were at the expense of the agent. We demonstrate that this is not always the case; there are other scenarios where dynamic manipulations where the principal, optimizes her revenue, can actually be Pareto improvements over the best static contract, increasing the overall welfare.
Example (Welfare improvement). Consider the setting depicted in Figure with a slight variation where the cost of action 2 is 1/2+e, with e < 1/T)). In this case, the best static contract incentivizes action 1 and yields a utility of for the principal and zero for the agent. However, the best dynamic contract remains the same as in the previous analysis: it starts by incentivizing action 2 for period of 2T steps and then transitions to action 1 by offering zero payments for the remaining time. This results in a utility of T for the principal and zero for the agent, thereby increasing welfare by a factor of 5/4 without altering the agent's utility.
Next, we show the existence of "win-win" scenarios where optimal dynamic contracts can enhance the payoffs for both the principal and the agent compared to the best static contract. The improvement in welfare can be substantial, reaching much as ((n). essentially achieving full welfare. Specifically, we establish that the multiplicative gap between the utilities of the best static contract and those of the best dynamic contract can be O(n) for the principal's utility and (log(n)) for the agent's 's utility.
Theorem 3.2 (Win-win optimal dynamic contracts). There exist repeated contract settings where an optimal dynamic contract improves expected welfare by (n)) multiplicative factor compared
8

---

to the best static contract, and where the agent's 's expected utility improves by a factor of O (log(()) Moreover, these settings have a positive measure in the space of repeated contract games.
The idea of the proof is to look at games where the values for the principal when incentivizing each action are similar, but the actions differ significantly in terms of welfare. Then, by investing a small amount of additional payment in the early stages of the game (compared to the best static contract), the principal can incentivize the agent substantially improve welfare, initially in the form of higher profits for the agent. This added welfare is then shared between the players during the free-fall stage of the dynamic.
The proof is deferred to Appendix C. One interesting point about the example presented in the proof is that if the agent had used a "smarter" learning algorithm that guaranties low swap regret, then the outcome of the best static contract would have been obtained (see Observation 1.2 in the appendix, following the analysis of [27]). The agent in this case would have had lower utility. That is, using better algorithm leads to a worse outcome! The explanation for this counter-intuitive result is that a mean-based regret-minimizing algorithm is only guaranteed approach the set of Coarse Correlated Equilibria (CCE), whereas no-swap-regret dynamics must approach the set of Correlated Equilibria (CE,& a subset of the set of CCE's). There are games in which some CCE distributions of play give higher utilities to the players than all CE distributions (see e.g., [36, 53] for examples in auctions, and [16] for related example in general games). In other words committing use algorithm with weaker worst-case guarantees yields better woon-wortt-asc) results.
3.3 General Contracts and Free-Fall
Unlike in the linear contract setting and the single digensiimesi scaling setting, free-fall contracts not optimal in the general contract setting. We provide an example outlining this in Appendix G. In fact it is an open question whether the the optimal dynamic contract is computable.
Unknown Time Horizon
Up until now, the principal has been able to take advantage of precisely knowing the time horizon. Notably, this assumption of knowledge of the time horizon underlies all prior theoretical results in the literature on optimization against learning algorithms. In this section, the principal only approximately knows this parameter. We will consider the case where the principal knows that the time horizon T falls into some range []. and wants to guard against a worst-case choice of time horizon from that range. What are the trade-off's between the time uncertainty and how much additional principal utility we can get over the best static contract? To explore these concepts precisely, we introduce the following definition:
explore what happens when
Definition 4.1. Suppose we have a principal- ageett problem (c, r). Let R. be the single-round
profit of the optimal static linear contract for this problem. We say that pair (e, 7) is feasible with respect to F, for all sufficiently large time horizons L, there exists a (potentially randomized)
principal algorithm A such that the (expected) profit of A at any time E [I. = [T>]] is at least (1 + e)tR, (and infeasible with respect to (c, F,r) otherwise).
The last part of our results is Theorem 4.2: for every principal- problem and any error-tolerance e > 0, it is impossible to indefinitely maintain an advantage over the optimal static contract. To be more precise, when y is (xps))()ss) we know that the instance has become (E)n) infeasible (for some instances, this infeasibility transition may occur earlier). We argue this via a potential function; in order to stay a constant factor ahead of the optimal static contract, the principal must be constantly giving up potential. To complement this result, in Theorem 4.3, we show that all time ratios y 2 permit some advantage & over the optimal static contract. We manage to achieve at least (2 (poly 7)) for all problems where the optimal dynamic contract (with known time horizon) outperforms the optimal static contract. These ideas are captured in the theorems below:
Theorem 4.2. Suppose we have principal-agent problem (c, F, F.r). For every > 0, there exists 2 such that (c, infeasible with respect to F.) for all 7 2
'In fact, for mean-based algorithms there is stricter characterization of the set of equilibria to which they may converge [53], but the above explanation still holds.

---

Theorem 4.3. Suppose we have principal- agent problem (c, F.r). If there exists a such that for any O and n 2 2. (c.7) is infeasible, then there are no dynamic strategies that outperform the optimal static linear contract.
The proof of Theorem 4.2 in Appendix E: Theorem 4.3, Appendix F. The key ideas are as follows. For Theorem 4.2, we construct potential function which assigns a value to the current time-averaged linear contract, and show that any principal forced to slowly sacrifice this potential as the possible time horizon gap grows. For Theorem 4.3, any dynamic strategy that outperforms the optimal static linear contract can also be made to either start or end at the optimal static linear contract. This allows us to pad such strategy to last for longer amount of time by adding a segment that just stalls at the optimal static linear contract. One technical issue we have to handle is that trajectories must be evaluated over the interval T T instead of at single time; this multidimensionality means must now consider distributions of trajectories (see Appendix H).
5 Conclusion
In this paper, we provide clean and tractable answer to our main question. When the agent's choice among n actions can lead to the success or failure of a project, the principal's optimal dynamic contract is surprisingly simple. Specifically, the principal should offer a carefully designed contract for a certain fraction of the T' rounds (both the contract and the fraction are poly-time computable), then switch to zero contract (i.e., pay the agent nothing) for the remaining rounds. Our main result also generalizes to settings with a rich set of outcomes beyond success/failure, as long as the principal changes the contract dynamically by scaling it ("single-ding diingie-dimensional scaling"). However, we show that without this single-dimensional scaling restriction, there exist principal-agent instances where the optimal dynamic contract does not take this form. In these cases, with non-linear contracts, the principal can do strictly better than offering the same contract for several rounds before switching to zero contract.
As our second main result, we address a significant gap in the current literature on optimizing against no-regret learners: the assumption that the optimizer knows the time horizon T. We show that when there is uncertainty about T, even if limited, the principal's 's ability to use dynamic contracts to guarantee more revenue than the optimal static contract diminishes. We characterize the optimal dynamic contract under uncertainty of T, demonstrating that the principal's added value from being dynamic sharply degrades with an appropriate measure of uncertainty.
Open Problems. The computational study of repeated contracts, particularly with learning agents, raises many open questions. These include determining the optimal dynamic contract when the principal is not restricted to one-dimensional dynamics, and the computational complexity of finding it. Additionally, it involves identifying the optimal dynamic contract against learning agent with hidden type, thereby unifying our contract model with the auction model of [15]. Another intriguing area is understanding what the optimal dynamic contract would be against a team of multiple learning agents. Finally, it is crucial to explore the effects on welfare and utilities when there are two learning players, rather than learner and an optimizer.
A seinowledgmente and Disclosure of Funding
This work received funding from the European Research Council (ERC) under the European Union's 'ss Horizon 2020 research and innovation program (grant No.: 101077862, project: ALGOCONTRACT,
PI: Inbal Talgam- Cohenn,, by the Israel Science Foundation (grant No.: 3331/24), by the NSF-BSF (grant No.: (021680), by the NSF (grant No.: 194-194 PI: S. Matthew Weinberg) and by Google Research Scholar Award. During Professor Weinberg's is development of this paper, he participated as an expert witness on behalf of the State of Texas in ongoing litigation against Google (the "Google Litigation").
References
[1] Tal Alon, Paul Dütting, Yingkai Li, and Inbal Talgam-Cohen. Bayesian analysis of linear contracts. In ACM Conference on Economicy and Computation, EC, page 66, 2023.
[2] loannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson. Noah Golowich, and Tuomas Sandholm. Near -etr-optimal no-regret learning for correlated equilibria in multi- general-sum games. In ACM Symposiun Theory of Computing, STOC, pages 736 236-749,00 2022.
10

---

[3] L. Anderlini and L. Felli. Incomplete written contracts: Undescribable states of nature. Quarterly Journal of Economicx, 109:1085-1124, 1994.
[4] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicatiie weights update method: A meta-algorithi and applications. Theory of Computing, 8(1): 164, 2012.
[5] Eshwar Ram Arumachaleswaran, Natalic Collina, and Jon Schneider. Parcto-optimal algorithms for learning in games. arXiv preprint 24f.:2200.0094444 2024.
[6] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, SICOMP, 32(1))48-77, 2002.
[7] Moshe Babaioff, Michal Feldman, Noam Nisan, and Byal Winter. Combinatorial agency. Journal of Economic Theory, 147())999-11055 2012.
[8] Moshe Babaioff, Yoav Kolumbus, and Eyal Winter. Optimal collaterals in multi-enterrrrie investment networks. In Proceedings of the ACM Web Conference 2022, pages 79 89, 2022.
[9] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel Procaccia. Commitment without regrets: Online learning in Stackelberg security games. In ACM Conference on Economics and Computation, EC, pages 61-78, 2015.
[10] Omer Ben-Porat, Yishay Mansour, Michal Moshkovitz. and Boaz Taitler. Principal- reward shaping in MDPs. In Proceedings of AAAI, 2024, Forthcoming.
[11] B. Douglas Bernheim and Michael D. Whinston. Incomplete contracts and strategic ambiguity. The American Economic Review, 88(4))902-99) 02229922,11 1998.
[12] Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimization and the price of total anarchy. In ACM Symposium on Theory of Computing, STOC, pages 373-382, 2008.
[13] Avrim Blum and Yishay Mansour, From external to internal regret. Mach. Learn. Res., 8:1307-1324, 2007.
[14] Patrick Bolton and Mathias Dewatripont. Contract Theory. MIT press, 2005.
[15] Mark Braverman, Jieming Mao, Jon Schneider. and S. Matt Weinberg. Selling to no-regret buyer. In ACM Conference on Economics and Computation, EC, pages 523-538, 2018.
[16] William Brown, Jon Schneider, and Kiran Vodrahalli, Is learning in games good for the learners? In Annual Conference on Neural Information Processing Systems, NewrIPS, 2023.
[17] Sébastien Bubeck, Nicolo Cesa- Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi- bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[18] Linda Cai. S. Matthew Weinberg. Evan Wildenhain, and Shirley Zhang. Selling to multiple no-regret buyers. Working paper available https: pettpps://ariiin /ttp//axivvvc/////// org/ pdf/ 23077 04175. 04175.pdf, 2023.
[19] Modibo K. Camara, Jason D. Hartline, and Aleck C. Johnsen. Mechanisms for a no-regret agent: Beyond the common prior. In IEEE Annual Symposiun Foundations of Computer Science, FOCS, pages 259-270, 2020.
[20] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti, Bayesian agency: Linear versus tractable contracts. Artif. Intell., 307:103684 2022.
[21] Matteo Castiglioni, Alberto Marchesi. and Nicola Gatti, Multi-agent contract design: How to commission multiple agents with individual outcomes. In ACM Conference Economics and Computation, EC, pages 412-448 2023.
[22] Nicolo Cesa-Bianchi and Gábor I Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[23] Alon Cohen, Argyrios Deligkas, and Moran Koren. Learning approximately optimal contracts. In International Symposium on Algorithmicc Game Theory, SAGT, pages 331-346, 2022.
[24] Vincent P. Crawford. Dynamic games and dynamic contract theory. Journal of Conflict Resolution, 19(2):195-224, 1985.
[25] Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. In IEEE Anmual Symposium Foundations Computer Science, FOCS, pages 2016.
11

---

[26] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Prior-free dynamic auctions with low regret buyers. In Annual Conference on Neural Information Processing Systems, NeurIPS, pages 4814-4814, 2019.
[27] Yuan Deng, Jon Schneider, and Ralasubramanian Sivan. Strategizing against no-regret learners. In Annual Conference on Neural Information Processing Systems, NewrlPS, pages 1577-1585, 2019.
[28] Paul Dütting Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts. In IEEE Anmual Symposium on Foundations of Computer Science, FOCS, pages 815-826, 2021.
[29] Paul Düting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In ACM Symposium on Theory of Computing, STOC, pages 1311-1324, 2023.
[30] Paul Dütting, Michal Feldman, and Yoav Gal Tzur. Combinatorial contracts beyond gross substitutes. pages 92-108, 2024.
[31] Paul Dütting, Michal Feldman, and Daniel Peretz, Ambiguous contracts. ACM Conference on Economics and Computation, EC, page 539, 2023.
[32] Paul Dütting, Guru Guruganesh, Jon Schneider, and Joshua Wang. Optimal no-regret learning of one-sided Lipschitz functions. In International Conference on Machine Learning, ICML, pages 8836-8850, 2023,
[33] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus optimal contracts. In ACM Conference on Economics and Computation, EC, pages 369-387, 2019.
[34] Paul Dütting, Tim Roughgarden, and Inbal Symposium on Discrete Algorithms, SODA, pages 2688-2707, 2020.
The complexity of contracts. In ACM-SIAM
[35] Eyal Even-Dar, Yishay Mansour, and Uri Nadav. On the convergence of regret minimization dynamics in concave games. In ACM Symposium Theory of Computing, STOC, pages 523 532, 2009.
[36] Michal Feldman, Brendan Lucier, and Noam Nisan. Correlated and coarse equilibria of single-item auctions. In International Conference on Web and Internet Economics, WINE, pages 131-144, 2016.
[37] Giannis Fikioris and Êvva Tardos. Liquid welfare guarantees for no-regret learning in sequential budgeted auctions. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 678-698, 2023.
[38] Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Falgam-Cohert and Nir Rosenfeld. Strategic classification in the dark. In International Conference on Machine Learning, ICML, pages
2021.
[39] Angeliki Giannou, Emmaanuull-aasinn rate of convergence of regularized learning in games: From bandits and uncertainty to optimism and beyond. Advances in Neural Information Processing Systems, 34:22655-22666, 2021.
Matakis-Gkaragkouiii and Panayotis Mertikopoulos, On the
[40] Angeliki Giannou, Emmanouil Vasileios VlatakisGGkarakee of the strictest: Stable and unstable equilibria under regularized learning with partial information. In Conference on Learning Theory, pages 2147-2148. PMLR, 2021.
and Panayotis Mertikopoulos. Survival
[41] David L Gregory. The problematic employment dynamics of student internships. Notre Dame JL Ethics & Pub. Pol'y, 12:227, 1998.
[42] Guru Guruganesh, Jon Schneider, and Joshua Wang. Contracts under moral hazard and adverse selection. In ACM Conference on Economics and Computation, EC, pages 563-582, 2021.
[43] Guru Guruganesh, Jon Schneider, Joshua R. Wang, and Junyao Zhao. The power of menus in contract design. In ACM Conference Economics and Computation, EC, pages 818 848, 2023.
[44] Minbiao Han, Michael Albert, and Haifeng Xu. Learning in online principal-agent interactions: The power of menus. Working paper available at https: //axxiv. org/abs. aa//a////331/ 22122. 09869, 2023.
[45] James Hannan. Approximation to Bayes risk in repeated play. In Contributions to the Theory of Games (AM-39), Volume III, pages 97 139, Princeton University Press, 1957.
[46] Jason D. Hartline, Vasilis Syrgkanis, and Éva Tardos. No-regret learning in Bayesian games. In Annual Conference on Neural Information Processing Systems, NewrIPS, pages 3061-3069, 2015.
[47] Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowd- sourcing markets: Bandit algorithms for repeated principal- problems. Journal of Artificial Intelligence Research, 55:317-359 2016.
12

---

[48] Bengt Holmström and Paul Milgrom. Aggregation and linearity in the provision of intertemporal incentives. Econometrica, 55:303-328, 1987.
[49] Robert D. Innes. Limited liability and incentive contracting with ex-ante action choices. Journal of Economic Theory, 52(1):45-67, 1990.
[50] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):91-3377, 2005.
[51] Jon Kleinherg and Manish Raghavan. How do classifiers induce agents invest effort strategically? In ACM Conference on Economics and Computation, EC, pages 825-844, 2019.
[52] Yoav Kolumbus, Joe Halpem, and Eva Tardos. Paying to do better: Games with payments between learning agents, arXiv preprint arXiv:2405. 20880, 2024.
[53] Yoav Kolumbus and Noam Nisan. Auctions between regret-minimizing agents. In ACM Web Conference, WebConf, pages 100-111, 2022.
[54] Yoav Kolumbus and Noam Nisan. How and why to manipulate your own agent: On the incentives of users of learning agents. In Annual Conference on Neural Information Processing Systems, NeurIPS, 2022.
[55] Jean-Jacques Laffont and David Martimort. The Theory of Incentives: The Principal-Agen Model. Princeton University Press, 2009.
[56] Wanyi Li, Nicole Immorlica. and Brendan Lucier. Contract design for afforestation programs. In International Conference on Web and Internet Economics, WINE, pages 130, 2021.
[57] Yingkai Li, Jason D. Hartline, Liren Shan, and Yifan Wu. Optimization of scoring rules. In ACM Conference on Economics and Computation, EC, pages 988 989, 2022.
[58] Thodoris Ly Lykouris. Vasilis Syrgkanis, and Êva Tardos. Learning and efficiency in games with dynamic population. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 120-129, 2016.
[59] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against learners in Bayesian games. In Conference on Learning Theory, COLT, pages 5221-5252, 2022.
[60] Denis Nekipelov, Vasilis Syrgkanis, and Éva Tardos. Econometrics for learning agents. In ACM Conference on Economics and Computation, EC, pages 1-18, 2015.
[61] Gali Noti and Vasilis Syrgkanis. Bid prediction in repeated auctions with learning. In ACM Web Conference, WebConf, pages 3953 006439944222 2021.
[62] Maneesha Papireddygari and Bo Waggoner. Contracts with information acquisition, via scoring rules. In ACM Conference on Economics and Computation, EC, pages 703-704, 2022.
[63] Maria Alejandra Ramirez, Yoav Kolumbus, Rosemarie Nagel. David Wolpert, and Jürgen Jost. Game manipulators the strategic implications binding contracts. arXiv preprint arXiv:2311.10588 2023.
[64] Yuliy Sannikov. A continuous-ting time version of the principal-agent problem. The Review of Economic Studies, 75(3):957 0944, 2008
[65] Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning. 12(1-2):1-286 2019.
[66] Emmanouil- and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. Advances in Neural Information Processing Systems, 33:1380-1333 1191, 2020.
ciamaanoull-Vaiiliioss Vasileios Vlatakis-Gkaragkonnn Lampros Flokas, Thanasis Lianeas, Panayotis Mertikopoulos,
[67] Ramiro Deo-Campo Vuong, Shaddin Dughmi, Neel Patel. and Aditya Prasad. On supermodular contracts and dense subgraphs. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 109-132, 2024.
[68] Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides, Federico Cacciamani, Stephen Marcus McAleer. Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Steering no-regret learners to optimal equilibria. 2023.
[69] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. In ACM Conference on Economics and Computation, EC, page 1188, 2023.
13

---

Appendix
A Further Related Work
Introduction to the Problem. Consider the following motivating examples: a worker joining a new team, student starting an internship, or junior professor joining a committee. These agents initially face uncertainty about the required effort and what constitutes good performance. They must decide when exert more effort and when to reduce Peer assessments introduce additional uncertainty and noise. Furthermore, the environment is dynamic. with the value of certain outcomes changing over time. Each agent encounters an implicit and evolving system of incentives that they must adapt to through repeated interactions. This pattern is prevalent in many real-life contractual relationships and increasingly relevant Al agents handling complex, open-ended, and computationally intensive tasks. For details to the aforementioned examples, the interested reader can see [41] and references therein. In settings like credit scoring, the evaluation system creates incentives for the agent while remaining opaque to prevent gaming, forcing the agent to act under uncertainty [38].
Simplifying Contracts. Given this complexity, one line of work focuses on identifying settings where simple contracts suffice. Notably, [48] assume constant absolute risk aversion (CARA) utilities and Brownian motion of the output, examining single payment at the end of the contractual relationship based on all outcomes. Another approach involves deliberately vague contracts, leaving agents uncertain about rerformance-bassee an agent's 's private type through online principal-agen agentt interaction and contract menus. [10] study principal-agen problems over MDPs, where a budgeted principal offers additional rewards, and the agent selects the MDP policy selfishly, without learning. Thus, a naturally arising question is:
compensation (e.g., [3, 11, 31). [44] explore how to learn
How should an agent choose their actions in a contractual relationship involving uncertainty and recurrent interactions?
Our algorithmic perspective introduces novel, learning- based approach address the complexity of repeated contracts, leveraging no-regret and general mean-based agents. Below, we discuss why learning methods are natural choices for agents' responses in the context of existing literature.
Optimizing Against No-Regret Learners. From an econometric perspective, agents often respond to repeated strategic interactions in auctions in ways consistent with no-regret learning [60, 61]. Inspired by these findings, [15] explore algorithmic mechanism design, demonstrating that no- regret learning methods natural responses for agents. No-regret learning has been extensively studied in repeated games (e.g..12, 12.5. 5, 12, 16, 35, 46, 54, 58, 68, 39, 40, 63, 66]). auctions and economic interactions (e.g..125, 19, 37, 53, 52]), and Stackelberg security games (e.g.. [9]). For comprehensive overview, see [65]. By assuming agents employ no-regret learning instead of complex strategic reasoning, we propose new approach to repeated contracting.
Optimizing Against Mcan-Baseh Learners. Finding an optimal dynamic strategy against mean- based learner in general games remains an open problem. [27] show an equivalence between this problem and an n-dimensional control problem, where n is the number of actions available to the agent. Non-trivial optimization against mean-based learner has been achieved only in repeated auction settings, where [15] demonstrate that the designer can extract full welfare as revenue. [26, 18] extend this to prior-free auction settings and multiple agents. However, optimal auction strategy, involving alternating between second-pric -pinc- auctions and charging large payments, is impractical and not intended to guide practice [18]. [19] study mechanisms for no-regret agents, incorporating principal learning to avoid common prior assumptions in economic design problems.
for single agent, the
B Proof of Theorem 3.1 (Optimal Dynamic Linear Contract)
Proof overview. We will present series of "rewriting" rules, which will allow us to replace a given dynamic contract π with a simpler, more constrained, dynamic contract T' with utility at least as large as At the conclusion of our sequence of rewriting steps, will see that contract takes the form of a free-fall contract, thus implying that there is an optimal free-fall contract.
We begin not with rewriting rule, but instead general observation about the structure of dynamic linear contracts - namely, that it is impossible for an agent to "skip over" an action. That is, if an agent is playing action at some point, and action at some later point, there must exist segments of
14

---

1.0
Cumulative contract: i
0.6
dr.
01:=3
0.2
0.0
0.7
0.4
0.6
0.8
1.0
Figure 3: An illustration of Lemma B.2. The plot shows the cumulative contract over time for the contract game shown in Figure I, repeated to T steps, where both axes normalized by T. The lemma shows how arbitrary dynamic strategics, the shown in the blue curve, be re-written as piecewise stationary strategies, depicted in the dotted red curve, inducing similar behavior by the agent and same utilities.
non-zero duration where the agent plays each of the intermediate actions between and j. Formally, we can write this as follows.
Lemma B.1. If क = {(at, , a is a dynamic linear contract, then for any k, lat k+1 S 1 (i.e., in any two consecutive segments, the learner's 's action change by at most one).
Proof. Note that a and *+1 must both be best responses the average historical contract a² i.e., a a k+1 E BR(a"). Since BR(a.) is always of the form {i} or {i, it 1). the conclusion follows.
Note that the proof of Lemma B. relies on the "linear topology" of the best-response regions in Figure 2 (i.e., any non-zero boundary between best-response regions connects two consecutive actions of the agent). This property is not true for general contracts or general games; however, we will later see that Lemma B. also holds for the class of p-scaled contracts introduced in Appendix D.
We now proceed to introduce our rewriting rules. The first rewriting rule we present very general (and in fact applies any game): we will show that without loss of generality, no two consecutive segments of a dynamic contract induce the same action for the learner. Intuitively, for any time interval in which a mean-based agent plays single action, we can replace the contracts in this interval with their average and obtain overall a revenue-equivalent dynamic contract. Formally, we can phrase this as follows.
Lemma B.2. Let be any linear dynamic contract. Then there exists a linear dynamic contract nt such that Util(z') 2 Util(TT) and no two consecutive segments of share the same agent action (a # k+l
Proof. Let π ((a* ( ) be any linear dynamic contract. Assume that for some k; a
s+l = a. Then the linear dynamic contract n' formed by replacing the two segments (a 7 a)
and (a++1, 1++1 a) with the single segment ((a">* + (+tik++1)/(t + 7 rk+1), 7 +h+1 pet1,a a) has the property that Util(rt)) Util(T). To see this, observe that the same action is played throughout the entire interval, and the average payout to the agent is the same. Therefore, in fact we have Util(m')= Util(TT.. It only remains to confirm that this is still valid dynamic contract (i.c., that each prescribed action still a best response the corresponding segment).
To see this, observe first that the cumulative contract at the start (respectively, end) of the merged segment in n' the same as the start of segment & (respectively, end segment k 1) in n. Therefore, all segments before and after the merged segment are still correct. To confirm the merged segment, we need only confirm that is best response on the merged segment n' using the fact that it was best response in both segments & and l + in π.
15

---

For this, let an denote the cumulative contract after the first k - 1 segments, a1 denote the cumulative contract after the first k + segments, a' (t) denote the cumulative contract of T' during a time in the merged segment, and (t)) denote the cumulative contract of π during a time /. in segments & or k + 1. Observe first that for every x between og and Q1, there is some such that (<t) = I. Because is best response on the entire segments lo and k + 1, this means that a is a best response to x for all æ between ao and 01, Moreover, observe that a' (t) lies between og and ai for all t. Therefore, a is indeed best response to a' (t) for all f in the merged segment, and the dynamic contract is valid,
By repeatedly applying this merging of segments, we can obtain linear dynamic contract x' satisfying the constraints of the lemma.
Figure 3 illustrates the above lemma graphically. The figure displays the cumulative contract over time for the contract game depicted in Figure 1. The blue curve represents the trajectory of an arbitrary dynamic contract strategy under which the agent's 's best response is to take action 3 until time I/T Rs 0.425, and then take action in the remaining time. The crossing point between the best response regions is marked with red dot. Lemma B.2 demonstrates that we can replace the blue trajectory with the simpler trajectory depicted in red. In this red trajectory, every region between two consecutive values is crossed by single linear segment (i.e., a piccewise-stational trajectory), resulting in the same behavior by the agent and the same revenue.
Our second rewriting rule is specific to linear contracts. It shows that for every linear contract in which the agent is indifferent between two actions, it is beneficial for the principal to shift the contract infinitesimally so that the agent prefers the action with the higher expected reward.
Lemma B.3. Let π = f(a*, , (²,,a)) ) be a dynamic linear contract where during segment is the agent is indifferent between actions i and i (i.e. BR(a==1) n BR(a")
2 {i,i +1), but at = i. we form nO by replacing a with i+ 1, then Util(x') 2 Util(z) (the principal always prefers that the agent plays the action with higher expected reward).
Proof. Since actions in the linear contract setting are sorted by increasing value of expected reward, = we have that Util(TT) Util(z) = F (ur(p", it up(px,i) i)) = 7: (Re+1 R:)(1 - x*) > 0.
Note that the principal can implement the change in the agent's action in Lemma B.3 by simply increasing their payment to the agent by an arbitrarily small amount- - this incentivizes the agent to break ties in favor of the action with larger expected reward (which is the action labeled with larger number). The fact that the principal can implement this change also follows as direct consequence of the
reduction of Theorem 2.4.
By applying the above two rewriting rules (Lemmas B.2 and B.3) along with observation in Lemma B.I, we can establish our third rewriting rule: it is always possible to rewrite a dynamic contract so that the sequence of actions is consecutively decreasing sequence.
Lemma B.4. Let be any dynamic linear contract. Then there exists a dynamic linear contract n' = (aa (aa,r* rk a²)) }]= with Util(x') ((((=)=)" 2 Util(Tt) and where a' aa....,,a* a.. is a decreasing sequence of consecutive actions (i.e., a = al - (A: 1)).
Proof. Apply the two rewriting rules in Lemmas B.2 and B.3 to ग until it satisfies the post-conditions of both lemmas (so, no two consecutive segments incentivize the same action, and any segment on a best-response boundary incentivizes the higher-reward action). Since Lemma B.1 implies that consecutive segments cannot skip over an action, this means that every two consecutive actions under are consecutive: either the agent switches to the next higher action or the next lower action each time step. We therefore just must show that any dynamic contract where the agent increases their action can be rewritten as a decreasing contract with at least same payoff.
Consider the first segment in where the agent switches to larger action, that is, the smallest & such that a A+I = a² + 1. Let a² = j (so a A+1 = j + 1). Note that the agent must be indifferent between actions j and j + at the end of the jth segment (i.e., {j.j + 1} C BR(a*)).
There are two cases: either segments and + 1 are the first two segments of the dynamic contract (i.c., k- = 1), there exists (k- 1)st segment. In the first case, the agent is indifferent between
16

---

4,5
4,5
3,,4
3,4
2,3
2
0 1,2
1,2
(a) Base policy æ. In this example, the kth seg- ment is the first segment where the action in- creases immediately after the segment (ag = 2, Ah-1 a4 + 1 3).
(b) Since Ok-1 = 12411 v. the kth lies along best response boundary d22,3, and its existence violates Lemma B.3 (we can rewrite it as a segment with 3, and then further collapse these segments Lemma B.2).
Figure 4: Illustrations for the proof Lemma B.4.
actions j and +11 for the entire first segment (from time 0 to T!), but plays action j. This contradicts the fact that cannot be reduced further by Lemma B.3.
In the second case, the (k: 1)st segment must incentivize action j + 1 for the leamer (since the sequence of actions is decreasing up until segment k). But this means that the agent must be indifferent between actions j and + also after the (k: - 1)st segment, and thus for the entirety of the kth segment (fj.J j + 1] S (R(a* k-1)). Since the agent plays j during the kth segment, this also contradicts the fact that cannot be reduced further Lemma B.3 (see Figure 4 for example of this reduction).
We are now almost done Lemma B.4 shows can rewrite any dynamic contract so that the agent descends through their action space. We now need only show that the principal should abruptly switch offering the zero contract after the first segment (instead of slowing the rate of descent through these regions by offering a positive contract). We do this in our final rewriting lemma.
A,5
a
4,5
a BR
a 3,4
CB
a
2.3
2,3
1,2
1,2
(a) Base policy π. The kth segment is the first non- free-fall segment; we decompose it into segment aBR 03,4 and fall-fall segment with
(b) The segment with a = aBn can be rewritten via Lemma B.3 to lie in region 4, where it can then be further combined with earlier segments Lemma B.2. This moves the first con-free-fal action earlier in æ.
Figure 5: Illustrations for the proof of Lemma B.5.
Lemma B.5. Let n a dynamic linear contract where the agent plays a decreasing sequence of actions. Then there exists free-fall linear contract a' with Util(z') > Util(TT).
17

---

Proof. Let x = f(aa, r", """,,,""") )²)) (with at decreasing), and consider the last non-free-fall segment
(a", -hi ",,,,,,,,) d.f).io i.e., k is the maximal k for which at * O. Assume that & > 1 (if not, then π is already a free-fall contract).
Let OBR = 41 be the indifference contract for the best-response boundary separating the current action from the previously incentivized action. Consider replacing this segment with the two consecutive segments (a:RR (a* //BR)) a²), (0, (1 - a² / )²)). In doing so we essentially doing the inverse of the first rewriting rule in Lemma B.2 -replaccng a single segment with two segments that average to the original segment - and because of this, the resulting dynamic contract is valid and has the same utility as our original contract (the construction also guarantees both segments stay within this region). But now we have a segment (aBR. (a* (BBR)"", a²) that lies along the best-response boundary aBR, so by Lemma B.3 we can replace it with the segment (oBn: (a /OBB)T a + 1) and strictly increase the utility of our dynamic contract (see Figure 5).
We can then merge this segment with the previous segment in (which also incentivizes action a + 1) to obtain a new dynamic contract with strictly greater utility than π and whose first non-free-fall action occurs strictly earlier. Repeating this process, we obtain a free-fall contract n' with at least the same utility
We can now prove the main theorem of this section.
Proof of Theorem 3.1. From Lemmas B.4 and B.5 the first part of this theorem (that there exists a free-fall linear contract nt with Util(z') (x)) immediately follows.
To show that we can efficiently compute this free-fall contract, note that the optimal free-fall linear contract might well start with segment of the form (0;-1,á, 7, for some indifference contract 14- (if it does not start by offering some indifference contract, we can apply the rewriting rule of Lemma B.2 to merge this segment with the following segment, which would incentivize the same action).
It is also true that the optimal free-fall linear contract might as well end at an indifference contract: that is, π. aj-1,j for some j. To see this, consider free-fall linear contract ı that does not end on an indifference contract. ends with segment of the form (0, T0, a) for some agent action a. Consider the contract (T)) formed by replacing the duration of the last segment with т; this operation
valid for all in some interval [0. Fmax]] Note that (TT(())() is a convex function of T (it is of the form ( K- + up (0, ( + T)) so it is maximized when T equals one of the endpoints of this interval. But at both endpoints, k lies on a best-response boundary (for т = 0, 0g,a+1. for Tmax ag-1,a).
Since our optimal contract is completely characterized by its start and end points, it can be computed in polynomial time in n by testing all the pairs of indifference points {a;-1,i, Qý-1.; } with j S as candidates for the start and end points of the optimal initial contract (this pair of indifference points also uniquely specifies the fraction of time that must be spent in free-fall). Note that in the case where in the optimal free-fall contract i = j. the optimal contract is the best static contract.
In Appendix (see Theorem D.1), we generalize Theorem 3.1, showing that free-fall contracts are optimal for a much broader family of dynamic contracts with "single-dimensionnl scaling," where the principal is using an arbitrary non-linear contract and dynamically rescales it during the interaction with the agent.
Our proof of Theorem D. is parallel the proof of Theorem 3.1 in the sense that we demonstrate wwwdediinnannssseeeeeeei
how to gradually transform a general while increasing utility for the principal. The main difficulty applying the proof of Theorem 3.1 directly is that the rewriting rule in Lemma B.3 no longer holds for general contracts with single-dimensional scaling, it is not the case that segments along a best-response boundary should always incentivize the higher action for the agent. In the proof of Theorem D. we forego the use of this rewriting rule and instead using the weaker condition that there cannot be two consecutive segments along a best-response boundary.
contract into free-fall contract,
18

---

C Proof of Theorem 3.2 (Win-Win)
Proof. Consider the following contract game. 10 There are n 2 actions, with expected reward R. = v² for some e > 0. Concretely, we let e = 2. The cost of the action are specified recursively by C1 = 0 and C; = C:-1 + R 2 for > 1, yielding G>1 = -i=2(2k-1 - }) The resulting indifference contracts are thus a; = 1 2 for 1 < <i= S n. In this game, the principal has the same utility (of one unit) for all the indifference contracts. The agent's utility under the contract as, as the
reader can verify, is given by 2 3 -i - 2) [1 + i). Notably, this utility is higher for the higher actions. The welfare of action is thus w; = (3 +1). Next, we slightl alter this game by increasing the payoff of action 2 by small amount > 0 such that the optimal static contract is now ag., which yields a utility of 1 + O(e) for the principal, and the agent is still indifferent under this contract between action 2 and the null action. In the following analysis, are mainly interested in large (but finite) n. Notice that the optimal static contract is extremely inefficient for large n, getting an arbitrarily low (independent of n) fraction of the optimal welfare.
Now consider an optimal dynamic strategy; by Theorem 3.1, there is an optimal strategy of a free-fall form. We will construct a frre-ffal contract p that starts at On, so action is played initially, where the duration XI' of that stage is chosen such that the final action at time T is action log(n)) 2"
Specifically, we require λoo + (1 X) 0 o{3 [og(n)] and so À = 2- JT)). We show that this free-fall strategy bounds the utilities of both players from below.
Claim C.I. In an optimal free-fall contract, the utilities for both players are least those obtained in the contract described above.
For ease of presentation, the proof for this claim is deferred the following subsection. It consists of three parts: first, we show that an optimal free-fall contract must start at O'n- This is done directly by way of contradiction. Then, the proof shows that the last action that is played by the agent in an optimal free-fall contract must be higher than 1 log n. The intuition for this part of the proof is that as the principal continues free fall through lower and lower actions, the marginal gain from each action (which is the expected reward of that action because we are free falling) continues to diminish. At some point, the marginal gain outweighed by the current average principal utility, which we show should occur at action Ologg n)) (since we know the principal can get an average utility of ((n) and the expected reward of action is 2¹). Lastly, we compare the utilities of both players in a free-fall strategy that begins action n and ends at action [ log n. to those of the optimal free-fall strategy and observe that the utilities in the former case bound the respective utilities in the latter case from below. The principal's utility is clearly bounded from below by her utility in our strategy due to optimality. For the agent, the total utility is determined by the stopping point. Since the agent's ' utility at a, increasing with in our game, we conclude that the agent's utility in an optimal contract is at least? 2 log n.
2
Now let us calculate the average utilities for the players under our dynamic strategy, averaged over the whole sequence of play. The agent's average utility at the last step is the same as the utility that would have been obtained under the average contract at that time, which is 41 + log(n)) To calculate the utility for the principal, we define I, to be the time when the agent switches from action i action i 1. We know that the transition from action n n 1 happens at time L,, = XT, and until that time the principal gains a utility of one per time unit. After that time, the average contract at time t is the weighted average until of the contract on with weight XI and zero contract with weight t - XT' Therefore, the transition times from each action i are given by t, = XI XT After time XT, the principal pays zero and extracts the full welfare from the agents actions, and so the overall utility for the principal is XT i== log(n)] (f--1 R,)
Claim C.2. The utility for the principal in the free-fall contract (an, X) is O(n).
II this example we shift the rewards with an additive constant such that the reward for the principal when the agent takes the null action equals some constant instead of zero. This simplifies the following analysis and is without loss of generality.
19

---

Proof. The utility from region i is XI + Σ log(n))
(t:-1 (0)))-t)RA- R4- The time intervals are
1
XT
(1-1-1)) aT
0
(2 - 2) -)
The utility for the principal from region i > 3 log(n)) and large n is thus:
XT'a,,
2(2 - 2) -1 0())
Summing over n 2 (n) such terms yields a utility of (()).
The above arguments hold similarly also for perturbed versions of this game. For example, shifting the rewards by arbitrary and independent values the range [-1, 1], as well as re-scaling the reward parameter e, yielding positive measure in the parameter space.
C.1 Proof of Claim C.I
Proof. We execute this proof in two parts. In the first part of the proof, will show that any optimal dynamic (free fall) contract must begin at Og In the second part of the proof, we show that an optimal dynamic (free fall) contract that begins at an must end at a logn] or higher, if n is sufficiently large. This is enough to imply the claim because if the optimal free fall contract stops at higher action than [ log n then the principal has higher utility due to optimality and the agent has higher utility since their utility is increasing in actions.
We now prove that any optimal dynamic contract must begin On. For the sake of contradiction, suppose that it instead begins at or for some action i E [1, n - 1]. In particular, it begins with the segment (p' R, - a² = 2) for some E [L, 1). To achieve a contradiction, we will show that this dynamic contract is not optimal by producing a better dynamic contract.
In particular, let consider replacing this first segment with the following two segments: (04+1R,2* - -;ا - + 1), (0, 1 ac+1 2) (and re-indexing all subsequent segments appropriately). We claim that this will achieve strictly greater principal utility, while leaving the total time unaffected. We first show how we solved for the appropriate time-split (I,, y).
+ y = 71
(zz, y) is time split)
30 -'
(At time 7', the cumulative linear contract is still o;))
7²
x 04+1
y
a++1
By construction, our choice of x and y keeps the total time invariant, so it remains to prove that this results in strictly more principal utility. Since all subsequent segments the same and generate the same amount of principal utility, we only need to compare the principal utility of these three segments.
The (cumulative) principal utility of the original segment (a, is just 7 since the contract problem is designed so that all indifference contracts a; result in one unit of utility to the principal. The exception is action one, which was adjusted to have 1 + O(e) principal utility and therefore has cumulative principal utility 7! (1 + Oe)))
Next, we consider the cumulative principal utility of our two new segments (a:+1 xr, i + 1) and (0, y, i). The first segment has (cumulative) principal utility equal to just for the same reason as above (but now + cannot be the first action). The second segment has (cumulative) principal utility equal to y( R2+1) where R2+1 is the expected reward from action i + 1, due to the fact that this segment offers the zero contract. Together, these two segments generate (cumulative) principal utility equal to the following.
I x- ( = (I + y) + v(14+1 - 1)
= + v(2tt1 - 1)
20

---

However, we can see from our choice of y that 0 and (2 -) > 0 since i > 1. Hence this strictly beats the cumulative principal utility of the original segment as long as is sufficiently small. This completes our contradiction, since the original dynamic contract was assumed to be optimal but we found a strictly better one. Hence the optimal dynamic contract must free fall from On (which there is no higher action to start from instead), completing the first part of the proof.
We now use this fact to prove that the optimal dynamic (free fall) contract must end at a logn] or higher, if n is sufficiently larger. The proof plan is to consider the effect of free falling through an additional action, and determining when that might improve the free fall contract. observe that the objective function of the continuous setting, Util(z), is invariant when we equally scale all times ,K As a result, we can assume without loss of generality that the first segment of free-fall (p' a, R, T a' n) uses 7' = We can also assume without loss of generality that + 1)) begin and end region boundaries, which is
first step, we
the other segments {(r* 0, rh, at enough to work out their durations 7 based when the average linear contract reaches particular indifference point.
*/
On
On
1-2
1 1- 2
- 2-n+k-I
2-
On-k+1
k+t
2-itk-1 2-1+k-2
=
[1 [1-2
(1 - 2- 11) [](1
2 2-n+k-2)
2 2-n+k-2
[1 - 2
2- (1 2
Hence segment & E [2, K] contributes the following (cumulative) principal utility.
2 2-
Mur(p", k2n- h+1 2n-++1, 2-
(1-2 2 - (1 2 2-
1 = [1 -2- 2- -11--1111122111 2 2
Let TH be the trajectory that uses K segments. We can compute its objective value to be the following.
1+ 1 2- 1 Ek (1----t11(112--000000 1
Util(Tx)=
(1-2 2-111/(11= -2 2-n x+
K
1/(1-2 =(1-2-n*K-l)
+
2
(1 2 1)(1 2-n+k-2)
k=
21

---

We can take the difference of two such expressions to decide whether TK+1 is better than Tg. For
n 2 logn n < S n 1:
K+1
Util(TR+1) Util(Tx)) (1- - )
1/(1-2-") +
2 n 1(1 2-ntk-2) )
2 (1 -  
K
(1 - 2 2-ntk-1)
1/(1 1/(1-2 -- + 2 k=? 2
(1 2 n 2 () 2)
(1- 1-22 -nntu
x**] 1
1
1/(1 1/(1-2 m/11-- n- + 1
(1 11-2-n-h-1j(- 1 Seitiea
1
(1 2 n- (x-- (1 2 2-n+ (n-
nー
1 log
- 2 2n- log
1
2
k=2
[ 12(n
11
log
2 (1/2)(3/4) 2
2
Since the positive term has magnitude O(1) and the negative term has magnitude (R)), this bound will always be negative when n is sufficiently large. Hence it is strictly not worth it to free fall below a logn]. as desired. This completes the proof.
D General Contracts with Single-Dimensien
Scaling
Here we consider general contracts, and in Theorem D.1 generalize the result of Theorem 3.1 to families of mie-immnsional (yet non- non-linear) dynamic contracts for which free-fall contracts are optimal.
Given any contract p. the set of p-scaled contracts are the one-dimensional family of contracts of the form op for some a 0. We will consider principal that is restricted only play p-scaled contracts. In the continuous-time time formulation of Section 2.2, this means that each contract p² must be p-scaled. We will let p² a'p, and we will often abuse notation and write a as shorthand for this contract (e.g., we will specify segments of the trajectory π in the form (a*, "a,aa))a)))) a))). Recall that a free-fall contract denotes such a dynamic contract for the principal where a = for all k > 1.
As with linear contracts, note that increases from 0, the contract op incentivizes the agent to play an action in (ax (which is unique except for most n. "breakpoint" values of a, where the agent indifferent between two actions). This induces an ordering over the actions; will relabel the actions so that actions (the null action), 2, 3, ... are incentivized for increasing values of a. Formally, the agent has actions, we have "breakkoints" 0 00,1 < Q1, < 02,3 < ... < 0n-1,n where action belongs to (a) iff a E [a;-1,i, 01,++1] (with an,++1 = =c).
Our main result in this section is the following theorem, by which free-fall p-scaled contracts are optimal p p-saleed dynamic contracts.
Theorem D.I. Let л be any p-scaled dynamic contract. Then there exists a free-fall p-scaled contract n' where Util(r') Z Util(IT).
To prove Theorem D.I, we will establish a sequence of lemmas constraining the potential geometry of an optimal p-scaled dynamic contract. Note that since linear contracts are a specific case of p-scaled contracts, this also provides an alternate proof of Theorem 3.1.
We begin our proof with the observation that, similar to linear contracts, p-scaled contracts cannot "skip over" actions for the agent (c.f. Lemma B.I, which has essentially identical proof).
Lemma D.2. If (aa rh, )}a))}}}))))}} is p-scaled dynamic contract, then Vk. Ja* ++1 < 1.
22

---

45
25
3,4
225
25
0,2
1
(a) Base policy л. In this exam- ple the kth and (l: + 1]st seg- ments both lie along the dg in- difference boundary, but the segments incentivize different ac- tions (a* = 4, a #+1 = 3).
(b) Policy m. formed by replacing the first l segments of ı with an enlarged version of the kth seg- ment.
(c) Policy R2 formed by replacing the first & segments of æ with an enlarged version of the first & segments.
Figure 6: Figures for the proof of Lemma D.3.
Proof. Note that a* and *+1 both must be best-responses to the average historical contract p after segment which is p-scaled contract with parameter a = > a nK /E 7h In other words, a and a k+1 belong to (a* Since (Rp(a) is always of the form {i} or {ú,i 1) the conclusion follows.
Now, recall that in Lemma B.2 we show that (for general contract problems) we can restrict our attention trajectories where two consecutive segments have the same agent best response (i.e., a o a ++1 for any k). The following lemma proves a strengthening of this fact specific to p-scaled contracts.
Lemma D.3. Let ι be any p-scaled dynamic contract. Then there exists p-scaled dynamic contract n' = {(a0, -h, , with the property that for all k; a + ++1 and at o k+2 and that Util( > Util(TT).
Proof. The fact that can rewrite æ into equivalent contract where at + *+1 follows from proof Lemma B.2. Therefore, assume without loss generality that æ already has this form. We will show how to rewrite it into new dynamic contract x' with the additional property that a * #+2
We will induct on the number of segments in the path (it is obviously true when there is only K segment). Assume that for some k. has the property that a² k+2 o a++ This implies that (a=)) BRp (1+
{a a a+1).. Since there is unique value of a for which BRp f a - (namely, one of the breakpoints 04,4+)), this can only happen if a² = ++1 which in turn means that k+1 पK g Pictorially, this is because if a dynamic contract spends only one segment in best-response region, this segment must lie along the boundary of the best-response region (see Figure 6).
Now, consider the following two modifications of
1. In II, we replace the first
segments of with scaled up version of the (A: + 1)st segment. That is, remove the first & + segments of π and replace them with (t1+1 T ( , To see that this is a valid contract, note that since a k+1 = ++1 a A+1 incentivizes action k-1 so the first segment of this contract valid. Moreover, after T time units have elapsed, both and resume the same sequence of segments from the same state 1+1
2. In n2, we replace the first k+ segments of π with a scaled up version of the first & segments. That is, remove the segment 1o-+1,,ki0 , k+1), and scale up 7k (for each 1 < k' < k) to TK (Tx+1/Tk) Again, this is valid dynamic contract because scaling up a (prefix a) dynamic contract results in a valid dynamic contract, and π and #2 both resume the remainder of segments at the same time and from the same state k+1
23

---

Oas
023
4/
9,2
(a) Base policy и with consecu- tively increasing actions.
(b) Policy TK formed by setting K to the minimum required to remain in the same best-response region (in this case, az)).
(c) Policy n' formed by scaling the first K segments of (i.c., all but the last segment).
Figure 7: Figures for the proof of Lemma D.4.
Finally, note that (Ti is a convex combination of Util(z1) and Util( - specifically. Util( (r*+1m mi T==2)//kt2 and is less than equal to of them. But both m and л2 have strictly fewer segments than n, so by applying the inductive hypothesis, we are finished.
As a consequence of Lemmas D.2 and D.3, we can restrict ourselves to dynamic contracts whose sequences of actions are either consecutively increasing (a*+11 = a + 1) or consecutively decreasing (a (a--1 = a - 1). We show that we can ignore the first case such contracts can never be better than static contracts.
Lemma D.4. Let = ((a*, r²,aa)) be p-scaled dynamic contract where the a² are consecutively increasing. Then there exists a static p-scaled contract x' (i.e., a single segment dynamic contract of the form (a', 1, a,)))) where Util(x') Util(T).
Proof. As in the proof of Lemma D.3, we will again induct on the number of segments of n. If has one segment, we are done.
with K segments, whose last segment is (a 7 a;-1, is the smallest value of a for which ap incentivizes action i. Note that if a > -1, we can improve the utility of the principal by decreasing K to 0g*-1,a* (this pays strietly less to the agent but still incentivizes the same action a )²), We'll therefore assume the last segment is of the form (a, -,ak, , -* a a²) note that this segment by itself valid static p-scaled contract, as Oa - incentivizes action K Call this contract тK-
Now consider
a²)). Recall that for any i,
Let T' be the dynamic contract formed by the first K - segments of π (see Figure 7 for examples of TK and x'). But now, Util( a convex combination of Util(=') and Util(m maximum of these two quantities. If this maximum is Util(= K) ), we are done (π K is a static contract); is Util( we are also done by the inductive hypothesis (x' has K segments).
is most the
Finally, show that in the case where the sequence of actions consecutively decreasing, such contract is no better than some free-fall contract.
Lemma D.5. Let ग ((at, Th at)} be p-scaled dynamic contract where the a² are consecutively decreasing. Then there exists a free-fall p-scaled contract x' where Util(T') 2 Util(T).
Proof. Assume that is not free-fall contract. We will show we can rewrite in way so that either the first agent action a² strictly decreases or the first non-free-fall occurs strictly later. Since the number of segments implies the theorem statement.
is bounded (by n, since the actions are consecutively decreasing). this
Let (a* Th a be the first segment in with k 2 2 where at 0 (so, the dynamic contract is not free-falling here). Note that since this segment ends on the boundary between the best-response regions for a and *+1 a 1, a² 00
The main observation of this proof that we can rewrite this segment as a combination of free-fall segment (with 0) and segment along the boundary of these two best-response regions (with

---

%
%
2/3
(a) Base policy и with consecu- tively decreasing actions. The kth segment is the first non-frec-fall segment: form æ' (the dashed trajectory) by decomposing this segment into a free-fall segment followed by boundary segment.
(b) Policy mi formed by replac- ing the first k segments of æ by a scaled up version of the boundary dashed segment.
(c) Policy Te formed by replac- ing the first & segments of ı by scaled up version of the prefix of up (but including) the boundary dashed segment.
Figure 8: Figures for the proof of Lemma D.S.
aa))). Specifically, form new dynamic contract n' by replacing (a a²) in with the two consecutive segments (0, Ar ,a²) and (0at-1,at, (1 A)r a²), where À is chosen so that (1 A)a = a². Note that by doing this n' now has K + segments, where segments & and + 1 are this new free-fall and boundary segment respectively. Note that we will let quantities like 7², Th and at still refer to the relevant quantities for π, not #'
This allows us to proceed via a similar technique as Lemma D.3. Consider the following two modifications of x (see Figure 8 for examples):
1. In Ti, replace the first k + 1 segments of nt with scaled-up version of the boundary segment of the form (a"; T ))
2. In #2, we replace the first k: + segments of x with a scaled up version of the first segments (the first k segments of and the free-fall segment, but not the boundary segment). Specifically, let C' = =T===<<(T> (T + \T*). Then the first k - segments of π2 are of the form (at Cr*", , and the kth segment of Ty is of the form (0, CAr a²))
As in the proof of Lemma D.3, we can check that both क and म2 valid dynamic contracts: in particular, after T units of time, they are both in the state a so the remaining suffix of i is a valid extension for both contracts.
Again, Util(TT) can be written as convex combination of Util(TT) and Util( specifically,
Util( (1 U)i"mt))( + (Tk-1 Ar Ar*)Uti)(TT)
T
But m starts at a later action than π (since further step than x (since a² = a This completes the proof.
a² = 0² (k - 1)), and na is free-fall contract for one
a k- 0, and the kth segment in 22 also has a = 0).
We can now conclude the proof of Theorem D.
Proof of Theorem D.I. Because of Lemmas D.2 and D.3, we can assume without loss generality that the actions a in æ are either consecutively increasing or decreasing. The conclusion now immediately follows from Lemmas D.4 and D.5.
E Proof of Thorem 4.2 (Unknown Time Horizon)
Proof. Due Theorem H.3, suffices to show that there exists some y such that U (1 E..
This lets focus on the contiuous-tiime setting.
25

---

slope is Rs
0
Q22
03 Q4
Figure 9: We use a "raw" potential function (aa) which maps time-averaged linear contracts a to (raw)
potentials.
The high-level plan from here is to focus particular continuous trajectory π k= {(pt rh a² apply a potential argument to We will then show our analysis extends to distributions D for free. We will define potential function (aa)) that maps time-averaged linear contracts a to potentials in Rzo. This potential is based only on the principal-agen problem (c, F,r). There are some peculiarities about our potential argument, relating the passage of time. Consider a principal managing to produce a time-averaged linear contract of a after units of time, and compare that with principal that has managed arrive time-averaged linear contract of a after 2/ units of time instead, i.e. twice the time. In terms of absolute (not time-averaged) units of profit we can extract from this point, it is twice good be in the latter situation. With this in mind, our proof will carefully distinguish between the raw potential (a) and the time-weighted potential ((a) tt If principal maintains a steady time-averaged linear contract, then the raw potential will remain constant while the time-weighted potential will grow.
The purpose of the tmme-weighted potential is model the ability of a principal to extract additional profit by gradually lowering time-averaged linear contract. will be used to demonstrate that this extra profit produced by using up finite resource, which will imply the desired theorem result.
We now give our raw potential function vb((x). We begin by writing down the linear contract breakpoints of (c, F,r); without loss of generality" they are 0 < 02 < 0r <... < Onn, where the linear contract ag leaves the agent indifferent between actions - and i. For notational convenience, we also define an di A as the minimum linear contract to incentivize the first action. We also denote the expected reward of action i with Rt With this notation in place, our raw potential function <i : [0, as,] > R the following piecewise-lineat function. Note that we can assume without loss of generality that the average linear contract never exceeds axg because capping it to this quantity only improves principal utility at all moments in time.
(00+1 R4 + (a - Rz) if a E (1w,02+)) (0++1 R: Ra
v(a)=
if a = On.
The potential above is depicted in Figure 9 and can be seen as the product of the following thought experiment: what if the principal was allowed to offer unbounded payments (in particular, payments can be negative and can exceed the payment bound Py? In our continuous-time setting, this gives the principal the ability to produce segments of play (v* .* a²) which have near-inttantaneous times 7 + 0 while using large- magnitude cumulative contracts p²** to move between the boundaries between actions. If these near-instantancous actions are used at time t, then the time-weighted potential (b(o:) captures the necessary payments to alter the time-averaged linear contract. One interesting aside about this thought experiment is that the necessary payment to near-instantaneously move up from a; to the next 0;41, namely (4((4+1) (baa))) f, is equal to the payout received for near-instantaneously using a negative contract to move down from a4+1 to Qq.
Implicitly, this step prunes away all actions which cannot be incentivized by linear contract.
26

---

Potential function in hand, we return to the original problem where payments are bounded and nonnegative. Let consider the h segment of play (p* a R. T² a²) and relate the total profit generated during this segment of play with the change in potential.
For notational convenience define shorthand for the cumulative linear contract offered.
A
a
We will also use u/. denote the (time-weighted) principal utility for segment & and u to denote the corresponding amount of principal utility that the optimal static contract obtains over r time. Using this notation, we can compute an upper bound on how much additional principal utility this segment manages to achieve over the optimal static contract.
u [1 a²) Rat 7k
u.. max(1 0, Ru 7
2 [11 aa²) R 7/ (u.) - w & [ k Raat/ 7/
At the same time, this contract has shifted the time- linear contract and hence altered the liiehwegghte potential.
(A* (T) T (A //b-1 T
a
(0c 04 1 Ri-1 + (A* /Tx oaw) Rot Th
(1; 0 R4-1 (Ah-1 /Tp-// Oaar) Pea gh-1
t
(as ai-1) (Ar T Thaae)) Rit
a; a--1) + (At-1- -Th 7k-1 aaa) 1
Rat
(aa a;-1a + [(a - (kor)))) Rayt)
Interestingly, the expression for time- weighted potential has term that perfectly cancels with our bound for how much additional principal utility this segment produces over the optimal static contract.
(u (A*/TT) T (A T4-1
Σ (a:
a
(A- + -T----1)aa dt
Th- v
T
The right-hand side expression above is just the integral of the current potential as this segment advances the time from T to T Conveniently, this upper bound still works out to the same amount even if we subdivide segment (p*, -. a²*) into two sub-segments (p of,2z a²) (p" a.) such that x, *0] and this bound to get overall bound for any time [O,T], just by splitting the last
و (and re-index the other segments appropriately). This means
27

---

segment appropriately. To formalize this, we introduce some more parenthetical superseript notation denote the corresponding objects when considering time from zero to In particular, u. denotes the optimal static contract's principal utility for t units of time, A denotes the cumulative linear contract for units time.
(up) 1 (T) + ( I' 1
A T
dt
Recall our notation where R, denotes the optimal static contract's principal utility. Fort E [T, we know that the excess principal utility needs to be at least e eR,t, which implies the following.
sR.t (At))) S
A
dt
+ (A - -RR + [
A(T) T
dt
With this bound in mind, we view every trajectory ı that manages to successfully beat the optimal static contract by (1 + E) in terms of how much raw potential it has as function of time. Note that this bound controls the current (minus a constant). As result, if we just consider trajectories л that obey this bound, the worst case for us would be function that satisfies with equality everywhere since greedily picking the maximum value for the function early on allow for higher values later on (greedy stays ahead). We now solve for this function f(t which simultaneously maximizes raw potential everywhere.
potential based the average raw potential up this point
ER. f(t)== = 1 J(T)dT
cR. f(t) + f()) f(t) f'(1) -eRu/t
At time T, we know the raw potential can be at most ((a.). We want to choose y and hence so that S(T) is negative in order to create contradiction. Because f yields the maximum possible function value attainable at time T, this means that our actual raw potential will also be negative at T. We now solve for the largest value of y that does not actually create a contradiction.
f(T) f(T) = v(an)
f ('())dt = (b(an)
eR. [In [In]]] (b(an))
(T (aa)
ER.
7 ((an))/(fHt
Hence it suffices to pick a > edaa.)((eR.) This demonstrates that it is impossible for a deterministic trajectory to beat the optimal static contract by (1 + =) multiplicative factor.
What about randomized dynamic contracts DD? We can just take the appropriate convex combination of our bounds according to drawing π ~ D. In particular, this yields:
EAND (14)0
- BAND [ (4 (10))]/ i5 J. BAND
vb
((T))
dT
We can then re-execute the remainder of the proof the same way, replacing the deterministic additional principal utility with expected additional principal utility and deterministic raw potential with expected raw potential. The expected potential function is still bounded everywhere by the same function fT) and we reach the same conclusions about y. This completes the proof.
D
28

---

Remark. Due to Yao's 's minimax principle, Theorem 4.2 implies that there exists an adversarial distribution over times in [[ such that for any randomized principal strategy. the ratio between expected principal ulility and the principal utility of the optimal static contract for that duration of time is strictly less than (1 (1+)). 8).
I In order to apply Yao's 's minimax principle, we need the set of relevant principal strategies and the set of relevant adversary strategies to be finite. We already do this in our proof of Theorem H.3: the latter can just be an e-net since principal utility is Lipschitz with Lipschitz constant depending on the contract problem, and after that the former then follows from Carathodory's Theorem by treating each deterministic trajectory as a vector with one coordinate for every point in our E-net.
F Proof of Theorem 4.3 (Unknown Time Horizon -Converse)
Proof. We prove this by proving the contrapositive. Suppose for any fixed time T there is a dynamic contract that can achieve an expected utility of (1 + c)u,T for some c > 0. By Theorem 3.1, we can assume without loss of generality that this is free-fall linear contract. We will show that for any y we will construct a dynamic contract such that for all T E R and all E [-. T. we can achieve an expected utility of (1 + f(c, u. t where f(c, 7) 2 52 mmi ((5) (())o (+))),
As a first step, we will show that if there is a free-fall linear contract that beats the optimal static contract, then there is a free-fall linear contract that beats the optimal static contract but also either (1) ends at or above the optimal static contract or (2) begins at the optimal static contract. Afterwards, we plan analyze case (1) and (2) separately.
If our free-fall linear contract does not already satisfy case (1) or (2), then it must do one of the following: (a) begin at a higher breakpoint than the optimal static contract and end at lower breakpoint than the optimal static contract or (b) being and end at lower breakpoints than the optimal static contract. We now analyze these two cases. In the process, will lose constant factor which is folded into our Ω notation.
Case A: Dynamic contracts beginning above or and ending below o., We write our free- fall linear contract in the usual form क = [(px, zk )))))) By virtue of being in this case, we know there is some index S i < K such that the average linear contract after segments, p'. is exactly o... We "cut" the trajectory π at this point to produce two new trajectories n' and x". Specifically, n' = ((*", ,", a Ja=1 and n" = {(a.. T a')' }} o {pp,, f ,², ,,, a² 1 Jk=it1 where o denotes concatenation. In other words, we construct x' by ending at this point and we construct x" by taking the optimal static contract to this point and continuing as normal. Observe that the combined performance of n' and n" is equal to the combined performance of and just playing the single segment {(a., T T"); (1+e)u, T +u, T This results in combined time-averaged performance of
(1 (1+6)uTT + +u, u. TK +Ti
TK T +T + (1) TK
T
2 (1+c/2)u,
since T 2 T'. Since T' and x" have this combined average, one of them must have at least this average (and we only lost a factor 1/2 on our which is indeed constant. Since n' matches case (1) and n matches case (2), this completes the analysis of case (a).
Case B: Dynamic contracts beginning and ending below O.., We take the obvious approach and choose begin o, instead. Specifically, we replace the first segment with a sequence of segments that begins at o, and then undergoes the appropriate number of free-fall segments to arrive at the same endpoint as before (same total time and average linear contract). We argue that each new segment has at least as much principal utility per unit time as the original segment. Since the total time is the same, this is a direct improvement over the original dynamic contract, both in terms of total principal utility and time-averaged principal utility. The argument that each new segment does at least as well per unit time similar to before. The first new segment just hovers the optimal static contract, which by definition is better than any other static contract (which our original segment must be). The remaining new segments are freefall segments, and achieve principal utility per unit time equal to the expected revenue of the actions they fall through. We observe that we fall through segments in order of decreasing expected utility, meaning all of these segments have higher expected utility than the action originally began with, and expected revenue is at least the principal utility
29

---

of the static contract that achieves a particular action. We finish this case by noting that we did not diminish at all, which trivially a constant factor.
This completes our analysis of cases (a) and (b). In all cases, we managed to reduce to either case (1) or (2), which we consider.
Case I: Dynamic contracts ending at or above ag. First, we consider the case where for any fixed T there is a dynamic contract (T)) ((a2, ,t,,,,,,,,,___ ,a"),..,,((c (a* , ,a*)) which ends at or above the optimal static action: a contract which starts with x (T), free falls to the optimal static contract, and then plays the optimal static contract for the remaining time period. We again observe (as we did for case (b)) that free
Given any " and time period [T, y - consider the dynamic
falling through actions that are at least the a, results in at least u. principal profit per unit time.
Hence the total revenue for any time E [T. T) for the principal (1 + ()) u. + T U4 which is at least (1 + R.I.
Case 2: Dynamic contracts starting in a.. By Theorem 3.1, know any dynamic con- tract can be transformed into a free-fall dynamic contract with no loss in revenue. There- fore, we assume that for any fixed time horizon T, there dynamic contract form (T) (a,,T!, T .a),, (0, aa),..., (0, rh aa)) which achieves total revenue of (1 c) Since this is free-fall contract, the optimal revenue from this contract can be characterized as R.. + Σx= R', which is at least (1 + +),, > (1 + E1 ... Let be the minimum fraction of time such that for any time T. the dynamic contract I (T) achieves revenue at least (1 + e/ e/,) Since we know that (T) achieves a total revenue of (1 =)u,T and starts out at the optimal static contract, we know that μ //EE.n r' and is a constant bounded away [log( (on((++)])) D) log(n)
from 1. Let S, = [n'T] and let be the first index where Sp is less than T (i.e.,
By construction, S: satisfy two properties:
1. Sp ST STSSSIS Sp ST.
2. If the principal runs dynamic contract ending S,, namely r(;)), then they are guaranteed revenue (1 R. for any t [;)+
We will construct sequence of dynamic contracts x' which have the property that for any E [S., TT] achieves revenue that is at least (1 + (5/4)") R.t. We do this via induction. For the base case, let π² = (T) By construction, we know that for all E [[ the principal will get revenue (/)x/2)u,tt Now suppose we have such dynamic contract n', then we construct n'+ by taking convex combination of n² and the optimal dynamic contract ending at 7 (S:). In particular, let
1 1/2/
(s/4)
+ I+E+ (f/4) " (S.).
1+//2+ (4/4)
For any t E [S,,T) we have that revenue we attain is at least the revenue from the contract
1 + 5/2
1 +/22
Revenue (tt
1 9/2 (5/a)s (1 (f/4)))utz
1 9/2 + (5/4)
e++ /2-4
1+ 1 5/2 (5/4)²
2 (1 + (c/4)t+))u.l
For any & E 1S St), observe that we get at least uut from the first contract or and at least (1 + a in the second contract. Therefore we get at least
1+ 6/2
(5/1)²
v.t + 1+ (5/4)s (1 (f/2)) 2 (1 (+/1)))),
1 + #/2+ (s/4)
G General Contracts
In this section, we give general contract instance with = 4 actions (3 non-null actions) and m 4 outcomes (3 non-null outcomes), where the best dynamic contract provably outperforms the best free-fall dynamic contract. The instance in question is defined follows:
30

---

The cost vector = (c1, 22 C3, ca)
00..2,004.0..
The reward vector (21,72,13, ra)
1.,
2.0.
/1.00
0.00
0.00
0.00
0.45
0.20
0.25
0.10
The forecast matrix is given by F
0.35
0.05
0.25
0.35
0.15
0.30
0.30
0.25
This instance was found by a programmatic search 12 over a large collection of instances. For this instance, we can (again, programmatically) compute that the best free-fall dynamic contract achieves a net asymptotic utility for the principal at most 0.753 per round. At the same time, we can exhibit a non-ffree-fall dynamic contract for this instance that achieves utility of least 0.764 per round. For conciseness, we present the details of our approach in Appendix G.I, where we construct well-tailored linear programs that provide the aforementioned intricate instance.
G.1 Programmatic LP Search Sub-Optimal Free Fall Against Non-Linear Contracts
At high level, the verification of the example of section 3.3 relies on the following fact: given sequence of actions (a',a? .?...... a ), , we can construct a polynomial-sizee linear program to find the optimal continuous-time dynamic (general or free-fall) contract {(p", "", {)))) with this specific action sequence.
The variables of this LP are the rh and p* corresponding each action at, The constraints follow from the definition of a valid trajectory of play in Section 2.2 and are as follows:
(Non-negativity) p", Th 2 O.
(Time normalization) K -== 1. We normalize the total duration of the trajectory 1.
Σ , us. (p a+
(Beginning of segment is best
response)
Ek K uy (p*, dd) for any a' E [n]. This represents the constraint at E BR(D"-1).
(End of segment is best response) E r un (p" aa*) 2 E n uz (pt, for any a' E [n]. This represents the constraint at E BR(p*).
The objective the LP is the optimizer utility Ek= (p* a²). ) If we want to further impose that the contract is a free-fall contract, we can add the constraint that p* = 0 for le >>> 1.
For free-fall contracts, we have an additional constraint on what sequences of actions are possible. Note that free-fall contract will never repeat an action
particular, after the initial segment, the cumulative utility of each action E [n) decreases by per round, so the sequence of actions a free-fall contract passes through must be sorted decreasing order of cost. This means there at most 2n sequences of actions to check, and by checking all of them can provably compute the optimal free-fall contract for a given general contract instance.
(a*, ..,...,.. k
On the other hand, it's not clear if there are any constraints on how complex the sequence of actions for the optimal general dynamic contract can be be-iit it an interesting open question whether there exists any efficient (or even computable) algorithm for computing U* for a general contract instance. Luckily, in order show this separation, we need only exhibit a single general contract which outperforms the best free-fall contract. In the example above, we compute the best general contract for the same action sequence that the optimal free-fall contract passes through, and observe that the general contract obtains strictly larger utility.
12ehe code verifying this example can be found at: https://colab. sandbox. googze..ooo.e..oooooooo com/gist/ /144a//00..2222020000/2021000000 imwpa/ll//ppmmmmmmmmmaamaamaaaaa dynamic- contracts minnimil example. ipynb
31

---

H Simplifying Tool: Reductions from Discrete to Continuous Time
H.1 Proof of Theorem 2.4
In this section we prove Theorem 2.4, showing that instead of working with discrete-time learning algorithms, it instead suffices to work with the set of continuous trajectories piecewise-linee trajectories described in Section 2.2. Our proof will generally follow the proof structure of [27] (which proves a similar reduction in the case of two-player bi-matrix games), with few slight additional complexities due to some differences in notation (namely, we do not insist that every segment lies in the interior of best-response region).
Before we begin the proof, it will be useful to establish a helpful auxiliary lemma about trajectories. Call segment (p*, Th a²) of trajectory π degenerate it lies on the boundary of two best-response regions (i.e.. |BR(p"-J) BR(P")) > 2), and non-degenerate otherwise. Let Utila(z) be the utility contributed by just non-degenerate segments. We begin by showing that starting with any trajectory π, we can construct mostly non-degenerate trajectory To with (tila(To) almost as large Util(T).
Lemma H.1. For any trajectory π and any there exists trajectory wo such that Utilo(Tro) 2 (1 (tti)())
Proof. Let = ((p Th )²)}. We will produce To by interleaving sequence of small perturbations (a", (8) into v for some of E IR and 8* > O; that is, we will let no be defined by the sequence of segments (q',8) 8)), (p', (r,aaa))) the best-response of the learner for the perturbation segments (4" 55)), because utility from these segments (in fact, these perturbation segments might cross best-response boundaries, in which case we can split them into smaller segments). We will show that if we choose o' and 8² correctly, a is the unique best-response for each of the shifted (p* , aa*) segments.
(92, (,,,)).... ....... (9 8*), (p", ,=,aa Note that we have not specified
will not count the
Without loss of generality, assume Ee Th 1. For any t E [0, 1]. we will let (()) be the average contract time under trajectory æ. That is, if 7! + 72 + + ri-1 + with S 7 r", then
p(t) r'pp' + +
+
+ Tp'
t
For each e [k], we will also let A 81 + 82 +... 8 and Q' = (6' +
Now, if t 7 + 72 + ... + 7 + T with 0 < r < T', we will let (t) be the average contract under trajectory æa time A + r (i.e., time r into segment (p', ,0,7 a. ",aa).. ). It the case that for such f,
Q'A' + tp(t) A +t
A A +t (Q' - p(()).
(1)
p())
We would like to choose Q' and A such that for each E [ki]. for a large sub-interval of E [0, +"), the unique best response to (t) is exactly a'. To begin, note that for any sequence of strictly positive contracts Q' E TR there is a sequence of 9² and 8 that implements it (because we can make each Q' any convex combination of Q' and q²). Moreover, we can make A arbitrarily small, because scaling all the 8' simultaneously does not affect the values of the Q²
Now, for each i, we will set Q' to positive contract that uniquely incentivizes action a². Note that non-negative contract exists by our assumption in Section 2; but since infinitesimal perturbations maintain the property that the contract uniquely incentivizes a', there must also be a positive contract with this property. We claim that if BR(Q*) = {a*} and at E BR(p(t)). then for any À < 1, BR(p(t) + X(Q p(t)) = {a*). }. To see this, note that we can write p(t) + X(@ p(t)) = (1- -t))p((t) + AQ* Since the utility of the agent is an affine linear function in the contract they are offered, for any action a' # a we have that un ((1 - ())(() + XQ a²) = (1 (p))( at) +
\ua(Q*, a+) > (1 - (p() a') + (u a') = u ((1 (1) X
It follows that if we choose the Q' in this way, (R (t)) {a*} and therefore each of the segments (p', T5, at) is non-degenerate. We will set A equal to Doing so, we have that:
32

---

Σ up(p',a'r"
Utilo(To) 2
2 et)l((
1 An
Equipped with Lemma H.1, we can now prove Theorem 2.4.
Proof of Theorem 2.4. We follow the proof structure of [27] and prove both parts separately.
Part 1. Let = ((r,, r², a²) }]=] represent a valid strategy for the principal in the continuous-time problem. Without loss of generality, assume Σx r I (if not, we can divide all 7 through by Ex without changing the value of this strategy). We will convert и into the following discrete-time strategy for the principal: for each i E [K] (in order), the principal offers the contract p² for T rounds.
Our goal is to show that for any 5 > 0 and any mean-based algorithm A, the above strategy results in least (x) 8yT o(T') utility for the optimizer. The conclusion then follows by choosing trajectory π for which (T) > U - =/22 (such a exists by Lemma H.1 and the definition of U*) and some d z/2. In the remainder of this proof, we will fix a specific mean-based algorithm A that is maaddd-aa for some ((T) = o(1).
As in Definition 2.2, let dit denote the aggregate utility of action i the agent the first t rounds. Let T = Σ T'T, and consider the values of o for rounds E [T*- corresponding to the kth segment. Note that or is linear in this interval and so we can interpolate
11 (t - Th Jopt (T t)oT=
TK
Furthermore, assume that segment k is non non-degenerate, and so B BR(P"R(()) {a²}. In particular, for any 1 E [7k-1, [ and a' * ag, either Oyp-1 > Opé-i_a or T > 0T .a' As a consequence of (1), this means that for any EY > 0, there exists òş 0 such that for t e [7 + , ,7* - =E Tr,a 2 Tt,a' + 6,7'. For sufficiently large T, 6 > >()),, and so the learner will put weight at least (1 nT(( on action a². The total utility of the principal from these rounds therefore at least
(1 (T)) 26x)= a²) 2 urp(p" at) - (nq(T) + 2.x)..
(2)
Summing all non-degenerate segments k; we find the total utility of the principal is at least
E - Σ ((n)((T) 25 I (Til Σ k(ny(T) 22x)
By choosing b sufficiently small, we can guarantee that this is at least Utilo(T)) 8T for sufficiently large T. as desired.
Part 2. Fix any E 0. Assume that for some sufficiently large To. there exists (possibly adaptive) dynamic strategy for the principal that guarantees utility at least (U* + +)To against every mean-based agent. We will show that this implies the existence of continuous trajectory and Util(TT) 2 U + E, contradicting the definition of U* Fix y(T) 112 and any time t, let J = [n]](maxx ot,,) ot, < (T)T) be the set of actions for the learner whose historical performance are within (I')I" of the optimally performing action. The set Jr contains exactly the set of actions that the mean- mean-based guarantee implies the agent must play with high probability. Our agent will do the following: if the principal is about to play contract p', the agent will play the action j E J, that minimizes (p',p. .j) (note that because we are tailoring the agent to this principal, we can do this).
Assume that this results in the principal playing the sequence of contracts p², p².p², .p.....pp2 To. Consider the trajectory defined by the sequence of tuples 1p",1/Tb) (p² 1/Tb), (p. 1/To). In this
33

---

description of the trajectory, we've omitted the response action for the agent, which can be any best-response action for that segment. In fact, some segments may not be valid, as they start in one best response region and end in another; for those, we can subdivide them into however many parts are necessary to form valid trajectory.
Now, note that the sub-segments corresponding to the step (p', 1/To) only contain agent actions in the set Jz. This is since the agent utility the start of this segment is or, the agent utility at the end of this segment is o++1 each component of 0++1 - Oy is at most 1 (since the problem is bounded), but any action j not in Jr is at least ((T) away from optimal. The principal's 's utility contributed by this segment is therefore at least 1 obtained in round of the discrete-time game. Therefore the total utility Util(TT) of this trajectory is at least U g but this contradicts the definition of U*, as desired.
To minjeJ, (p'p'.)) .). But this is exactly the utility the principal
We will need the following lemma which says loss of generality.
restrict our attention to finite-suppors D without
Lemma H.2. Fix a principal-agent problem, a > 1, and an e > O. Let 'D be any distribution over trajectories. Then there exists fintte-support distribution DD' over trajectories with the property that Util, 2 (D).
(1) (m)] 2 Ut for eacht in the discretized set of time-intervals Se, = {1/7,, 1/7 + e/7, + 2e/Y.....
Proof. We first claim the following: if distribution 'D has the property that EE
E/4, 1}. then is the case that Bx [up (0) (+)) 2 (U - =) for all E [1/r, This follows from the fact that the principal's profit per round is bounded above by 1, so |u
( (T)
t/. up (m) - I -/. In particular,
if t' is the closest element of S,,e to a E [1/7,, 1), it is the case that [up (t) (T) - upp s e/7 S st.
Now, associate each trajectory the |Se,y/tuupl of real numbers [(T) [up (4) (T)), define f(D) = [f Define X' = {f(z) π is a trajectory] C RR S to be the set of all such tuples. By Caratheodory's theorem, we can construct distribution over at most |S| elements of X that (is arbitrarily close to) (D), for any D. we let D' be the corresponding distribution over trajectories, this satisfies the constraints of the theorem statement.
H.2 Reduction from Discrete to Continuous Time with Unknown Time Horizons
In this section, we extend the previous reduction to the case where the time horizon can belong to an interval. One of the biggest differences is the introduction of this parameter y 2 1 which equals the multiplicative ratio (T/T). Instead of trajectory = {p 7* a² Tk=1 being solely evaluated at its end time T.K we now care about its performance over its final interval of multiplicative width namely T JK].
K
In order quantify the performance of trajectory at a certain time 1, we will introduce some corresponding parenthetical superscript notation. In particular, ( (x) will denote the cumulative expected principal utility of trajectory æ from time zero to t, and is formally defined as
Aurlpt at) + (1 - T (p .ak))
if E [TK,TK-) if TK.
(2) P (T)
Tuuppp"
Then, the worst-case (under possible time horizons) expected (under drawing from the distribution and actions producing random outcomes) utility of the principal for distribution D is given by
up
(aT
(T)
Util,
min ENND xE[l/x.]
xTK
where each T is according to the drawn trajectory n.
Finally, let U = supp Util, where the sup runs over all distributions of valid trajectories of arbitrary finite length. We can think of U as the maximum possible worst-case utility of the principal in the unknown time horizon continuous setting game.
34

---

Theorem H.3. Fix any principal-agent problem and y 2 1. We have the following two results:
1. For any > O, there exists an oblivious strategy for the principal that gets at least (U*, e)t - ((t) utility for the principal for all E [T, [+T], sufficienty large T.
2. For any E > there exists a mean-based algorithm such that no (even adaptive
principal can get more than (U, + +ett 8 + o(t) utility against agent running A for all t f any T.
Proof of T'hhorem H.3. Part 1. Begin by picking a strategy 'D for the optimizer in the continuous- time game that achieves utility at least U e/2. This strategy 'D is a distribution over trajectories :; by Lemma H.2, we can assume (at the cost of losing arbitrarily small (E)) term) that D has finite support. For each of these trajectories, we apply Lemma H.1 to transform into a new trajectory xL which obtains least (1 e) fraction of the utility of on non-degenerate segments. We will also normalize the total duration of each x' to 1.
Now, note that since inequality (2) holds per segment (and indeed, even fractionally per segment), we can convert each resulting trajectory n' to a discrete-time strategy over T rounds, with the property that for sufficiently large values of T, for any E [ = T/7, TJ, the utility of this discrete-time strategy until time is at least up! (TT). Taking the corresponding distribution over these discrete-time strategies (choosing a sufficiently large T for all such strategies note that we can do this because D has finite support). we obtain a discrete-time randomized (but otherwise oblivious) strategy for the principal that satisfies the theorem statement.
Part 2. As in the previous proof, fix an E > O, assume to the contrary there exists a Tn along with a discrete-time (possibly randomized adaptive) dynamic strategy which achieves least (U; e)t utility for the principal for all t E [To/7; To] against any mean-based bidder. Construct the same mean-based bidder as in the proof of part 2 of Theorem 2.4, which always picks the action in the set of approximate best- responses that least to the minimum expected utility for the principal.
When this principal plays against this agent, this leads to a distribution over sequences of con- Each such sequence can be converted to a trajectory æ of the form
tracts (p², ............. ...-, ,...). =f) {(p', 1/To). (p², 1/To). (pTo, 1/To)). This trajectory π not only has the property that (ti upper bounds the utility of the discrete-tines agent (as in the proof of part 2 of Theorem 2.4), but in fact up (T)) is at least the utility of the agent discrete-time agent at time ITo (by exactly the same logic). It follows that if we let DD be the distribution over such trajectories, it is the case that (D) 2 U + e. This contradicts the definition of U.², as desired.
Finally, we conclude this supplementary section with the proof of preliminary lemma exploited in Section 3.1
Lemma H.4. (Restated Lemma B.2) Consider any dynamic contract. For any time interval in which a mean-based based agent plays single action, we can replace the contracts in this interval with their average and oblain overall a revenue-equivalee dynamic contract.
Proof. The result follows since the utility for the principal up is affine in its first argument. Formally, let π = { 7* {K) be a dynamic contract, with at k++ a for some k. Consider a different contract x' where we replace the consecutive pair of segments and (1 pk+1 a k+1) with the their average segment, i.e., (7, nK + *&+1 a). where pl+1), and all other segments remain the same as in æ. Then,
(It "T -*,,at) ata
p = (p 1
have Util(T') (til(T)) Σイ (7*up(p*, a) -k+lup(p a) (7* bb+))p 0. That is, both contracts give same utility for the principal. A similar argument holds for the discrete formulation of the model as well.
As with the known mone-oorionn result, this holds against adaptive principals in the full full-feedback setting, if the principal is deterministic. See Appendix H.3 for details.
35

---

H.3 Mean-Based Algorithms in the Partial-Feedbatt Setting
We conclude with some clarifying remarks on the definition of mean- baaa- learning algorithm in stochastic, partial-feedback setting (the bandits setting). The proofs of Theorems 2.4 and H.3 continue to hold essentially as written, but there are some subtleties that are worth pointing out.
We begin by clarifying the definition of mean- based in a partial-information setting. Formally, we write it as follows. Recall that of Σe= uf is equal to the expected utility the learner would receive they had played action for the first 1 rounds, assuming the sequence of contracts the principal offers the learner remains static (so in particular, for an adaptive / stochastic principal, o² is a random variable).
Definition H.5. (Mean- -anndd algorithms in partial-ing information settings) A learning algorithm in a -nntialiiformaation setting is (TT) -me---manaatt based if the following conditions hold: Fix any adaptive dynamic strategy of the principal and let (for each round E [T), Xt be the event that of oby (T() TT and Y, be the event that the algorithm takes action i in round t. Then the algorithm is mean based if the probability Pr[X, A Yi) (over all randomness in the learner's 's algorithm, principal's strategy, and problem setting) is at most (T)). We say an algorithm is mean- mean- if it is (T)) -mean- based for some ((T) = o1).
The above definition is very similar to Definition 2.2; the main reason for stating it like this is to avoid implying the slightly stronger constraint that event X, deterministically implies that the probability of Y, is small conditioned on the current history of play. This implication is fine in the full-information setting where algorithms like multiplicative weights will indeed deterministically place small weight on action i' if the event X, holds; but in the partial-information setting, there is always a chance that the learner is unable to accurately observe whether X, holds, and therefore no partial-infol intiiaaaiiooootiionn algorithm can achieve that guarantee. On the other hand, standard bandit algorithms with high-proe bigh-irobability guarantees such as EXP3 (see [17J) satisfy the above definition of mean-based learning.
The proof of Theorem 2.4 works equally well with Definition H.5. The only subtlety is in Part 2, where show a principal cannot do well against all beean-based agents, we design a based agent that foils this specific principal. If the principal is randomized and adaptive, the agent cannot accurately predict the expected contract y the principal will play in round (note that if the principal is adaptive but deterministic, the agent can still simulate the principal's behavior - likewise, if the principal is oblivious and randomized, the agent can compute the expected contract p' any round). The proof of Theorem H.3 is similar.
I Final Remarks
The following are observations about our repeated contract games with learning agents that arise from our analysis and from known results on learning agents in general games.
Observation L.1. In the fixed contract setting, for any regret-minimizing agent in the limit T + co the support of the average empirical distribution of play includes only best-response actions with probability one. Therefore, the repeated game with static contract against regret-minimizing agent is essentially equivalent to the single-shot game against a rational agent.
Proof. This follows directly from the regret- sngret-minimizationn property. Indeed, suppose, for the sake of the support which is not a best response. Denote the
contradiction, that there exists an action best-response utility by OPT. Action a is played with probability p >> O. Notice that since there is only one player, the regret from any other action cannot be negative. Then we have that the regret is Regret 2 p(OTT u(a))T = OT)), a contradiction.
Observation 1.2.
the agent is using no-swap-regrel algorithm, then the optimal static contract played repeatedly is also optimal in the dynamic setting. As a corollary, this is the case also for general no-regret algorithms if the agent has at most two actions.
Proof. The result follows from [27], who show that in any game between an optimizer and a no- swap-regret algorithm, the optimizer cannot extract higher payoff than the Stackelberg value of the game where the optimizer plays the first move. The corollary is since with (at most) two actions internal regret and external regret are equivalent.
36

---

Below we show that in our analysis of dynamic linear contracts, it suffices to only examine linear contracts with a [0, 1]. Note that although this is obvious in the static setting (offering a requires the principal to suffer negative utility), it is not a priori clear that the principal cannot benefit via a dynamic strategy which offers contract with a >> for some fraction of the time horizon (perhaps counterbalancing it by offering contract with a much smaller later on). In fact, [43] show that when the agents have private information ("types") the principal can benefit by offering a randomized menu of linear contracts which possibly contains linear contracts with 1.
Nonetheless, we show that the principal cannot benefit by doing this in the dynamic setting. The proof below follows from a slight modification of Lemma B.3 in our proof of Theorem 3.1.
Observation I.3. Let x = {(a 7* )=))==> be any linear dynamic contract with some linear contract a² > 1. Then there exists a dynamic linear contract x = {(a", -", )) with Util( (T) and where & < for all k.
Proof. We first observe that in Lemma B.3, when agent is indifferent between actions and + 1 then the change in utility for the principal by choosing an action i i over is proportional to and therefore the principal will prefer agent to play action i when O > 1. However if a² < 1, then the principal will prefer that the agent play action + 1. Thus in this modified rewriting lemma, contracts with breakpoints greater than will prefer the lower action and breakpoints lower than 1, will prefer the higher action. By modifying Lemma B.3, we can rewrite any linear contract ı using the rewriting rules of Theorem 3.1 into new linear contract x with breakpoints that are at most 1, without any loss in utility.
(1 a²) This is negative if a*
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction an accurate description of the proofs in the rest of the paper. The paper is theoretical and the proofs are self-contained.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Our paper focuses on the case of linear contracts; the general contracts setting is also discussed and is much more difficult (e.g. in some cases it is not known whether these objects are even computable). This is discussed in the body of the paper.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specifiiatton, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
38

---

Answer: [Yes]
Justification: Our paper fully provides the assumptions and the claimed proofs. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is purely theoretical paper and it does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
39

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include any experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ccppp.ccpppulcc///eecccc/ gealdiic/guiee...ee /CodeSubmia (iioiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is purely theoretical paper and does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is purely theoretical paper and does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
40

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurip: httpp//sss.cppbbcceccccecceeeeee
Answer: [Yes]
Justification: The paper does not use humans or data. The authors do not believe the listed potential harmful societal impacts apply.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is purely theoretical and works in an abstract setting and has no direct foreseeable impact society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
41

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is purely abstract and theoretical and has no foresecable risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
42

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The project neither involves crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The project neither involves crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "yy6lyz74eG", "reviewer": "Reviewer_HskF", "summary": "This work studies the problem of contracting with a no-regret learning agent. They show that\n\n- In linear contracts, the optimal dynamic contract against a mean-based learning agent is a free-fall contract.\n- dynamic contracts can be win-win. Both principal and agent can benefit from some dynamic contractor and mean-based learning agent.\n- Knowing time horizon is very important. They provide a lower bound showing that there exists a problem in which no dynamic strategies outperform the optimal static linear contract.", "questions": "- In line 218-226, they introduced full feedback and bandit feedback. I am a bit confused here about bandit feedback. Does this mean that the agent won't observe the chosen contract $p_t$ at each round?\n\n- In Thm 3.2, they show that there exists a problem in which optimal dynamic contracts lead to \"win-win\" for both principal and agent. I am curious if there are scenarios in which agents get hurt by running learning algorithms.\n\n- For Thm 4.3, in the construction for proving the theorem, is $(\\epsilon, 1)$ feasible? I think they should mention this to justify that the infeasibility is indeed caused by the uncertainty of time horizon but not that the game itself is infeasible.", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem studied by this work is very interesting --- repeated contracts with learning agents. \n\nThe results are novel. There are some interesting findings in this work, including the optimality of free-fall contract, the existence of win-win scenarios, and the impact of the knowledge time horizon.\n\nThe writing is clear.", "weaknesses": "If I have to say some weaknesses of this work, I would say most results seem to be instance-dependent but not general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We address the points raised in the review below. \n\n**Bandit feedback:**  One possibility for bandit feedback is when the agent does not observe the contract $p_t$ but only observes the payoff induced by this contract for the action that was played. A different scenario is when the agent may observe the contract but does not know the outcome distributions or what they imply for the actions that were not played, which again requires some additional exploration. Our analysis, however, holds for full feedback or any of these partial feedback scenarios.  \n\n**Theorem 3.2:** The theorem shows that there is a positive measure of contract games where learning by the agent and an optimal dynamic contract by the principal lead to a strict Pareto improvement (win-win) outcome. This is, however, not true for all contract games; there are games where learning reduces a player’s utility compared to a myopic best response (for instance, the example in the introduction). The construction in Theorem 3.2 shows that there are cases where using either a best-response strategy or, alternatively, smarter learning (no-swap-regret) leads to a loss compared to using simpler learning (mean-based learning; see our remark at the end of Section 3). So, whether it is beneficial to use learning, and which type of learning to use, depends on the game.      \n\n**Theorem 4.3:** Whether or not $(\\epsilon,1)$ is feasible just depends on whether $(1 + \\epsilon)$ is less than the ratio between the optimal (known-time horizon) dynamic contract and the optimal static contract; for any problem there is some sufficiently large $\\epsilon$ to make $(\\epsilon, 1)$ infeasible. The theorem statement is perhaps easier to conceptualize by considering its contrapositive: if there is an $\\epsilon > 0$ such that $(\\epsilon, 1)$ is feasible, then for any $\\gamma > 1$ there exists an $\\epsilon_\\gamma$ such that $(\\epsilon_\\gamma, \\gamma)$ is feasible as well. We will provide additional context for this theorem to better clarify the situation.", "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": "eKuyItNLLA", "reviewer": "Reviewer_x3aE", "summary": "This paper considers the problem of contract design against a (mean-based) no-regret agent. The papers shows several results on the optimal contract design in this dynamic setting. First, with binary outcome, dynamic linear contract, it is optimal to design a free-fall contract. Second, the paper constructs instances (with non-zero measure) where optimal dynamic contract can pareto-improve the principal and agent utility than the optimal static contract. The paper also extends some of the results to the case of non-binary outcomes and unknown time horizon.", "questions": "Please address my concern in the above section if possible.", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is super well-written and easy to follow. It clearly explains the problem and the solution, as well as their relation to various lines of prior work. The examples and figures in these papers are also very carefully constructed to explain intuitions of their results. These readability optimizations help us a lot to get a quick and deep understanding of the paper.", "weaknesses": "While I think the paper is well-executed from its writing to technical derivation, the problem setting and the result it derives seems to me a bit artificial. The optimality of \"free-fall contract\" does not make any economic sense to me, but rather an unrealistic exploitation of the agent's no-regret learning algorithm. I can be wrong here, but I cannot think of any realistic situation in practice where anything similar to the free-fall contract is implemented. Maybe something loosely related: the quality of many restaurants, hotels over time can degrade after they establish a good reputation. This is because they can exploit the reputation to attract customers and reduce the quality to cut the cost. This is a kind of \"free-fall contract\" in a sense, but it is not sustainable (unless time horizon T is known to be finite like your setup). In general, I would say the mean-based regret model may not be a good model to capture the real-world learning agents, which prevents the unrealistic yet optimal solution of \"free-fall contract\": Perhaps they are not no-regret agents but admits a strong discounting factor to the historical reward in the regret notion so that they are quickly aware of the change in the contract (due to the distribution shift in the received payment) and adapt their response to it. The last section on the case of unknown time horizons is more realistic and it indeed rules out the free-fall contract as the optimal solution, though the results are not as strong as the simpler cases. Overall, I would say the paper could have taken a much stronger stance by exploiting its economic implications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We address the main point raised in the review below. \n\n**Mean-based learning and free-fall contracts:** We completely agree that—knowing now the exploitability of mean-based learning agents—studying different types of learning approaches, such as learning with recency bias or loss aversion, would be an important direction to explore. Such approaches can be realistic for human learners while preventing the principal from implementing free-fall contracts. \n\nThere is, however, significant interest in establishing clear results for mean-based learning in our setting. First, we note that the result that a principal can exploit mean-based regret-minimizing learners in a large class of contract games using a very simple family of contracts (free fall) is not trivial and certainly not obvious before doing an analysis. Furthermore (see also our response to review HskF), our results show that it is not always better to use smarter learning strategies (after accounting for how the principal might adjust their dynamic contract). While this analysis (Theorem 3.2) uses a particular construction, it demonstrates that whether it is beneficial to use learning and which type of learning to use is more subtle and depends on the details of the game.\n\nAdditionally, as also suggested in the review, with human agents, one could think of free-fall contracts as happening over at least limited time spans. There are lines of work in economics studying delayed or insufficient responses to new information (see [1,2,3] below), or even limited learning over extended time periods [4]. Essentially, a decision that was extremely good for a long period of time may have momentum and will not always be abandoned in the first (say) month of a bad outcome. Mean-based regret minimization is a form of learning with these properties. \n\nWe would like to emphasize, however, that we think there is value in our analysis regardless of whether mean-based regret minimization is the way human agents act. Mean-based regret minimization is a prominent algorithmic approach to learning in repeated games, which has been extensively studied in other contexts. In particular, algorithms of this family have been traditionally motivated in the theoretical economics literature as “simple,” “adaptive,” and “natural” theoretical models of learning by boundedly rational agents (see, e.g., [5] and references therein). It is thus important to understand the implications of such learning approaches for repeated contracts, especially in comparison to other types of learning and to static contract setting. In this sense, our analysis of mean-based and no-swap regret learners in this paper is a first step in exploring contracts with learning agents more broadly. \n\n[1] Carroll, C.D., Crawley, E., Slacalek, J., Tokuoka, K. and White, M.N., 2020. Sticky expectations and consumption dynamics. American economic journal: macroeconomics, 12(3), pp.40-76.\n\n[2] Bouchaud, J.P., Krueger, P., Landier, A. and Thesmar, D., 2019. Sticky expectations and the profitability anomaly. The Journal of Finance, 74(2), pp.639-674.\n\n[3] Ba, C., Bohren, J.A. and Imas, A., 2022. Over-and underreaction to information. Available at SSRN 4274617.\n\n[4] Benjamin, D.J., Rabin, M. and Raymond, C., 2012. A Model of Non-belief in the Law of Large Numbers. Available at SSRN 1945916.\n\n[5] Hart, S. and Mas-Colell, A., 2013. Simple adaptive strategies: from regret-matching to uncoupled dynamics (Vol. 4). World Scientific.", "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": "l1VUDaKEL0", "reviewer": "Reviewer_caMQ", "summary": "The paper studies the repeated interaction between a principal and a learning agent. In particular, the authors assume that the agent employes a mean-based learning algorithm. The goal is to design a sequence of contracts that maximizes the principal’s cumulative utility. The main result of the paper is to show that in binary outcome settings the optimal strategy for the principal is to employ a “free-fall” contract in which: the principal commits to the same contract for some rounds and than switch to the zero contract. This result generalizes to settings with more than two outcomes in which the principal restricts to use linear contracts.\n\nThe second main result of the paper regards the uncertainty over the time horizon $T$. The authors show that this uncertainty hurts the effectiveness of dynamic contracts, characterizing the performance of optimal dynamic contracts.", "questions": "None.", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper introduces a new interesting problem and provides interesting results. The techniques are novel and non-trivial. The paper is well-written.", "weaknesses": "I’ve some doubts on the realism of a model in which the agent is a no-regret minimizer, and not a swap regret minimizer. Nonetheless, this difference is clearly analyzed in the paper, and I do believe that the study of this setting is important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We will further extend our discussion of the learning models, and in particular, the comparison between mean-based regret minimization and no-swap regret. Please see also our responses to the other reviews regarding this point.", "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": "eZ6dUBJIer", "reviewer": "Reviewer_8ua3", "summary": "This theoretical paper studies repeated principal-agent contracts where the agent uses no-regret learning algorithms rather than complex strategic reasoning. The main results characterize optimal dynamic contracts against mean-based learning agents:\n\nFor linear contracts (including success/failure settings), the optimal dynamic contract has a simple \"free-fall\" structure - offer a carefully designed contract for some fraction of time, then switch to paying nothing. This can be computed efficiently.\nThere exist settings where both principal and agent benefit from the optimal dynamic contract compared to the best static contract.\nWith uncertainty about the time horizon, the principal's ability to outperform static contracts degrades as the uncertainty increases.", "questions": "1. Are there natural economic settings where the \"win-win\" dynamic contracts might arise in practice?\n2. Do you expect qualitatively similar results for multiple interacting agents? What are the key challenges there?\n3. How do you expect the results to change if the agent uses a more sophisticated no-regret algorithm, such as one with bounded memory or one that is aware of the principal's strategy?\n4. The paper focuses on optimizing the principal's utility. How would the analysis change if we consider Pareto-optimal contracts that balance utilities between the principal and agent?\n5. Are there any interesting implications of your results for the design of real-world incentive structures, such as employee compensation plans or insurance contracts?\n6. Your results show that dynamic contracts can sometimes benefit both parties. Are there conditions under which this is guaranteed, or conversely, conditions under which it's impossible?\n7. The paper mentions potential extensions to MDPs. How do you envision applying these ideas to more complex sequential decision-making settings?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel and interesting problem formulation, bridging contract theory and online learning\n2. Clean theoretical results with full proofs provided\n3. Careful analysis of both linear and general contract settings\n4. Considers practical issues like unknown time horizons\n5. Results provide interesting insights, e.g. potential for \"win-win\" dynamic contracts", "weaknesses": "Limited to mean-based learning agents;\nOptimal contracts for fully general (non-linear) settings not analyzed", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We address the points raised in the review below. \n\n**Win-win dynamics:** In general, win-win situations arise in “general-sum” games, where the players are not complete adversaries, but rather can increase and share the overall welfare. In the constructions we used for demonstrating win-win dynamics, the structure was that different agent actions resulted in different levels of welfare. Thus, both players were better off if the principal could initially invest to create a strong motivation to play high-welfare actions. More broadly, one takeaway is that win-win scenarios, at least from our example, can be those where such an investment has an increasing return in terms of welfare.\n\n**Multiple agents:** The question of how to optimally incentivize multiple learning agents is an interesting one to consider in future work. A main challenge is that if agents jointly produce an output—meaning the payoff for the principal is a function of the agents’ joint action profile—it may become complicated to disentangle their contributions and incentivize them. It seems plausible that if agents’ contributions to the payoff are additive and contracts are linear (one alpha per agent), some multi-agent generalization of free-fall contracts might still be optimal. However, we have not analyzed this scenario. Other issues that may arise in interaction between multiple agents that one would need to consider in the model are multiplicity of equilibria and free-riding problems between the agents.\n\n**Different learning algorithms:** We agree that studying different types of learning approaches is interesting. Which type of learning is a good question. Some approaches may eliminate the possibility of free-fall contracts, but could have other limitations. We address below the two potential directions mentioned in the review. We also note that no-swap-regret is known to be the right notion for non-manipulability and results in the optimal static contract remaining optimal.  \n\n*Bounded memory:* If we think about agents whose response at time $t+1$ is only a function of the history of steps $[t-k, t]$, with some constant $k$, other issues may arise, which are not necessarily in the benefit of the agent. This is related to the fact that such agents are not regret-minimizing. An extreme example is when $k=1$. Here, the principal can alternate between incentivizing some good action and paying zero in the following step. The principal ends up not paying anything , but the agent is always responding with a lag of one step and so he plays the good action half of the time. This kind of example is, in fact, not pathological, but could be extended to larger memory size. \n\n*Agent who is aware of the principals strategy:* In this case we need to think through how the agent reasons about their strategies in the repeated game, and are we still thinking about some notion of learning, or about general strategies in the repeated game. The latter case has been studied in prior literature, as we discuss in the introduction, and this was not our focus. A potentially related notion from online learning that one could think about in the context of the first case is contracting with an agent who is minimizing policy regret. This is an interesting direction to look into.\n\n**Pareto-optimal contracts:** The current solution, which maximizes the principal’s utility, is already Pareto-optimal (PO). If we consider PO contracts more generally, the analysis would include contracts that balance utilities between the principal and agent. We suspect that for the classic contracts setting, the entire PO curve can be recovered using similar linear programs to those used to compute the principal-utility-maximizing contract. When moving to the mean-based agent setting, our results already show that the PO curve is improved (we find a point with higher principal utility). However, there will be part of the PO curve that favors the agent and is bound by the total welfare, which cannot be improved. This is an interesting question to more carefully consider.\n\n**Real-world interpretation:** Our results could be interpreted in two main directions: from the perspective of the agent or the principal. On the agent’s side, a potential message is that in repeated contract scenarios, one should be careful in choosing which learning algorithms to implement. Using simple off-the-shelf options like Multiplicative Weights or Follow the Perturbed Leader may make the agent susceptible to exploitation by a sophisticated principal. On the principal’s side, the results show that one can do better by considering dynamic contracts, especially if there is reason to believe that the agent is using simple learning strategies or has some delay in response.      \n\n**Conditions related to win-win scenarios:** We currently do not have a full characterization of the conditions for win-win scenarios. We can think of some such conditions. For example, “all actions have the same welfare” makes it impossible, because principal utility and agent utility sum to welfare and without increasing the welfare pie, principal gains come at the cost of agent losses. On the other hand, our analysis shows that the agent’s utility from a freefall contract is as if the final (stopping) action was played the entire time, so we know sufficient conditions need to imply that this stopping action has higher agent utility than the static contract’s induced action. This is an interesting question for future research. \n\n**Learning in contracts with MDP models:** While MDPs have been studied in contract settings. In the work we mention in the paper, the MDPs are either due to the principal having long-term constraints [reference 9 in the paper], or due to an underlying evolving state of the world [reference 53 in the paper], but not with learning agents. We have not considered the direction of learning agents with states. It would be an interesting direction for future research.", "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:
We thank the reviewers for the constructive comments and will use this feedback to improve our paper. We address the specific points raised in the reviews in a separate response to each review.

Meta-review: The paper studies repeated contracts with learning agents. The problem studied is novel, and the derived results are comprehensive, characterizing optimal dynamic contracts against a mean-based learner. The reviewers agree on the clarity of writing, indicating that the paper is well-written and easy to follow. Given the novelty and the high quality of this work, I recommend acceptance.
Decision: Accept (poster)