Oracles and Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learning
Authors: Matthias Gerstgrasser
David C. Parkes
Venue: Submitted to ICLR 2023 (2023)
Keywords: Multi-Agent Reinforcement Learning
Game Theory
Security Games
Mechanism Design
Stackelberg Equilibrium
Indirect Mechanism Design

Abstract: Stackelberg equilibria arise naturally in a range of popular learning problems, such as in security games or indirect mechanism design, and have received in- creasing attention in the reinforcement learning literature. We present a general framework for implementing Stackelberg equilibria search as a multi-agent RL problem, allowing a wide range of algorithmic design choices. We discuss how previous approaches can be seen as specific instantiations of this framework. As a key insight, we note that the design space allows for approaches not previously seen in the literature, for instance by leveraging multitask and meta-RL techniques for follower convergence. We propose one such approach using contextual poli- cies and evaluate it experimentally on standard benchmark domains. Finally, we illustrate the effect of adopting designs outside the borders of our framework in controlled experiments.

Under review as a conference paper at ICLR 2023
ORACLES & FOLLOWERS: STACKELBERG EQUILIBRIA IN DEEP MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Stackelberg equilibria arise naturally in a range of popular learning problems, such in security games indirect mechanism design, and have received increasing attention in the reinforcement learning literature. We present a general framework for implementing Stackelberg equilibria search multi-agent RL problem, al- lowing a wide range of algorithmic design choices. We discuss how previous approaches can be seen as specific instantiations of this framework. As key insight, we note that the design space allows for approaches not previously seen in the literature, for instance by leveraging multitask and meta-RL. techniques for follower convergence. We propose one such approach using contextual policies and evaluate it experimentally on standard and novel benchmark domains, show- ing greatly improved sample efficiency compared to previous approaches. Finally, we explore the effect of adopting designs outside the borders our framework.
INTRODUCTION
Stackelberg equilibria are an important concept in economics, and in recent years have received increasing attention in computer science and specifically in the multiagent learning community. In these equilibria, we have an asymmetric setting: A leader who commits to strategy, and one or more followers who respond. The leader aims to maximize their reward, knowing that followers in turn will best-respond to the leader's choice of strategy. These equilibria appear in a wide range of settings. In security games, a defender wishes to choose an optimal strategy considering attackers will adapt to it (An et al. 2017 Sinha al.) 2018). In mechanism design, aim to design mechanism that allocates resources in an effiiiett manner, knowing that participants may strategize (Nisan & Ronen 1999] Swamy 2007 Brero et al. (0211). More broadly, many multi-agen agent system design problems can be viewed as Stackelberg equilibrium problems: we as the designer take on the role of the Stackelherg leader, wishing to design a system that is robust to agent behavior.
We are particularly interested in Stackelberg equilibria in sequential decision making settings, i.e. stochastic Markov games, and using multi-agent reinforcement learning techniques to learn these equilibria. In this paper we:
1. Introduce a new theoretical framework for framing Stackelberg equilibria as a multi-agent reinforcement learning problem,
2. Discuss how a range of existing approaches fit into this paradigm, as well as where there remain large unexplored areas in the design space.
3. Reveal novel approach to accelerating follower best-response convergence, borrowing ideas from multitask and meta-RL, including an experimental evaluation, and
4. Elaborate on several important conditions for Stackelberg convergence, and demonstrate how things can fail when these conditions are not met.
Our main theorem (Theorem D allows a black-box reduction from learning Stackelberg equilibria into separate leader and follower learning problems. This framing encompasses and generalizes several prior approaches from the literature, in particular Brero et al. (2022). and gives a large design space beyond what has been explored previously. Our second main technical contribution applying contextual policies, a common tool in multitask and meta-RL (Wang et al.) 2016), to the follower learning problem. In doing so, followers can generalize, and quickly adapt to leader

---

