acceptodds
Under review as a conference paper at ICLR 2027

Contracting With a Reinforcement Learning Agent by Playing Trick or Treat

Abstract

We study *principal-agent* problems where a *farsighted* agent takes costly actions in an MDP. The core challenge in these settings is that agent's actions are *hidden* to the principal, who can only observe their outcomes, namely state transitions and their associated rewards. Thus, the principal's goal is to devise a policy that incentives the agent to take actions leading to desirable outcomes, by committing to a payment scheme (a.k.a. *contract*) at each step. Interestingly, we show that Markovian policies are unfit in these settings, as they do not allow to achieve the optimal principal's utility and are constitutionally intractable. Thus, accounting for history in unavoidable, and this begets considerable additional challenges compared to standard MDPs. Nevertheless, we design an efficient algorithm to compute an approximately optimal policy, leveraging a compact way of representing histories for this purpose. Unfortunately, this policy incentivizes the agent to take the desired actions only approximately. To fix this, we design an efficient method to make such a policy incentive compatible, by only introducing a negligible loss in principal's utility, generalizing an existing technique for classical principal-agent problems.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
algorithmic game theory, contract design

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_LKd1OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies dynamic contract design for a farsighted agent taking costly hidden actions in a finite-horizon MDP. The principal commits to a history-dependent policy specifying outcome-contingent payments and action recommendations. The paper shows that Markovian policies can be suboptimal and that approximating the best Markovian policy is NP-hard. It then uses promised continuation utility to represent history-dependent policies and develops a dynamic program over discretized promises. Finally, it adapts a payment-interpolation technique to convert an approximately incentive-compatible policy into an exactly incentive-compatible one with a bounded loss in the principal's utility. Together, these results yield a polynomial-time algorithm for computing an approximately optimal, incentive-compatible history-dependent policy.

Critical strengths
  1. Thorough mathematical development. The paper provides a substantial theoretical treatment of dynamic hidden-action contracting, with detailed arguments covering policy representation, approximation, and incentive-compatibility restoration.

  2. Complete theoretical result. The paper connects its structural results to a constructive approximation algorithm. In particular, the final guarantee combines a compact policy representation, polynomial-time computation, approximate optimality, and exact incentive compatibility.

Critical weaknesses
  1. Limited conceptual and technical advance over existing approaches. My main concern is the limited additional understanding provided by the paper. The usefulness of history-dependent policies in dynamic principal-agent problems is already established in closely related work. In particular, Bernasconi et al. [1] demonstrate the limitations of Markovian policies and develop the promise-based representation and utility-discretization framework for farsighted persuasion. Against this background, extending the approach to dynamic contracting is a natural direction, and discretizing continuation utility to obtain a tractable dynamic program is a natural approximation strategy.

    The approximate-to-exact IC conversion is potentially the most distinctive component, but it also uses the existing payment-interpolation technique of Dütting et al. [2]. Appendix E requires additional arguments to implement the transformation within a compact dynamic policy and to reconstruct honest promises; however, its central payoff comparison closely follows the existing one-shot argument. These extensions constitute mathematical work, but I find their technical increment limited. Overall, the paper does not make sufficiently clear what new insight into dynamic incentives, beyond the extension of an established framework to this setting, emerges from its results.

  2. The presentation obscures the central ideas and the incremental contribution. Sections 4 and 5 introduce the full promise-form representation, several value functions, approximation-oracle requirements, and error parameters before providing a sufficiently accessible account of the underlying recursion. A reader must work through considerable notation to see how current payments and continuation promises define the dynamic program, why discretization relaxes IC, and which steps differ materially from prior work. An early recursive formulation or worked example, followed by an explicit comparison with the previous framework, would make both the method and its contribution easier to assess.

[1] Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, and Mirco Mutti. (2023). Persuading Farsighted Receivers in MDPs: The Power of Honesty. Advances in Neural Information Processing Systems, 36.

[2] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. (2021). The Complexity of Contracts. SIAM Journal on Computing, 50(1), 211–254.

Questions for authors

Which result do the authors consider the most surprising new insight of the paper, beyond extending existing promise-based and IC-repair techniques? In particular, what does it reveal about dynamic contracting that is not already suggested by the related literature? If the novelty of the result could be established, I would be more prone to accept.

1 comment

We thank the Reviewer for the effort in evaluating our work.

