Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning

Q1. The idea of fictitious uncertainty set looks interesting, can it be useful somewhere else.

Fictitious uncertainty sets, inspired by behavioral economics, hold significant value in game theory and behavioral economics and have several meaningful applications:

• Understanding human preferences regarding risk and robustness under uncertainty: Humans are generally risk-averse and prefer robustness under uncertainty 1 2 3, whose behaviors correspond to our fictitious uncertainty set, rather than the $(s,\mathbf{a})$-rectangular uncertainty set used in prior works. Applying our framework to real-world human data could help predict individual risk preferences and facilitate the design of personalized decision-making strategies for users.
• Improving robustness in safety-critical applications. As mentioned in the introduction, numerous safety-critical scenarios can benefit from our proposed framework to identify optimal solutions for multi-agent interactions, such as financial markets, social dilemmas, autonomous driving, and human-robot interactions.

2. Further improve the presentation.

We sincerely thank you for your valuable suggestion regarding the writing. In the revised version of our work, we have moved part of the background information to the Appendix and included the algorithm description in the main text.

3. The convergence rate

We acknowledge that the $O(\epsilon^{-4})$ convergence rate may seem suboptimal but note that rate $O(\epsilon^{-4})$ or $O(\epsilon^{-3})$ are common in MARL literature, as seen in 4 and 5. As the first to break the curse of dimensionality in RMGs, we see great value in further improvements and plan to explore ways to accelerate the algorithm in future work.

4. The relationship of this work to linear MG works

• Is the idea of assuming $(s,a_i)$ structures around instead of $(s, **a**)$ similar to the independent linear function approximation in linear MGs?

  The proposed $(s,a_i)$ plays a fundamentally different role in robust MGs compared to the methods used in non-robust linear MGs..

  1. Different problems and challenges: Nonlinearity in Robust MGs. Robust MGs pose additional challenges compared to non-robust MGs due to the nonlinearity of the robust value function, unlike the linear payoff functions in non-robust MARL, which fundamentally alters the problem structure and solution methods.
  2. Inspired by game theory and behavioral economics. The $(s,a_i)$ structure is considered for two key reasons: 1) Capturing human behavior in reality inspired by behavioral economics, both $(s,a_i)$-rectangular structures and $s$-rectangular structures ($\otimes\_{s\in \mathcal{S}} \mathcal{U}\_\rho^{\sigma_i}(\mathbb{E}\_{\mathbf{a} \sim \pi_h} P\_{h, s, \mathbf{a}})$) can predict human behavior, but $(s, **a**)$ fails to do so; 2) We ultimately choose to consider the $(s,a_i)$ structure instead of the $s$-structure because, the $(s,a_i)$-rectangular set makes Nash (also CCE and CE) is guaranteed to exist, whereas this is not the case for the $s$-rectangular set.
  3. Distinct techniques for breaking the curse of dimensionality in $(s,a_i)$ structures A direct indication is that our techniques developed for $(s,a_i)$ structures also apply to $(s)$-uncertainty set, whereas no corresponding result exists for non-robust linear MG.

• How does your model technically break the curse of multi-agency compared to prior work?

  A concise answer is that it allows for the decomposition of the non-linear payoff function in robust MGs. The key reason why the $(s, a_i)$ structure helps break the curse of dimensionality lies in its role within the Bellman equation:

  $$V^{\pi}\_{i,h}(s) = \mathbb{E}\_{\mathbf{a} \sim \pi_h(s)}[r\_{i,h}(s, \mathbf{a})] + \mathbb{E}\_{a_i \sim \pi_{i,h}(s)} \left[ \inf\_{\mathcal{U}\_{\rho}^{\sigma_i} \left(P^{\pi_{-i}}\_{h,s,a_i} \right)} P V^{\pi}\_{i,h+1} \right],$$

  $V^{\pi}\_{i,h}$ becomes a linear function with respect to the $i^{th}$ agent's policy $\pi_{i,h}$. This property also holds for the $(s)$-uncertainty set but not for the $(s, \mathbf{a})$ uncertainty set used in prior works. Consequently, we can leverage concentration inequalities to control the gap between the estimated and true value functions, effectively breaking the curse of dimensionality for $(s, a_i)$ and $(s)$ uncertainty sets, but not for $(s, \mathbf{a})$.

1. "The proposed algorithm is the first to overcome the curse of multiagency in RMGs, irrespective of the uncertainty set types." Is it due to an additional assumption?

