Contracting with a Learning Agent

Authors: guru  guruganesh
yoav  kolumbus
jon  schneider
inbal  talgam-cohen
emmanouil-vasileios  vlatakis-gkaragkounis
joshua r wang
s matthew weinberg
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:36:26

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.

Main paper: 
 introduction: 
 In the classic contract setting, a principal (she) incentivizes an agent (he) to invest effort in a project. The project's success depends stochastically on the effort invested. The incentive scheme, a.k.a. contract, is performance-based -it determines the agent's payment based on the project's 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.Due to their immense importance in practice, the design of contracts has long been studied in Economics, forming a rich body of literature that was recognized by a Nobel prize in 2016. Recently, there has been a surge of interest in computational aspects of contract design, leading to the ongoing development of a new algorithmic theory of contracts (see, e.g., [1, 7, 8, 20, 21, 28, 29, 33, 30, 42, 43, 34, 51, 57, 62, 67] ). Much of the computational research has focused on the classic, one-shot contract setting -the principal and agent share a single interaction, in which the principal offers a contract and the agent chooses a best-response action. 1 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 theory beyond the basic single-shot setting and into the realm of repeated contracts, applying a fresh perspective to contract design for repeated interactions.Repeated contracts have been studied extensively in Economics. The literature explores many possible variations of how outcomes, actions, and contracts may evolve over time as the principal and agent interact (see, e.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 on this, we revisit the classic question of optimal contract design in a 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?Optimizing against a 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 ∈ [T ], the agent takes a 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 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 to see that the principal's revenue in this case against a no-regret agent will essentially be the optimal static revenue (Observation I.1 in Appendix I).Our main focus is on "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 sub-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 meanbased, learning (e.g., [13] ). Against such agents, a crisp optimal strategy is immediate from previous work on general repeated games against learners [27, 59] : It is known that the best static solution is also the best dynamic one. In our context this means that no dynamic contract can achieve better than the optimal static contract (Observation I.2 in Appendix I). Since no-swap-regret learning also counts as a 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 naïve, mean-based learning (although, as expected, there are also many cases where the agent winds up worse off due to this interaction). Due to space constraints, we defer a more extended discussion of related work to Appendix A and highlight here our 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 optimal dynamic contract is 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-parameter) 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, 33, 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 a no-swap-regret algorithm is better for the agent against an adversarial player, an agent who commits to using a mean-based algorithm allows the principal more freedom to dynamically implement outcomes of common interest. A similar advantage of simple no-regret learning over no-swap-regret was noted in a different context by [16] .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-dimensional scaling"). However, we also show that absent this single-dimensional scaling restriction, there exist principalagent instances where the optimal dynamic contract does not take this form. Equivalently, with non-linear contracts it is 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.Actions "Failure" "Success" a1: (c1 = 0/6) 1 0 a2: (c2 = 1/6) 1/2 1/2 a3: (c3 = 3/6) 0 1Figure 1 : A canonical contract setting in which a simple dynamic contract extracts higher expected revenue than the best static contract. The table entries show the outcome probabilities given the actions.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 2 for completeness. Consider the setting in Figure 1 . There are three actions with costs c 1 , c 2 , c 3 for the agent, leading, with the probabilities shown in the figure, to two outcomes-"failure" and "success"-with rewards 0 and 1 for the principal. Since there are two outcomes, w.l.o.g. we can consider linear contracts, which pay the agent α for success (leaving the principal with a payoff of 1 -α).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 α 1,2 = 1/3 and α 2,3 = 2/3, respectively. These lead to the same expected utility for the principal, where the expectation is over the probability of success:(1 -α 1,2 ) • 1 2 = (1 -α 2,3 ) • 1 = 1 3 .That is, both α 1,2 and α 2,3 are optimal static contracts. Now consider a principal interacting with a mean-based learning agent. The principal initially offers the contract α = 2 3 + ϵ for T /2 time steps, with some small ϵ > 0. The agent follows his mean-based strategy and plays action 3 (in a 1 -o(T ) fraction of the time with high probability), which yields a utility of roughly α • 1 -c 3 = 1 6 per step for the agent and 1 3 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 T 12 (compared to zero from action 1). But in every step of the subsequent stage, the cumulative utility of action 3 is degraded by an amount of 1 2 and the cumulative utility of action 2 is degraded by an amount of 1 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≈ T 2 • 1 3 + T 2 • 1 2 = 5 12 T > 1 3T . The principal thus improves her utility by a factor of 5 4 compared to the optimal static contract. Figure 2 shows a 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 a 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 λT 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 a single scalar parameter. For details, see Appendix D.Figure 2 : Two representations of the same dynamic contract, as applied to the contract setting described in Figure 1 and repeated for T steps. The dotted red curve on the left describes the cumulative contract at time t as a function of t, with both axes normalized by T . The shaded areas represent the mean-based best-response regions for the agent. The lines α1,2 and α2,3 are the indifference curves between these regions. The right diagram depicts the same dynamic contract as a function of the fraction of total time t/T , where here the vertical axis represents the average contract at time t. 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.We initiate the study of repeated principal-agent problems with a learning agent; the key takeaways from our work are as follows: Theorem (See Theorem 3.1 in Section 3.1). In success/failure settings, as well as in arbitrary contract settings where the principal restricts to linear contracts, the optimal dynamic contract against a mean-based agent is a free-fall 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 a subset of this space of positive measure, both the principal and agent achieve unboundedly better expected utilities from the principal's optimal dynamic contract compared to the optimal static contract.One takeaway from the previous theorem is 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 a buyer committing to a 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.1 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 it starts from an arbitrary contract p ∈ R m ≥0 , and at every time step t ∈ [T ] plays α t p for some scalar α t ≥ 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 are 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 a 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 of 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 advantage is still always possible.Theorem (See Theorems 4.2-4.3 in Section 4). For any contract problem and error-tolerance parameter ε > 0, 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 + ε) 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 ε > 0 such that for a sufficiently large time horizon minimum T , there is a randomized dynamic contract that can guarantee the principal a (1 + ε) multiplicative advantage over the optimal static contract simultaneously for every time horizon T in the range [T , γT ].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 are 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 in 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 or 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 to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