Which result do the authors consider the most surprising new insight of the paper, beyond extending existing promise-based and IC-repair techniques? In particular, what does it reveal about dynamic contracting that is not already suggested by the related literature? If the novelty of the result could be established, I would be more prone to accept.

The goal of our paper is to study the computational complexity of sequential contract design. Our main new insights concern the representation of an approximately optimal contract that can be computed in polynomial time.

The main additional challenge compared with the setting of Bernasconi et al. (2023) is that we cannot detect whether the agent deviated or not from the recommendations. Bernasconi et al. (2023) could naturally express IC as a "local" constraint, since their principal stops playing after a deviation; the agent's cumulative utility after a deviation Q^h(a,s)\hat Q_h(a,s) is thus independent from the principal's policy, and IC essentially reduces to ensuring that the utility following recommendations is larger than a fixed quantity. By contrast, in our setting Q^hπ(s,a,ι)\hat Q^\pi_h(s,a,\iota) depends on the principal's policy. This leads to more complex IC constraints, which in principle could prevent us from devising an FPTAS. The most novel result is that it is nonetheless possible to compute compact and approximately optimal policies in polynomial time.

Reviewer_d9brOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
3(+2)
Read review
Paper summary

This paper studies the problem of incentive design for non-myopic agents whose actions are unobserved. The setting presupposes an MDP in which an agent carries out actions unseen by a principal, leading to outcomes (state transitions) which are observed. The question is to design a policy for the principal, which is a payment scheme that maximizes the principal's total return (payoff from outcomes minus payment to agent), assuming the agent is risk neutral under limited liability (payments are non-negative). The paper has three major beats:

  1. showing that optimization over Markov payment schemes (functions from state to payment) is intractable.
  2. showing that promise-form policies (functions over potential next state and amount promised over the trajectory to potential next payment) is optimization-equivalent to policies over the entire history of states to payment (the optimal value is preserved).
  3. showing that optimization over promise-form policies is approximable.
Critical strengths

The paper provides a comprehensive treatment of the dynamic agent-principal problem, from hardness to tractability (covering both the issue and the solution). The vertex cover hardness argument seems clearly nontrivial and novel. The approximation guarantees are also interesting and relatively novel to this problem as far as I can tell.

Critical weaknesses

It appears to me that this paper has some material lack of clarity about the novelty of the ideas. Given that I'm not native to the field, I can't provide a value judgement of how interesting the results are to the community. I did do some investigation on novelty, however, and found that there are some major branches of literature with similar results, which might eat into the novelty claims. Here's a breakdown of the assessment:

  1. The vertex cover hardness result seems unquestionably novel.
  2. Regarding the properties of promise-form policies and their tractability, there seems to be quite a bit of precedent not stated in the paper:

Spear, S. E., & Srivastava, S. (1987). On Repeated Moral Hazard with Discounting. The Review of Economic Studies, 54(4), 599–617.

  • shows that the agent's promised return is a sufficient statistic for history in a similar problem framing. Phelan, C., & Townsend, R. M. (1991). Computing Multi-Period, Information-Constrained Optima. The Review of Economic Studies, 58(5), 853–881.
  • solves dynamic moral hazard numerically with a recursive formulation, using lotteries to make each step a linear program. This is structurally the same recipe as Section 5's grid DP with one LP per step, but without approximation guarantees. Doepke, M., & Townsend, R. M. (2006). Dynamic Mechanism Design with Hidden Income and Hidden Actions. Journal of Economic Theory, 126(1), 235–285.
  • computational recursive contracts with both hidden actions and hidden states in Markov settings. Strictly harder setting, and also an LP-based method. Additionally: Lambert, R. A. (1983). Long-term Contracts and Moral Hazard. Bell Journal of Economics, 14, 441–452.

Rogerson, W. (1985). Repeated Moral Hazard. Econometrica, 53, 69–76.

Abreu, D., Pearce, D., & Stacchetti, E. (1990). Toward a Theory of Discounted Repeated Games with Imperfect Monitoring. Econometrica, 58(5), 1041–1063.

Sannikov, Y. (2008). A Continuous-Time Version of the Principal-Agent Problem. The Review of Economic Studies, 75(3), 957–984.

What the implications are:

  1. The way that novelty is characterized regarding promise-form policies is that Bernasconi et al. (2023) has considered a similar idea in a different setting. To a reader not familiar with the background literature, this grossly misrepresents the lineage of this notion.
  2. I think that even accounting for this, the paper has enough novelty and contributions to be publishable, but the story will need to be restructured substantially. It seems to me that these citations need to be seriously engaged with, one cannot wave them away under the umbrella of "having done something similar."
  3. The fact that similar arguments appear in the literature is also reassuring about the soundness of the idea. Worst case, the authors have rediscovered a few things.

