Optimal Robust Subsidy Policies for Irrational Agent in Principal-Agent MDPs
Authors: Bowen Hu
Yixin Tao
Venue: ICLR 2026 Poster (2026)
Keywords: Principal-Agent Problem
Markov Decision Process
Reinforcement Learning
Primary area: reinforcement learning
TL;DR: We analyze robust subsidy schemes for principal–agent MDPs with boundedly rational agents.

Abstract: We study a principal-agent problem in a Markov Decision Process where the principal provides subsidies to influence the agent's policy, which in turn determines the accrued rewards. Our focus is on designing a robust subsidy scheme that maximizes the principal’s cumulative expected return, even when the agent displays bounded rationality and may deviate from the optimal action policy after receiving subsidies.

As a baseline, we first analyze the case of a perfectly rational agent and show that the principal’s optimal subsidy coincides with the policy that maximizes social welfare, the sum of the utilities of both the principal and the agent. We then introduce a bounded-rationality model: the globally $\epsilon$-incentive-compatible agent, who accepts any policy whose expected cumulative utility lies within $\epsilon$ of the personal optimum. In this setting, we prove that the optimal robust subsidy scheme problem simplifies to a one-dimensional concave optimization, revealing that optimal subsidies concentrate along social-welfare-maximizing trajectories. We also bound the associated loss in social welfare. Finally, we investigate a finer-grained, state-wise $\epsilon$-incentive-compatible model. In this setting, we show that under two natural definitions of state-wise incentive-compatibility, the problem becomes intractable: one definition results in a non-Markovian agent action policy, while the other renders the search for an optimal subsidy scheme NP-hard.

Published as a conference paper at ICLR 2026
OPTIMAL ROBUST SUBSIDY POLICIES FOR IRRA- TIONAL AGENT IN PRINCIPAL-AGENT MDPs
Bowen Hu', Yixin Tao
The Engineering& Technical College of Chengdu University of Technology
hubowen ustt..c.... edu en
2 Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics
taoyixineman 1. shufe. edu.
ABSTRACT
We study principal-agent problem in a Markov Decision Process where the prin- cipal provides subsidies to influence the agent's policy, which in turn determines the accrued rewards. Our focus is on designing robust subsidy scheme that max- imizes the principal's 's cumulative expected return, even when the agent displays bounded rationality and may deviate from the optimal action policy after receiving subsidies.
As a baseline, we first analyze the case of a perfectly rational agent and show that the principal's optimal subsidy coincides with the policy that maximizes social welfare, the sum of the utilities of both the principal and the agent. We then in- troduce bounded-rationaliis model: the globally cincentive-compatible agent, who accepts any policy whose expected cumulative utility lies within of the per- sonal optimum. In this setting, we prove that the optimal robust subsidy scheme problem simplifies to a one-dimensional concave optimization, revealing that op- timal subsidies concentrate along bound the associated loss in social welfare. Finally, investigate a finer- finererained, state-wise poncentiveccompatbbee model. In this setting, we show that under two natural definitions of state-wise incentive-com incentivecoompatiiillyy. the problem becomes in- tractable: one definition results in a non-Markon Markovian agent action policy, while the other renders the search for optimal subsidy scheme NP-hard.
-itffaar-maimizzingggg trajectories. We also
INTRODUCTION
The principal-agent problem (often modeled as Stackelberg game) has long been central to the study of strategic interactions where one party acts on behalf of another, yet with potentially mis- aligned incentives. This setting arises frequently in economics and governance: for example, gov- ermments design tax credits, subsidies, and public investments to guide individual behavior toward socially beneficial outcomes, even though market participants ultimately maximize their own private utility. A similar dynamic appears in machine learning, where reinforcement learning with human feedback (RLHF) is employed to align large language models (LLMs) with societal values such as ethics and legal compliance. In both cases, the principal faces the fundamental challenge of shaping an agent's behavior without direct control, while respecting both parties' interests.
In this paper, we investigate the principal-agent problem within the framework of a Markov Decision Process (MDP), where the principal can provide subsidies to influence the agent's action choices. More specifically, in our setting, each action under each state yields two distinct rewards: one for the principal and one for the agent. The principal may also assign non-negative subsidies actions. The agent selects an action policy based on its own reward combined with subsidies offered by the principal. The principal, in turn, strategically designs these subsidies to influence the agent's choices, aiming to maximize the principal's overall payoff, which equals the total principal's 's reward associated with the agent's ' chosen action minus the subsidies provided.
"Corresponding author.

---