model: 
 We first present basic (non-repeated) contracts, and the class of linear contracts; a familiar reader may wish to skip to Sections 2.1-2.2 on 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 > 1 actions, among which it chooses an action a and incurs a corresponding cost c a ≥ 0 (in addition to a we will use i to index actions). W.l.o.g. the actions are sorted by cost (c 1 < c 2 < ... < c n ) and the cost of the first (null) action is zero (c 1 = 0). There is a finite set [m] of m > 1 possible outcomes, and every action a is associated with a probability distribution F a ∈ ∆ m over the outcomes. The null action leads with probability 1 to the first (null) outcome. Every outcome o is associated with a finite reward r o ≥ 0 for the principal (in addition to o we will use j to index rewards). We assume w.l.o.g. that r 1 ≤ r 2 ≤ ... ≤ r m and r 1 = 0. We denote the expected reward by R a = E o∼Fa [r o ] for action a. As is standard we assume no dominated actions: i) if c a < c a ′ then R a < R a ′ and ii) for every action there exists a contract that uniquely incentivizes it. The contract setting (a.k.a. principal-agent problem) (c,F, r) = ({c a , F a } n a=1 , {r o } m o=1) 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 j ) m j=1 , p j ≥ 0, where p j ≤ p max is the nonnegative amount the principal will pay the agent if outcome j is realized. 2 In particular, p can be the zero contract in which p j = 0 for all j.(2) The agent selects an action a ∈ [n], unobservable to the principal, and incurs a cost c a .(3) An observable outcome o is realized according to distribution F a . The principal receives reward r o and pays the agent p o . The principal thus derives a utility (payoff ) of r o -p o , and the agent of p o -c a .Expected utilities and optimality. In expectation over the outcomes, the utilities from contract p and action a are u P (p, a) = R a -E o∼Fa [p o ] for the principal, and u A (p, a) = E o∼Fa [p o ] -c a for the agent. Summing these up we get the expected welfare R a -c a from the agent's chosen action a. For a given contract p, let BR(p) = arg max a u A (p, a) be the set of actions incentivized by this contract, i.e., maximizing the agent's expected utility (usually this will be a single element, but in the case of ties we include all actions in BR(p)). 3 The goal of the contract designer is to maximize the principal's expected utility, also known as revenue. Such a contract is referred to as optimal.Linear contracts. In a linear contract with parameter α ∈ [0, 1], the principal commits to paying the agent a fixed fraction (commission) α of any obtained reward. Thus by choosing action a, the agent gets expected utility αR a -c a , and the principal gets (1 -α)R a . As α is raised from 0 to 1, the agent's expected utility is affected less by the action cost, and the agent'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 α at which the agent switches from action i -1 to action i (for i > 1) is denoted byα i-1,i = (c i -c i-1 )/(R i -R i-1 ), and is also referred to as an indifference point or breakpoint. For i = 1 we define α 0,1 = 0. Using this notation, for every linear contract α ∈ (α i-1,i , α i,i+1 ), the agent plays action i. In the linear contract setting, the focus is on linear contracts and only such contracts are allowed.We study a repeated contract setting (c, F, r, 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, 5 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 ∈ [T ] by p t , a t , o t , r t , respectively. The agent's payoff at time t is p t o t -c a t . The sequence (p t ) T t=1 of contracts is called a dynamic contract, and the T pairs {(p t , a t )} T t=1 form the trajectory of play. We define the following class: Definition 2.1. A free-fall contract is a dynamic contract in which the principal offers a (single-shot) 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 a 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 payoffs of all actions (whether taken or not -e.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 an 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 u t i be the expected utility the agent would achieve from taking action i at round t, and letσ t i = t-1 t ′ =1 u t ′i represent the cumulative utility achievable from action i up to time t given the principal's trajectory of play. Then:). A learning algorithm is γ(T )-mean-based if whenever σ t i < σ t i ′ -γ(T ) • T , then the probability that the algorithm takes action i in round t is at most γ(T ). We say an algorithm is mean-based if it is γ(T )-mean-based for some γ(T ) = o(1). 6Optimal dynamic contract. The design goal in the repeated setting is to find an optimal dynamic contract: a sequence (p t ) T t=1 that maximizes the total expected revenue against a learning agent (whether mean-based or no-swap-regret, where in either case we assume the worst-case such learning algorithm). In the linear contract setting, the sequence (α t ) T t=1 is composed of linear contracts. If it 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 with7 α ≤ 1.Note that, as described here, the contract sequence is fixed by the principal at the beginning of the game. We refer to such a principal as oblivious. If the principal can choose p t as a function of the agent's previous actions, we say the principal is adaptive. Our positive results (showing the principal can guarantee at least some amount of utility) hold even for oblivious principals, and our negative results hold even for adaptive principals.Optimal static contract. In a repeated setting, a static contract is a sequence of contracts in which the same one-shot contract is played repeatedly. The repeated game with a static contract and a regret-minimizing agent is, in the limit T → ∞, equivalent to the classic one-shot contract game with a 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.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-time 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 a mean-based learner in a repeated bi-matrix game, and show it reduces to designing dynamic strategies for a simplified continuous-time analogue (note that the choice of continuous-time analogue is tailored to mean-based learning -it is not intended to be a special case of a general discrete-continuous 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-time setting (Section 2.1), to a simpler problem in a continuous-time setting. We later extend the reduction to 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 k , τ k , a k )} K k=1 , each representing a "segment" of play where the principal plays a constant contract and the agent responds with a constant action. Here, each p k ∈ R m ≥0 represents an arbitrary contract, each τ k ∈ R ≥0 represents the (fractional) amount of time that the principal presents this contract to the agent, and each a k ∈ [n] represents the action the agent takes during this time. In the linear contract setting, we use the notation α k instead of p k . We sometimes refer to π as a contract, by which we mean the dynamic contract composed of p 1 , . . . .p K for segments of length τ 1 , . . . , τ K .To form what we call a valid trajectory of play against a mean-based learner, the responses a k of the agent must satisfy certain constraints. LetT k = k k ′ =1 τ k ′ ; p k = k k ′ =1 (p k ′ τ k ′ )/T kbe the total duration of the first k segments, and the average contract offered by the principal for the first k segments, respectively. Then each a k (for k > 1) must satisfy a k ∈ BR(p k-1 ) and a k ∈ BR(p k ). In words, a k must be a best-response to the historical average contract at both the beginning and end of segment k (and therefore also throughout segment k).The following is a continuous analogue of Definition 2.1. Definition 2.3. A free-fall trajectory π is a game trajectory in which p k = 0 for all k > 1.Optimal trajectory. The expected utility of the principal along trajectory π is given byUtil(π) = K k=1 τ k u P (p k , a k ) T K . Let U ⋆ = sup π Util(π), where the sup runs over all valid trajectories of arbitrary finite length. We can 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 9 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 an oblivious strategy for the principal that gets at least (U ⋆ε)T -o(T ) 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 8 ) principal can get more than (U ⋆ + ε)T + 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.One important thing to note about Theorem 2.4 is that the first part is constructive. In fact, the discretetime strategy for the principal corresponding to a trajectory π is essentially the straightforward extrapolation, which plays each contract p k for τ k T K T rounds (although a slight perturbation is necessary to account for segments with a non-unique best-response). This means that when we show, in Theorem 3.1, that the utility-optimizing π for U ⋆ takes the form of a free-fall trajectory, we are simultaneously showing that a 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α k = k k ′ =1 α k ′ τ k ′ / k i=1 τ k ′ in place of p k .Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: 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. Guidelines:• The answer NA means that the paper has no 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 a 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-specification, 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 m = 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.The following theorem shows that free-fall contracts are optimal dynamic linear contracts. Theorem 3.1. Let π be any linear dynamic contract. Then, there exists a free-fall linear contract π ′ where Util(π ′ ) ≥ Util(π), and which can be computed in time polynomial in the problem size.The proof is deferred to Appendix B and hinges on applying a sequence of "rewriting" rules which allow us to gradually transform any given linear dynamic contract π with a free-fall linear contract π ′ . At a 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 a higher action is being induced. Grouping together all the stall at the highest action used exactly results in a free-fall contract.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 1 with a slight variation where the cost of action 2 is 1/2+ϵ, with ϵ < 1/(2T ). In this case, the best static contract incentivizes action 1 and yields a utility of 1/3 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 a period of 2 3 T steps and then transitions to action 1 by offering zero payments for the remaining time. This results in a utility of 5 12 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 as much as O(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 O(log(n)) for the agent's utility. Theorem 3.2 (Win-win optimal dynamic contracts). There exist repeated contract settings where an optimal dynamic contract improves expected welfare by a Θ(n) multiplicative factor compared to the best static contract, and where the agent's expected utility improves by a factor of Θ(log(n)). 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 to 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 I.2 in the appendix, following the analysis of [27] ). The agent in this case would have had lower utility. That is, using a 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 to approach the set of Coarse Correlated Equilibria (CCE), 9 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 a related example in general games). In other words -committing to use an algorithm with weaker worst-case guarantees yields better (non-worst-case) results.Unlike in the linear contract setting and the single-dimensional scaling setting, free-fall contracts are 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 to 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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, we explore what happens when 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 [T , T ], and wants to guard against a worst-case choice of time horizon from that range. What are the trade-offs 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: Definition 4.1. Suppose we have a principal-agent problem (c, F, r). Let R ⋆ be the single-round profit of the optimal static linear contract for this problem. We say that a pair (ϵ, γ) is feasible with respect to (c, F, r) if for all sufficiently large time horizons T , there exists a (potentially randomized) principal algorithm A such that the (expected) profit of A at any time t ∈ [T , T = ⌈T γ⌉] is at least (1 + ϵ)tR ⋆ (and infeasible with respect to (c, F, r) otherwise).The last part of our results is Theorem 4.2: for every principal-agent problem and any error-tolerance ε > 0, it is impossible to indefinitely maintain an ε advantage over the optimal static contract. To be more precise, when γ is exp(Ω( 1 /ε)) we know that the instance has become (ε, γ) 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 γ ≥ 1 permit some advantage ε over the optimal static contract. We manage to achieve ε at least Ω(1/(poly γ)) 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 a principal-agent problem (c, F, r). For every ϵ > 0, there exists a γ such that (ϵ, γ) is infeasible with respect to (c, F, r) for all γ ≥ γ. Theorem 4.3. Suppose we have a principal-agent problem (c, F, r). If there exists a γ such that for any ϵ > 0 and γ ≥ γ, (ϵ, γ) is infeasible, then there are no dynamic strategies that outperform the optimal static linear contract.The proof of Theorem 4.2 is in Appendix E; Theorem 4.3, Appendix F. The key ideas are as follows. For Theorem 4.2, we construct a potential function which assigns a value to the current time-averaged linear contract, and show that any principal is 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 a strategy to last for a 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 [ 1 γ T K , T K ] instead of at a single time; this multidimensionality means we must now consider distributions of trajectories (see Appendix H). 
conclusion: 
 In this paper, we provide a 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 a 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-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 a 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 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 a learning agent with a 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 a learner and an optimizer. 
