Stackelberg Learning with Outcome-based Payment

Thanks for your review, reviewer jtyD! We will be sure to incorporate your feedback in our next revision.

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. 

Just 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.

No empirical results to support the author's theoretical claims.

Thanks 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).

With 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.

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.

The 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.

By 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.

For 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.

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.

Under $\alpha = 0.5$, our plots show that:

1. 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.
2. UCB-VI-FP attains sublinear regret, showing the importance of payment in incentivizing exploration needed to learn the optimal policy.
3. 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.
4. 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]$.

Here is a table summarizing average regret (cumulative regret / $T$) across episodes, averaged over the runs.

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.

Thanks for this comment! We have a few points of disagreement with this characterization of our work:

Firstly, 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”.

Secondly, 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.

Thirdly, 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.

Finally, 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.

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?

In 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.

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.

To 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).

In 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.

Altogether, 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!

Proof 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.

Thanks 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.

Thank you for getting back to us, Reviewer jtyD! We appreciate it, and for completeness, we would like to follow up on some of the points raised.

If I'm not mistaken, the payment mechanism appears to be a modification of the original reward scheme (e.g., [1]), which is not explicitly discussed in the literature review of this paper.

To clarify, payment in our setting corresponds to reward shaping, which dates back to [Ng et al 1999]. We explicitly discuss the literature review of this first in L33-35 and then in L150-154.

[1] looks to be about reward gaming, and characterizes what happens when a single (fixed) imperfect reward is optimized instead of the true reward. In our setting, the leader gets to adaptively modify the true reward over episodes to incentivize exploration. And so, the two formulations seem to be somewhat different on our first reading. We plan to take another closer look, and please let us know if there is a connection we missed here, thank you!

Furthermore, the payment system (lines 90–93) resembles a principal-agent task-assignment problem, where a principal contracts an agent to act on their behalf to achieve optimal outcomes. This game has been extensively studied in economics and game theory literature [2], yet it is not acknowledged in this paper.

Thank you for clarifying! We believe we have acknowledged this connection to the principal-agent contracting game. The acknowledgement is in the lines 90-93 that you noted: "This is often used to model a principal contracting an agent to act on their behalf, with the trajectory informing how much the leader will be paying ex-post" (L92-93).

In light of your comment, we will be sure to make this more clear, and include a pointer to the broader algorithmic contracting literature (e.g. [2]) as you suggest.

The authors' perspective is interesting, though some similar concepts may already exist in the field.

Thanks for this! We believe a strength of our paper is the generality of the setting we study, which subsumes some of the more specific settings studied in prior works. For instance, one general result of ours is an efficient algorithm for learning with payment (which we show to be necessary) in any Cooperative Stackelberg Markov Game.

To clarify further, regarding the KKT reformulation of bilevel optimization problems [3]—a well-known and elegant methodology in bilevel and multi-level optimization—there are known limitations. However, some bilevel optimization problems can be formulated as linear programs (LPs) or convex quadratic programs (QPs), leading to a poly(T) solution. Thus, I am uncertain about the author's claims of NP-hardness (though I could be mistaken). Contrary to the authors' rebuttal, this is a global solution (not local). Additionally, gradient ascent algorithms for bilevel optimization can lead to sufficient local solutions, but I am unsure if this was covered in the literature review [4,5]—it seems relevant here.

Thank you very much for helping us understand your point!

1. As you write, some bi-level optimization programs can be formulated as a LP/QP, whose global optimum can be computed in poly time. We agree with this. But would you agree that this statement does not imply all bi-level optimization programs can be solved in poly time?

2. Our result is that the optimization program in the general-sum case cannot be solved in poly time. We believe this does not contradict your statement that some bi-level programs are solvable in poly time.

Please let us know if this helped to address your uncertainty about our NP-hardness result. And thank you for your references [4] and [5]! We will be sure to include our discussion on bi-level optimizers and local vs global optimum in the revision.

I appreciate the authors' inclusion of additional empirical results. Given the paper's claims, empirical validation is essential to strengthen its credibility and applicability. Overall, I believe the clarity of the work needs improvement. I found the formulations and proofs difficult to follow—either due to my own failure to appreciate the work or because the paper requires further refinement.

I'll updated my score in light of the rebuttal and have no further questions.

Thank you for this note on the clarity of our paper, and for updating your score!

We will work to improve our paper using your detailed feedback. Please let us know if you have any further questions, thank you!

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.

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.

Thanks 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).

With 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.

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.

The 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.

By 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.

For 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.

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.

Under $\alpha = 0.5$, our plots show that:

1. 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.
2. UCB-VI-FP attains sublinear regret, showing the importance of payment in incentivizing exploration needed to learn the optimal policy.
3. 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.
4. 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]$.

Here is a table summarizing average regret (cumulative regret / $T$) across episodes, averaged over the runs.

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…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?

Firstly, 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).

As 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.

Secondly, 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.

We 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.

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?

Yes, 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.

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.

Thanks 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.

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.

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.

To 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.

1. 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.
   Moreover, 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).

2. 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.
   And 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.

3. 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.

Overall, 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!

Lastly, 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.

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?

In 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!

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.

This follows from that the value function is additive in terms of rewards: $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.

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?

We believe that there are genuine constraints in the real world such that upfront payment is preferred and/or necessary.

Another 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.

More 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:

1. Non-enforceable/costly contract situations: when the principal can renege upon observing the outcome.
2. 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.
3. Risk-aversion on the part of the agent: when the agent is risk-averse, upfront payment may be preferred when the outcome is stochastic.

While 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!

At the end of Section 4 it would be helpful to reference where in the appendix local Stackelberg optima are treated

Thanks for this! Yes, we will be sure to include a pointer to section A.2.2 of the Appendix in the revision.

Thank you for getting back to us, Reviewer tKfe! Stackelberg games are a general class of games with an extensive body of literature. So it makes a lot of sense that you had some questions on how our work is positioned w.r.t. existing works.

We are glad to hear that we are able to address the questions you had. Please do let us know if you have any further questions. Thank you once again for your review, which has helped to improve our paper and better contextualize the novelty of our results!

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.

In Section 6.2, unless I missed it, you did not define indicator bonus? What is this?

Thanks 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).