Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning

We thank the reviewer for their time and thoughtful and positive feedback. We appreciate that the reviewer recognized the significance of our results, especially the impossibility of offline MAIL without interaction and the corresponding positive results for the interactive setting. Below, we address the reviewer's question regarding sample complexity.

Sample complexity

The reviewer correctly points out that the current upper bounds for sample complexity leave room for improvement, which we also acknowledge in our paper “the focus of this work was to show the first sample complexity bound for a computationally efficient algorithm in the queriable expert setting.” Below we would like to point out why it is non-trivial to improve the dependency on $\epsilon$ for MAIL-BRO and MURMAIL.

Non-convexity of objective

• The original problem is non-convex, therefore, we first have to change the objective to make it convex, which involves squaring it. This leads to $\epsilon^{-4}$ dependency for MAIL-BRO. Currently, we do not see a way to resolve this.

Missing knowledge of reward function

• Removing the assumption of a best response oracle and introducing MURMAIL brings up new challenges. The key one is how to upper bound the expectation that involves the best response policy, despite not having access to the reward function. This rules out the use of standard optimistic estimators. To overcome this, we introduce the maximum uncertainty response policy. This new principle leads to a further degradation in sample complexity to $\epsilon^{-8}$.

We believe this technique is novel and key to enable our guarantees in the context of Multi-Agent Imitation Learning, where no reward knowledge is assumed. That said, we agree with the reviewer that improved bounds might be achievable with new techniques, and we view this as a promising direction for future research.

Once again, we thank the reviewer for their time and positive assessment of our paper. We hope this response clarifies the origin of the sample complexity bounds. We would be happy to address any further questions.

Best,

Authors

We sincerely thank the reviewer for their insightful and encouraging review. We are especially grateful for the recognition that our paper is “very well written and provides necessary background, literature review, and proof sketch for people who are not intimately familiar with the topic.” Please find some comments on your questions below.

Theoretical contributions

We appreciate the reviewer’s assessment of our theoretical contributions. While the high-level ideas may seem intuitive, we would like to highlight that our analysis includes several technically non-trivial components.

• In particular, our analysis tackles the non-convex optimization problem of interactive Imitation Learning: $\min_{\widehat{\mu} \in \Pi} \max_{\nu \in \mathrm{br}(\widehat{\mu})} \mathbb{E}_{(\mu_E, \nu)} \left[ \sum\_{t=0}^{\infty}\gamma^t , \mathrm{TV}(\mu_E(\cdot \mid s), \widehat{\mu}(\cdot \mid s)) \right].$ The key difficulty lies in the fact that the data generation process depends on the minimizer itself $\widehat{\mu}$. To be precise, the data is generated from the occupancy measure of $(\mu_E, \nu)$ and $\nu$ is one of the best responses to the minimizer $\widehat{\mu}$. This makes the minimization too hard to be tackled in a computationally efficient manner. To bypass these problems, we derived an upper bound on the optimization problem above (Equation 4 in the paper), which is easy to optimize leveraging a Best Response Oracle. For more details, see lines 230 to 237 of our paper. Additionally, when the reward function is not known and a best response oracle is not available, we introduce the UCBVI inner loop to compute the maximum uncertainty response, which is by itself a new principle that could find further applications.

These new techniques allow us to provide a computationally efficient algorithm with sample complexity guarantees for MAIL, which was an important open problem.

Theorem 3.2

• Regarding Theorem 3.2, the reviewer correctly understood the issue: without knowledge of the reward function, the learner cannot be guided to recover a good policy. We tried to give some more intuition why knowing the transition dynamics is not sufficient in Appendix E(l.725-726) of the paper: “Additionally, note that even if the learner has access to the transition dynamics, the learner can not differentiate the actions from s1 as all actions lead to different states. Therefore, she cannot use this knowledge to recover an action that would lead to [a good state]”. As the reviewer has identified correctly, this is due to the missing reward function.

Practical applications

• A practical example could be route navigation recommendations. In this example, minimizing the Nash gap ensures robustness of route recommendations against individuals that may deviate from recommendations to increase their personal utility to e.g. to avoid traffic jams.

Tabular setting and deep imitation learning

• The reviewer has raised a valuable point regarding the limitation of the tabular setting. Since this is the first work that gives a sample-efficient imitation learning algorithm, we leave the extension to function approximation as future work (see Appendix C).
• As stated in lines 609-613, we believe that the same algorithmical framework presented in this work can carry over to deep settings and give insight into the main steps that need to be adjusted: “..., the main conceptual ideas easily carry on to deep imitation learning experiments. The largest theory-practice gap would be in the inner loop where UCBVI would need to be replaced by a Deep RL algorithm..”. To summarize, while our theoretical analysis may be limited to the tabular case, the ideas carry over to more general applied settings.

We hope this response has addressed the reviewer’s thoughtful questions and clarified the theoretical depth and practical relevance of our work. We are happy to incorporate any additional suggestions in the final version and thank the reviewer again for their constructive review.

Best,

Authors

We sincerely thank the reviewer for their thoughtful and positive evaluation. We are especially grateful for the kind comments that “the paper is well written, easy to read, and has nice illustrations that are intuitive” and that we “provide strong theoretical results that are coupled with experiments which verify them”. Please find below the answer to your questions.

Is the single policy deviation concentrability coefficient a property of the game or the data trajectories?