Published as a conference paper at ICLR 2026
("I. 0, 1)
0.7
(ap. 0,2)
S2
(az. 2, 0)
0.3
0.5
Ar
+
$1
Ar = +
(az, 2,
1)
83
(az,3, 3,0)
0.5
Ar = 2 +
Example of the principal-agent problem. Solid arrows represent actions, annotated with triplets denoting the action index, principal reward, and agent reward, respectively. For example, (a2, 2, 1) indicates that the agent taking action 02 yields reward of 2 for the principal and for the agent. Under subsidy of + 5, the agent's ss reward for selecting increases to 2 + 5, while the principal's 's reward decreases to
Figure 1:
We provide simple illustrative example of such an MDP with three states, where two distinct actions are available each state, in Figure II A natural assumption in such models is that the agent always behaves rationally, selecting the policy that maximizes the sum of the agent's reward and the subsidies provided by the principal. Thus, in the absence of subsidies, the agent would consistently select action a (highlighted in blue) across all states, yielding an expected agent value of 3.3, but resulting in a value of 0 for the principal. To improve this outcome, the principal introduces subsidy scheme Ar targeting the red-marked actions with an infinitesimal amount & > O. Consequently, the agent is incentivized to select d2 in all states, yielding an expected agent value of 3.3 + 26. Meanwhile, such subsidy increases the principal's expected utility to 2 26.
However, the validity of the above example hinges entirely on the agent's 's strict adherence to opti- mal behavior. practice, the rationality assumption of agent is often violated: agents may deviate from perfect rationality due to bounded cognition, incomplete information, or limited computational power. For example, in economics, individuals may fail to optimize utility precisely because of un- certainty or behavioral biases. Similarly, in reinforcement learning. approximate training algorithms may yield suboptimal policies due to limited exploration or finite computation.
Motivated by these considerations, ask:
How should the principal design subsidies when the agent may behave irrationally?
Our goal to identify robust subsidy scheme that guarantees the principal the best possible expected cumulative return in the worst-case scenario.
Our Contributions We introduce a theoretical framework based on Markov Decision Processes (MDPs) to model the principal-agent problem and formulate the design of an optimal robust subsidy scheme as a minimax optimization problem. Within this framework, we systematically analyze three agent models: the perfectly rational agent, the globally --incentive-compatble (IC) agent, and the state-wise e-IC agent. For each model, we provide structural insights and algorithmic solutions.
We first study a perfectly rational agent as a baseline, who always selects actions that maximize its own utility. In Theorem 3.1. we characterize the optimal subsidy scheme and show in Proposition 3.2 that it suffices subsidize only actions that maximize social welfare, defined the sum of the principal's 's and agent's utilities. Under this scheme, the agent's 's best-response policy aligns with the social welfare-mann maximizing policy, establishing a clear benchmark for incentive alignment.
Next, we consider globally c-IC agents, who tolerate at most an c loss relative to their optimal reward under given subsidy scheme, Unlike perfectly rational agents, these agents may adopt stochastic policies, making the principal's optimization nontrivial bi-level problem. Theorem 4.1 shows that this problem can be equivalently reduced to maximizing a one-dimensional concave function over bounded interval, allowing efficient solution via standard first-order methods. Structurally, in Proposition 4.2, we show the optimal subsidy mirrors the perfectly rational case by exclusively rewarding actions that align with maximizing social welfare; and, in the worst-case response, the
2

---

Published as a conference paper at ICLR 2026
agent's policy will assign positive probability to the socially optimal actions, though it may also mix with other actions. We further provide a quantitative analysis of the gap between the total payoff achieved under this robust scheme and the maximum possible social welfare, as shown in Proposition 4.3
Finally, in Section each individual state. Two natural formalizations arise, each presenting distinct challenges. In the first formalization, the agent's worst-case response may necessitate non-Markovian policy, thereby violating the foundational assumptions of the MDP framework and introducing history dependence that makes the problem computationally intractable. worst-case response remains polynomial- timemomial-tmme computable. Theorem [..] demonstrates that the prin- cipal's problem becomes NP-hard. These findings illustrate that, although state- wise constraints are conceptually appealing, they introduce significant computational and modeling complexities that limit practical applicability.
examine state-wise c-IC agents, for which the c-tolerance must hold
the second formalization, while the agent's
Related work The prineipal-agent problem, a central concept in economics (Ross)
1973 Gross-
man & Hari 1992), arises when principal delegates tasks an agent whose actions may be guided by self-interest. This framework underpins both contract theory (Laffont Maskin 1981 Guru-
ganesh et al. 2021 and mechanism design (Myerson 1982 Kadan et al. 2017).
Recent work has examined this problem in the setting of Markov Decision Processes (MDPs). Re- search in this area falls into two broad directions. The first, information design, seeks to influence the agent's 's beliefs, as in Bayesian persuasion (Gan et al. [022a 2023 Wu et al. [022] Bernasconi et a 2023). The second, more closely aligned with work, focuses on shaping the agent's 's incentives through policy teaching (Zhang & Parkes) 2008 |Banihashem et al., (022) or environment/model
design (Thoma et al. 2024 Yu Ho 2022). A comprehensive survey is provided by Dütting et al. (2024).
In this paper, we specifically focus on how the principal uses extra payments to guide the agent's behavior. A related literature is steering agents in games by payments, which studies how principal uses subsidies to induce outcomes multi-player games. Monderer Tennenholtz (2003) intro- duced k-implementation to realize a desired outcome set by committing to non- non-negatvve transfers. More recently, focusing on the steering problem for no-regret learners, /Zhang et al. (2023) showed how mediator can payments to guide agents toward a desired equilibrium. Building Zhang et al. (2025) then introduced a method where a principal uses payments to learn agent utility functions from repeated play, thus providing path to steering even without prior knowledge of the utilities.
this,
Among these, two approaches are most closely related our study:
Contract-based models. This line of research integrates contract theory with MDPs, assuming the principal observes only states and offers state-dependent payments. Prior studies analyze subgame
perfect equilibrium (Wu et al. 2024: [vanov et al. 2024). showing that history- -epoodde contracts
necessary for farsighted agents (Bollini et al. 2024). These works typically assume perfectly
rational agents and establish that the optimal contract design problem is NP-hard.
Reward design. In Reward shaping, the principal modifies the agent's incentives via additional rewards for specific state-action pairs. The principal's goal is to minimize the final cost (Gan et al. 2022b) or subject to fixed budget (Ben-Porat et al., (2024). with the design problem remaining NP- hard. Extensions address behavioral uncertainty through robust reward design (Wu et al.) 2025). In contrast, we incorporate incentive costs directly into the principal's objective, treating them as part of payoff optimization rather than an external constraint.
PROBLEM FORMULATION
The Principal-Agent MDP Model We consider a principal-agent problem modeled as a time- finite-horizon Markov Decision Process (MDP). In this setting, the principal aims
inhomogeneou [
For clarity, tamme-inomogeenooe implies that the MDP's transitions and policies depend on the current state and timestep. This is distinct from non-Markovian (or history-dependent) settings, where dynamics depend on the sequence of past states and actions.
3

---

Published as a conference paper at ICLR 2026
to achieve goal by influencing agent's actions. The principal can offer subsidies to incentivize the agent to follow a policy that benefits the principal.
Formally, define the problem instance using the tuple M (S, A, H.P.P.,,A 8), where:
S is the set of the finite states and A is the set of actions. We assume that both states and actions are discrete.
= [0,1, ................................ . - 1) is the set time steps, with H representing the time horizon. P:
+ ((S) is the transition kernel, where P(s'|s. s, a, hi) indicates the proba- biliity of transferring to state s' S after executing action A in state S at timestep h E H.
TP,TA: : x H + R are the reward functions of the principal and the agent, respec- tively, where rp(s, a,, h) (resp. (s a, h)) denotes the reward obtained by the principal (resp. agent) when the agent executes action a E A in state E S at timestep h E H.
Without loss of generality, 8 is the fixed starting state for the agent.
Subsidy Scheme and Action Policy A process is called Markovian if it depends solely on its current state, independent of its past trajectory. Conversely, a process non-Markovian if it can depend on historical states, i.e., it possesses "memory". While we consider both Markovian and non-Markovian policies, we begin by establishing the definitions within the Markovian framework. The principal commits to a subsidy scheme Ar S x A x H + Igz- Here, Ar(s, h)) is non-negative payment from the principal to the agent for taking action a in state at timestep h. We denote the set of all feasible subsidy policies as Ra.
Given a subsidy Ar on action a in state s at timestep h, the effective rewards for the principal and agent become ~ Tp Ar and A = - Ar. Once the agent observes the subsidy scheme, it chooses a Markovian action policy x S H + ((A). Based on the agent's (ir)rationality, for any given Ar, the agent will choose policy from specific set of feasible policies, which is denoted by II(Ar).
Value Functions To avoid redundancy, we first define the value functions for a generic reward signal u S x Ax x H - R. Then, the Bellman expectation operator To maps next-step value function Vi+1 to the current nction-value function:
(TvV)
al), P(s
s'ES
Based on this, we define the generic state-value V*." and action-value TT."" backward from h H to O, with Va H) = 0:
(=*"(sa,h)) (T)v a, h), where V=."(sh)) E (Q (T. a, h)].
Similarly, we define the Bellman optimality operator and the corresponding optimal values V and Q+.a a by replacing the expectation over with maximization:
(s, a,,,,,h) (Ta (T.V (x, (s,a, h),, where V*, = max (s,"
Then, for any player i E {P, under a subsidy scheme Ar, the standard value functions for player i are simply instances of the generic definition with r denoted as V. and A.T.Ar The agent's optimal value functions given subsidy scheme Ar, denoted as v and QAr correspond to Verr" and Q
Social Welfare We define social welfare as the aggregate reward of both the principal and the Tew rp TA which is invariant to the subsidy scheme Ar. Given the action policy m the social welfare value functions V and Q correspond to the generic values with u = rsw- Similarly, the optimal social welfare values V and Q;,, correspond to the optimal generic values with u Tow- An action a is secial-welaarremmmaiiiiinngg E arg max D (8. lt).
agent:
is greedy with respect to Q i.c.,
4

---

Published as a conference paper at ICLR 2026
Optimization Objective We consider robust formulation where the principal seeks subsidy scheme that performs best against the agent's 's worst-case response. The agent's s adversarial action policy subsidy Ar is an agent policy Tar that minimizes the principal's 's expected return within the feasible set IT(Ar) which models agent's rationality:
TAr E arg min Vp V.. (8, rell(Ar)
The principal's objective is to find the optimal subsidy scheme Ar" that maximizes this worst-case outcome. The optimal value for the principal is therefore:
- max min V Vr. (s,h OPT
(2.1)
ArERA nell(Ar)
Non-Markovian setting In non-Markovian setting, both principal and agent can make decision based on the whole history rather than the current state. Formally, a trajectory is a sequence of states and actions of length I', denoted as ($1, a1, $2, 42, ST-1, 0r-1, ST). Let 7 be the set of all trajectories. Unless otherwise specified, we assume that all trajectories originate from the fixed initial state 8. Building on this, the Man-Markovian subsidy scheme and action policy are defined by substituting the state and timestep dependency with the trajectory, i.c., Ar: : T A + R>0 and T ((A). In addition, under non-Markovian policies, the corresponding value function is also history-dependent e.g., (T) and (T). We note that though we mainly analyze in the Markovian setting, all positive results can be extended to non-Markovian setting.
3 WARM-UP: THE PERFECTLY RATIONAL AGENT
We begin with the simplest setting of perfectly rational agent, defined agent that seeks to maximize cumulative reward. Although this scenario conceptually straightforward, provides a crucial foundation for the subsequent analysis of more complex, irrational agents. We formalize this concept as follows.
Definition 3.1 (Perfectly Rational Agent). Given subsidy scheme Ar, the action policy Tl of a perfectly rational agent satisfies the constraint
VĀ ( 05 (s,h (
Tie-breaking Rule A tie-breaking rule dictates the agent's choice when multiple actions yield identical rewards. In this setting with a perfectly rational agent, assume that when two options provide the same personal reward, the agent selects the more cooperative action, that is, the one that benefits the principal more. For example, consider a single state with actions. Both give the agent a reward of 0, but the principal receives 2 for the first action and 0 for the second. Even a negligible subsidy on the first action makes strictly preferred. As the subsidy approaches zero, the agent's 's choice remains the action with higher principal value. Thus, tie-breaking systematically favors actions that increase the principal's payoff. This assumption allows for a tractable proof of optimality in this section, but it is important to note that we will not rely on this rule in the more general frameworks developed later the paper.
3.1 OPTIMAL SUBSIDY SCHEME
With the definition of perfect rationality, now address the problem of determining the optimal subsidy scheme Ar*. The following theorem characterizes the principal's optimal payoff and the optimal subsidy scheme. Detailed proof is deferred Appendix A.3.
Theorem 3.1 (Optimal Subsidy Scheme). For perfectly rational agent, the principal's optimal payoff given by
V - (2.
that is, the maximum attainable social welfare (over all action policies) minus the maximun reward the agent can obtain in the absence of subsidies. Furthermore, there exists optimal subsidy scheme Dr such that, for every state-action triple (s, a, h)),
Ar" (s,
V
h) QA Ar= (8)
(3.1)
5

---

Published as a conference paper at ICLR 2026
Proof Sketch. The prineipal's optimal payoff bounded above by (8, h = 0) v 0), since the total value of the principal and agent cannot exceed the maximum possible social welfare, and the agent will not accept less than their stand-alone value without subsidies. This upper bound is achieved under the subsidy scheme Ar" defined in equation (3.Ip. Under this scheme, the agent's adjusted Q-values are equalized across all actions: QA" (s.a,h) - (s, h) for all (s, a, ft). Thus, the agent is indifferent among all actions. Our provisional tie-breaking rule then ensures the agent selects actions that maximize the principal's reward, allowing the principal's payoff to exactly reach the upper bound.
(8,
Although Theorem 3.1 identifies an optimal subsidy scheme that provides transfers on nearly all actions, the following proposition shows that, to achieve optimal rewards, the principal needs to subsidize only the woiil--wllarremmxxmmie A.4.
actions. The detailed proof is deferred to Appendix
Proposition 3.2 (Social Welfare). There exists an optimal subsidy scheme aw that assigns posi- tive transfers exclusively to www.awe--axiiiiaaaeeee actions. Under Arwo the agent implements social welfare-maximizing agent policy Tyw, allowing the principal to attain the maximum achiev- able social welfare.
4 OPTIMAL POLICIES FOR GLOBALLY 6-IC AGENTS
When an agent is no longer perfectly rational, the optimality of its response ceases to be the sole factor guiding its decisions. model such bounded rationality, natural approach is assume that the agent can tolerate a maximum reward loss of in line with the classical notion of e-incentive compatibility (IC). However, since we are dealing with sequential decision-making, several interpre- tations of 6-IC are possible. Here, we focus on the so-called globally e-IC agent, which constrains only the cumulative reward loss over the entire decision horizon.
Definition 4.1. An agent is globally e-IC agent if and only if. given subsidy scheme Ar, the action policy π E 11 Ar) satisfies
VT A (8
(5, 0) -c
4.1 OPTIMAL SUBSIDY SCHEME
We now consider the problem of determining the optimal subsidy scheme Art. Unlike the perfectly rational case, the agent's best-response policy may be stochastic. To handle this, we reformulate the objective 2.1 using occupancy measures. Specifically, let p(s, a, denote the probability that the agent takes action a in state s at timestep h. Replacing the policy æ with its corresponding occupancy measure μe, the optimization problem becomes
max min ArERa HEM(Ar) s.a.h
Σ m(s a, h)(rp(ss, Ar(s,a,
(4.1)
where M( is the set of occupancy measures satisfying the following constraints:
Initial state:
Σ u( 0) 1,
Σ En(s,a, 0) Vs +
(4.2a)
Transition:
Σ u(s,a,h)) = Σ -
1),
(4.2b)
s'.a'
Non-negativity: u(s,a,h) 20
(4.2c)
Global e-IC:
Σ p(s,a, (i Ar(s,,, > V (8, 0) - 8.0.h
(4.2d)
Directly solving this program is challenging for two main reasons. First, the feasible set of is not fixed but depends on the choice of Ar, creating a coupling between the inner and outer variables that distinguishes setting from standard minimax formulations. Second, defining f(Ar)

---

Published as a conference paper at ICLR 2026
miAne Es..h pls, a.s,,,,))rra (r,)))())(sss a, ar(s,a,)) h)) shows that f(Ar) is not concave in Ar (see Appendix 1.2.1 for example). Consequently, the outer problem maxar f(Ar) is not concave maximization, which rules out standard convex optimization methods.
In our main theorem, show the problem can be reformulated to one-dimensional concave optimization (Theorem 4.1). The approach leverages the dual of the inner optimization problem and swaps the order of optimization between the subsidy scheme Ar and the dual variables (a, V). The optimal subsidy scheme can then be expressed as the difference between the V-function and Q-function, analogous the perfectly rational case.
Theorem 4.1. The optimization problem (4.1) l is equivalent to maximizing a concave F(z), formulated as
x
max x.
F(x) - vV (s, 0) (s. = 0) 1
where, for each state 8 and timestep h, (s, h) m { { Nm (s, h) -Vp (s, h1.
Furthermore, for an optimal x², there exists an optimal subsidy scheme Ar" such that Ar' h) (2, Q2,
(4.3)
where Q (s, a. h) e x² rm (s, - ap(s,,,)) + Eves P(s'ls, (8', +
Proof. We begin by considering the inner program over the state-action occupancy measure μ for fixed subsidy scheme Ar. This program is linear program. By introducing dual variables a E R2 for the globally e-IC constraint (4.2d) and V E [ for the transition (4.2a) and initial state 4.2b) constraints, we can express the problem in its dual form. Combining this with the outer maximization over Ar, and V yields the following optimization problem:
V(s, = 0) ae + av (8, h 0)
max ATERA.020.V
such that ((s, h) S rr(ss, a, a a, -)-()++10 (1)))(()rssss..... a, h)+ Ev's a WV h+1) for any 8 E E. E A, and H: and with the terminal condition V(s, H) = 0 for any state a S.
Next, we exchange the order of maxArER and maxx20,v and analyze maximization over Ar for fixed V and a. Notice that the objective is non-decreasing with respect to Ar, since V (s, h 0) represents the maximum value attainable by the agent under the subsidy Ar. Additionally, the constraints impose an upper bound on each Ar(s. a.
1 Ar(s, a, h) < I+a (
h(s,h)+ + P(dol,, + +rp(s, -ar.))))aar((s.. arx(s,o,
s'ES
Thus, the optimal choice for Ar is to take this upper bound, making the inequality hold with equal- ity. Given a and V, substituting the optimal choice of Ar, the RHS of the above inequality, into
A (8, 0) = max, Ex Σ H-1
r. (st, ae, 1) + Ar(s), (es,,a))))
gives
Ar V A (8, = 0) = max n
(rp(s), ar 1) (e,
1 Cx
Σ
V(se.
St11ES
V/ (8, 0) V 1 0)). 0)).
Substituting this back, the problem reduces to the following optimization problem. Note that the first constraint guarantces the feasibility of Ar.
max a20
I a V(s,h=
1 i V (8, 0) a6
s.t. V(s, h) E rr(ss h)) or a + Σ
1),
s'ES
V(s, H1 50

---

Published as a conference paper at ICLR 2026
Observing the inner optimization over ((s, h) coincides with form of minimizing cumulative reward
in an MDP with modified reward rp - QT 4- By letting x = 1+a
a and introducing V (s, h) equals
times the optimal value of (s, f),, the formulation equals
x
max ee
I Vis (8, h = 0) - (5, h =
x
where (8, _ (1 - x) min
Vp Vo.Ar= (3, 1 = 0)
x
VA
(8, 1 0)
1
max <
I pف (5, 0) - (s,
Restricting и to deterministic action policies does not change the value of (8, h = 0). and under this restriction, (s, h = 0) is the maximum of finitely many linear functions in x. the objective function is concave over the interval [0, 1).
Markovian vs. Non-Markovian In our framework. both the principal and the agent may adopt non-Markovian strategies. For example, the principal might determine subsidies based not only on the agent's 's current action but also on past actions. Similarly, in equation 4.. the agent could adopt a non-Markovian globally c-IC policy to reduce the principal's reward. Nevertheless, the following two key observations establish that it suffices to restrict attention to Markovian strategies.
First observation: Given Markovian subsidy scheme of the principal, there always exists Marko- vian globally e-IC policy for the agent that minimizes the principal's 's reward. This follows from the fact that the inner optimization problem in equation (4.1) is linear program. Any non-Markovian e-IC policy can be represented by an occupancy measure juss, a, h),, which specifies the probability of taking action in state at timestep h. Such occupancy measure can always be replicated by a Markovian policy, ensuring identical rewards for both the principal and the agent.
Second observation: Among all possible subsidy Markovian scheme specified in equation (4.3) is optimal. A non-Markovian scheme can be trans- formed into Markovian
Non-Markovian--tte
by augmenting the state space encode the relevant history. By Theorem 4.1 for each state-action pair in this augmented representation, the scheme in equation 4.3 coincides exactly with its Markovian counterpart.
Remark We briefly examine the boundary cases of x* and in Theorem 4.1 When 0, as x' + 1, the principal's value approaches ($, h = 0) V h 0). consistent with the tie- be-breaking rule in the perfectly rational case. This shows that the globally e-IC agent naturally generalizes the perfectly rational agent.
4.2 ACTION POLICY
According Theorem 4.1 the optimal subsidy scheme Ar" takes form similar to that in the perfectly rational case. The following proposition shows that the principal can still allocate positive transfers exclusively the to cooperate with the principal to a certain extent by choosing one policy Tsw with probability x², the optimal solution in Theorem 4. The detailed proof of the following proposition is deferred to Appendix A.5.
maximizingii actions. Furthermore, the agent is still willing
welffrr-mmxxiiizing agent
Proposition 4.2 (Optimal subsidy scheme and action policy). There exists optimal subsidy scheme Arw that assigns positive reward transfers solely to necial-welfare-maaxee Meanwhile, there exists a globally e-IC action policy Tarn. minimizing the principal's 's reward. which is the mixture of a a weight of at least x" on Tww-
actions.
wewlare-maximizze agent policy and one other action policy, placing
Proof Sketch. The proof relies on two key insights. First, under the optimal subsidy scheme Ar", the policy Tsw achieves the maximum agent expected cumulative reward, V (8, implies that sufficient provide subsidies only along the trajectories induced by kww. without affecting the optimal value for the principal. Second, there exists an action policy & whose agent
0). This
value falls below V (s, h = 0) e, which can be combined with Tww to form the globally e-IC policy Ar such that the dual of the global e-incentive compatibility constraint is tight.
n
8

---

Published as a conference paper at ICLR 2026
4.3 SOCIAL WELFARE
We define the social welfare gap dew as the difference between the maximum attainable welfare and the welfare achieved under the optimal subsidy scheme Ar*. When +00, the agent can effectively bypass the global e-IC constraint and freely select any action policy. In this limit, the welfare gap becomes 6sw V (8, h 0) ming (5, h 0). Our objective
characterize the upper bound on dsw and the rate at which social welfare declines as a function of c, particularly the regime where remains small. We first establish the following upper bound on &sw
Proposition 4.3. Given and the corresponding optimal solution x:" E (0, the social welfare gap is p - and upper bounded by O (vv))-
This O(Ve) bound can be achieved in certain specific cases (see Appendix A.2.2 for an example). However, in most cases, the social welfare gap dew exhibits two different growth rates-O(ve or deeeddepnn on whether V is differentiable at x². A concrete example is provided below, while detailed discussions are deferred Appendix A.6.1.
Example Consider a single-period scenario with three actions. For the first action, the principal's reward and the agent's reward is 3. For the second action, the principal's reward and the agent's 's reward is 2. For the third action, the principal's 's reward is and the agent's reward is Figure showsw that 6ew can grow at rates of O(e) and O (E))), corresponding to the cases in Figure where I remains constant and decreases at O(ve). Figure 2 depicts the piecewise- linear relationship between (s, h = 0) and x, where the constant-z value in Figure coincides with the break point of V2 (s, 0), non-differentiable point of the objective function.
50-
V. 60 hm 30 with reepect to.8
0.857
06
255
20-
6.
X"
0.500
0.500
decreases constant
00
00
04
66
(a) dew
(b) versus
(c) (3 0) versus
Figure 2: Curves of 6ew and x² versus when (2, is non-differentiable.
5 STATE- STATE-WISE E-IC AGENT
In this section, we examine the state-wise E-IC agent, which differs from the globally e-IC agent in that incentive compatibility is enforced locally each state and decision step. Intuitively, such an agent ensures that its chosen action remains within e of the best immediate value available at that decision point. While the idea is straightforward, constructing mathematically consistent and tractable formalization more subtle. We provide two definitions below.
Value-Consistent State-Wiss e-IC Agent We first define the value-consistent state-wise E-IC agent, where the agent's 's action at each state must approximate the optimal reward within e. Definition 5.1. An agent value-consistent state-wise e-IC agent if. under a subsidy scheme Ar, the induced policy E TT: (Ar) satisfies V AT,Ar(s, 2 VÂ (s. h) for all E S and h E H.
key challenge with this formulation that the agent's policy minimizing the principal's 's reward under given subsidy scheme may be non-Markovian. Specifically, consider the agent can apply a Man-Mvooviinn policy я such that for any trajectory т, V.. V...rrrr (r) 2 V (r) - e. In such cases, the agent's policy cannot be represented within polynomial size. Mcanwhile, from the perspective of the principal, the principal can gain extra value by applying the non- Markoovinn subsidy scheme principal further assume the agent is Mon-Markovian.

---

Published as a conference paper at ICLR 2026
To illustrate, consider the post-subsidy MDP in Figure 3 with 1. The rewards are: (i) action di at $1 yields 3.21 for the principal and for the agent; (ii) dg at 83 yields 0.21 and 1, respectively; and (iii) 0 otherwise. Under a Markovian policy, the agent steers from $1 8q and selects d2, limiting the principal's reward to 0.21. However, under a non-Markovian policy, we can split 83 into history-dependent states sg and sg. At sg. the agent always chooses d2 while at sg. it deterministically chooses the action other than ag. This drops the principal's expected reward to 0.105.
We further demonstrate that principal can gain more by applying the non-Markovian subsidy scheme: Consider the standard model where the principal applies Markovian subsidy scheme to Markovian agent. Calculations show the optimal subsidy targets only action with value 1, resulting in principal value of 0.71. the agent becomes non-Markovian but the subsidy remains unchanged, the principal's value falls to 0.605. However, by implementing non-Markovian scheme that includes an additional 0.1 subsidy for action 02 state sg., the principal can recover higher optimal value of 0.615. Detailed calculations are deferred to Appendix A.7.2.
S3
Q2
S2
$2
a2
(a) Original MDP instance
(b) History-dependent MDP expansion
Figure 3: Illustration value-consistent state-wise e-IC agents.
Greedy State-Wise e-IC Agent To avoid non-Markovian behavior, we introduce the greedy state- wise c-IC agent, which replaces recursive value computations with greedy look-ahead. Once the subsidy scheme is fixed, V becomes deterministic, and the agent greedily minimizes the princi- pal's 's value through local decisions.
Definition 5.2. An agent is a greedy state-wise e-IC agent if, under subsidy scheme Ar, the induced policy π E (Ar) sutisfies, for all E S, H:
Σ xals, h) (s, + aEAA
V
V hs, -c
S'ES
However, even in this simplified greedy setting, designing the principal's optimal subsidy scheme remains computationally intractable. The complete proof is deferred to Appendix A.7.3.
Theorem 5.1. Given greedy state-wise e-IC agent, computing the principal's optimal subsidy scheme is NP-hard.
6 CONCLUSION
In this paper, we study a principal- -agent problem with the aim of designing a robust subsidy scheme that maximizes the cumulative expected return in the presence of irrational agent. We demonstrate that, under the globally e-IC assumption, the optimal subsidy scheme can be effectively determined, representing a natural extension of the perfectly rational case. We further show that formulating the state-wise c-IC follower is computationally challenging. As future work, it would be interesting to consider scenarios in which the principal does not have prior knowledge of the agent's reward function the value of such in learning-based setting.
ACKNOWLEDGMENTS
This work was supported by the National Natural Science Foundation of China under Grant No.62502296.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Kiarash Banihashem, Adish Singla, Jiarui Gan, and Goran Radanovic. Admissible policy teach- ing through reward design. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6037-6045, 2022.
Omer Ben-Porat, Yishay Mansour, Michal Moshkovitz, and Boaz Taitler. Principal-agent reward shaping in mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 9502 9510, 2024.
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, and Mirco Mutti. Persuading farsighted receivers in mdps: the power of honesty. Advances in Neural Information Processing Systems, 36:14987-15014, 2023.
Matteo Bollini, Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Contracting with reinforcement learning agent by playing trick or treat. arXiv preprint UrXiv:2410.13520 2024.
Paul Dütting, Michal Feldman, and Inbal Talgam-Cohen. Algorithmic contract theory: A survey. Foundations and Trends@ in Theoretical Computer Science, 16(3-4):211-422, 2024.
Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in se- quential decision-making. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 36, pp. 5025-5033, 2022a.
Jiarui Gan, Rupak Majumdar, Adish Singla, and Goran Radanovic. Envy-frre policy teaching to multiple agents. Advances in Neural Information Processing Systems, 35:13290-13302, 2022b.
Jiarui Gan, Rupak Majumdar, Debmalya Mandal, and Goran Radanovic. Stochastic principal-agent problems: Efficient computation and learning. arXiv preprint arXiv:2306.088 03832, 2023.
Sanford J Grossman and Oliver D Hart. An analysis of the principal-agemt problem. In Foundations of insurance economics: Readings in economics and finance, pp. 302-340. Springer, 1992.
Guru Guruganesh, Jon Schneider, and Joshua R Wang. Contracts under moral hazard and adverse selection. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 563-582, 2021.
Dima Ivanov, Paul Dütting, Inbal Talgam-Cohen, Tonghan Wang, and David C Parkes. Principal- agent reinforcement learning: Orchestrating ai agents with contracts. arXiv preprint arXiv:2407.18071 180744 2024.
Ohad Kadan, Philip J Reny, and Jeroen M Swinkels. Existence of optimal mechanisms in principal- agent problems. Econometrica, 85(3):769-88 0276699-2,200 2017.
Jean-Jacques Laffont and Eric Maskin. The theory of incentives: An overview. Université des sciences sociales, Faculté des sciences économiques, 1981.
Paul Milgrom and Ilya Segal. Envelope theorems for arbitrary choice sets. Econometrica, 70(2): 583-601, 2002.
Dov Monderer and Moshe Tennenholtz. k-implementation. Proceedings of the 4th ACM confer- ence on Electronic Commerce, pp. 19-28, 2003.
Roger Myerson. Optimal coordination mechanisms in generalized principal-agen agent problems. Journal of mathematical economics, 10(1):67-81, 1982.
Stephen A Ross. The economic theory of agency: The principal's problem. The American economic review, 6342):134-139, 1973.
Vinzenz Thoma, Barna Pásztor, Andreas Krause, Giorgia Ramponi, and Yifan Hu. Contextual bilevel reinforcemeet learning for incentive alignment. Advances Neural Information Process- ing Systems, 37:127369--127455 2024.
11

---

Published as a conference paper at ICLR 2026
Jibang Wu, Zixuan Zhang. Zhe Feng. Zhaoran Wang, Zhuoran Yang, Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. arXiv preprint arXiv:2202.10678, 2022.
Jibang Wu, Siyu Chen, Mengdi Wang. Huazheng Wang, and Haifeng Xu. Contractual reinforcement learning: Pulling arms with invisible hands. arXiv preprint WrXiv:2407.014555 2024.
Shuo Wu, Haoxiang Ma, Jie Fu, and Shuo Han. Robust reward design for markov decision processes. Journal of Artificial Intelligence Research, 84, 2025.
Guanghui Yu and Chien-Ju Ho. Environment design for biased decision makers. In IJCAI, pp- 592-598, 2022.
Brian Hu Zhang. Gabriele Farina, Ioannis Anagnostides, Federico Cacciamani, Stephen Marcus McAleer, Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Steering no-regret learners desired equilibrium. arXiv preprint arXiv:2306.0522,, 2023.
Brian Hu Zhang, Tao Lin, Yiling Chen, and Tuomas Sandholm. Learning game by paying the agents. arXiv preprint arXiv:2503.0197,. 2025.
Haoqi Zhang and David C Parkes. Value-based policy teaching with active indirect elicitation. In AAAI, volume 8, pp. 208-214, 2008
A APPENDIX
A.1
USAGE OF LLM
We employed the large language model (LLM) to assist in refining the language and enhancing the clarity of this manuscript. The LLM was not used for generating research ideas, identifying related work, performing analyses, or contributing to the substantive scientific content of this paper.
A.2
MISSING EXAMPLES
A.2.1 COUNTEREXAMPAA CONVEXITY
Consider a single-period scenario with three actions and = 2. The principal receives 0 for the first action and 5 for both the second and third actions, while the agent's reward is 0 for the first action and 1 for other actions. Let Ar; and Ar2 transfer 2 units to the second and third actions, respectively: both yield a principal value of 1. convex combination, Ar3, transferring I unit to both actions, results in leader value of 0, directly violating concavity. This illustrates that the outer optimization cannot be assumed concave.
A.2.2 EXAMPLE OF dsw SCALING AS O(ve)
Consider single-perice scenario with two actions and 1. The principal and agent values for the first action are 4 and 0, respectively, and for the second action, they are and 2. In this setting, 1-x* always scales as (vE)) and matches the upper bound. The core idea behind is such instance, the function V ($, h 0) is complete linear function in interval [0, 1]. Figure iillustrates relationship between dww and e, along with the behavior of V (s, h 0) as a function of x.
A.3 PROOF OF THROREM 3.1
By definition, for any subsidy scheme Ar with induced action policy Far ll((r)), we have
V.Ar Ar ( h= 0) + VTA.. Ar ( 0) = V-A ($, 0) V (8, 0).
(A.1)
12

---

Published as a conference paper at ICLR 2026
V215
1.7
175
1.6
1.00
65x 1.00
1/
1.00
0.1
0.03
0.5
0.5
Ou scale (V+7)
--- decreuses as GIVT)
130
(a) 6yw versus
(b) versus E
(c) (8, 0) versus J
Figure Curves of de and x² versus when V (8, = 0) differentiable.
Moreover, since any subsidy scheme provides the agent with non-negative reward transfers, back- ward induction gives
H
VT (8, h = = max E
(St, as
H
2 max E
Σ
Ta( 42,
(A.2)
1=
= - A
(8, (8,4=0) 0).
Combining this with inequality A.1 the optimal principal value is upper bounded by
OPT < V (s, 0) V Ar=
(s, h 0).
remains show that
v (8 - -Ar=D (s, a,
Ar (s,
achieves this bound. For any policy substituting Art into ArrAr' (8, = 0) and applying back-
ward induction establishes that the agent's value for every action equals VAr=0((s h 0), which makes inequality (A.2) tight. In addition, since the nocial-welfare ceeefarr-maximizinge policy Nyw renders inequality AA.1 exact, the principal's value under Ar* is
V. (&, h 0) V (6, h 0) VÀ Ar (s - =),
which coincides with the upper bound. Consequently, under the cooperative tie-breaking rule, the agent selects Tsw, thereby achieving
OPT ( 0) V Ar
(s, h 0)-
A.4 PROOF FOR PROPOSITION 3.2
Recall that in Theorem 3.1 we defined the optimal reward transfer as
V Arr= hs -Ar=0 (s,a, " h).
Ar" as",s,,,h
In fact, it suffices retain the reward transfer only along the social-weffare-mmxxmiiiing actions. In particular, we define subsidy scheme Art
(s, a. h) = { (s) TTw (als, > 0,
otherwise.
so that the agent value of docial-welfareemaaxiie
action policy New under Arww
VT Aro. (8, 0) = / (&, = 0) = Ar== (8. = 0),
which yields principal value of V (8. h - (8, h 0)
13

---

Published as a conference paper at ICLR 2026
A.5
PROOF OF PROPOSITION 4.2
Optimal subsidy scheme
Recall from 443 that
Ar" h)) = Vi- (s) - Q (5,(s,,,1) a))
Vi- (s. (s. rp(s,
Σ
8'ES
= (1 - I))
x' x'ra,,,,)) (s,
E
H'ES
Let Taw be a deterministic social welfar--eearreeeeeeee maxiamiiiniii agent policy. We now define a subsidy scheme Arsw that is restricted to sww
(ss a, h) A (sr"(s, h),, New (a|s, h)) 0, otherwise.
0,
First, we claim that under either subsidy scheme, Arsw or Ar", the agent's 's optimal value is identical:
($ v (8, = 0).
The central argument of the proof is that, under both Ar" and Arsw. action policy Tsw can achieve the agent's maximal value, and the values thus attained coincide. Specifically,
v (s, h = 0) A
Ar (s, h 0) V. (8, 0) (c) v (s. = 0).
In what follows, we establish the validity of each equality (a)-(c) sequentially. We first show (a):
(8, 0) Arr To this, consider any action policy under Ar".
Ar' h = 0).
A
Vr (8, h = 0) E
ra 0r, 1) + Ar (st,
(A(Se, Or, (c, +1- ("p===")p(ssssst) x 2 (A.3)
+ (st, Σ
P(s az, V (8t+1, +
S4+EES
= =(1 (1-=z)>VV (8, = 0) V22 ($, = 0).
Subtracting the agent value under any policy from that under ग.. gives
VT Arr
($, 0) nar (s 0)
(1 x= (V ($. h 0) V (s, h = 0))
< 0,
(A.4)
which implies Tew can achieves the maximum agent value under Ar"
Am Ar" (8, = 0) = V (8 = 0).
(A.5)
Then, we show (b):
Ar' V Arr (8, 0) V Arw (8, h 0).
Based on the definition of Arsw, we can express Arsw for any triple (s, (s,a, h) as
Ar (8, a, (x>0) (Tsw (als, Ar)
14

---

know that Published as a conference paper at ICLR 2026
where 1 [x:00 (x) is the indicator function:
1, x > 0:
1 [x>0)
0, x 0.
By introducing the occupancy measure Mew of policy New. which satisfies (Enr Msw (s, a', ,', Tsw (als,, h) = (s, a, h) for any (s, a, h),, we have (1>0)(TTw)) (als, 2 1 (x>0) (Now (8, a, h)).
Hence,
Vm. (8,h=0)
Σ 8,0,h
Ar Mow (i Ar (s,,,,))))
Σ 8,0,h
( (Hult,,,,,y + (u as, a (s,
h)) Mew (o a, h) h) (0 () +
2,0,h
(sw + (sw a, Ar
8,0,h
Viinn (8, (8,h=0) =0.
Meanwhile, since (s, hi) 2 Arsw (s, a, h) for any (s, a, h), by construction, it follows that
V V ($, 0) > V wmw ($, 0).
Combining the above results, we can conclude that
V (8, h 0) = Ar (8, h 0)-
Ars
Finally, we establish (c):
A VTw 0) 0)
VAr (s, 0).
To prove this, it suffices to show that for any policy n, V Ar (8, h 0) S Vā Ara..Arm (8, = 0), which directly implies that Tsw attains the maximum agent value under Ar i.c, V (s, (3, 1. h = 0). The inequality, vrw (s, =0 S Aosnrrs ( 0), follows from the chain
0) V ww.Ar Arsu
VT. TM (s, = 0) E V Ar (s, h = 0) S Vi To. (s, h = 0) = V Fio Arw (8, 0).
The first inequality holds because the construction, Ar (s a, h) I Ar* h)) holds for all (s, a, h), which implies, for any action policy т, V VT (s, h = 0) I Va. (s. h = 0). The sec- ond inequality follows from (A.4) The final equality holds because Ar" (s, h) (s. whenever Tew (a]s, (088,)) h) > 0.
By combining (a), (b), and (c), we can conclude V (8, - (8, h follows.
Next, show that the principal's worst-case reward under Arsw is worse than under Ar". Suppose an action policy и globally e-IC under Ar By definition, this implies that the agent's From the previous discussion,
value under Ar.. achieves V (8, h VÁ" h h 0) globally e-IC under Ar". The converse, however, does not necessarily hold.
(8, A 0) and Arsw Ar". Consequently, the action policy æ is also
Thus, relative to Ar*, the scheme Arw reduces the set of agent policies that are globally e-IC. Moreover, for any given action policy, the principal's 's payoff under Arw is at least as large as under Art. It follows that the principal attains least the same worst-case reward under Arw under Ar". Since Ar* is optimal, the principal's worst-case reward identical under both schemes, thereby establishing the first part of the proposition.
15

---

Published as a conference paper at ICLR 2026
Action Policy under Ar* To prove the latter part of Proposition 4.2 the key idea is to analyze the agent's 's response under a given subsidy scheme Ar. Recall from the preliminaries that we define the adversarial response Tar to subsidy scheme Ar
E arg min VP V. (3, A - xEll(Ar)
In the following discussion, we refer to π &är as the agent's adversarial action policy. Further, we begin by analyzing the agent's behavior in single-period instance and then extend the results the multi-period case. Formally, when = 1, there is only one state 8, so we can omit (s, h) in the expressions. The optimization problem for agent then becomes
min Σ T(a)r s.t. Σ (a)) max c, 2 O, Σ [=(a==1 =1
As this is linear program, apply the KKT conditions analyze the optimal solution. The Lagrangian function is
(()) a = ( (a) a m (a) - ----nm [m(a)r²((a)
Σ B(a)(-T(a)) vV(1 [(a)))
Σ ( -r - + B(a)) V + al max x (a) -e).
ar
The resulting dual program is followed:
max a.V
+ arl max (a) s.t. a a2 -
Let Ar and v denote the optimal dual values under the subsidy scheme Ar, and let ОТр denote the final principal value under the same subsidy scheme. By complementary slackness, for any action such that
(a) - (ar = vår min (a) ar
we have TAr(a) (a) 2 O. We refer to such actions as the candidate actions a E A, since they can potentially be chosen by the agent given subsidy scheme Ar.
However in certain problem instances, there exist candidate actions that do not appear in any agent's adversarial action policy. For example, consider 1 and two actions: the first action has principal reward O and agent reward 1, while the second action has principal reward 1 and agent reward 2. The unique agent's adversarial action policy deterministically selects the first action, yet setting a would include both actions as candidate actions. In general, based on the value of optimal dual variable a² under optimal subsidy scheme Ar*, we claim there are three possible scenarios:
Case I: a* O. Every candidate action at this point attains the minimum principal value, so any action satisfying the globally e-IC constraint can be deterministically chosen.
Case 2: a* > O, and all candidate actions satisfy the globally e-IC constraint. Comple- mentary slackness implies the agent's value is exactly max, r'A (a) - e, so only actions attaining this value can be chosen. This case coincides with the above example.
Case 3: a* O, and some candidate actions have agent reward below max, (a e. Then, the agent can mix actions above and below this threshold to form an agent's s adversarial action policy, leading to the fact that any candidate action may become part of agent response.
To further explain the agent's ' behavior pattern in Case and Case 3, we use the following equations to show that when a Ar > 0, as long the action policy distribution is supported only candi- date actions and achieves an agent value exactly equal to max, r (a - e, the policy æ constitutes possible adversarial action policy of the agent. In other words, we only need to consider how
16

---

Published as a conference paper at ICLR 2026
to organize the policy distribution supported candidate actions achieve agent value exactly equal to max, Fa(a) - 6.
-aa Σ ( -ata)))(()) a
Σ =
I(aa)vrr+ +adr(maxr (a) cc)
OPT
We now extend to the multi-period case. Observe that under subsidy scheme Ar, any multi-period policy T, can be viewed as single-period action with principal reward V (s, = 0) and agent reward VA (s, h 0). yielding a single-period instance with infinitely many tions. Although this transformation is generally intractable, it provides a useful framework for analyzing the properties of action policies. Suppose the single-period agent' adversarial action policy is Tg. the multi-period agent's adversarial action policy can be recovered as x x*(als, (1l h) E, T. (a;) (a h) for any state s, action a and timestep h, where ( (a,) denotes the probability assigned policy и. Accordingly, we define the candidate policy π E II under subsidy scheme Ar
p (s = 0) - - (8, h = 0) = =min (V
(s, - (8, 0)]
analogous the single-period candidate actions, so that the adversarial agent's 's action policy can be expressed as a convex combination of these candidate policies.
We next establish that, under the optimal subsidy scheme Ar" from Theorem every action policy including ssw qualifies as candidate. Recall from (4. that
Ar (s, a, h) = V (s, h) - Q7 as
Vi- (s,h) h) - x² r' a, h) + rr(s,,,))
Σ (1)
S'ES
(1 x' -
(s,
P( (s,
S'ES
where x²
1ta- For any action policy, under optimal subsidy scheme Ar substituting Ar" into Ar (s, h 0) a V Arr ($, h 0) yields
the expression Vp
Vp
V.
h = 0) - a a'v (3, h = 0)
#-1 1
=Ex
(p(8, az 1) - a r (8,, ar, t) - (1 + a (") a))
x² 1- xz
Ex
(s 0z, ()
(8 ac,1) x
Ar (sc,
E
TP St, uz, 1)
r' (s(
(A.6)
xx
((1 x (r)s,(s), - x "rass
1 r-
P( Se, ae, 1)V2 (omm)(+))
Vi (it
Σ
1 x
Vg. (8, h 0).
x
Thus, every action policy yields the same value
Vr.Ar' (8, h 0) A' (8, 0).
17

---

Published as a conference paper at ICLR 2026
Consequently, all action policies qualify candidate policies, and we have
min Vi - = 0) a V (8, (8,h= 0)] 1
V (8
Having established this, we note that not all candidate policies necessarily receive positive probabil- ity in the support of an agent's adversarial action policy, as illustrated in the single-period analysis. Similarly, we distinguish cases based on the value of the optimal dual variable a*: when a* O, the corresponding optimal solution is x² = O, making the proposition trivial; When a > 0, we assert that Case 2 will never happen under optimal subsidy scheme Ar* as there exists candidate
policy á whose agent value is strictly smaller than V (š, h = 0) - e. Moreover, this policy क can be combined with Tew to construct the agent's 's adversarial action policy.
In detail, we construct the candidate policy á by analyzing the derivative of the objective function. Applying the envelope theorem (Milgrom Segal 2002), the derivative of the objective with respect to in Theorem 4.1 is given by
F'(x)) = V. h 0) V (š, h =0) (1 x)²
(A.7)
where मх = arg max, ( 0) 1V vg. (8, = 0)}. In general, the objective function may have a finite number of non-differentiable points, arising from the potential non-uniqueness of Va (8, h = O). Nevertheless, since the set of sub-differentials can be fully characterized by the derivative expression, for simplicity and elarity we do not distinguish between derivatives and sub-derivatives, and we treat stationary points by directly setting Fz) = 0.
Since the objective function is concave, the optimal solution x² and the corresponding policy Ta- can be characterized by the vanishing derivative condition. Furthermore, the requirement a" > ensures that x E (0, 1), implying that x², as an interior optimum, necessarily exists as a stationary point. Consequently, imposing F' F(rr)= = 0 yields
V (s, = 0) V (8, h
(1 - x²)²
In general, Tg. can be represented as any convex combination of some action policies 7e maximiz- ing x v (8, h = 0) V vr...Ar00( (8, h 0). Since every action policy qualifies as a candidate policy under Ar", kg- can equivalently be viewed as a convex combination of candidate policies. Hence, there exists candidate policy मे such that
arg max (anxxfaVVV (6, = 0) - Vp VI.Am 1
(8, 0)}
with
V (5, V (S, 0) 2 (1 x )2
To upper bound the agent value of a, using equations AA.)) and A.5 policy म,
deduce that for action
(8 - VĀ Ar h = 0) = -1 (1-11))) (s, h = 0) - V hs,h-
(A.8)
A
which, combined with the preceding inequality, implies
v A
(&. h = 0) - vrr (8, 16.h-0 =
Thus, by mixing New and with weight p, we construct an agent's adversarial action policy whose value is exactly V (3, 0) Moreover, the mixing weight nsw must satisfy p 2 x². The derivation of this lower bound on p is as follows:
First, by the definition of the mixed policy and dual variable a 0.
pVA Ar (8, 0) (1 p) (6,h=0) v (8, h 0)
Ar"
18

---

Published as a conference paper at ICLR 2026
Since V Vr (8, h = 0) = =VA" (8, h = 0). this equality can be rewritten as
pc + (1 p) vrr (8, 0) (VA') (8, 0) -() 0. Next, using the inequality V A
(8, h = 0) - V/a
(8, h = 0) 2 (1 11xx))--e we obtain
p + (1 p){
-6
+ E) 20
1- x²
Finally, dividing both sides by c givee p N x²
Action Policy under Arsw When the optimal subsidy scheme is shifted from Ar" to Arsw: our primary toowadsve-towards establishing the latter part of the proposition-is to verify that both t and Tew continue to satisfy the requirements of candidate policies. We first claim that the optimal solution x and the optimal dual variable a" remain unchanged under this modification. By the first part of Proposition 4.2 the principal's 's optimal value is preserved in this transition. Furthermore, recalling from Theorem 4.1 that the objective function Fxx) is concave, it follows that both xx and a" remain optimal.
Then, to determine whether an action policy ग. such as स and Tsw, qualifies candidate policy under Arw, it suffices to verify whether
Vp Vr (š, = 0) -a'V (8,
(A.9)
min Vp Vr. = 0) - a VVVa V (3, = 0)}
For clarity, we define
(0: Ar) A vp Ar (8, h = 0) - a (8, 00.
The proof proceeds in two steps. First, we establish a lower bound for the right-hand side of (A.9)
min ((:;; Arsw) min { V7 Anw (š, h 0) a aa---VVVVV Ar h 01} 2
1 xx
V (8, 0).
Second, we show that for the action policies से and Tww.
gi Arsw) [TTww Arsw)
Vga (8, = 0).
xx
In the first step, note that since Ar" Arsw, we have for any action policy n.
va. (&, h- - 0) < Ar (s, (s, 0),
VarAr"
(s, 0) Arm (3, 13, 0).
V
As a² 0, it follows that for any n
g(T, Arsw) min
Ara (8, 16,1=00 = 0) - a a'V (8, = 0]
pp
2 min
VT. (8,h= = 0) a a.V (8,1= 0]
(A.10)
Vg (8, = 0). x
In the second step, to prove के is candidate policy and attains the minimum - Via (8, 0), connect ( Arsw) and -I--- Vg- (8, h 0) via ب( Ar 0). Substituting x² Ita
19

---

Published as a conference paper at ICLR 2026
obtain
g(;;; Ar = 0) Vp
Ar (s, 0) - a V
(8, h = =0)
v=
p
h h 0) I-
x²
V=.Ar=
1
(8, h 0)
1
(x' - Ar=0
(3, h = 0) + x
= 0)
x
1
x (V'V (8, h 0) Vp
(8, h = =0)
x
1
max fx² Viw (8, / 0)
vr. (8, 0)}
p
(A.11)
1 x
min Vp Ar= 0 (8, 11 = 0) - 1 x
x²
Vx
VT. (8, = 0)
Vi- (8, h = 0).
(A.12)
Equality 1A.1 follows since
= arg max VT ($, = 0)- -Vp Ar (s.
0
0)}
while 1. corresponds to the definition of (s, h = 0) in Theorem 4.1
V" h 0) - -(1 x) min vg. (s, 0) 1-
x
V Ar=0 (s.h - }0}
We next turn to discuss the equality between g(ft, Arsw) and g(f,, Ar = 0). Combining (A. with g(f,, Ar = 0) I- V (8, h = 0), we obtain
g(#, Arw)) 2 g( =
To establish equality, it suffices to show g(f,, Arsw) S g( Ar 0). Since Arsu(s,a,h) 2 Ar(s, a, fi) for all (8, a, h), we have
Vr (8, h 0) s Ar hs, Vă Va.Anw (s, h = 0) 2 V v= A (s,h= = 0).
With a* 2 0, follows that
giA,, Arsw) = Vol (s, 0) a 5m (5, 0)
0) - a V Ar= -8,
g Ar = 0).
Thus g(tt Ar.w)
g Ar 0).
For sww recall that after changing from Ar" to Arw. its agent value remains unchanged. Since the social welfare is unaffected by the subsidy scheme, the principal's 's value also remains the same. Hence,
g(Tww Arsw)) = VpT. Arm (8, h = 0) a V Ara (8,h 0)
(A.13)
-agm
(8, = 0) - a VV
Ar" (8,1=0)
(4.
1
V (6, h 0),
(A.15)
where the last equality follows from (A.6).
Finally, bound the probability weight, recall that both the maximum agent value and the agent value of Tew remain unchanged, i.e.
Vee Arw h h 0) Vrr.Ar' (8, h = 0) -
ri (8,
0) V (8, 0)-
20

---

Published as a conference paper at ICLR 2026
Mcanwhile, for it its deviation from the maximum agent value is still bounded as
VAL Ar
(8, h= = 0) - V (8, h 0)
V (s, h 0) c
0) 1 x²
Therefore, by the same reasoning under Ar", we conclude that Tsw and á constitute an optimal adversarial pair for the agent, with Tsw assigned probability weight of at least x².
A.6 PROOF OF PROPOSITION
According to the proof Theorem 4.1 recall that the optimal subsidy scheme Ar" given optimal dual variable (a"" V*) is
a, a)) = 1 (sV
+ Σ ( -rr as))
-
d'ES
Therefore, the agent's 's action policy TAr under Ar* satisfies
Vpan Ar" 0) ++ V (s, 0) 1+ V (S, h 0) a²c.
c Based on the KKT condition, when x" E (0. hence a* > 0, the above inequality becomes the equality. Therefore, combining the above two equations, we can conclude that
V V Ar h V
- c= 1+
0) V -c
6. = V ($, = 0) Vi (š, h = 0) = (1 + 1 - x
The key analyze such gap is examine the relationship between e and x². By applying the envelope theorem (Milgrom & Segal 2002), the derivative of the objective function respect to æ in Theorem is
F'(x) Vis (5, h 0) V (8, h 0) (1 (1=x)?'
(A.16)
where Tx = arg max, (xV = 0) V. v.. (3, h = 0)}. In general, the objective func- tion contains finite number of non-differentiable points, which arise from the non-uniqueness of v ($, h = 0). Nevertheless, since the set of sub-differential can be fully characterized by the expression of the derivative, for the sake of simplicity and clarity we do not distinguish between derivatives and sub-derivatives, and in the discussion of stationary points we directly set the deriva- tive F to O.
Meanwhile, since the objective function is concave, the optimal solution x* and the corresponding policy म.. can be characterized by the condition that the derivative vanishes. Moreover, the require- ment a* > 0 ensures that x² E (0, 1), which implies that x²' as an interior optimum, necessarily exists as a stationary point. Consequently, imposing the condition (a(x) yields
(A.17)
V= (8, = 0) V (3, 0) 0)
Since Ta- is action policy, can immediately have trivial bound as
V= (6, h 0) V ($, h (s, h 0) min V (8, h =0),
However, in fact, we can obtain tighter constant bound on V ($. h = 0) V ($. h 0). Denote TA as the action policy that attains the minimum principal value in the absence of a subsidy, i.e.,
^ arg min VT
(8, h 0),
and if multiple action policies achieve this minimum, we select म to be the one among them that maximizes social welfare. We claim that
%/ (8, h V (8. h 0) Vi (5, h 0) VTA (8. h 0)-
21

---

Published as a conference paper at ICLR 2026
To prove this, show that for any (0,1),
v (3, = 0) 2 V (8, 0).
Recall that
T2 arg max
0) Ar - (8,h=0)}
By simple rearrangement and using x > O, we obtain
V (8, h = V (8, h = 0) 2 _ (vp VT=:Ar=0 (3, h- = 0) - Vp mr (3. h h -0).
As R minimizes the principal value with Ar the right-hand side is nonnegative, which imme- diately implies
V ($, 0) 2 V ($, = 0).
as desired. Moreover, this bound is tight: based on the definition of π, there always exists some To E (0, 1) such that for any E [0, 2o). the policy maximizes vV (s, h) Vr. (s, h).
Having established a bound on V (8, = 0) v (8, h 0), we can immediately derive corresponding bound on 1-="" x=:
(B, h 0) V (8, 0)
Finally, applying the condition F Fxx once more, we obtain
8pm x
(Viu (8, h = 0) ($,
V sw ($, h = 0)) (1 xx))
V 0
demonstrating that the social welfare gap dew is upper bounded by O(ve).
A.6.1 THE DEPENDENCE OF 6ew ON e
When analyzing the relationship between dew and straightforward observation is that the effec- tiveness of the limited subsidy diminishes approaches infinity, allowing the agent to bypass the globally e-IC constraint and achieve trivial minimization of the leader's value. In this scenario, even as continues to increase, the social welfare gap remains unchanged. Therefore, our analy- sis focuses relatively small values of examining how the social welfare gap grows daw increases and x² E (0, 1).
The key issue in equation (A.17) is that changes in may simultaneously affect both x² and the term (3, h = 0) V (3,h = 0). However, a closer analysis the derivative reveals that e cannot influence these two quantities simultancously. Before presenting the detailed argument, first establish the following lemma, which shows that x" is monotone in e.
Lemma A.I. The optimal solution x² 1) is monotonically non-increasing in
Proof. Recall that
V (8, h = 0) max ( 0) Vp A (8, = 0)}-
Since (s, 0) the maximum of finitely many linear functions in xr, its derivative V (8, h = 0) is non-decreaiigg in a. Consequently, (s h = 0) V (s. h = 0) is non-increasing in x.
Further, for x² (0, 1), imposing the stationarity condition (x( = yields
c= x >=)²"
0) V (s. h 0)).
As increases, both (1 (1=x")= and ViL (8, 0) - Vi (s, 0) decrease, making the right-hand side of the above equation monotonically non-increasing in x². Thus, for the equality hold, an increase in must be matched by an non-increase in x=, which proves the claim.
We then analyze the two possible cases of x" given e, corresponding to 8.n scaling as ((ve) or Oc)), respectively:
22

---

Published as a conference paper at ICLR 2026
When the piecewise linear function (s. is differentiable x", every Tx- II yields the same social welfare Vis (s, = 0). Owing to this uniqueness, there exists a small interval 5 such that for all x E (a* ö, xx + 5), the policy т remains unchanged. Consequently, x" is linearly related to VF, and the social welfare gap scales as ((ve).
When (s, h) is non-differentiable at x", different тx- induce different levels of social welfare. In this achieving the minimum and maximum social welfare, respectively, which define the left- and right-hand derivatives around x²" We claim long
F(z) is concave, within II.-, there exist two policies T' and T
V (8, h 0) - Vsw"" (8, = 0) (1 x+)
V (3, = 0) V (8, = 0),
the optimal solution for é' remains x", and the social welfare gap scales as O(e). To see this, consider the counterexample. Recall from the proof of Lemma A. that V (š, h 0) is non-decreasing in z. Suppose the solution for is x'. If x' < x then
F'(2') = V ($, = 0) VSN"" (3, h = 0)
(1 x')²
sw (8, = 0) Vasa* (8, = 0)
(1 x²)²
V (8, 0) Vau (8, = 0) x²
20,
which shows is not a stationary point, and hence not optimal for a concave function. The proof for x' follows analogously by replacing T... with q.. and showing / (xxxx) < O.
A.7 OMITTED CALCULATIONS AND PROOF IN SECTION 5
A.7.1 TECHNICAL LEMMAS
As our proof and example construction involves iteratively optimizing the subsidy scheme for the single-period problem instance, we begin by introducing the following definitions for clarity.
Definition A.1. Given tolerance c, the problem instance I= ((rp(a)), A (ax));) is single-period problem where H 1, the agent is globally e-IC agent, and rp, A are the principal and agent reward functions for actions ; Given and problem instance I:
(I) denotes the principal value under subsidy scheme Ar.
(I) denotes the maximal agent value under subsidy scheme Ar.
VT(T) denotes the optimal principal value under the optimal subsidy scheme Ar".
Vā( denotes the maximal agent value under the optimal subsidy scheme Ar
Based on the above definitions, we establish several useful properties of the subsidy scheme in the following lemmas, which will be employed in the proof of NP-hardness. Intuitively, the first lemma describes how the principal's value is determined when the agent adversarially reallocates probabilities in response to given reward transfer. The second lemma characterizes the optimal reward transfer and the corresponding principal and agent values in a simple two-action instance. The third lemma analyzes how the optimal principal value in a three-action instance relates to the optimal values of its two-action sub-instances, providing useful bounds for iterative constructions.
Lemma A.2. Let I = ((a, b), (c) with a > c and z d. Under the subsidy scheme Ar = 0, the principal's final value is
v ab ae ad + b
Proof. To adversarially minimize the principal value under the constraint of global e-IC, it's obvious that the agent will choose to mix the first and the second action that Vår=0 (T) b By
23

---

Published as a conference paper at ICLR 2026
denoting the probability weight the first action p, have
b d -
pb + - (1-p)d=b-c
- d =
Substituting into the principal's value formula,
ab - ae ad + ce
VPr=0()) (T) pa (1 p)c
d
Lemma A.3. Ler I= ((a, 0), (0, with a > c. Then the principal's optimal value is
Vā(1) = (va - ve)",
achieved by setting the reward transfer for the first action voc. Correspondingly, the agent's value under this optimal transfer is
V Voe.
Proof. Clearly, the principal will allocate a positive subsidy to the first action only if doing can yield principal value exceeding zero. Consider reward transfer x 2 e assigned to the first action under subsidy scheme Ar. For given the principal's 'ss value is
V (7) =
ae x
Maximizing over x 2 6, we obtain the optimal principal value
VP(T) max =
Vpr(T) + 2/ (Va VE2.
Consequently, the agent's value under the optimal agent value is Vī(T) Vac.
Lemma A.4. Let = (Ai, A2,AA) with A, = (rp(a;), TA (a:)). Suppose for i (2,3), rp(a)) + ra(a)) > rp(a)) + (a(aa) te. Define I' = (A1, and 1" (A1, Then
Vī(1) E min(V)(()
Proof. According Proposition 4.2 for any instance, the optimal reward transfer assigns nonzero reward only to the first action. Applying concave maximization to instance 1, we recall that the objective function
F(x) = VV h = 0) - ($, h 0)
where T. = arg max, (x ww (3 0) - vp -r.0 (s, h = 0)}, and its derivative is
F'(x) =
Va, VVa = 0) V (8, h = 0) (1 - x)²
By observation, have
FO = (s, V (8, = - -c
where mo minimizes the principal's value, and F'(x)) 0 as 1. Therefore, there are two cases:
There exists mo that chooses aj instance Substituting into the derivative, we obtain (O) < O. and the optimal solution is x = 0, which implies that the optimal subsidy scheme Ar" = 0. Similarly, the optimal schemes for I' and I" are also Ar* = 0. Since action a1 yields the highest social welfare, it also provides the largest agent value. Conse- quently, in all three instances, the agent will deterministically select action a,, resulting in Vū(T) (T(T") Vi()".
24

---

Published as a conference paper at ICLR 2026
To chooses action other than d1. In this case, based on the condition that for i {2, 3), +
T' Tp(a1) + +r((a1) > (p(a))+ra(a) + e, we have (0) > 0 and x E (0, 1) for instances I. I' and I". According to Proposition 4.2 the optimal subsidy assigns a positive transfer only to action 01, and there exists an agent's adversarial action policy that mixes action an with other actions in all three instances. Suppose the optimal subsidy schemes for instances 1,, I" are Ar" (1), Art (1'), and Ar" resppeivcepcc Then we have
(r"())),
VI(1) (Vp (arr((Arr))))) (1 (0) ( (A1,
Vi(d") Vp- (AI, A2),
Vi(L") = V.-. VAr (r") (A1,As).
By the definition of the optimal subsidy scheme, then obtain
(A & VV (1)) V2
Vp (1 (AI, S vp (A1, (AI,
which completes the proof.
A.7.2 SUPPLEMENTARY CALCULATIONS FOR EXAMPLE IN SECTION 5
In this section, we provide supplementary details regarding the computation of the optimal subsidy scheme and the corresponding principal value for both Markovian and non-Markovian agents. For the Markovian agent, there exists an optimal subsidy scheme Ar" in which the principal exclusively subsidizes actions and 02. This is because, for any scheme that subsidizes actions other than a and 02 eliminating these additional subsidies increases the principal's value. To illustrate this, we consider the action governing the transition from to 83 other actions are straightforward. When the subsidy on this action reduced to zero, the resulting occupancy measure of the agent's policy increases for action a₁ and decreases for state 83 and action a2- Consequently, as long as the principal derives greater value from action a1, this modified scheme yields higher overall principal value. As we will demonstrate later, the optimal subsidy on action a1 is at most 3, which substantiates this claim.
example, as the arguments for
Let and y denote the subsidies for actions d1 and 02 respectively, and let p represent the probability of choosing action 02 in state 82. We begin by establishing preliminary bounds for the optimal subsidies, x² and y". First, we observe that y² I 0.21. If y 0.21, the principal's reward becomes negative; thus, the principal can always increase its value by reducing the subsidy on 02- Second, is straightforward
verify that the combination (z 1, 0, p = 1) is feasible and yields principal value of 0.71. Consequently, we must have x < 3: if x 2 3, the optimal principal value is bounded by 0.21 + (3.21 3) = 0.42, which is strictly less than 0.71. Finally, the optimal subsidies
must satisfy x² 2 y": For any combination where x y. the principal's 's value strictly decreases compared to the zero-subsidy baseline.
Then, by applying Lemma A.2 the principal's reward function with respect to æ. y. and is derived as (x, p.P):
1
x - + P(0.21 3)
f(r,
3.21 x
2
2 + (1 y)p
Based on all above derivations, the optimization problem for the principal's 's value is defined as
max (0.00.2 2E(v.3) pElp/(v+11)11
max
min f(x, v.P)
where the lower bound on y arises from the e-IC constraint. We first analyze the best response of p given x and The second-order derivative of ʃ with respect to is given by:
82 (1 + y) y-3) 0p2
(2 + x - y)))
Given the domains of x and y. the function is concave with respect to p when p 2 O. Consequently, the optimal p" y) lies at the boundaries: either y + y) 1. This allows apply the
25

---

Published as a conference paper at ICLR 2026
Envelope Theorem to analyze the derivatives with respect to x:
0f
1
5
1+
0x
2
(2 + x - 4)²
0º1 f
ux
(2 + I - y)
0ʃ
-1 +
dr p=1
(1 y)
0
4
2x
[1 (1+ x - y)
Based on the ranges of and y. the function is concave with respect æ. The stationary point is either + y or æ - y. We can thus further constrain the range of [y, + and investigate the first-order derivative of f with respect to at = 0:
F(x, v) 2 0f
(1 + v) y 3)
+ (0.21-11
0p p=0
(2 + 2)
Examining the derivative with respect to H, we observe that F(x, y) is monotonically increasing in for [0, 1+ y] and y [0, 0.21]:
aF
(1+y)(-3)) 2y++4
dr
(2+ x)
Let hy)) A F(1 + y. w): we now show that h is monotonically decreasing with respect to y:
2(1 + y) (3 + y)²
h(y) = 0.21 -
('(w) = - 2(1 v)
(3 + y)3 <0
= Thus, h(y) < = 0.21 0.21
0. Since f is concave with respect to p. it follows that f range [0, 1]. This demonstrates that the agent will
monotonically decreasing with respect deterministicallyy choose d2 at state 82 when x E [ys, + and E [0, 0.21]. Therefore, for a given y. the optimal choice of x is + y. Substituting p and reduces to the following maximization problem:
y into f(r p). the objective
max 0.71 vE[0,0.21]
Clearly, the optimal solution is y² = 0. yielding a final principal value of 0.71. Accordingly, we have x= = and p" p==== =
For the non-Markovian case, we directly apply Lemma A.3 to determine that the optimal subsidy action d2 state si 0.1. Regarding the 51 branch, we apply a method similar to Markovian setting, using modified principal value function:
3
f(x, v.P) 3.21
2 x (1 + u)p
Obviously, p* since y > By computing the derivatives with respect to x and y. we find x² = and y" = O. Thus, the final optimal principal value is 0.605 + 0.01 0.615.
A.7.3 PROOF OF THEOREM 5.1
We prove the hardness by reduction from the Maximum Independent Set problem.
26

---

Published as a conference paper at ICLR 2026
ht = 0
ATm
e m
W on
Spy
Sug
Suz
Spy
Dg (9c.0) 0)
4g
h
Seud
222
D2.
(2-2)
07
47
SEL.
SpL
Figure 5: Illustrative Construction of the NP-Hardness Reduction Instance
Construction Given graph G EV, we construct corresponding problem instance as illustrated Figure 5
Let [V| and m = [F] and assume n 2 2.
Throughout the proof, we refer to an action with horizon is set to /l = 4, with a global initial state & that has only one blank action, which transitions uniformly to the vertex states Suy Sug. ...,,,,,,, Sv., and the edge states 5e1 S.g..... Se..
0 and P = 0 as blank action. The time
For each vertex state 8,, there is blank action leading to an intermediate state & for padding. The subsidy scheme at this intermediate state encodes whether the corresponding vertex is included in the maximum independent set. Two actions, and Or, are available from s with the following specifications:
art rp(s 0z, h = 2) = (1 2n ) rA 0r, 2) = deterministically transition- ing to state s"
a,: blank action that deterministically transitions state s!!'
For each edge E connecting vertices and dy, the corresponding edge state s, has three actions at am, and a, designed to enforce the independent set constraints:
at (s al, h 1) 9e, (se: a,, h 1) 0, deterministically transitioning state Se, which is then followed by a padding state s"
an! blank action that deterministically transitions state s'mm which is then followed padding state s! "mm"
a, (s(ee, a,, h = 1) and TA ar. = 1) = - (1+ 1 e, which transitions with equal probability states s',, and 8'yg-
Under this MDP construction, we claim that there exists an independent set size in if and only if there exists subsidy scheme Ar in the MDP that allows the principal achieve reward of
+ 4m
4n
m
If direction Given size-k independent set V V graph G, we construct subsidy scheme I
Ar that achieves principal value and
+4m atm e. The scheme is defined as follows:
For each V*, set Ar(s at, 2) 1 2n and Ar(5, ar h 2) 0.
27

---

Published as a conference paper at ICLR 2026
For each V*, set zero subsidy for both actions o; and a, at (s/ 2).
For each edge e E E, Ar(se: at, h 1) 3e and leave actions am and or with zero subsidy.
No subsidy is applied to any other actions.
With this subsidy scheme Ar, the agent greedily minimizes the principal value from bottom to top. First, consider vertex state sy and let denote the agent's action policy under Ar. By utilizing Lemma A.3
we obtain:
For U E V VA
Ar (s h 2) = 4nz and V (s h = 2) 1+
1 2n
For u & V Vp AR
Ar (5 h 2) = 0 and V (5 = 2) 0.
Next, consider edge state Se, where connects vertices and 02- There are two scenarios depending on whether one of the endpoints is in the independent set:
If one endpoint is in V (ie., in V U2 V*), the agent faces single-penn period problem instance ((6e, 3e), (0, 0), (0,0)) Since two actions have identical principal and agent rewards, Lemma A.2 implies that the resulting principal value in (s., h 1) is 4e.
If neither endpoint is in V (i.e., VA V and 1/2 é V*), the agent faces the instance ((6e,3r (0, 0). (- Sn.
2 (1 + 2n )c)). Following the analysis in Lemma A.4 the agent chooses a mixture between (a), (2) or (a), Applying Lemma A.2 we find with
1
1
AAr= P
((Ge, (0,0)) V V 36),
1 (-8)
1
(
1+
- 2n
)
2
15 +
3
E
+ 4n
(14 + 1
(15 +
1 8n
2 4m
+
2m
Sn
0,
+ 4n
2
which confirms that the final principal value remains 4e.
Therefore, the total principal value under subsidy scheme Ar is
Vp V AT h= =) k An (n k) 0 + 4e m
+ 4m
4n
n + m
n m
Only if direction Suppose a subsidy scheme Ar achieves In2 4m
n+mm e. for the principal. We show
that this implies the existence of size-k independent set V* c C G.
We first upper bound the maximum principal value achievable under any subsidy scheme Ar. There are two primary sources of principal value:
Vertex states s/, by Lemma A.3
A.3 each vertex contributes at most 2
Edge states by Lemma A.3 and Lemma A.4 each edge contributes at most V5((9,, 0), (0, 0)) 4c.
Consequently, to attain the claimed principal value, at least vertex states must yield positive con- tributions. We claim that these vertices form an independent set. To see this, suppose otherwise: let Vi and 02 be connected by an edge Since both s', and s', have nonzero principal values, the principal must provide reward transfer of at least action at both s', and 8',, Then, for action ay at 8z, the agent's expected value is at least (} 1 )e, while the principal's 's value is most
28

---

Published as a conference paper at ICLR 2026
We can upper bound the principal value from (śz, h 1) under any subsidy scheme Ar as
8x22
1
1
1
P
(sz, = =)
Vp
(9c, 0),
0),
c 1 4n )e)))
(A.18)
8n2
1
+
Vi
(9c
8nzc, (,,,, 0))),(0)) (0, 15
1
_
1
)
(A.19)
8n
8n2
4n
+
Vo
(9c, (0, (
4n )
1
(A.20)
8n
17
+ Vo((
)e, 0), (0,
(A.21)
8n
2
4n
2
1
(v/22
17
1
8n?
e+ +
+
- ve
4n
19
17
4n - 21
8n2
4n
Inequality (A.18) follows directly from Lemma A.4 together with the observation that, in any single- period problem instance, simultaneously decreasing the principal's reward and increasing the agent's reward for action can only reduce the optimal principal value. In equality (A.19), It evident that subtracting the same value from the principal reward of each action and then summing afterwards does not affect the optimal solution. Inequality (A.20) arises from the fact that there is pure principal reward increase in the first action. In equation (A.2I). to obtain a strictly positive principal the first action. After such subsidy, both actions now have the same agent reward, we set zero reward for both actions to sustain the relative value. Meanwhile,
value, at least ( Iे ) must be subsidized
apply lemma A.3 to find the optimal principal value.
Next, we upper bound the total principal reward across all sources:
Principal reward from agent visiting 8p: at most in2 c per vertex, for at most n vertices.
1
Principal reward from agent visiting s, for edges e E {e]: most per edge, for most edges.
Principal reward from agent visiting Se: most
19
2
17
2
Summing over all contributions, the total principal value is
ViamAr
p (š, h = 0)
1
1
19 1
17
1
Y1 + m
8n1
4n
2
2
4n
e
(m 1) 4e
4n
Comparing with the claimed value, for n 2 2 we obtain
4m
4n
e ---arri (8, 88 0)
+ m
k
1
19
1
17
1
1
2
(A.22)
11 m
4n2
8n2
2
4n
2
4n
4m
2 17
11
1
(A.23)
11 m
8n2 2
2n.
17
11
2
12 m
32
29

---

Published as a conference paper at ICLR 2026
Here, inequality (A.22) follows from neglecting the 4nd term, and inequality (A.23 is obtained by substituting n = This contradiction demonstrates that any set of & vertices ylelding positive principal value must form an independent set, thereby completing the proof.
30


Reviews:
[{"review_id": "xtmIxe9Yi1", "reviewer": "Reviewer_vNuN", "summary": "This paper considers the principal-agent MDP problem where the agent is assumed to be boundedly rational in the sense that the agent may take any suboptimal responses up to epsilon gap. This problem is modeled as a robust, minimax game: the principal tries to find a subsidy policy that maximizes social welfare, while the agent responds with the worst-possible, sub-optimal deviation. The paper shows that, if the agent response is globally epsilon suboptimal, the optimal subsidy scheme can be effectively determined. Meanwhile, if the agent response is the state-wise ϵ-IC, finding the optimal subsidy is NP-hard.", "questions": "What's the motivation or is there any technical result that this work focus on the welfare maximization objective?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper makes a good effort to extend the setting of principal-agent MDP problems. Modeling agent’s bounded rationality moves beyond the perfect-world assumptions of classical game theory and makes the work directly applicable to real-world systems where users are not perfect optimizers.", "weaknesses": "It is unclear why the paper chose to focus on the welfare maximization problem instead of the more common objective to maximize the principal’s utility. I suspect the results of this paper will no longer hold under the objective to maximize the principal’s utility. Therefore, the authors should clarify on this modeling choice and explain how the current solution might rely on the welfare maximization objective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "My0zEdtk02", "reviewer": "Reviewer_dbNJ", "summary": "This paper studies a principal-agent Markov Decision Process (MDP) problem where the principal can offer state-action-dependent subsidies to influence the agent's action policy.  The paper considers both perfectly rational (best-responding) agent as well as $\\epsilon$-best-responding agent.  The paper shows that:\n\n1. For perfectly rational agents, the principal's optimal subsidy can be characterized easily: it is the highest achievable social welfare minus the agent's default value. \n2. For $\\epsilon$-best-responding agents, taking the worst case for the principal among the $\\epsilon$-best-responding policy sets, the paper shows that the principal's maximin problem can be converted into a single-dimensional concave maximization problem that admits an efficient solution. \n3. Lastly, the authors consider a special case of $\\epsilon$-best-responding -- state-wise $\\epsilon$-IC -- in which case the optimal subsidy turns out to be NP-hard to compute.", "questions": "## Questions for the authors\n\n(Q1) Do you have any results for **Markovian** state-wise $\\epsilon$-IC agent?  Namely, if the agent uses a Markovian policy that is $\\epsilon$-optimal at every state, can the principal find the optimal subsidy efficiently?  (I am not sure whether Theorem 5.1 applies to Markovian state-wise $\\epsilon$-IC.) \n\n\n\n## Suggestions\n\n* For the future direction \"consider scenarios in which the principal does not have prior knowledge of the agent's reward function or the value of $\\epsilon$, such as in a learning-based setting\", [3] is very related.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(S1) The theoretical result for $\\epsilon$-best-responding agent, where the authors show that the maximin problem can be converted into a single-dimensional concave problem (using a duality approach) is very interesting.  The fact that such an optimization problem can be solved efficiently is not obvious at all, especially given some previous works on $\\epsilon$-best-response in other principal-agent problems, such as information design [Yang & Zhang, NeurIPS 2024, Computational Aspects of Bayesian Persuasion under Approximate Best Response].\n\n(S2) Good theoretical coverage.  The main $\\epsilon$-best-response model is in the ex-ante sense: the agent computes the overall expected utility.  The authors also consider the state-wise $\\epsilon$-best-response model, establishing a clear boundary between tractable and intractable cases.  And both Markovian and non-Markovian policies are discussed.  \n\n(S3) The paper is very well written, with rigorous definitions, helpful examples, and intuitive proof sketches.", "weaknesses": "(W1) A related literature is \"steering agents in games by payments\", e.g., [1, 2, 3], which studies how a principal can add payment (subsidy) to a game to induce certain outcomes among the players.  This literature studies multi-player games, which are more general than the single-agent problem in this paper.  But on the other hand, this literature usually considers static or repeated game, which is less general than this paper's MDP model.  [2, 3] consider no-regret learning agent, which is a form of $\\epsilon$-best-responding agent considered by this paper.  Given the conceptual similarities, I think a discussion to this literature is needed.  Nevertheless, I view this as a minor weakness because the techniques are different due to modeling differences.  \n\n\n\n---------------------------------\n\n[1] Monderer & Tennenholtz, 2004, K-Implementation.\n\n[2] Zhang et al, EC 2024, Steering No-Regret Learners to a Desired Equilibrium.\n\n[3] Zhang et al, 2025, Learning a Game by Paying the Agents.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2j00Z6GRoX", "reviewer": "Reviewer_v8gw", "summary": "The paper studies a principal-agent problem. The agent performs actions in a Markovian environment. The principal offers subsidies to change the agent's reward. The agent acts optimally (either exactly or approximately) based on the subsidized rewards. The goal of the principal is to find a subsidy scheme so that the agent's best response gives the highest possible value to the principal. The authors studied both the case where the agent responds in a perfectly optimal way and the case where it does so only approximately. For both cases, the paper characterizes optimal subsidy schemes. The paper also analyzed the relation between the social welfare gap and the agent's rationality bound. Moreover, the paper considers a stronger constraint which arises when the gap between the agent's maximum attainable value and the policy they use is bounded below an epsilon threshold at every time step. The authors argue that in this case, the agent's induced policy may be non-Markovian, which introduces additional complexity to the problem. To work around, they considered an alternative greedy state-wise epsilon-IC condition, but even with that the problem remains NP-hard.", "questions": "- Does your proof of Theorem 4.1 also imply that in the fully rational case, it is also always optimal for the principal to use a Markovian subsidy scheme.\n\n- Would you be able to show that the problem against a state-wise epsilon-IC agent (Definition 5.1) is NP-hard?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think the problem studied is interesting and natrual. The paper is very clear and easy to follow. I didn't check the full proofs but the proof sketches are helpful for understanding the ideas, and the arguments look sound. The characterization results about optimal subsidy schemes and their relation to social welfare maximizing policies are very interesting, so is the relation between the social welfare gap and epsilon. The paper is overall solid and I enjoy reading it.", "weaknesses": "- The part in Section 5 could be explored a bit more. The authors introduced an alternative type of agent in an attempt to overcome the complexity caused by history-dependency, but even that is intractable. The paper would be stronger if a tractable alternative is introduced.\n\n- Some related works are missing, but this is minor. The idea of subsidizing the agent's reward is a special case of the reward design problem. There are many papers in this direction which also adopt a worst-case perspective in the face of uncertainty about the agent's response; see, e.g., Admissible Policy Teaching through Reward Design, Banihashem et al., 2022. Similar principal-agent subsidy problems have also been studied under fairness considerations: Envy-free Policy Teaching to Multiple Agents, Gan et al., 2022. And there are similar principal-agent models based on Markov games, e.g. Stochastic Principal-Agent Problems: Efficient Computation and Learning, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H8igaB4ezl", "reviewer": "Reviewer_v2YQ", "summary": "This paper considers the Principal-Agent problem on Markov Decision Processes (MDP) where the Principal sets subsidies to the Agent in a form of an additive factor to the Agent's reward function. In turn, the Agent optimises its subsidised cumulative reward over a finite horizon MDP.\nThe main contributions of this paper are theoretical insights into optimal subsidy schemes under the assumption of bounded rationality of the Agent. In particular, three cases are considered; perfect rationality, $\\epsilon$-incentive compatible Agent over episodes, and $\\epsilon$-incentive compatible Agents over states.\nIn the first case, the authors show that the Principal's optimal payoff is the difference between the social welfare payoff and the Agent's unsubsidised payoff and provide an analytical solution to the optimal payoff scheme that only needs to subsidies actions corresponding to the social welfare maximizing actions.\nIn the second case, the authors show that the Principal's problem can be reformulated as a one-dimensional concave optimization, therefore, optimal subsidy schemes can be found with first-order optimization methods.\nIn the third case, the authors show that the Principal's optimization problem is NP-hard.", "questions": "1. The authors claim the the Agent's optimal policy is deterministic in the perfectly rational case but might be stochastic in the bounded rational setting. Could they elaborate on this claim and at least provide pointers that show these results formally?\n2. On page 7 Line 355-373, the authors discuss Markovian vs. Non-Markovian policies and claim that the Principal and the Agent adopt non-Markovian strategies in the globally $\\epsilon$-IC case. Could the authors formalise the notion of non-Markovian in the case of finite-horizon MDPs and elaborate on what is the difference between non-Markovian and time-dependent?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is easy to follow and has a clear structure that builds from section to section.\n2. Considering non-rational Agents in the Principal-Agent problem is a fundamental issue and having Principal actions that are robust to bounded rationality is crucial for applications.", "weaknesses": "1. The paper lacks discussion on how results connect to previous publications and what is the novelty of the contributions. While many recent publications are mentioned briefly in the Related Works section, without reading each of them it is hard to position the paper's contribution to the field. I strongly suggest the authors to provide more details for each Proposition and Theorem they prove what is the novelty compared to previous results.\n2. The setting is limited to finite-horizon and finite state-action space MDPs with additive subsidy schemes. While this is a nice setup for toy experiments, for the results to be more relevant for the applications of Principal-Agent problems this is a clear limitation without any guidance on how the results might generalise to more complex spaces or Principal actions. Furthermore, as the authors also highlight the Conclusion this work is limited to settings where the Principal knows the Agent's reward function which does not hold for most applications, therefore, results when the Principal has to learn the Agent's incentives would be more relevant.\n3. The paper lacks experimental results demonstrating the theoretical results. The Principal-Agent problem has many applications as the authors also highlight in the Introduction, therefore, empirical evaluations on some of the applications would solidify the theoretical results. Especially, ablations on the parameter $\\epsilon$ to show how bounded rationality affect the outcomes of the problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)