Under review as a conference paper at ICLR 2023
policies. We validate this approach in experiments and show greatly reduced sample complexity inner loop-outer loop approaches. We also show how violating the conditions
compared to previous of our theorem can lead to complete failure of the learning process, consistently across underlying algorithms.
In the remainder of the paper, will introduce Stackelberg equilibria and Markov games in Sec- tion 2 In S3 we motivate and define our framework for learning Stackelberg equilibria using multi-agent RL and discuss its scope and limitations. We define our novel contextual policy oracle in and empirically evaluate it in Section 5 on existing and novel benchmark domains.
1.1
PRIOR WORK
Learning Stackelberg Equilibria. Most prior work Stackelberg equilibria focus on single- shot settings such as normal-form games, a significantly simpler setting than Markov games, often in security games. A broad line of work focuses on computing Stackelberg equilibria, such as Paruchuri et al.] ): Xu et al. bp; Blum et al. (2014); Li al. (2022), Among the first works on learning Stackelberg equilibria was Letchford al. (2009), p, who focus on Bayesian games. Peng jet al.] (2019) give results for matrix games with sample access only. |Wang et al. (2022) show an approach differentiating through the so-called KKT conditions, again for normal-form games. Bai iet al. (2021) give lower and upper bounds on learning Stackelberg equilibria in general-sum games, including bandii RL" games with one step for the leader, and sequential
meriiiion-maiingge for the followers. Few works in this area consider Markov games: Zhong et al. (2021) show algorithms that find Stackelberg equilibria in Markov games, but assume myopic followers, a significant limitation compared to the general case. [Brero et al. (2021 a b (022) use an inner-outer loop approach, which they call the Stackelberg POMDP, primarily aimed at indirect mechanism design.
Mechanism Design. One of the first works specifically discussing Stackelberg equilibria in a learning context is [Swamy (007), who design interventions in traffic patterns. More recently, sev- cral strands work have focused on using multi-agent RL techniques to learn optimal mechanism design, often framing this is bi-level or inner-outer-loop optimization problem. Zheng et al. (2022) use a bi-level RL. approach to design optimal tax policies in a simulated world but without provably Stackelberg properties. Yang al. (2022) use a meta- veeta-grdieent approach in specific incentive de- sign setting. [Shu & Tian (2018) and Shi et al. (2019) learn leader policies in a similar "Stackelberg Markov games" setting. Both use form of modeling other agents coupled with rule-based follow- ers. Balaguer et al.] (2022) use an inner-loop outer-loop gradient descent approach for mechanism design on iterated matrix games (which we also use as an experimental testbed). They mainly focus on the case where both the environment transition as well as the follower learning behavior is dif- ferentiable, and otherwise fall back to evolutionary strategies for the leader. Interestingly, none of these recent works explicitly mention Stackelberg equilibria. As direct corollary of our own work, we show that Balaguer et al. (2022) and Zheng et al. (2022) may not give Stackelberg equilibria, but Balaguer et al. (2022) could do so with minor modifications.
PRELIMINARIES
Markoy games. We consider partially observable stochastic Markov games, essentially a multi- agent generalization of partially observable Markov Decision Process (POMDP).
Definition 1 (Markov Game). A Markov Game M with n agents is tuple (,,
consisting of a state space S, an action space A = (A), ... : An). a (stochastic) transition function S x A + B observation space Ω factorr
T 5 x A + S, (stochastic) reward function functiion
(S,,..., P2), a (stochastic) observation function O S x A > Ω and a discount factor 7/-
At each step of the game, every agent: chooses an action ai from their action space A,, the game state evolves according to the joint action (a1,t...., an,z) and the transition function T, and agents receive observations and reward according to O and R. An agent's behavior in the game is charac- terized by its policy n, O as which maps observations to actions Each agent in Markov
'To keep notation concise we discuss here the memory-less case, but all our results generalize to stateful leader policy in a straightforward manner, as discuss in Appendix B
2

---

Under review as a conference paper at ICLR 2023
Game individually seeks to maximize its own (discounted) total return Σ "rri(ss,,s, as,e, as,c;0-..)) This gives rise to the usual definitions of Nash equilibria (NE), correlated equilibria (CE), and coarse cor- related equilibria (CCE), which do not repeat in full here, well their Bayesian counterparts. Note that strategies in Markov games and in each of these equilibrium definitions are policies, not actions: pair of policies 7 22 in two-player Markov game is Nash equilibrium if neither agent can increase their expected total reward by unilaterally deviating different policy Te.
Stackelberg Equilibria. Unlike all the above equilibrium concepts, Stackelberg equi- librium is not symmetric: There is a special player, the leader, who commits to their strategy first; the other player (the follower) then chooses their best strategy given the leader's choice of strategy. This makes the leader potentially more powerful.
Example 1. In a game often called the "battle of the sexes," you and wish to have dinner together, but you prefer restaurant A (deriving happiness 2, but I only get happiness 1), and prefer restaurant B (I get happiness 2, you
Table "Battle of the Sexes" game.
get happiness b)-but we would both rather eat logether al our less-preferred venue, than to eat separately (we both get happiness 0). Table 7 shows the payoff matrix of this game. There two pure Nash equilibria in this game: We both go to restaurant A, or we both go to restaurant B. But there is only a single Stackelberg equilibrium (per leader): If you commit going restau- rant A, then my only best response is to also go to restaurant A. In doing so I receive happiness 1, whereas my only alternative would be eat alone at restaurant B for happiness O. Notice that this hinges on the leader strictly committing to their choice of restaurant.
2.1 0,0
0,0
1,2
This Stackelberg concept again also extends to Markov games: Here leader agent L decides on their policy (i.c. strategy), and the remaining (follower) agents - knowing the leader's choice of policy- - best-respond to this. The leader seeks to maximize their own reward, considering that followers will always best-respond to their choice of policy. For instance, in an iterated prisoner's dilemma (Robinson & Goforth (2005), leader might commit tit-for-tat strategy, in turn leading the follower to cooperate.
We are interested in multi-follower settings, where Stackelberg equilibria have also been defined Nakamura (2015); Zhang et al. (2016); Liu (1998): [Solis et al. (2016); Sinha et al. (2014); Wang al.) (2022 : Brero al. (2021a). With multiple followers, the "best response" of the followers can be an ambiguous term. Any choice of leader strategy IT, induces a Markov game between Fxz between the followers, which could feature multiple equilibria and equilibria of different types, such as Nash, correlated and coarse correlated equilibria, each giving rise to corresponding Stackelberg- Nash, Stackelberg- and Stackelberg-CC
concept. We handle this our definition through an oracle (see also e.g. [Wang al. (2022): y: For any choice of leader strategy, we assume we are given a follower equilibrium (or probability distribution over equilibria), 8 E(Fa.). by an oracle
Definition 2 (Stackelberg equilibrium). Given Markov Game M and a follower best-response oracle ε, a leader strategy a together with a tuple of follower strategies TF a Stackelberg equi- librium, if TT. maximizes the leaders expected reward under the condition that follower strategies are drawn from E(FT..):
TL E arg max "L
E (FFE(FFL)
as,,
where the second expectation is drawing actions and state transitions from their respective policies Lt, uF and transition function T, and the reward function is r, all as in Definition 7 If the fol- lower oracle & gives a Nash equilibrium in the induced game Faz, we call this a Stackelberg-Ner equilibrium, and similar for CE and CCE.
This use of an oracle is convenient not only for the multiple-follower definition, but also crucially useful abstraction for any number followers. What we have in mind for practical purposes is an algorithm that computes or learns the follower best-response equilibrium, E(Fa)) given the leader strategy nr, often using RL. In the remainder of the paper, when we say "oracle" this is what we mean.
3

---

Under review as a conference paper at ICLR 2023
3 A GENERAL FRAMEWORK FOR STACKELBERG EQUILIBRIA IN MULTI-AGENT RL
Several approaches have been proposed to learning Stackelberg equilibria in Markov games, or to use multi-agent RL for mechanism design in such settings. A main aim of our work is to elucidate commonalities between these approaches, and to delineate what is required to guarantee Stackelberg equilibria. For instance, most of the existing approaches use (reinforcement or no-regret) learning to implement the follower best-response, effectively arriving an "imeer-oop--outer-loy system ": The leader performs one update to their policy, then the followers perform many updates to theirs until they converge to a best response, then this repeats. Is this the only possible approach? Can you mix-and-match leader and follower approaches at will? One approach for leader learning is reinforcement learning, where the gradient of the leader policy is estimated from sampled trajecto- ries (Brero et al., 102laattiis is in contrast to global approaches such as direct differentiation of the leader policy in a world where everything is differentiable or evolutionary strategies (Balaguer al.] 2022), which modify the leader policy as a whole based on total episode reward, without looking at what happens at each step. Some RI. approaches (Brero et al. 2021a 2022) incorporate the follow- ers' learning dynamics into the leader's view of the environment. Is it necessary that the leader can see this adaption process? Or could we also have follower best-respond to the leader immediately on the first step it takes? Some approaches for mechanism design do not explicitly mention Stackelberg equilibria (Zheng et al. 2022; Balaguer et al. 2022). but seem very similar to approaches that do; do those approaches converge framework that answers these questions, and provide a common language to categorize the various strands of research in this area.
Stackelberg equilibrium? In this section we develop common
A key idea is that we can separate the problem into a leader's learning problem, and an imple- mentation of the follower oracle. Our framework informally, provides two insights. One, for any follower oracle implementation and any construction of the leader problem, a solution is a Stackel- berg equilibrium as long as the reward given to the leader is that from the original Markov game with restoresppnning followers. A key insight following from this is that follower oracles need not be im- plemented using learning algorithms, leading to new approach which we will outline Section 4 This also encompasses wide range of leader learning approaches, including direct gradient de- scent, optimization, and evolutionary strategics. At the same time it gives very simple conditions to ensure Stackelberg solutions, and delineates approaches that do and do not give these. Two, for any query-based oracle implementation, we can construct the leader problem as a POMDP, amenable to solving through RL methods. Since most follower oracle implementations are query-based (or can be approximated through queries), this again encompasses a wide range of possible approaches. Together, these simple conditions open wide design space, which includes existing approaches but also provides a much wider field of possibilities, one of which we demonstrate in Section +
We now make this formal. The general case of the following theorem is intentionally kept close to the definition of a Stackelberg equilibrium, and we will discuss implications of this after the theorem statement.
Theorem 1. Given a Markov Game M and a follower equilibrium oracle E, then:
[General Case] If
1. the leader locally aims solve a single-agent optimization problem [(TL), and
2. for each choice of leader policy LL, L computes the follower best- rest-response E(ML), and
3. ((TL) evaluates the leader policy Ty against the follower best-response E(TL) in M, i.e. the value of L(TL) is L E(TL)) in M,
then optimal solution nÝ to L together with the follower best-response E(T)) form Stackelberg equilibrium in M.
(Query-Orach) Special Case] Furthermore, additionally
4. the follower oracle implementation & only requires query access to n, L.e. values a (o) for one or more observations o E Ωu from M.
then L can be constructed POMDP.
4

---

Under review as a conference paper at ICLR 2023
Proof. See Appendix A We briefly note for the following discussion that the construction in the query-oracle case constructs episodes in C by using an initial segment in which the oracle queries Tt, and a final segment in which episode of M is played by nT. and the E(Tr.) computed in the initial segment. This is formalized in the proof in the Appendix.
Theorem I unifies several approaches from the literature. The main theorem of Brero et al. (202 aa can be of our theorem significantly generalizes that result to allow for any query-based follower oracle. Furthermore, the general case of the theorem extends this to approaches that do not require the leader problem to be a POMDP. While the general case follows very easily from Definition [2] it still provides a very powerful insight. For instance, the "good shepherd" approach (Balaguer al.) 2022) performs gradient descent directly on the leader policy, either by differentiating through the environment and followers, or by estimating the gradient using evolutionary strategies. Neither requires the problem to be a POMDP. At the same time, the general case of Theorem applies, and tells us that the "good shepherd" approach in its current form may not give Stackelberg equilibria: it accumulates leader reward even during follower learning, i.e., when followers are not (yet) playing (TT). This may be intentional: In the "good shepherd" approach the leader optimizes its expected return over longer horizon during which followers adapt from scratch. This is subtly different optimization target than a Stackelberg equilibrium, which optimizes steady-state return (see also Appendix C.3). Further, the theorem does not make any assumptions about the type of access the environment and follower oracle, and can thereby encompass approaches that only require sample access as well those that have access a description, and approaches where followers or the environment are differentiable.
special case of the query-oracle case. However, even the query-oracle special case
3.1 SOLVING THE LEADER PROBLEM
Theorem M does not assume a specific approach to solve the leader problem L; rather, it gives us broad array of tools to solve Stackelberg problems in practice. One particular set of tools lie in the query-oracle special case: by constructing L as a POMDP, the entire suite of existing (deep) RL algorithms become available. We later show experimental results using PG, PPO and DQN, but this is by no means exhaustive.
A reasonable question to ask is whether the POMDP property is actually required for RL algorithms to solve these problems. For instance, if we implemented the follower oracle & in a way that is not part of the leader problem L, essentially skipping the "initial segment" used in the construction of C in the special case of Theorem [ would RL still be able to solve the leader problem? Theorem 2 in Appendix D shows that the POMDP property of the query-oracle construction meaningful in practice: There are Markov games where an RL algorithm provably cannot learn the optimal leader policy if the follower best-response oracle not implemented in this manner. This is further demonstrated experimentally in Appendix C.I
Appendix further details how to extend Theorem | to leader policies with memory, and details crucial condition of leader invariance which we would like to draw particular attention to. This condition requires that the leader policy act the same during oracle queries as it does during real play. In the memory-less case this follows immediately in theory, but is an important implementation detail in practice. In Appendix (C.4 we show an example where a scemingly innocuous step counter being made part of the leader's observation leads learning failure.
3.2 IMPLEMENTING THE FOLLOWER ORACLE
A key insight is that Theorem works for any implementation of follower oracle. Some of the prior literature focuses entirely on the leader problem and assumes literal oracle for follower best- response, sometimes also requiring this be differentiable. Practical follower oracle implementations in the literature can broadly be grouped into two categories.
Optimization-basee approaches, which have access to a description of the environment (e.g. payoff matrix), have been used in simple one-shot settings such as (non-iterated) matrix games, where description of the leader policy and environment can be used to compute an optimal follower response. This is often coupled with optimization for the leader policy, for instance in in/acuchrrii et al. 2008 Xu al. (2014).
5

---

Under review as a conference paper at ICLR 2023
Learning-based approaches, which require only sample access to the environment, and potentially the leader policy. This approach is taken in some of the single-shot Stackelberg literature and most of the RL-based Stackelberg literature: every time the leader policy is updated to new policy, T L,new, followers use a standard learning algorithm, for instance RI. or regret minimization in the Markov game case, to learn in the induced game Fe Any convergence guarantee for the follower algorithm (e.g., CCE in no-regret, or Nash in V-Learning in some conditions) translates to the equivalent Stackelberg-CCH) or Stackelberg-Natt initialized randomly after each leader update, which makes the environment stationary, or trained without this (possibly requiring less training, in the case the leader policy only changed a little, but see Appendix C.4. It is worth noting that our framework using an RL oracle "looks like" leader and follower are simultaneously learning to act a typical multi-agent RL system, just at different timescales. However we find it useful to think of this setup in terms of leader learning separate from follower oracle, and there are important differences from standard multi-agent RL: The leader should receive reward only when followers are playing their best-response equilibrium, and the entire follower learning process should be one episode for the leader.
equilibrium. Follower weights can be re-
4 META- RL FOR STACKELBERG RL
Going beyond this, Theorem suggests wide design space for implementing the follower oracle. As a key contribution, we explore using multi-task and meta-RL, as a means of implementing the follower oracle. This is both to illustrate the power of Theorem a way to think about Stackelberg learning, as well as due to the advantages of the approach over cxisting ones.
We can recognize that the follower games, Fazs are in fact family of related problems. For this reason, the follower oracle problem can be seen as a multitask or meta-RL RL problem. and solved using techniques from those fields. We make use of contextual policies (Wang al.) (016), where a context w describes the task an agent is supposed to solve. In our case, the context provides the specific MDP among a family of MDPs follower finds itself in, and is a description of the leader policy. This context, w, is concatenated to the follower agent's 's observation o and agent i observes w)) at timestep
We focus on settings where the leader policy's 's effect on the follower can be fully understood with a small number of queries, and we directly use the leader's response to fixed set of queries as the context w. For instance, in an iterated prisoner's dilemma, we ask the leader three questions: "How do you act on the initial step of the game?", "How do you act if the opponent cooperated in the previous step?" and "How do you act if the opponent defected in the previous step?" Clearly, if these are the only three possible states, this is sufficient to characterize the leader policy. We further use two-stage training approach. In Phase 1, we train follower meta-policy against different, randomized leader policy in each episode. By the end of this phase, the meta- meta-policy is able to best-respond to all possible leader policies. In Phase 2, we train leader policy against this follower, where the leader is queried at the beginning of each episode. In our current experiments explicitly define the context in the above way. For settings where this is not possible, the multitask and meta-RL literature provides a range of approaches that infer context, often using recurrent networks (Wang et al. [0166] Mishra al. 2017 Duan et al., 2016 Rakelly et al. 2019
Zintgraf et al. 2019 Humplik et al.) 2019).
Relation to existing approaches in the literature Previous approaches for Markov games have largely focused on no-regret and policy gradient learning to implement follower oracles, coupled with either RL or direct gradient descent methods for the leader. [rero et al.] (2021a 2022) use
no-regret dynamies or Q-learning to implement the follower oracle inside the leader's episode roll- out, and standard RL techniques to solve the resulting leader POMDP. Balaguer et al. (2022) use gradient methods to implement the follower oracle. In the case where both followers and world dynamics are differentiable they directly differentiate the leader policy (as opposed to estimating its gradient using sampled trajectories). For the non-differentiable case they use evolutionary strategies (Sllimans et al.) 2017). Interestingly, they seem to accumulate leader reward throughout the entire learning phase of the follower. This puts their approach outside the scope of our Theorem [ and may give the leader the wrong optimization target, ing is that if the leader were to optimize for its final reward at the end of follower learning instead, their approach would fall within Theorem T and yield Stackelberg equilibria. /Zheng al. (2022)
detail in Appendix C.3 Our understand-
6

---

Under review as a conference paper at ICLR 2023
Table 2: Situating different approaches within the framework of Theorem [ Approaches marked do not fully satisfy the conditions of the theorem. Approaches marked in bold indicate approaches that apply to general Markov games, i.c., that are sequential for both leader and followers, and otherwise unrestricted.
Leader Learning Approach
Oracle Implementation
Optimization, Search
Direct Gradient Descent, Evolutionary Strategies
N/A Oracle
Letchford al. (2009)
Wang et al. (2022)
Zhong et al.
(2021)
Assumed Given
Peng et al. 2019)
No-Regret
Brero et al. 2021a
Balaguer al. 2022 x
Zheng al.
(2022 8
RL
Bai et al
2021
Yang et al. 2022)
Brero et al.
2022
Multitask / Meta-RL.
new
similarly use two-level RL design, using policy gradient learn each of the follower oracle and the leader policy. While they do not specifically mention Stackelberg equilibria, this would be the target equilibrium condition in their taxation- cattion-policy design setting. Interestingly, they use curriculum learning approach that can be seen a rudimentary form of the contextual policy meta-learning approach that we develop in this paper. As with Balaguer et al. (2022). Zheng et al. (2022) also seem accumulate leader reward, putting them outside the assumptions of Theorem | It is also not clear their implementation leader memory could violate the leader invariance requirement. However, it may be possible adapt their approach fall within the theorem by adjusting leader reward and resetting leader memory between follower queries / learning iterations.
5 EXPERIMENTS
We evaluate our Meta-RL approach on both a benchmark iterated matrix game domain, comparing to existing approaches, as well as on a novel Atari 2600-based domain that is significantly more challenging. In the first, our main positive finding is that our approach can match or exceed prior approaches at greatly improved sample efficiency. In the latter, we show for the first time a positive result using a principled Stackelberg approach on a state-of-the-an general RI. benchmark domain. We will detail each of the two domains and the results obtained therein using the Meta-RL algorithm. Appendices and G give further details on the algorithms used and full hyperparameters.
Environments: Iterated Matrix Games We evaluate contextual policy approach and gen- eral framework on an ensemble of iterated symmetric matrix games, such as the iterated prisoner's dilemma (Robinson & Goforth 2005). We choose these games present significant step up in complexity from previous approaches that give explicit Stackelberg guarantees, in that both leader and followers face sequential we play a matrix game for n 10 steps per episode, and give agents one-step memory. This makes these environments Markov games, with five states: one for the initial steps of each episode, and four for later steps depending on the two agents' previous actions. At each step, each agent has choice of two actions (e.g. "cooperate" or "defect"), leading to the next state, e.g. "both cooperated"..
evaluation domain they
decision-making problem. In these,
Figure shows the performance of our Meta-RI. approach using PPO for the leader. We compare against the approaches of BBllggur et al. (2022) and Brero et al. (022)). For our PPO+Meta-RL. approach, plot the combined environment steps used by the meta-follower training plus the leader training on the x-axis. For [alaguer et al. (2022). we estimate performance from Figure therein. Note that this is the eventual performance at the end of training (Balaguer al. 2022 do not publish learning curves).
We that final performance largely matches that of the "good shepherd" ES-MD approach, and by extension also matches or outperforms all their baselines (c.f. Figures and 2 therein). Importantly, notice that our approach converges in around 50k environment steps, whereas Balaguer et al. (2022)

---

Under review as a conference paper at ICLR 2023
env assurance
eTV battle
env chicken
env = coordination
Performanc
-1
-1
100000
200000
100000
200000
100000
200000
100000
200000
env = deadlock
env harmony
env = hero
env mixedharmony
Perforance
-1.0
0.0
-0.5
-1
-2.0
1.0
100000
200000
100000
200000
100000
200000
100000
200000
env noconflict
env prisoners_deliee
env prisoners dilemma
env = stag_hunt hunt
Porformance
-1.0
-0.25
-0.50
1.5
0
100000
200200
100000 200000
0
100000 200000
100000 200000
timestops_ooe
timestops_ total
timesteps_ total
timesteps -otal
Figure 1: Blue: Performance of our novel PPO+Meta-RI approach on 12 canonical symmetric iterated matrix games. Orange: PPO+Q-learn [rero et al. (2022). Dashed green: Good Shepherd
ES-MD Balaguer et al. (2022) (final performance at 1.28B timesteps, estimated from Fig. ibid.)
report performance 1.28 billion environment steps in the ES-MD case. We give further details on comparing performance to |Balaguer et al. (2022) in Appendix H
We also see that approach outperforms the PPO+Q-leam approach of Brero et al. (0022) In Appendix H we show the PPO+Q-learn approach training for significantly longer, and see that where it does converge it does so around 500k environment steps at the earliest, whereas for most of the harder cases it still has not nearly reached optimal performance at 2M timesteps. We again note that our approach shows greatly improved sample efficiency.
Environments: Bilateral Trade on Atari 2600 As a second, significantly sigher-diiensionall and challenging domain, we present a bilateral trade scenario on a modified Atari 2600 game (which are a state-of-the-ae oh-the-art art benchmark domain in single-agent RL). We use two-player version of the game "Space Invaders", and introduce an artificial resource constraint: Each agent can only fire in the game if they have bullet available. Initially, neither player has any bullets available. Throughout the episode, we give bullets to player 1, one at a time at stochastic intervals. Player can then choose to offer the sell this bullet to player 2 by offering them price, Player can choose to the bullet themselves. Player 2 in turn can choose to accept or reject a particular offer at a particular price. If trade takes place, the sales price is added to player I's reward, and subtracted from player 2's reward. Additionally, we introduce a reward scale imbalance: Each time player 1 successfully shoots an alien invader, they get reward of 0. However each time player 2 shoots an alien, they get a much higher reward of 1.0. Noting that even well-trained AI agents do not hit every single shot they take, we should still expect that player 2 be able generate just under 1.0 reward from each bullet they fire, and player 1 a much smaller reward of just under 0.1.
Clearly there more total reward generated player sells all their bullets to player 2, with the difference referred to as the "gains from trade" in economics. However, notice that this is not a mechanism design setting (there is no mechanism), and also that there are two Stackelberg equilibria: If player 1 is the leader, then their optimal strategy is to offer bullets to player 2 at just under player 2's average utility per bullet. Player 2 will best respond by accepting the trade, still generate small positive reward, and player 1 will receive almost the entirety of the gains from trade. In the second Stackelberg equilibrium, player 2 is the leader. Player 2's optimal strategy is to refuse any price higher than just above player 's average utility per bullet; and player 1 's best response is to offer to sell at that (low) price. In this scenario, player 1 will be left with little more reward than had they kept and used the bullets themselves, and player 2 will receive almost all the gains from trade.
8

---

Under review as a conference paper at ICLR 2023
Metric Seller Reward
Matric Buyer Reward
Metric Total Reward
Matric Avg Price
0.75
Value
Leader
2
0.50
Seller
Buyer
0
50
100
150
50
100
150
0
50
100
150
50
100
150
Slep
Step
Step
Step
Figure 2: Performance of PPO+Meta-RL. on Atari 2600 bilateral trade scenario. Plots show two Stackelberg equilibria: Agent (seller) as leader (blue curves) and agent (buyer) as leader (orange).
Figure 2 shows that our Meta-RL algorithm is able to successfully learn this for both equilibria. In this experiment we use discrete prices (0, 0.25, 0.5, 0. 0.7).1.0) for compatibility with the discrete Atari environment, so the results shown the exact optimum.
CONCLUSION AND DISCUSSION
Conclusion: We have introduced a general framework for using multi-agent RL approaches find Stackelberg equilibria in Markov games, and discussed how this encompasses several approaches in the literature while also conveying much larger design space. As second key contribution, we have proposed and evaluated novel approach to Stackelberg learning that uses Meta-RL to implement the follower oracle. This shows the power of our main theorem, which enables this approach, but is also key contribution itself. Our approach matches or exceeds performance to previous approaches at greatly reduced sample complexity in experiments. learning in novel domains beyond the reach of previous approaches, which we show on novel Atari 2600-based bilateral trade scenario. Finally, we show theoretically and experimentally the limits of Theorem []] and in particular that RL algorithms provably be unable to learn without the query-oracle special case construction.
enables Stackelberg
Discussion: In addition to the technical results, would like offer more high-level interpreta- tion of the framework. A useful way to think about learning Stackelberg equilibria in Markov games is that they are, in way, two problems in One, how does my strategy, i.e., choice of policy, affect the best-response of other agents? Two, how does my interactions with the environment, i.e., actions each step, affect the reward I (and others) get? These are two very different problems, even operating at different levels-entire policy, versus action at each step. In way, Theorem iis giving ways reconcile the best-response "meta-level" and the dnviromment-interacinn In the general case, using techniques such direct gradient descent or evolutionary policies, we focus on the best-response meta-level and either ignore the environment interaction (in evolution- ary strategies) or subsume them inside an end-to-end differentiation (in direct policy gradient). In contrast, in the query-oracle special case, we focus on the environment interaction RL problem, and implicitly work the follower best-response into this. One way of looking at the contextual-pooie follower oracle is that it makes the latter more feasible, by greatly reducing the number of leader queries compared to real environment interaction.
"RL problem."
We hope that this Meta-RL for Stackelberg learning work will enable Stackelberg RL approaches to scale up to richer settings, both through the explicit, contextual-policy approach taken in this paper, as well as approaches that infer context through recurrent networks. Beyond this, we hope the framework of Theorem will inspire novel ways of thinking about Stackelberg RL. One potential avenue for future work that we are excited about is to study approaches that explicitly take into account both the "meta-level" and cnnvirinmmentinteeraeee that doing so could enable Stackelberg RL to scale to much more complex scenarios and open novel applications to If successful, this may enable automated learning of system design beyond traditional security games and mechanism design.
problems outlined above. We believe

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
All source code used for experiments will be submitted as part of the supplementary material, along with detailed instructions how recreate the experiments presented this paper. Hyperparam- eters used are also listed in the appendix. We plan to release the source code of our experiments under an open-source license upon acceptance.
REFERENCES
Bo An, Milind Tambe, and Arunesh Sinha. Stackelberg security games (SSG) basics and application overview. Improving Homeland Security Decisions, pp. 485, 2017.
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.
Jan Balaguer, Raphael Koster, Christopher Summerfield, and Andrea Tacchetti. The good shepherd: An oracle agent for mechanism design. arXiv preprint arXiv:2202.1013: 2022.
James Bergstra, Daniel Yamins, and David Cox. Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. In International conference machine learning, pp. 115-123. PMLR, 2013.
Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment overcome insecurity, Advances Neural Information Processing Systems, 27, 2014.
Gianluca Brero, Darshan Chakrabarti, Alon Eden, Matthias Gerstgrasser, Vincent Li, and David C. Parkes. Learning Stackelberg equilibria in sequential price mechanisms. In Proc. ICML Workshop for Reinforcement Learning Thheory, 2021a.
Gianluca Brero, Alon Eden, Matthias Gerstgrasser, David Parkes, and Duncan Rheingans- Yoo. Re- inforcement learning of sequential price mechanisms. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 5219-5227, 2021b.
Gianluca Brero, Nicolas Lepore, Eric Mibuari, and David C Parkes. Learning mitigate ai collusion on economic platforms. Advances in Neural Information Processing Systems, 35, 2022.
Yan Duan, John Schulman, Xi Chen, Peter Bartlet, Ilya Sutskever, and Pieter Abbeel. RI 2: Fast reinforcement learning via slow reinforcement learning. arXiv preprint 1eXiv:6611.02779 2016.
Jan Humplik, Alexandre Galashov, Leonard Hasenclever, Pedro A Ortega, Yee Whye Teh, and Nicolas Heess. Meta reinforcement learning as task inference. arXiv preprint 2019.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the opti- mal strategy to commit to. International symposium on algorithmic game theory. pp. 250-262. Springer, 2009.
Zun Li, Feiran Jia, Aditya Mate, Shahin Jabbari, Mithun Chakraborty, Milind Tambe, and Yevgeniy Vorobeychik. Solving structured hierarchical games using differential backward induction. In Uncertainty in Artificial Intelligence, pp. 1107-1117. PMLR, 2022.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph E. Gonzalez, Michael I. Jordan, and lon Stoica. RLlib: Abstractions for distributed reinforcement learning. In International Conference Machine Learning (ICML), 2018.
Baoding Liu. Stackelberg-Nash equilibrium for multilevel programming with multiple followers using genetic algorithms. Computers Mathematics with Applications, 36(7):79-89, 1998.
Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel. A simple neural attentive meta- learner. arXiv preprint arXiv:1707.03144, 2017.
10

---

Under review as a conference paper at ICLR 2023
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 (187540):529-5555 2015.
Tomoya Nakamura. One-leader and multiple-followe Stackelberg games with private information.
Economics Letters, 127:27-30, 2015.
Noam Nisan and Amir Ronen. Algorithmic mechanism design. Proceedings of the thirty-first annual ACM symposium Theory of computing, pp. 129-140, 1999.
Praveen Paruchuri, Jonathan Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, and Sarit Kraus. Playing games for security: An efficient exact algorithm for solving Bayesian Stackel- berg games. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems- Volume pp. 395-902, 2008.
Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 2149-2156, 2019.
Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. Efficient off-policy meta-reinforcemenn learning via probabilistic context variables. In International conference on machine learning. pp. 5331-5340. PMLR, 2019.
David Robinson and David Goforth. The topology of the 2x2 games: a new periodic table, volume 3. Psychology Press, 2005.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning, arXiv preprint arXiv:1703.03864 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Zhenyu Shi. Runsheng Yu, Xinrun Wang, Rundong Wang. Youzhi Zhang, Hanjiang Lai, and Bo An. Learning expensive coordination: An event-based deep rl approach. In International Conference
Learning Representations, 2019.
Tianmin Shu and Yuandong Tian. rl: Mind-aware multi-agent management reinforcement learning, arXiv preprint 1rXXv:1810000144 2018.
Ankur Sinha, Pekka Malo, Anton Frantsev, and Kalyanmoy Deb. Finding optimal strategies multi-period fulli-leader-followerr Stackelberg game using an evolutionary algorithm. Comput- ers & Operations Research, 41:374-385 2014.
Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: Looking beyond decade of success. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), 2018.
Cesar U Solis. Julio Clempner, and Alexander S Poznyak. Modeling multileader-follower non- cooperative Stackelberg games. Cybernetics and Systems, 47(8):650-67) 2016.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Chaitanya Swamy. The effectiveness of Stackelberg strategies and tolls for network congestion games. In SODA, pp. 1133-1142. Citeseer, 2007.
Jane X Wang. Zeb Kurth-Nelson, Dhruva Tirumala. Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. arXiv preprint arXiv: L05663, 2016.
11

---

Under review as a conference paper at ICLR 2023
Kai Wang, Lily Xu, Andrew Perrault, Michael K Reiter, and Milind Tambe. Coordinating followers to reach better equilibria: End-to-end gradient descent for stackelberg games. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 5219-5227, 2022.
Haifeng Xu, Fei Fang, Albert Xin Jiang, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. Computing minimax strategy for discretized spatio-temporal zero-sum security games. In In- ternational Joint Workshop on Optimization in Multi-Agent Systems and Distributed Constraint Reasoning (OPTMASDCR) at AAMAS. Citeseer, 2014.
Jiachen Yang, Ethan Wang, Rakshit Trivedi, Tuo Zhao, and Hongyuan Zha. Adaptive incentive design with multi-agent meta-gradient reinforcement learning. Proceedings of the 21st Inter- national Conference Autonomous Agents and Multiagent Systems, pp. 1436-1445, 2022.
Huaqing Zhang, Yong Xiao, Lin X Cai, Dusit Niyato, Lingyang Song, and Zhu Han. A multi-leader multi-follower Stackelberg game for resource management in LTE unlicensed. IEEE Transactions on Wireless Communications, 16(1):348-361, 2016.
Stephan Zheng. Alexander Trott, Sunil Srinivasa, David C Parkes, and Richard Socher. The AI Economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances, 8( 8(18)xabk2267, 2022.
Han Zhong, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Can reinforcement learning find Stackelberg-Nard -ash equilibria in general-sum markov games with myopic followers? arXiv preprint arXiv:21 2021.
Luisa Zintgraf, Maximilian Igl. Kyriacos Shiarlis, Anuj Mahajan, Katja Hofmann, and Shimon Whiteson. Variational task embeddings for fast adapta-tion in deep reinforcement learning. In International Conference on Learning Representations Workshop (ICLRW), 2019.
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM 1
We include here the proof of Theorem
Theorem 1, Given a Markov Game M and a follower equilibrium oracle &, then:
[General Case] If
1. the leader locally aims to solve single-agent optimization problem L( and
2. for each choice of leader policy n. L computes the follower best-response E(TL),, and
3. ((TL) evaluates the leader policy a against the follower best-response {(LL) in M, i.e. the value of ((TL) is (, (TTL)) in M,
then an optimal solution oi to & together with the follower best-response { form a Stackelberg equilibrium in M.
[Query-Oracle Special Case] Furthermore, if additionally
4. the follower oracle implementation only requires query access to wr, i.e. values n (o) for one more observations E frofrom M, and
5. leader policies a invariant, i.e. acting the same during queries they would in M,
then C can be constructed POMDP.
Proof. We show the proof in two parts, first for the general case, then the query-oracle special case.
[General Case] We first show the general case:
Assume 87, optimally solves L. i.e. (L,2(8),) maxr
By condition 3 the leader's reward in the same that M when the followers play their best- response equilibrium, i.c. rL,c(st)) maxFz.c(TZ) means that sf together with {(TL) form a Stackelberg equilibrium in M. Condition 2 is only required implicitly to ensure that followers playing their best-response equilibrium when the leader strategy T is evaluated in M. This shows the general case.
FL.FLLM(TLL.. (Tz)). This immediately
[Query-Oracle Special Case]
Construction of L: Given a Markov Game M and a follower best-response oracle that only requires query access to the leader strategy n. define leader POMDP L follows:
[initial segment] For an initial number of steps in L, each step performs one query from the follower oracle If a given query wishes to determine the leader policy's 's response to observation o, then the leader will receive as its observation in L, and the leader's action will given to the response to its query. The leader will receive no reward these steps.
[final segment] Once follower equilibrium br has been determined, the remainder of L will be constructed from the original Markov game M: We let followers act according to the computed follower equilibrium Re and treat them (including all their internal state) as part of the environment.
We now show that C is a POMDP.
POMDP, setup: Let the state of L be cquilibrium oracle (in the initial part of the L), the state of the original Markov Game, and the internal state of the follower agents (in the final part of the L). In the initial part wlog assume this is (zg, O, 0), and in the final part (0, 2M,i, ZF.))
(zg, &M,t, 2F,)), the internal state of the follower
POMDP, part 1: By assumption, & only requires query access to TL. i.c. if at timestep t, the oracle's 's internal state is Σg,, and the oracle issues the query o,, then the oracle's next internal state #8,++1 1 function of only zg, and gt, the leader's response the query or By the construction of
13

---

Under review as a conference paper at ICLR 2023
the first part of L, we have that the leader's observation timestep t is precisely the oracle query or, and so it's s's action a gives the oracle response 9t. Together, we get that the L state at time + 1, 2441, is function of only 2, and a,, showing that L is a POMDP in the initial part.
POMDP, part 2: In the final part of C, at step t. the Markov Game state is 2M.t. and leader and follower observations depend only on this state, i.e. O7, (2,)() and of = op; In tum, both the follower actions F,r, as well as the next follower state 2 only depend on OF,, and the current follower state FF. therefore both depend only on Z,Mz and FF... In turn, the next state of M, I, depends on leader and follower actions, and therefore only on leader action, 2,,r and 2 Together. follows that 2141 only depends on 2 and the leader's action oL,e meaning the final part of L is Markovian.
We have therefore shown that L as a whole is a POMDP. We now show that an optimal policy in C forms Stackelberg equilibrium.
Stackelberg: By the assumption that the leader policy is invariant, we have that if x in response to an oracle query, then (o) = in the Markov Game . as well. Therefore, the follower equilibrium Tт computed by the oracle at the end of the initial part of C is a best-response
equilibrium to the strategy the leader plays in M in the final part of L.
Now, by construction of L, the leader reward given any TT. in L is the same as the leader reward in M when followers play FF. and by the above TF is indeed a best-response equilibrium, i.e. (TT) = ML.M (TL, FF) = (TL, (TTL)). Finally, by optimality of पं in L, тŹ E argmax(rz.c and therefore म argmax(F L. ( LT ((T)))). But this precisely means that म.. and (TT). form a Stackelberg equilibrium in M.
B THEOREM T LEADER MEMORY AND LEADER INVARIANCE
Leader Memory. We state the query-oracle case of Theorem for memory-less leader policies, i.c. leader policies that map directly from observations to actions. This is without loss of generality because for leader policies that use memory we may take the view that the leader policy operates on belief states, mapping belief state to action. In this view, the theorem applies as-is, and we query the leader policy on belief states. This would work well, for instance, if leader memory was implemented through sufficient statistic. Alternatively, if we want to treat memory intrinsic to the leader policy, queries become sequences of observations. In this view, the proof applies mutatis mutandis. The main technicality in this case is to reset internal state of the leader policy between queries, so that queries are well-defined. This is also important in order to ensure the leader invariance conditions (an unrestricted LSTM could easily allow leader to distinguish queries from real game).
Leader Invariance. It may be possible to give the leader policy memory beyond the two cases above, i.c. memory with state that carries through between follower oracle queries and/or to real play. In any such cases, it is necessary that the leader policy be invariant, meaning it is acting the same during the initial segment (i.e. oracle queries) and the final segment (i.e. original game) of the constructed leader POMDP L. This has not been stated explicitly in previous works, but is a critical part of ensuring convergence to the correct equilibrium. If the leader policy were to act differently during the oracle queries, it could "trick" followers into suboptimal behavior that gives the leader better reward but is not best-response, and thus not Stackelberg equilibrium. For instance, in an iterated prisoners dilemma, a leader could pretend to be playing tit-for-tat during oracle queries, leading followers cooperate; and could then defect during the actual game. We show this experimentally in Appendix C22 Invariance is easily ensured if the leader policy cannot distinguish queries and real play, which is generally true for memory-less policies. Alternatively the leader policy could be explicitly constrained to be invariant, e.g. through an appropriate loss term.
C LIMITATIONS OF THEOREM I
We now present experimental evidence of the limitations of our main Theorem. In particular, we will show that violating any of the conditions of the theorem can lead to learning failure.
14

---

Under review as a conference paper at ICLR 2023
Algorithm PG
Algoritim ES
0.0
-122
Performnnc
-1.3
Queries
-1.0
Otserved
Hidden
1.5
-1.6
-2.0
-1.7
250
500
750
1000
1250
0
50
100
150
200
250
Step
Step
Figure 3: Performance of contextual-policc approach with hidden and rolled-out oracle queries in iterated prisoners dilemma.
C.1 NON-POMDP
An interesting question we asked carlier is whether rolling out the follower queries into the leader episode to form POMDP is strictly necessary. In the next section will present proof that this is the case, but we also show this experimentally here. Figure]]shows the performance of our approach on slightly modified iterated prisoner's dilemma (see Appendix D for full payoff matrices). We show our standard setting where queries are part of the leader episode, as well as a setting where they are hidden from the leader. The hidden-queries setting fails learn sensible behavior. This is consistent across learning rates, and across algorithms. Note however that this only applies to RL algorithms. An approach that operates directly on the policy space such as Evolutionary Strategies is still able to learn successfully, as shown on the right hand side of Figure
C.2 NON-INVARIANT LEADER
We also experimentally illustrate the leader in- variance condition Theorem[[in the iterated prisoner's dilemma setting. For simplicity, we emulate memory for the leader policy by con- catenating binary variable to its observation, set to during the first five steps of each episode (the queries), and afterwards As be
0.0
Memory
Perforaance
True
False
-1.0
Leaming Rate
seen in Figure 4. when given access to this ad- ditional variable, the leader gains significantly higher reward. The leader policy effectively learns act if it was playing tit-for-tat dur- ing the queries, thereby inducing the follower to respond by cooperating; the leader then always defects during the actual game, thereby achiev- ing maximum reward. This is not Stackelberg equilibrium.
-1.5
0.004
0.008
2.0 1000
0.015
0
2000
0.03
Step
Figure 4: Leader reward with invariant and non- invariant policies in iterated prisoners dilemma.
C.3 LEADER REWARD DURING FOLLOWER LEARNING
One condition of Theorem is that the leader only be evaluated against followers who are best- responding. the follower oracle implemented using learning dynamics observable to the leader, this means that the leader must not receive reward during this learning phase. If leader did receive reward, this could give the leader the wrong optimization target. Imagine for instance a setting where the leader has one strategy choice corresponding quickly-learnable follower best-response strategy that gives medium reward to the leader, and another leader strategy choice corresponding
A neural network could learn to extract the same discriminator from step counter, and recurrent network could casily learn keep such counter.
15

---

Under review as a conference paper at ICLR 2023
matrix - [[[2. 0.0001 o). [[0. [1. 211)
matrix IT2. 0.001]. [-5. оμ), (1-5, 0). (1. 2111
2.0
1.8
1.8
Reward During
Follower Learning
144
False
True
5000
10000
15000
20000
0
5000
10000
15000
20000
0mestaps_ total
tmesteps_tooe
Figure 5: Leader performance with and without reward during follower Q-learning. Clearly the leader fails learn the sole Stackelberg equilibrium (reward 2.0) if reward given during follower learning. Plots show reward during actual play only, i.e. without reward during follower Q-learning, as this the relevant quantity for Stackelberg equilibria.
to slow-to-lcarn follower strategy with high leader reward. We can casily simulate this using a slightly modified version of the "Battle of the Sexes" single-shot matrix game we used as an example in the introduction. In this, modify the follower reward that the leader-preferred option gives the follower very little reward. We then couple this with carefully chosen (but entirely reasonable) Q-learning hyperparameters for the follower. As result, leader who receives reward during the follower learning phase is not able to reliable learn the correct equilibrium anymore, even in such simple game, as Figure shows. we further modify the game penalize the leader for coordination failure, this can even lead to the leader consistently learning the wrong coordination choice, as the right-hand plot shows.
Notice however that this (reward throughout follower learning) is also valid target to optimize for, where the leader aims to optimize its expected return taking into account that followers may need some time to adjust to the leader's behavior. In the case of Balaguer et al. (2022) this is the intent, especially with regards to designing mechanisms for human participants as followers.
C.4 CONTINUOUS FOLLOWER LEARNING
Finally, virtually all previous approaches in the literature use some sort of learning dynamics to implement the follower oracle. A tempt- ing way of improving learning speed in such paradigm would be to retain follower poli- cies between leader updates. That is, if at the end of the leader learning iteration t, the fol-
2.00
1.75
Perfomecce
1.50
Follwer Leaming
Reset
1.28
Oniging
Learrnng Rate
1.00
0.008
lower is best responding using strategy pol- icy parameters Ót,end, then instead of initial- izing follower weights 1, randomly, set 0141,star dr..nnd- Under the assumption that the leader policy only changed a little, and the conjecture that therefore the optimal follower policy only changed a little, this should allow follower learning start from very near the op- timum, and thus hopefully require much short inner (follower learning) loops. However, this has some drawbacks. For one, it makes the leader learning problem non-stationary. Beyond this, it can lead to learning failure, if both leader and follower get stuck local optimum. Figure D shows this in practice the "Battle of the Sexes" example, where non-resetting follower learning can lead to convergence to the follower-preferred choice rather than the Stackelberg equilibrium.
0.03
Stop
Figure 6: Leader reward with Q-learning fol- lower on Battle of the Sexes, where the follower initializes blank Q-table each episode (blue) or keeps their previous Q-table (orange).
16

---

Under review as a conference paper at ICLR 2023
D PROOF OF NON-POMDP DIVERGENCE
We now present a theorem that shows that the query-oracle special case is meaningful. A priori it is not clear that the query-oracle POMDP construction is strictly necessary, or if standard RL algorithm could also learn without it. Without the POMDP construction, the leader would effectively always play against followers who immediately best respond. The following theorem shows that this cannot work.
Theorem 2. There exists a Stochastic Markov Game M where neither tabular Q-learning nor policy gradient can learn the optimal policy for the leader, if the follower agent always best-responds (without the construction of the query- special case of Theorem
Proof. We consider slight variation of the iterated prisoner's dilemma discussed in the main text.
Consider payoff matrices L (-1 -1 -3
0 -2 and F
(-1 0
3 -2) denoting the payoff to the leader
and follower agent respectively. The leader chooses the row, the first row denoting "cooperate" or C and the second row "defect" or D, and similarly the follower chooses the column. Notice that these are the standard prisoner's dilemma payoff matrices, except the top and bottom row for the leader have been switched.
Let each agent's observation space be a one-step memory of the other agent's previous action, that is, there are three possible observations On, og and on. At the first step of each episode, both agents observe Op- If at step / the leader cooperates and the follower defects, then at step I. + 1, the leader observes op ("other agent defected") and the follower observes oc ("other agent cooperated"). We also write SCD for this state if we want to refer to both agents. In particular SCD corresponds to leader reward -2 for the leader and for the follower (top right corner of both matrices). This is simplification of the setting presented in the main text, but without loss of generality in the case of iterated prisoner's dilemma, and also defines valid stochastic Markov game in its own right. Let us define an episode of our SMG to be h iterations of the matrix game, where h denotes the horizon or episode length of the game, As a preliminary, notice that for any leader policy, the follower best-response is always deterministic. This is easy to check.
is also easy to see that the optimal leader policy is to cooperate on the first step, and to then play tit-for-tat. That is, if the follower cooperated, the leader cooperates in the following step. If the follower defects, the leader defects in return. If the leader plays this policy, then the follower will in turn always cooperate, leading to leader episode reward O, clearly the optimum. Using the construction in the query-oracle special case of Theorem[] [[] this optimal leader policy can be learned using standard RL algorithms. What we will now show that if the follower best-responds without that construction, i.e. immediately without queries folded into the leader sample batch, then standard RL algorithms will diverge. This is independent of choice of hyperparameters, but matter of principle.
Intuitively, the problem is one of a missing counterfactual: Notice that for the leader tit-for-tat Stackelberg equilibrium, it is essential that the leader commits to defecting if the follower defects. But notice also that when the leader plays this fit-for-tat policy. the follower will always best respond, and so the leader will never actually see follower defection. But this also means that it cannot accumulate gradient for this hypothetical behavior.
We now make this formal. Consider first the case of (tabular) Q-learning. Let q(s, a) be the (leader's) ss) Q-value of taking action a in state s. We let a denote the learning rate and y the discount factor. Given experience (s, a, s')) s') we update Q-values as follows:
q(8,a) a)
(1-a) g(8, a) + a. (r max g(s',.)
As convenient shorthand and as a slight abuse of notation, we will define 0 as follows:
0_ = 0 if g(s D) S g(s, C) if q(s. D) C(
In words, we let 9₂ denote that the current leader policy given the q(s, a) values will defect in state s, and 0 if the leader will cooperate in state s. We can then write 0 = (fn. fc, fn) for the entire leader policy induced by the current Q-table. 0 (0, O, 0) would denote leader policy that always
17

---

Under review as a conference paper at ICLR 2023
cooperates, 8 11, 1) denotes leader always defecting, and 0 (0, denotes the (optimal) tit-for-tat strategy.
Now consider the case of tabular Q-learning with parameter noise exploration. In this, we collect experiences from any of the eight possible deterministic leader policies. Note also that the leader action on the initial step does not affect the follower's best response strategy; and it does not influ- ence Q-table updates for the non-initial observations oc, OD (because Oo will never be revisited and so the reward generated from og can never appear in a Q-table update or indeed in a reward-to-go calculation in a policy gradient algorithm). We can therefore disregard the leader's initial action and for brevity focus only on the four cases 9 (+, 0, 0), 0 (+, 0. 1). 0 (+, 1,0) and 0 (+, 1, 1). It is easy to see that for 0 (+, O, 1) the follower best-response is to always cooperate, and for the other three cases it is to always defect. We may therefore encounter experiences of the following form:
0 = (4,0,0) 0)
(oD, -22,0p)
0 = ())
(oc, C, oc)
0 = 1,,
(op; C, -2,0pp)
0 (+, 1,1)
(OD, D, -p)
It is easy to see that under usual Q-learning update rules and for any choice of learning rate, we will have that in the limit g(oD, C)- = -2- (lines 1, 3) and g(oD, D) = -3-g (line 4) where g == 1-7"/a 4/2 is term from the discount factor y. Crucially we have that g(oD; C) > gioD, D), and therefore the policy will converge toward = (+, *, 0), which not optimal. This holds for any choice of learning rate, discount factor and exploration parameters (as any mix of the above trajectories will lead to this).
1-y
For the e-greedy case, let 05 = 0. + (-1)) That is, if our current Q-table induces the deterministic policy 8 then 6% gives the probability of choosing action D in state in the e-greddy case. It is easy to see that for sufficiently small and 0: = (+, 1 c) the follower best-response is still to always cooperate, and for any other 0% the follower best-response is to always defect. Therefore in particular, no matter which way particular leader action is sampled, the follower will best-respond in the same way (only depending on the leader policy as a whole, not the particular leader action sampled). In turn this means that q(op. C') can only continue to accumulate -2 terms, and q(OD, D) can only continue to accumulate -3 terms, and the policy will converge toward 0 = (x, *, 0), which is not optimal.
To show this for policy gradient, let the leader policy be parametrized by theta as above, i.e. let 6 be the probability that the leader policy defects given observation o, and 6, the probability that the leader cooperates given Recall the basic REINFORCE gradient update rule:
t- f + aG. no(a,
Here G, denotes the (discounted) "reward to go", i.e. G. rz + + 7 as usual. A very similar argument as in the Q-learning case now holds to show that the reward-to-go from cooperat- ing when observing oD will always be larger in expectation than the reward-to-go from defecting, because Tt when defecting is smaller than 73 when cooperating given oD and the remainder of the sum in G is the same in expectation. This in turn pushes gradients toward cooperation, and away from the optimal tit-for-tat policy.
The above holds for tabular Q-learning and basic policy-gradicne with direct parametrization, but likely can be extended to further RI. algorithms such as DQN or actor-critic.
Notice the key difference the query-oracle POMDP construction: In this, the oracle must query the leader policy for its action given op at least once in the initial "oracle" segment of the episode. That action therefore sees as its reward to go the reward from the entire final segment, i.c. the entire episode reward of the original Markov game. Intuitively, the leader gets to see at least one experience where it retaliates on a follower defection and this leading to an entire episode of cooperation and good rewards. Without the oracle query, the leader never gets to this, and cannot learn from it. It may still see experiences where it retaliates for defection, but these will be from within the actual episode, will not influence follower behavior, and will lead strictly worse rewards than
18

---

Under review as a conference paper at ICLR 2023
cooperating. Finally, it is also clear that this only applies to typical RL algorithms that learn taking actions in individual steps. Approaches that learn on the policy space as a whole, such as evolutionary strategies, are not affected by this (as indeed they never look at individual steps and actions at all).
E NECESSARY CONDITIONS FOR STACKELBERG CONVERGENCE
may also be interesting to consider the inverse direction of Theorem T i.e. what are necessary conditions that follow from Stackelberg convergence. The resulting theorem is not very strong, but still informative, as it suggests avenues for future research. Recall that in Theorem we map a Markov game to single-agent RL problem (POMDP) for the leader. In the general simply taking the leader's 's view the original Markov game as-is, and in the query-orack special construct POMDP that incorporates oracle queries. We then show that a solution to the leader's POMDP together with the follower best-response forms a Stackelberg Equilibrium.
this is
Consider now the reverse: Suppose we are given some mapping from Markov game to leader POMDP, and a guarantee that no matter the original Markov game, an optimal solution to the leader POMDP it maps forms part of Stackelberg equilibrium. What needs to be true of any such map- ping? We formulate this here in a slightly more general manner, in that we also allow an additional (not necessarily identity) mapping between leader policies the Markov game and the POMDP.
Theorem 3 (Necessity). Suppose we are given mappings L M:My L(M) and I - M L maps any Markov Game M to a single-agent RL problem, and I maps policies in L to policies in M. Furthermore suppose that whenever policy LL, optimally solves L(M), then (TI,CC) together with E ((((),c)) are Stackelberg equilibrium in M. Then the following two conditions must be true of C and l.
1.
The leader reward in is maximized by the same choice of strategy as the leader reward in M when followers play {(TL.,, i.e.
I( ((rgg max maxrL,c(TL)) S arg Mag
2. C implements a follower equilibrium oracle {(TL)
Proof (Sketch). The first condition immediately follows from the problem statement. For the second condition, consider that given full freedom in choosing M, we can construct M so as to let be any arbitrary function from leader follower policy space. Similarly, is any arbitrary function. Both of these follow from cardinality arguments, and the observation that since Markov games may be partially observable are essentially unrestricted in the complexity of the Markov game we choose to construct even for small strategy spaces. Since by the first condition L. needs to compute E, both of which can be arbitrary, it thus also needs compute E.
choose M so that r
The main difference to the conditions in Theorem I is that we can only show that the argmax of leader reward needs to be that of the original Markov game, not that the rewards need to be identical. This is in way trivial (of course Theorem [ still holds if we scaled leader rewards in the leader learning problem by a constant factor), but it also suggests that reward shaping may be a viable technique to accelerate leader learning, potentially still with provable Stackelberg equilibrium guarantees.
F FURTHER EXPERIMENT DETAILS: ITERATED MATRIX GAMES
Environments We use the 12 canonical symmetric matrix games identified in Robinson Goforth (005) and also used by Balaguer et al. (2022). We construct Markov games from these matrices by concatenating multiple iterations into an episode, and giving both agents one-step memory of both agents' action in the previous step. We use matrices for all the Markoy games, reported on the same scale as the figures. During training, we scale rewards to be centered O. i.e. taking values -1.5. -0.5, 0.5, 1.5, but report results offset to match the reward scales used by Balaguer et al. (2022). This has no effect on comparability of results.
10 steps per episode. Table H shows the payoff
19

---

Under review as a conference paper at ICLR 2023
Algorithm. We focus on the contextual policy meta-learning approach described in subsection for followers, and standard RL for the leader: At the beginning of each episode, the leader is queried (as part of the episode rollout) for its action in each possible state of the environment. Its responses are then concatenated to the follower observation. In pre-training phase, we train the follower against randomly sampled leader policies. In the main training phase, we then train the leader against the follower meta-policy. Algorithm [ in the Appendix details this in pseudo-code. An advantage of the generality of our framework that it agnostic to which specific RL algorithm is used. We generally use a standard policy gradient (PG) algorithm for the followers, although our results do not depend on this specific choice.
Algorithm details the two-phase learning algorithm we use. In all the experiments shown in the main text, we use policy gradient to train the follower meta-policy in the pre-training loop. We use PG (Sutton et al. 1999). PPO (Schulman et al. 2017) and DQN (Mnih et al.. 2013 2015) in the main training loop, as indicated in the respective figures. We use linear models, and disable exploration in the leader policy while pre-training the follower and vice versa. Table H lists the hyperparameters used for each of these algorithms. Any hyperparameters not listed were left at default values rllib version 2.0.0. All experiments were run with single rollout worker (per experiment), and using Torch.
Equilibrium Verification. At the end of every experiment, we freeze the leader policy and further train the follower policy for n = 50 iterations. Unlike in the pre-training phase, we here train them only against the specific leader policy trained the main training loop. This to further verify that the policies indeed form Stackelberg equilibrium, and in particular that the follower meta-policy is best-responding to the trained leader. If this is the case, we should not see any change in leader or follower performance in this post-training phase. If the follower meta-polics responding to the leader, we may see an increase in follower performance during this post-training phase. In all of the experiments in this paper (except the ones designed to show failure modes) see no follower improvement, i.e. behavior consistent with a Stackelberg equilibrium. This is not shown in the training curves in the figures, but can be reproduced from the source code.
not already best-
Implementation and Environment. All experiments were implemented using Ray / RLlib 2.0.0 (Liang et al. 2018). Experiments were run on recent Intel Xeon processors with a single core and 2GB RAM per experiment.
Hyperparameter Tuning. Learning rates and batch sizes were tuned using grid search, with some additional tuning using the HyperOpt Python package (Bergstra et al., (013). yielding no further improvement however.
G FURTHER EXPERIMENT DETAILS: ATARI 2600
Environment. We modify the Atari 2600 game "Space Invaders". We read from emulator RAM to detect when a shot has been fired, and by which player. Separately in a Python wrapper we keep count of how many shots each player has available. We decrement this whenever we detect that the player fired a shot. If the Python variable keeping track the available bullets reaches zero, we overwrite the player action that is fed to the Atari emulator not-firing. Both players start with zero available bullets, but we increment the bullets available to player 1 at stochastic intervals for up to a total of five times per episode.
We implement a bilateral trade between agents: The selling agent may offer a price, and the buying agent may choose accept this price.
Neural Network Architecture. This is implemented by augmenting both action and observation space, both providing a dictionary of both the underlying Atari action/observation, as well as the new economic action and observations.
The action space contains the original Atari action, as well as the trading action. For the seller, the trading action is picking
of several discrete price points, where choice = 5 price points ranging from 0 to 1 in 0.25-step increments. For the buyer, instead of giving a discrete buy don't '- buy action, we let the buyer policy maximum price is willing to buy If the offered sales
20

---

Under review as a conference paper at ICLR 2023
1x32
FC
Econ Input
Action
Out
Image
Input
Joint Logits
CNN
2x256 FC
Concat
Figure 7: Neural Network Architecture used in the Atari 2600 bilateral trade experiments.
price is below the maximum buying price of the buyer, the trade happens, and the price paid that set by the selling agent. It is easy to see that this is equivalent to letting the buying agent observe the price offer and respond with acceptance or rejection. We chose this implementation implementing the follower oracle easier when the buyer is Stackelberg leader, but it does not affect the outcome.
makes
In the observation space, we provide Dictionary to each agents containing both the original Atari 2600 image observation, as well as all the relevant economic information (number of bullets the agent currently has available, if applicable price offered by the other agent, whether a trade is current being proposed).
the neural network, we run these economic features through a separate fully connected layer, which feeds into joint logits layer. The Atari input is run through default RLlib CNN and fully connected layers. Figure shows this neural network architecture as a diagram.
Algorithm. We use standard PPO for both the leader and follower. Hyperparameters from RLlib tuned examples and are listed at the end of Table H For convenience, we initialize weights of the CNN and default RLlib FC layers unmodified game. This speeds up training, but is not strictly necessary. We utilize the same Meta- RL approach we do in the iterated matrix game experiments: We first train a meta-follower. In this phase, we let the gameplay actions of the leader agent be controlled by an agent trained on the unmodified game, but we randomize the leader's economic actions. Once this meta-follower training has finished, we train the leader. In this phase, the meta-follower weights are frozen, and only the leader policy is trained. In the Atari experiments, we let the meta-follower query the leader immediately before each trade rather than at the start of the episode, this allows us to fold the queries into the trading exchange.
taken
weights obtained from training agents in the
H FURTHER DETAILS ON PERFORMANCE COMPARISONS
Figure we compare our Meta-RL approach with the PPO+Q-learn approach of Brero et al. 2022 and the ES-MD approach of Balaguer al. (2022).
For Brero et al, (2021a), we implement follower Q-learning using information therein. Hyperparam- eters for both the leader and the follower were tuned using the HyperOpt package (Bergstra et al. 2013). In Figure we plot learning curves up to 200k timesteps, as our approach converges before that point. We show in Figure 8 learning curves until 2M timesteps. We PPO+Q-learn eventually converges to the optimum, while in the majority of cases this still has not happened by 2M timesteps.
that in some cases
For Balaguer et al. (202)), we estimate their performance from Figure 2 therein. Notice that that figure is not a learning curve, but represents single inner loop at the end of their training procedure.
21

---

Under review as a conference paper at ICLR 2023
batle
chicken
Pertima
1.0
1.5
2.0
0/
0.5
1.0
2.0
harmoryy
Perfommrnc
-1.0
-1.5
-0.
-20
-1.0
Aigantim
tee
1e5
Te6
PRO RL.
0.0
eny hero
env mixedhamony
en nocontic et
cot ESAID"
#PONG-LLam
-05
-1.0
-1.5
0.0
1.0
155
20
0.0
0.5
1.0
20
0.0
0.5
1.0
15
2.0
disemm
-.28
-1.00
tmenteps__oo 2018
165
tmwdteps_tot Jotal
tmesteps__ong Jobi
166
Figure 8: Performance on symmetric matrix games (see Figure T up to 2M timesteps.
In the ES-MD case, Balaguer et al. 2022 report their performance after 1.28 billion environment
steps. In the Diff-MD case, comparison of sample complexity difficult, as that approach uses description of the environment rather than sample access. The closest we can come a like-for- like comparison is noting that Balaguer et al. (2022) report performance for Diff-MD after 500k computed expected episode returns with 10-step episodes. In some sense this could be seen to be equivalent to 5M environment steps as lower bound.
22

---

Under review as a conference paper at ICLR 2023
Algorithm Contextual Policy
Pre-Training Loop
Initialize follower policy TF for each pre-training iteration for each episode per sample batch do Sample random leader policy TÝ. for each or Oz do
Query σ for (o1. end for Set context = (or),, or E Or
for each episode step do
Return o7, to leader, (w: op:)) to follower
Step environment using OL. x (OL), apf [T(WW. OF.) end for end for Update follower policy Fr using collected sample batch using PG/PPO/DQN end for
Main Training Loop
Initialize leader policy TT for each training iteration do for each episode per sample batch do for each or. Or, do
Query n. for (or. end for
Set context w (or)), or Or
for each episode step do
Return oL. to leader, (w, or,;) to follower
Step environment using ar, = xI (ot), aF.: oF(w, OF.) end for end for Update leader policy Ty using collected sample batch using PG/PPO/DQN end for
23

---

Under review as a conference paper at ICLR 2023
Table Payoff Matrices used in the matrix-game experiments
Iterated Matrix Games (Figure I etc.)
Name
Leader Payoff
Follower Payoff
-3
prisoners dilemma
0
-2
3
-2)
0
-3
0
-1
stag hunt
-1
-2)
-3 -2
0 -3
-2
assurance
-2 -1
-3 -1
0 -2
-3
coordination
3 -1
- -1
0 -1
-3
mixedharmony
3 -2
-1 -2
0 -1
-2
harmony
-2 33
-1 -3)
0 -2
-1
noconflict
-1 -3
-2 -3
-2 -3
0
deadlock
0 -1
3 -1
-3 -2
prisoners delight
0 -1
-1
-3 -1
3 0
hero
0 -2
-2
-2 -1
0
battle
0 3
-3
2 3
chicken
0
-3
Single-Shot Matrix Game (Appendix
2
0
( 2
battle of the sexes
0
1
Modified Prisoner's Dilemma (Theorem 2)
0
prisoners dilemma modified
-1
33
-2
24

---

Under review as a conference paper at ICLR 2023
Table 4: Hyper-Parameter Parameter Configuration Table
Follower Policy Gradient
Hyper-Parameter
Value
Hyper-Parameter
Value
algorithm
PG
rollout fragment length
100
Ir
0.02
train_ bain_batch_size
100
iterations
500
batch_mode
complete_episodes
Leader Policy Gradient
Hyper-Parameter
Value
Hyper-Parameter
Value
algorithm Ir
PG
rollout Tragment.leggt
100
0.156
train bateh_size
100
iterations
1200
batch mode
complete epiisodes
Leader PPO
Hyper-Parameter algorithm Ir
Value
Hyper-Parameter
Value
PPO
rollout_ frant.fffggtte.engllll
1000
0.008
train batch size
1000
entropy coeff iterations
0.0
sgd minibatch size
1000
500
batch_mode
complete_episodes
Leader DQN
Hyper-Parameter algorithm Ir
Value
Hlpee-Paraameter
Value
SimpleQ
rollout fraoou..ragmmettlengee
10
0.001
train batcbbatchiize
1024
learning_stare
5000
exploration_type
ParameterNoise
exploration initial stddev
1.0
exploration random timesteps batch mode
0
iterations
20000
complete episodes
Atari PPO
Papee-Parreeter
Value
Plyper-Parameter
Value
rrin_batch_sizz
5000
follout.ragmeentlengg
100
sgd wwwimatch.siiiiii
100
num-sgd.img
10
lambda
0.95
kl clooeff
0.5
clip hip_param entropy coeff
0.1
vf clip pparam clippppram
10.0
0.01
Ir
0.001
Hom_rollout_worken
10
num_envs.per_wworee
5
25


Reviews:
[{"review_id": "lonVPwAFSg", "reviewer": "Reviewer_3yUN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper deals with the question of learning Stackelberg equilibria -- games with a leader-follower structure -- an important topic with many relevant applications. The main contribution is to show that, given access to a best-response oracle for the follower, this problem can be reduced to learning in a POMDP consisting of two phases. In some simple games, the authors then implement this reduction experimentally. A crucial requirement is that in the first phase of the POMDP, the leader does not adapt their policy; the authors also experimentally test this point.", "summary_of_the_review": "I recommend weak acceptance simply because in the end, I was glad to read this paper and think it is a positive contribution to the community.\n\nUpdate after reading author's rebuttal: due to the presence of new experiments (and clarification of comparison to previous methods) which are indeed more convincing, I've increased my score.", "strength_and_weaknesses": "Strengths: The paper presents a very clear paradigm which unifies many existing approaches. This is an important topic, as shown by the cited prior work that involves using RL-style approaches in Stackelberg games, but much prior work has somehow lacked the clarity of perspective which this paper provides.\n\nWeaknesses: the main theorem is not very exciting in some sense. And the experiments are not particularly impressive (they mainly look at very toy matrix games, when there are many more interesting problems that in principle can be described by this framework).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WvHPyX_F6Y", "reviewer": "Reviewer_671a", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies Stackelberg equilibria and presents a general framework for implementing Stackelberg equilibria search as a multi-agent RL problem, which encapsulates both previous approaches and some new design spaces such as contextual policies. Some numerical experiments are also provided.", "summary_of_the_review": "Given the comments above, I think the paper is not qualified for publication in ICLR due to the drawbacks in both writing quality and solidity of the results.", "strength_and_weaknesses": "Strengths:\n* Propose a general framework for implementing Stackelberg equilibria search as a multi-agent RL problem.\n* Numerical experiments are provided to demonstrate the usefulness of the proposed framework.\n\nWeaknesses:\n* The notation is confusing and inconsistent. For example, in Definition 2, it is unclear how these notation are related to the Markov Game notation in the previous page. Also, it seems that the authors are confusing strategies $s$ with actions $a$. In particular, if ${\\bf s}_F$ is the follower strategies, then what is ${\\bf a}_F$? Similarly, if $s_L$ is the leader strategy, then what are $s_t$ and $a_L$?\n* Theorem 1 is either trivial or very hard to follow, making the claim about a general framework for implementing Stackelberg equilibria search as a multi-agent RL problem unconvincing. The general case seems to be a simple restatement of the problem formulation, and the proof in the appendix also seems to suggest this. The special case is hard to understand. and also $s_L(o)$ and $\\mathcal{O}_L$ are undefined. The authors should try to make these statements and proofs more formal, instead of using informal statements like \"acting the same during queries as they would in $\\mathcal{M}$\". \n* The authors seem to only compare with Balaguer et al. (2022) as the benchmark. However, there are tons of Stackelberg RL algorithms that the authors fail to compare with. See [A, B] for example.\n\n[A] Tianmin Shu and Yuandong Tian. M3RL: Mind-aware multi-agent management reinforcement learning. In ICLR, 2019.\n\n[B] Runsheng Yu, Xinrun Wang, Youzhi Zhang, Rundong Wang, Bo An, ZhenYu Shi, and Hanjiang Lai. Learning expensive coordination: An event-based deep RL approach. In ICLR, 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GiG226BrpK0", "reviewer": "Reviewer_RZA6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper combines recent multi-agent RL approaches for finding stackelberg equilibria into one framework, with conditions on convergence. Also, ideas from meta-RL are used to improve the follower. \n", "summary_of_the_review": "Overall, I think this paper needs a bit more work, with better theory that proves existing methods won't work, with extensive experiments. ", "strength_and_weaknesses": "This paper provides a nice overview of the existing literature for solving sequential Stackelberg games. I especially like table 2. I think that a version of this paper that does a better job experimentally comparing against all the existing approaches and with better theory characterizing when one would expect approaches to not work could be useful to the community. \nHowever, as it currently is, the theory seems to give a result that is already known, the experiments do not sufficiently compare across all the baselines, and the novel algorithmic contribution does not have good enough experiments to back it up.\n\nThe experiments should be a lot more extensive and compare against all the related works shown in the table\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6hS1Aowd1MF", "reviewer": "Reviewer_FBtF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a framework for convergence to Stackelberg equilibria in multi-agent RL. The main contribution of the paper can be summarised by Theorem 1 in the paper. Theorem 1 states 3 conditions for convergence so that the solutions for the leader and the follower form a Stackelberg equilibrium. Additionally, 2 more conditions are stated that are required to consider the problem of the leader as a POMDP. Finally, the authors experimentally evaluate when Theorem 1 holds in several matrix games and scenarios.", "summary_of_the_review": "I recommend a weak reject for this paper. I do not feel that it significantly alters our understanding of Stackelberg equilibria. Additionally, I believe that ICLR is not a suitable venue for this paper. I would expect higher dimensional experiments.\nMy ranking reflects my current understanding of the paper. I would be happy to change my score if the authors satisfactorily refute my main points of criticism.", "strength_and_weaknesses": "Strengths:\n- The paper is clearly written, and the concepts are nicely described.\n- The background information is described concisely.\n\n------------------------------------------------------------\nWeaknesses\n\n- Page 2, last paragraph: \"We focus here mainly on this memory-less case.\" Why do you only consider memory-less cases?\n- Page 3, first line: \"total reward\" ---> this should be \"total return\"\n- The paper is heavily based on three works of Brero et al, which however only one of those is published in an archival venue.\n\n- I would recommend including the payoff matrices of the games in the appendix.\n\n- Page 6, 3rd paragraph: Could you please elaborate more on this sentence: \"The leader should receive reward only when followers are playing their best-response equilibrium, and the entire follower learning process should be one episode for the leader.\" Why do we need such a constraint? \n\n- There are small typos and incorrect use of articles in the paper, which, however, do not make the paper hard to read. For example, on page 8 in the last paragraph: alllow ---> allow\n\n- I would like to see the baselines of Balaguer et al. (2022) included in Figures 1 and 2. Otherwise, the reader has to go to the paper of Balaguer et al. (2022) to see the achieved returns of the baselines.\n\n- I feel that ICLR is not a suitable venue for this paper. ICLR, as its name indicates, focuses on learning representations, and I do not see how this paper fits in this scope. I think conferences such as AAMAS/AAAI/IJCAI/ICML/NeurIPS/COLT are more suitable for this paper.\n\n- Why are the matrix games POMDPs?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject