Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of multi-agent Markov games with one leader and multiple followers. Moreover, the games considered are controlled by the leader, meaning that the transition function only depends on the action of the leader. The goal is to find the Stackelberg-Nash equilibrium of the game by means of reinforcement learning-based algorithms, both for the offline and online setting. The algorithms proposed have guarantees in terms of regret which is sub-linear in the number of episodes for the online setting and converges to zero in the offline setting in the size of the dataset.
main_review: The paper seems to consider the interesting problem of computing SNE for linear MDPS, which seems to be a novel problem. The technical level of the paper seems to be of high quality. However, the structure of the paper would benefit from some adjustments. In particular, the related work section is of paramount importance in this work, as it is not obvious how much of the presented work is already in the literature. I would suggest moving the related works section to the main paper. Also, the algorithms presented in the paper are hard to follow: it is hard to understand the meaning of instantiating a function.

The main idea of the work is not well transmitted. Since the case of H=1 is already solved in the literature, does your method just recursively use such oracle recursively on a game with optimistic estimates? What is the main difficulty of computing such equilibrium, w.r.t. the case H=1?

The paper would greatly benefit from an empirical evaluation of the algorithm. As a benchmark, I think you could employ a solver of normal form Stackelberg games on the normal form formulation of the sequential game. This could be done in small games. Since such analysis is expected a motivation on why it is missing would be welcomed. The related work section of the work misses a work that the reviewer is familiar with, namely: Balcan et al. "Commitment Without Regrets: Online Learning in Stackelberg Security Games" (2015). In that case, the horizon is H=1 and there are no externalities (the best response to the leader is a joint NE for the followers). However, the paper underlines that the problem poses many difficult features, such as non-convexity, and non-continuity of the payoffs, and, hence, a careful analysis of the strategy space is needed. In this work, such specific analysis seems missing. A discussion around this topic is hence welcomed.

summary_of_the_review: The paper would benefit from more discussion on the related works and analysis similar to the one presented in the work by Balcan (2015).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper investigates leader-controlled multi-player general-sum games in the episodic setting. Based on optimistic and pessimistic LSVI, the paper proposes algorithms that achieve sublinear regret in the online and offline setting, respectively. 
main_review: The paper requires a considerable revision and re-organization. There are many details and remarks, but the setting, the challenges and the proposed solutions are unclear.

- First of all, the notion of linear function approximation is unclear. In Algorithm 1 (Line 10) and Algorithm 3 (Line 9), it is seen that the algorithm keeps and updates the value function for each state $x\in\mathcal{S}$ in an $|\mathcal{S}|$-dimensional array. We observe the same thing for the policies also, i.e., Line 8 in Algorithm 3 indicates that policies are kept for all $x\in\mathcal{S}$. This looks tabular, and for large state spaces, it is intractable. If there is an underlying parameterization, then storing and updating policies and value functions at each iteration is inefficient, the algorithms should indicate that only the corresponding value function (and policy) is computed. This should be clarified.

- The paper closely follows (Jin et al., '18; Jin et al., '20b) and the technical contributions seem a little incremental.

- The algorithm requires a matrix inversion at each iteration, and requires solving Line 2 of Algorithm 3, as the authors also indicate. I understand that the paper focuses on sample efficiency, but computational feasibility is an important concern especially in RL, especially in the function approximation setting where there is a large-scale problem. Could it be possible to solve the least-squares problem in Equation (3.2) by using SGD? How would that impact the sample complexity?

- What is the prevalence of the problem that is considered in this paper? There is a structural assumption on the transition dynamics, i.e., the transition kernel is linear with a given kernel. How broad is this class of problems?

- The literature review and notation are deferred to the supplementary material, and the paper is missing a conclusion. I think some space can be saved for these important discussions by deferring some of the technical details to the supplementary material instead.

- The paper considers structured (i.e., linear) Markov games, which is stated in Section 2.1. This important aspect can be emphasized for the sake of clarity earlier, perhaps in the abstract also.
summary_of_the_review: The problem setting, the algorithms and the results require considerable clarification. The proposed methods can have large memory and computational complexities, which may be problematic for large state spaces. The technical contributions seem a little incremental.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies multi-player general-sum Markov games with one of the players designated as the leader and the rest regarded as the followers. In particular, we focus on the class of games where the state transitions are only determined by the leader's action while the actions of all the players determine their immediate rewards. 
main_review: In general, I enjoy the paper while as every MDP paper has an unlimited preliminaries dense section.
I strongly believe that I will praise with large acceptance the first paper that will provide a more intuitive way of description of the RL/MDP notions. Of course this is not an issue of this specific problem but of the whole community.

So, let's go to my main questions

Issue #1. I feel that there is a huge lack of motivation in the problem. Can you give three nowadays good examples of Leader/Followers General-Sum MDP games in practice?

Issue #2. What are the novel parts of your algorithms? More precisely, what are the intuitive steps of the proposed algorithms and your novel introductions in a typical MDP scheme? I would like a extent answer in this issue because honestly I felt that the proposed algorithms were just plug-and-play folklore tools that we employ in practice.
summary_of_the_review: Interesting paper with important theoretical contributions. There are issues about the motivation of the model.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of computing Stackelberg-Nash equilibria in a certain restricted family of Markov games, in which the followers do not control the transitions. Assuming an oracle that solves each stage game, the authors develop an algorithm for solving for Stackelberg-Nash equilibria in the overall game. 
main_review: Strength: The paper provides a near-optimal and, to my knowledge, novel regret bound for learning Stackelberg equilibria in the chosen setting.

Weaknesses: The setting is not very well motivated. The authors stipulate very significant assumptions on the problem (the existence of a normal-form SNE oracle, and the followers not affecting the state transitions) without justifying them. Why should we care about this very specific setting? Are there interesting problems that fall into it? 

Also, the above two assumptions together seem to immediately sidestep everything difficult and interesting about Stackelberg equilibria and multiplayer games. Indeed, the followers' strategy at each time step is now a function of the leader's strategy (because the followers cannot control the transitions), and that function is given by an oracle (by assumption). As such, the problem is reduced immediately to a (single-player) MDP.

In some sense, given the above, what is really going on is that the authors have developed algorithms for solving a class of MDPs perhaps more general than linear MDPs. If that class of MDPs can be isolated and is significant or interesting in its own right, perhaps it would be a good idea to frame the paper in that light instead. I also wonder if directly framing the problem as an MDP results in a simplification of the algorithms or analyses via known tools for MDPs. 
summary_of_the_review: A perhaps interesting theoretical result, but poorly motivated and very narrow.
review_title: null

Meta-review: This paper studies a Markov game with a single leader and multiple followers, where the state transitions are independent of the actions of the followers.  The paper studies online and offline RL methods for this subclass of the Markov game, and establishes a sublinear regret bound for the online RL method and sublinear suboptimality of the offline RL methods.

Although the paper appears to contain interesting ideas and contributions, the responses and revisions have not sufficiently addressed some of the major concerns of reviewers.  The reviewers and AC thus agree that the paper is not ready for publication.  For example, the issue of motivation and the myopic-follower setting has not been resolved yet.  Also, the discussion on the issues studied in Balcan et al. (2015) is not provided.  Please also note that (Jin et al., '20b) also proposes an optimistic variant of LSVI, and the exact algorithmic contributions still have some unclarity.
Decision: Reject