Adaptive Incentive Design for Markov Decision Processes with Unknown Rewards
Authors: Haoxiang Ma
Shuo Han
Ahmed Hemida
Charles A kamhoua
Jie Fu
Venue: Accepted by TMLR ()

Abstract: Incentive design, also known as model design or environment design for Markov decision processes(MDPs), refers to a class of problems in which a leader can incentivize   his follower by modifying the follower's reward function, in anticipation that the follower's optimal policy in the resulting MDP can be desirable for the leader's objective.  In this work, we propose   gradient-ascent algorithms to compute the leader's optimal incentive design, despite the lack of knowledge about the follower's reward function.  
First, we formulate the incentive design problem as a bi-level optimization problem and demonstrate that, by the softmax temporal consistency between the follower's policy and value function, the bi-level optimization problem can be reduced   to single-level optimization, for which a gradient-based   algorithm can be developed to optimize the leader's objective. We establish several key properties of incentive design in MDPs and prove the convergence of the proposed gradient-based method.
Next, we show that the gradient terms can be estimated from observations of the follower's best response policy, enabling the use of a stochastic gradient-ascent algorithm to compute a locally optimal incentive design without  knowing or learning the follower's reward function. Finally, we analyze the conditions under which an incentive design remains optimal for two different rewards which are policy invariant.  The effectiveness of the proposed algorithm is demonstrated using a small probabilistic transition system and a stochastic gridworld.

Adaptive Incentive Design for Markov Decision Processes with Unknown Rewards* *
Haoxiang Ma
hma2 edu
Deportment of Electrical and Computer Engineering University of Florida
Shuo Han
hanshuo@uuic.c edu
Department Electrical and Computer Engineering University of Mlinois Chicago
Ahmed Hemida
wtw.mida..tt@rrrry....oooommmm.. mil
DEVCOM Army Research Laboratory
Charles Kamhoua
charles. a. wawmoooa.cooBarrrryy.yooo
DEVCOM Army Research Laboratory
Jie Fu
fujie edu
Department of Electricol and Computer Engineering University of Florida
Abstract
Incentive design, also known model design enviromment design for Markov decision processcsMMDPs), refers to class of problems in which a leader can incentivize his follower by modifying the follower's reward function, in anticipation that the follower's optimal pol- icy the resulting MDP can be desirable for the leader's objective. In this work, we propose gradient-asceut algorithms to compute the leader's optimal incentive design, despite the lack of knowledge about the follower's reward function. First, we formulate the incentive design problem bi-level optimization problem and demonstrate that, by the softmax temporal consistency between the follower's policy and value function, the bi-level optimization prob- lem can be reduced to single-level optimization, for which a gradient-based algorithm can be developed to optimize the leader's objective. We establish several key properties of incentive design in MDPs and prove the convergence of the proposed mudicnt-bbsed method. Next, we show that the gradient lerms can estimated from observations the follower's best response policy, enabling the use of a stochastic gradient- algorithm compute locally optimal incentive design without knowing learning the follower's reward function. Finally, analyze the conditions under which an incentive design remains optimal for two different rewards which are policy invariant. The effectiveness of the proposed algorithm is demonstrated using a small probabilistic transition system and a stochastic gridworld.
1 Introduction
Incentive design, also known the principal-agent problem (Bolton & Dewatripont 2005
is concerned with
applications where leader aims optimize the performance of system which multiple people/ agents
actively interact with. Incentive design has been widely explored in economics (Seabright
1993 Kamenica
2012
Easley & Ghosh 2016 Athey & Roberts, 2001 and control systems (Ho et al.
1981
Ho & Teneketzis,
1984
Ratliff & Fiez 2020). with applications such as demand response (Zhou et al.
2017
Dobakhshari &
Gupta 2016) and network congestion control (Barrera & Garcia, 2014 Alpcan et al.
2009
et al. 2017
*Diistiibution A: Approved Public Release, Distribution Unlimited."

---

From a game-theoretic perspective, incentive design can be viewed as a non-cooperative Stackelberg game (Simaan & Cruz Jr 1973), also called leader-follower game. In a leader-follower game, the fol- lower faces a planning problem that can be influenced by an incentive policy designed by the leader. Once the incentive policy is chosen, the follower will play a best response policy that optimizes the objective of the planning problem. With the anticipation of the follower's best response policy, the leader aims to choose the incentive policy to align the follower's policy with the objective of the leader, subject to limited resources to realize the incentive policy.
In this work, we consider special class of leader-followee games: The follower faces sequential planning problem described by a Markov decision process (MDP), whereas the incentive policy of the leader can be used to provide additional side-payments or rewards to the follower at the cost of the leader's own payoff. The leader has complete knowledge of the MDP faced by the follower except the follower's reward function. The leader interacts with the follower repeatedly, during which the leader can observe the follower's 's decisions and tunes the incentive policy basod on the observations.
Our setting of unknown follower's reward is different from most existing settings in incentive design, which assuine that the leader knows the follower's reward function. Relaxing this assumption is crucial for many practical applications: In congestion control, traffic management system cannot know individual drivers' preferred routes and destinations; in resource allocation for defense in security, a defender in general has limited or incomplete information about the attacker's goal or intention. These applications motivate the following question: Despile the unknown reward of the follower, can we learn an optimal incentive policy when is possible to interact with the follower multiple times? To this end, we develop gradient- based optimization method that computes a locally optimal incentive policy and prove its convergence. We also develop method to compute a unbiased estimate of the gradient, based on the observed trajectories from the follower's 's best-response policy. The gradient estimation leads to an adaptive incentive design method for the unknown follower's reward case.
Related work Incentive design where the follower's planning problem is modcled as an MDP has been studied under several other names including "reward tempering" (Everitt et al. 2021 Skalse et al. 2022
"model design" (Chen et al. 2022). "behavior modification" " (Savas et al. 2022). and "environment de- sign" " (Zhang & Parkes 20088 Zhang et al. 2009). Zhhng & Parkes (2008) first introduced environment
design in the MDP setting and developed a mixed-integer programming approach to solve the optimal de- sign assuming the follower best responds to the designed MDP with deterministic optimal policy. [Zhang] ct al. (2009) further generalized the environment design and provided binary-scarch algorithm with loga- rithinc convergence for the case when an agent's 's model parameters are initially unknown to the designer.
In (Chakraborty et al. 2023), the authors study a similar bi-level optimization formulation to align the follower's policy with the leader's interests, where the leader is allowed to directly choose the paramoters that define the follower's reward function. In order to compute the gradient of the follower's policy mapping with respect to the reward parameters, both the Jacobian and the Hessian of the lower-level objective (i.e., the follower's value function) have to be evaluated. In (Chen et al., 2022), the authors propose brasdd algorithm to regulate the follower's reward function or transition dynamics by selecting design parameter. The gradient computation requires evaluating the gradients of the value function, the Q-function, and the advantage function in the design parameter. They developed a provably convergent single-loop gradient algorithm to update the MDP policy and the design parameter. The authors mentioned that in the case when the pre-regulated MDP is unknown, one can learn the transition model and the reward function using offline data. Our gradicnt- based optimal incentive design does not require learning the follower's reward function the gradient can be computed using the sampled trajectories under the follower's best response policy.
Savas et al. (019)) studied sequential incentive design for a principal agent to optimize the probability of satisfying a temporal logic formula. Sequential incentive design differs from environment design or model design as the principle can provide incentive dynamically based on the agent's current state, rather than static design, anticipating the agent's 's best response. As a result, soquential incentive design can be formulated as an MDP with an augmented state space. [Savas et al. (2022) studied the sequential incentive design in setup with myopie follower who selects the optimal action based the sum of the current reward
2

---

and the provided incentive from the leader. They showed that the sequential incentive design problem is PSPACF-hard but computing e-optimal solution can be reformulated as constrained MDP.
However, all these aforementioned works assume that the follower's reward function is known to the leader. Ratliff & Fiez (2020) studied adaptive incentive problem with multiple followers, whose decision-mant maaiinn processes are unknown to the leader. They consider another class of incentive design where the follower's planning problem is a generalized linear model, rather than an MDP with modifiable reward function.
Another related line of work is optimization with decision-dependent distribution (Wood & Dall' Anese,
2023 Drusvyatskiy & Xiao 2023), where the variability in the follower's policies is modeled distribution that depends on the leader's s decision variable. However, the optimization method does not adjust the leader's ss decision based on the observation of the follower's responses.
Our contributions Compared to existing work, our work has the following contributions:
The aforementioned work on incentive design in MDPs requires knowing the follower's reward func- tion, either by having it as prior knowledge or learning the follower's reward from observed behaviors. Our approach does not rely on knowing the follower's reward function and only assumes that the follower's response satisfies softmax temporal consistency (Nachum et al. 2017 and that the fol- lower uses a softmax policy. The resulting incentivizing strategy for the leader is an adaptive law that chooses the incentivizing decisions based the historical response from the follower.
2.
We propose a gradient- based method to compute the optimal incentive for the follower. Leveraging the softmax parameterization and the property of sarroyy-rggllaiiedd optimal policies, we develop a method to compute the exact gradient of the follower's policy with respect to the incentive design variables. The method involves multiple policy evaluations, cach for different "reward" function (see Section 3). As a main advantage, our method avoids the computationally expensive procedure of evaluating the Jacobian and the Hessian of the lower-level objective, which are used in hypergradient descent methods in bi-level optimization Further, our method leads to adaptive incentive design using estimated gradients. We formally prove that the proposed method is guaranteed to converge to a locally optimal incentive policy.
3. Building on the insight from the gradient-based method, we develop an unbiased estimator of the gradient terms, which enables to extend the method to the case when the follower's reward function is unknown. Our method does not require reward learning, which differs from other adaptive model design method (Chen et al. 2022
4. Lastly, we prove that under certain conditions, the optimal incentive design for a. follower with reward function R remains to be optimal for a follower with reward function R!, provided that R and Rt are policy-invariant under reward shaping. This result has two implications: 1) It shows that method for the reward-known case is also applicable to the case when the follower's reward function is unknown but learned from data, provided that the Icarned reward Rt is policy-invariant to the true reward R under reward shaping; 2) The leader only needs to design one incentive policy to a set of followers whose different reward functions are policy-invariant.
2 Preliminaries and Problem Formulation
Notations Let R denote the set of real numbers and Rd the set of real n-vectors. The vector of all ones is represented as 1 with the dimension understood from the context. The notation 2; refers to the i-th component of a vector E R" or to the i-th element of a sequence E2, which will be clarified by the context. The set of probability distributions over a finite set Z is denoted as D(Z).
We consider an incentive design problem where an agent (the leader, player 1/P1) can incentivize his oppo- nent (the follower, player 2/P2) with a side payment, in anticipation that the best response of P2, given the combined side payment and P2's original reward, can maximize P1's utility.
3

---

We start by modeling the interaction dynamics between P2 and stochastic environment MDP:
M (S,
where S is set of states, A is a set of actions, P A D(S) is probabilistic transition function such that P(s"|e 8s a) is the probability of reaching state 8 given action a being taken in state 8, and E D(S) is the initial state distribution. Throughout the paper, we assume that both S and A are finite. Under this R, we somctimes view f as vector R SSxA and use fxa
assumption, for any function f: S place of (s)a).
The leader (P1)'s objective PI's objective is given by a reward function Ri : SS A + R. However, PI cannot take actions in the MDP but relies on P2's policy obtain reward. Given P2's policy ı and the initial state distribution μ1, the total discounted reward received by P1 is
Vi(u, x) Ex
Σ (S, So ~ p
where y discount factor. That is, Pl's value defined by evaluating P2's policy in the MDP M given Pi's reward function.
Because Pl's objective depends P2's policy, P1 aims to incentivize P2 to take policy that maximizes PI's own value.
Incentives side payments In the MDP, P2's original reward function without any incentive is R2: Sx A + R where R2(8, is the reward received by P2 for taking action in state 8. Pl's incentive to P2 is represented as a function æ: S x A + R+, hereafter referred to as the side payment. Specifically, x(s,a) is the additional non-negative reward that Pl offers to P2 when P2 takes action a in state s.
Given a side payment H, P2's modified reward function R2(x)) is defined as follows: For all (8, E SS A,
R2(8, a;x) = R2(s, + a()
(1)
We model P2's planning problem with side payment as an entropy-regularized MDP
M(x) = AS,A,P,147 R2(x)).
The value function of the entropy-regullarzzed MDP is defined by
(a( Ex
Σ y Ra(S,, 7 llg (s), So
where 7 is the temperature parameter that controls the amount of entropy regularization and reflects the level of rationality of P2. We assume that the temperature parameter common knowledge. The value given the initial distribution is written V2 (2)x), π) = V2(s, x))
Problem (Incentive design). P1's incentive design problem is the following bi-level optimization problem:
maximize EER E x
Vi(,,T)) h(x))
(2)
subject to
T" E Earg max max V2(u, (2(x),
sell
where h is cost function for side payment. The function h is LA- -iipschtt continuous and L-smooth (i.e., Vh is L-Lipschilz contivuous).
One particular choice of h is given by h(x) c|/2:111 for some constant. c c> 0.

---

Remark 1. P2's reward function with the incentive con be more general than the sum of P2's original reward and the side payment. Our resulls only require knowing the derivalive of R2(8, a; for all E S and a E A. This holds, for example, when [2(s, a;æ)) R2(s, a) f(z a), where f(,, s, a) is an Ly-LLipschtzzcomtinvun function for all 8 E S and a E A. We omit this generalization for clarity in the main results.
The optimal value function Vi of the entropy-regulariee MDP satisfies the following regularze Bellman equation (Nachum et al. 2017):
(s, (2(x)) log Σ
[x 7BB (d', Ra(x)))/T); V
aEA
Note that, as r approaches 0, equation
recovers the standard optimal Bellman equation.
Let (Ra())) SxA + R the optimal state-action value function of the entropy-regularized MDP under reward (z):
Q' (s, a, R2(x)) R2(s, a; a) Et V/ (s', R2(x)).
For a fixed temperature parameter т, the optimal policy of the entropy-regularized MDP is uniquely defined by
exp(Q (,()))))))( n" a) Ed'es exp(Q"(x, R2(x))/T)
(4)
For convenience, for any 0 E R define the softmar policy we as
exp(0x.a/T) no (8, a) ENEA exp(0x,a
(5)
Then, the optimal policy the rotropy-rogularized MDP can be written succinetly as (R)(R(())), where Q" (R2(z)) is viewed as vector in R [SxAA
3 Adaptive Incentive Design via Gradient Ascent
Due to the relation between the optimal policy and the optimal state-action value function of the entropy- regularized MDP given by equation 4 the lower-level problem in the bilevel optimization problem in equa- tion 2 has unique solution (R2(()())) Thus, the bi-level optimization problem reduces to single-level optimization problem using constraint climination:
maximize =
Vi (R))())) - h(z).
(6)
For convenience, we denote the objective function by J(x) A Vi ((- h(()).
Lemma 1. The function [x) can be non-concave.
Proof. We provide a concrete example, in which the objective function J(x) is non-concave. Consider a simple MDP in Figure Ia] both states and are sink states. The follower receives a reward R2(1) = 0 if state is reached, and (2) if state is reached. The leader receives reward of Rı (1) when state is reached, and (2) 0 if state 2 is reached. The temperature paramcter 0.1. The leader only assign nonnegative sidepayment to state 1. The cost function h(z) |z].
The follower has two actions 01, 02 from state 0 and both have deterministic outcomes to reach state 1 and 2, respectively.
In this example, the follower's best response policy given leader's decision a is 7 (0,a);)) x exp((R((1)+z)) and (0,, az;x) x) x exp((R2 + 7))
The objective function is
J(x) Rí (1) m(0, a1) R2( =00,a2) h(x))-
5

---

60-
-1.0-
61.P =
-20-
02. ==
-10-
(a) A small MDP.
(b) The plot of the objective function (())
Figure 1: An example to illustrate the non-concavity of ((r).
The function J(x) for x e [0, oc) has local maximal solutions and one global optimal 0, as shown in Fig. 1b
3.1 Computing the total gradient: The case with known P2's reward
We consider using the gradient-ascent method to find that maximizes P1's objective function. For any A, define (0) Vi (H, (o), using which one can write J(x) (Rz())) M(x). Following the chain rule, the derivative of J is given by
DJ(x) = (Q(
(Q2 -D2( Dh(x).
Because h given, Dh(r) can be computed analytically. Similarly, DR2(x) can be computed analytically given the function R2. The derivative DJı can be computed using the following proposition. (Recall that the derivative and the gradient of real-valued function J1 are related by (0) (O)
Proposition 1 (Agarwal et al. (2021)). Let no be the softmax policy defined by equation 5 Then
(0) V.. (R) = END [Ri()) log To(p)).
(8)
where P 50, 00. 81, 0ls... Sn, On is the path generated from the Markov chain Mr.. Te(p)
Th= P(s--118;, (s), at) is the probability of the path p from the Markou chain Ma and R1(p)
7 R1 (sk, ax) is the cumulalive reward of the poth p. For path p, the gradient V log No (p) v To ax), where V log a) can be computed follows:
0
if + 8,
b log a)(s,a)
To(s,a))/T
if s and ā if = ă and a # à.
(9)
00,,
T)(
The derivative DQ can be computed using the following proposition.
Proposition 2. Consider an infinite-horizn MDP M = (S, A, P, 80, 7, with discounting. Let Q+ Sx R be the optimal state-action value function of the entropy- regularzee MDP under the reward function r. For any (s, a), (8, a) S A, holds that.
aQt (1,,))(8, BBBop(paa)) a'eA
Σ (s 8Q
(10)
Ōra.ä
Dr
where
{1
of (s. (s.a)=
(x,a)(8,
0 otherwise.
(11)

---

Proof. According to the entropy-regularizze Bellman equation action value function Q* satisfies
Nachum et al. 2017 the optimal state-
Q"(,,ar)) ((,,) + + T llg Σ exp (ep(@"(6,
a'EA
or equivalently, by treating both (r) and as vectors R |SxAl
(r) reaa 3BBenP((s,))
T Flog Σ exp (Q (()
(12)
a'EA
Let Z(s) - Loed exp (Q)(s, = exp
Taking the derivative with respect to ra,a
both sides of equation 12
one can obtain
8Q2. (1,8)(8, + P(epaa))
aQ'
exp(02
Örg.a
*(8")
Ors.a
a'EA
oQ' Ōrz,
(3,,)((8,a) + P(ssa)
1xpl (r(//T))
Z(0')
d'EAA
0Q
=(,a))(s, a) (BB
(r) a')
Ørsa
a'EA
where the last step follows from (T)(t) exp(=( (8', x)/r)/Z(x)) ex (+)-)//(())
For any given (8, E S x A, equation 10 is in the form of the standard Bellman equation for stale-action value functions. This implies that the partial derivatives
{ 1QQia Orz.a
8 SES,
can be computed using any method for solving the Bellman equation. The partial derivative of Q with respect to the reward ra,a be interpreted as the discounted number of visiting state-action pair (ś, under the entropy-regularizee optimal policy (Q*(r) after taking the action in the state s. If a state-action pair is visited more frequently, then the optimal state-action value function is more sensitive to the changes in the reward for the stale-action pair. Moreover, the derivative with respect to the current stale-action pair is also influenced by the derivative with respect to future state-action pairs under (Q*
Algorithm describes the gradient ascent method.
Next, will conduct the convergence analysis of our algorithm given known P2's reward. Proposition 3. The total derivative DJ of the objective function is Lipschitz continuous: There exists L > O such that for all 21,
[DJ(()) - - DJ(xz)ll < L||e1 x2]1-
Proof. See Appendix A.2
Theorem 1. When n S 1/L, Algorithm
converges asymptotically to stationary point of J as l
Complexity analysis for per-step gradient computation For each state-action pair a), the com- plexity to caleulate oq- (([S)2[A[) because it is equivalent to policy evaluation. Consider the reward P2's original reward and side payment,
Br..
function with side payment defined as a linear combination R2(s, a, .)) R2(s, a) + x(s,a), for cach (s, a) E 5 x A. Suppose that only a subset Z C S A of state- action pairs are allocated with nonzero side payments, that is, a(s, a) 2 for (s, E and z(s,, a) for (s,a) a) & Z, then the time complexity to calculate (Ra())):) (R2(x) is O(Z7) |S| This analysis

---

Algorithm Incentive design given P2's reward
1: procedure GRADIENT-BASED INCENTIVE DESIGN GIVEN P2's REWARD
2: Initialize To, 60 > 0;
is the step size, 6g is a termination threshold and is close to 0.
3: k +-- 0:
4: Solve P2's optimal state-action value function of (Ba((=))))
Jf ((oo):
8 8+-0;; 00;
while 8 2 60 do
8:
Calculate the gradient DJ(xx); Ik+1 t ProiRISAA (ox + nxJ((x)); Jk+1 ((
9:
> Projection to non-negative orthant.
10:
11:
8 - [jktt |b;
12:
k k 1;
13: end while
14: return Σk-
15:
end procedure
informs that in practice, the leader may need to constrain the number of state-action pairs be allocated with side payment to reduce the complexity in calculating the gradient terms, instead of allocating side payment every state-action pair.
In the general case of reward with side payment, for each (s, a) E SSS A, R2(8, R2(s, a) + f(x, 8, a). Let x E R be K-dimensional vector. Thus, the term (22(x) (z) is dense square matrix of size (|S]||| x K). The term DQ (R2(x)) is a dense square matrix of size ([S)|A|)² and is computed with a time complexity of 8Q" O(I ||| [|) because Dra. is to be computed for each (s, a) S x A. Thus, the time complexity of calculating DQ' (R2())) (2)(2) in the general case is given by OKK]S A/2 + ||))
3.2 Estimating the total gradient: The case with unknown P2's reward
In the previous section, we discuss how to use a gradient-based algorithm to find an optimal side payment that maximizes Pl's total payoff. However, the method assumes that P2's reward function is known to Pl. In this section, show that the proposed gradient- baaee algorithm can be extended to the design of adaptive incentive when P2's reward is unknown. In this setting, at the beginning of the interaction, P1 has incomplete information about P2's reward function Rg. Instead, P1 can observe P2's decisions (in the form of state-action trajectories) under any side payment chosen by P1. P1 is allowed to interact with P2 repeatedly by choosing different side payments, through which P1 aims to eventually find a near-optimal side payment. The term adaptive incentive design analogous to adaptive control, because the algorithm adapis to the unknown reward of P2 and optimizes the side payment through interactions.
Our approach is to estimate the derivative DJ using the trajectories generated by P2. First, it can be seen from equation that both D (2,(z) and Dh(r) are independent of P2's reward function and can be computed as before. For (Q* (Q2(((()))))) recall the following sample-baser approximation of DJ:
(0) E, ( log To (p))
Σ V
Ri(pi)
Σ (a.))En
Vlogno(s,o) (13)
X
where X (p. ii N] set of sampled trajectories under To for 0 (R2(())) However, because P1 has no information about P2's original reward R2, given side payment I. P1 cannot solve P2's entropy-regulariized optimal policy and thus cannot directly compute the gradient V log (p)).
In order to calculate the gradient term in equation 13 without knowing the exact policy, we estimate a policy from the sampled trajectories. If a state-action pair (s appears in Ps E X for some i, then we need to compute V mo
(s, a). A simple maximum- maximum-likelihood estimator for ne is (s, N(s.e) where N(s, a) is N(s)
8

---

the number of times that (s appears in X and N(s) - EoEA N(s,a). The estimated policy Ao can be used to approximate V T a) based on equation & log ko(a.))
+1 - a)) 2 +1 ft a)), and a') = - - (s. d'). If state does not appear in any trajectory in X, then N(s) 0, and there is no information to estimate x(s, for any a E A. However, given the policy gradient estimate (0) is computed from the sampled trajectory, then the term V log TT(8, a) will not appear in the gradient estimate for unseen state 8.
20,..
8 llo (s(aa) 60,,''
aQ" for cach (š. â) where We also need find the gradient DQ" (R2(2)). For this step, we need to estimate ärg,a
(Rg())sa # 0 for any s',d'. This step of calculating aq'. is equivalent to data-driven off off-py evaluation given the reward function r(s.a) if (s, a) (š, â) and r(s, = 0 otherwise. So, we can use Monte Carlo policy evaluation (Precup 2000) to construct an unbiased estimator DQ*(R2(x)) of DQ (R2(z)).
8ay'a'
Brs.a
To make sure that the estimated gradient unbiased, that is,
(D01000)) (R((()(R)(()))) (R2(T)))) = (R())) (RQ())))))
we use two different samples X and X2 estimate the value of (Rs(()()s(z)) and (Q((R2(x)) respec- tively. This operation ensures that two estimates are uncorrelated.
Algorithm 2 Adaptive incentive design without knowing P2's reward
procedure ADAPTIVE INCENTIVE DESIGN WITHOUT KNOWING P2's REWARD() )
Initialize To, 77 60 0;
17 is the step size, óg is termination threshold and is close to 0.
k+ 0;
4: Collect two sets of P2's trajectories X,, Xi given P2's best response to (xo);
5: Jo + Ixjuxzi Epextux3 (p) h(xo):
8 8+ :0;
while 8 > 60 do Estimate (J((Q from X
8:
Estimate (R((()) using Monte Carlo policy evaluation from X2: (J((x) (Q' (fx))) (Q2(m))mx)) DR2(xx) Dh(r=s;; Projection to non-negative orthant.
10:
11:
Fk+1 + !sxal (I + (x())
12:
Collect new trajectories , X2, X given P2's best response to R2(xx-1);
13:
X1-1 t X141 UX
Jut + |841al Epexem Rp) -((x+1);
14:
8 + 1-1 -1-1- -ftl
15:
16:
kek+1 k+1;
17:
end while
18: return I*k
19:
end procedure
Algorithm 2 describes an adaptive incentive design without knowing P2's reward function. At the k-th iteration, P1 employs a side payment Ie and observes two sets X1, X2 of sampled trajectories from P2's best response given (zxz)). The gradient (xx( of the objective function is estimated from the two sets of samples and then used to compute the updated side payment 2*+1- The algorithm terminates once P1's value does not change more than óg between two consecutive ilerations.
Next, we show that without knowing the follower's 's reward function, our algorithm still converges to local optimal solution.
Proposition 4. The gradient estimate DJ(x) is unbiased.

---

Theorem 2. Let (oK)REN be sequence of side payments generated by adaptive incentive design in Algo- rithm With the step size 1j = LVT we have that
2 2v2L(sup,
ZER 9x J(x) (x
min
B[DJ(
Equivalently, for a given c <> 0, it requires T T= O((²) iterations to ensure mink=u,.... 1n (I)x c.
4 Incentive-invariant reward shaping
Our proposed adaptive incentive design requires no knowledge or learning of P2's reward function. An alter- native approach is learn P2's reward function from observed trajectories P2, using inverse reinforcement learning methods (Abbeel & Ng. 2004; Ng & Russell 2000 Ramachandran Amir 2007 Ziebart et al, 2008), and then apply the incentive design with the learned P2's reward case. For more information about inverse reinforcement learning algorithms, the readers are referred to the survey by Arora & Doshi 2021
Let's refer the second method as reward baased incentive design. However, it is known that inverse reinforcement learning is ill-posed because there can be multiple reward functions that generate the same optimal policy (Arora & Doshi 2021). In that case, no amount of data can distinguish them. These reward functions are known as policy invariant.
For the reward-learning-baasee incentive design, we are interested in the following question: Given two reward functions R2 and R2 that are policy-invariant to each other, these two rewards also ceenntive-inooriniii Namely, is the optimal incentive design for P2 with reward function Rg also optimal incentive design for P2 whose reward function is R
First, we consider a class of policy-invariant reward functions defined by potential-based reward shaping Skalse et al. 2023 Ng et al. 1999).
Definition 1 (Potential shaping). A potential function is a function é : S + R, where d(s) = if s is a obb//bbsgbingg state. Let R2 and R2 be reward functions. The R2 is produced by a o6-polenlial-ban baseed reward shaping of R2 if
R5(0, a) = R2(8, + -1E5 M(s).
For simplicity, let a(s,a) P( (s') ((s) be the shaping reward function.
The following results are shown in Skalse et al. (023) and paraphrased.
Theorem 3 (Skalse et al. (2023)). Given an MDP M = (S, A, P, R) and temperature parameter the entropy-regulater policy π determines R up to potential- based reward shaping.
In other words, if R is a @-potential based reward shaping of R2, then an nntropy-regulate optimal policy æ with respect to Rg is also entropy-regulated optimal policy given the reward function R
Next, we prove the following theorem.
Theorem 4. Given an MDP M and a temperature parameter T, the leader's reward function R₁ and side payment cost function h, if P2 selects an entropy-regulated optimal policy given reward R2(x) for any side payment x, then the optimal incentive design x² for P2 with reward R2 is optimal for P2 with reward nt..
The above incentive-invariance condition holds when P2 selects the entropy- entropy-regulated optimal policy given the reward function. However, the result naturally generalizes to the case when P2 selects maximal supportive optimal policy with respoct the reward function. An optimal policy is mazimally supportive if it takes all optimal actions with positive probability. The maximally supportive optimal policy is not unique.
Corollary 1. Given an MDP M and lemperature parameter T, the leader's reward function Rí and side payment cost function h, if P2 selects mozimally supportive optimal policy given the reward R2(x) for any incentive design x and always break the tie in the favor for P1 (formal definition in the proof), then the optimal incentive design x² for P2 with reward R2 is optimal for P2 with reward Rt.
10

---

Model based
0.37
Sample size: 20
1.3
payort]
0.36
Sample
Sample size: 200
Vgint
1.0
Vaint
Value
0.34
0.33
0.32
0.7
0.390
0.30
0.4
0.29
0.375
0.3
0.27
0.370
0.0
0.26
150
160
170
180
190
200
50
100
150
200
Iterations
(a) Model-based result in small MDP.
(b) Model-free results in small MDP.
Figure [Left] Incentive design with known follower's reward functions and different cost functions for side payments. Rightt] The convergence results of adaptive incentive design with unknown follower's reward functions, with different sample sizes usod for gradient estimation. All results are for the small MDP example.
5 Experiments
We illustrate the proposed methods with two sets of examples, one is a probabilistic graph-based MDP and another is a stochastic gridworld + For all case studies, the workstation used is powered by Intel i7-11700K and 32GB RAM. experiments, we constrain the leader to allocate a subset of state-action pairs with side-payments. This constraint reduce the computation for gradient calculation (rocall the complexity analysis in Section 3.1 and can be removed if more powerful GPUs are used.
5.1 An MDP Example
We consider first small MDP in which the follower has four actions ["a", "b", "6" "d"]. For clarity, the graph in Fig. 2 only shows the transition given action a where a thick (resp. thin) arrow represents a high (resp. low) transition probability, self-loops are omitted. For example, P(O, "a") = {1 0.7,2 0.1,3 0.1, 0.1). Once the follower enters states {10, 11, 12), the follower enters the "Sink" state with probability 1 by taking any actions. The follower only receives a reward of when he visits state 10. The leader only obtains reward of I when the follower visits state 11. The discounting factor is 0.95 in this example. In order to incentivize the follower to visit state 11, the leader offers aide-payment to the follower the follower visits state 11 and takes action a, which mcans the domain of variable x is confined to X' = (x a(s,a) = 0, V(s,a) A (11, a), x(11,a) 0}. The follower's reward with the uddeppayment is simply the sum R2(s, a, (s(s, a) + a(s,a), for all (s, S A.
Figure 2: Illustrating the graph of a small MDP.
We consider the cost function of making side-payment in the form of l(()) c||-||i- We conduct the experiment for a E {0.1, 0.2, 0.3, 0.4, 0.5). Figure 3a shows the result of the leader's 's total payoff( [ x, T)), the leader's expected value Vi (T)), the follower's expected value (V2(T)) given the follower's best response policy and the reward R2(-, 2), and the value of ||œ/[2- When the leader does not offer any side-payment. the leader's expected value 0.152, and the follower's expected value 0.531. In this case, the follower visits due the probabilistic outcomes of the policy.
!Code: http::///ttt.cccooaaaaaaaaatatta

---

It is observed that when {0.1, (0.1,0.2,0.3) the leader's side-payment policies h(z) are similar, where a(11, "a") x 1.33. These similar side-payment policies result in similar best response policies from the follower, and thus the similar value (T) ~ 0.648 for the leader. However, the total payoff of the leader decreases due to the increasing cost of side-payment. As c increases to 0.4, the leader's side-paymen policy is xr11, = 0.108, and the corresponding leader's value (1(z) is 0.198, and the total payoff J 0.155.
If the leader's side-payment policy given c 0.4 is a(11, "a") s 1.33 (used when 0.3), the total payoff J is 0.127, which indicates the cost of side-payment outweighs the benefit to the total payoff. Finally, when increases to 0.5, the leader does not offer any incentive. As ranges from 0.1 to 0.5, the follower's value (r) given the best response policy to reward ar) decreases due to the decrease in the side-payment When e = 0.4, the follower's value is 0.543. When = 0.5, the leader stops offering any side-payment and the follower's expected value is the lowest 0.531, recovering the original follower's value without any incentives.
Next, we consider the scenario, when the follower's reward unknown to the leader. We fix to be 0.2. Figure 3b shows the value of leader's total payoll converges over iterations, given different trajectory sample sizes used in the gradient estimates. Our result shows that in the first 150 iterations, the convergence trend is stable in all three cases, compared to the model-based approach. After 150 iterations, oscillations are observed with a small sample size (20). After 200 iterations, the algorithm converges for all three cases with different sample sizes. The result. indicates that the leader can obtain the optimal incentive design without estimating the follower's true reward function.
5.2 Gridworld Example
In the second example, we consider robot motion planning problem in stochastic gridworld. Consider six by six gridworld in Figure 4 The robot aims to reach a set of goal states while maximizing its payoff. The robot intended cell with - 2a probability and enters the neighboring cells, which are west and east cells with a probability. In our experiments, a is selected to be 0.1. Each state is identified by its coordinates (i, denoting the state at row and column j. The robot's lask is to reach one of the green or blue cells. Entering a green cell yields a reward of 10, while entering a blue cell results in a reward of 8. The process terminates once the robot enters one of these blue or green cells. Upon entering the states with fire, the robot incurs punishment of -5. The leader only receives reward of 10 when the robot enters a blue cell. Thus, the leader is to incentivize the robot to visit the blue cells. The discounting factor is 0.95.
move in four compass directions. Given an action, say, "N", the robot enters the
We first conduct the experiment on the model-basee case. The cost function of making side-payment is in the form of h(x) = e||æ||ı- Assume the leader can incentivize the robot with side-payment x, constrained by x E X = {x I(8,a) a) = 0, V(s, a) * ((0,3), "N") and z(00, 3), "N") 0}. The experiment results under various values are shown in Figure 5a When is less than 1.1, the sido-payment value and the leader's value slowly decrease with the increase of the c. However, when reaches 1.1, the leader opts for strategy of assigning 0 side payment to the state-action pair ((0,3), "N"). If the leader were to maintain the same side-payment policy as the policy when e equals 1.0, the resulting total payoff is negative. That indicates placing side-payment at state (0,3), "N") becomes disadvantageous for the leader's overall payoff when 1.1.
4
3
+
2
1
0
5
Figure 4: A 6 x gridworld.
We also conduct the experiment under different constraint set X" = fa x(s,a) = 0, Vs & {11,4), (4, 5)), 2(s,a) 2 0. for (s,a) E {(1, (4,5)) x A}. Our intuition is that the robot selects to reach a cell where it obtains the highest reward. Thus assigning side nade-p to other states only incurs a cost the leader's total payoff J. Given the environment, costs less side-payment attract the robot 41, compared to 5). As shown in Figure 5bb for 0.1 $ c 0.7, the leader achieves higher expected value compared to the result. when the leader allocates side-payment to ((0,3), "N"). But the leader also
12

---

Total payoft]
[|R])s
Value
V2061
Ysdel
Value
5
Tocal payoff
Vyfmi
0.3
0.4
0.8
0.1
0.2
0.7
C
(a) Model-based result in gridworld, given the leader as- sigus side payment (),,3), "N").
Model-based result in gridworld, given the leader as- signs side-payment at [(1, (4, 5)] A.
(b)
Figure 5: Incentive design results with known follower's reward functions in the grid world, with different side payment cost functions.
Model based
Model based
Sample
Sample
2.20
size: 100
Sample size: 100
Sample size: 200
3.76
Sample sizw: 200
Value
2.15
Value
2.10
2.20
3.785
2.23
2.05
140
160
100
150
200
0
50
100
150
200
Iterations
Iterations
(a) Model-free solution convergence trend gridworld, given the leader assigns side payment at ((0,3), "N").
(b) Model-free solution convergence trend in gridworld, given the leader assigns side-payment at {(1, (1,5)) A.
Figure 6: The convergence results of adaptive incentive design with unknown follower's reward functions in the gridworld, with different sample sizes used for gradient estimation.
allocates more resources, so higher leader's expected value (T does not necessarily mean a higher value for the total payoff J. In particular, when increases 0.8, the leader assigns 0 side payment, resulting in the leader's 's value approaching O.. But in the previous case with the constraint set. X, the leader can still allocate palmep to incentivize the follower, which leads to total payoff J = 0.814 when c = 0.8. These two sets of experiments indicate the significance of the state-action pairs chosen by the leader for allocating side-payments.
Next, we look into the model-free scenarios. Let us fix to be 0.3 and assume the leader allocates side- payments (), "N We conduct the experiments with different trajectory sample sizes and illustrate the results in Figure 6al As depicted, the results of the gradient-ascent algorithm for different sample sizes are similar in the initial 100 iterations. However, after 100 iterations, noticcable oscillations are observed, particularly when the sample size is 20. The oscillations also exist when the sample size is 100 but not that significant. When the sample size is 200, the convergence result over iterations is close to the model-based scenario. The final converged side- side-paydnn payment policies are similar with model-based methods across all cases.
Similar experiments are conducted given c 0.3 and the leader allocates side- dede-payment to {(1, 4), (4.5)) x A. We show the results in Figure ib and the results of the value versus iterations similar to the previous
13

---

cases. Due to the property of stochastic gradient ascent, larger sample size corresponds to more stable convergence.
6 Conclusion
We develop a gradient-based method for designing an optimal incentive policy that aims to motivate the follower to choose policies in favor the leader. The gradient- based incentive design hinges upon computing the gradient of the follower's policy parameters with respect to the leader's incentive decision variables. We show that if the follower uses an entropy-regulatee optimal policy, then the exact gradient can be computed in polynomial time. In addition, the gradient be estimated from the sampled trajectories generated by the follower's response. As a result, our method naturally provides an adaptive incentive design method where the leader can iteratively update his incentive policy upon observing sampled runs from the follower's policy, without the need to infer the follower's reward function. At last, we also show that the optimal incentive policies can be the same for two different followers' reward functions, provided that the two reward lunctions are related through a policy-invariant reward shaping. We experimentally validate the proposed method and discuss the stability of the convergence given various sample sizes used in gradient estimation.
The limitations of the method would be that if the leader has the flexibility to provide incentive for any state- action pair, then il is computationall, expensive to solve the optimal incentive policy. To improve efficiency, we could restrict the size of leader's incentive decision variables by selecting subset of statc-action pairs for allocating side-payments. Experiment results show that the leader's value varies given different sets of selected state-action pairs. How to optimally determine the subsets of state-action pairs for efficient computation is an important topic. Another interesting direction with respect to uncertainty in the follower's parameters, for example, the bounded rationality temperature parameter T can be unknown and belong a given range. It open question if the incentive design can be robust to small variations in these parameters.
robustifying the incentive design
Acknowledgements
Research was sponsored by NSF under award numbers 2207759 and in part by the Army Research Laboratory under Cooperative Agreement Number W911NF-22-1-011 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Taboratory or the U.S. Government. The U.S. Government is authorized reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Twenty- First International Conference on Machine Learning 1CML '04, pp. 1, Banff, Alberta, Canada, 2004.
ACM Press. doi:
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431 4506, 2021.
Tansu Alpcan, Lacra Pavel, and Nem Stefanovic. A control theoretic approach to noncooperative game design. In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pp. 8575-8580. IEEE, 2009.
Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, August 2021. ISSN 0004-3702. doi: 10.1016/j.aa artt:// 2021.. 103500. http:://ww.....aeece.........aaa
Susan Athey and John Roberts. Organizational design: Decision rights and incentive contracts. American economic review, (2):2000 205, 2001.
14

---

Jorge Barrera and Alfredo Garcia. Dynamic incentives for congestion control. IEEE Transactions Auto- matic Control, 60(2):299-3166 2014.
Patrick Bolton and Mathias Dewatripont, Contract Theory. MIT Press Books, 1, 2005. URL https: Publisher: The MIT Press.
//ideas. repeac..repe.oo httppppp....p/////tttt/////////a
Souradip Chakraborty, Amrit Singh Bedi, Alec Koppel, Dinesh Manocha, Huazheng Wang. Furong Huang, and Mengdi Wang, Aligning agent policy with externalities: Reward design via bilevel rl. arXiv preprinl arXiv:2308.0255 2023.
Siyu Chen, Donglin Yang, Jiayang Li, Senmiao Wang, Zhuoran Yang, and Zhaoran Wang. Adaptive Model Design for Markov Decision Process. In Proceedings of the 39th International Conference on Machine Learning, pp. 3679 3700. PMLR, June 2022. URL https://prooceeding. mlr pre.ss//112/chhe2222b. html ISSN: 2640-3498.
Keith Conrad. Equivalence of norms. Expository Paper, University of Connecticut, Storrs, heruntergeladen von, 17(2018), 2018.
Donya G Dobakhshari and Vijay Gupta, Optimal contract design for incentive-basee demand response. In 2016 American Control Conference (ACC), pp. 3219 -224. IEEE, 2016.
Dmitriy Drusvyatskiy and Lin Xiao. Stochastic Optimization with Decision-Dependent Distributions. Moth- emalics of Operalions Research, 48(2):954 998, May 2023. ISSN 0364-765X. doi: 10.1287 11128//mor... htt.///20222....... 2022. 1287.
URL btttps:/ppubooniie
informs http://ood///ooooo/o////e 1287/moor 2022. 1287 Publisher: INFORMS.
David Fasley and Arpita Ghosh. Incentives, gamification, and game theory: an economic approach to badge design. ACM Transactions on Economics and Computation (TEAC), 4(3):1-26, 2016.
Tom Everitt, Marcus Hutter, Ramana Kumar, and Victoria Krakovna. Reward tampering problems and solutions in reinforcement learning: A causal inffuence diagram perspective. Synthese, 198(Suppl 27): 6435 6467, 2021.
Y Ho and D Teneketzis. On the interactions of incentive and information structures. IEFF Transactions Automatic Control, 29(7):647 650, 1984.
Yu-Chi Ho, P Luh, and Ramal Muralidharan. Information structure, stackelberg games, and incentive controllability. IEEE Transactions on Automatic Control, 26(2):454-460, 1981.
Emir Kamenica. Behavioral economics and psychology of incentives. Annu. Rev. Econ., 4(1):427 452, 2012.
Yuqing Li, Bingyu Shen, Jinbei Zhang, Xiaoying Gan, Jingchao Wang, and Xinbing Wang. Offloading in hens: Congestion-aware network selection and user incentive design. IEEE Transactions on Wireless Communications, 16(10):6479 6492, 2017.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems, 30, 2017.
Andrew Y. Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In In Proc. 17th Interna- lional Conf. on Machine Learning, pp. 663 670. Morgan Kaufmann, 2000.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application reward shaping. In Ieml, volume 99, pp. 278 287, 1999.
Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Facully Publication Series, pp. 80, 2000.
Decpak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI'07, pp. 22911, San Francisco, CA. USA, 2007. Morgan Kaufmann Publishers Inc.
15

---

Lillian J Ratliff and Tanner Fiez. Adaptive incentive design. IEEE Transactions Automatic Control, 66 (8):3871-388 2020.
Yagiz Savas, Vijay Gupta, Melkior Ornik, Lillian J. Ratliff, and Ufuk Topeu. Incentive Design for Temporal Logic Objectives. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 2251-2258, De- cember 2019. doi: N0.109/CDC40000 201.999.779 URI. lnttps://keeexpporre ieee. wtg.ee/rraabbttt...oaeoo document/90299287 ISSN: 2576-2370.
Yagiz Savas, Vijay Gupta, and Ufuk Topcu. On the Complexity of Sequential Incentive Design. IEEE Transactions on Automatic Control, 67(11):5808 5824, November 2022. ISSN 001 0018-9286, 1558-25231 2334-
3303. doi: 10.1109/ 10.1109/TAC.200 TAC12102.11221111 URL https:///eeexpplores ieee. org//ocument/9599553
Paul Seabright. Managing local commons: theoretical perspectives, 7(4):113 134, 1993.
issues in incentive design.
Journal of economic
Marwaan Simaan and Jose Cruz Jr. On the stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications, 11(5):533 555, 1973.
Joar Skalse, Nikolaus Howe, Dmitrii Krasheninnikor, and David Krueger. Defining and characterizing reward gaming. Advances in Neural Information Processing Systems, 35:9460-998 9471, 2022.
Joar Max Viktor Skalse, Matthew Barrugia-Roberts, Stuart Russell, Alessandro Abate, and Adam Gleave. Invariance in Policy Optimisation and Partial Identifiability in Reward Learning. In Proceedings of the 40th International Conference on Machine Learning, pp. 32033 32058. PMLR, July 2023. URL https: /pproceedings. wwriiinnn..m....pp..m..mm mlr.prees/v202/ skalse23a html ISSN: 2640-3498.
Killian Wood and Emiliano Dall'Anese. Stochastic saddle point problems with decision-dependen distribu- tions. SIAM Journal Optimization, 33(3):1943 1001:-9933-996,,,,-- 2023.
Haoqi Zhang and David Parkes. Value-based policy teaching with active indirect elicitation. In Proceedings of the 23rd national conference on Artificial intelligence Volume 1, AAAT008, pp. 208 214, Chicago, Illinois, July 2008. AAAI Press. ISBN 978- 1-57733--------
Haoqi Zhang, Yiling Chen, and David Parkes. general approach to environment design with one agent. In Proceedings of the 21st. International Joint Conference Arlificial Intelligence, IJCAT09, pp. 2002-2008, San Francisco, CA, USA, July 2009, Morgan Kaufmann Publishers Inc.
Xinyang Zhou, Emiliano Anese, Lijun Chen, and Andrea Simonetto. An incentive-based online opti- mization framework for distribution grids. IEEE transactions on Automatic Control, (17)):019-20333 2017.
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse rein- forcement learning. In Proceedings of the 23rd National Conference on Artificial Intelligence Volume 3, AAAI008, pp. 1433-1438, Chicago, Illinois, 2008. AAAI Press. ISBN 978-1-57735-368-3.
A Derivations and Proofs
A.1 Derivation of policy gradient
The detailed derivation of policy gradient in equation g in Proposition 1 8 log (s.m))
Recall that
if s # and
00
log To (s.
i log exp exp(2e)
lag)
log En E exp
Pral
00 a.a
00.a
00 s.a
i expp( On.
1
(14)
Evee exp(
00 8.0
1
(1 (s, 0.)
16

---

and
Ölog (T(s,
1 (0 TT(s,
(15)
00 00,,a'
A.2 Proof of Proposition
To show that (xx is smooth (Proposition 3),
we first prove the following properties:
Proposition 5. Consider ((,0): + R the value function of softmax policy with parameter 0. For ony S, the value function (s,,)) is Lipschitz continuous, which is
[V 01) (ss, 02)1 S Lell01 B2ll.
where Le is the Lipschilz conslant.
Proof. Using the policy gradient with softmax policy, 00,,. (8) where d (s)
(V(a.))
(1 (1-7) Ei= 7² "pp (st = s|80 ~ (4) is the discounted state visitation distribution. Thus,
1 [oV(s, = dh (4)
(16)
Σ (dH (S)TT(S, A),
(17)
1 1-71
mmxx, T (s,a) a) (s)o0())))))))
(18)
Y
|max,,e 2.0 A (8, ())
(19)
1-7
Rmaal 1-7
(20)
where the last step is because [1 (s)To(s, (s)aa (dd S of the reward function.
[Rmaa! the maximum possible value
Let La [Bmaal we have 1-7
(V(s,01) (2sl s Lol10: -211. Vs E S.
Proposition 6. The function (1( & (14,0) is Lg-smooth, that is,
[() voJ(6')) S Lolle 8'112.
where La is Lipschilz constant.
The proof of Proposition 0 is based on Lemma 55 in Agarwal et al. 2021 by setting the coefficient before the barrier function to 0. Thus, omit the detailed proof here.
Proposition 7. Let (Rz(()) be the entropg-regulated optimal state-action value function in the MDP (xx, il holds that Q* (Rz(z)) is Lipschilz continuous in x, that is,
(R((m))))) - Q" (*Ra(12))1 < T.zl -22ll-
where Ly is the Lipschitz constant.
Proof. For notational convenience and clarity, let Q*(x) 2 (+2((x))
First, we start from the infinity norm term (x1* Q" (222)loc is noted that [[*((1) Q* m Q" (8, a1) Q* (s, a2)2))
17

---

By the definition of untropy-regularized state-action value function,
(* 2) Emq
Σ
y R2,, Ag:)) log ( (x) Ab) So s, Au = a
Thus,
(1( - (s, a.22)
(1))
(2(,, Açzi)) - (S, Ar) So 8, Ao =
D
(xg)
7¹t (Ri, A1aa2) (0g Ar) Σ
So s, Ao =0
(F1)
y RR((S Aç - To Ar)
So 8, Ao a
-Brgten
(R, Ax;22) - log log ( Ar)
So s, An =0
E
(S,,, Aga22) r log (o)) Ar) So 8, Ap
(x2)
RS,,, Agæ22) - mog (St, Ar)
So = 8, Ao =a
(
0
Emgr(n) I
7 (Ra(S,,A,ay) (5, So 8, Au = a
x
(S,,, Aga2)) - log 1o Ar)
So = 8, Ao
8
=EnQy(e))
Σ
72 (R2(S,, A;E1) (2, Ac: So s, Ao
ETggr(e)
7 max 21 (s', - 8'aa
1 |111 x2llox
where inequality (i) is because (xa) is optimal w.r.t. the reward function R2(x2).
Due to the equivalence of norms Courad (2018), the finite dimension C, for all x E C, B||2|| I | 5 B' || ooo where B, B' are two constants. We can rewrite the infinity norm case we used above to 1-norm case. Thus, we have [|Q* - Q" (Ra(zz)) < L E2ll-
Remark 2. Proposition holds for a more general case when for any state-action action pair (s,a) E S x A, the reward function R2(8, a, x. = R2 a) + g(s, a, a) for any Lipschitz continuous function g(-).
Proposition 8. DQ' (R2(z)) (22(x) is Lipschitz continuous with respect x. which means
|IQQ' (R2(x1)) DR2(11) - DQ' (R2(2))))) DR2(2z))l S Løllz1 22ll
where Lg is the Lipschilz constand.
Proof. By Proposition 2 it is noted that
as,07, Engres
Σ faaaaS Ar) So 8, Ao = (s,
0r(3,ā)
18

---

where (x)) is the state-action value function given the policy ())())) and reward function fs.a defined by (8, (,, a). Thus
|DQQ (R2(z1)) - DQ (B2 11Q (TQ0 - Q (TQr
(21)
S (R2())) - Q" (R2(12)))
(22)
Equation 22
1 This because the derived based on Proposition where the Lipschitz constant Le 1-
reward function is indicator function and Amax = 1 and the entropy-regularized optimal policy (Q-(Ra())) has softmax parameterization with policy parameter Q* (R)(())).
Combining equation 22 with Proposition 7 we have [IDQ*(R2
DQ & Lo x2ll.
Since R2(2)) is a linear combination of the original follower's reward function R2 and a Lipschitz continuous function f æ. Let be Lipschitz continuous with a Lipschitz constant Ly, then we have DRy(2) S Lg. a special case when R2(2) = R2 + b x,, then Dr(x) = Ly. Thus, (R2(()) DR2(2)) (Ra(((())) (22(12)) < Ly || x2l|- The proof is completed by letting Lg Lohe
In the next, we show a general result and the Lipschitz continuity of the term (Ji (R2(x))) (Rz(() (R2(2) can be derived by letting f(x) DJ1 (Q" (R2(x))) and g(x) = DQ (R2(a)) DR2(2)) Lemma 2. Let f: + Rmx and g: X + R" be two Lipschitz continuous functions with [f(x))) 3 and [[(())]| S for all x E X. Then f.g is Lipschilz continuous.
Proof. Since I and are Lipschitz continuous, there exist Ly and Lg such that that [í(x) - f(x))l z Ly|| - 2'|l and (la(x) - g(x')ll < , - x'll for all x, E N. For any x, x' E N, one can obtain
[f(())(()) f(x')
- (=(1')((('))) < (1((x))(z) - (00 - ((x')((2)1)
= [l(())(()) -
< (1(((x) -(=d))/lo( (1/()))) 2((())
S <04ل|lx-- - +1411
= + + + 1'
which implies that f g is Lipschitz continuous.
Finally, ready to prove Proposition g
Proof. Function (xx is non-concave but differentiable our setting. Tts total derivative DJ(x)) is Lipschitz continuous because
1) Dh(x) is Lipschitzzcoontimoous due to the assumption of h(x) (sce Problem
2) DJ (R(((E)) is Lipschitz continuous function and upper bounded by Rmas (Proposition 5
3) (Q*(R2(z)) (22(2)
Furthermore, because [Q(((R(()))l is the norm of state-action value vector given policy (Qz(R)())) and indicator reward functions, is upper bounded by 1. [[) I Ly given R2(s, a, x) R₂ + f(s,a, where is Ly-Lissciitz continuous. Thus, (R(()) DR2(=))l upper bounded.
Lipschitz continuous function (Proposition
4) (J* (Rz(z))) (R2()) (R)(z) is Lipschitz continuous due to the aforementioned properties 2) and 3) and Lemma 2 where ((x) is DJ, (Re(x)) and g(x) is DQ" (Ra(R)))) DR2(x).
19

---

A.3 Proof of Theorem [
Proof. Given the update rule we used in our algorithın #1+11 = R sxA (Ix + (x)). We want to show as k - 00, F& converges to a critical point. Following the Taylor expansion of function J around 24, for a sufficient small step size 7, we have
Tnp [VJ((=)]1 2
J(zx+1) - (xxk) 2 7/ [|[])(
(23)
= =11 Ln ml VJ(x))11
(24)
Using 17 - Z: we have (1 (1- L 2' Thus have J( - Jaxx) 3 Which means J 1 JIx) is always positive. Moreover, function J(-) is bounded due to the value function of the leader (0) is bounded. Therefore the function J(r) is monotonically increasing and bounded. Due to the Bolzano- Bolzano-Weierstrass Weierstrass Theorem, every bounded sequence of real numbers has a convergent subsequence thus, the gradicnt-bar based method converges to a local optimal point of the function J(z).
A.4 Proof of Theorem 2
Proof. Consider the estimated gradient from the observed P2's trajectories:
DJ(z) = D. (22(((( DRy(#1) - Dh(x,)
First, the term (Bg(()()) is the estimated policy gradient with respect to Pl's reward function. For notational convenience, let B & (x, be the ontropy-rogularized state-action value function.
Since P2's reward function unknown, we replace the exact gradient term log (p) in equation with the approximated gradient V dog)a(()) The bias of the estimator is
E
(0) (0)
(25)
EE
To
(o( log to (p)
(f
E
(o(p) (V log (p())
V Vlog (o) dp)
=E
(1(P)
V Vlog TT(s)) - log (sg dp
lel
/ (p)
Σ
E (V log To(si, a:) V log (og, dp
=0
The last step due to the (s, a) the unbiased estimator of ((s, a). To see why this is the case, consider those non-zero elements in V log To (s), from equation g we have
log
Ölog t
E
E (ftoss))) To(s, a)) 0.
00,
00
So, E ( log (8;, oz)
V Vlo a:)) = O. and we have last step equals to 0.
For the second (erm DQ* (Rz(())))) based Proposition & (Ra(()))) is the policy evaluation of the indicator reward function (s a') = (s,a)(s',a a') with respect to the policy sQ.. We use a Monte Carlo policy evaluation for computing DQ* (Ry(zz) from sampled trajectory (Precup) 2000). because known to be unbiased estimator of DQ' (Rz(x:)).
20

---

Next, consider the product term DJ1(Q" (Ra(z))) (Q*(RR(2z)) Given that both (Rg((z()((za)) and (Q*(R((1z)) are unbiased estimates for (R((()(R((z)) and (R2()) based our aforementioned analysis. We select two independent samples to estimate (Ji(Q (z)) and (Q((D)( By doing so, the covariance between these two estimates to be Hence, we arrive at the conclusion that DJ(x) is a unbiased estimator of DJ(x).
A.5 Proof of Theorem 4
Proof. Given P2's reward R2, denote by BR( the entropy-regularized optimal policy (best response) of P2, which is unique. Suppose x² is an optimal incentive when P2's reward is R2. This implies max, BR(R((zr)) J(x (T) B [z, π) for all
Slightly abusing notation, we refer to R2, F. Ry by their vector representations. Since F is potential-based reward shaping for R2, by definition it is also potential-based reward shaping for R2(2), for any x. Due to Theorem 3 we have (R)) = (R) + F) (R)) for any (including x*). Thus, it follows that max max =BR(R(()(() , 2 max max 1=BR [zz x) for all æ, which implies that x" is also an optimal incentive design when P2's reward is R2 R2 F.
A.6 Proof of Corollary 1
First, the following result is proven in Skalse et al. (023)
Theorem 5. [Skalse et al. 2023) Given an MDP M (,, J, R) and temperature parometer т, the marimally supportice optimal policy n determines R up to polenlial-based reward shaping.
Proof. The proof is similar to that of Theorem With few changes to handle the non-uniqueness in P2's maximally supportive optimal policy. Given P2's reward R2, denote by (RMs(R2) the set of maximally supportive optimal policies (best responses) of P2. Suppose x² is optimal incentive when P2's reward is Rg. This implies that when P2 breaks the tie in favor of Pl, that is, P2 selects ग E (Ras(B2(11))) that maximizes Pl's value J(x", T), then (aXrEBRMss(Ra(e")) [x= T) 2 maX J(r, π) for all x.
Since is a potential-basod reward shaping for R2, by definition it is also potential-based reward shaping BRass (R2(x) F) BRMs (R (R)(x) for
for R2 + x, for any x. Due to Theorem 3 we have BR (Ras(RRg(:)) any (including x²). Thus, follows that max SERRs J (x=" T) max REBRiss (R](a)) [ar л) for all x, which implies that x² also an optimal incentive design when P2's reward R..
21


Reviews:
[{"review_id": "c4PTrcNFU7", "reviewer": "Reviewer_soZq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The proposed method doesn’t require knowing follower’s reward function, which makes it quite general\n2. Good theoretical foundations with convergence guarantees\n3. Experimental validation on probabilistic transition systems and gridworld environments shows the effectiveness of the method\n\nWeakness (not necesarily weakness, more towards future directions)\n1. I’m not sure about the scalability of the method since it scales with state-action space size.\n2. The experimental validation could be expanded to more complex scenarios", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the problem of incentive design in Markov Decision Processes (MDPs) where a leader aims to influence a follower's behavior through reward modifications without knowing the follower's original reward function.\n\nKey contributions include:\n\n- Development of a gradient-based algorithm to compute optimal incentive designs without requiring knowledge of the follower's reward function\n- Theoretical analysis proving convergence of the proposed method\n- A method to estimate gradients from observed follower responses\n- Analysis of conditions under which incentive designs remain optimal across different reward functions that are policy invariant", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Would be interested to see more discussions around the local vs. global optimiality of the proposed method.", "broader_impact_concerns": "No concerns on ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5qVBJx0Y5Q", "reviewer": "Reviewer_MbQe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Incentive design with no knowledge of the follower's reward function is an important yet underinvestigated problem\n- Gradient based algorithm is an interesting solution that shows promising results\n- Theoretical analysis gives some good mathematical grounding to the method\n\nWeaknesses:\n- Clarity: paper lacks clarity at times and it can be hard to understand what is the objective of each section - e.g. section 3, \"Main result\" does not say much, while Algorithm 2 is only introduced much later.\n- Section 4 is not very novel. It basically corresponds to Inverse Reinforcement Learning, but no work or literature from the field has been cited nor discussed. \"there can be multiple reward functions that are consistent with the data\" is the reward ambiguity coming from Inverse Reinforcement Learning being ill-posed.\n- Method is tested only in very simple if not toy settings. While these are good for understanding the behavior of the method, the paper lacks testing in a more complex setting.\n- No code for reproducibility", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the problem of incentive design in a leader-follower setting, i.e. how can the leader influence the follower's policy in order to maximize their payoff. The particularity of the problem tackled is the fact that the leader does not know the follower's reward function. \nAfter introducing the necessary background, the paper presents its main gradient based algorithm to find the optimal incentive design solely based on observations of the follower's behavior. It also provides some theoretical properties and guarantees on the algorithm, before showing empirical results on its behavior in simple environments such as gridworld.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vzN6crCUPb", "reviewer": "Reviewer_DgTw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe authors clarify the situation of their work in estimating the leader’s optimal incentive design, without knowing the follower’s reward function, even though the extent of the effectiveness is not certain due to the limit scope of the experiments. \n\nWeakness\n1. The bilevel optimization problem is known to be hard to solve and I think it simplifies the problem too much when reduced to the single-level optimization problem, deviating from the original optimization problem.\n2. The experiments part is not solid enough to verify the effectiveness of this method, without comparison of other state-of-art methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a gradient-ascent algorithm to compute the leader’s optimal incentive design, without knowing the follower’s reward function. Based on the assumption that the follower’s response satisfies softmax temporal consistency, the paper designs a method to compute the exact gradient of the follower’s policy with respect to the incentive design variables, getting an unbiased estimator of the gradient terms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add comparison to other methods in the experiments part. It can also be compared with the ideal case where the follower’s reward function is known, to see the gap between the best possible result. \t\n2. The structure and the notation in the paper can be more clear. What is the relationship between Section 4 Incentive-invariant reward shaping and the main results? Is section 4 proposing another way to estimate the follower’s reward function compared to the Monte Carlo policy evaluation proposed in section 3?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The recommendation is to accept the paper subject to the following minor revisions that the authors promised in the rebuttal, but did not include in the latest version:

1. Add a discussion and references about related work in inverse RL.
2. Provide a link to the source code for reproducibility.
3. Improve the clarity by revising section titles to be more informative and revising the structure of the paper.
Decision: Accept (poster)