Finally, on an unrelated note, it might be a good idea to change the title to "Contracting with a Non-Myopic Agent...". The current title seems to suggest that there's something about reinforcement learning in particular that makes the agent do something it otherwise wouldn't (e.g. if it were relying on symbolic planning for example).

Questions for authors

Is it possible to clarify the novelty situation within the reviewing timeframe? Given that I'm kind of a tourist here, I'll do the risk-averse thing of suggesting a weak reject, but I'm looking forward to the discussion.

4 comments

We thank the Reviewer for the effort in evaluating our work.

Is it possible to clarify the novelty situation within the reviewing timeframe? Given that I'm kind of a tourist here, I'll do the risk-averse thing of suggesting a weak reject, but I'm looking forward to the discussion.

We agree with the Reviewer that the idea of condensing histories into expected future utilities has been explored in other previous works. However, the economic literature focuses on characterizing optimal contracts in specific settings (see e.g, Spear and Srivastava (1987)), while we study the problem of computing such contracts in a rather general framework. Since the optimal policy could employ an exponentially large set of promises, we need to analyze policies that employ a small set of approximate promises. The work of Bernasconi et al. (2023) is thus the most similar to ours in terms of algorithms and analysis, as it uses promises as a computational tool to build approximate solutions. The main difference is that in the model of Bernasconi et al. (2023) deviations can be detected after one step. Therefore the effect of a deviation does not depend on the principal’s future choices.

From a computational point of view, dynamic programming with a discretized state variable is a rather standard approach for devising approximation algorithms, and LPs are a natural tool in algorithmic contract design (see Dütting et al., 2024). However, applying these techniques to our setting requires considerable work. Let us also observe that while Doepke et al. (2006) study a similar hidden-action setting with a farsighted agent and employ a dynamic programming approach with multiple LPs, they do not obtain an FPTAS, which is the most challenging part of our work. Indeed, they provide guarantees only when the optimal set of promises is known beforehand and is small. By contrast, we need to consider discrete and approximate promises. This requires not only different optimization programs (the model by Doepke et al. (2006) allows for a direct LP formulation) but also a substantially different anlysis.

Dütting, P., Feldman, M., & Talgam-Cohen, I. (2024). Algorithmic contract theory: A survey. Foundations and Trends in Theoretical Computer Science, 16(3-4), 211-411.

Thank you for the response. Your explanation of the gap relative to Bernasconi et al. (2023) clarifies the algorithmic contribution. Consider my concern resolved in this respect. Where I am still unsatisfied is the scholarship and positioning around adjacent work. Even coming from outside this specific field, it is clear that your paper sits very close to prior work on several fronts at once: condensing histories into promised utilities (Spear & Srivastava, 1987), dynamic programming with LPs over discretized promises (Phelan & Townsend, 1991; Doepke & Townsend, 2006), sequential persuasion with approximate promises (Bernasconi et al., 2023), and contract rounding/repair. When the building blocks overlap this closely, foundational work cannot be dismissed summarily as just "specific settings". Along those lines, I looked up Doepke & Townsend (2006) after reading your comment. Unless I am misreading their setup, saying they only provide guarantees "when the optimal set of promises is known beforehand and is small" doesn't look like a fair characterization of what they do. They explicitly note that the set of feasible promises is not known in advance, establish the exact recursion over continuous promises, and then introduce a finite grid (using lotteries) in Section 4.3 as a numerical approximation. As far as I can tell, the real difference is that they treat grid discretization heuristically without proving worst-case approximation bounds (an FPTAS)—which is already a clean, strong distinction for your paper without misstating theirs. Right now, none of this discussion is in the manuscript itself, and Theorem 2 still reads as if promise-based state reductions originated in recent CS papers rather than decades-old contract theory. To reconsider my score: I would like to see a commitment towards updating the Introduction, Related Work, and the discussion around Theorem 2 that engages seriously with Spear & Srivastava (1987), Phelan & Townsend (1991), Doepke & Townsend (2006), and Bernasconi et al. (2023), and draws an explicit, accurate boundary between classical promise/grid-LP ideas and your FPTAS and IC-repair contributions.

We thank the Reviewer for the response. We have updated the paper to include a discussion of the related works in the economic literature, and to place our contributions within the established literature.

