betaFeedback

WorksComputer Science

Contracting with an Agent under Model Mismatch

Abstract

In the classical principal-agent setting, the principal delegates some task to the agent, who receives a payment conditioned on the outcome of the task, which in turn benefits the principal. To align their objectives, the principal designs a contract that incentivizes the agent to take actions beneficial to the principal. In practice, however, the agent may act under misspecified beliefs about the underlying environment, leading to systematically suboptimal decisions. In this work, we study this problem through a principal-agent Markov Decision Process (PAMDP), in which the principal repeatedly interacts with an agent whose transition model may differ from the true environment dynamics. The principal has access to the true transition model and designs contracts that account for the agent's belief and incentives. We characterize contract design under model mismatch and develop a framework that enables the principal to induce desirable long-term benefits even though the agent has a potentially inaccurate understanding of the environment.

Introduction

The incentive alignment between two parties has long been described through the principal-agent framework, in which a principal delegates a task to an agent by offering a contract that specifies an outcome-based payment. The design of optimal contracts has been explored by economists and computer scientists [5, 6, 13], where it plays a fundamental role in understanding strategic interactions and incentive mechanisms in both macro- and micro-economic settings.

In the era of increasing human-AI cooperation, the contract design problem has become more relevant than ever before. When delegating tasks to AI systems, we must account for the potential misalignment of the environment dynamics, where one party cannot always assume that the other possesses an accurate model of the environment and may act according to a misspecified understanding of the environment dynamics. This form of model disagreement has been studied in a two-agent sequential stochastic game, where agents may use different models of the world while sharing the same reward structure [8]. Existing formulations of the principal-agent Markov Decision Process (PAMDP) [3, 26] assume that both parties share the same model of the world. We, however, consider a case where the agent acts according to an unknown, potentially suboptimal misspecified model. Under this model misalignment, the principal’s goal is to design contracts that maximize its utility while remaining incentive compatible with respect to the agent’s transition model.

We study the problem of contract design under uncertainty about the agent’s environment model. Our approach is based on balancing exploration, in which the principal proposes contracts that reveal information about the agent’s model, and exploitation, in which the principal leverages the information to offer approximately optimal contracts. Exploration is crucial because the agent’s dynamics influence both the actions induced by a contract and the decision to accept it. Consequently, a principal who ignores these belief misalignment risks may design suboptimal contracts, resulting in suboptimal utility or even contract rejection.

We propose a Bayesian learning approach for contract design in PAMDPs with misspecified agent beliefs, where the principal knows the true transition dynamics and the agent uses a different model. We assume that the principal has access to a finite set of possible agent models. The principal maintains a posterior distribution over this set and updates this belief through their repeated interactions. Using the estimated agent’s transition model, the principal computes least payment contracts using backward induction and linear programming. We analyze how mismatched transition dynamics in a PAMDP setting influence contract design and the resulting incentive mechanism. Our main contributions are reformulating the optimal solutions for this setting and validating our approach through empirical experiments. We further investigate how the choice of the candidate model set influences the learning process, including the accuracy of the agent’s transition model estimation, the convergence of the posterior and the resulting contract design.

Related Work

Principal-agent problems, which formalize settings in which a principal delegates a task to an agent under moral hazard, have been extensively studied in economics and computer science as a fundamental framework [5, 13, 17, 18, 23]. [5] has provided an extensive overview of standard contract theory and incentive mechanism design. Recently, algorithmic contract design has been widely studied in the literature to investigate how contracts can be designed using computational methods [1, 7, 12, 13, 14, 20]. The complexity of finding optimal contracts has been studied in [2, 15, 19, 27]. Moreover, [6, 11] have considered multi-agent settings where the principal designs contracts for multiple agents by extending the single agent contract design approaches.

Optimal contract design is closely related to online learning when the principal does not have perfect information about the agent. In such settings, learning effective incentives over time through repeated interactions has become crucial in the literature [9, 10, 21, 28]. Furthermore, [4, 19, 25] have focused on the settings where the agent learns over time, investigating how to design suitable contracts by incentivizing the learning agent.

We focus on a PAMDP setting, where the principal learns how to design contracts to incentivize an agent making sequential decisions in an MDP. The principal-agent reinforcement learning framework has been introduced in [22]. More recently, different approaches to designing optimal contracts have been investigated, including reward shaping [3] or history-dependent policies instead of Markovian policies [4].

Our setting is related to the contractual reinforcement learning framework [26], but we consider a setting where the principal and the agent have different transition models, and the principal must infer this to design appropriate contracts. [8] has introduced multi-view decision processes with two agents, where they disagree on transition probabilities and share the same reward function. Moreover, [16] has introduced the Berk-Nash Equilibrium to model decision making under misspecified beliefs. Recently, [24] has analyzed the learning dynamics of a Bayesian agent with a finite set of misspecified beliefs and demonstrated that the action frequencies converge to such an equilibrium for a learning agent with two actions. However, these works do not consider an MDP setting. In contrast, we study model mismatch in a principal-agent MDP and investigate how learning the agent’s belief influences contract design.

Problem Setting

We consider a principal-agent MDP setting in which a principal interacts with an agent over a finite horizon. In each step, the principal offers a contract to the agent, and the agent selects an action based on its own transition dynamics. The resulting state transition is then realized according to the true transition dynamics of this environment. We assume that the principal has access to the true transition model while the agent may have a misspecified model. Figure 1 demonstrates how the principal and the agent interact in such an environment.

PAMDP setting under model mismatch

Figure 1. PAMDP setting under model mismatch

