Tractable Multi-Agent Reinforcement Learning through Behavioral Economics

Q3 Questions about the sampling mechanism --- a simulator.

• The proposed algorithm requires access to a simulator, which is a strong assumption and may limit the practical applicability of the method, especially in real-world scenarios where such simulators are unavailable or costly to obtain.
• What challenges arise in adopting conditions weaker than requiring a simulator?

A3 We appreciate this insightful question.

• Simulator (a generative model) is a widely-used fundamental setting in RL and MARL literature, and even this setting is heavily understudied when considering additional risk-aversion or robustness. Sampling through a simulator is a fundamental setting with a long line of research for decades in RL ranging from all kinds of single-agent RL and multi-agent RL problems [1-2]. The widely studied data collection settings can be categoried into "simulator" settings, "online," and "offline". Simulator setting plays an essential role in shaping the theoretical foundation of RL and are critically needed before addressing more complex or practical sampling settings (such as online).

  However, even the fundamental simulator setting for robust MARL is understudeid and open with only a few prior works [3-4]. This motivates us to take a step in this open question, where our theoretical findings are potential to be extended to more settings such as online, offline, or function approximation robust MARL.

• The more complex setting introduces additional challenges, such as when doing offline sampling, we encounter insufficient coverage of the entire state and action spaces in offline scenarios [3]; and when doing online sampling, we need to balance the trade-off between exploitation and exploration during the interactive learning process, where data collection and agent strategy updates occur alternately.

[1] Clavier, Pierre, Erwan Le Pennec, and Matthieu Geist. "Towards minimax optimality of model-based robust reinforcement learning." arXiv preprint arXiv:2302.05372 (2023).
[2] Kearns, M., & Singh, S. (1998). Finite-sample convergence rates for Q-learning and indirect algorithms. Advances in neural information processing systems, 11.
[3] Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 2024
[4] Laixi Shi, Eric Mazumdar, Yuejie Chi, and Adam Wierman. Sample-efficient robust multi-agent reinforcement learning in the face of environmental uncertainty. In Forty-first International Conference on Machine Learning, 2024

Q4 Typo on L161: To allow agents to have risk preferences we make u a general class of convex

A4 Thank you so much for the detailed review. We will fix it in the updated revision as: 'we make a general class...'

We sincerely thank the reviewer for acknowledging our contributions and providing constructive suggestions.

Q1 What is the technical contribution? Duality and risk aversion concepts have been previously explored in game theory and multi-agent reinforcement learning (MARL).

A1 Thanks for raising this insightful question. From the view of risk-averse games with duality (both matrix games and Markov games, i.e., MARL), this work propose a new solution concept --- a natural equilibrium (RQE) for risk-averse games that is tractable to be computed for all finite games and finite-horizon Markov games (MARL). Risk aversion on its own gives rise to a convex game but cannot guarantee computational tractabiltiy of the resulting equilibrium notion (risk-averse Nash equilibria).

The key is to combine risk-aversion with bounded rationality, another important observation in behavirol economics. Bounded rationality on its own is also well known to help with computational tractability (as is pointed out by reviewer BGUx), but the degree of bounded rationality required to ensure this holds depends on the game structure (i.e., the relationship between players' payoffs and their magnitude). In contrast, the class of RQE we prove is computationally tractable is completely independent of the game structure. Furthermore, RQE is expressive in that it can recreate peoples' patterns of play in experimental data as observed in Figure 1.

Two benefits distinguish RQEs from previous other equilibrium notions such as Nash equlibrium and Quantal Response Equilibriums (only consider bounded rationality), offering a fresh perspective on learning games with tractability: 1) predictive of human decision-making; 2) guarantees for computationally tractability. To the best of our knowledge, this is the first result of its kind and while we only scratch the surface of their analysis we are excited at the protential that these equilibria represent for designing principled algorithms for multi-agent reinforcement learning. We achieve this by incorporatin another observation from behaviral economics that

Q2 Extending the findings to finite-horizon Markov Decision Processes (MDPs) may be somewhat straightforward, as the process involves relatively conventional methods. While this extension adds scope, it may not significantly deepen the theoretical insights or complexity of the approach.

A2 The reviewer is correct that much of the technical contributions on computational tractability primarily focus on matrix games. However, introducing uncertainty in environment dynamics, as Markov games are sequential in nature, requires new techniques from high-dimensional statistics to address the randomness in dynamics when the environment is unknown. In Section 4, extending one-shot games to the finite-horizon setting significantly broadens the scope of this work, encompassing sequential decision-making and games with unknown structures. This extension offers a fresh perspective by introducing a new equilibrium concept for learning MARL with tractability, expanding its relevance beyond the game theory and economics community to broader fields such as machine learning and reinforcement learning.

We sincerely appreciate reviewer E3pZ for recognizing the contributions of this work and providing various insightful suggestions.

Q1. Suggestions on presentation

• The difference between $\pi$ and $p_i$ is not clearly defined.
• Typo in line 160: "we make u a general class..."

A1. Thanks for raising these points. We will specify them in the updated version. For the reviewer's convenience, $\pi$ is usually represent a possible $\pi_{-i} \in \Delta_{\mathcal{A}_{-i}}$, an element in the joint action space of all agents except the $i$-th agent.

Q2. Suggestions on the experimental results

• The experiments lack breadth in demonstrating the algorithm’s efficacy across diverse problem settings. Only one cliff walk example is demonstrated, and very standard simple benchmarks are used for the repeated game.
• Could we not also have a baseline comparison with standard algorithms, such as Nash Q-learning in the MG, or other MARL algorithms (e.g., multi-agent PPO), to assess its performance against established algorithms?
• Similarly, could we extend the MG setting to more than two players in the toy examples? This could significantly increase computation time, even with the proposed, more efficient, algorithm.

A2 Thanks for raising this question for the experiments. Even though we are inspired by the concept of bounded rationality from behavioral economics, we want to highlight that this is used to rather enable the computation tractability of the risk-averse quantal equilibria solution concept. Thus, we believe risk-averseness of agents' behavior plays critical role in the cliff-walking environment we built and in the standard matrix-games promoting risk-averse solutions. We emphasize that our algorithms uses full information about the environments to reach the solutions shown in the three figures; thus, our evaluation criteria is more about showcasing risk-averseness than comparing performances in the learning setting. We validated our risk-averseness and bounded rational parameters' conditions in our Corollary 7.1-7.2. We believe our results on cliff-walking example provide important insights for future scalable RL algorithm development for large-scale environment experiments. These are important future directions that are of interest in the multi-agent RL community.

Q3. How would this accommodate non-convex compositions of risk-averse functions? Is there a simple extension, or would it be more complex?

A3 Thank you for raising this point. We focus on convex risk metrics for our risk-averse functions, motivated by the advantages of their dual representation, which simplifies the inner optimization problem by introducing a regularization term [1]. However, our results cannot directly extend to non-convex risk-averse functions (won't guarantee a dual representation), as non-convex optimization is generally more challenging and does not guarantee convergence to the global optimum. Exploring non-convex risk metrics is an intriguing direction for future research.

[1] Föllmer, Hans, and Alexander Schied. "Convex measures of risk and trading constraints." Finance and stochastics 6 (2002): 429-447.

Q4. What economic scenarios could the RAMG apply to, given that the concept of risk aversion originally stems from economics?

A4 Thanks for raising this important question. RAMGs are of widely interests not only in behavorial economics, but also in optimal control, operations research, finance, neuroscience, etc.

[1] Mihatsch, Oliver, and Ralph Neuneier. "Risk-sensitive reinforcement learning." Machine learning 49 (2002): 267-290.

We sincerely appreciate the reviewer’s thoughtful review and recognition of our work’s theoretical and experimental contributions.

Q1. Suggestions on the experimental results**

• There is only one toy example game for Markov game results.
• Bounded rationality is less obvious than risk averseness on Cliff Walk experiments. Interpreting bounded rationality from the experiments is difficult.

A1: Thanks for raising this question. Even though we are inspired by the concept of bounded rationality from behavioral economics, we want to highlight that this is used to rather enable the computation tractability of the risk-averse quantal equilibria solution concept. Thus, we believe risk-averseness of agents' behavior takes critical role in the cliff-walking environment we built. We emphasize that our multi-agent Markov game algorithm uses full-information of the environment to reach at the solutions shown in the two figures. We validated our risk-averseness and bounded rational parameters' conditions in our Corollary 7.1-7.2. We believe our results on cliff-walking example provide important insights for future scalable algorithm development for large-scale environment experiments. These are important future directions that is of interest in the multi-agent RL community.

Q2. What is the significance of the choice of aggregate risk aversion and action-dependent risk aversion? When should we pick either one?

A2:

Thanks for this question. Using the same $\rho_{i,\pi_{-i}}(\cdot)$，the Aggregate Risk Aversion formulation (2) is more conservative (always not bigger) than Action-dependent Risk Aversion formulation (3), follows by the Jensen's inequality. Intuitively this means the Aggregate Risk Aversion formulation in (2) considers the regularized worst-case when the agent i let the 'adversarial' know its strategy during the attack. This additional information can help the 'adversarial' to choose a harder case for agent i than the latter formulation in (3) where the 'adversarial' won't know agent i's policy. Hence, it is left to practitioners to choose the appropriate conservatism they need for their applications -- for e.g. (2) in communication games where adversarial agents often get agents' information and (3) in traffic networks where adversarial agents is the nature affecting the weather and so on.

Q2 Equilibrium collapse is briefly mentioned in l. 294. I would like to see a more in-depth description of how the results of this paper connect to the prior work regarding this phenomenon. It seems that the extended game you introduce seems to have some zero sum structure under a perhaps more stringent assumption than what you set (\epsilon_1 = \xi_{2,1} and \epsilon_2 = \xi_{1,2}, a condition satisfying your condition), under which J_1 + J_2 + \bar{J}_1 + \bar{J}_2 = 0. This can be seen from setting \lambda = 1/2 in your proof of Theorem 7 p. 21, l. 1133-1146. Is this an observation that connects to prior work about zero sum games and equilibrium collapse? It is also worth mentioning that setting \lambda = 1/2 leads to a condition that is consistent with your extension to the n-player setting (l. 1226-1232).

A2:

You are again correct that equilibrium collapse is key to our results, which is a phenomenon that is known to occur in n-player zero-sum matrix games and certain Markov games. For example, (Cai et al, 2016) and (Kalogiannis and Panageas, 2023) show that the set of CCE collapses to the set of NE for zero-sum polymatrix normal-form and Markov games, resp. In our work the introduction of risk-aversion gives rise to such a zero-sum structure if a stringent assumption such as $\epsilon_1 = \xi_{2,1}$ and $\epsilon_2 = \xi_{1,2}$ holds. The zero-sum game however is nonlinear due to the risk metrics. Thus, the zero-sum structure by itself is not enough to guarantee collapse and we require more convexity/concavity on the loss functions which we achive through the careful introduction of bounded rationality. In the two-player setting we allow for slight deviations away from an exact zero-sum structure by introducing the parameter $\lambda$ and we believe that the requirements for tractability can be relaxed in n-player games but presented the $\lambda=1/n$ case for simplicity. All told, we are making use of the fact that n-player zero-sum games are conducive to equilibrium collapse, but due to the nonlinearities in our games we generalize previous proofs.

Q3: I think the introduction and motivation of (6) and (7) needs some improvement. Could you give more motivation and intuition?

A3: Motivation for the studied $2n$-player game (6,7) can be summarized as follows. Incorporating risk aversion into the normal-form games is challenging. As illustrated in Example 1 (l.977), we show that even in two-player zero-sum games, the risk-adjusted game loses any zero-sum structure and may cease to even be strictly competitive (one player's gain is the other's loss). However, by using the dual form of a risk metric we show that the risk-adjusted game can be strategically equivalent (in that the eq. coincide) to a $2n$-player game which has a almost $zero-sum$-like structure that we can exploit using bounded rationality. We plan to add this discussion to the main text (adjusted to page-limits) making it clearer.

Q4: The notations $\xi_1^*,\xi_2^*$ are quite confusing, especially that you also use the notations $\tau_1,\tau_2$ in Fig. 1 without defining them in the main part. What do you mean precisely by satisfy the conditions of Theorem 2 (l. 328)? How do the \tau s and \xi s relate?I believe one issue in the presentation is that you chose to hide \tau in the definition of the regularizer D without putting it in front of D (as it appears from the appendix). Maybe a solution is just to add the examples to the main part to clarify this and further comment on the relationship between the \xi s and \tau s.

A4:

The $\tau$'s are special instances developed in Cor.7.1-7.2 as $\xi^*=1/\tau$. Thank you for the editing suggestions. We plan to add the following informal corollary to the main text (adjusted to page-limits), pointing the Fig.1 to this statement making it clearer:

Corollary: Suppose the players are risk-averse using some risk metric (for e.g., entropic risk, also see Table 1) with parameters $\tau_1$ and $\tau_2$ respectively. If they respond in the space of some associated quantal responses (for e.g., Kullback-Leibler divergence, also see Table 1) with parameters $\epsilon_1$ and $\epsilon_2$ respectively, then the players can compute a risk-averse QRE by using no-regret learning when the parameters satisfy $\epsilon_1 \tau_1 \ge \frac{1}{\epsilon_2\tau_2}.$

Before addressing the reviewer’s questions and suggestions, thank you for the thorough review and many constructive comments, which we feel have really helped us improve our presentation. When writing the paper we had to cut some exposition and move some to the appendix due to space constraints but you bring up many valid points that we will clarify and expand on in the revision. Below we address your individual comments:

Q1: My main concern about this paper is the following question: What exactly makes the introduced games tractable? The paper argues that it is the combination of bounded rationality and risk aversion. I find the focus on tractability rather confusing. Risk aversion has its own motivation but it is unclear if it is required here for tractability. To be precise, I think the contribution in this paper is that you can achieve tractability (for computing another solution concept than NE/CCE relating to a modified game) independently of the knowledge of payoff functions (their bounds I guess). More precisely, I think bounded rationality is already enough to allow for tractability but it should require some assumptions on the payoffs which this paper avoids. Please correct me if I have missed something here. The paper does not exactly present the contribution this way. -- l. 111-112: ‘RQE not only incorporates features of human decision-making but are also more amenable to computation than QRE …’ Why? There is no extended discussion about this whereas I believe it is essential to clarify the contributions. -- l. 235-238: While risk aversion might not be enough, I think bounded rationality should be enough (e.g. QRE as demonstrated in a number of works) under relevant assumptions on the structure of the game (mainly conditions on the bounded rationality level compared to the magnitude of the utilities/rewards). I find the presentation order confusing here. You start by introducing risk aversion and show its shortcomings as for the tractability of computing equilibria in such risk averse games to motivate the need of something else but equilibria should become tractable only with bounded rationality. -- From the title and the abstract (and throughout the paper), the emphasis is on tractability, as if both are actually needed to ‘achieve’ tractability. How does this condition compare to the one for say QREs? What’s the price to pay and advantages (if any) for RQNEs compared to QREs (beyond the advantage of incorporating risk aversion)?

A1: Your intuition and understanding of our contributions are highly accurate, and your suggestions on presentation are really helpful. In the revision we will adjust the presentation order to first introduce bounded rationality and why it is not enough to esnure computational tractabiltiy (more on this below). We will emphasize and give intuition for the following point: What makes these games computationally tractable? The combination of both risk-aversion and bounded rationality.

• Bounded rationality alone is insufficient for computational tractability. The reviewer has accurately explained this aspect. If we consider only bounded rationality (e.g., Quantal Response Equilibria, QREs), additional assumptions about the level of bounded rationality are required, which depend on the structure of the original game (e.g., the dimensionality of pure strategies and the magnitude of payoffs).

For instance, in a simple two-player game where the agents aim to solve objectives such as $\min_{\pi_1} \pi_1^\top A \pi_2 - \epsilon H(\pi_1)$ and $\min_{\pi_2} \pi_1^\top B \pi_2 - \epsilon H(\pi_2)$ with d-dimensional pure strategies $\pi_1,\pi_2$, a sufficient condition for computational tractability would require the bounded rationality parameter $\epsilon^2 \geq d^2 ||A+B||^2$. This requires $\epsilon$ to be excessively large, which may not always be practical or realistic. This point is central to the clarification in lines 111–112 of our manuscript and we will expand on this extensively in the revision to drive home this point.

• The contribution of this work: achieving computational tractability independently of the original game structure. In contrast, the condition for tractability of RQE only depends on the relative degrees of risk-aversion and bounded rationality and not on the underlying game structure. This allows one to choose these parameters independent of the game/task. This is achieved by the incorporation of risk in its dual form which allows the extended game to be essentially a nonlinear n-player zero-sum game (no matter the underlying payoffs). We will make this clearer as well.