safeguards: 
 Question: 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, or scraped datasets)?Answer: [NA]Justification: The paper is purely abstract and theoretical and has no foreseeable risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 not require this, but we encourage authors to take this into account and make a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Introduction to the Problem. Consider the following motivating examples: a worker joining a new team, a student starting an internship, or a junior professor joining a committee. These agents initially face uncertainty about the required effort and what constitutes good performance. They must decide when to exert more effort and when to reduce it. 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 is increasingly relevant to AI 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 a single payment at the end of the contractual relationship based on all outcomes. Another approach involves deliberately vague contracts, leaving agents uncertain about performance-based compensation (e.g., [3, 11, 31] ). [44] explore how to learn an agent's private type through online principal-agent interaction and contract menus. [10] study principal-agent 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:How should an agent choose their actions in a contractual relationship involving uncertainty and recurrent interactions?Our algorithmic perspective introduces a novel, learning-based approach to 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 noregret learning methods are natural responses for agents. No-regret learning has been extensively studied in repeated games (e.g., [2, 5, 12, 16, 35, 46, 54, 58, 68, 39, 40, 63, 66] ), auctions and economic interactions (e.g., [25, 19, 37, 53, 52] ), and Stackelberg security games (e.g., [9] ). For a comprehensive overview, see [65] . By assuming agents employ no-regret learning instead of complex strategic reasoning, we propose a new approach to repeated contracting.Optimizing Against Mean-Based Learners. Finding an optimal dynamic strategy against a meanbased 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 a 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, even for a single agent, the optimal auction strategy, involving alternating between second-price 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.B Proof of Theorem 3.1 (Optimal Dynamic Linear Contract)Proof overview. We will present a series of "rewriting" rules, which will allow us to replace a given dynamic contract π with a simpler, more constrained, dynamic contract π ′ with utility at least as large as π. At the conclusion of our sequence of rewriting steps, we will see that our contract takes the form of a free-fall contract, thus implying that there is an optimal free-fall contract.We begin not with a rewriting rule, but instead a 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 i at some point, and action j at some later point, there must exist segments of Proof. Note that a k and a k+1 must both be best responses to the average historical contract α k , i.e., a k , a k+1 ∈ BR(α k ). Since BR(α) is always of the form {i} or {i, i + 1}, the conclusion follows.Note that the proof of Lemma B.1 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.1 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 is very general (and in fact applies to 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 a 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 π ′ such that Util(π ′ ) ≥ Util(π) and no two consecutive segments of π ′ share the same agent action (a k ̸ = a k+1 ).Proof. Let π = {(α k , τ k , a k )} K k=1 be any linear dynamic contract. Assume that for some k, a k = a k+1 = a. Then the linear dynamic contract π ′ formed by replacing the two segments (α k , τ k , a) and (α k+1 , τ k+1 , a) with the single segment ((α k τ k + α k+1 τ k+1 )/(τ k + τ k+1 ), τ k + τ k+1 , a) has the property that Util(π ′ ) ≥ Util(π). To see this, observe that the same action a is played throughout the entire interval, and the average payout to the agent is the same. Therefore, in fact we have Util(π ′ ) = Util(π). It only remains to confirm that this is still a valid dynamic contract (i.e., that each prescribed action is still a best response in the corresponding segment).To see this, observe first that the cumulative contract at the start (respectively, end) of the merged segment in π ′ is the same as the start of segment k (respectively, end of segment k +1) in π. Therefore, all segments before and after the merged segment are still correct. To confirm the merged segment, we need only confirm that a is a best response on the merged segment in π ′ using the fact that it was a best response in both segments k and k + 1 in π.For this, let α 0 denote the cumulative contract after the first k -1 segments, α 1 denote the cumulative contract after the first k + 1 segments, α ′ (t) denote the cumulative contract of π ′ during a time t in the merged segment, and α(t) denote the cumulative contract of π during a time t in segments k or k + 1. Observe first that for every x between α 0 and α 1 , there is some t such that α(t) = x. Because a is a best response on the entire segments k and k + 1, this means that a is a best response to x for all x between α 0 and α 1 . Moreover, observe that α ′ (t) lies between α 0 and α 1 for all t. Therefore, a is indeed a best response to α ′ (t) for all t in the merged segment, and the dynamic contract is valid.By repeatedly applying this merging of segments, we can obtain a linear dynamic contract π ′ 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 best response is to take action 3 until time t/T ≈ 0.425, and then take action 2 in the remaining time. The crossing point between the best response regions is marked with a 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 a single linear segment (i.e., a piecewise-stationary 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 π = {(α k , τ k , a k )} Kk=1 be a dynamic linear contract where during segment k the agent is indifferent between actions i and i + 1 (i.e., BR(αk-1 ) ∩ BR(α k ) ⊇ {i, i + 1}), but a k = i.If we form π ′ by replacing a k with i + 1, then Util(π ′ ) ≥ Util(π) (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 thatUtil(π ′ ) -Util(π) = τ k T K u P (p k , i + 1) -u P (p k , i) = τ k T K R i+1 -R i )(1 -α k ≥ 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 a larger number). The fact that the principal can implement this change also follows as a direct consequence of the discrete-to-continuous reduction of Theorem 2.4. By applying the above two rewriting rules (Lemmas B.2 and B.3) along with our observation in Lemma B.1, we can establish our third rewriting rule: it is always possible to rewrite a dynamic contract so that the sequence of actions is a consecutively decreasing sequence. Lemma B.4. Let π be any dynamic linear contract. Then there exists a dynamic linear contractπ ′ = {(α k , τ k , a k )} K k=1 with Util(π ′ ) ≥ Util(π)and where a 1 , a 2 , . . . , a K is a decreasing sequence of consecutive actions (i.e., a k = a 1 -(k -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 a larger action, that is, the smallest k such that a k+1 = a k + 1. Let a k = j (so a k+1 = j + 1). Note that the agent must be indifferent between actions j and j + 1 at the end of the jth segment (i.e., {j, j + 1} ⊆ BR(α k )).There are two cases: either segments k and k + 1 are the first two segments of the dynamic contract π (i.e., k = 1), or there exists a (k -1)st segment. In the first case, the agent is indifferent between actions j and j + 1 for the entire first segment (from time 0 to τ 1 ), 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 learner (since the sequence of actions is decreasing up until segment k). But this means that the agent must be indifferent between actions j and j + 1 also after the (k -1)st segment, and thus for the entirety of the kth segment ({j, j + 1} ⊆ BR(α k-1 )). Since the agent plays j during the kth segment, this also contradicts the fact that π cannot be reduced further by Lemma B.3 (see Figure 4 for an example of this reduction).We are now almost done -Lemma B.4 shows we 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 to 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. Lemma B.5. Let π be a dynamic linear contract where the agent plays a decreasing sequence of actions. Then there exists a free-fall linear contract π ′ with Util(π ′ ) ≥ Util(π).Proof. Let π = {(α k , τ k , a k )} Kk=1 (with a k decreasing), and consider the last non-free-fall segment (α k , τ k , a k ), i.e., k is the maximal k for which α k ̸ = 0. Assume that k > 1 (if not, then π is already a free-fall contract).Let α BR = α a k ,a k +1 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 (α BR , (α k /α BR )τ k , a k ), (0, (1 -α k /α BR )τ k , a k )). In doing so we essentially are doing the inverse of the first rewriting rule in Lemma B.2 -replacing 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 (α BR , (α k /α BR )τ k , a k ) that lies along the best-response boundary α BR , so by Lemma B.3 we can replace it with the segment (α BR , (α k /α BR )τ k , a k + 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 k + 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 π ′ with at least the same utility as π.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 π ′ with Util(π ′ ) ≥ Util(π)) immediately follows.To show that we can efficiently compute this free-fall contract, note that the optimal free-fall linear contract might as well start with a segment of the form (α i-1,i , τ, i) for some indifference contract α i-1,i (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, α K = α j-1,j for some j. To see this, consider a free-fall linear contract π that does not end on an indifference contract. It ends with a segment of the form (0, τ K , a) for some agent action a. Consider the contract π(τ ) formed by replacing the duration of the last segment with τ ; this operation is valid for all τ in some interval [0, τ max ]. Note that Util(π(τ )) is a convex function of τ (it is of the form (Util(π(0))T K-1 + u P (0, a)τ )/(T K-1 + τ )) so it is maximized when τ equals one of the endpoints of this interval. But at both endpoints, α K lies on a best-response boundary (for τ = 0, α a,a+1 , for τ = τ max , α a-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 {α i-1,i , α j-1,j } with j ≤ i 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 D (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-dimensional 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.1 is parallel to the proof of Theorem 3.1 in the sense that we demonstrate how to gradually transform a general single-dimensional-scaling contract into a free-fall contract, while increasing utility for the principal. The main difficulty in 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.1, 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.Proof. Consider the following contract game. 10 There are n > 2 actions, with expected reward R i = v i for some v > 0. Concretely, we let v = 2. The cost of the action are specified recursively by c 1 = 0 andc i = c i-1 + R i-1 -1 2 for i > 1, yielding c i>1 = i k=2 (2 k-1 -1 2). The resulting indifference contracts are thus α i = 1 -2 -i for 1 < i ≤ 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 α i , as the reader can verify, is given by2 i -3 2 - i k=1 (2 k-1 -1 2 ) = 1 2 (1 + i).Notably, this utility is higher for the higher actions. The welfare of action i is thus w i = 1 2 (3 + i). Next, we slightly alter this game by increasing the payoff of action 2 by a small amount ϵ > 0 such that the optimal static contract is now α 2 , which yields a utility of 1 + O(ϵ) for the principal, and the agent is still indifferent under this contract between action 2 and the null action. In the following analysis, we 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 free-fall contract p that starts at α n , so action n is played initially, where the duration λT of that stage is chosen such that the final action at time T is action 1 2 log(n) . Specifically, we requireλα n + (1 -λ) • 0 = α ⌈ 1 2 log(n)⌉ , and so λ = 2 n 2 n -1 1 -1 √ n .We show that this free-fall strategy bounds the utilities of both players from below.Claim C.1. In an optimal free-fall contract, the utilities for both players are at least those obtained in the contract described above.For ease of presentation, the proof for this claim is deferred to the following subsection. It consists of three parts: first, we show that an optimal free-fall contract must start at α 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 2 log n. The intuition for this part of the proof is that as the principal continues to 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 is outweighed by the current average principal utility, which we show should occur at action Θ(log n) (since we know the principal can get an average utility of Θ(n) and the expected reward of action i is 2 i ). Lastly, we compare the utilities of both players in a free-fall strategy that begins at action n and ends at action 1 2 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 α i is increasing with i in our game, we conclude that the agent's utility in an optimal contract is at least 1 2 log n. 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 1 2 (1 + 1 2 log(n) ). To calculate the utility for the principal, we define t i to be the time when the agent switches from action i to action i -1. We know that the transition from action n to n -1 happens at time t n = λT , 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 t of the contract α n with weight λT and zero contract with weight t -λT . Therefore, the transition times from each action i are given by t i = λT αn αi . After time λT , the principal pays zero and extracts the full welfare from the agents actions, and so the overall utility for the principal is λT+ n i=⌈ 1 2 log(n)⌉ (t i-1 -t i )R i-1 .Claim C.2. The utility for the principal in the free-fall contract (α n , λ) is O(n).Proof. The utility from region i is λT+ n i=⌈ 1 2 log(n)⌉ (t i-1 -t i )R i-1 . The time intervals are (t i-1 -t i ) = λT α n 1 α i-1 - 1 α i = λT α n 2 i (2 i -2)(2 i -1).The utility for the principal from region i > 1 2 log(n) and large n is thus:λT α n 2 2i 2(2 i -2)(2 i -1)= Θ(1).Summing over n -1 2 log(n) such terms yields a utility of O(n).The above arguments hold similarly also for perturbed versions of this game. For example, shifting the rewards by arbitrary and independent values in the range [-1, 1], as well as re-scaling the reward parameter v, yielding a positive measure in the parameter space.C.1 Proof of Claim C.1Proof. We execute this proof in two parts. In the first part of the proof, we will show that any optimal dynamic (free fall) contract must begin at α n . In the second part of the proof, we show that an optimal dynamic (free fall) contract that begins at α n must end at α ⌈ 1 2 log n⌉ or higher, if n is sufficiently large. This is enough to imply the claim because if the optimal free fall contract stops at a higher action than 1 2 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 at α n . For the sake of contradiction, suppose that it instead begins at α i for some action i ∈ [1, n -1]. In particular, it begins with the segment(p 1 = α i R, τ 1 , a 1 = i) for some i ∈ [1, n -1].To achieve a contradiction, we will show that this dynamic contract is not optimal by producing a better dynamic contract.In particular, let us consider replacing this first segment with the following two segments: (α i+1 R, x ≜ αi αi+1 τ 1 , i + 1), (0, y ≜ 1 -αi αi+1 τ 1 , i) (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 (x, y).x + y = τ 1 ((x, y) is a time split)xα i+1 = τ 1 α i (At time τ 1 , the cumulative linear contract is still α i ) x = α i α i+1 τ 1 y = 1 - α i α i+1 τ 1By 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 are 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 (α i R, τ 1 , i) is just τ 1 since the contract problem is designed so that all indifference contracts α i result in one unit of utility to the principal.The exception is action one, which was adjusted to have 1 + O(ε) principal utility and therefore has cumulative principal utility τ 1 (1 + O(ε)).Next, we consider the cumulative principal utility of our two new segments (a i+1 R, x, i + 1) and (0, y, i). The first segment has (cumulative) principal utility equal to just x for the same reason as above (but now i + 1 cannot be the first action). The second segment has (cumulative) principal utility equal to y(R i+1 ) where R i+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.x + y(R i+1 ) = (x + y) + y(R i+1 -1) = τ 1 + y(2 i+1 -1)However, we can see from our choice of y that y > 0 and (2 i+1 -1) > 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 α n (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 α ⌈ 1 2 log n⌉ 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. As a first step, we observe that the objective function of the continuous setting, Util(π), 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 1 = α n R, τ 1 , a 1 = n) uses τ 1 = 1. We can also assume without loss of generality that the other segments {(p k = 0, τ k , a k = n -k + 1)} K k=2 begin and end at region boundaries, which is enough to work out their durations τ k based on when the average linear contract reaches a particular indifference point.τ k = α n α n-k+1 - α n α n-k+2 = 1 -2 -n 1 -2 -n+k-1 - 1 -2 -n 1 -2 -n+k-2 = [1 -2 -n ] 2 -n+k-1 -2 -n+k-2 (1 -2 -n+k-1 )(1 -2 -n+k-2 ) = [1 -2 -n ] 2 -n+k-2 (1 -2 -n+k-1 )(1 -2 -n+k-2 )Hence segment k ∈ [2, K] contributes the following (cumulative) principal utility.τ k u P (p k , a k ) = τ k 2 n-k+1 = 2 n-k+1 • 1 -2 -n 2 -n+k-2 (1 -2 -n+k-1 )(1 -2 -n+k-2 ) = 1 2 1 -2 -n 1 (1 -2 -n+k-1 )(1 -2 -n+k-2 )Let π K be the trajectory that uses K segments. We can compute its objective value to be the following.K ) = 1 + 1 2 [1 -2 -n ] K k=2 1 (1-2 -n+k-1 )(1-2 -n+k-2 ) (1 -2 -n )/(1 -2 -n+K-1 ) = (1 -2 -n+K-1 ) 1/(1 -2 -n ) + 1 2 K k=2 1 (1 -2 -n+k-1 )(1 -2 -n+k-2 )We can take the difference of two such expressions to decide whether π K+1 is better than π K . For n -1 2 log n ≤ K ≤ n -1:Util(π K+1 ) -Util(π K ) = (1 -2 -n+K ) 1/(1 -2 -n ) + 1 2 K+1 k=2 1 (1 -2 -n+k-1 )(1 -2 -n+k-2 ) -(1 -2 -n+K-1 ) 1/(1 -2 -n ) + 1 2 K k=2 1 (1 -2 -n+k-1 )(1 -2 -n+k-2 ) = (1 -2 -n+K ) 1 2 1 (1 -2 -n+K )(1 -2 -n+K-1 ) -2 -n+K-1 1/(1 -2 -n ) + 1 2 K k=2 1 (1 -2 -n+k-1 )(1 -2 -n+k-2 ) ≤ 1 2 1 (1 -2 -n+(n-1) )(1 -2 -n+(n-1)-1 ) -2 -n+(n-1 2 log n)-1    1 2 n-⌈ 1 2 log n⌉ k=2 1    = 1 2 1 (1/2)(3/4) - 1 2 √ n 1 2 (n - 1 2 log n -1)Since the positive term has magnitude O(1) and the negative term has magnitude O( √ n), this bound will always be negative when n is sufficiently large. Hence it is strictly not worth it to free fall below α ⌈ 1 2 log n⌉ , as desired. This completes the proof.Here we consider general contracts, and in Theorem D.1 generalize the result of Theorem 3.1 to families of one-dimensional (yet 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 αp for some α ≥ 0. We will consider a principal that is restricted to only play p-scaled contracts. In the continuous-time formulation of Section 2.2, this means that each contract p k must be p-scaled. We will let p k = α k p, and we will often abuse notation and write α k as shorthand for this contract (e.g., we will specify segments of the trajectory π in the form (α k , τ k , a k )). Recall that a free-fall contract denotes such a dynamic contract for the principal where α k = 0 for all k > 1.As with linear contracts, note that as α increases from 0, the contract αp incentivizes the agent to play an action in BR p (α) (which is unique except for at most n "breakpoint" values of α, where the agent is indifferent between two actions). This induces an ordering over the actions; we will relabel the actions so that actions 1 (the null action), 2, 3, . . . are incentivized for increasing values of α. Formally, if the agent has n actions, we have n "breakpoints"0 = α 0,1 < α 1,2 < α 2,3 < • • • < α n-1,n , where action i belongs to BR p (α) iff α ∈ [α i-1,i , α i,i+1 ] (with α n,n+1 = ∞).Our main result in this section is the following theorem, by which free-fall p-scaled contracts are optimal p-scaled dynamic contracts. Theorem D.1. Let π be any p-scaled dynamic contract. Then there exists a free-fall p-scaled contract π ′ where Util(π ′ ) ≥ Util(π).To prove Theorem D.1, 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.1, which has an essentially identical proof). Proof. Note that a k and a k+1 both must be best-responses to the average historical contract p k after segment k, which is a p-scaled contract with parameterLemma D.2. If π = {(α k , τ k , a k )} is a p-scaled dynamic contract, then ∀k, |a k -a k+1 | ≤ 1.α k = k k ′ =1 α k ′ τ k ′ / k i=1 τ k ′ .In other words, a k and a k+1 belong to BR p (α k ). Since BR p (α) is always of the form {i} or {i, i + 1} the conclusion follows. Now, recall that in Lemma B.2 we show that (for general contract problems) we can restrict our attention to trajectories where no two consecutive segments have the same agent best response (i.e., a k ̸ = a k+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 a p-scaled dynamic contract π ′ = {(α k , τ k , a k )} with the property that for all k, a k ̸ = a k+1 and a k ̸ = a k+2 , and that Util(π ′ ) ≥ Util(π).Proof. The fact that we can rewrite π into an equivalent contract where a k ̸ = a k+1 follows from the proof of Lemma B.2. Therefore, assume without loss of generality that π already has this form. We will show how to rewrite it into a new dynamic contract π ′ with the additional property that a k ̸ = a k+2 . We will induct on the number of segments in the path (it is obviously true when there is only K = 1 segment). Assume that for some k, π has the property that a k = a k+2 ̸ = a k+1 . This implies that BR p (α k ) = BR p (α k+1 ) = {a k , a k+1 }. Since there is a unique value of α for which BR p (α) = {a k , a k+1 } (namely, one of the breakpoints α i,i+1 ), this can only happen if α k = α k+1 , which in turn means that α k+1 = α k = α k+1 . Pictorially, this is because if a dynamic contract spends only one segment in a 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 π 1 , we replace the first k + 1 segments of π with a scaled up version of the (k + 1)st segment. That is, remove the first k + 1 segments of π and replace them with (α k+1 , T k+1 , a k+1 ). To see that this is a valid contract, note that since α k+1 = α k+1 , α k+1 incentivizes action a k+1 so the first segment of this contract is valid. Moreover, after T k+1 time units have elapsed, both π and π 1 resume the same sequence of segments from the same state α k+1 .2. In π 2 , we replace the first k +1 segments of π with a scaled up version of the first k segments. That is, remove the segment (α k+1 , τ k+1 , a k+1 ), and scale up τ k ′ (for each 1 ≤ k ′ ≤ k) to τ k ′ (T k+1 /T k ). Again, this is a valid dynamic contract because scaling up a (prefix of 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 . Finally, note that Util(π) is a convex combination of Util(π 1 ) and Util(π 2 ) -specifically, Util(π) = (τ k+1 π 1 + T k π 2 )/T k+1 -and so is less than or equal to one of them. But both π 1 and π 2 have strictly fewer segments than π, 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 k+1 = a k + 1) or consecutively decreasing (a k+1 = a k -1). We show that we can ignore the first case -such contracts can never be better than static contracts. Lemma D.4. Let π = {(α k , τ k , a k )} be a p-scaled dynamic contract where the a k are consecutively increasing. Then there exists a static p-scaled contract π ′ (i.e., a single segment dynamic contract of the form (α ′ , 1, a ′ )) where Util(π ′ ) ≥ Util(π).Proof. As in the proof of Lemma D.3, we will again induct on the number of segments of π. If π has one segment, we are done. Now consider a π with K segments, whose last segment is (α K , τ K , a K ). Recall that for any i, α i-1,i is the smallest value of α for which αp incentivizes action i. Note that if α K > α a K -1,a K , we can improve the utility of the principal by decreasing α K to α a K -1,a K (this pays strictly less to the agent but still incentivizes the same action a K ). We'll therefore assume the last segment is of the form (α a K -1,a K , τ K , a K ); note that this segment by itself is a valid static p-scaled contract, as α a K -1,a K incentivizes action a K . Call this contract π K . Let π ′ be the dynamic contract formed by the first K -1 segments of π (see Figure 7 for examples of π K and π ′ ). But now, Util(π) is a convex combination of Util(π ′ ) and Util(π K ), so it is at most the maximum of these two quantities. If this maximum is Util(π K ), we are done (π K is a static contract); if it is Util(π ′ ), we are also done by the inductive hypothesis (π ′ has K -1 segments).Finally, we show that in the case where the sequence of actions are consecutively decreasing, such a contract is no better than some free-fall contract. Lemma D.5. Let π = {(α k , τ k , a k )} be a p-scaled dynamic contract where the a k are consecutively decreasing. Then there exists a free-fall p-scaled contract π ′ where Util(π ′ ) ≥ Util(π).Proof. Assume that π is not a free-fall contract. We will show we can rewrite π in a way so that either the first agent action a 1 strictly decreases or the first non-free-fall occurs strictly later. Since the number of segments in π is bounded (by n, since the actions are consecutively decreasing), this implies the theorem statement.Let (α k , τ k , a k ) be the first segment in π with k ≥ 2 where α k > 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 k and a k+1 = a k -1,α k = α a k -1,a k .The main observation of this proof is that we can rewrite this segment as a combination of a free-fall segment (with α = 0) and a segment along the boundary of these two best-response regions (with (a) Base policy π with consecutively decreasing actions. The kth segment is the first non-free-fall segment: we form π ′ (the dashed trajectory) by decomposing this segment into a free-fall segment followed by a boundary segment. α = α k ). Specifically, form a new dynamic contract π ′ by replacing (α k , τ k , a k ) in π with the two consecutive segments (0, λτ k , a k ) and (α a k -1,a k , (1 -λ)τ k , a k ), where λ is chosen so that (1 -λ)α a k -1,a k = α k . Note that by doing this π ′ now has K + 1 segments, where segments k and k + 1 are this new free-fall and boundary segment respectively. Note that we will let quantities like τ k , T k , and α k still refer to the relevant quantities for π, not π ′ . This allows us to proceed via a similar technique as in Lemma D.3. Consider the following two modifications of π ′ (see Figure 8 for examples):1. In π 1 , we replace the first k + 1 segments of π ′ with a scaled-up version of the boundary segment of the form (α k , T k , a k ).2. In π 2 , we replace the first k + 1 segments of π ′ with a scaled up version of the first k segments (the first k -1 segments of π and the free-fall segment, but not the boundary segment). Specifically, let C = T k /(T k-1 + λτ k ). Then the first k -1 segments of π 2 are of the form (α k ′ , Cτ k ′ , a k ′ ), and the kth segment of π 2 is of the form (0, Cλτ k , a k ).As in the proof of Lemma D.3, we can check that both π 1 and π 2 are valid dynamic contracts: in particular, after T k units of time, they are both in the state α k , so the remaining suffix of π is a valid extension for both contracts.Again, Util(π) can be written as a convex combination of Util(π 1 ) and Util(π 2 ), specifically,Util(π) = (1 -λ)τ k Util(π 1 ) + (T k-1 + λτ k )Util(π 2 ) T k .But π 1 starts at a later action than π (since a k = a 1 -(k -1)), and π 2 is a free-fall contract for one further step than π (sinceα 2 = α 3 = • • • = α k-1 = 0, and the kth segment in π 2 also has α = 0). This completes the proof.We can now conclude the proof of Theorem D.1.Proof of Theorem D.1. Because of Lemmas D.2 and D.3, we can assume without loss of generality that the actions a k in π are either consecutively increasing or decreasing. The conclusion now immediately follows from Lemmas D.4 and D.5.Proof. Due to Theorem H.3, it suffices to show that there exists some γ such that U ⋆ γ < (1 + ε)R ⋆ . This lets us focus on the continuous-time setting. The high-level plan from here is to focus on a particular continuous trajectory π = (p k , τ k , a k k apply a potential argument to it. We will then show our analysis extends to distributions D for free. We will define a potential function ψ(α) that maps time-averaged linear contracts α to potentials in R ≥0 . This potential is based only on the principal-agent problem (c, F, r). There are some peculiarities about our potential argument, relating to the passage of time. Consider a principal managing to produce a time-averaged linear contract of α after t units of time, and compare that with a principal that has managed to arrive a time-averaged linear contract of α after 2t 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 as good to be in the latter situation. With this in mind, our proof will carefully distinguish between the raw potential ψ(α) and the time-weighted potential ψ(α) • t. If a 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 time-weighted potential is to model the ability of a principal to extract additional profit by gradually lowering time-averaged linear contract. It will be used to demonstrate that this extra profit produced by using up a finite resource, which will imply the desired theorem result.We now give our raw potential function ψ(α). We begin by writing down the linear contract breakpoints of (c, F, r); without loss of generality 11 they are 0 < α 2 < α 3 < • • • < α n , where the linear contract α i leaves the agent indifferent between actions i -1 and i. For notational convenience, we also define an α 1 ≜ 0 as the minimum linear contract to incentivize the first action. We also denote the expected reward of action i with R i . With this notation in place, our raw potential function ψ : [0, α n ] → R ≥0 is the following piecewise-linear function. Note that we can assume without loss of generality that the average linear contract never exceeds α n , because capping it to this quantity only improves principal utility at all moments in time.ψ(α) ≜ i ′ -1 i=1 (α i+1 -α i )R i + (α -α i ′ )R i ′ if α ∈ [α i ′ , α i ′ +1 ) n-1 i=1 (α i+1 -α i )R i if α = α nThe 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 P )? In our continuous-time setting, this gives the principal the ability to produce segments of play (p k , τ k , a k ) which have near-instantaneous times τ k → 0 while using large-magnitude cumulative contracts p k τ k to move between the boundaries between actions. If these near-instantaneous actions are used at time t, then the time-weighted potential ψ(α) • t 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 α i to the next α i+1 , namely [ψ(α i+1 ) -ψ(α i )] t, is equal to the payout received for near-instantaneously using a negative contract to move down from α i+1 to α i . 11 Implicitly, this step prunes away all actions which cannot be incentivized by a linear contract.Potential function in hand, we return to the original problem where payments are bounded and nonnegative. Let us consider the k th segment of play (p k = α k R, τ k , a k ) and relate the total profit generated during this segment of play with the change in potential.For notational convenience we define shorthand for the cumulative linear contract offered.A k ≜ k k ′ =1 τ k ′ α kWe will also use u k P to denote the (time-weighted) principal utility for segment k and u k ⋆ to denote the corresponding amount of principal utility that the optimal static contract obtains over τ k 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 k P = (1 -α k )R a k τ k u k ⋆ = max a (1 -α a )R a τ k ≥ [(1 -α a k )R a k ] τ k (u k p -u k ⋆ ) ≤ (α a k -α k )R a k τ kAt the same time, this contract has shifted the time-averaged linear contract and hence altered the time-weighted potential.ψ A k /T k T k -ψ A k-1 /T k-1 T k-1 =   α k i=1 (α i -α i-1 )R i-1 + A k /T k -α a k R a k   T k -   α k i=1 (α i -α i-1 )R i-1 + A k-1 /T k-1 -α a k R a k   T k-1 =   T k α k i=1 (α i -α i-1 )R i-1 + A k -T k α a k R a k   -   T k-1 α k i=1 (α i -α i-1 )R i-1 + A k-1 -T k-1 α a k R a k   = τ k α k i=1 (α i -α i-1 )R i-1 + α k τ k -τ k α a k R a kInterestingly, the expression for time-weighted potential has a term that perfectly cancels with our bound for how much additional principal utility this segment produces over the optimal static contract.(u k p -u k ⋆ ) + ψ A k /T k T k -ψ A k-1 /T k-1 T k-1 ≤ τ k α k i=1 (α i -α i-1 )R i-1 ≤ T k T k-1 ψ A k-1 + (T -T k-1 )α k T dTThe right-hand side expression above is just the integral of the current raw potential as this segment advances the time from T k-1 to T k . Conveniently, this upper bound still works out to the same amount even if we subdivide our segment (p k , τ k , a k ) into two sub-segments (p k , x, a k ), (p k , y, a k ) such that x, y ∈ [0, τ k ] and x + y = τ k (and re-index the other segments appropriately). This means we can sum this bound to get an overall bound for any time t ∈ [0, T ], just by splitting the last segment appropriately. To formalize this, we introduce some more parenthetical superscript notation to denote the corresponding objects when considering time from zero to t. In particular, u⋆ denotes the optimal static contract's principal utility for t units of time, A (t) denotes the cumulative linear contract for t units of time.(u (t) p (π) -u (t) ⋆ ) + ψ A (t) /t t ≤ t 0 ψ A (T ) T dTRecall our notation where R ⋆ denotes the optimal static contract's principal utility. For t ∈ [T , T ], we know that the excess principal utility needs to be at least εR ⋆ t, which implies the following.εR ⋆ t + ψ A (t) /t t ≤ t 0 ψ A (T ) T dT ψ A (t) /t ≤ -εR ⋆ + 1 t t 0 ψ A (T ) T dTWith this bound in mind, we can view every trajectory π that manages to successfully beat the optimal static contract by (1 + ε) in terms of how much raw potential it has as a function of time. Note that this bound controls the current raw potential based on the average raw potential up to this point (minus a constant). As a result, if we just consider trajectories π that obey this bound, the worst case for us would be a function that satisfies it 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.εR ⋆ t + f (t)t = t 0 f (T )dT εR ⋆ + f (t) + f ′ (t)t = f (t) f ′ (t) = -εR ⋆ /tAt time T , we know the raw potential can be at most ψ(α n ). We want to choose γ and hence T so that f (T ) is negative in order to create a 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 γ that does not actually create a contradiction.f (T ) -f (T ) = -ψ(α n ) T T f ′ (t)dt = -ψ(α n ) -εR ⋆ [ln t] T T = -ψ(α n ) ln(T /T ) = ψ(α n ) εR ⋆ γ = e ϕ(αn)/(εR⋆)Hence it suffices to pick a γ > e ϕ(αn)/(εR⋆) . This demonstrates that it is impossible for a deterministic trajectory π to beat the optimal static contract by a (1 + ε) multiplicative factor.What about randomized dynamic contracts D? We can just take the appropriate convex combination of our bounds according to drawing π ∼ D. In particular, this yields:E π∼D (u (t) p (π) -u (t) ⋆ ) + E π∼D ψ A (t) /t t ≤ t 0 E π∼D ψ A (T ) T dTWe can then re-execute the remainder of the proof in 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 f (T ) and we reach the same conclusions about γ. This completes the proof.Remark. Due to Yao's minimax principle, Theorem 4.2 implies that there exists an adversarial distribution over times in [T , T ] such that for any randomized principal strategy, the ratio between expected principal utility and the principal utility of the optimal static contract for that duration of time is strictly less than (1 + ε). In order to apply Yao'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 ε-net since principal utility is Lipschitz with Lipschitz constant depending on the contract problem, and after that the former then follows from Carathéodory's Theorem by treating each deterministic trajectory as a vector with one coordinate for every point in our ε-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 + ϵ)u ⋆ T for some ϵ > 0. By Theorem 3.1, we can assume without loss of generality that this is a free-fall linear contract. We will show that for any γ we will construct a dynamic contract such that for all T ∈ R and all t ∈ [T , γ • T ], we can achieve an expected utility of(1 + f (ϵ, γ)) • u ⋆ • t where f (ϵ, γ) ≥ Ω min ( ε 4 ) O(log(1+γ)) , ε γ .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 to 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 a 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, we will lose a constant factor which is folded into our Ω notation.Case A: Dynamic contracts beginning above α ⋆ and ending below α ⋆ . We write our freefall linear contract in the usual form π = {(p k , τ k , a k )} K k=1 . By virtue of being in this case, we know there is some index 2 ≤ i < K such that the average linear contract after i segments, p i , is exactly α ⋆ . We "cut" the trajectory π at this point to produce two new trajectories π ′ and π ′′ . Specifically,π ′ = {(p k , τ k , a k } i k=1 and π ′′ = {(α ⋆ , T i , a i )} • {(p k , τ k , a k } K k=i+1where • denotes concatenation. In other words, we construct π ′ by ending at this point and we construct π ′′ by taking the optimal static contract to this point and continuing as normal. Observe that the combined performance of π ′ and π ′′ is equal to the combined performance of π and just playing the single segment {(α ⋆ , T i , a i )}: (1+ϵ)u ⋆ T K +u ⋆ T i . This results in a combined time-averaged performance of(1 + ϵ)u ⋆ T K + u ⋆ T i T K + T i = u ⋆ (1 + ϵ) T K T K + T i + (1) T i T K + T i ≥ (1 + ϵ/2)u ⋆ since T K ≥ T i .Since π ′ and π ′′ 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 a constant. Since π ′ matches case (1) and π ′′ matches case (2), this completes the analysis of case (a).Case B: Dynamic contracts beginning and ending below α ⋆ . We take the obvious approach and choose to begin at α ⋆ instead. Specifically, we replace the first segment with a sequence of segments that begins at α ⋆ 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 is similar to before. The first new segment just hovers at 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 we originally began with, and expected revenue is at least the principal utility 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 now consider.Case 1: Dynamic contracts ending at or above α ⋆ . First, we consider the case where for any fixed T there is a dynamic contract π(T ) = ((α 1 , τ 1 , a 1 ), . . . , (α k , τ k , a k )) which ends at or above the optimal static action: a k ≥ a ⋆ . Given any γ and time period [T , T = γ • T ], consider the dynamic contract which starts with π(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 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 t ∈ [T , T ] for the principal is(1 + ϵ) • u ⋆ T + (t -T ) • u ⋆ , which is at least (1 + ϵ /γ)R ⋆ t.Case 2: Dynamic contracts starting in α ⋆ . By Theorem 3.1, we know any dynamic contract can be transformed into a free-fall dynamic contract with no loss in revenue. Therefore, we assume that for any fixed time horizon T , there is a dynamic contract form π(T ) = α ⋆ , τ 1 , a 1 ), (0, τ 2 , a 2 ), . . . , (0, τ k , a k ) which achieves a total revenue of (1 + ε)R ⋆ T . Since this is a free-fall contract, the optimal revenue from this contract can be characterized as(1 -α ⋆ )R ⋆ τ 1 + k i=2 τ i R ai which is at least (1 + ε)R ⋆ t > (1 + ε)(1 -α ⋆ )R ⋆ .Let µ be the minimum fraction of time such that for any time T , the dynamic contract π(T ) achieves revenue at least (1 + ε/2)µu ⋆ T . Since we know that π(T ) achieves a total revenue of (1 + ε)u ⋆ T and starts out at the optimal static contract, we know that µ ≥ τ 1 / k i=1 τ i and it is a constant bounded away from 1. Let S i = ⌈µ i T ⌉ and let p be the first index where S p is less than T (i.e., p = ⌈ log(1+γ) log(µ) ⌉) . By construction, S i satisfy two properties:1. S p ≤ T ≤ S p-1 ≤ . . . S 1 ≤ T .2. If the principal runs dynamic contract ending at S i , namely π(S i ), then they are guaranteed revenue (1 + ε /2)tR ⋆ for any t ∈ [S i+1 , S i ].We will construct a sequence of dynamic contracts π i which have the property that for any t ∈ [S i , γT ] achieves revenue that is at least (1 + ( ε /4) i )R ⋆ t. We do this via induction. For the base case, let π 1 = π(T ). By construction, we know that for all t ∈ [S 1 , T ], the principal will get revenue (1 + ε /2)u ⋆ t. Now suppose we have such a dynamic contract π i , then we construct π i+1 by taking a convex combination of π i and the optimal dynamic contract ending at π(S i ). In particular, letπ i+1 = 1 + ε /2 1 + ε /2 + ( ε /4) i π i + ( ε /4) i 1 + ε + ( ε /4) i π(S i ).For any t ∈ [S i , T ], we have that revenue we attain is at least the revenue from the contract1 + ε /2 1 + ε /2 + ( ε /4) i Revenue(π i (t)) ≥ 1 + ε /2 1 + ε /2 + ( ε /4) i (1 + ( ε /4) i )u ⋆ t ≥ 1 + ε i+1 /2•4 i 1 + ε /2 + ( ε /4) i ≥ (1 + ( ε /4) i+1 )u ⋆ t.For any t ∈ [S i+1 , S i ], observe that we get at least u ⋆ t from the first contract π i and at least (1 + ε /2)u ⋆ t in the second contract. Therefore we get at least1 + ε /2 1 + ε /2 + ( ε /4) i u ⋆ t + ( ε /4) i 1 + ε /2 + ( ε /4) i (1 + ( ε /2))u ⋆ t ≥ (1 + ( ε /4) i )u ⋆ t.In this section, we give a general contract instance with n = 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 as follows:• The cost vector c = (c 1 , c 2 , c 3 , c 4 ) = (0, 0.2, 0.4, 0.5).• The reward vector r = (r 1 , r 2 , r 3 ) = (0, 1.0, 1.6, 2.0).• The forecast matrix is given by F =    1.00 0.00 0.00 0.00 0.45 0.20 0.25 0.10 0.35 0.05 0.25 0.35 0.15 0.30 0.30 0.25This 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 of at most 0.753 per round. At the same time, we can exhibit a non-free-fall dynamic contract for this instance that achieves a utility of at least 0.764 per round. For conciseness, we present the details of our approach in Appendix G.1, where we construct well-tailored linear programs that provide the aforementioned intricate instance.G.1 Programmatic LP Search for Sub-Optimal Free Fall Against Non-Linear Contracts At a high level, the verification of the example of section 3.3 relies on the following fact: given a sequence of actions (a 1 , a 2 , . . . , a K ), we can construct a polynomial-sized linear program to find the optimal continuous-time dynamic (general or free-fall) contract {(p k , τ k , a k )} K k=1 with this specific action sequence.The variables of this LP are the τ k and p k corresponding to each action a k . The constraints follow from the definition of a valid trajectory of play in Section 2.2 and are as follows:• (Non-negativity) p k , τ k ≥ 0.• (Time normalization) K k=1 τ k = 1. We normalize the total duration of the trajectory to 1.• (Beginning of segment is best response)k-1 k ′ =1 τ k ′ u L p k ′ , a k ≥ k-1 k ′ =1 τ k ′ u L p k ′ , a ′ for any a ′ ∈ [n]. This represents the constraint a k ∈ BR(p k-1 ).• (End of segment is best response)k k ′ =1 τ k ′ u L p k ′ , a k ≥ k k ′ =1 τ k ′ u L p k ′ , a ′ for any a ′ ∈ [n]. This represents the constraint a k ∈ BR(p k ).The objective of the LP is the optimizer utility K k=1 τ k u O (p k , a k ). If we want to further impose that the contract is a free-fall contract, we can add the constraint that p k = 0 for k > 1.For free-fall contracts, we have an additional constraint on what sequences of actions are possible. Note that a free-fall contract will never repeat an action -in particular, after the initial segment, the cumulative utility of each action i ∈ [n] decreases by c i per round, so the sequence of actions (a 1 , a 2 , . . . , a K ) a free-fall contract passes through must be sorted in decreasing order of cost. This means there are at most 2 n sequences of actions to check, and by checking all of them we can provably compute the optimal free-fall contract for a given general contract instance.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 -it is an interesting open question whether there exists any efficient (or even computable) algorithm for computing U ⋆ for a general contract instance. Luckily, in order to 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.Util 0 (π 0 ) ≥ k i=1 u P (p i , a i )τ i 1 + ∆ k ≥ (1 -ε)Util(π)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 π = {(p k , τ k , a k )} K k=1 represent a valid strategy for the principal in the continuous-time problem. Without loss of generality, assume k τ k = 1 (if not, we can divide all τ k through by k τ k without changing the value of this strategy). We will convert π into the following discrete-time strategy for the principal: for each i ∈ [K] (in order), the principal offers the contract p k for τ k T rounds.Our goal is to show that for any δ > 0 and any mean-based algorithm A, the above strategy results in at least (Util 0 (π) -δ)T -o(T ) utility for the optimizer. The conclusion then follows by choosing a trajectory π for which Util 0 (π) > U ⋆ -ε/2 (such a π exists by Lemma H.1 and the definition of U ⋆ ) and some δ < ε/2. In the remainder of this proof, we will fix a specific mean-based algorithm A that is γ(T )-mean-based for some γ(T ) = o(1).As in Definition 2.2, let σ i,t denote the aggregate utility of action i to the agent over the first t rounds. Let T k = k j=1 τ j T , and consider the values of σ t for rounds t ∈ [T k-1 , T k ] corresponding to the kth segment. Note that σ t is linear in this interval and so we can interpolateEQUATIONFurthermore, assume that segment k is non-degenerate, and so BR(p k-1 ) ∩ BR(p k ) = {a k }. In particular, for any t ∈ [T k-1 , T k ] and a ′ ̸ = a k , eitherσ T k-1 ,a k > σ T k-1 ,a ′ or σ T k ,a k > σ T k ,a ′ .As a consequence of (1), this means that for any ε k > 0, there exists a δ k > 0 such that fort ∈ [T k-1 + ε k τ k , T k -ε k τ k ], σ t,a k ≥ σ t,a ′ + δ k T .For sufficiently large T , δ k T > γ(T )T , and so the learner will put weight at least (1 -nγ(T )) on action a k . The total utility of the principal from these rounds is therefore at leastEQUATIONSumming over all non-degenerate segments k, we find the total utility of the principal is at leastk τ k u P (p k , a k ) - k k(nγ(T ) + 2ε k )T = Util 0 (π) - k k(nγ(T ) + 2ε k )T.By choosing ε k sufficiently small, we can guarantee that this is at least Util 0 (π) -δT for sufficiently large T , as desired.Part 2. Fix any ε > 0. Assume that for some sufficiently large T 0 , there exists a (possibly adaptive) dynamic strategy for the principal that guarantees utility at least (U ⋆ + ε)T 0 against every mean-based agent. We will show that this implies the existence of a continuous trajectory π and Util(π) ≥ U ⋆ + ε, contradicting the definition of U ⋆ . Fix γ(T ) = T -1/2 and at any time t, let J t = {j ∈ [n]|(max i σ t,i ) -σ t,j < γ(T )T } be the set of actions for the learner whose historical performance are within γ(T )T of the optimally performing action. The set J t contains exactly the set of actions that the 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 t , the agent will play the action j ∈ J t that minimizes u L (p t , 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 1 , p 2 , . . . , p T0 . Consider the trajectory π defined by the sequence of tuples (p 1 , 1/T 0 ), (p 2 , 1/T 0 ), . . . , (p T0 , 1/T 0 ). In this 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 a valid trajectory. Now, note that the sub-segments corresponding to the step (p t , 1/T 0 ) only contain agent actions in the set J t . This is since the agent utility at the start of this segment is σ t , the agent utility at the end of this segment is σ t+1 , each component of σ t+1 -σ t is at most 1 (since the problem is bounded), but any action j not in J t is at least γ(T ) away from optimal. The principal's utility contributed by this segment is therefore at least 1 T0 min j∈Jt u P (p t , j). But this is exactly the utility the principal obtained in round t of the discrete-time game. Therefore the total utility Util(π) of this trajectory is at least U ⋆ + ε -but this contradicts the definition of U ⋆ , as desired.We will need the following lemma which says we can restrict our attention to finite-support D without loss of generality. Lemma H.2. Fix a principal-agent problem, a γ > 1, and an ε > 0. Let D be any distribution over trajectories. Then there exists a finite-support distribution D ′ over trajectories with the property that Util γ (D ′ ) ≥ Util γ (D).Proof. We first claim the following: if a distribution D has the property that E π∼D [u (t) P (π)] ≥ U t for each t in the discretized set of time-intervals S ε,γ = {1/γ, 1/γ + ε/γ, 1/γ + 2ε/γ, . . . , 1 -ε/γ, 1}, then it is the case that E π∼D [u (t)P (π)] ≥ (U -ε)t for all t ∈ [1/γ, 1]. This follows from the fact that the principal's profit per round is bounded above by 1, so |u(t ′ ) P (π) -u (t) P (π)| ≤ |t ′ -t|. In particular, if t ′ is the closest element of S γ,ε to a t ∈ [1/γ, 1], it is the case that |u (t ′ ) P (π) -u (t) P (π)| ≤ ε/γ ≤ εt. Now, associate to each trajectory π the |S ε,γ |-tuple of real numbers f (π) = {u (t) P (π)} t∈Sε,γ ; define f (D) = E π∼D [f (π)]. Define X = {f (π) | π is a trajectory} ⊂ R |S|to be the set of all such tuples. By Caratheodory's theorem, we can construct a distribution over at most |S| + 1 elements of X that (is arbitrarily close to) f (D), for any D. If we let D ′ be the corresponding distribution over trajectories, this satisfies the constraints of the theorem statement.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 γ ≥ 1 which equals the multiplicative ratio (T /T ). Instead of a trajectory π = {(p k , τ k , a k } K k=1 being solely evaluated at its end time T K , we now care about its performance over its final interval of multiplicative width γ, namely[ 1 γ T K , T K ].In order to quantify the performance of a trajectory at a certain time t, we will introduce some corresponding parenthetical superscript notation. In particular, uP (π) will denote the cumulative expected principal utility of trajectory π from time zero to t, and is formally defined asu (t) P (π) ≜ k ′ -1 k=1 τ k u P (p k , a k ) + (t -T k ′ )u P (p k ′ , a k ′ ) if t ∈ [T k ′ , T k ′ +1 ) k ′ -1 k=1 τ k u P (p k , a k ) if t = T K .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 byUtil γ (D) = min x∈[1/γ,1] E π∼D u (xT K ) P (π) xT K ,where each T K is according to the drawn trajectory π.Finally, let U ⋆ γ = sup D Util γ (D), 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.Theorem H.3. Fix any principal-agent problem and γ ≥ 1. We have the following two results:1. For any ε > 0, there exists an oblivious strategy for the principal that gets at least (U ⋆ γε)t -o(t) utility for the principal for all t ∈ [T, ⌈γT ⌉] for sufficiently large T .2. For any ε > 0, there exists a mean-based algorithm A such that no (even adaptive 13 ) principal can get more than (U ⋆ γ + ε)t + o(t) utility against an agent running A for all t ∈ [T, ⌈γT ⌉] for any T .Proof of Theorem H.3. Part 1. Begin by picking a strategy D for the optimizer in the continuoustime game that achieves utility at least U ⋆ γ -ε/2. This strategy D is a distribution over trajectories π; by Lemma H.2, we can assume (at the cost of losing an arbitrarily small O(ε) term) that D has finite support. For each of these trajectories, we apply Lemma H.1 to transform π into a new trajectory π ′ which obtains at least (1 -ε) fraction of the utility of π on non-degenerate segments. We will also normalize the total duration of each π ′ to 1. Now, note that since inequality (2) holds per segment (and indeed, even fractionally per segment), we can convert each resulting trajectory π ′ to a discrete-time strategy over T with the property that for sufficiently large values of T , for any t ∈ [T = T /γ, T ], the utility of this discrete-time strategy until time t is at least u (t) P (π). 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 ε > 0, assume to the contrary there exists a T 0 along with a discrete-time (possibly randomized / adaptive) dynamic strategy which achieves at least (U ⋆ γ + ε)t utility for the principal for all t ∈ [T 0 /γ, T 0 ] 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 contracts (p 1 , p 2 , . . . , p T0 ). Each such sequence can be converted to a trajectory π of the form {(p 1 , 1/T 0 ), (p 2 , 1/T 0 ), . . . , (p T0 , 1/T 0 )}. This trajectory π not only has the property that Util(π)T upper bounds the utility of the discrete-time agent (as in the proof of part 2 of Theorem 2.4), but in fact u (t) P (π) is at least the utility of the agent discrete-time agent at time tT 0 (by exactly the same logic). It follows that if we let D be the distribution over such trajectories, it is the case that Util γ (D) ≥ U ⋆ γ + ε. This contradicts the definition of U ⋆ γ , as desired.Finally, we conclude this supplementary section with the proof of a preliminary lemma exploited in Section 3.1Lemma H.4. (Restated Lemma B.2) Consider any dynamic contract. For any time interval in which a mean-based agent plays a single action, we can replace the contracts in this interval with their average and obtain overall a revenue-equivalent dynamic contract.Proof. The result follows since the utility for the principal u P is affine in its first argument. Formally, let π = {(p k , τ k , a k )} K k=1 be a dynamic contract, with a k = a k+1 = a for some k. Consider a different contract π ′ where we replace the consecutive pair of segments (p k , τ k , a k ) and (p k+1 , τ k+1 , a k+1 ) with the their average segment, i.e., (p, τ k + τ k+1 , a), where p = (p k τ k + p k+1 τ k+1 )/(τ k + τ k+1 ), and all other segments remain the same as in π. Then,we have Util(π ′ ) -Util(π) = 1 K k=1 τ k τ k u P (p k , a) + τ k+1 u P (p k+1 , a) -(τ k + τ k+1 )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.We conclude with some clarifying remarks on the definition of a mean-based learning algorithm in a 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 σ t i = t-1 t ′ =1 u t ′ i is equal to the expected utility the learner would receive if they had played action i for the first t -1 rounds, assuming the sequence of contracts the principal offers the learner remains static (so in particular, for an adaptive / stochastic principal, σ t is a random variable). Definition H.5. (Mean-based algorithms in partial-information settings) A learning algorithm in a partial-information setting is γ(T )-mean-based if the following conditions hold: Fix any adaptive dynamic strategy of the principal and let (for each round t ∈ [T ]), X t be the event that σ t i < σ t i ′ -γ(T ) • T , and Y t be the event that the algorithm takes action i in round t. Then the algorithm is mean based if the probability Pr[X t ∧ Y t ] (over all randomness in the learner's algorithm, principal's strategy, and problem setting) is at most γ(T ). We say an algorithm is mean-based if it is γ(T )-meanbased for some γ(T ) = o(1).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 t deterministically implies that the probability of Y t 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 t holds; but in the partial-information setting, there is always a chance that the learner is unable to accurately observe whether X t holds, and therefore no partial-information algorithm can achieve that guarantee. On the other hand, standard bandit algorithms with high-probability guarantees such as EXP3 (see [17] ) 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 to show a principal cannot do well against all mean-based agents, we design a mean-based agent that foils this specific principal. If the principal is randomized and adaptive, the agent cannot accurately predict the expected contract p t the principal will play in round t (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 t at any round). The proof of Theorem H.3 is similar.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 I.1. In the fixed contract setting, for any regret-minimizing agent in the limit T → ∞ the support of the average empirical distribution of play includes only best-response actions with probability one. Therefore, the repeated game with a static contract against a regret-minimizing agent is essentially equivalent to the single-shot game against a rational agent.Proof. This follows directly from the regret-minimization property. Indeed, suppose, for the sake of contradiction, that there exists an action a in the support which is not a best response. Denote the best-response utility by OP T . Action a is played with probability p > 0. 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 ≥ p(OP T -u(a))T = O(T ), a contradiction. Observation I.2. If the agent is using a no-swap-regret 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 noswap-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.Below we show that in our analysis of dynamic linear contracts, it suffices to only examine linear contracts with α ∈ [0, 1]. Note that although this is obvious in the static setting (offering α > 1 requires the principal to suffer negative utility), it is not a priori clear that the principal cannot benefit via a dynamic strategy which offers a contract with α > 1 for some fraction of the time horizon (perhaps counterbalancing it by offering a 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 π = {(α k , τ k , a k ) K k=1 } be any linear dynamic contract with some linear contract α i > 1. Then there exists a dynamic linear contract π ′ = {(α k , τ k , a k )} K k=1 with Util(π ′ ) ≥ Util(π) and where α k ≤ 1 for all k.Proof. We first observe that in Lemma B.3, when an agent is indifferent between actions i and i + 1 then the change in utility for the principal by choosing an action i + 1 over i is proportional to (1 -α i ). This is negative if α i > 1 and therefore the principal will prefer to agent to play action i when α i > 1. However if α i < 1 , then the principal will prefer that the agent play action i + 1. Thus in this modified rewriting lemma, contracts with breakpoints greater than 1, 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 a new linear contract π ′ with a breakpoints that are at most 1, without any loss in utility.The non-negativity 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-breaking 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 a there is a linear contract α which uniquely incentivizes it (otherwise when focusing on linear contracts we may omit this action from the setting).InSection 4 we consider what happens when T 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 T .Some small changes need to be made to this definition for the partial-feedback (bandits) setting -see Definition H.5 in Appendix H.3.This is a non-trivial consequence of our proof machinery. The proof appears as Observation I.3 in Appendix I for completeness.In the partial-feedback (bandit) setting, this result only holds for deterministic adaptive principals and not for randomized adaptive principals (with full-feedback, it holds for either); see Appendix H.3 for further discussion.In fact, for mean-based algorithms there is a stricter characterization of the set of equilibria to which they may converge[53], but the above explanation still holds.In 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.The code verifying this example can be found at: https://colab.sandbox.google.com/gist/ jschnei/4d067ac2892d6b7c215dcea909577c53/optimal-dynamic-contracts-minimal-example. ipynbAs with the known time-horizon result, this holds against adaptive principals in the full-feedback setting, or if the principal is deterministic. See Appendix H.3 for details. 


Decision: 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.

Reviews: review: paper_summary: paper_summary: This work studies the problem of contracting with a no-regret learning agent. They show that

- In linear contracts, the optimal dynamic contract against a mean-based learning agent is a free-fall contract.
- dynamic contracts can be win-win. Both principal and agent can benefit from some dynamic contractor and mean-based learning agent.
- 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.
strength_weakness: strength_weakness: If I have to say some weaknesses of this work, I would say most results seem to be instance-dependent but not general.
questions: 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?

- 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.

- 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Please address my concern in the above section if possible.
limitations: limitations: n/a
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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.
questions: questions: None.
limitations: limitations: None.
paper_summary: paper_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:

For 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.
There exist settings where both principal and agent benefit from the optimal dynamic contract compared to the best static contract.
With uncertainty about the time horizon, the principal's ability to outperform static contracts degrades as the uncertainty increases.
strength_weakness: strength_weakness: Limited to mean-based learning agents;
Optimal contracts for fully general (non-linear) settings not analyzed
questions: questions: 1. Are there natural economic settings where the "win-win" dynamic contracts might arise in practice?
2. Do you expect qualitatively similar results for multiple interacting agents? What are the key challenges there?
3. 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?
4. 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?
5. Are there any interesting implications of your results for the design of real-world incentive structures, such as employee compensation plans or insurance contracts?
6. 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?
7. The paper mentions potential extensions to MDPs. How do you envision applying these ideas to more complex sequential decision-making settings?
limitations: limitations: Yes

Comments: title: Thanks for the response
comment: Thanks for your response! I will keep my score unchanged.
Thanks for your response! I will keep my score unchanged.
Thanks for the response. I would keep my score for accepting this paper.
Thanks for your response. I will keep my positive score.