This is an excellent and important question. In the behavior cloning upper bound, the concentrability coefficient appears in terms of the estimated policies and, therefore, depends on the data. However, in our hardness result (Theorem 3.2), we pay for $\mathcal{C}(\mu_E,\nu_E)$, which depends only on the game structure and on the expert policies pair that collected the dataset. Importantly, this is a data and algorithm independent quantity that no non-interactive imitation learning algorithm can avoid.

To summarize, the hardness result depends on a property of the game and of the particular expert policies pair that generates the dataset.

Intuition on concentrability coefficient

To build more intuition, consider the example used in our experiments:

• In the provided Markov Game, there exist two paths resulting from different pure strategies taken in $s_0$ with the same value.
• The upper path is sensitive to deviations and therefore samples in the sensitive (worst case state) $s_1$ are required to recover a robust policy to deviations, i.e,. the Nash policy.
• The concentrability coefficient can therefore intuitively be interpreted as the coverage of this worst-case state (the coverage is an upper bound on it). If the expert distribution does not cover this sensitive state, the coefficient can be infinite and if the observed equilibrium is a convex combination of both, then the concentrability coefficient decays with the convex coefficient for this upper exploitable path, reaching its minimum if both are covered equally (see Figure 2).

We would be happy to clarify this further and add a more intuitive explanation to the camera-ready version to improve accessibility.

We thank the reviewer again for reading our paper and helping us to improve its quality. Happy to answer any further questions the reviewer might have.

Best, Authors

We thank the reviewer for their thoughtful, detailed, and positive feedback, and for recognizing that our work presents a “clear-cut improvement from previous work” and “the algorithm and its guarantees' proof make use of a broad array of the theoretical toolbox of RL and learning theory.”

In the following, we would like to address the different questions and few mentioned weaknesses raised by the reviewer:

Benchmarking

In the current submission, we focus on providing theoretical guarantees, leaving more practical extension for future work. Our numerical simulation on the same Markov Game used for the hardness result in Theorem 3.2 were thought to verify our theoretical results, in particular showing that the degradation of BC under high concentrability is a real effect. Moving forward, we plan to explore experiments in route recommendation, inspired by the motivating example in [1]. Importantly, in this setting, a low Nash gap ensures that no agent (car driver) has benefits in taking a different route.

Other interesting experiments can be performed in recent libraries such as BenchMARL [2]. However, the design of Deep MAIL experiments requires care in estimating how the concentrability coefficient behaves in practical environments and in computing the Nash Gap for evaluation purposes.

Relation with Convex Markov Games

We see a twofold relation with the work of Gemp et al. 2024, which we outline below:

• Imitation as Convex Markov Game: First, notice that in their section 5.2, they use the convex formulation for imitation learning. However, they use this technique in presence of reward for equilibrium selection purposes. When one sets the reward to zero in their formulation, we are left with an occupancy measure matching problem which is akin to minimize the value gap according to (Tang et al 2024) terminology. Therefore, their technique does not seem to be suitable to learn equilibria from data in presence of high concentrability coefficient.
• Imitating equilibria in Convex Markov Game: As a final connection, we point out that one might study the question of learning equilibria from data in convex markov games which is a more general setting than the markov games studied in our work. If the markov game functional has G-bounded gradients our techniques still apply via a standard reduction from convex to linear losses in online learning. However, studying imitation in convex markov games with unbounded gradients is an interesting open question.

Extension to Low-rank interactions games

The low rank interaction assumption might help in bypassing the concentrability coefficient. In particular, if the norm of the difference between the learnt and expert policy is a low interaction rank function. It is, in our opinion, unclear under which conditions this can be proven. Moreover, notice that in [4] this assumption allows the authors to avoid the exponential dependency on the number of players in Offline MAIL. Under our setting, the dependence is polynomial even without the low rank assumption, see Remark 4.1.

KL divergence in algorithm 2

We did not use the KL divergence in Algorithm 2 because our analysis relies on the Cauchy–Schwarz inequality (see Equation 8 in Appendix G), which naturally leads to a squared norm. While one could derive an upper bound on Equation 8 using the strong convexity of KL and formulate updates that minimize this bound, doing so would likely result in suboptimal performance. Specifically, such an alternative would optimize a possibly looser bound than what Murmail currently minimizes (Equation 8).

Uniqueness of equilibria

Our analysis does not rely on a uniqueness assumption for equilibria. In Zero-Sum Games, the value is unique, but not the strategy. Under the uniqueness assumption, the lower bound construction is no longer valid, and the concentrability coefficient could be avoided. This is an interesting open question. Moreover, our theorems can be extended to the general-sum Markov Game setting, where not even the uniqueness of equilibrium value holds true as stated in Remark 4.1 and sketched in Appendix I.

We hope these responses clarify the raised points. We are grateful for the reviewer’s detailed and constructive feedback and would be happy to incorporate any further suggestions in the camera-ready version.

We would be glad to further clarify any additional points the reviewer may have.

Best, Authors

[1] J. Tang, G. Swamy, F. Fang, and Z. S. Wu. Multi-agent imitation learning: Value is easy, regret is hard. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, NIPS2024

[2] Matteo Bettini, Amanda Prorok, and Vincent Moens. 2023. BenchMARL: Benchmarking Multi-Agent Reinforcement Learning.

[3] Gemp, I., Haupt, A.A., Marris, L., Liu, S. and Piliouras, G., Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning

[4] Zhan, W., Fujimoto, S., Zhu, Z., Lee, J.D., Jiang, D.R. and Efroni, Y., 2024. Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank.