AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimation

Summary

the paper presents a novel approach, AlberDICE, an offline MARL algorithm that performs centralized training of individual agents based on stationary distribution optimization, to tackle the distribution shift challenge in offline MARL. The proposed method avoids OOD joint action selection by computing the best response of one agent at a time, thereby circumventing the exponential complexity of MARL. The authors provide theoretical proof of convergence to Nash policies and demonstrate through experiments that AlberDICE outperforms baseline algorithms on standard MARL benchmarks.

Strengths

1. It proposes a novel solution to address the distribution shift problem in offline reinforcement learning by performing centralized training of individual agents and optimizing the stationary distribution. This approach effectively mitigates the issue of excessive distribution shift in offline multi-agent reinforcement learning. 2. The authors avoid the exponential complexity challenge in multi-agent reinforcement learning by computing the best response of individual agents in a sequential manner, reducing the computational burden. 3. The paper provides theoretical proof of convergence to Nash policies through the alternating optimization process, offering a theoretical guarantee for the effectiveness of the algorithm. 4. Experimental results demonstrate that AlberDICE outperforms baseline algorithms significantly on standard multi-agent reinforcement learning benchmarks, validating the performance and effectiveness of the algorithm.

Weaknesses

1. This paper considers the other agents’ policies are fixed and optimized based on the distribution correction technique. However, what if the data set contains multiple cooperation strategies? 2. Even though there are many derivations in Section 3, many are derived from existing work [1-3]. Section 3 should be simplified to highlight the contribution of this work. 3. This works adopt BC(Behavioral Cloning) to learn \pi^D_{-i}. When the quality of the data set is not high, such as the medium data set, the effect of BC is very poor. Will this affect the performance of the algorithm? 4. There is little discussion on the limitations and applicability of the algorithm, and there is a lack of in-depth exploration of special cases or problems, which may restrict the generalization and application of the algorithm. 5. Necessary ablation experiments are required, such as the robustness of parameters, the selection of network models, etc.

Questions

Please refer to the weakness.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

This paper proposes a new algorithm called AlberDICE for addressing the challenge of out-of-distribution joint actions in offline Multi-Agent Reinforcement Learning (MARL). The proposed algorithm performs centralized training of individual agents based on stationary distribution optimization, which circumvents the exponential complexity of MARL by computing the best response of one agent at a time while effectively avoiding OOD joint action selection. The authors show that the alternating optimization procedure converges to Nash policies theoretically and demonstrate that AlberDICE significantly outperforms baseline algorithms on a standard suite of MARL benchmarks in experiments.

Strengths

- Nice writing flow for solving the original LP problem. The paper provides a clear and concise explanation of the proposed approach and its implementation. - AlberDICE is shown to produce much stronger policies than baselines in experiments conducted in many multi-agent environments.

Weaknesses

- Since $\pi_{-i}$ is fixed, the process in Section 3 is quite similar to that of OptiDICE, including Lagrangian formation, the closed-form solution, and I-projection used in policy extraction. Also, the distribution shift/OOD problem is solved by the series of DICE. It weakens the contributions of this paper. - The key point for AlberDICE is Theorem 4.2 which NE can be achieved. However, it is theoretically unclear to me why after the optimization, the inequality between lines 591-592 in the appendix holds. Let's consider an extreme case in the Rock Paper Scissors game. If the dataset only contains draw cases, how does AlberDICE reach NE? Maybe Theorem 4.2 lacks the necessary assumptions. minors/typos - "+" before the second line of eq.5 - In line 188, "pretrained." -> "pretrained," - "=" before eq.16 -> "$min_{\pi_i}$"

Questions