Formally, a finite horizon Markov Decision Process (MDP) is defined by a tuple M:=(S,A,{μhP,rh}h=1H,ρ0)M := (\mathcal{S}, \mathcal{A}, \{\mu_h^P, r_h\}_{h=1}^{H}, \rho_0) where S\mathcal{S} is a set of possible states, A\mathcal{A} is an action space, and HH denotes the finite horizon length. In each step hh, the transition dynamics is determined by the true transition kernel μhP:S×A→Δ(S)\mu_h^P : \mathcal{S} \times\mathcal{A} \to\Delta(\mathcal{S}), where μhP(s,a)\mu_h^P(s, a) specifies the probability distribution over the next state after taking action a∈Aa \in\mathcal{A} in state s∈Ss \in\mathcal{S}. rh:S×A→Rr_h : \mathcal{S} \times\mathcal{A} \to\mathbb{R} is the environment reward function in step hh and the initial state is sampled from the initial state distribution ρ0∈Δ(S)\rho_0 \in\Delta(\mathcal{S}).

A PAMDP is represented by a tuple G:=(M,B,{μhA,ch,πh}h=1H)\mathcal{G} := (M, \mathcal{B}, \{\mu_h^A, c_h, \pi_h\}_{h=1}^{H}). In addition to the underlying MDP MM, a PAMDP contains a contract space B\mathcal{B} such that bh:S×S→Rb_h : \mathcal{S} \times\mathcal{S} \to\mathbb{R} specifies the contract payment received by the agent based on the state and the next state. In each step hh, the principal observes the current state shs_h and offers a contract bhb_h to the agent. The agent then selects an action ah∈Aa_h \in\mathcal{A} according to its policy πh:S→Δ(A)\pi_h : \mathcal{S} \to\Delta(\mathcal{A}). While the agent makes decisions based on its own transition model μhA:S×A→Δ(S)\mu_h^A : \mathcal{S} \times\mathcal{A} \to\Delta(\mathcal{S}), the next state is realized according to the true transition model The agent suffers a cost ch:S×A→Rc_h : \mathcal{S} \times\mathcal{A} \to\mathbb{R} and the principal receives the reward rhr_h defined in the underlying MDP. Thus, the principal designs contracts while accounting for the mismatch between the agent’s transition model μhA\mu_h^A and the true transition model μhP\mu_h^P.

Principal and Agent Value Functions

Given an action policy πh\pi_h and a contract bhb_h in a step hh, we define value functions for the principal and the agent as they optimize different objectives and have different beliefs about the transition dynamics. The principal evaluates the expected cumulative reward under the true transition model μP\mu^P. In contrast, the agent evaluates its expected cumulative utility under its own transition model μA\mu^A, considering the contract payments received and the costs of action incurred.

We define the principal’s state value function at step hh under any action policy π\pi and contract bb as:

VhP(s∣π,b):=E[∑τ=hHrτ(sτ,aτ)−bτ(sτ,sτ+1)∣{πτ}τ=hH,sτ=s,μP]=∑a∈Aπh(a∣s)QhP(s,a∣π,b)(1)V_h^P(s \mid\pi,b) \mathrel{\mathop:}= \mathbb{E}\left[\sum_{\tau=h}^{H} r_\tau(s_\tau,a_\tau)-b_\tau(s_\tau,s_{\tau+1}) \mid\{\pi_\tau\}_{\tau=h}^{H},s_\tau=s,\mu^P\right] = \sum_{a\in\mathcal{A}}\pi_h(a\mid s)Q_h^P(s,a\mid\pi,b) \tag*{(1)}

where QhP(s,a∣π,b)Q_h^P(s,a\mid\pi,b) is the principal’s state-action value function which is written as

QhP(s,a∣π,b):=E[∑τ=hHrτ(sτ,aτ)−bτ(sτ,sτ+1)∣{πτ}τ=hH,sτ=s,aτ=a,μP](2)Q_h^P(s,a\mid\pi,b) \mathrel{\mathop:}= \mathbb{E}\left[\sum_{\tau=h}^{H} r_\tau(s_\tau,a_\tau)-b_\tau(s_\tau,s_{\tau+1}) \mid\{\pi_\tau\}_{\tau=h}^{H},s_\tau=s,a_\tau=a,\mu^P\right] \tag*{(2)}
=rh(s,a)+∑s′μhP(s′∣s,a)(Vh+1P(s′)−bh(s,s′))(3)= r_h(s,a)+\sum_{s'}\mu_h^P(s'\mid s,a)\left(V_{h+1}^P(s')-b_h(s,s')\right) \tag*{(3)}

Similarly, the agent’s state value function is defined by:

VhA(s∣π,b):=E[∑τ=hHbτ(sτ,sτ+1)−cτ(sτ,aτ)∣{πτ}τ=hH,sτ=s,μA]=∑a∈Aπh(a∣s)QhA(s,a∣π,b)(4)V_h^A(s\mid\pi,b) \mathrel{\mathop:}= \mathbb{E}\left[\sum_{\tau=h}^{H} b_\tau(s_\tau,s_{\tau+1})-c_\tau(s_\tau,a_\tau)\mid\{\pi_\tau\}_{\tau=h}^{H},s_\tau=s,\mu^A\right] = \sum_{a\in\mathcal{A}}\pi_h(a\mid s)Q_h^A(s,a\mid\pi,b) \tag*{(4)}

where QhA(s,a∣π,b)Q_h^A(s,a\mid\pi,b) is the agent’s state-action value function which is expressed by

QhA(s,a∣π,b)=E[∑τ=hHbτ(sτ,sτ+1)−cτ(sτ,aτ) | {πτ}τ=hH,sτ=s,aτ=a,μA](5)Q_h^A(s,a\mid\pi,b)=\mathbb{E}\left[\sum_{\tau=h}^{H} b_\tau(s_\tau,s_{\tau+1})-c_\tau(s_\tau,a_\tau)\ \middle|\ \{\pi_\tau\}_{\tau=h}^{H},s_\tau=s,a_\tau=a,\mu^A\right] \tag*{(5)}
=−ch(s,a)+∑s′μhA(s′∣s,a)(Vh+1A(s′)+bh(s,s′))(6)=-c_h(s,a)+\sum_{s'}\mu_h^A(s'\mid s,a)\left(V_{h+1}^A(s')+b_h(s,s')\right) \tag*{(6)}

