Mitigating Relative Over-Generalization in Multi-Agent Reinforcement Learning
Authors: Ting Zhu
Yue Jin
Jeremie Houssineau
Giovanni Montana
Venue: Accepted by TMLR ()

Abstract: In decentralized multi-agent reinforcement learning, agents learning in isolation can lead to relative over-generalization (RO), where optimal joint actions are undervalued in favor of suboptimal ones. This hinders effective coordination in cooperative tasks, as agents tend to choose actions that are individually rational but collectively suboptimal. To address this issue, we introduce MaxMax Q-Learning (MMQ), which employs an iterative process of sampling and evaluating potential next states, selecting those with maximal Q-values for learning. This approach refines approximations of ideal state transitions, aligning more closely with the optimal joint policy of collaborating agents. We provide theoretical analysis supporting MMQ's potential and present empirical evaluations across various environments susceptible to RO. Our results demonstrate that MMQ frequently outperforms existing baselines, exhibiting enhanced convergence and sample efficiency.

Published in Transactions on Machine Learning Research (11/2024)
Mitigating Relative Over-Generalization in Multi-Agent Re- inforcement Learning
Ting Zhu", Yue Jin?, Jeremie Houssinean 9 Giovanni Montanalio 1.2,1
Deportment of Statistics, University of Warwick Coventry, UK
Warwick Manufacturing Group, University of Warwick, Coventry, School of Physical & Mathematical Sciences, Nanyang Technological Universily, Singapore Alon Turing Institute, London, UK
ting.zhu whwwwwwricckcom ac.ub Freejin.@@wowiie. ac. ac.uk
jeremic. jeremie.houssineee www.sooowwwwwwsoeoo sgu.sg g- momonnnaa wwarwick..cc.o
Reviewed on OpenReview: /ttp:s///ppnrevette net/ forum? id= oAkSRA13gU
Abstract
In ralindd multi-agent reinforcement learning, agents learning in isolation can lead to relative veegraeeraiinttion (RO), where optimal joint actions are undervalued in favor of suboptimal ones. This hinders effective coordination in cooperative tasks, as agents tend to choose actions that are individually rational but collectively suboptimal. To address this issue, we introduce MaxMax Q-Learning (MMQ), which employs an iterative process of sampling and evaluating potential next states, selecting those with maximal Q-values for learning. This approach refines approsimations of idcal state transitions, aligning more closely with the optimal joint policy of collaborating agents. We provide theoretical analysis supporting MMQ's potential and present empirical evaluations across various environments susceptible to RO. Our results demonstrate that MMQ frequently outperforms existing baselines, exhibiting enhanced convergence and sample efficiency.
1 Introduction
Cooperative multi-agent reinforcement learning (MARL) has become increasingly important for address- ing complex real-world challenges that require coordinated behaviors among multiple agents. Successful applications included playing card games (Brown & Sandholm, 2018). autonomous driving (Shalev-Swwartz
et al.
2016
Zhou et al. 2021h, unmanned aerial vehicles (Wang et al. 2020), wireless sensor networks (Xu
et al.
2020:
Sahraoui et al. 2021 and traffic light control (Bazaan 2009 Zhou et al.] 2023). A dominant
framework in MARL is centralized training with decentralized execution (CTDE) (Lowe et al. 2017 Rashid
et al. 2018 Son et al. 2019), which often relies on a centralized coordinator to aggregate information, such local observation or individual actions from other agents during training. While this approach has been widely adopted due to its effectiveness in leveraging global information, may still face scalability challenges, particularly in environments with large number of agents complex interactions. Additionally, in scenarios where privacy is a critical concern, CTDE methods that require access to individual agent data could be less desirable. While many CTDE methods do not require exhaustive local information from all agents, the potential for scalability and privacy issues in certain implementations warrants consideration. While inter-agent communication can partially mitigate some of these challenges (Foerster al. 2016 Zhu al., 2022), introduces additional overhead, which can be prohibitive in environments where communication is costly unreliable.

---

Published in Transactions on Machine Learning Research (11/2024)
Consider large-scale drone swarms for search and rescue surveillance tasks (Baldazo al. 2019 Batra et al. 2022). In a CTDF framework, centrally aggregating data from each drone can be impractical due to network delays, dynamic environments, and potential communication failures. Additionally, communication frameworks may struggle with channel congestion or high packet loss, espocially in complex terrain or with electronic interference. Fully decentralized learning presents a promising alternative, where agents rely solely on their experiences without considering the actions or policies of other agents during both training and execution. This approach enables the system to scale effectively and remain resilient to communication issues. However, decentralized approaches come with their own challenges. From an individual agent's 's perspective, the learning process occurs within a non-stationary MDP, as the transition probabilities change due to the evolving policies of other agents.
Existing decentralized MARL methods, including optimism strategies in Q-learning (Lauer & Riedmiller 2000 Matignon et al. 2007 Wei & Luke| 2016), attempt to mitigate these challenges. More recently, Ideal Independent Q-lcarning (I2Q) (Jiang & Lu 2022) explicitly models state transitions assuming optimal joint behavior, introducing ideal transition probabilities to address non-stationarity in independent Q-learning.
Another critical issue in decentralised MARL is Relative Over-generulisation (RO), where agents prefer suboptimal policies because individual actions appear preferable without coordinated strategics. First defined and studied within the field of cooperative co-evolutionary algorithms (Wiegand 2004 Panait et al. 2006;
Panait 2007), it has more recently been explored predominantly in centralised MARL contexts (Rashid
et al. 2020: Gupta et al. 2021 Shi & Peng 2022). : RO occurs when agents adapt their actions to limited interactions, often focusing on the exploratory behaviours of other agents. Consequently, agents may favour more robust but less optimal solutions in the absence of coordinated strategies. In decentralised learning settings, this problem has been discussed within simple matrix game scenarios (Wei & Luke, 2016). RO, exacerbated by non-stationarity, presents a significant challenge as agents make decisions based on fluctuating global rewards without the benefit of coordinated strategies (Matignon et al. 2012 Wei & Luke 2016).
Although provious implementations of optimistic strategics have shown some efficacy, our empirical rcsults indicate they fall short in cooperative tasks with pronounced RO challenges.
This paper introduces MaxMax Q-Learning (MMQ), a novel algorithu designed to address the RO problem in decentralised MARL scttings. MMQ aims to mitigate the challenges posed by RO and non-stationarity in decentralised learning environments. The key insight behind MMQ is enabling agents to reason about beneficial experiences that occur infrequently. At its core, MMQ employs two uon-parameterised quantile models to capture the range of state transitions, accounting for both environmental factors and the evolving policies of learning agents. These models iteratively sample, evaluate, and select optimal states, refining the approximation of ideal state transitions and facilitating global reward maximisation. The state with the highest Q-value is then selected to update the value function, promoting convergence towards optimal Q-values in the context of other agents' best actions. The MMQ algorithm incorporates two maximum operators in the Bellman update: the first takes the maximum over all possible next states to select the most promising future scenario, and the second takes the maximum over Q-values of state-action pairs to determine the best action in that scenario. MMQ's adaptive nature, which involves continuously updating the ranges of possible next states, enables effective decision-makinn making in dynamic environments.
The main contributions of this paper are throcfold. First, we introduce MMQ, a novel algorithm that employs quantile models to capture multi-agent dynamics and approximate ideal state transitions through sampling. Second, we provide theoretical demonstration of MMQ's potential to converge globally optimal joint policies, assuming perfect knowledge of forward and value functions. Third, we present empirical results showing that MMQ often outperforms or matches established baselines across various cooperative tasks, highlighting its potential for faster convergence, enhanced sample efficiency, and improved reward maximisation in decentralised learning environments.
The remainder of this paper is structured as follows: quantification. Section 3 provides background on multi-agent Markov Decision Processes and the challenges of relative over-genoralization. Section 4 presents the methodology of MaxMax Q-Learning, including its theoretical foundations and implementation details. Section 5 describes our experimental setup and results
Section 2 discusses related work in MARL and uncertainty
2

---

Published in Transactions on Machine Learning Research (11/2024)
across various environments. Finally, Section 6 concludes the paper with discussion of our findings and potential directions for future research.
2 Related work
Centralised learning methods. Within the centralized training paradigm, RO has been discussed mostly for value factorization methods like QMIX (Rashid al.
2018). The monotonic factorization in QMIX cannot represent the dependency of one agent's value on others' policies, making prone to RO. Proposed solutions include weighting schemes during learning (Rashid et al. 2020), curriculum transfer from simpler tasks [Gupta et al. 2021 Shi & Peng 2022), and sequential execution policy (Liu et al. 2024 Soft Q-learning extensions to multi-agent actor-critics (Wei et al. 2018 Lowe et al. 2017) utilise energy policies for global search to mitigate RO. However, unlike our decentralized approach, these methods require a centralized critic with joint action access during training.
Fully decentralized learning. Decentralized approaches in MARL aim to overcome the scalability and privacy issues associated with centralized methods. However, they face unique challenges, particularly in addressing non-stationarity and RO. Existing approaches can be categorized based their strategies for tackling these issues. Basic independent learning methods like Independent Q-lcarning (IQL) (Tan) 1993) and independent. PPO YYu et al. 2022) form the foundation of decentralized MARL. However, their simultaneous updates can lead to non-stationarity, potentially compromising convergence. Recent work by Su & Lu (2023) on DPO addresses this by providing monotonic improvement and convergence guarantees. To mitigate negative impacts of uncoordinated learning, several methods promote optimism toward other agents' behaviors. Distributed Q-learning {Lauer & Riedmiller 2000) selectively updates Q-values based only on positive TD errors. Hysteretic Q-learning (Matignon al.) 2007) uses asymmetric learning rates, while Lenient Q-learning (Wei & Luke 2016 selectively ignores negative TD errors. These techniques aim to overcome convergence to suboptimal joint actions by dampening unhelpful Q- changes. Taking a different approach, the recently introduced Ideal Independent Q-learning (T2Q) (Jiang & Lu 2022) explicitly models ideal cooperative transitions. However, it requires learning an additional utility function over state pairs. Our proposed method, MMQ, builds upon these approaches by encoding uncertainty about decentralized MARL dynamics. We model other agents as sources of heteroscedastic uncertainty with an epistemic flavor, providing more flexible way to represent optimistic policics. By sampling from possible next states, MMQ avoids the need for heuristic corrections separate Q-functions, offering novel solution to the challenges of decentralized MARL.
Quantifying different sources of uncortainty is crucial in reinforcement learning, particularly multi-agent settings. Prior work distinguishes between aleatoric uncertainty, arising from environment stochasticity, and epistemic uncertainty, due to insufficient experiences (Osband al. Depeweg et al. 2016). Various methods, including variance networks (Kendall & Gal 2017 Wu et al., 2021 and ensembles [Lakshminarayanan et al. 2017 have been proposed to model these uncertainties, with applications in single-agent RT, (CCua et al. 2018 Sekar et al. 2020). MARL introduces additional complexity due to the dynamic nature of agent interactions, leading to non-stationarity. This non-stationarity limits an agent's 's ability to reduce epistemic uncertainty through repeated state visits (Hernandez- el al. 2017) and can be viewed as another form of epistemic uncertainty. Our proposed MMQ algorithm addresses these challenges by using quantile networks to effectively manage two key sources of epistemic uncortainty in multi-agent settings: limited experiential data and evolving strategies of other agents. This approach allows MMQ to better handle the unique uncertainties present in decentralized MARL environments.
Uncertainty quantification.
2016
3 Background and preliminaries
3.1 Multi-agent Markov Decision Process
Consider a multi-agent Markov Decision Process (MDP) represented by M = (S, R, Pewv. 7). Within this tuple, S denotes the state space, A is the joint action space, (snv a) and R(s, s') are respectively the environment dynamics and reward function for states s, s' E S and action A, and y is the discount factor. Given N agents, the action space is of the form A Ai ... Av with any action A taking the form
3

---

Published in Transactions on Machine Learning Research (11/2024)
Table 1: Payoff matrix for a two-agent game
Agent
A
C
A
3
-6
-6
gent
B
-6
0
C
-6
0
a a= (aI...... (a)....,aN.. At each time step f, agent indexed by i {I,...,N) selects an individual action, a,. When the N actions are executed, the environment transitions from state s to state s', and every agent receives a global reward, rz- The objective is to maximize the expected return, iee, B 7'rel, where T is the time horizon. The individual environment dynamics is defined as
P,(5'ss,a)) Σ Penv
where a-; represents the joint action excluding agent and m-i the joint policy of all other agents. Here, the joint action inherently depends ag and a-+. From any individual agent's perspective, the learning process occurs within a non-stationary MDP due to the evolving policy T-..
3.2 Relative over-generalization through an example
Consider two-agent game with the reward structure shown in Table I In this game, there are three possible actions: A, B, and C. Agents would receive joint reward of +3 if they take A logether. However, if only one agent takes A, that agent incurs a penalty of -6. Agents end choosing less optimal actions (B or C) if they percoive the reward for choosing A to be lower, based on their expectations of the other agent's actions. For agent 1, the utility function Q1(-) is related to the probability that the other agent chooses A, ie.. (2))). In this case, (A) would be smaller than (B) or Qi(C) if TT (A) < f- This threshold arises because the expected value of choosing A becomes lower than choosing B C' when the probability of the other agent also choosing A falls below z. Consequently, during initial uniform exploration where (A( = (A) 1. both agents tend to favour B or C over A, even though A is the globally optimal choice. Thus, with independent learning without considering the other agent's best action, both agents may end up with choosing suboptimal actions and fail to cooperate.
3.3 Independent Q-Learning
In independent Q-learning (Tan 1993 each agent i learns a policy independently, treating other agents as part of the environment. The individual Q-function is Q, ax) = E 1 7're 8p 8, 0,00 a.) for agent i. Each agent updates its Q-function by minimizing the loss (. (3: - Qi at)) where is the target value defined as R(s, 8') + max,; Qi(s', a(() The RO problem arises this setup as each agent seeks maximize its own expected return based on experiences where other agents' policies evolve and contain random explorations.
3.4 Ideal transition probabilities
To address the RO problem in this context, some approaches introduce implicit coordination mechanisms centered on the concept of an âdeal transition model (Lauer & Riedmiller) 2000 Matignon al. 2007 Wei & Luke 2016; Palmer et al.) 2018 Jiang & Lu 2022). These methods guide each agent's 's learning with hypothetical transitions that assume optimal joint behavior, aligning independent learners towards coordination. Let т-; denote the joint policy of other agents, and Q' the optimal joint Q-function. The optimal joint policy of other agents can be expressed as =-, = arg max Q*
(x. 0j a..).
The concept of idcal transitions refers to hypothetical state transitions that assume other agents are following optimal joint policies. These ideal transition probabilities represent the dynamics that would occur all agents achieved perfect coordination, and are defined PV ( (,, 0i) Peno (s'(s, 0i, HI (8, Based on
4

---

Published in Transactions on Machine Learning Research (11/2024)
these probabilities, the Bellman optimality equation is given by
(s a:) (e(laa)) R(s,s') + + max Q7 at)
(1)
of
where (8, a;) is the optimal Q-function for agent i.
An important theoretical result from Jiang & Lu 2022 establishes that when all agents perform Q- learning based on these ideal transition probabilities, the individual and joint optimality align, that is, max,, (7 a;) (s T7" (s)),, where (* a) is the optimal joint Q-function for any action a E A, and n² is the optimal joint policy. However, achicving true ideal transitions is intractable in practice due to the evolving, rncontrolled nature of learning agents. This motivates developing techniques approximate ideal transitions.
4 MaxMax Q-learning Methodology
4.1 Approximation of Bellman optimality equation
Our methodology aims to approximate ideal transition probabilities, which assume other agents follow optimal joint policies. We focus on deterministic environments and reformulate the Bellman optimality in Eq. (1) to highlight the dependence on the set Sg,a, of possible next states,
Sa.a; ( Sonv(,,, ui, a..) a E
AI 3
(2)
where (s, 0g, a-s) is the deterministic transition function that maps the current state and the joint actions of all agents (ai, a.:) to the next state s', Aj is the action space for each agent j and the Cartesian product AT represents all possible combinations of actions by the other agents. It is noted that we only use fenv to define the set Sa,a; here, but do not need to learn this global transition function directly in our algorithm. Encoding the deterministic transitions by a delta function, (s.a)(s),))) Eq.
is rewritten as
(1 az) = Eg' inntor (mma)))))) R(ss,6)) + 7 max (7
(3a)
= max .'ES:
[R(s,')) + max Qi (((
(3b)
of
where Si,a, is any subset of Ss.a, including s'* = fenv ai
By reformulating the Q-value optimization over the set Si our approach allows for targeting the optimal value Q" (s, a;) under the true coordinated joint behavior, without directly approximating s* When there is no information about s'*, the set S;.a, could be set in principle to S.,a, if it were known, ensure the inclusion of s'a However, this will also make the maximisation over St,,; in Eq. (3b) more computationally challenging, implying trade off between reducing the size of Si and ensuring the inclusion of s't. We propose learning procodure that enables each agent to progrossively shrink their set of next states S all agents explore and accumulate experiences.
In practice, at the algorithmic step t, we work with a subset Sta.. which approximates one of the possible subsets S Since neither Ss.a, nor s'* are known practice duc to the incomplete information about other agents' policies and the environment dynamics, we cannot guarantee that 8"* E S S Sq,a: holds, but we will show in our performance assessment that s** E S.aat holds with high probability. Furthermore, direct. maximization over S is challenging as this set infinite in general.
To address this, we resort Monte Carlo optimization, as in e.g. Robert et al. 1999), by introducing a finite set. S.M S.h of M points randomly sampled from S. Assuming approximation error in the predicted
5

---

Published in Transactions on Machine Learning Research (11/2024)
QA
Figure 1: Illustration of the MMQ updale for two agents. Different positions of agents in the rounded rectangles represent different possible next states s' = (Ta. Ty), From the perspective of the blue agent: The yellow curve (P) represents the distribution of states with different yellow agent positions (zy) in the replay buffer. The red curve (Q) represents the estimated Q-values for those possible next states. In the MMQ update, the blue agent selects samples for update based on the highest Q-value, marked by v- Importantly, this selection may not always coincide with the most frequently encountered scenarios (corresponding to the peak of the ycllow curve) from past experiences, which may be sub-optimal.
bound, that is Sa,a. S Ss,a, holds, the sample SM s.a.. contains only reachable states and it follows that
(8, 2 max S'E s.ngi
R(s,8') +7yma Q7's', ((f)
(4a)
of
max mE(1....MM)
s(s + max (7( of)
(4b)
of
With the considered approach, there are two natural phases when running the associated algorithms:
1. With little information to rely on, the agents explore the state space at random and collect diverse trajectories, which improve their understanding of the range of possible next state Sa,,, In this phase, the estimated sets S3,ar. will be close to Sg.a.-
2. As agents refine their estimates of the set Sz.a; of possible next states and accumulate sufficient. reward information, the maximisation in Eq. 41b) yields increasingly stable values, facilitating policy convergence. This, in turns, means that the new trajectories will be more similar and optimised, progressively outnumbering the initial diverse trajectories. This will cause the sets S.,a,, to zero in on s'*, hence facilitating the Monte Carlo optimisation in Eq. (4b).
An illustration of our sampling and selection process shown in Figure ! given set of possible next state samples, our algorithm selects the state with the highest estimated Q-value for updating, which implicitly indicating the optimal action of other agents. As agents explore more possible actions, the estimated set Sa,a, increasingly approximates the true set S.,,, Crucially, if the optimal next stale is contained within the estimated set, the equality
Q (s. (s)) =
max S'ES..agd
A(s, max (7 df) o
holds. This property fundamental to our method, as implies that through iterative learning and effective sampling, each agent can learn Q-values that closcly align with those derived from ideal transition probabilitics. In the following section, we analyse the convergence properties of this approach under ideal conditions. The complete algorithm, including implementation details, will be presented in Section
4.2 Convergence analysis
Our combined learning and sampling approach facilitates the gradual convergence of the agents' policies toward the globally-optimal joint policy. This gradual convergence supported by the insights from the following theorem, which shows the disparity between the optimal Q-values and those learned by the agents

---

Published in Transactions on Machine Learning Research (11/2024)
is limited by the difference between the best next state in the estimated set and the true best next state. This bounding relationship is crucial, as it indicates that the closer our estimated set of next states is to the actual set composed of all the possible next states, the more accurate the estimations of the agents' optimal Q-functions become.
In this section, we further elaborate on this mechanism and provide a formal convergence analysis. This analysis demonstrates how our proposed model-based Q-eearning approach, combined with the sampling strategy, effectively facilitates convergence to an optimal global policy. We begin by showing that the difference between the Q-values learned by our approach and the optimal Q-values depends how well we can estimate the best next state.
Theorem 4.1. Let Sa.a, be the set of all possible next states as defined in ( and let $ be non-empty subset of Ss.a. Let 8 and 8 represent the best next states in the optimal and approzimate regimes, respectively, that
8" arg max R(s, )') + max (7()'ad)) d'ES.a,
d:
8"" arg max R(s, s') + max s'ES
Qi(s', a,)) of
Under Assumptions A.1 A.3 (see Appendir
B if the Euclidean distance d(s"", 8hr) at most e for all (s, as), then there erisls K such that [Q] (8,0s) Qi(s, a:)l (1 -)-- for all (s, ui).
The proof can be found in Appendix
B
In the context of our algorithm, we can relate this thcorem to our specific implementation. Omitting the algorithm step from the notations for simplicity, S in our case corresponds to SM s.a.' This set consists of M states uniformly sampled from Ss, as, which is itsclf non-empty subset of Ss, az. Sa,a, is formed by all possible outcomes predicted by our learned model. Figure P
illustrates the relationships between these sets.
This result demonstrates that if the distance between the estimated best next state g"* and the actual best next state s'* is arbitrarily small for all state-action pairs (s, (s, then the discrepancy between the learned Q-values Q: a:) and the optimal Q-values Q) (s, a.) is bounded. This implies that as we refine our estimation of the optimal next state through iterative sampling and learning, we progressively narrow the gap between the learned Q-values of our agents and the true optimal values.
Symi
Figure 2: Illssraatoon of the set relationship among Sa,a,, Sa,a and S (denoted as M above). The red star, s't, is the best next state in the real set, and g*x, and 8 represent the two states that are the closest to the best next states in Sa,e and SM s.a;" According to the triangle inequality, the distance between s"* and s'", d(s" S)), upper bound by the sum of d(s"* ""t) and d(s"*,8"
To better analyse the distance d(s',3'), we introduce a third state 3' as the best next state in S.a. This allows us to use the triangle incquality to upper bound the distance as d(s', 8') S d(s',8") d(s', 8')
The first. term, d(s',8") reflects the difference between the optimal next state in Sa,;; and the one in Sw As the size of Sa,, increases in the first phase of the algorithm, it's more likely to include states closer to s', thus decreasing d(s', 3¹). The second term, d(s', 33), represents the error in the Monte Carlo optimization. This error tends to be large initially but decreases in the second phase as S..a shrinks, making it easier to
7

---

Published in Transactions on Machine Learning Research (11/2024)
sample states close to 3. This analysis shows how our algorithm progressively improves its estimation of the optimal next state, contributing to the overall convergence of the Q-values.
Theorem 4.2. Assume that S = R and that Sa,a, is of the form [-u, u] for some u E (0, oo). Consider M i..dd samples 833...,888 from the uniform distribution on u, u]. holds that
2u
E
min
s/yl
<
M
M +
The proof can be found in Appendix B
This result demonstrates that the Monte Carlo optimization error d(8"", diminishes as the number of samples M increases. Incidentally, the Monte Carlo optimisation error could exhibit exponential dependence as the dimensionality of the state space increases. However, in multi-agent scenarios, partially-observe MDPs typically limit effective dimensionality growth, agents rely restricted view of the overall state spacc.
Seemingly, there is an inherent trade-off involved in expanding the state set Sa,a,, i.e., expanding in the above one-dimension case, to cover more possibilities while managing the resultant error. A broader Sa reduces the gap between 3 and the true best state s'*, as it increases the likelihood of encompassing s' This action effectively shrinks the error term ,(s"*, 8²)). Yet, increasing the size of S,,a; ie., increasing also typically increases variability, leading to larger error d(3"*, 88*) and necessitating more samples to maintain a given level of precision.
4.3 Implementation details
Algorithm 1: MMQ for each agent i
Input: Q-network Qi, actor network n; and target networks 2., क,; Quantile models g and g,"; Reward network RG; Replay buffer D;
for t I.... Tmax do
All agents interact with the environment using random action (for initial P steps) or e-greedy policy and store experiences (s, ag, r, s') in D,
Sample a mini-batch from D;; Update 9,'h and 9,"h by minimizing Draw M samples from predicted bound 1g, (-).9"" [.)] to construct set $
Calculate the target value over S uussin
Update Qi multiple times by minimizing
Update R2 by minimizing
Update x; by minimizing
Update the target network Q, and मे
end for
To capture the range of possible next states, our implementation utilises two non-parametrised quantile models, of and oi which employ neural networks to predict the 7 0.05 and тu 0.95 quantiles for each dimension of the next stale. The neural network parameters, denoted by of and Φ", learnt by minimising the quantile loss according to their respective values over samples from individual replay buffer D;:
L(Ø.) Es,a,,D, [L (gf (s, az 0.) s']],
where (T(u) = I(u > 0)ru+ + I[u < 0) (1(1-1]) r)u. For each (s, as) pair, the two quantile models predict bounds (s, a.), 9 - (s, a.)). We then construct the potential next state set Å by including the truc s' and M samples drawn from the quantile bounds. We also explored parametrised multivariate Gaussian model as another method to estimate the possible next states, detailed in Appendix
8

---

Published in Transactions on Machine Learning Research (11/2024)
Each agent also learns Q-network, parameterised by 0g. and represented as Qi(s, 0,) The target value for the Q-network update is given by:
(i(s, a;;0;) 0,) max max (3,58');)))) + max S'
(6)
"i
where [1(8, 8 (4)) is estimate from a learned reward model parameterised by th. Here apply a stop-gradient operator to the target value to prevent gradient flow back to the next state estimation process. This operation is crucial for maintaining stability in the learning dynamics by separating the optimization of the Q-network from the updates to the next state estimation. The loss function for optimising the Q-network parameter 0g is then given by
L(O,) = Ba, (Qi(s, a; 0,) as(
This loss aims align the Q-network's prodictions with the maximum expected return, considering both the immediate reward and the discounted future Q-values of the potential next states sampled from the estimated quantile bound. Additionally, the learned reward function Rs(s, s';))), parameterised by thi, is trained to approximate the rewards for state transitions. The loss for this reward model is the mean squared error between the predicted and actual rewards,
L(vi) = E,DD,
r]?
(8)
To deal with continuous action spaces, each agent uses an actor network 7s(s; parameterised by Ps, to learn its policy. The loss function for the actor nelwork, aimed at maximising the Q-value, is
M(p)) = EE,D, I- -i((,, (sss::))
(9)
The training process summarised in Algorithm ] and the full source code is available at https/////m//gg///////aa... Battmmxx___eeaannnge The full algorithm interleaves the optimisation of vari- ous constituent models, allowing agents to adaptively learn and improve their policies based on their own experiences and the evolving environmental dynamics. Our implementation incorporates two key strategies. First, delayed update approach for the actor network relative to the critic network, where the critic is updated 10 times more frequently to maintain stability (Fujimoto et al. 2018). Second, negative reward shifting (Sun et al. 2022), which enhances our double-max-style updates (see also Appendix C.1)
5
Experimental results
5.1 Environments
We evaluated the MMQ algorithm in three types of cooperative MARL environments characterized by the need for complex coordination among agents; see Figure 3 for an overview.
Differential Games We adapted this environment from Jiang & Lu 2022 where agents move within the range 1]. At each time step, an agent indexed by selects an action a; E [-], The state of this agent then transitions to clip(æ, + 0.1 a, -1, 13, where I; the previous state and the clip(y, Mmin Mmax) function restricts within [Vmin: |uma]] The global state is the position vector (21, The reward function, detailed in Appendix A assigns rewards following each action. A narrow optimal reward region is centred, surrounedd by wide zero-reward area and suboptimal rewards at the edges (see DG in Figure 3 This setup can lead to RO problems as agents might prefer staying in larger suboptimal areas.
Multiple Particle Environment We designed six variants of cooperative navigation tasks with RO rewards as shown in Figure 3 The common goal is for two disk-shapod agents, D, and D2, to simultancously reach a disk-shaped target. To encourage coordination, we introduce a penalty for scenarios where only one agent is within certain distance from the target. Specifically, define disk D centered the target with
9

---

Published in Transactions on Machine Learning Research (11/2024)
Cooperative navigation (CN)
CN More penaliy
CN + Hieterogemeooss targets (ITT)
Target
Target
Agent
Target 0
Agent
Target A
Agent
Agent
Agent
Agent
(a) Differential Game (DG)
CN Heteroogunoous
Predatur-Prey (PP)
Sequential tasks
Target 0
Prey @
Agent
Target A @
Target
Agent
19
Agent
Agent
Agent 0 Agent
(b) Half- Chif-Chectah 2x3
(c) MPF scenarios
wide zero-reward area to move to the center to gain the optimal reward. (b) Half- ChiffChhetthh 2x3: the Half-Cheetah 2x3 scenario in MAmujoco domain; (c) MPE scenarios; Cooperative navigation((N) two agents need to enter the grey area of the target together to gain the reward, the solo entry would induce a penalty. CN + More penally: Same task as CN but with more penalty for solo entry; CN + НT: Agents could choose to approach one the two Targets with different reward settings; CN+HA: same task as CN but two agents have different sizes and velocity; Pecdotor-PreyPPPP) two agents need to first go through the grey area of Target B and then enter the grey of Target A with the same RO reward design CN.
Figure 3: Task visualization. (a) Differential Game(DG): agents need to
two agents need enter the grey area of pre-trained prey. Sequential Task:
radius TD and penalize agents if only is within D. This setup is designed illustrate the RO problem, where agents might prefer staying outside D rather than risk being the only one inside it. The task difficulty increases the radius rp decreases. The reward function, designed to reflect the RO problem, is defined as:
Rin
if D.D D D 1,2
TCN
Rout
if (Di U D2) n D = otherwise.
Rout
The rewards for the three cases should satisfy Rout p < Rout < Rin- Detailed descriptions of Rout and Ran for different settings are provided in Appendix A In task CN, the penalty for solo entry into the circle is p 0.2; in task CN+More Penalty, the penalty increases to p = 0.5 for entering the circle alone; in task Hetroggnncss Agents (HA), two agents performing the CN task are heterogencous, having different sizes and velocities; in task CN Heterogenoous Targets (HT), there are two targets, where entering the circle of target follows the previous RO design, and entering the circle of target B incurs no RO penalty but offers reward lower than Ra,; in the sub-optimal scenario, agents might only enter the circle of target B; in task Sequential Task, agents must coordinate over longer period they could either directly reach target A with the same RO reward before first reach target B to pick up cargo, then receive a bonus each step (a higher Rin) when they later enter target A together; in task Predator-Prey (PP), two predators (which we control) and one prey, who interact an environment with two obstacles. The prey, trained using MADDPG (Lowe el al., 2017), adept al escaping faster than the predators. The predators need to enter the prey's disk together receive the reward R..-
Multi-agent MuJoCo Environment We employ the Half-Cheetall 2x3 scenario from the Multi-agent MuJoCo framework (de Witt al. 2020). This environment features two agents, each controlling three joints of the Half Cheetah robot via torque application. It presents partial observability setting, with each agent accessing only its local observations. We implement. RO reward structure designed to necessitate
10

---

Published in Transactions on Machine Learning Research (11/2024)
MMQ
HynDPS
InnsS
12Q
12Q
DG
CN
CN+ More penalty
CN+HT
-70
[lea Return
2
2 Sequential Took
Holf Cheetah
-20
Macnn Ratim
-172
-33
Mar
150
160
-15
-306
-1:0
-93
-100
Timesteps
16
Timesteps
Timesteps
Timesteps
Figure Performance comparison for two-agents setting DG, MPE scenarios and Half-Cheetah
high coordination between agents. The reward function r, is defined as: -7 v < v1 -9 if m S Vas and -2, otherwise; where t 0.035/dt, v., 0.04/dt dt, and dt 0.05, This structure rewards agents for moving forward at speeds exceeding tu: penalizes speeds between and Vay and provides moderate penalty for very low speeds. Agents failing to overcome the RO problem may settle for maintaining low speeds to avoid the harshest penalty.
Table 2: Settings with N agents. Mean Returns and 95% Confidence Interval (over eight seeds) for all algorithms at the end of training. Values are bolded if their confidence intervals overlap with the maximum value.
Setting
Setting
MMQ
IDPG
HyDDPG
12Q"
12Q
DG
N 2
19.5510.16
14.6744..11
19.17=0.17
17.8413.01
14.62-4.23
CN
-15.66+1.75
12.91-12.78
-19.12+ 1.56
-51.24+12.01
13..16+11.82
MPE Tasks
CN more penalty
-18.0142.24
-00.25-0.07
-5..12113.21
-60.55220.66
-60.5420.70
CN+HT
-24.2540.49
-40.34=26.01
-30.93:6.92
-56.04144.80
-35.95++15.83
CHAHA
-17.63.14.12
15.76-13.99
19.721
66.40.10.15
-00.25100.3
PP
-35.28.10.40
-6.66300.11
40..4017.18
57.10010.3
-56.6710.14
Sequential Task
-215.09++5999
295.31149.75
-33.555+
300.53+0.45
266.42-+43.37
Half-Cheetaih 2
-134.09+16.05
163.81+9.00
152.66+10.32
-155655++4600
-1 -140.44+8.55
Table 3: Setting with more than agents. Mean Returns and 95% Confidence Interval (over eight seeds)
for all algorithms the end of training. Values are bolded if their confidence intervals overlap with the maximum value.
Setting
Setting
MMQ
IDDG
HyDDPG
12Q
I2Q
N
3
19.5110.15
15.45.13.76
16.17
13.95
8.19.13.85
DC
N
20.09110.10
14.09114.22
12.77.14.56
16.3114.28
12.59114.45
=
20.44+0.11
13.94+4.227
16.02+33.97
16.91+3.30
2.98+0.70
CN (N=3)
-34.7912.75
-60.11117006
-45.47115.48
-50.86117.68
-54.89117.49
MPE Tasks
(N=3)
-37.86+1.01
-49.6442.14
46.16+44.84
-52.52+0.26
-51.86+0.95
5.2
Baselines
Our benchmarks include comparisons with three baseline algorithns: Ideal Independent Q-Learning (I2Q),
Independent Deep Deterministic Policy Gradient. (IDDPG), and Hysteretic DDPG (HyDDPG). We differ-
11

---

Published in Transactions on Machine Learning Research (11/2024)
M=1
M=
M=15
DG (N=4)
PP
Half-Cheetah
20.0
-35
17.5
-120
Mean Return
15.0
130
Sercestage
40
12.5
12.0
-50
7.
-160
-55
65
DG (N-4)
50
-170
25
-60
Half-Cheetah
Timesteps
165
Timesteps
le5
Timesteps
le5
Ireettps
(a)
(b)
Figure 5: (a) Ablation study for different sample number M three lasks; (b) Percentage of each dim of true next states fall within the predicted quantile bound for three tasks
entiate between two versions of T2Q: the original implementation by Jiang & Lu 2022 which refer to as 12Q*, involves multiple updates of all network components after every 50 interaction steps. In contrast, our implementation, denoted as I2Q, updates only the critic network multiple times every 50 steps. This distinction allows us to more accurately assess the performance impact of these differing update strategies.
5.3 Experiment Results
To compare the performance among different baselines, we consider the mean episode return over seeds, where the episode return is defined the accumulated reward Σ Tt for the whole episode, with T being the episode length.
Differential Games Our evaluations, depicted in Figure and Table 2 show that MMQ outperforms other algorithms with 15 samples drawn from the quantile bounds predicted by two quantile models. HyDDPG and 12Q" also perform well. Interestingly, the performance of HyDDPG and IDDPG surpasses that reported for 12Q in Jiang & Lu (022), possibly due to our implementation's emphasis on updating the critic netw more frequently than the actor network to stabilize training. However, 12Q learns much slower compared to 12Q', which updates all modules rather than just the critic multiple times. These update strategies have different effects on various algorithms. With more agents, the performance of other algorithms degrades slightly, showing higher variability, shown in Table 3 MMQ consistently identifies the optimal region in all test cases, demonstrating its higher sample efficiency and scalability. We also tested MMQ in stochastic version of this game (Appendix D.I.. D.I.. confirming that MMQ still outperforms the baselines under stochastic state transitions and reward dynamics.
Multiple Particle Environment As shown in Figure 4 and Table 2 our algorithm, using 15 samples from the predicted quantile bounds, successfully overcomes the Relative Over-generan gereraeneraiiitoonn (RO) problem in all settings. HyDDPG performs particularly well, especially in the lower penalty scenarios, such as CN, CN+HT, and CN+HA. In CN and CN+HT, 12Q" initially demonstrated some ability solve the task but its performance deteriorated over time. We observed that the learned Q-values of some seeds increased rapidly and incorrectly simultaneously, despite setting the weight of the (s, value to a minimal parameter during the update process. This might be due to the challenges in computing effective (s"(s values in 12Q, leading to less accurate predictions of optimal states and resulting in cumulative estimation errors over time. With a higher solo-entry penalty in CN+More Penalty, all baselines' performance significantly declines, remaining stuck suboptimal areas except for HyDDPG, which could learn a limited extent. Our sampling- based approach, however, demonstrates robustness even with the increased RO problem.
12

---

Published in Transactions on Machine Learning Research (11/2024)
PP presents a more challenging task compared to the above settings due to its larger state space, more agents, and fast-moving prey that the predators must catch. Our results, illustrated in Figure $ show our algorithm successfully overcomes the RO problem, demonstrating higher mean return and greater sample efficiency than other basclines.
In the Sequential Task, both our MMQ and HyDDPG initially learned to enter target directly. After discovering that entering target B could yield a bonus, they deliberately targeted B, which led to a temporary decline in performance. MMQ recovered quicker than HyDDPG. I2Q began to show learning towards the end of the training while IDDPG failed in this task.
We also tested our algorithm in the CN and PP settings with an additional agent (as shown in Table 3 With one more agent, the state dimension increases and the transition dynamics become more complex. In CN with three agents, the results for HyDDPG and 12Q" showed large variability, indicating that these methods were effective only under certain initial conditions. In PP with three agents, which is more challenging, all baselines were stuck in suboptimal areas. However, our algorithm still managed to overcome the RO problem, demonstrating scalability with an increased number of agents. Further tests with the default reward setting (detailed in Appendix D.2 show that our algorithm matches the performance of other baselines in settings without significant RO problems.
Multi-agent MuJoCo environment In this setting, we also utilized 15 samples drawn from the predicted quantile bounds. As depicted in Figure | MMQ remains competitive in this challenging environment, consistently surpassing other baselines during the latter half of the training period. Given the inherent complexity of the task, we maintained mild level of the RO problem preserve feasibility. This explains why 12Q was able to perform well, despite its sensitivity to RO problems noted in other environments. We provided results for one more partitions of Half-Cheetah (Half-Cheetah 4|2) and two partitions of Ant. (Ant 2 x 4 and 4 x 2) with the same reward setting in Appendix D.3 In these tasks, MMQ consistently outperforming other basclincs.
A Ablation study: number of samples We conducted an ablation study to investigate the effect of varying the number of samples across three different environmental settings, as shown in Figure 5a| The results demonstrated that MMQ, even with just one sample, outperformed baselines in the DG and Chef-Cheetahh environments. In the PP environment, using one sample was slightly less effective than HyDDPG, but using three or more samples consistently outperformed all baselines. Additionally, increasing the number of samples M appeared to accelerate learning across the three settings, aligning with our theoretical analysis. Furthermore, we included a study (see Appendix C.2) that employed a small ensemble of quantile models. Although this ensemble enlarged the predicted bounds and enhanced the percentage of true next states within these bounds, as shown in Figure [b]] it did not lead to further performance improvements. Thus, we did not incorporate the ensemble approach in the final results for simplicity.
To demonstrate the effectiveness of the quantile model, Figure 5b shows the percentage of cach dimension of the true next states that fall within the predicted quantile bounds during the learning process for three environment settings. The percentage is calculated as follows: For each sample in the mini-batch, consisting of n samples, during the update process, we have the predicted bound [la, ua] for each dimension d of the state with value sa. The state has total of D dimensions. If the state value sy falls within the prodicted bound, i.e., la S 8a S ud; we increment count. If the total count. across all dimensions and samples is P, the percentage is then calculated as ' 100%.
The percentage is already high initially for the DG and CN environments but is a bit lower for Chlf-Cheetah, possibly due to its more complex dynamics compared to the other two. These results indicate that the quantile model can effectively capture most state changes as expected, suggesting that S.,, closely reflects the true set Saaa, as analyzed in Section 4.1
6 Discussion and Conclusions
In this work, we introduced MaxMax Q-learning (MMQ), a novel algorithm designed mitigate the Relative Over-generalisation problem in multi-agent collaborative tasks through the use of quantile models and
13

---

Published in Transactions on Machine Learning Research (11/2024)
optimistic sampling. Our key theoretical contribution establishes connection between the accuracy of estimating the best next state and the convergence towards globally optimal joint policies within the MMQ framework, providing a solid foundation for understanding the algorithm's behaviour and performance.
Empirically, we demonstrated the effectiveness of MMQ across three diverse tasks, showing its ability to outperform existing baselines terms of convergence speed, sample efficiency, and final performance. A notable outcome is MMQ's scalability, it can accommodate an increased number of agents while achieving superior performance with minimal samples, which reduces computational overhead crucial factor in practical multi-agent systems.
Despite these promising results, several limitations of MMQ remain. First, the Monte Carlo optimisation error in MMQ may exhibit. exponential dependence as the dimensionality of the state space increases. However, this issue somewhat mitigated in multi-agent settings, where the use of partially-observed MDPs limits the effective dimensionality. Second, although MMQ has demonstratod scalability our experiments, challenges may arise in environments with very large populations of agents, where increased computational costs and coordination complexity could impact performance.
Looking ahead, future work may aim to address these limitations and further enhance MMQ's capabilities. One promising direction involves developing adaptive mechanisms to gauge the informativeness of observations about other agents, which could improve the robustness of reward function learning, especially in scenarios with partial or noisy observations. Additionally, relaxing the current assumption independence across dimensions in the quantile model by predicting the covariance matrix could capture more complex state dynamics, potentially leading to more accurate estimations. Further improvements in scalability might be achieved by reducing the number of samples required the state space grows, thereby lowering computational demands in high-dimensional and large-agent scenarios. Together, these future developments aim to overcome current limitations and extend the applicability of MMQ to broader range of multi-agent scenarios.
Acknow/cdgmeents TZ acknowlodges support from the UK Engineoring and Physical Sciences Research Coun- cil (EPSRC EP/ W523793/1), through the Statistics Centre for Doctoral Training al the University of Warwick. GM acknowledges support from UKRI AI Turing Acceleration Fellowship (EPSRC EP/V024868/I).
Broader Impact Statement
This paper presents work whose goal is to advance the field decentralized lcarning of multi-agent systems. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
References
David Baldazo, Juan Parras, and Santiago Zazo. Decentralized multi-agent deep reinforcement learning in swarms of drones for flood monitoring. In 2019 27th European Signal Processing Conference (EUSIPCO), pp. 1-5. IEEE, 2019.
Sumeet Batra, Zhehui Huang, Aleksei Petrenko, Tushar Kumar, Artem Molchanov, and Gaurav S Sukhatme. Decentralized control of quadrotor swarms with end-to-end deep reinforcement learning. In Conference Robot Learning, pp. 576-586. PMLR, 2022.
Ana LC Bazzan. Opportunities for multiagent systems and multiagent reinforcement learning in traffic control. Autonomous Agents and Multi-Agent Systems, 335, 2009.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359((374))418-422) 4444, 2018. doi: 0..112//sceence.aaol URL https: ://www//wwwww
science wwtpooo/ag//oooooooooooooo http:/bbb//0.11112/siieeeee a aao1733
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 2018.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Christian Schroeder de Witt, Bei Peng, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. Deep multi-agent reinforcement learning for decentralized continuous cooperative control. arXiv preprint arXiv:2003.06700 19, 2020.
Stefan Depeweg, Jose Miguel Hernandez-Lobato, Finale Doshi-Velez, and Steffen Udluft. Learning and policy search in stochastic dynamical systems with bayesian neural networks. Xiv preprint orXiv:605.007127
2016.
Jakob Foerster, Toannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances in neural information processing systems, 29, 2016.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International conference machine learning, pp. 1587 1596. PMLR, 2018.
Tarun Gupta, Amuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. Uneven: Universal value exploration for multi-agent reinforcement learning. In International Conference on Machine Learning, pp- 3930-30 3941. PMLR, 2021.
Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A survey of learning in multiagent environments; Dealing with non-stationarity. In 2017 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp. 1164 1170. IFAMMAS, 2017.
Jiechuan Jiang and Zongqing Lu. 12q: A fully decentralized q-learning algorithm. Advances in Newral Information Processing Systems, 35:20469 20481, 2022.
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? Aduances in neural information processing systems, 30, 2017.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty ostimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Martin Lauer and Martin A Riedmiller. An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In Proceedings of the Seventeenth International Conference on Machine Learning, pp. 535 542, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.
Shanqi Liu, Dong Xing, Pengjie Gu, Xinrun Wang, Bo An, and Yong Liu. Solving homogeneous and heterogeneous cooperative tasks with greedy sequential execution. In The Twelfth International Conference on Learning Representations, 2024. URL https://openrrviiet hett/forumidd-hhiittxxl
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Picter Abbool, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compelttie environments. Advances in neural information processing systems, 30, 2017.
Laëtitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Hysteretic q-learning: an algorithm for decentralized reinforcement learning in cooperative multi-agent teams. In 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 64 69. IEEE, 2007.
Laetitia Matignon, Guillaume J Laurent, and Nadine Le Port-Piat. Independent reinforcement learners in cooperative markov games: survey regarding coordination problems. The Knowledge Engineering Review, 27(1):1-31, 31, 2012.
Tan Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, pp. 4026 4034, 2016.
Gregory Palmer, Rahul Savani, and Karl Tuyls. Negative update intervals in deep multi-agent reinforcement learning. Xi preprind arXiv: wtw.180.0000000 0009000 2018.
Liviu Panait. The analysis and design of concurrent learning algorithms for cooperative multiagent systems. George Mason University, 2007.
15

---

Published in Transactions on Machine Learning Research (11/2024)
Liviu Panait, Sean Luke, and R. Paul Wiegand. Biasing cocvolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolulionary Compulation, 10(6):629-60 -45,,9999,5--- 2006.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whitcson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseorch, pp. 4295 4304, PMLR, 10-13 15 Jul 2018.
URL https:://proceedingg mlr. wttp:/s......p.seeeessss.. arress//80/rashhd1153 html
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function lactorisation for deep multi-agent reinforcement learning, Advances in newral information processing systems, 33:10199-10210, 2020.
Christian P Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume Springer, 1999.
A. Sahraoui, M. Boulmalf, and A. Tahri. Schodule-basod cooperative multi-agent reinforcement learning for multi-channel communication in wireless sensor networks. Wireless Personal Communicaaiins,, 120(1): 429 447, 2021. URL 08362-6.
DOL: 10.1007/s11277-0221
Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervised world models. In International Conference on Machine Learning, pp. 3583-8592 PMLR, 2020.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. Xixiv preprint orXiv: 161000395,, 2016.
Lin Shi and Bei Peng. Curriculum learning for relative overgeneralizatton. arXiv preprint ar1::22112.02739, 2022.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International conference on machine learning, pp. 5887 5896. PMLR, 2019.
Georg Still. Lectures on parametric optimization: An introduction. Optimization Online, pp. 2, 2018.
Kefan Su and Zongging Lu. A fully decentralized surrogate for multi-agent policy optimization. Transactions Machine Learning Research, 2023.
Hao Sun, Lei Han, Rui Yang, Xiaoteng Ma, Jian Guo, and Bolci Zhou. Exploit reward shifting in value-based deep-rl: Optimistic curiosity-based exploration and conservative exploitation via linear reward shaping. Advances in Neural Information Processing Systems, 35:87719-37734, 2022.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. Tn Proceedings of the
Tenth International Conference on Machine learning, pp. 330-337, 1993.
Liang Wang, Kezhi Wang, Cunhua Pan, Wei Xu, Nauman Aslam, and Lajos Hanzo. Multi-agent deep reinforcement learning-basse trajectory planning for multi-uav assisted mobile edge computing. IEEE Transactions Cognitive Communications and Networking, 7(1):73-86 2020.
Ermo Wei and Sean Luke. Lenient learning in independent-learmer stochastic cooperative games. The Journal of Machine Learning Research, 17(1):291442955, 2016.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. arXiv preprint vrXiv:1804.09811 2018.
Rudolf Paul Wiegand. An analysis of cooperalive coevolutionary algorithms.. George Mason University, 2004.
16

---

Published in Transactions on Machine Learning Research (11/2024)
Yue Wu, Shuangfei Zhai, Nitish Srivastava, Joshua Susskind, Jian Zhang. Ruslan Salakhutdinov, and Hanlin Goh. Uncertainty weighted actor-critic for offline reinforcement learning. arviv preprint ar 2021.
Jing Xu, Fangwei Zhong, and Yizhou Wang. Learning multi-agent coordination for enhancing target coverage in directional sensor networks. Advances in Neural Information Processing Systems, 33:10053-10064 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in Neural Information Processing Systems, 35:24611-24622 2022.
M. Zhou, X. Ma, and Y. Li. A novel multi-objective routing scheme based on cooperative multi-agent reinforcement learning for metaverse services in fixed 6g. In WOCN, 2023. URL https://dblp..nn org rec/ conf/wocc//houMM22 DOI: 10.1109/WWa WWCC52294 2003.0009..
Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, Iman Fadakar, Zheng Chen, Chongxi Huang, Ying Wen, Kimia Hassanzadeh, Daniel Graves, Zhengbang Zhu, Yihan Ni, Nhat Nguyen, Mohamed Elsayed, Haitham Ammar, Alexander Cowen-Rivers, Sanjeevan Ahilan, Zheng Tian, Daniel Palenicek, Kasra Rezace, Peyman Yadmellat, Kun Shao, dong chen, Baokuan Zhang, Hongbo Zhang, Jianye Hao, Wulong Liu, and Jun Wang. Smarts: An open-source scalable multi-agent rl training school for autonomous driving. In Jens Kober, Fabio Ramos, and Claire Tomlin (eds.), Proceedings of the 2020 Conference on Robot Learning, volume 155 of Proceedings of Machine Learning Research, pp. 264-285. PMLR, 16-18 Nov 2021.
Changxi Zhu, Mehdi Dastani, and Shihan Wang. A survey of multi-agent reinforcement learning with communication. Xiviv preprint arXiv:220300800 2022.
17


Reviews:
[{"review_id": "owqjqUfMry", "reviewer": "Reviewer_sjZT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- I want to preface this by acknowledging that I am not an expert on multi-agent reinforcement learning, but the studied problem and the challenges in RO and non-stationarity (from each agent's perspective) seem interesting, well-motivated, and relevant to the community.\n- The proposed mechanism integrates new techniques from sampling and uncertainty quantification into the existing approach of implicit coordination through modeling ideal transition probabilities.\n- The theoretical results offer insights into how accurately estimating the best next state is connected to learning the optimal policy.\n- An empirical study in three different environments shows superior performance in comparison with three benchmark algorithms.\n\nWeaknesses:\n- Despite the authors' efforts to explain the intuitions behind the methodology, the paper can be somewhat difficult to follow in parts. For example, it is unclear what exactly the agents can communicate in this decentralized setting -- do they observe the actions of other agents? Additionally, Figure 1 mentions a replay buffer, but this is not discussed elsewhere in the paper. Furthermore, the pseudocode (with details such as the use of $\\epsilon$-greedy) is deferred to the appendix -- while I can generally grasp how the approach works, it can be hard to fully understand where each part fits into the mechanism; it would be helpful to include a high-level description of the algorithm in the form of pseudocode in the main paper.\n- The theoretical analysis is a nice addition, but it does not seem to fully demonstrate convergence to the optimal joint policy. In particular, can one formally show how (fast) $\\hat{\\mathcal{S}}_{s,a_i}$ shrinks and zeros in on $s'^{*}$? \n- The experiments used environments with hand-crafted reward functions that may lead to RO. It would be nice to evaluate the approach in more realistic or real-world settings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies multi-agent reinforcement learning in a decentralized setting. Without explicit coordination, each agent may select actions based on how they expect the others to act, which may not be collectively optimal and can lead to relative over-generalization (RO). To address this challenge, the paper proposes a mechanism that introduces implicit coordination by guiding the agents towards the optimal joint policy, utilizing Q-learning, Monte Carlo optimization, and quantile models. The paper gives some theoretical justification towards understanding why this approach may work, and then provides an empirical evaluation in three environments that are designed to induce RO problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I've listed some suggestions above. In addition:\n- How should one determine the duration of each phase, specifically $T_\\text{pretrain}$?\n- The discussion of \"non-stationarity\" in Section 1 can be a bit confusing, as it may suggest that $P_\\text{env}$, instead of $P_i$, changes over time. This only becomes clearer to me after the problem setting is introduced in Section 3.\n- There are some typos and grammar mistakes in Section 3.1.\n- The caption of Figure 1 is confusing -- what does the yellow agent’s \"position\" mean? What does it mean for the blue agent to \"select\" samples?\n- What aspects of Theorem 4.1 are specific to the multi-agent setting? Can it be applied to single-agent RL?\n- For Theorem 4.2, would there be an exponential dependence if the states are in a higher-dimensional Euclidean space?\n- It is mentioned in Section 1 that the theoretical results assume \"perfect knowledge of forward and value functions.\" Can you elaborate on this?\n- In Equation (5), what is the definition of $D_i$?\n- In the experiments, it would be nice to include a formal definition of \"return\".\n- Why is the approach called MaxMax?\n- Can you further discuss the setting and results in (Jiang & Lu, 2022) and how the proposed approach in this work differs?", "broader_impact_concerns": "Nothing specific.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "N8vbzZfKID", "reviewer": "Reviewer_VGaS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\nThis paper is well-structured, presenting clear motivations and solution methods. This work provides detailed theoretical results and illustrative visualizations.\n\n## Weaknesses\n### Methodology\n\nIn Eq.6, there is no stop-gradient operation applied to the target value?\n\n### Experiment\nI encourage the authors to perform more comprehensive experiments on the complex MA-Mujoco benchmark. The work only includes the Half-Cheetah 2x3 task. More tasks such as Half-Cheetah 6x1, and Ant 2x4/4x2 are also suitable evaluation scenarios by implementing the RO reward in a similar way.\n\nMMQ demonstrates the best overall performance, yet it only outperforms all baselines in two tasks. This also necessitates more experiments in MAMujoco tasks to better support their claims.\n\n### Writing\nSec 1, \"...may encounter scalability and privacy issues\". CTDE methods do not necessarily gather local information from all agents. Some approaches could directly utilize global state information, thereby circumventing the scalability issue. Also, whether the privacy issue is considered in practice depends on the task. Task completion in many domains is not concerned with privacy.\n\nI suggest the authors motivate decentralized learning with another example. The mixed autonomous traffic example does not necessitate gathering information or communicating with *all* agents. In practice an agent only needs to focus on its surroundings and ignore others.\nIt is worth noting that CTDE and communication allow information exchange, but it does not mean every CTDE/communication method must utilize information from the entire population.\n\nSec 2. in the first paragraph, the weighted QMIX work is cited as the QMIX paper. \n\nSec 3.1, typo in the individual dynamics equation: $\\mathbf{a}-i$ should be  $\\mathbf{a}_{-i}$ under the summation symbol.\n\nSec 4.1, on page 5, first sentence of the second paragraph repeats the last sentence of the first paragraph.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces MaxMax Q-Learning (MMQ), a novel method designed to mitigate the issue of relative over-generalization (RO) in decentralized multi-agent reinforcement learning. MMQ addresses RO by iteratively sampling and evaluating potential next states, selecting those with the maximal Q-values.\nMMQ refines approximations of ideal state transitions. This work provides a theoretical analysis demonstrating MMQ’s potential to converge to globally optimal joint policies under certain assumptions. \nEmpirical evaluations across various environments prone to RO show that MMQ demonstrates stronger overall performance than existing baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LG4veJsvtl", "reviewer": "Reviewer_PxMX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nMMQ introduces a new approach to address the RO problem, enhancing convergence and sample efficiency.\n\nThe paper provides both theoretical analysis and empirical evaluations demonstrating MMQ's effectiveness across various environments.\n\nThe experiments results are good and adequate to show the effectiveness of the paper.\n\nQuestions:\n\nIn my understanding, to get the maximum expected return will also face a scalability problem, how did you solve that? \n\nHow does the computational complexity of MaxMax Q-Learning (MMQ) compare to traditional Q-learning in large-scale multi-agent environments, and what are the specific computational trade-offs?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces MaxMax Q-Learning (MMQ), an algorithm designed to mitigate RO by sampling and evaluating potential state transitions and selecting those with maximal Q-values. This process aims to refine approximations of ideal state transitions and align more closely with optimal joint policies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the questions in the previous session.", "broader_impact_concerns": "Broader Impact is stated in this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an algorithm to address "relative over-generalization" (RO) caused by fully-decentralized actors. From the paper:

"Another critical issue in decentralized MARL is Relative Over-generalization (RO), where agents prefer suboptimal policies because individual actions seem preferable in the absence of coordinated strategies."

I find this to be a peculiar name for this phenomenon. Why is this about "generalization" at all -- where is the generality here? If anything, the agents are *overfitting* to their (incorrect) local assumptions. They're all independently solving the "wrong" problem. One could argue that MMQ is making them "more general" by considering the wider problem rather than the agents fixating on a local sub-problem, so this can be lead to confusion. If this is a new term being proposed in this paper, I would advise a careful reconsideration, or at least some justification in the text for why generalization is in the name.

Aside from this, the paper presents an algorithm that addresses the problem, both in theory and practice. The reviewers had a number of comments and criticisms regarding technical clarity which have been addressed in the new versions.

The reviewers remain skeptical about the limited experiments and scaling potential as the population grows. I recommend briefly describing the limitations in its own section or subsection to elaborate on any points or settings that could be problematic from a potential user's perspective.
Decision: Accept (poster)