- $x$ in eq.10-14 is sample $(s, a, s')$, $e_v$ is also a function of $(s,a)$. How eq.14 is state-dependent instead of state-action-dependent?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The paper does not explicitly mention any limitations of the proposed method. The paper has no potential negative societal impact.

Summary

In this paper, the authors propose an alternative multi-agent offline reinforcement learning algorithm, where each agent is optimized for the best response policy and avoiding the out-of- distribution joint actions. The theoretical part proves the nash policies convergence after the presented training paradigm. The empirical results show promissing results on several well- known environments over existing offline MARL algorithms.

Strengths

● The paper is well-written and easy to follow. ● The theoretical results show the Nash policy convergence which integrates the trackable theory, relaxing the conventional IGM regularization. ● The joint-action problem is novelly addressed in the offline MARL algorithm.

Weaknesses

● The solution of the XOR game shown in the introduction for IGM-based and decentralized methods may not converge to (B,B) from the reviewer's perspective. These two categories of methods will connect the agents' policies by the mixing network for example, which is not totally individually be executed. ● The claim from the authors for circumventing the curse of dimensionality in MARL is somewhat overclaimed. The curse of dimensionality also includes the explosion in the joint policy space due to the increasing agent number.

Questions

See the weakness part.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

In the practical scenarios, the observation and action space may have some noise that is not computable and may obstacle to the presented method.

Summary

The authors consider the offline multi-agent reinforcement learning setting. They provide an example to demonstrate that decentralisation can lead to out of distribution actions at test time. They derive AlberDICE, an offline RL method based on computing alternating best responses to the other agents' policies. Starting from the linear program for an MMDP, they learn a policy by: 1. Pretraining a data policy $\pi^D_{-i}(a_{-i} | s, a_i)$ 2. Using the current policy and current data policy to resample the dataset 3. Solve a minimisation problem to find $\nu^*$ 4. Extracting the policy from $\nu^*$ using I-projection. This method prevents out of distribution actions by optimising each agent alternately and assuming the other agents' policies are fixed. A KL penalty is used to ensure that the resulting learned policy stationary distribution stays faithful to the dataset's distribution. By alternately optimising each agent, issues of producing out-of-distribution actions due to simultaneous updates do not arise.

Strengths

Overall I enjoyed reading this paper. In particular: * The paper evaluates their algorithm on a wide range of domains and performs strongly across most tasks. * The authors explain the problem setting clearly and point out some problems with naive approaches to the problem. * The paper is generally well-written and clearly presented.

Weaknesses

While the paper is good overall, there are some weaknesses of the work. * It would have been nice to see an explicit demonstration that the proposed method reduces out-of-distribution actions in the more complex environments and therefore that the mechanism proposed is the reason for the better performance. * The evaluations mostly focus on a small number of agents ($\leq 10$). * Although the authors evaluate on a wide range of domains, they only evaluate on a small number of SMAC maps. This is a well-documented problem with MARL evaluation [1]. * The discussion in lines 125--131 doesn't seem to make clear the presence of the KL penalty term in (2). For example, $\pi^*$ is only the optimal policy *for the MMDP with a penalty as the reward*. Adding a few words in key places clarifying this point would make this section easier to read -- I was a little confused on first reading. [1] Gorsane, Rihab, et al. "Towards a standardised performance evaluation protocol for cooperative marl." Advances in Neural Information Processing Systems 35 (2022): 5510-5521.

Questions

I have a few clarifying questions. - How does the method scale to larger numbers of agents? Is the relatively small number of units in each scenario because of computational constraints running this method for more units? - In equation (4), the $\pi_{-i}(a'_{-i} | s')$ from equation (3) seems to have disappeared. It reappears later in equation (5) so I think this is just a typo. Is this correct or have I missed a detail here?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The author discuss the limitations briefly in the appendix. The discussion there seems fine to me but of course more discussion of limitations is always appreciated.

Summary

This paper introduces the AlberDICE framework that targets to address the out-of-distribution challenge (or distributional shift) in off-policy MARL. AlberDICE addresses this challenge by the alternating optimization procedure along with the regularization term. Also, AlberDICE addresses the curse of dimensionality in multi-agent settings with the autoregressive policy architecture. Empirical evaluations show that AlberDICE can find a more optimal solution than baselines in multiple multi-agent benchmark domains.

Strengths

1. Theoretical contribution about showing how AlberDICE converges to a Nash equilibrium. 2. Evaluations are performed across multiple domains, showing the empirical evidence of AlberDICE.

Weaknesses

1. A possible concern about alternatively finding the best response policy while fixing others is that this approach effectively solves a static single-agent problem from each agent's perspective. As a result, in some cooperative settings, this method may learn some sub-optimal joint collaborative policy. 2. Related to #1, the approach of alternatively finding the best response may not work or be effective in competitive/mixed-sum game settings, limiting the scope of the proposed method.

Questions

In addition to my concerns in the weaknesses section, I would like to ask the following questions: 1. I appreciate the intuitive example (Figure 1) in the Introduction. If a centralized critic is employed with a decentralized actor, would the sub-optimality problem still happen? 2. Section 3 states that "when each agent is optimized alternatively, the objective function will always be monotonically improved and convergence is guaranteed." Would there be a proof or reference to this statement? 3. Related to #2, while the monotonic improvement is guaranteed, would convergence to an optimal (Nash) equilibrium be guaranteed? 4. According to Levine et al., 2020, the main challenge of off-policy learning is the distributional shift: a policy is trained under one distribution and it will be evaluated on a different distribution. In the evaluation section, it is unclear whether the learned cooperative policies are evaluated under a different distribution/environment/setting compared to the training dataset. 5. Because the authors focus on cooperative settings, wouldn't it be better to target to converge to a correlated equilibrium instead of a Nash equilibrium as correlated equilibria are a superset of Nash equilibria (i.e., possible to converge to a more optimal solution). Reference: Levine et al., Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems, 2020

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes, the authors have adequately addressed the limitations.

Urgent request to engage

Dear Reviewers 82R1and 5Yz6, Please urgently engage in the discussion phase, since it is coming to the end. The authors provided detailed responses to the points raised as well as additional experimental evaluations. It is absolutely vital that these datapoints are carefully considered in the process. Many thanks! AC