Regarding (Doepke et al. 2006), we agree that our initial assessment was too harsh. (Doepke et al. 2006) treats discretiazion as a practical approximation, without providing theoretical guarantees on the value lost. They prove that their algorithm computes, in time polynomial in the sizes of the grids, an optimal policy under the additional constraint that only the discrete values on their grids are used. Let us also remark that, unlike (Doepke et al. 2006), we do not discretize contracts (which would introduce additional challenges in evaluating the approximation) and we cannot directly randomize over future promises (which would require a richer interaction protocol). Both these elements were crucial to design the LPs in (Doepke et al. 2006).

I believe the authors' latest changes resolve my concerns. I will adjust my scores and final recommendation upwards.

Reviewer_F6p9OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies a special class of MDP where there is a principal and an agent. The actions of an agent are hidden to the principal and only the corresponding reward are observable. In particular, the agent is farsighted meaning that it maximizes the accumulated reward over an interval rather than instantaneous rewards. The paper shows that with history-dependent policy, computing approximately optimal policy can be polynomial whereas with Markovian policy, it can be NP-Hard. Moreover, it is shown that the history-dependent policy induces larger return than Markovian policy can do under particular instances. The authors develop a promise form policy achieving the optimal expected cumulative reward for the principal while incentive compatible (IC).

Critical strengths
  1. The paper studies an underexplored setting in the literature--where the agents are farsighted and the interaction between the principal and the agents are sequential rather than one-shot. This is closer to practical settigns and makes the problem more complex.

  2. The complexity results derived in this paper seems to be interesting. The result that non-stationary Markovian policies are NP-hard for solving the principal-agent problems seems to be an important result highlighting the limitation of common usage of Markovian policy. The authors suggest the history-dependent policy as a viable option, and provides a polynomial time algorithm. This clearly explains the advantage of the proposed method.

  3. The paper directly addresses and resolves the primary obstacle of of history-dependent policies and propose a solution for this. The history-based method can lead to an intractable history space and the authors propose a promise-based method to resolve this without loosing optimality.

Critical weaknesses

Major concerns

  1. The methodological and technical differences between the proposed framework and the method proposed by Bernasconi are not clearly explained. Clarification on what stricter notion of promises is used and what relative incentive-compatibility constraints have changed would help better contextualize the paper's specific contributions.

  2. Even though the authors propose a polynomial-time algorithm, and this is theoretically interesting, the major concern is whether this can be implemented in practice. The authors should clarify what the important factors are to make this algorithm practical, and which dependencies are important. Furthermore, it should be clarified what prior knowledge of the model is required to implement the proposed algorithm. Providing small toy examples would help with understanding this.

Minor Comments

  1. The citation format needs to be corrected, for example line 90.

  2. The acronym IC appears before its explanation.

  3. I would recommend cutting the heavy technical details in the main manuscript and including a conclusion in main manuscript.

Questions for authors
  1. Related to the weakness, what is the dependency on the model parameters for the polynomial-time algorithm proposed, and what prior knowledge of the model do we need to implement the algorithm?
2 comments

We thank the Reviewer for the effort in evaluating our work.

What is the dependency on the model parameters for the polynomial-time algorithm proposed?

The main source of computational complexity in our procedure is Algorithm 2, which solves at most O(H2∣S∣/δ)\mathcal{O}(H^2|\mathcal{S}|/\delta) linear programs with O(∣A∣∣S∣H/δ)\mathcal{O}(|\mathcal{A}||\mathcal{S}|H/\delta) variables and O(∣A∣2+∣A∣∣S∣H/δ)\mathcal{O}(|\mathcal{A}|^2 +|\mathcal{A}||\mathcal{S}|H/\delta) constraints each. We remark that this is the first polynomial-time algorithm for this problem and we do not have a benchmark to compare to.

What prior knowledge of the model do we need to implement the algorithm?

We solve an offline planning problem that requires full knowledge of the model parameters. We do not study the problem of learning unknown parameters; while some related works (Wu et al., 2024; Gan et al., 2026) provide learning algorithms, they do so under strong feedback assumptions, essentially removing the hidden-action assumption that gives raise to the main challenge of our planning problem.

Thanks for the detailed response. Most of my concerns have been addressed and the computational complexity result is a contribution to the field. However, the concerns that proper comparison with exisitng works that used similar ideas in the classical contract theory raised by the other reviewers seems to be an important point to be addressed. I will followup on the discussion and adjust the ratings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.