Our work breaks the curse of multiagency through two key innovations: the introduction of a new class of fictitious RMGs and a new algorithm. Both elements are essential. While the algorithm addresses a specific type of RMGs—the proposed fictitious RMGs—it is also the first to break the curse within the broader class of RMGs, as no prior work has achieved this, even for other subclasses of RMGs. Specifically,

• Novel and Realistic Assumption Inspired by Behavioral Economics General RMGs are computationally intractable to solve, which leads to the widely used rectangularity assumptions. We didn't add addtional assumption, but replace the state-joint-action rectangular assumption used in prior work by a realistic rectangular assumption inspired by human behavior in behavioral economics. While this fictitious uncertainty set helps break the curse of multiagency, its primary purpose is to realistically model human behavior.
• Tailored Algorithm for Breaking the Curse of Multiagency. Breaking the curse of multiagency in our proposed RMGs is more challenging than in standard MGs due to the nonlinearity of the robust value function, unlike the linear payoff functions in standard MARL. To address this, Algorithm 1 uses tailored sampling methods to handle nonlinearity and integrates them with a customized online learning algorithm.

2. Is it "impossible" to break the curse for state-joint-action rectangular sets?

• Possibly Impossible, but a decisive conclusion for this is hard. We agree with the reviewer's intuition that it may be impossible. Prior work shows an exponential sample complexity lower bound for computing Nash in general-sum games 2. However, no work has established a lower bound for computing CCE/CE in any type of game. This remains a very open question and area in game theory and a promising direction for future research.
• We emphasize that the proposed fictitious uncertainty set is inspired by how human behavior is observed in reality through behavioral economics, not because the state-joint-action approach from prior works is infeasible, prompting a simpler alternative.

3. Can other assumption lead to polynomial sample complexity results and make sense?

A "reasonable" uncertainty set should ensure the well-posedness of the problem --- guaranteeing the existence of equilibria (e.g., Nash). This presents challenges in problem formulation (assumptions), requiring both a well-posed uncertainty set and feasible algorithms with polynomial sample complexity to compute the corresponding equilibria, which may involve trade-offs between the two. For example, $s$-rectangular uncertainty sets may ensure polynomial sample complexity but fail to guarantee Nash equilibrium, making them less desirable. Exploring other uncertainty sets that ensure well-posedness and allow tractable algorithm presents exciting opportunities for both game theory and MARL community.

4. Get better convergence rates if use optimistic FTRL [Syrgkanis et al. 2015]?

A brief answer, based on the authors' intuition, is no. The non-linear payoff functions in RMGs create a dilemma between the statistical complexity of estimating the transition kernel and the regret from online adversarial learning algorithms (e.g., FTRL and optimistic FTRL). The current bottleneck lies in the statistical complexity of estimating the transition kernel. Since we already use a state-of-the-art online learning algorithm with optimal sample complexity in standard MARL 1, switching to optimistic FTRL is unlikely to improve the results further.

5. Others:

• Adding detailed comparison between the proposed set and prior works.
  • As the reviewer suggested, we will certainly include a more detailed comparison in the appendix of the revised version.
• The reviewer is correct that the cartesian product in Equation (9) is over all $h,s,a_i$ for any $i$-th agent.
• 289 to 305: Why does the value function take actions as arguments?
  • Here, $V$ represents a general payoff function that naturally depends on all agents' actions, not the value function. We will revise $V$ to a different notation, $u$, to avoid ambiguity.
• 306 to 317: Will $(s,**a**)$-rectangular degrade to single-agent $(s,a)$-rectangular RMDP in case other agents remain fixed?
  • No, it does not degrade to $(s,a)$-rectangular RMDPs. Since even if other agents' policies $\pi_{-i}$ are fixed but stochastic, their selected joint actions $**a**\_{-i}$ will vary, leading to corresponding uncertainty sets around each joint action $**a**\_{-i}$. As a result, other agents cannot be treated as a fixed part of the environment, preventing the model from simplifying to the single-agent $(s,a)$-rectangular case.

We sincerely thank the reviewer for the careful reading of the paper and the insightful and valuable feedback.

1. Additional experiments verifying the effectiveness of Robust-Q-FTRL against baseline methods could be beneficial.

Thank you very much for this valuable suggestion! As the reviewer rightly observed, in this work, we focus on taking an initial step toward developing a clear and realistic formulation and framework for players in multi-agent systems under uncertainty. Towards this, we introduce a fictitious uncertainty set inspired by behavioral economics, establish the existence of Nash equilibria (as well as CCE and CE) and propose an algorithm with theoretical guarantees. As the reviewer suggested, further experimental validation of both the proposed formulation and the proposed algorithm with comparison to baseline across diverse application scenarios would be highly valuable. In the future, we are considering several such scenarios, including autonomous driving simulations in CARLA or real-world experiements for human-robot interactions with the humanoid robot Unitree G1.

2. Can some of the assumptions in Robust-Q-FTRL be relaxed to make it applicable to deep MARL?

Thank you for raising this valuable point! Both assumptions underlying Robust-Q-FTRL can be relaxed to better align with practical deep MARL settings, which are truly interesting future directions. Specifically:

• Relaxation of data collection through a generative model: Our theoretical findings have the potential to extend to more practical data collection scenarios commonly used in deep MARL, such as online or offline settings. Exploring these extensions represents an interesting direction, which introduces additional challenges—particularly in online settings, which inherently pose difficulties in terms of statistical estimation and sample efficiency [2].
• Relaxation of the tabular Markov game formulation for MARL problems: We believe our current results in tabular cases provide a strong foundation for exploring more general scenarios involving function approximation. This aligns closely with deep MARL, where neural networks are typically employed to approximate policies and Q/V-value functions. Nevertheless, adapting our approach to general robust MARL problems (e.g., robust linear MARL) will require distinct problem formulations—an open research area with no existing solutions to the best of our knowledge. Moreover, algorithm design and theoretical analysis frameworks would necessitate different assumptions, such as linearization conditions for linear function approximation [1] and realizability or low-rank structural assumptions for general function approximation.

[1] Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. "Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation." COLT 2023.
[2] Lu, Miao, et al. "Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm." arXiv preprint arXiv:2404.03578 (2024).

We sincerely thank the reviewer for recognizing and appreciating our contributions, both in terms of the problem formulation and the technical results. This acknowledgment is extremely rewarding!

1. How does this work perform in real-world MARL tasks, and are there existing practical applications?

Thanks for pointing out this essential point! Definitely, practical usefulness is the main motivation behind our problem formulation and the proposed fictitious uncertainty set. Currently, two promising classes of applications emerge from this work, providing exciting future research directions:

• Understanding human preferences regarding risk and robustness under uncertainty: A classical finding in behavioral economics is that humans are typically risk-averse and prefer robustness when facing uncertainty stemming from other players or the environment [1]. Applying our algorithms to real-world human data could help predict individual risk preferences and facilitate the design of personalized decision-making strategies for users.
• Improving robustness in safety-critical applications. As mentioned in the introduction, numerous safety-critical scenarios can benefit from our proposed framework to identify optimal solutions for multi-agent interactions, such as financial markets, social dilemmas, autonomous driving, and human-robot interactions. Various experimental scenarios include autonomous driving simulations in CARLA, financial analysis using Kaggle datasets, and other datasets in Hugging Face, as well as real-world experiements for human-robot interactions with the humanoid robot Unitree G1.

In this work, we focus on taking an initial step toward developing a clear and realistic formulation and framework for players in multi-agent systems. As the reviewer suggested and recognized, the next step is to apply this framework to diverse practical scenarios.

2. Further experiments to verify the effectiveness of the algorithm.

Thank you very much for this valuable suggestion! In this work, we focus on taking an initial step toward developing a clear and realistic formulation and framework for players in multi-agent systems. As the reviewer suggested, further experimental validation of both the proposed problem formulation and the corresponding algorithms would be highly valuable across diverse application scenarios. In the future, we are considering several such scenarios, including autonomous driving simulations in CARLA or real-world experiements for human-robot interactions with the humanoid robot Unitree G1.

3. Discussions on the computational complexity of Robust-Q-FTRL

We sincerely thank the reviewer for this valuable suggestion. In summary, the computational complexity of our proposed Robust-Q-FTRL algorithm is similar to that of the current state-of-the art algorithm for standard MARL presented in [2]. Specifically, Robust-Q-FTRL converges within $K=O(\frac{H^3}{\epsilon^2})$ iterations, with each iteration requiring computational complexity $O(HS\log(S)\sum_{i}A_i)$, which is nearly linear with respect to the size of the state and action spaces. As the reviewer suggested, we will incorporate this detailed discussion following the introduction of our main result, Theorem 4.1.

4. An extra period at the end of page 2, line 97

Thank you for pointing this out. We have removed the extra period and will thoroughly polish the entire manuscript again in the revised version.

[1] Goeree, Jacob K., Charles A. Holt, and Thomas R. Palfrey. "Risk averse behavior in generalized matching pennies games." Games and Economic Behavior 45.1 (2003): 97-113.
[2] Li, Gen, et al. "Minimax-optimal multi-agent RL in Markov games with a generative model." Advances in Neural Information Processing Systems 35 (2022): 15353-15367.