Contract Constraints

The optimal contract design problem is subject to several standard constraints containing Individual Rationality (IR), Incentive Compatibility (IC) and Limited Liability (LL). These constraints ensure that the designed contract is both acceptable to the agent and effective in inducing the desired behavior.

Definition 1 (Individual Rationality). A contract bb satisfies the IR constraint if

VhA(s∣π,b)≥0.(7)V_h^A(s\mid\pi,b)\ge0. \tag*{(7)}

Otherwise, the agent rejects the contract. It means that the agent accepts the contract only if the expected utility obtained from the induced policy is non-negative.

Definition 2 (Incentive Compatibility). A contract is incentive compatible if it induces the agent to take the desired action by making the intended action optimal under the agent’s own model. Specifically, for a target action a∗a^* in state ss, a contract bb satisfies the IC constraint if

QhA(s,a∗∣π,b)≥QhA(s,a∣π,b),∀a∈A.(8)Q_h^A(s,a^*\mid\pi,b)\ge Q_h^A(s,a\mid\pi,b),\quad\forall a\in\mathcal{A}. \tag*{(8)}

This constraint ensures that, given the contract and the agent’s transition model μA\mu^A, the agent’s best response is the desired action a∗a^*.

Definition 3 (Limited liability). The principal cannot assign negative payments to the agent:

bh(s,s′)≥0,∀s,s′∈S(9)b_h(s,s')\ge0,\quad\forall s,s'\in\mathcal{S} \tag*{(9)}

Remark 1. The agent is assumed to always participate in the game. This allows us to ignore the IR constraint by adding a terminate action a0a_0 to A\mathcal{A} with rh(s,a0)=ch(s,a0)=0r_h(s,a_0)=c_h(s,a_0)=0 for all s∈Ss\in\mathcal{S} and all step hh, which ensures nonnegative utility for the agent. Therefore, we only need to enforce the IC constraint.

Since the principal and the agent interact at each step, as illustrated in Figure 1, selecting the terminate action at any step hh can be interpreted as the agent rejecting the contract for that step. In this case, the agent receives no payment and incurs no additional cost, ensuring a nonnegative utility for the agent.

Optimal Solutions Using Backward Induction and Linear Program

In this section, we consider a solution approach similar to [26], where the contract parameters are computed iteratively using backward induction and linear program from the final step HH to the initial step 1. Unlike existing formulations, we reformulate the least payment equations under different beliefs about the transition dynamics. The goal of the optimization problem is to minimize the total contract payment of the principal subject to the agent’s incentive compatibility constraint. Thus, we derive a least payment solution under the assumption of full observability of the system.

In each step hh, the principal designs a contract that maximizes its expected utility under the true transition dynamics μP\mu^P:

bh(s)=arg⁡max⁡b∈B VhP(s∣π,b)(10)b_h(s)=\underset{b\in\mathcal{B}}{\arg\max}\ V_h^P(s\mid\pi,b) \tag*{(10)}

Then, given a contract bhb_h, the agent selects an action according to its policy πh\pi_h under its own transition model μA\mu^A:

πh(s)=arg⁡max⁡a∈A QhA(s,a∣π,b)(11)\pi_h(s)=\underset{a\in\mathcal{A}}{\arg\max}\ Q_h^A(s,a\mid\pi,b) \tag*{(11)}

Since the principal cannot directly incentivize the agent’s action, the contract is designed to induce the desired action through the agent’s best response policy.

We first consider the terminal step HH, which serves as the base case of the backward induction. We then derive the recursive formulation for the remaining steps h<Hh < H. Accordingly, we set VH+1A(s)=0V^{A}_{H+1}(s) = 0 and VH+1P(s)=0V^{P}_{H+1}(s) = 0. Thus, the agent’s and principal’s state value functions at step HH are given by

VHA(s∣π,b)=∑a∈AπH(a∣s)QHA(s,a∣b)(12)V^{A}_{H}(s \mid\pi, b) = \sum_{a \in A} \pi_{H}(a \mid s) Q^{A}_{H}(s,a \mid b) \tag*{(12)}

with

QHA(s,a∣π,b)=−cH(s,a)+∑s′∈SμHA(s′∣s,a)bH(s,s′),(13)Q^{A}_{H}(s,a \mid\pi,b) = -c_{H}(s,a) + \sum_{s' \in S} \mu^{A}_{H}(s' \mid s,a)b_{H}(s,s'), \tag*{(13)}

and

VHP(s∣π,b)=∑a∈AπH(a∣s)QHP(s,a∣b)(14)V^{P}_{H}(s \mid\pi,b) = \sum_{a \in A} \pi_{H}(a \mid s) Q^{P}_{H}(s,a \mid b) \tag*{(14)}

with

QHP(s,a∣π,b)=rH(s,a)−∑s′∈SμHP(s′∣s,a)bH(s,s′).(15)Q^{P}_{H}(s,a \mid\pi,b) = r_{H}(s,a) - \sum_{s' \in S} \mu^{P}_{H}(s' \mid s,a)b_{H}(s,s'). \tag*{(15)}

In step HH, for each action a∈Aa \in A, we calculate the optimal contract bH∗(s;a)b^{*}_{H}(s;a), which represents the least payment contract that induces the agent to select action aa. This contract can be computed by the following linear program:

bH∗(s;a)=arg⁡min⁡b∈B∑s′μHP(s′∣s,a)b(s,s′)(16)b^{*}_{H}(s;a) = \mathop{\arg\min}_{b \in B} \sum_{s'} \mu^{P}_{H}(s' \mid s,a)b(s,s') \tag*{(16)}

subject to

−cH(s,a)+∑s′μHA(s′∣s,a)b(s,s′)≥−cH(s,a′)+∑s′μHA(s′∣s,a′)b(s,s′),∀a′≠a,-c_{H}(s,a) + \sum_{s'} \mu^{A}_{H}(s' \mid s,a)b(s,s') \geq-c_{H}(s,a') + \sum_{s'} \mu^{A}_{H}(s' \mid s,a')b(s,s'), \quad\forall a' \ne a,
b(s,s′)≥0b(s,s') \geq0

This optimization is equivalent to maximizing the principal’s utility at step HH since the reward term rH(s,a)r_{H}(s,a) is independent of the contract bb.

Using the resulting contract bH∗(s;a)b^{*}_{H}(s;a), the principal obtains the corresponding state-action value function QHP(s,a∣bH∗(s;a))Q^{P}_{H}(s,a \mid b^{*}_{H}(s;a)). Therefore, with ties broken in favor of the principal, the optimal action policy for the principal to induce is determined by

πH∗(s)=arg⁡max⁡a∈AQHP(s,a∣bH∗(s;a))(17)\pi^{*}_{H}(s) = \mathop{\arg\max}_{a \in A} Q^{P}_{H}(s,a \mid b^{*}_{H}(s;a)) \tag*{(17)}

We denote the optimal action under the policy πH∗(s)\pi^{*}_{H}(s) by aH∗a^{*}_{H} since we have a deterministic action policy. Then, the optimal contract bH∗(s)b^{*}_{H}(s) under the action aH∗a^{*}_{H} is subsequently obtained by

bH∗(s)=bH∗(s;aH∗).(18)b^{*}_{H}(s) = b^{*}_{H}(s;a^{*}_{H}). \tag*{(18)}

The optimal value functions of the principal and the agent in step HH, VHP∗V^{P*}_{H} and VHA∗V^{A*}_{H}, are then obtained under the best action policy πH∗\pi^{*}_{H} and the optimal contract bH∗b^{*}_{H}, respectively.

At each step h<Hh < H, following the backward induction procedure, the principal computes the least payment contract required to induce action aa by solving the following:

bh∗(s;a)=arg⁡min⁡b∈B∑s′μhP(s′∣s,a)b(s,s′)(19)b^{*}_{h}(s;a) = \mathop{\arg\min}_{b \in B} \sum_{s'} \mu^{P}_{h}(s' \mid s,a)b(s,s') \tag*{(19)}

subject to

−ch(s,a)+∑s′μhA(s′∣s,a)(Vh+1A∗(s′)+b(s,s′))≥−ch(s,a′)+∑s′μhA(s′∣s,a′)(Vh+1A∗(s′)+b(s,s′)),∀a′≠a-c_{h}(s,a) + \sum_{s'} \mu^{A}_{h}(s' \mid s,a)(V^{A*}_{h+1}(s') + b(s,s')) \geq-c_{h}(s,a') + \sum_{s'} \mu^{A}_{h}(s' \mid s,a')(V^{A*}_{h+1}(s') + b(s,s')), \quad\forall a' \ne a
b(s,s′)≥0b(s,s') \geq0

where Vh+1A∗V^{A*}_{h+1} is under the optimal policy πh+1∗\pi^{*}_{h+1} and the optimal contract bh+1∗b^{*}_{h+1}. Thus, using the principal’s state-action value function QhP(s,a∣bh∗(s;a))Q^{P}_{h}(s,a \mid b^{*}_{h}(s;a)) under the contract bh∗(s;a)b^{*}_{h}(s;a), the best action policy for the principal to induce an action is:

πh∗(s)=arg⁡max⁡a∈AQhP(s,a∣bh∗(s;a))(20)\pi^{*}_{h}(s) = \mathop{\arg\max}_{a \in A} Q^{P}_{h}(s,a \mid b^{*}_{h}(s;a)) \tag*{(20)}

and the optimal contract bh∗(s)b_h^*(s) under the action ah∗∼πh∗(s)a_h^* \sim\pi_h^*(s) can be determined by

bh∗(s)=bh∗(s;ah∗).(21)b_h^*(s) = b_h^*(s; a_h^*). \tag*{(21)}

Similarly, in step hh, the optimal value functions can be written using the best action policy πh∗\pi_h^* and the optimal contract bh∗b_h^*. As a result, we note that the principal can design a contract which is likely to incorporate the agent’s action costs and transition model, which enables the principal to incentivize the agent directly with the contract.

The optimal solutions are computed under the perfect information about the agent’s transition model to induce a target action policy. Therefore, we note that the resulting contracts are incentive compatible, as the principal’s induced policy is aligned with the best response policy of the agent.

Motivation

Figure 2 compares the value functions of both the principal and the agent under settings with shared and mismatched beliefs and the corresponding total payments offered by the principal. We apply the optimal solution derived in the previous section. The results demonstrate how misspecified beliefs about the transition dynamics influence their value functions and the total contract payments by the principal. We report the average results over 20 trials, where rewards and costs are randomly sampled from [0,1][0, 1], and contract payments are bounded in [0,2][0, 2]. We use an MDP with ∣S∣=5|S| = 5, ∣A∣=3|A| = 3, H=3H = 3 and a uniform initial state distribution.

Figure 2. Comparison of optimal solutions under the same and different beliefs

We compare the total contract payments under different beliefs and the same beliefs. The promised payment is computed as the sum of all entries in the contract payment matrix. We also evaluate the expected total payment under both the agent’s transition model and the true transition dynamics by accounting for the action policy. This enables us to compare the payment the agent expects to receive based on its own model and the payment the agent actually receives under the true dynamics. For their expected utility, we focus on the state value function, where we apply the backward induction steps in the previous section.

The results in Figure 2 show that when the principal and the agent share the same belief about the transition model, the principal can induce the desired behavior with relatively lower contract payments. In contrast, under different beliefs, the principal offers higher contract payments to compensate for the discrepancy between the agent’s model and the true dynamics. The figure highlights the difference between the agent’s expectation and realized performance. According to its own model, the agent believes to receive a higher return; however, when evaluated under the true dynamics, the realized payments and the resulting state value of the agent are lower. Consequently, the agent overestimates its expected utility due to misspecified model, at the same time, the principal achieves higher utility under belief mismatch despite offering a higher contract payment to the agent. This is because the realized payments under the true transition dynamics are lower than those in the shared belief setting. These results demonstrate that different beliefs can significantly affect the contract design and the incentive mechanism in sequential decision-making.

Learning in a PAMDP Setting with Misspecified Model

The principal’s objective is to offer contracts that incentivize the agent to act in a way that maximizes the principal’s utility. We consider an episodic learning consisting of TT episodes, where the principal and the agent interact over HH steps in each episode. In each episode t∈[T]t \in[T], at each step h∈[H]h \in[H], the principal offers a contract and observes the agent’s response, where the agent is assumed to be best responding to the offered contract according to its own transition model. Since the state transitions are generated by the true transition dynamics μP\mu^{P} (rather than μA\mu^{A}), the agent’s model is not directly observable from the realized transitions. The principal commits to a contract payment bb, which maximizes its expected utility, at the beginning of each episode, since the principal can anticipate the agent’s best response to the committed contract. The agent computes the optimal action policy after the principal offers the contract. This implies that updates are performed at the end of each episode.

To simplify the analysis, we assume that the principal has access to a finite set of possible agent models M\mathcal{M}. The principal knows the true transition dynamics μP\mu^{P}, observes (sh,ah,sh+1)(s_h, a_h, s_{h+1}) in each step hh, which is stored in the trajectory ξt\xi_t for episode tt, where shs_h is the current state, aha_h is the action taken by the agent according to the policy πh\pi_h, which is determined by the model of the agent, and sh+1s_{h+1} is the next state realized according to the true dynamics μhP\mu_h^{P}. In addition, for any step hh, the action cost function chc_h is assumed to be known by the principal.

Algorithm 1 Bayesian Learning for Contract Design under Misspecified Model

  1. Input: S,A,μP,ρ0,M,H,T\mathcal{S}, \mathcal{A}, \mu^{P}, \rho_0, \mathcal{M}, H, T

  2. Initialize P0=Unif⁡(M)P_0 = \operatorname{Unif}(\mathcal{M}).

  3. for t=1,2,⋯ ,Tt = 1, 2, \cdots, T do

  4. Sample μ^A∼Pt\hat{\mu}^{A} \sim P_t

  5. Compute bt={bht}h=1Hb^t = \{b_h^t\}_{h=1}^{H} using (22)

  6. Initialize the trajectory ξt←∅\xi_t \leftarrow\varnothing.

  7. Sample initial state s0∼ρ0s_0 \sim\rho_0

  8. for h=0,1,⋯ ,H−1h = 0, 1, \cdots, H - 1 do

  9. Offer bht(sh)b_h^t(s_h) to the agent based on current state shs_h

  10. The agent selects an action aht∼πht(sht)a_h^t \sim\pi_h^t(s_h^t)

  11. The agent incurs the cost ch(sht,aht)c_h(s_h^t, a_h^t)

  12. The next state sh+1t∼μhP(sh,ah)s_{h+1}^t \sim\mu_h^P(s_h, a_h) is realized

  13. Observe sh+1ts_{h+1}^t and make the payment bht(sht,sh+1t)b_h^t(s_h^t, s_{h+1}^t)

  14. Observe ahta_h^t and receive reward rh(sht,aht)r_h(s_h^t, a_h^t)

  15. Update ξt←ξt∪{(sht,aht,sh+1t)}\xi_t \leftarrow\xi_t \cup\{(s_h^t, a_h^t, s_{h+1}^t)\}

  16. end for

  17. Update Pt+1P_{t+1} using Bayes’ rule based on ξt\xi_t

  18. end for

Therefore, the principal maintains an estimate μ^A\hat{\mu}^{A} of the agent’s transition model and updates it through repeated interaction using a Bayesian learning approach. Based on the posterior, the principal obtains a prior estimate μ^A\hat{\mu}^{A} of the agent’s transition model and designs contracts accordingly. In particular, the principal uses the observed trajectories in each episode to update its posterior over M\mathcal{M}. Using the updated belief, the principal can offer approximately optimal contracts according to the true dynamics μP\mu^{P}, but is constrained by the estimated agent’s model μ^A\hat{\mu}^{A}. Therefore, for step hh in episode tt, the least payment contract is computed using estimates as follows:

b^h(s;a)=arg⁡min⁡b∈B∑s′μhP(s′∣s,a)b(s,s′)(22)\hat{b}_h(s; a) = \mathop{\arg\min}_{b \in\mathcal{B}} \sum_{s'} \mu_h^{P}(s' \mid s, a)b(s, s') \tag*{(22)}

subject to

−ch(s,a)+∑s′μ^hA(s′∣s,a)(V^h+1A(s′)+b(s,s′))≥−ch(s,a′)+∑s′μ^hA(s′∣s,a′)(V^h+1A(s′)+b(s,s′)), ∀a′≠a-c_h(s, a) + \sum_{s'} \hat{\mu}_h^{A}(s' \mid s, a)\left(\hat{V}_{h+1}^{A}(s') + b(s, s')\right) \geq-c_h(s, a') + \sum_{s'} \hat{\mu}_h^{A}(s' \mid s, a')\left(\hat{V}_{h+1}^{A}(s') + b(s, s')\right),\ \forall a' \ne a
b(s,s′)≥0b(s, s') \geq0

where V^hA\hat{V}_h^{A} is an estimate of the agent’s value under the estimated induced policy and the committed contract. Then, we follow similar steps as in Section 3 to determine the best contract payment and the policy to induce for the principal.

Let PtP_t denote the distribution over the set M\mathcal{M} in episode tt. At the beginning of the interaction, a prior P0P_0 is initialized as the uniform distribution over M\mathcal{M}. In each episode tt, the principal updates the posterior distribution PtP_t using observed trajectories, samples a model μ^A∼Pt\hat{\mu}^{A} \sim P_t from M\mathcal{M} and designs the contract which is constrained by μ^A\hat{\mu}^{A}. The learning procedure for each episode consists of the steps in Algorithm 1.

Based on the trajectory ξt={(sht,aht,sh+1t)}h=1H\xi_t = \{(s_h^t, a_h^t, s_{h+1}^t)\}_{h=1}^H in episode tt, the principal updates its posterior belief over the possible agent models using Bayes’ rule as follows:

Pt+1(μ^A)∝Pt(μ^A)P(ξt∣μ^A)(23)P_{t+1}(\hat{\mu}^{A}) \propto P_t(\hat{\mu}^{A})P(\xi_t \mid\hat{\mu}^{A}) \tag*{(23)}

Since transitions to the next states are realized according to the true dynamics μP\mu^P, the observed transitions do not provide crucial information to distinguish possible agent models. Instead, the agent’s model only affects the action policy. Thus, in each episode tt, after computing the policy induced by each possible model μ^A∈M\hat{\mu}^{A} \in\mathcal{M}, the log-likelihood term is determined by

log⁡(P(ξt∣μ^A))=∑h=1Hlog⁡(π^h(aht∣sht,μ^A))(24)\log\left(P(\xi_t \mid\hat{\mu}^{A})\right) = \sum_{h=1}^{H} \log\left(\hat{\pi}_h(a_h^t \mid s_h^t,\hat{\mu}^{A})\right) \tag*{(24)}

where (sht,aht,sh+1t)∈ξt(s_h^t, a_h^t, s_{h+1}^t) \in\xi_t.

Experiments

In this section, we present the simulation results. First, we introduce the evaluation metrics we use throughout the experiments to demonstrate how learning the agent’s misspecified model affects the contract design and how even small differences between the estimated and agent’s transition models may result in significant changes in contract payments. Specifically, we consider regret to measure the principal’s loss throughout their interaction, the Kullback–Leibler (KL) divergence between estimated transition model and the agent’s model to evaluate estimation accuracy, and mean squared error (MSE) between learned and optimal contracts.

We evaluate the performance using expected regret over TT episodes, which measures the cumulative loss of the principal because of the uncertainty about the agent’s transition model compared to the optimal solutions. The expected regret can be expressed as

RT=∑t=1T∣VP∗−VP(⋅∣π^t,bt)∣(25)R_T = \sum_{t=1}^{T} \left|V^{P*} - V^P(\cdot\mid\hat{\pi}^t,b^t)\right| \tag*{(25)}

where VP∗V^{P*} represents the principal’s optimal value under the optimal contract b∗b^* and the optimal policy π∗\pi^*, which is obtained through the steps in § 3 when the agent’s transition model is known, btb^t denotes the contract offered by the principal and π^t\hat{\pi}^t denotes the agent policy to induce for the principal by the estimated agent’s transition model μ^A\hat{\mu}^{A} in episode tt. We use the absolute value since the principal’s realized utility is not always lower than VP∗V^{P*}. As shown in Figure 2, misspecified beliefs may enable the principal to achieve higher utility than in the same belief setting. Moreover, under model mismatch, a contract computed using the estimated agent model may result in a higher principal value than a contract computed based on any other agent’s transition model.

In each episode, to measure how the principal accurately estimates the agent’s model, we compute the KL divergence between the agent’s true transition model μA\mu^A and the estimated one μ^A\hat{\mu}^A. For every state action pair (s,a)(s,a), we have the next state distribution and compute the average KL divergence over all pairs as

DKL(μA∥μ^A)=1H∣A∣∣S∣∑h∈[H]∑s,s′∈S∑a∈AμhA(s′∣s,a)log⁡(μhA(s′∣s,a)μ^hA(s′∣s,a))(26)D_{\mathrm{KL}}(\mu^A \mathbin{\|} \hat{\mu}^A) = \frac{1}{H|\mathcal{A}||\mathcal{S}|}\sum_{h\in[H]}\sum_{s,s'\in\mathcal{S}}\sum_{a\in\mathcal{A}}\mu_h^A(s'\mid s,a)\log\left(\frac{\mu_h^A(s'\mid s,a)}{\hat{\mu}_h^A(s'\mid s,a)}\right) \tag*{(26)}

where ∣S∣|\mathcal{S}| and ∣A∣|\mathcal{A}| are the number of states and actions, respectively.

Furthermore, since the principal updates its posterior estimate over the set of possible agent models, we also evaluate the KL divergence between the agent’s and the estimated models using the posterior distributions over the set. Thus, the KL divergence with the posterior is defined as follows:

DKLposterior(μA∥M)=1H∣A∣∣S∣∑h∈[H]∑s,s′∈S∑a∈AμhA(s′∣s,a)log⁡(μhA(s′∣s,a)∑μ^A∈MPt(μ^A)μ^hA(s′∣s,a))(27)D_{\mathrm{KL}}^{\mathrm{posterior}}(\mu^A \mathbin{\|}\mathcal{M}) = \frac{1}{H|\mathcal{A}||\mathcal{S}|}\sum_{h\in[H]}\sum_{s,s'\in\mathcal{S}}\sum_{a\in\mathcal{A}}\mu_h^A(s'\mid s,a)\log\left(\frac{\mu_h^A(s'\mid s,a)}{\sum_{\hat{\mu}^A\in\mathcal{M}}P_t(\hat{\mu}^A)\hat{\mu}_h^A(s'\mid s,a)}\right) \tag*{(27)}

To evaluate how much the learned contracts differ from the optimal one, we compute the MSE between the learned contract bb and the optimal payments b∗b^*, which is defined as

MSE⁡(b∗,b)=1H∣S∣2∑h∈[H]∑s,s′∈S(bh∗(s,s′)−bh(s,s′))2(28)\operatorname{MSE}(b^*,b) = \frac{1}{H|\mathcal{S}|^2}\sum_{h\in[H]}\sum_{s,s'\in\mathcal{S}}(b_h^*(s,s')-b_h(s,s'))^2 \tag*{(28)}

To construct a finite set of candidate agent transition models, we generate transition probabilities by sampling from a Dirichlet distribution centered around a combination of the agent’s model and the true transition dynamics. For any s∈Ss \in\mathcal{S}, a∈Aa \in\mathcal{A}, and step hh, we sample

μh(⋅∣s,a)∼Dirichlet⁡(α(εμhA(⋅∣s,a)+(1−ε)μhP(⋅∣s,a)))(29)\mu_h(\cdot\mid s,a) \sim\operatorname{Dirichlet}\left(\alpha\left(\varepsilon\mu_h^A(\cdot\mid s,a) + (1-\varepsilon)\mu_h^P(\cdot\mid s,a)\right)\right) \tag*{(29)}

where α>0\alpha> 0 is the concentration parameter of the Dirichlet distribution, controlling how closely the sampled transition probabilities are concentrated around the given distribution and ε∈[0,1]\varepsilon\in[0,1] determines the influence of the agent’s model and true dynamics. For example, if ε=1\varepsilon= 1, then the sampled distribution is concentrated on the agent’s transition model.

We consider a PAMDP setting with ∣S∣=5|\mathcal{S}| = 5, ∣A∣=3|\mathcal{A}| = 3, ρ0=Unif⁡(S)\rho_0 = \operatorname{Unif}(\mathcal{S}) and T=200T = 200. The agent and true transition models are randomly generated and remain fixed throughout the experiments. The rewards and costs are also randomly generated from [0,1][0,1], and the contract payments are bounded within [0,2][0,2]. We note that all results are averaged over 20 trials.

Figure 3 and Figure 4 compare the effect of the time horizon HH on learning the agent’s transition model when all sets contain μA\mu^A and μP\mu^P. We construct five different model sets by fixing α=102\alpha= 10^2 and varying the coefficient ε∈{1,0.75,0.5,0.25,0}\varepsilon\in\{1, 0.75, 0.5, 0.25, 0\}, respectively, from Set 1 to 5. Each set contains 300 transition models, 150 randomly generated models, μA\mu^A, and μP\mu^P, while the remaining models are sampled from the Dirichlet distribution described above. We note that the average KL divergence between the true dynamics and the agent’s model, DKL(μP∥μA)D_{KL}\left(\mu^P \mathbin{\|} \mu^A\right), is 0.41 for Figure 3 and 0.40 for Figure 4.

Comparison of different model sets containing the agent’s transition model

Figure 3. Comparison of different model sets containing the agent’s transition model μA\mu^A for H=3H = 3

Comparison of different model sets containing the agent’s transition model

Figure 4. Comparison of different model sets containing the agent’s transition model μA\mu^{A} for H=1H = 1

In Figure 3, we set H=3H = 3, whereas in Figure 4, H=1H = 1. With a higher number of interactions in each episode, the principal is able to distinguish the agent’s transition model more easily, and the KL divergence with the posterior consistently converges to μA\mu^A across all sets, as shown in Figure 3. In contrast, in Figure 4, the principal observes only one transition per episode, which may lead to insufficient exploration of some states and actions in some trials. Since some of the state action pairs are rarely or never visited by the agent, some models may induce similar likelihoods over the observed trajectories. Consequently, when they interact for fewer steps in each episode, it may result in convergence to a suboptimal posterior by assigning a positive probability to some suboptimal models. We also observe that even small differences in transition probabilities may result in significant loss for the principal, which means that models with similar KL values may lead to different performance, while models with larger KL divergence can still achieve comparable results.

Furthermore, we present additional experiments for model sets which do not contain the agent’s true transition dynamics μA\mu^A, as shown in Figure 5, to investigate whether the posterior distribution converges to the model that is closest to the agent’s model. We consider sets of models constructed in the same style as those in Figure 3, except that μA\mu^A is excluded from the sets. We note that DKL(μP∥μA)D_{KL}\left(\mu^P \mathbin{\|} \mu^A\right) is 0.36 and the closest model to μA\mu^A has KL divergence of 0.002 for all sets.

Comparison of different model sets that do not contain the agent’s transition model

Figure 5. Comparison of different model sets that do not contain the agent’s transition model μA\mu^{A} for H=3H = 3

Since the agent’s model is not in the sets, exact convergence to the agent’s model, as observed in Figure 3 and Figure 4, is no longer possible. Thus, we update the posterior using a Boltzmann softmax policy with a temperature parameter of 1 to obtain a meaningful belief distribution over the model set while keeping the rest of the learning procedure unchanged. The results demonstrate that Set 1, which contains models closer to μA\mu^{A}, achieves lower regret, but also results in larger fluctuations in the contract distance and the KL divergence, since this set contains more candidate models similar to μA\mu^{A}, making the posterior distribution less concentrated. We observe a decreasing trend in the KL divergence and contract distance as the closest model consistently maintains a positive posterior probability. On the other hand, as shown in the KL divergence plot, multiple models maintain positive posterior probabilities throughout the learning process, preventing convergence in KL divergence and contract distance.

Consequently, when the sets contain the agent’s transition model, we observe convergence in the plots as long as the principal and agent interact sufficiently. In contrast, when the agent’s model is excluded from the sets, such convergence is no longer guaranteed. Our experiments show that while KL divergence and contract distance provide useful insight into the learning process, they do not fully capture the effectiveness of the learning approach. In particular, regret provides a more informative measure of performance. We also observe across all three experiments that Sets 1 and 2, which contain models closer to the agent’s transition model, consistently yield lower regret for the principal. We conclude that accurately learning the agent’s dynamics is essential to design effective contracts and provide incentives under belief mismatch.

Discussion

In this work, we study a PAMDP setting with model misalignment where the principal and the agent have different beliefs on transition dynamics. We investigate how this mismatch affects the contract design. In particular, we consider the setting where the principal has access to a set of possible agent transition models and designs contracts by learning the agent’s model through repeated interactions. Our experimental results show that accurately estimating the agent’s transition model is essential for effective contract design. As the principal’s estimate converges to the agent’s model, the learned contracts approach the optimal contracts computed under perfect information, and thus the principal incurs lower regret. Moreover, the experiments demonstrate that even small differences in learning the agent’s model may result in noticeable changes in contract payments and the principal’s loss. In future work, our aim is to extend our analysis to continuous model spaces and analyze how contracts can be used to estimate the misaligned belief of the agent. Moreover, an important extension is to establish theoretical guarantees for this learning framework. Finally, many PAMDP settings consider that the principal cannot directly observe the agent’s actions. Extending our approach to such settings would be an interesting direction, as it has additional challenges in learning the agent’s model and contract design.

References

  1. [1]Tal Alon, Paul Dütting, Yingkai Li, and Inbal Talgam-Cohen. Bayesian Analysis of Linear Contracts, July 2023. arXiv:2211.06850 [cs, econ].
  2. [2]Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning optimal contracts: How to exploit small action spaces. In International Conference on Learning Representations, volume 2024, pages 11944–11970, 2024.
  3. [3]Omer Ben-Porat, Yishay Mansour, Michal Moshkovitz, and Boaz Taitler. Principal-Agent Reward Shaping in MDPs, December 2023. arXiv:2401.00298 [cs].
  4. [4]Matteo Bollini, Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Contracting With a Reinforcement Learning Agent by Playing Trick or Treat, October 2024. arXiv:2410.13520 [cs].arxiv.org/abs/2410.13520
  5. [5]Patrick Bolton and Mathias Dewatripont. Contract theory. MIT Press, Cambridge, MA Londin, England, 2005.
  6. [6]Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Multi-Agent Contract Design: How to Commission Multiple Agents with Individual Outcomes. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 412–448, London United Kingdom, July 2023. ACM.DOI
  7. [7]David Molina Concha, Kyeonghyeon Park, Hyun-Rok Lee, Taesik Lee, and Chi-Guhn Lee. Algorithmic Contract Design with Reinforcement Learning Agents, August 2024. arXiv:2408.09686 [cs].
  8. [8]Christos Dimitrakakis, David C. Parkes, Goran Radanovic, and Paul Tylkin. Multi-view decision processes: the helper-AI problem. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS ’17, pages 5449–5458, Red Hook, NY, USA, 2017. Curran Associates Inc.
  9. [9]Ilgin Dogan, Zuo-Jun Max Shen, and Anil Aswani. Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards, August 2023. arXiv:2308.06717 [cs, stat].
  10. [10]Ilgin Dogan, Zuo-Jun Max Shen, and Anil Aswani. Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents, May 2023. arXiv:2304.07407 [cs, stat].
  11. [11]Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-Agent Contracts, November 2022. arXiv:2211.05434 [cs].
  12. [12]Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-Agent Combinatorial Contracts, May 2024. arXiv:2405.08260 [cs].
  13. [13]Paul Dütting, Michal Feldman, and Inbal Talgam-Cohen. Algorithmic Contract Theory: A Survey, December 2024. arXiv:2412.16384 [cs].
  14. [14]Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus Optimal Contracts. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 369–387, Phoenix AZ USA, June 2019. ACM.
  15. [15]Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. The Complexity of Contracts, February 2020. arXiv:2002.12034 [cs].
  16. [16]Ignacio Esponda and Demian Pouzo. Equilibrium in misspecified markov decision processes. Theoretical Economics, 16(2):717–757, 2021.arxiv.org/abs/1502.06901
  17. [17]Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Generalized Principal-Agency: Contracts, Information, Games and Beyond, February 2024. arXiv:2209.01146 [cs].arxiv.org/abs/2209.01146
  18. [18]Sanford Grossman and Oliver Hart. An analysis of principal-agent problem. Econometrica, 51:7–45, 01 1983.
  19. [19]Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Joshua R. Wang, and S. Matthew Weinberg. Contracting with a Learning Agent, January 2024. arXiv:2401.16198 [cs, econ].
  20. [20]Guru Guruganesh, Jon Schneider, and Joshua R. Wang. Contracts under Moral Hazard and Adverse Selection. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 563–582, Budapest Hungary, July 2021. ACM.arxiv.org/abs/2010.06742
  21. [21]Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 359–376, Palo Alto California USA, June 2014. ACM.
  22. [22]Dima Ivanov, Paul Dütting, Inbal Talgam-Cohen, Tonghan Wang, and David C. Parkes. Principal-Agent Reinforcement Learning, July 2024. arXiv:2407.18074 [cs].arxiv.org/abs/2407.18074
  23. [23]Jean-Jacques Laffont and David Martimort. The Theory of Incentives: The Principal-Agent Model. Princeton University Press, December 2009.
  24. [24]Yingkai Li and Argyris Oikonomou. Dynamics and contracts for an agent with misspecified beliefs. arXiv preprint arXiv:2405.20423, 2024.arxiv.org/abs/2405.20423
  25. [25]Tao Lin and Yiling Chen. Generalized Principal-Agent Problem with a Learning Agent, October 2025. arXiv:2402.09721 [cs].arxiv.org/abs/2402.09721
  26. [26]Jibang Wu, Siyu Chen, Mengdi Wang, Huazheng Wang, and Haifeng Xu. Contractual Reinforcement Learning: Pulling Arms with Invisible Hands, July 2024. arXiv:2407.01458 [cs].arxiv.org/abs/2407.01458
  27. [27]Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I Jordan. The sample complexity of online contract design. arXiv preprint arXiv:2211.05732, 2022.arxiv.org/abs/2211.05732
  28. [28]Banghua Zhu, Sai Praneeth Karimireddy, Jiantao Jiao, and Michael I. Jordan. Online Learning in a Creator Economy, May 2023. arXiv:2305.11381 [cs].arxiv.org/abs/2305.11381

Paper details

vlnc:W_yj8mjmjz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents