Stackelberg Learning with Outcome-based Payment
Authors: Tom Yan
Chicheng Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Multi-agent learning
Learning with Incentives
Outcome-based Payments
Primary area: theory

Abstract: With businesses starting to deploy agents to act on their behalf, an emerging challenge that businesses have to contend with is how to incentivize other agents with differing interests to work alongside its own agent. In present day commerce, payment is a common way that different parties use to \emph{economically} align their interests. In this paper, we study how one could analogously learn such payment schemes for aligning agents in the decentralized multi-agent setting. We model this problem as a Stackelberg Markov game, in which the leader can commit to a policy and also designate a set of outcome-based payments. We are interested in answering the question: when do efficient learning algorithms exist? To this end, we characterize the computational and statistical complexity of planning and learning in general-sum and cooperative games. In general-sum games, we find that planning is computationally intractable. In cooperative games, we show that learning can be statistically hard without payment and efficient with payment, showing that payment is necessary for learning even with aligned rewards. Altogether, our work aims to consolidate our theoretical understanding of outcome-based payment algorithms that can economically align decentralized agents.

Stackelberg Learning with Outcome-based Payment
Tom Yan
Chicheng Zhang University of Arizona chichengz&cs. arizona. edu
Carnegie Mellon University tyyan@cmu.edt
Abstract
With businesses starting to deploy agents to act their behalf, emerging challenge that businesses have to contend with how to incentivize other agents with differing interests to work alongside its own agent. In present day commerce, payment is a common way that different parties use to economically align their interests. In this paper, study how one could analogously learn such payment schemes for aligning agents in the decentralized multi-agent setting. We model this problem Stackelberg Markov game, in which the leader commit policy and also designate set of outcome-basee payments. We are interested answering the question: when do efficient learning algorithms exist? To this end, we characterize the computational and statistical complexity of planning and learning in general-sum and cooperative games. In general-sum games, find that planning is computationally intractable. In cooperative games, we show that learning can be statistically hard without payment and efficient with payment, showing that payment is necessary for learning even with aligned rewards. Altogether, our work aims to consolidate our theoretical understanding of outcome-based payment algorithms that can economically align decentralized agents.
Introduction
Increasingly, we are seeing businesses deploying agents to earry out tasks on their behalf. In the coming agentic era, we will inevitably have multiple, decentralized agents interacting together. An emerging challenge that businesses may have face how to incentivize other agents work alongside its agent. This challenge requires addressing central difficulty in decentralized multi-agent systems, which is that of differing interests.
In present day commerce, payment is a standard way that two parties use to resolve this challenge and more closely align their business interests. This inspires us study the overarching question in this paper: how can we analogously implement such payment schemes in the multi-agent setting and enable economic alignment? That if I am a business looking to use payment incentivize another business (and/or its agent) to work with my agent, how can learn good policy for my agent along with payment scheme to go with it?
On a technical level, this setting may be viewed as Stackelberg Markov game. In this paper, we study the two-player Stackelberg game, where one player (leader) commits to a policy taking into account the best response to the policy by the other player (follower). We focus on Stackelberg Markov games in particular agents will be interacting over multiple turns and potentially long horizons. Finally, to model the payment aspect, the leader is able to also increase the reward of the follower in the Markov game, which may be viewed as a form of reward shaping line with the existing formulation in the literature [Ben-Porat et al. 2024 Bollini et al. 2024 Ivanov et al. 2024
Scheid et al. 2024 Wu al. 2024
In this work, we aim to consolidate the theoretical foundations of Stackelberg learning with payment, complexity results have yet be established for two-player Stackelberg Markov games. We focus
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Without Payment
With Payment
Planning, Learning
DAG
Tree
DAG
Cooperative
V, X (Theorem 5. 15.2
(Theorem
6.5
General Sum
(Proposition
V.V (Proposition 4.3
X (Theorem
Table I: Planning & learning settings where computationally and statistically efficient algorithms exist.
on fundamental question: there an efficient algorithm that can provably compute or learn the optimal policy and payment? Indeed, this is an important question to address as businesses in the future would want payment schemes with provable guarantees, so as to ensure that their expenditure is optimal.
Contributions: We analyze the planning and learning setting through both the computational and statistical lens. Please see Table | for an overview of our results.
1. We begin by considering planning in general-sum games. Is there efficient algorithm that can return the optimal policy and payment? We prove that such a computationally efficient algorithm cannot exist unless NP-P, and identify the structural property of the MDP that results in this hardness, To complement the negative results, we develop an efficient algorithm, applicable when this property is removed.
2. Next, we turn to Cooperative games, which is broad subclass of Markov games useful for modeling e.g. the interaction between AI service- prrvcceprovvidess and their users. Moreover, planning is computationally efficient in this setting, making it plausible that efficient learning algorithms may be attainable. As the rewards are already aligned, we begin by considering learning in the Stackelberg game without payment. Surprisingly, however, we find that an efficient algorithm cannot exist, this time in the statistical sense. We identify structural properties of the MDP that result in statistical hardness, and develop efficient algorithm for when such properties are removed to complement our negative results.
3. Finally, we study learning in Cooperative games with payment. Can payment be used to alleviate the statistical hardness of learning? We answer this in the affirmative by showing that we can adapt existing no-regret RL algorithms to enable sample-efficient learning. In closing, we also use this setting to contrast the two different payment settings we study. We derive matching upper and lower regret bounds for when the leader has to make payments upfront versus on-the-fly, allowing to quantitatively assess the benefits of being able to make payments on-the-fly.
2 Formulation
2.1 Stackelberg Markov Game
We consider the standard two-player. episodic finite-horizon Markov game M parameterized by (S, A, B, H, P, P,p,r", p.r.rr") with state space S, initial state distribution 8p p. transitions P and episode length H. The leader has action set A and reward rf E [-1,1], the follower action set B and reward f El 1-1,, 1]. In the case that the game is cooperative, r F..
In the problem of online learning for Stackelberg Markov games, the learner plays the role of the leader, where apriori the reward functions -","" and the transitions are unknown to the leader. At each episode k [T'] the leader commits first a policy Tk. The follower best responds T& with ((TT)) argmax,, y (M); F). One may view best response as the equilibrium behavior of the follower to the leader policy.
After the episode, the leader and the follower observe the resultant trajectory To = ((s), Oi by rs,, ai, b:), F (s,,a;,b))) " realized by the chosen policies in M: a; TT(s:), b, (s1)) 81+1 Pr(-|ss, az, b.).
This trajectory the outcome of the policies' interaction, which turn determines the outcome-busee payment the follower receives.

---

Following existing formulations in prior literature, the leader can increase r" by creating outcome-based payment by (s;, az b;). if state-actions S;, ag b, are realized during the episode, 8i, di by E Tk- This results in a modified Markov game where the leader is able to additionally assign payment, with the payment function having signature bytt S x A x - R+.
Leader Payment:
We note that the outcome-based payment need not correspond to direct monetary transfer. For example, we may be interested in modeling the setting where the leader an Al-service-provider and the follower is a customer user. The leader spends money to improve its agent, and this improved agent adds additional value (e.g. more saved time) for the user during its use. But during this interaction, there is no direct transfer of money from the company to the user.
Thus, to model indirect payments in addition to direct ones, we introduce final piece of notation, multiplier k E IR. x by (8t, as, by) corresponds to the proportional cost to the leader in creating payment (reward) by (ss: az, b,) for the follower. We believe proportionality is a natural assumption to make, and verily = 1 corresponds to direct payment.
2.2 Payment Settings
To complete the formulation, we touch on the two types of payment settings considered in this paper.
The first is the existing payment setting commonly studied in prior literature, which we term trajectory payment. Here, a payment is made by the leader for every state-action on the realized trajectory. This form of payment considered in principal-agent contracting literature. where the trajectory informing how much the leader will be paying ex- -x-post [Dutting et al., 2021].
Trajectory Payment:
Moreover, this form of payment corresponds to the trendy outcome-basee pricing model, which is experiencing rapid adoption by several notable SaaS companies due to the rising usage of AI agents [Stripe] 2025 Intercom 2025 Zendesk 2025). Indeed, this marks fundamental paradigm shift in software pricing in industry, moving from seat-based subscriptions (traditional SaaS) and usage-based models (cloud infrastructure) to now outcome-based pricing in the agent era [Boston Consulting Group 2025 Sequoia Capital 2025]. This also makes it imperative then to bolster our theoretical understanding of outcome based pricing, which we study in this paper.
In this paper, we will also consider a setting that we term upfront payment. As the name suggests, the leader pays for every state-action in the MDP, regardless of the realized trajectory. Note that the follower is still paid based on the realized trajectory. This is more realistic in settings where the leader pays indirectly to the benefit of the follower, and is bound by temporal constraints such that the payment cannot be made on- on-the-fit fhe-fly.
Upfront Payment:
For motivating example, consider the Al-service provider setting discussed earlier. The company invests before deployment to improve the agent's functionality, which means that the user (follower) gains added value (reward) temporal constraint is that the company cannot improve its agent on-the-fly, as the users are using it. Thus, this makes upfront payment more realistic model of the leader's 's expenditure. The leader had to invest upfront to improve the agent's 's capabilities in all states, even though this includes off- tffjetrjyttory states that are not visited during the interaction with the user. For instance, suppose the agent is a computer-using usingr-unnn-gegee agget [Anthropic] 2024]. The user may use it to handle emails, and the agent would act in states of the computer corresponding to the inbox. However, even though the company had also invested to improve the agent's 's capabilities in coding, the user may not invoke the agent to do so (perhaps due excessive risk). And so, the agent would not have acted in other states of the computer corresponding to the codebase.
the trajectory realized during the agent's 's use. However, the key
More generally, there is sizable body of economics contracting literature studying settings where only ex-ante (upfront) payment is possible. Some reasons for this include non-enforceed con-ceforeee contracts, where the principal can renege upon observing the outcome Hart and Moore [1988]. Another cause for this may be non-verifialle outcomes; that is, when outcomes cannot be verified, ex-post contracts become unenforceable there is way to condition legally binding payments (Aghion and Holden 201T]. Finally, one other reason may simply be that the agent is risk-averse, thus preferring upfront payment in face of stochastic outcomes Laffont and Martimort [2002]
Leader Optimization: Putting all together, we can now write down the resulting Stackelherg game under the two payment settings.
3

---

Definition 2.1. In Stackelberg Markov games with trajectory payment, the leader optimizes:
VT.a( ki R.b
max a,620
(I)
s.l. p(x) & argmax Va.w (80;r" + bb
In Stackelberg Markov games with upfront payment, the leader optimizes:
(su
Σ
b(s,a,b)
max 8,620
(2)
s,a.bSSAAB
s.t. (TT) E argmax, Va. (50; P + +b
Before moving on, we highlight the generality of the class of games we are studying. The class of Stackelberg Markov games with payment generalizes Stackelberg Markov games, Indeed, con- straining the leader to zero payment (i.e. (I, b) (ι, 0)) corresponds the leader's policy space in Stackelberg Markov Games. Analogously, for Cooperative Stackelberg Markov games with payment studied in the later sections, this class of games generalizes Cooperative Stackelberg Markov games.
Related Works
As focus on Stackelberg Markov games with payment, our paper is most related to two lines of work. The first is the line of work studying the complexity of Stackelberg policy computation in Markov games. And the second is algorithms for computing optimal payment schemes in MDPs. We cover both lines of work below, and include a discussion on additional related works in Appendix
Stackelberg Optimal Policies in Markov Games without Payment: Due to the wide applicability of the Stackelberg Markov games, there has been a long line of work seeking to understand how to compute optimal leader policies with provable guarantees.
For planning, Conitzer and Sandholm (2066] Letchford al. 2012 Letchford and Conitzer 2010 study the computational tractability of optimal Stackelberg policy computation in Markov games and subclasses thereof. For stochastic MDPs, they establish that computing the optimal Stackelberg policy is NP-Hard.
For learning, Zhao al. 2023 studies the statistical complexity in cooperative bandit games. Bai et al. 2021 studies the statistical complexity in bandit-RL. games, a particular subclass of Markov games. Our work differs from this line of work in focusing Markov games, which more general than bandit-RL. games and have longer horizon than bandit settings. Moreover, the leader allowed use payments to shape the follower's rewards. As will see, this turns out be crucial for improved exploration during learning in certain settings.
Learning the Optimal Payment Scheme in MDPs: Recently, there has been burgeoning interest in computing optimal payment schemes for contracting agents to act MDP environments, wherein the leader may increase the follower's rewards form of reward shaping to incentivize the follower to play policies desirable to the leader.
The single-agent MDP setting, where only the follower acts in the MDP and the leader incentivizes, formulated by Sen-Porat al. [2024) Chen et al. [2022] This is followed by series of interesting work by Bollini et al. 2024 Ivaov et al. 2024 Wu et al. 2024 studying learning under variety of different payment functions taking as input the state, the state-action or the state-next-state. Our work adds this line of work by focusing
two-player Markov games, which generalize the single-player setting. Furthermore, while previous works mostly focus on trajectory payment, we also consider upfront payment, applicable in settings where the leader cannot pay on the fly due to temporal constraints. We derive tight regret guarantees to contrast the two differing payment settings.
The paper closest in formulation to that of ours is that by Scheid et al. 2024 who considers the same state-action based payment function the bandit setting. Our work differs in focusing on Markov games, with a longer horizon than that in bandit settings. This in turn introduces difficulty in terms of exploration, and requires more nuanced optimal payment computation beyond the binary search approach used in Scheid et al. 2024

---

Finally, as payment may be viewed as strategic reward shaping, our analysis is also related to existing RL literature that seeks theoretically quantify the benefits of reward shaping [Ng et al. [999]. Gupta et al. [2222 quantifies how statistical sample complexity is improved by reward shaping in the single-agent setting. By contrast, in our work, we study improved sample complexity two-player cooperative Stackelberg Markov games.
4 Planning in General-sum Games
In this section, we ask: is there an efficient algorithm that can compute the optimal policy and payment in general-sum games? We investigate the computational complexity of such an algorithm, starting with the planning setting, where the Markov game dynamics and reward functions are known.
Our main finding is that there is no such computationally efficient algorithm unless NP=P. Outcome- based payment does not alleviate the computational intractability of computing the optimal Stackel- berg policy, even in planning [Conitzer and Sandholm, 2006]. We identify that when the MDP has DAG structure, this leads computational intractability. Later in the section, we complement this negative result with positive result for when the MDP has tree structure. All proofs in this section may be found in Appendix A
4.1 Hardness Results
We first derive a result showing that NP-Hard to compute the optimal leader policy even in deterministic MDPs, without payment. Note that in [Conitzer and Sandholm 2006 computational intractability is demonstrated in stochastic MDPs.
Proposition 4.1. Under Markov games that are deterministic DAGs, it NP-Hard compute the optimal policy:
VaLu(m) (80;r")
(TT) E argmax, Va. (sa:rF)
s.f.
Helpfully, deterministic MDPs allow provide guarantees for both two payment settings. As we show in the proof, the optimal payment scheme pays zero in off-policy states, which can be readily characterized in deterministic MDPs. This result is intuitive paying in off-policy states only incentivizes the follower to deviate off-policy, which is undesirable and increases leader total payment. With this result, can derive that the optimal payment scheme is the same under trajectory and upfront payment. Thus, we use same construction, which provides reduction to the PARTITION problem, to prove computational intractability under both payment settings.
Theorem 4.2. Under Markov games that are deterministic DAGs, it is NP-Hard to compute the optimal policy and optimal trajectory payment:
(Tal")(s;;7"- k.b))
n,520
p(x) E argmax,, van (so;r + bb)
s.f.
and it is also NP-Hard to compute the optimal policy and optimal upfront paymens:
max T.620
Va..(s) (s0; r2) K
Σ
b(s, a. b)
s.a.bESxAXB
s.f. ((x) E argmax V (503r" +
In closing, we note that the optimal objective value of the subset of Markov games used reduce to the PARTITION problem is an integral multiple of 1/2. Due to this, we have that computational intractability planning implies computational intractability
learning. In more detail, let M be the optimal objective value, which is an integer multiple of 1/2. Suppose by contradiction that we had an algorithm with sublinear regret 7 (a < 1). We can then set T' large enough such that TO /T < 1/2. This allows us to infer M exactly by rounding to the nearest 1/2, giving us computationally efficient algorithm for answering the decision version of the PARTITION problem, which is contradiction.
5

---

Algorithm Planning Algorithm for MDP with Deterministic Tree Structure
Require:
Pre-computed policy x E argmin V* (so; (so:r r (efficiently computed via Nash-V VI) for all root to leaf paths 7 = 81, 41. bi, 82, 02, b2, .2,,... 8H, 0,t, bys do
Define rss;) = a, for 8; 02 E T. In every other state si E T, let π (s)) = x (s(). Compute p(x) and compute follower Q-values, QT.A(T)) (,'')).
Solve for the minimal payment scheme using LP:
67 (T) = argming
Σ
b(sis ass b;)
BEET
Σ
(s, b/)+ + b(8,, b4) 2 max Qu-a(()) (8h 4/ b/(5²))
s.t.
7bn
end for
Output the leader policy x and payment scheme of the path with maximal return Enary r (Bi, ai, b,) - K (*)).
4.2 Positive Results
To complement negative results, we show that positive results attainable in MDPs without DAG structure. That is, in general-sum games where the MDP has tree structure, there is a polynomial-tmee algorithm for learning the optimal leader policy and payment. We describe our planning algorithm, Algorithm that forms the crux of our approach to learning in this setting, and is applicable under both trajectory and upfront payment.
Proposition 4.3. Under Markov games that are deterministic trees, there exists polynomial time planning algorithm that computes the optimal policy and payment.
Remark 4.4. To complete the result, we note in Appendix A that there is simple exploration strategy using payment for general-sume sum, deterministic trees, as exploration needs to only recover rewards. This strategy allows us to reduce learning to planning, and then apply Algorithm 7
Before moving on, we note that in this general-sum game, the leader behaves in zero-sum like manner in off- off-policy states in Algorithm D This incentivizes the follower take the desired policy and allows the leader to minimize the total payment needed to incentivize such policy.
Finally, due the intractability of computing a global Stackelberg optimum, it is natural consider computing a local Stackelberg optimum instead, so that the policy and payment scheme does attain some guarantees. Building on existing results on first order methods in Stackelberg games (Shen et al. 2024). we derive first order approach to this end. Note that while our paper is concerned with global Stackelberg optimality guarantees, use this to illustrate that more relaxed solution concept can be computed, if desired.
Learning in Cooperative Games without Payment
The computational intractability in the general-sum case prompts us to investigate whether efficient algorithms are attainable in significant subclasses of Markov games. Cooperative games are broad subclass of Markov games useful for modeling e.g. the aforementioned AI-service based setting. Indeed, since the goal of the assistant agent is aid the user, their rewards are aligned. And so, such settings correspond to a two-player cooperative game, making it an important subclass of Markov games to understand.
Moreover, on a technical level, seems that there is hope for efficient algorithms as planning is efficient in cooperative games (e.g. via Nash-VI as in Bai and Jin (2020). And so, in this section, cooperative games? We delve
we study the question: is there an efficient learning algorithm into this by first considering cooperative games without payment, which has yet to be addressed in the prior literature. Since the rewards are already aligned, we might expect that there are efficient learning algorithms. To our surprise, however, find that learning in Cooperative Markov games

---

best response can be prohibitively hard, this time in the statistical sense. All proof' in this section may be found in Appendix
Structural properties of MDP: We identify the specific MDP properties under which exploration can be statistically intractable, along with complementary positive results. In a nutshell, we find that if the MDP has deterministic tree structure, then efficient algorithms are possible. However, allowing for stochastic or DAG transitions leads statistical hardness.
Theorem 5.1. There exists turn-based Stochastic Tree Markov game such that: any (possibly randomized) algorithm that returns the optimal leader policy with probability at least 1/2 requires at least (2) number of episodes.
Theorem 5.2. There exists a turn ourn-based Deterministic DAG Markov game such that: any (possibly randomized) algorithm that returns the optimal leader policy with probability least 1/2 requires at least (2(2) number of episodes.
Proposition 5.3. Under Markov games that are deterministic trees, then there exists polynomial- time algorithm that can learn a near-optimal leader policy.
We remark that the statistical intractability results are based on a "needle-in the -tahll--i--th--hytakkkk""" construc- tion, where only specific combination of leader actions is optimal. Structural properties of the MDP like stochastic or DAG transitions allow us to embed this construction in the MDP. Combined with the follower best responding instead of coordinating exploration with the leader, we can show that an exponential number of samples is needed by the leader to find the right combination, even if the rewards are already aligned.
Relaxing Follower Best Response behavior: As the statistical hardness is due to both the structural property of the MDP and the best response nature of the follower, natural question one may ask is: can relaxing the latter alleviate statistical hardness and allow for efficient learning across all MDPs?
The natural way to relax best response is to consider best response under ceentrop-reeullrizeee which generalizes follower best response (corresponding when X oc). This behavior model is often used to model human behavior in human-Al interaction and behavioral economics litera- ture (Ziebart et al. 2010 Reddy al. 2018 McKelvey and Palfrey 1995]. However, we again find that learning with this follower behavior does not allow for more sample efficient exploration:
Theorem 5.4. There exists a turn-based Deterministic DAG Markov game such that: any (possibly randomized) algorithm that outputs the optimal policy given with probability at least 1/2 requires at least (2eex((>HH]) episodes if X S. 1 and (exp((H/8) episodes if X 1.
In closing, we offer conceptual interpretation of the technical results in this section, using the example of the assistant agent and the user. Our results suggest that the service provider company can have difficulty exploring, due to the user's best response. Indeed, users are simply looking to use the agent wherever it is at its best, and will not use the agent for the sake of its improvement. In particular, this means that users are not willing to use the agent in states that it currently does not currently excel in. Even though, these are precisely the states that the agent needs to obtain more training samples in. And so, this suggests that if the company wants to efficiently explore to learn an even better agent, incentivized exploration is needed.
Learning in Cooperative Games with Payment
In sum, we know from the previous section that Stackelberg games, coordinated exploration is necessary for efficient learning. And so, in this section, we study how payment can be used to align the follower and enable efficient leader exploration. Our overall finding is that payment can lead to efficient exploration, and alleviate the statistical hardness in cooperative games without payment. All proofs in this section may be found in Appendix
6.1 Regret Guarantees in Cooperative Games
We study regret guarantees under the standard reinforcement learning setup with unknown transitions and unknown rewards, which can be stochastic.
7

---

Learning protocol: At each episode k E [T], the leader commits first to a policy л and payment function b The follower best responds to x* with su(*)) E argmax, (s; 8²). After the episode, the leader and the follower observe the resultant trajectory Th {(s, ag b;, (s,, 0,, b,), realized by the chosen policies in M (recall that r² = r The goal of the learner is to minimize its Stackelberg regret, defined follows:
Definition 6.1. In Stackelberg games with trajectory payment, the Stackelberg regret is defined as:
T
R(T) = Σ v au(=" =r" ++*) (so: r b.)b))= - "p=="""="rr + (80; - k. b8
The regret under upfront payment regret may be defined analogously.
Towards analyzing Stackelberg regret, we characterize the optimal policy and trajectory payment when ndh rr; we can analogously show the same result under upfront payment. Lemma 6.2. For any ,² such that:
πt" b" = argmax VELu(aW" 4b) 48) (so;r" - K
s.t. u(T;r" + b) E argmax, V ( + b)
rf = F.F then must have n² :- argmax (so: and b" O.
With this, we have that the optimal payment scheme any cooperative game must be zero, as one would intuitively expect with already aligned rewards. This allows to decompose Stackelberg regret into regret due sub-optimality in policy and regret due to payment used during exploration, which will be responsible for the differing rates between trajectory and upfront payment.
Moreover, we note an interesting contrast due this result. As we just saw, learning can be prohibitively hard in the absence of payment. Hence, we have that payment is not necessary in planning, but is crucial for learning (efficiently).
The crux of our positive results is that we can apply the canonical optimism under uncertainty principle to achieving sublinear Stackelberg regret. This follows from the observation that payment enables optimism in learning, which the leader can operationalize by setting payments according to its bonuses. This incentivizes the follower also explore optimistically. A key lemma for bounding the policy regret portion of Stackelberg regret goes as follows.
Lemma 6.3. Suppose can construct optimistic MDP Mj of the true MDP M. Let the optimal leader policy under Mg be Tg. then:
T
T
Vs (ss((=)) (80; - V M
(ase (80; r
S
v (M M2
(s0i V Mar (3r)
(80;
Note that because the leader knows Mr. they know the policy JMM, (m*) that they would like to incentivize the follower to play. Using this, we show that one can also bound the regret due to the cumulative payment, to obtain the following regret guarantees.
Theorem 6.4. UCB-VI-FP (Algorithm 2 incurs ((T1/2) regret under trajectory payment. This is tight as there exists subset of Markov games, where any learning algorithum must incur 1/2 regret.
Theorem 6.5. There exists an algorithm, leveraging UCB-VI-FP as subroutine, that incurs (
regret under upfront payment.
6.2 Contrasting Trajectory Payment with Upfront Payment
Finally, as positive results are attainable in Cooperative Markov games, we can analyze the difference in regret rates under the two different payment settings. What is the benefit afforded by settings where the leader can pay on-the-fly? Towards answering this question, we analyze the simple setup of unknown, deterministic rewards. Helpfully, this learning task already a sizable contrast in terms of regret between the two settings. We provide tight bounds on regret guarantees under both payment settings to contrast the two payment settings.
8

---

Algorithm 2 UCB-VI with Follower Payment (UCB-VI-FP)
Initialize (8 b) H for all h (,),, Sp. A B.
for 11,.,, for h = H, .... 1;8, a, S₁ x A B do
econstruct Mş
Compute estimated transitions from data in buffer: Pa((''8, a, a, b) = Nyle,a.b.."
(s.00.))
Compute optimistic rewards of M& from reward samples in buffer: a
(s, b) + CV (g....)))
Ha
bsstandad bonus for stochastic rewards
Qn,s, a. b) min(H, + (
(s) = m Qn,
end for
Leader commits to Stackelberg policy Th: x (sh) = argmax, max, (sh, a, b).
Set outcome-based payment scheme: 3 (sh, on, bn.) = 2 cv (x.a,)))
HaS
for = I,... H do Leader plays a 77 (s%), follower plays of via via 1((T)) Transition to hh+1 Pl ot by)) and save data (sh, at bh. oh+1)
1) in buffer
end for end for
Proposition 6.6. UCB-VI-FP with indicator bonus incurs constant O(SSTAA|BB) regret un- der trajectory payment, where we designate reward under indicator bonus be f(s,a,b) 1(f (s, a, b) is unvisited] and r(s, 0, b) o.w.
As the regret bound is constant in T,, we have that the bound must be tight. Next, we derive regret rates under upfront payment, whose regret lower bound requires a significantly nuanced probabilistic argument using Yao's lemma.
Proposition 6.7. There exists an algorithm, leveraging UCB-VI-FP with indicator bonus as subrou- tine, that incurs ((T)/2) regret under upfront payment. Proposition 6.8. There exists a subset of Markov Game instances such that any learning algorithm has to incur (2( regret under upfront payment.
The construction of the negative result reveals the key difference in two payment schemes. nutshell, upfront payment is affected by difficult-oorracch states (e-significant states (Jin et al. 2020)). On the other hand, trajectory payment is unaffected as the payment is made only if the follower does reach such state. That is, the leader's payment for actions in that statement is weighted by the visitation probability.
And so, the key difficulty in exploration under upfront payment is that when payment is needed to incentivize the follower reach insignificant states, lot of the payment can be wasted even if the follower is aligned, due to the low visitation probability. This is directly responsible for the sizable change in the regret guarantee, going from ((1) to /2T Overall, this suggests that if the leader cannot pay on-the-fly, the payment scheme should factor in the reachability of states.
7 Discussion
In this work, we study learning in Stackelberg Markov games with payment. To consolidate the theoretical foundations of this setting, we chart the computational and statistical complexity of both planning and learning.
Due to the intractability of general-sum settings, believe that there is much more work to done in analyzing more specific subclasses of Markov games. Which other subclasses of Markov games such that efficient algorithms attainable?
Future Work:
One key assumption underlying our paper that the follower's action can observed by the leader. We believe that this can be realistic for modeling certain digital settings (such as computers), wherein the agent's 's actions can be readily tracked cemputee-using-agene actions can
Limitations:
be logged and monitored) [Anthropic 2024 Sumers et al. 2025 With that said, handling the case

---

for when the follower's action is not observable is very important, especially in physical environment where monitoring is not possible. And we believe that results from the setting we study can serve as a stepping stone towards results in partial information settings with unobserved actions.
Another key underlying assumption is that the leader can readily observe the follower's 's reward, either directly or through the follower's 's report. It conceivable that in cases the leader cannot observe the reward directly, the follower may not report their reward truthfully. In such settings, we note two observations. Let (r), (r)) denote an optimal policy under reported follower reward r. Let yf denote the true reward and r' the reported reward.
First, we are in the cooperative setting, we observe that there is no incentive for the follower to misreport. Because the leader payment is zero, truthful reporting yields the highest return: V (rf Dita""""" (r(a""("")) (s") ( 2 "ru(""(r""))) (r"")) (ss; (5);""))
Second, the general-sur sum bandit setting with direct payment considered by [Scheid et al. 2024 the payment now be nonzero but the follower's gain from misreporting is bounded.
Proposition 7.1. Suppose the follower can misreport F up to A, || -r 111 A. In the bandit setting, the follower's 's return can change by at most:
| Duln (r (so:r" br)(r)) y (T (N(
+ br((r")) (sur) 2
and the leader's 's return can change by most:
V (aa (r (s0; - by (r²)) - (r'F 1n(=" (v' Msu 1000;--~-'000 -b"(r"")) s 24
However, an open question is whether such a bound carries over to the Markov game case. How much could the follower gain from misreporting r" up to A? Are there algorithms that can induce truthfulness, while still attaining some optimality guarantees? We believe there is a fruitful line of work to be done to handle cases where the leader cannot directly observe and/or verify the follower rewards.
8 Acknowledgement
TY grateful for the support of the NSF GRFP. CZ is supported by NSF Award IIS-2440266.
References
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, pages 9502-9510, 2024.
Matteo Bollini, Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Contracting with reinforcement learning agent by playing trick or treat. arXiv preprint arXiv:2410.135200 2024.
Dima Ivanov, Paul Dütting, Inbal Talgam-Cohen CChhe, Tonghan Wang, and David C Parkes. Principal-agent reinforcement learning: Orchestrating ai agents with contracts. arXiv preprint arXiv:2407. 18074, 2024.
Antoine Scheid, Daniil Tiapkin, Etienne Boursier, Aymeric Capitaine, El Mahdi El Mhamdi, Éric Moulines, Michael I Jordan, and Alain Durmus. Incentivized learning in principal-agent bandit games. arXiv preprint arXiv:2403.0388
2024.
Jibang Wu, Siyu Chen, Mengdi Wang. Huazheng Wang, and Haifeng Xu. Contractual reinforcement learning: Pulling arms with invisible hands. arXiv preprint arXiv:2407.01455 2024.
Paul Dutting, Tim Roughgarden, and Inbal Talgam-Coher The complexity of contracts. SIAM Journal on Computing, 50(1):211-254, 2021.
Stripe, Outcome-hased pricing: guide for businesses. Stripe Resources, 2025. URL https
10

---

Intercom. Pricing Al agents: What does value-based pricing really mean for AI?, May 2025. URL https://www intercom. wwt.coomoooooo. www.b//gg/rrciing//cgooooo ageattsss/
Zendesk. Zendesk first in CX industry to offer outcome-based pricing for Al agents.
Zendesk Newsroom, 2025. URL
zendesk- -ocesk--utoomeeeee based- pricing/
Boston Consulting Group. Rethinking B2B software pricing in the agentic Al era.
BCG Publications, 2025.
URL https://wwx. http://www.bbgg.co///bbiiiiiieee rethinking-b286 b2b- pricing taa-the-se eoo--rra-f-aa cttp//ppbblcccatioo////////////
Sequoia Capital. Pricing in the AI era: From inputs to outcomes, with Paid CEO Manny
Medina. Sequoia Capital Podcast, 2025. URL http:://sequoiiaaa.cccoo cowp://iaa..accoooo/cccsss.t//
pricing- Berhanginn-haae in-the-ai-err--rrom htt.:ppt........cccocoooooaaaaaa
Anthropic. Developing computer model, 2024. URL https:/www.nntiropi.ccc
developing- compute-- uuse
Oliver Hart and John Moore. Incomplete contracts and renegotiation. Econometrica: Journal of the Econometric Sociery, pages 755-785, 1988.
Philippe Aghion and Richard Holden. Incomplete contracts and the theory of the firm: What have we learned over the past 25 years? Journal of Economic Perspectives, 25(2):181-197, 2011.
Jean-Jacques Laffont and David Martimort. The theory of incentives: the principal-agent model. Princeton university press. 2002.
Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceed- ings of the 7th ACM conference on Electronic commerce, pages 82-90, 2006.
Joshua Letchford, Liam MacDermed, Vincent Conitzer, Ronald Parr, and Charles Isbell. Computing optimal strategies to commit to in stochastic games. In Proceedings of the AAAI Conference Artificial Intelligence, volume 26, pages 1380-13860 2012.
Joshua Letchford and Vincent Conitzer. Computing optimal strategies to commit to in extensive-form games. In Proceedings of the I 1tth ACM conference on Electronic commerce, pages 83 92, 2010.
Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. Online learning in stackelberg games with omniscient follower. In International Conference on Machine Learning, pages 42304- 42316. PMLR, 2023.
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances Neural Information Processing Systems. 34:25799-25811 2021.
Siyu Chen, Donglin Yang, Jiayang Li, Senmiao Wang, Zhuoran Yang, and Zhaoran Wang. Adaptive model design for markov decision process. In International Conference on Machine Learning, pages 3679-3700 PMLR, 2022.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Icml, volume 99, pages 278-287. Citeseer, 1999.
Abhishek Gupta, Aldo Pacchiano, Yuexiang Zhai, Sham Kakade, and Sergey Levine. Unpacking reward shaping: Understanding the benefits of reward engineering on sample complexity. Advances in Neural Information Processing Systems, 35: 15:1121--1529.. 2022.
Han Shen, Zhuoran Yang, and Tianyi Chen. Principled penalty- based methods for bilevel reinforce- ment learning and rlhf. arXiv preprint arXiv:2402.066986, 2024.
Yu Bai and Chi Jin, Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR, 2020.
Brian D Ziebart, J Andrew Bagnell, and Anind K Dey. Modeling interaction via the principle of maximum causal entropy. 2010.

---

Sid Reddy, Anca Dragan, and Sergey Levine. Where do you think you're re going?: Inferring beliefs about dynamies from behavior. Advances in Neural Information Processing Systems, 31, 2018.
Richard D McKelvey and Thomas Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-33) 1995.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870 4879. PMLR, 2020.
Theodore Sumers, Raj Agarwal, Nathan Bailey, Tim Belonax, Brian Clarke, Jasmine Deng, Evan Frondorf, Kyla Guru, Keegan Hankes, Jacob Klein, Lynx Lean, Kevin Lin, Linda Petrini, Madeleine Tucker, Ethan Perez, Mrinank Sharma, and Nikhil Saxena. Monitoring computer via hierarchical summarization, 2025.
http://lliaaaaaaaaaaaaaarro...oa anthropic..com /025/
summar commarriaat ization wor-oooo-oooo----eee for-moniooriig
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. International conference on machine learning, pages 263-272. PMLR,
2017.
Han Zhong, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Can reinforcement learning find stackelberg-nan -ash equilibria in general-sum markov games with myopically rational followers? Journal of Machine Learning Research, 24(35):1-52, 2023.
Siyu Chen, Mengdi Wang, and Zhuoran Yang. Actions speak what you want: Provably sample- efficient reinforcement learning of the quantal stackelberg equilibrium from strategic feedbacks. arXiv preprint arXiv:2307. 14085, 2023.
Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Cohen, Emmanouil- -ansaloui-VVaiiccios Vlatakis- Koutakis-Garagkkunii. Joshua Wang, and S Weinberg. Contracting with learning agent. Ad- vances in Neural Information Processing Systems, 37:77366-77408, 2024.
Hsu Kao, Chen-Yo Yu Wei, and Vijay Subramanian. Decentralized cooperative reinforcement learning with hierarchical information structure. In International Conference on Algorithmic Learning Theory, pages 573-605, PMLR, 2022.
Maria-Florie Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the sixteenth ACM conference on economics and computation, pages 61-78, 2015.
Matthias Gerstgrasser and David C Parkes. Oracles & followers: Stackelberg equilibria in deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 11213-11236. PMLR, 2023.
Stephan Dempe and Alain Zemkoho. On the -uck reformulation of the bilevel optimization problem. Nonlinear Analysis: Theory, Methods & Applications, 75(3):1202-13 1218, 2012.
Roi Naveiro and David Ríos Insua. Gradient methods for solving stackelberg games. In International conference on algorithmic decision theory, pages 126-140. Springer, 2019.
Vinzenz Thoma, Barna Pásztor, Andreas Krause, Giorgia Ramponi, and Yifan Hu. Contextual bilevel reinforcement learning for incentive alignment. Advances in Neural Information Processing Systems, 37:127369 2024.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
12

---

The abstract and introduction state the claims made, including the contributions made in the paper and important assumptions and limitations.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss this in the Discussions section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We have written down all the proofs for the results in the paper, which are in the appendix due to the page limit of the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
13

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This is a theoretical paper that does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may tricky some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
14

---

Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
y htipss.ccpublic///e http:///pw/pc....iioooooooooaaaa
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
15

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform in every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical papers focused foundational research. We do not anticipate this paper will have any immediate societal impact, especially negative ones.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt of technologies that could make decisions that unfairly impact specific groups). privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
16

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, snperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
17

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMSs as any important, original, or non-standard components.
Guidelines:
18

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non non-standard components.
Please refer to our LLM policy (attps://neuripp /ttp://p.....coooeeeeeee///////s for what should or should not be described.
19


Reviews:
[{"review_id": "Tw7jBspivb", "reviewer": "Reviewer_tKfe", "summary": "This paper studies how to design incentives in long-horizon settings where a principal agent (the “leader”) interacts with another agent (the “follower”) with potentially misaligned interests. The interaction is modeled as a Markov game, and the leader can influence the follower’s behavior by committing to a policy and a payment scheme—either based on realized trajectories or upfront across all state-action pairs. The authors analyze both the planning and learning problems in this setting. They show that finding optimal policies can be computationally or statistically hard in general—particularly in deterministic DAG MDPs for computational hardness, and under probabilistic transitions (even in trees) for statistical hardness—but becomes tractable in certain structured cases, like deterministic tree-structured environments. In the cooperative setting, they propose a UCB-based learning algorithm that leverages payment schemes to achieve sublinear Stackelberg regret. A key insight is that while payments are unnecessary for planning in fully aligned environments, they can be critical for efficient exploration during learning. The paper also draws a contrast between trajectory and upfront payments, showing that the ability to pay adaptively—only for visited states—can substantially improve regret guarantees.", "questions": "1. Several of the results (e.g., the hardness in DAGs, the benefit of optimism-based exploration in cooperative settings) felt natural or familiar. Could the authors clarify the extent to which these results are new, and how they relate to prior work in Stackelberg planning, incentive design in MDPs? A more explicit positioning against existing approaches—especially for the learning results—would help assess the originality of the work. \n\n2. In the deterministic tree planning algorithm, a subroutine named “Nash VI” is used to compute a worst-case policy for the follower. However, it was unclear whether this refers to a known algorithm, a construct introduced earlier, or a definition given only in the appendix (I couldn't find other references to it in the appendix). Could the authors clarify its meaning and role in the main text? \n\n3. In the cooperative learning setting with payments, the paper argues that Stackelberg regret can be decomposed into policy regret and payment regret. While the high-level intuition is discussed, I found the mechanics of this decomposition somewhat opaque. A more detailed explanation (perhaps with a figure or simple example) could make the logic clearer. \n\n4. The comparison between upfront and trajectory payments was concrete and insightful. However, I was left wondering about the practical scope: in what types of real-world systems is upfront payment a genuine constraint? Are there more examples from digital platforms, robotics, or AI agent systems where the upfront model is necessary or preferred?", "limitations": "The authors have made a good effort to acknowledge the limitations of their work, particularly in highlighting assumptions about full observability of follower actions and rewards, as well as the open question of handling misreporting. These are important caveats, especially for applying the framework in real-world or strategic settings. One area that could benefit from further discussion is the practical scope of the payment models—in particular, how common or feasible trajectory vs. upfront payment schemes are in deployed multi-agent systems. \n\nAnother limitation not directly addressed is the scalability of the approach in environments with large or continuous state/action spaces. The framework assumes access to full policy and payment representations, but real-world systems may require function approximation or compact representations to be tractable. Discussing whether the planning and learning results extend to such approximate or parameterized settings would strengthen the paper’s practical relevance.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper tackles an increasingly relevant question in multi-agent systems: how a principal can design payment schemes to influence another agent’s behavior over long time horizons, particularly in cooperative and partially aligned settings. One strength of the paper is its clear structure and organization—the distinction between planning and learning settings, and between trajectory and upfront payments, provides a useful framework for understanding the design space. The formalism is clean, and the core contributions are communicated clearly, especially in the cooperative learning setting with payments. The use of optimism-based (UCB-style) algorithms to obtain sublinear Stackelberg regret is an interesting application of existing tools in a Stackelberg learning context.\n\nThe main theoretical contributions are well-articulated, though it’s somewhat difficult for me to gauge how novel or surprising they are within the broader literature on learning in Markov games or incentive design. Some results, like the hardness in DAG-structured environments and the benefit of trajectory-based payments during exploration, seemed fairly expected given the setup. The use of optimism-based learning (e.g., UCB) is clean and sensible, but may largely follow existing paradigms. Still, the conceptual clarity around payment structure and its impact on regret is helpful and potentially useful for future work in applied settings.", "was_revised": true, "final_justification": "After considering the rebuttal, the author responses, and the discussion with other reviewers, I have improved my evaluation of the paper. The authors’ clarifications addressed many of my earlier concerns, particularly regarding the technical contributions of the learning results and the novelty of hardness results and the UCB-based approach for achieving sublinear Stackelberg regret. The rebuttal also helped clarify the role of the “Nash VI” subroutine and the decomposition of Stackelberg regret, which were points of confusion in my initial reading.\n\nSome minor issues remain—such as a deeper exploration of the practical applicability of the payment models and how the results extend to large-scale environments (especially in number of agents as others points out in reviews). These remaining issues are minor compared to the paper’s strength (clear writing, justified setting, strong theoretical framework) so combined with the clarifications during the discussion, I have raised my score.", "rebuttal": "Thank you very much for your careful reading of our paper, Reviewer tKfe! We will be sure to include further discussion on the practical scope of the payment schemes and large state/action space settings in Section 7, as you suggest.\n\n```\nSeveral of the results (e.g., the hardness in DAGs, the benefit of optimism-based exploration in cooperative settings) felt natural or familiar. Could the authors clarify the extent to which these results are new, and how they relate to prior work in Stackelberg planning, incentive design in MDPs? A more explicit positioning against existing approaches—especially for the learning results—would help assess the originality of the work.\n```\n\nTo clarify, we believe all of our results are novel. In terms of prior work, there are a few papers that study Stackelberg Markov games with payment (L133-145). All of these papers consider the setting where the leader can only set payments (but not policy), which is a special case of the setting we consider. To our knowledge, our paper is the first to study Stackelberg Markov games with payment, wherein the leader can set both the policy and the payment.\n\n1. For the hardness in DAGs result that you reference, we note that it does not hold in the less general setting; the leader would simply set the optimal payment to be zero. And so, our negative result is novel as it only arises in the more general setup, which we study.  \nMoreover, we note that planning is efficient in cooperative games. And so, at least we found it surprising that learning can be statistically intractable, even when the rewards are *already* aligned (L215-216).\n\n2. For the positive result (UCB-VI-FP) that you reference, we believe this is novel as well and complements the (new) negative result discussed above. Indeed, while multi-agent RL algorithms where agents jointly explore are common, multi-agent algorithms where only one agent can explore are less common and require addressing new challenges. To see this, Theorem 5.1, 5.2 show that even if the leader is using a no-regret learning algorithm, then learning can still be inefficient.  \nAnd so, a new learning algorithm needs to be developed here, using payment to incentivize collective exploration. The challenge in algorithm design is two-fold. First, the payments have to induce joint exploration to lead to sublinear policy regret. Second, and importantly, the payments also need to be strategically set so that the total payment does not grow arbitrarily, but rather tapers off to be sublinear in $T$. Controlling total payment growth along with policy regret is the new challenge we have to handle in this setting.\n\n3. Furthermore, we add that we also obtain results under upfront payment, which is a new form of payment that has not been considered in prior literature.\n\nOverall, we are confident that all of our results are novel. Certainly, Stackelberg games is a very well studied topic. So please let us know if there are any other results we could comment on to help assess the originality of our work, thanks!\n\nLastly, we wish to point out that a main strength of our paper, in addition to the clear organization that you mention, is the comprehensiveness of our set of positive and negative results. They serve to tightly show where the complexity barriers are in this general setup.\n\n\n```\nIn the deterministic tree planning algorithm, a subroutine named “Nash VI” is used to compute a worst-case policy for the follower. However, it was unclear whether this refers to a known algorithm, a construct introduced earlier, or a definition given only in the appendix (I couldn't find other references to it in the appendix). Could the authors clarify its meaning and role in the main text?\n```\n\nIn RL theory, Nash Value Iteration (Nash VI) is a known planning algorithm (mentioned e.g. in Bai et al) that computes the minimax optimal policy in zero-sum Markov games. We will be sure to include a reference to it in the revision. Thanks for this note!\n\n```\nIn the cooperative learning setting with payments, the paper argues that Stackelberg regret can be decomposed into policy regret and payment regret. While the high-level intuition is discussed, I found the mechanics of this decomposition somewhat opaque. A more detailed explanation (perhaps with a figure or simple example) could make the logic clearer.\n```\n\nThis follows from that the value function is additive in terms of rewards:\n$V^{\\pi, \\mu}(s_0; r - \\kappa \\cdot b) = V^{\\pi, \\mu}(s_0; r) - V^{\\pi, \\mu}(s_0;  \\kappa \\cdot b)$, where the first term is the return and the second is the payment incurred. Please let us know if this has addressed your question, thanks! Overall, we agree with you that proof sketches would benefit the presentation. Please understand our paper was fairly constrained in terms of space in order to fit all the results in.\n\n\n```\nThe comparison between upfront and trajectory payments was concrete and insightful. However, I was left wondering about the practical scope: in what types of real-world systems is upfront payment a genuine constraint? Are there more examples from digital platforms, robotics, or AI agent systems where the upfront model is necessary or preferred?\n```\n\nWe believe that there are genuine constraints in the real world such that upfront payment is preferred and/or necessary.\n\nAnother example is insurance, which is another form of upfront payment. For example, a company that has leased a robot may wish to purchase insurance upfront for the robot. Paying for the insurance means paying some fee upfront to be insured against bad scenarios (states) that the robot could land in during use. And verily these scenarios may not all be realized ex-post.\n\nMore generally, thanks to your question, we ended up finding a sizable body of economics contracting literature where the principal can only pay the agent ex-ante (i.e. upfront payment). Some reasons for this are:\n\n1. Non-enforceable/costly contract situations: when the principal can renege upon observing the outcome.\n2. Non-verifiable outcomes situations: when outcomes cannot be verified by third parties, ex-post contracts become unenforceable (Aghion and Holden). So even if both parties can observe the outcome, without verifiability, there's no way to condition legally binding payments on results. This makes ex-ante payments necessary.\n3. Risk-aversion on the part of the agent: when the agent is risk-averse, upfront payment may be preferred when the outcome is stochastic.\n\nWhile we are not sure what future business settings are like with digital agents, based on this line of economics literature, it does seem like there are a number of reasonable assumptions under which upfront payment is preferable. Thus, it seems important to also study upfront payment as a viable form of payment. Thanks again for your question, and we will be sure to include these points when motivating the consideration of the upfront payment!\n\n```\nAt the end of Section 4 it would be helpful to reference where in the appendix local Stackelberg optima are treated\n```\n\nThanks for this! Yes, we will be sure to include a pointer to section A.2.2 of the Appendix in the revision."}, {"review_id": "f3DskbzQEa", "reviewer": "Reviewer_fS36", "summary": "Setting:\n\n- This paper considers the computational and statistical complexity of leader-follower (Stackelberg) games. In these games, there are two players and a series of stages called epochs. In each epoch, the leader commits to a strategy and then the follower, observing the leader’s policy, commits to its own strategy. Over the course of a epoch, the current state, leader’s action and follower’s action mutually determine the next state. Each leader and follower receives a (possibly differing) reward based on the trajectory of state-action combinations that was realized. The follower is assumed to best-respond to the leader so that it maximizes its reward under the leader’s policy.\n- The paper considers planning problems, where the leader tries to determine the policy/payment that achieves the highest reward, and learning problems, where the goal is the same but the leader does not know the transition or reward functions.\n- Many variants of the problem are considered, including:\n    - Whether or not to allow the leader to transfer payments to the follower.\n    - If payment is allowed, whether the leader must pay “upfront” for all state/action combinations it would like to incentivise or whether the leader just has to pay the follower for the state/action combinations that were realized over the course of the dynamics.\n    - Whether the game is general sum, where the leader and follower may have different reward functions, or cooperative, where the leader and follower have the same reward function.\n    - Whether the state space is described by a directed acyclic graph (DAG) or a tree.\n    - Whether the transition function (which maps the current state and the player’s actions to the next state) is deterministic or stochastic.\n\nMain results:\n\n- Prop 4.1 and Thm 4.2: In general sum games, if the state space is a DAG and transitions are deterministic, with and without payment, it is NP-hard to compute the optimal leader policy (and payment, where applicable).\n- Prop 4.3: In the same settings as above, if the state space is instead a tree, planning and learning are computationally/statistically efficient.\n- Thm 5.1, 5.2 and Prop 5.3: In cooperative games without payment, if the state space is a tree and transitions are deterministic, planning and learning are efficient. If either condition (tree or deterministic) are relaxed, no statistically efficient learning algorithm exists.\n- Thm 6.4 and 6.5: Sublinear regret guarantees for trajectory and upfront payment in cooperative games with payment.", "questions": "In Section 6.2, unless I missed it, you did not define indicator bonus? What is this?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The problem of learning/planning in leader/follower contexts is well-motivated, particularly in contexts with LLM agents etc.\n- The theoretical results seem complete to me, with satisfactory answers about the computational and statistical complexity for each of the variants of the game.\n- I really appreciate the intuition provided for the results. The discussion around the results is very informative. In particular, around Theorem 5.4, it is interesting that the role of payment is to incentivise the follower to explore actions they would not otherwise take, thereby letting the leader determine the value of such less-desirable states.\n\nWeaknesses:\n\n- There should be a definition of planning versus learning problems in the preliminaries.", "was_revised": true, "final_justification": "This is a clearly written, technically strong paper. My limited concerns were addressed during the rebuttal period, and I did not see any concerns raised by other reviewers that would have led me to revise my scores downward.", "rebuttal": "Thank you very much for your thorough review of our paper, Reviewer fS36! We will be sure to include a definition of planning versus learning in the preliminaries section, as you suggest.\n\n```\nIn Section 6.2, unless I missed it, you did not define indicator bonus? What is this?\n```\n\nThanks for this note, we will make this clear in the revision! We mean that the optimistic reward is set to be $\\hat{r}(s,a,b) = 1(\\text{if $(s,a,b)$ is unvisited})$ and $r(s,a,b)$ otherwise (L1106 in the Appendix)."}, {"review_id": "abq666dBaG", "reviewer": "Reviewer_twSH", "summary": "This paper analyses the computational hardness of Stackelberg games, with a especial emphasis on the setup where the leader is able to influence the policy of the follower by modifying its rewards (a.k.a. \"payment\") at the trajectory level (adding a reward for each state-action pair on the realized trajectory) or upfront (before the trajectory is realized). The authors study three main settings of Stackelberg games and provide the following computational hardness results on each of them: \n\n1. General-sum Stackelberg games: An efficient algorithm that returns both optimal policy and payment cannot exist unless $\\text{P}=\\text{NP}$.\n2. Cooperative Stackelberg games: An efficient algorithm that returns both optimal policy and payment cannot exist due to statistical hardness tied to structural properties of the MDP.\n3. Cooperative Stackelberg games with payment: The authors introduce an efficient algorithm, UCB-VI with Follower Payment (UCB-VI-FP), for which they prove upper and lower regret bounds for the trajectory level and upfront payment setups.", "questions": "1. Is there a simulator or game that could be used to demonstrate the effectiveness of UCB-VI-FP empirically? Is this a direction that the authors have considered or is the algorithm mostly a theoretical construct for the hardness proofs?\n\n2. How do you anticipate the results to change when considering $n$ agents instead of two? The *curse of multi-agents* is well known in related literature and I wonder if there is a hope that an extension to UCB-VI-FP could also be efficient in the $n$-player setting.\n\n3. Are there any other real-world examples of two player cooperative Stackelberg games with payment (besides the AI assistants example discussed in the paper) that could benefit from the efficiency results?", "limitations": "The Discussion section contains a candid “Limitations” paragraph that flags the full-information assumption, namely, that the leader can observe both the follower’s actions and rewards. It also notes that this may fail in physical settings or where rewards are privately reported.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I want to preface by stating that I am not an expert on reinforcement learning theory, therefore I am unable to validate the correctness of the proofs presented on this paper. Everything on this review assumes that the theoretical results are correct and well justified.\n\n## Strengths\n\n**Clarity:** The paper is well written. In particular, the theoretical results are explained and discussed in detail, to the extend that a non-expert like myself can understand them and their implications. The mathematical notation is consistent and unambiguous, as each artifact is defined and sometimes explained.\n\n**Novelty:** The study of the computational hardness of Stackelberg games in the three settings discussed on the paper is completely novel. The authors also introduce a new algorithm based on UCB-VI-FP to prove that cooperative Stackelberg games with payment can be solved efficiently and compute its corresponding regret bounds in two different settings. \n\n**Impact:** Stackelberg games are a model that can be used in all sorts of interaction, therefore the results about the computational hardness of these games are of great interest to both experimentalists and theoreticians in areas like game theory, multi-agent reinforcement learning, economics, among others.\n\n## Weaknesses:\n\n**Lack of experimental results:** The paper’s contributions are entirely theoretical, leaving readers without empirical evidence that the proposed payment schemes can be implemented stably or efficiently in practice. Even a small-scale simulation or toy example would support the validity of the theoretical results and overall strengthen the paper.\n\n**Applicability to real world problems:** In this particular case I am not referring to Stackelberg games in general, but the particular subset of Stackelberg games for which the authors prove that an efficient algorithm exist. Namely, two player cooperative games with payment seem to be very limited in scope and not directly tied to real world applications.", "was_revised": true, "final_justification": "My recommended score remains the same, I believe in the practical utility of this paper and the discussion helped me improve my confidence.", "rebuttal": "Thank you very much for your detailed review of our paper, Reviewer twSH! We appreciate your useful feedback that has helped to improve our paper.\n\n```\nLack of experimental results: The paper’s contributions are entirely theoretical, leaving readers without empirical evidence that the proposed payment schemes can be implemented stably or efficiently in practice. Even a small-scale simulation or toy example would support the validity of the theoretical results and overall strengthen the paper.\n```\n\nThanks for this note! Indeed, our contributions in this paper are mainly theoretical. Theory is important in this setting as algorithms are used to compute payment. Thus, provable guarantees are important to ensure that the payment computed are sensible/optimal (L39-40).\n\nWith this said, we have performed experiments, following your feedback that experiments would further improve the paper. Please find below a description of the experiment we ran.\n\n\n**Setup:** We consider a turn-based Markov Game, where the leader is solving a RL problem and the follower solves a bandit problem in its BR (Bai et al). This class of Markov Games includes the hard instance construction in Section 5. Our goal is to examine whether learning without payment can get stuck in more \"average (and not worst) case\" Markov Games.\n\n\nThe leader is doing RL in a toy MDP with $H = 5$. For the follower, arm $a_1$ leads to a MDP, whose optimal return is the optimal return in the (turn-based) Markov game. Arm $a_2$ has a deterministic high reward that is $\\alpha$ that of the optimal return.\n\n\nBy varying $\\alpha$, we can make the follower get \"stuck\" in myopically choosing $a_2$, thus preventing the leader from exploring and learning the actual optimal policy. This is the intuition behind the negative results, Theorem 5.1 and 5.2, where we set $\\alpha$ very high.\n\n\nFor the baseline, we use the single-agent learning algorithm UCB-VI in the without payment case, and compare it against UCB-VI-FP in the with payment case. We track the cumulative regret of the two learning algorithms over $40000$ episodes and across $20$ runs.\n\n\n**Finding:** We experiment with different $\\alpha$’s, finding that learning without payment can get stuck in the myopic optimum even when $\\alpha$ is as low as $0.5$. Interestingly, this suggests that there are “non-worst-case” Markov games, where exploration can be difficult without payment.\n\n\nUnder $\\alpha = 0.5$, our plots show that:\n\n1. In absence of payment, even if the leader is using a (one-sided) no-regret algorithm (UCB-VI), the leader may not be able to explore adequately and incur linear regret.\n2. UCB-VI-FP attains sublinear regret, showing the importance of payment in incentivizing  exploration needed to learn the optimal policy.\n3. UCB-VI-FP initially incurs a higher regret, which we expect due to the additional payment used by the algorithm to incentivize exploration. Over time, its regret improves due to exploration shrinking the policy regret, and reduced incentivization and thus payment regret. UCB-VI-FP’s regret eventually dips below that of UCB-VI, with a crossover point at around episode 13500.\n4. UCB-VI-FP’s regret converges like $O(\\sqrt{K})$, which matches our upper bound. We verify this upper bound for every episode $i$ for $i \\in [40000]$.\n\nHere is a table summarizing average regret (cumulative regret / $T$) across episodes, averaged over the runs.\n\n| Episode $T$  | $5000$ | $10000$ | $15000$  | $20000$ | $25000$ | $30000$ | $35000$ | $40000$ |\n|--------------|--------|---------|----------|---------|---------|---------|---------|---------|\n| UCB-VI Average Regret  | 0.42   | 0.42    | 0.42     | 0.42    | 0.42    | 0.42    | 0.42    | 0.42    |\n| UCB-VI-FP Average Regret  | 0.70 | 0.49    | 0.40     | 0.35    | 0.31    | 0.28    | 0.26    | 0.24    |\n\n\n```\nApplicability to real world problems: In this particular case I am not referring to Stackelberg games in general, but the particular subset of Stackelberg games for which the authors prove that an efficient algorithm exist. Namely, two player cooperative games with payment seem to be very limited in scope and not directly tied to real world applications…Are there any other real-world examples of two player cooperative Stackelberg games with payment (besides the AI assistants example discussed in the paper) that could benefit from the efficiency results?\n```\n\nFirstly, to clarify, Cooperative Stackelberg Markov games with payment are not limited in scope. This class of games generalizes Cooperative Stackelberg Markov games (without payment). Indeed, constraining the leader to zero payment (i.e. $(\\pi, b) = (\\pi, 0)$) corresponds to the leader’s policy space in Cooperative Stackelberg Markov Games (without payment).\n\nAs we write in L77-78, payment is simply an *additional* action that the leader can take to enhance cooperation. And more generally, Stackelberg Markov game with payment generalizes Stackelberg Markov games, which is a broad class of games as you noted earlier.\n\nSecondly, in terms of applicability to real world problems, two-player Cooperative Markov games is a general class of games that models cooperative real world settings, wherein states are fully observable. These include human-AI collaboration, where human is the leader and AI is some digital and/or physical assistant agent, and AI-AI collaboration, which can include interaction among digital and/or physical agents representing different businesses.\n\nWe believe that our work is most relevant in settings involving contracting and/or interaction between agents (be they human or AI) representing two businesses. In these *decentralized* settings, payment becomes a natural (economic) means to induce cooperation, as joint training is not possible. As we write in our introduction, we believe we will soon see more of such settings arise, with agents becoming more capable and more widely deployed by businesses.\n\n```\nIs there a simulator or game that could be used to demonstrate the effectiveness of UCB-VI-FP empirically? Is this a direction that the authors have considered or is the algorithm mostly a theoretical construct for the hardness proofs?\n```\n\nYes, please see the experiment description we have provided earlier, which detail our setup for empirically demonstrating the effectiveness of UCB-VI-FP. And yes, you’re right that our algorithm also serves as a theoretical upper bound on regret that complements the hardness results.\n\n\n```\nHow do you anticipate the results to change when considering n agents instead of two? The curse of multi-agents is well known in related literature and I wonder if there is a hope that an extension to UCB-VI-FP could also be efficient in the n-player setting.\n```\n\nThanks for this question! One consideration is that with $n$ agents, the action space becomes exponential in $n$. And so, we anticipate that additional assumptions (e.g. factorization assumptions) are needed so that positive results could be attainable."}, {"review_id": "F5aU07oiPT", "reviewer": "Reviewer_jtyD", "summary": "This paper provides an algorithm for two-stage resource allocation problem modelling two-player leader-follower task assignment within the context of a Stacklberg game. The authors provide an algorithm to solve this game. The authors show that efficient optimal planning in general-sum games is impossible unless NP=P, while identifying structural conditions that allow tractable solutions. Furthermore, in cooperative games without payments, learning is statistically hard despite aligned rewards, but tractable under certain conditions. With payments, sample-efficient learning becomes possible, and comparing upfront versus on-the-fly payments provide advantages.", "questions": "- How did the structure of the payment(s) and reward(s) change in the Stackelberg game to turn this from a cooperative game to general sum game?", "limitations": "- The construct of the Stackelberg game the authors propose - task for payment, refers really to only one type of game, and not a general class of Stackelberg games. This is fair, but limited to this setting.\n\n- Overall, with the lack of empirical results, and lack of baseline comparison with many other approaches to solving Stackelberg games, I do not feel this paper contributes significantly to advancement in Stackelberg game learning.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The study of Stackelberg-Markov games is in general highly relevant to RLHF and robust human-AI interaction environments. This research has potential to shed insight in the area.\n\nWeaknesses:\n\n- No empirical results to support the author's theoretical claims.\n- The complexity theory is somewhat trvial and not meaningful. Stackelberg games are notoriously inefficient to solve for equilibrium. Established bilevel optimization algorithms such as KKT reformulations, which can compute Stackelberg solutions under polynomial time, are not covered in the literature review. The authors need to do more review on SoTA and established Stackelberg solvers.", "was_revised": true, "final_justification": "While the empirical results strengthen the paper, the clarity of formulations and proofs needs improvement - its a bit hard to verity. Furthermore, I feel that a lot of literature that should have been covered in the literature review were not. Leads me to think that some similar concepts may already exist in the field - and could be leveraged, compared against, or benchmarked against.\n\nI see that the other reviewers do appreciate the work more than myself. I'm happy to not be a blocker on this front, perhaps there's something I've missed. I've raised my score, but the recommendation the same - perhaps under revisions it could become a better work.", "rebuttal": "Thanks for your review, reviewer jtyD! We will be sure to incorporate your feedback in our next revision.\n\n```\nThis paper provides an algorithm for two-stage resource allocation problem modelling two-player leader-follower task assignment within the context of a Stacklberg game. \n```\n\nJust as a point of clarification, our paper is not about “resource allocation” nor “task assignment”. It considers the general Stackelberg Markov Game setting, wherein the leader is able to also set outcome-based payment.\n\n```\nNo empirical results to support the author's theoretical claims.\n```\n\nThanks for this note! Indeed, our contributions in this paper are mainly theoretical. Theory is important in this setting as algorithms are used to compute payment. Thus, provable guarantees are important to ensure that the payment computed are sensible/optimal (L39-40).\n\nWith this said, we have performed experiments, following your feedback that experiments would further improve the paper. Please find below a description of the experiment we ran.\n\n\n**Setup:** We consider a turn-based Markov Game, where the leader is solving a RL problem and the follower solves a bandit problem in its BR (Bai et al). This class of Markov Games includes the hard instance construction in Section 5. Our goal is to examine whether learning without payment can get stuck in more \"average (and not worst) case\" Markov Games.\n\n\nThe leader is doing RL in a toy MDP with $H = 5$. For the follower, arm $a_1$ leads to a MDP, whose optimal return is the optimal return in the (turn-based) Markov game. Arm $a_2$ has a deterministic high reward that is $\\alpha$ that of the optimal return.\n\n\nBy varying $\\alpha$, we can make the follower get \"stuck\" in myopically choosing $a_2$, thus preventing the leader from exploring and learning the actual optimal policy. This is the intuition behind the negative results, Theorem 5.1 and 5.2, where we set $\\alpha$ very high.\n\n\nFor the baseline, we use the single-agent learning algorithm UCB-VI in the without payment case, and compare it against UCB-VI-FP in the with payment case. We track the cumulative regret of the two learning algorithms over $40000$ episodes and across $20$ runs.\n\n\n**Finding:** We experiment with different $\\alpha$’s, finding that learning without payment can get stuck in the myopic optimum even when $\\alpha$ is as low as $0.5$. Interestingly, this suggests that there are “non-worst-case” Markov games, where exploration can be difficult without payment.\n\n\nUnder $\\alpha = 0.5$, our plots show that:\n\n1. In absence of payment, even if the leader is using a (one-sided) no-regret algorithm (UCB-VI), the leader may not be able to explore adequately and incur linear regret.\n2. UCB-VI-FP attains sublinear regret, showing the importance of payment in incentivizing  exploration needed to learn the optimal policy.\n3. UCB-VI-FP initially incurs a higher regret, which we expect due to the additional payment used by the algorithm to incentivize exploration. Over time, its regret improves due to exploration shrinking the policy regret, and reduced incentivization and thus payment regret. UCB-VI-FP’s regret eventually dips below that of UCB-VI, with a crossover point at around episode 13500.\n4. UCB-VI-FP’s regret converges like $O(\\sqrt{K})$, which matches our upper bound. We verify this upper bound for every episode $i$ for $i \\in [40000]$.\n\nHere is a table summarizing average regret (cumulative regret / $T$) across episodes, averaged over the runs.\n\n| Episode $T$  | $5000$ | $10000$ | $15000$  | $20000$ | $25000$ | $30000$ | $35000$ | $40000$ |\n|--------------|--------|---------|----------|---------|---------|---------|---------|---------|\n| UCB-VI Average Regret  | 0.42   | 0.42    | 0.42     | 0.42    | 0.42    | 0.42    | 0.42    | 0.42    |\n| UCB-VI-FP Average Regret  | 0.70 | 0.49    | 0.40     | 0.35    | 0.31    | 0.28    | 0.26    | 0.24    |\n\n\n\n\n```\nThe complexity theory is somewhat trvial and not meaningful. Stackelberg games are notoriously inefficient to solve for equilibrium. Established bilevel optimization algorithms such as KKT reformulations, which can compute Stackelberg solutions under polynomial time, are not covered in the literature review. The authors need to do more review on SoTA and established Stackelberg solvers.\n```\n\nThanks for this comment! We have a few points of disagreement with this characterization of our work:\n\nFirstly, Theorem 4.2 of our results actually show that general-sum Stackelberg Markov games with payment cannot be solved in polynomial time, contrary to your claim that bi-level optimization algorithms “can compute Stackelberg solutions under polynomial time”.\n\nSecondly, bi-level optimizers can compute a local but not global optimum, which is the main goal of our paper. On the topic of local optimum, we did consider adopting an existing optimization approach (Shen et al) to compute this, should it be of interest. Although, as we write in L205-207, solving for the local optimum is not the main focus of our paper.\n\nThirdly, we believe bilevel optimization algorithms are mainly applicable in planning, where one wishes to compute the optimal policy offline under known rewards and dynamics. On the other hand, we study *learning* in this work as well, where online adaptive exploration is needed to minimize regret under unknown rewards and dynamics. To this end, we have shown several results in the learning setting, where we do not believe bi-level optimization solvers are applicable.\n\nFinally, we will be sure to include this discussion on bi-level optimization solvers and global vs local optimum in our next revision. Thank you for drawing attention to this with your comment! And please let us know if there are any other relevant works on “SoTA and established Stackelberg solvers”, as we believe we have covered all the pertinent works on computing and/or learning *global optimum* in Stackelberg Markov Games in Section 3.\n\n\n```\nHow did the structure of the payment(s) and reward(s) change in the Stackelberg game to turn this from a cooperative game to general sum game?\n```\n\nIn terms of rewards, by definition, the only difference between the general-sum and the cooperative setting is that in the latter case, $r^L = r^F$ (L67). In terms of payments, we show in Lemma 6.2 that the optimal payment in cooperative games is zero.\n\n```\nThe construct of the Stackelberg game the authors propose - task for payment, refers really to only one type of game, and not a general class of Stackelberg games. This is fair, but limited to this setting.\n```\n\nTo clarify, we allow for any Stackelberg Markov game in our setup. Please see the first sentence in our formulation (L64-66), where we make no assumptions on the Stackelberg Markov game we consider besides bounded rewards (a standard assumption in RL theory).\n\nIn our setup, the leader is able to also set payment. Thus, Stackelberg Markov games with payment generalizes Stackelberg Markov games. Indeed, constraining the leader to zero payment (i.e. $(\\pi, b) = (\\pi, 0)$) corresponds to the leader’s policy space in Stackelberg Markov Games without payment.\n\nAltogether, we believe we study a fairly general setup, which is more general than the class of Stackelberg Markov games. We will be sure to make this clear in the revision, and please let us know if there are more concerns we could clarify, thanks!\n\n```\nProof sketches should be included in the main paper for the reader to get a general idea how the proof for each theorem was arrived at.\n```\n\nThanks for this! We will be sure to include proof sketches with the additional space provided in the revision. Please understand our paper was fairly constrained in terms of space in order to fit all the results in."}]

Author rebuttal:

Meta-review: This paper studies Stackelberg Markov games with outcome-based payments, offering a theoretical treatment of planning and learning under different reward alignment conditions. The authors establish hardness results for general-sum settings and identify structural cases where efficient solutions exist. They also introduce a UCB-based learning algorithm for cooperative settings with payments, proving sublinear Stackelberg regret and clarifying the necessity of payments even with aligned rewards. Strengths include the clean formalization, thorough characterization of complexity boundaries, and clear exposition. While the main weakness lies in the absence of extensive empirical validation and some questions regarding scope and scalability, the authors partially addressed this with toy experiments and clarifications during rebuttal and the authors' final comment. Overall, the combination of rigorous theoretical contributions, strong motivation, and responsive engagement with reviewer concerns justifies acceptance.
Decision: Accept (poster)