Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Summary:
Extrapolation error is a vital issue in offline reinforcement learning, and this paper addresses its impact and solution on both the single-agent and  multi-agent scenario. The paper analyzed the root cause of extrapolation error with Batch Constrained Q learning as a starting example by analyzing the Bellman-like extrapolation error propagation. The state action transition pairs are divided into seen to unseen, seen to seen, unseen to seen, and unseen to unseen.
The authors further showed that the extrapolation error accumulated with the growth of number of agents, both theoretically and with a toy example.
To address the issue, the authors proposed a constrained optimization objective where the constraint is KL divergence between the policy to be optimized and the behavioral policy, using this objective, the author derived the off-policy important sampling weight that does not involve the policy to be optimized, and the IS is used to regulate the critic loss, while the actor is learned through the IS weighted log policy probability. Similar to the Q function decomposition in  VDN, the author decompose the extrapolation error and policy agent wise, and use centralized training and decentralized execution. Different from VDN, the author proposed to use a mixture network to generate weight to decompose the Q function, where the weight is also conditioned on state.

The multi-agent ICQ is evaluated on Starcraft benchmark, and the single agent version is evaluated on the D4RL task. Both seem to gain improved performance compared to baselines.

The multi-agent ICQ is evaluated on Starcraft benchmark, and the single agent version is evaluated on the D4RL task. Both seem to gain improved performance compared to baselines.

main_review: These issues should be addressed:
1. In Section 4.2.1, in the inline equation in the second line, what is $o$?

2. In Figure 4, the behavioral cloning overrate the rest of the competitor algorithms except ICQ-MA, which seems to be due to the deterministic nature of the SMAC environment. Thus, the success of ICQ-MA seems to be a weighted loss trading off the behavior cloning error and the implicitly constrained Bellmann error. That means, if ICQ-MA does not exist, behaviorial cloning is the best way to do multi-agent offline RL?

3. I feel there is a lack of explanations to the theorems in the main text, one has to go to the proof to understand what is the intention, although some details can be guessed, but it might be better for them to be elaborated in the main text.

4. The partition function Z is approximated in a min-batch, is there some analysis on the potential effect? How is Z calculated exactly?

5. Eqn (11), the loss is the KL divergence between $\pi_{k+1}$ and $\pi_{\theta}$, taking expectation with respect to the state distribution of the behavior policy, can this be roughly described as making as little change to the current policy?  


6. In the derivation of Eqn (11) in step (a), the entropy term of $\pi_{k+1}$ is dropped in the optimization due to it is not related to $\theta$, I have not fully understood why this entropy part has no theta involved?


limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary:  
The paper focuses on the distribution shift issue of offline RL in multi-agent systems. It is an important problem because 1. Offline RL trains on a fixed dataset and thus is hard correct the overestimation error of the Q function on unseen (s,a) pairs. 2. Offline RL multi-agent environment is an under-explored area. 
 
The paper first proved that under some assumptions (including 1. all agents share the same reward function. 2. the joint value function can be decomposed into value functions across agents) the extrapolation error grows linearly with the number of players. Current SOTA offline RL methods such as BCQ is shown to perform poorly under this setup.
 
The authors proposed ICQ, a general offline RL algorithm that only trusts the (s,a,r,s’,a’) pairs from the collected data and uses an estimation of the importance sampling ratio to learn the Q value of the policy under training. They then extends ICQ to the multi-agent setting (ICQ-MA). The algorithms are evaluated first on a toy tabular multiplayer environment, then on several StarCraftII two-player mini-games and on the single-agent D4RL tasks. The experiments showed that ICQ and ICQ-MA do not suffer from exploding Q values and overestimation. It outperforms other Offline RL and Off-policy RL baselines.


main_review:  
The proposed method ICQ for single-agent RL bears some resemblance to AWR and the main novelty comes from the critic loss, where the target Q(s’, a’) is reweighed by the importance sampling weight. The paper had a good theoretical analysis of most of the claims it made. The experiments clearly shows that the proposed method ICQ and ICQ-MA does not suffer from Q function over-estimation problem. 
 
This paper contains several strong aspects. The usage of the importance sampling ratio in the update of the Q function is novel afaik. The intersection of Offline RL and Multi-agent RL is novel and deserves more consideration. And the long standing problem of value overestimation can benefit from the contributions of this paper. The experimental and the ablation study results look sound -- starting with a toy environment as a motivation, then moving on to more complicated benchmarks.
 
One major point that was unclear was whether ICQ should be solely used in a multi-agent env, or does the method work equally well in a single-agent env. More specifically, In l127, you mentioned that the unseen (s,a) pairs grow exponentially with the number of agents. Is that because the amount of data collected is held fixed while the joint action space A of all of the agents increases exponentially with the number of agents? If so, I wonder whether the better performance is because ICQ is better than BCQ at handling additional dimensionality in the state-action space, or because it is better at multi-agent data specifically. I imagine a relatively straightforward way to test this is to hold the dimensionality of (s,a) constant by add dummy observation dimensions to the two-agent toy env and compare two-agent+dummy v.s. four-agent. 
 
 
Additionally, I am uncertain around the following points
 
1. In l87, what is $Q^\pi_B$ exactly? Is that just the expected value of $r + Q(s’, a’)$ over the batch of $(s,a,r,s’)$ and $a’\sim\pi(s,a)$? Or is that what $Q^\pi$ converges to when only using data from B?
2. In l96 around the fixed additional error. Do you assume here that seen pairs will have an exact estimate and 0 or close to 0 error?
3. In l56, it is not immediately obvious what does “all agents share the same reward function” may imply. Does that restrict us to a cooperative environment? Because the given reward function is a function of the env state, not the agent’s observation. I think you may have meant the latter.


Other suggestions for better readability/clarity: 
1. In the paper, it is not clear that the optimal policy in eq 8 is already proposed in AWR (Peng et al. 2019). 
2. L31-32  “unseen state-action pairs will grow exponentially as the number of agents increases in multi-agent systems” It is not immediately clear why it is exponential and I think it’s only mentioned once in l127. You’ve shown that the error grows linearly with the number of agents in Theorem 2. It might be more clear if you drop the exponential part.
3. In 6.1 you mentioned that StarCraft II is deterministic. That is in fact not the case. See [this link](https://github.com/deepmind/pysc2/blob/master/docs/environment.md#determinism-and-randomness)
4. In 6.1 and elsewhere, it is unclear from the paper whether a) the paper tested its agents on the full StarCraft II game or specialized maps; b) whether the environment is two-player or 2+; c) whether the goal is competitive or cooperative.  That information is available in the DOP, but is worth specifying again for the readers unfamiliar with that work or with StarCraft. 
5. There is a typo in l104 I believe. Did you mean “by optimizing $\pi(a'_u | s'_s)$”?

-------Updated review----

After the rebuttal, the author added results for the single agent use cases, which makes the proposed algorithm (ICQ) applicable to more domains beyond the multi-agent use case. The authors also improved the clarity of the paper and added discussions around the pros and cons of ICQ. The changes made the paper stronger and thus merit a re-evaluation of the score. I’ve changed my ratings accordingly.
limitations_and_societal_impact: A missing part to the discussion is the strength and the weakness of the algorithm. The authors only discussed the tradeoff between higher training cost and better performance.  It would benefit the readers to have more discussion for the question: should we all stop using AWR, BCQ, and BC in favor of ICQ?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a new algorithm that investigates centrally trained, decentrally executed coordinated offline multiagent RL (MARL) tasks. The main insight in this papers approach is that in offline MARL, out of distribution errors accumulate exponentially as the number of agents grows and alleviate this issue by only trusting state action pairs in the training dataset (offline trajectories). They first demonstrate the error accumulation theoretically and motivate their Implicit Constraint Q-learning (ICQ) algorithm with the theory. Finally, they show that existing offline RL algorithms fail to scale to the multi-agent setting while ICQ is able to, in addition to improving offline RL in the single-agent setting. 
main_review: This paper is well-motivated - the problem of offline learning from a static dataset is well known and its challenges have been studied in terms of unseen actions during value-function training. The authors also state in the appendix that the coordinated setting is a limitation, but this is a reasonable starting point for this work. The results and experiments are extensive and very convincing. I also appreciate the simplification of the algorithm over the BCQ baseline, which requires training an additional generative model and perturbation model. The main concern I have is surrounding the clarity. 

My main questions are around the derivation of the forward KL objective. Specifically, I am not clear on what the target of the normalization constant should be. It is also not clear from the B.4 section of the appendix, and I would like to have seen a more detailed derivation from equations 31 to 32. There are other works that derive a policy optimization objective from the forward KL, the partition function is computed by integrating over actions, for example in the M-step of MPO algorithm (Abdolmaleki 2018). In the practical algorithm, this is approximated by sampling several actions for a given state and taking the softmax. In this paper, however, I am not sure what the normalizing constant should be capturing. In the practical algorithm, it seems you are taking a softmax accross the batch dimension as you state, which I interpret as integrating over actions and states. However, the motivation behind this is confusing to me without seeing more detailed steps. Finally, this raises a question for me in terms of the practical consideration of batch-size. I imagine that given the weights are computed as a softmax operation on the minibatch Q-values, this would mean that small batch sizes are preferable for stronger learning signal. It would be interesting to see this explored and/or expanded on. 

If this can be cleared up, I think the experimental results and comparisons to baselines (and even in the single-agent case) makes this a strong paper. 

Originality: This seems novel as far as I know. There are some works that utilize the forward KL in RL whereas most policy gradient objectives can be viewed as derived from the reverse KL. However, this is a specific case of utilizing it in order to avoid sampling from the trained policy for the updates, which seems very clever. Additionally, in the policy update, tuning the alpha parameter between 0 and \inf interpolates between Q-learning and behavior cloning, but an intermediate value works best for high reward. 

Quality: This is a dense paper, but there are several ablation studies and intuitions given for the implementation details. The experiments on the multi-agent settings are especially extensive and impressive. 

Clarity: See above. 

Significance: Offline RL is an important topic in RL, and that this is able to outperform existing baselines in the single agent case is already impressive to see. The significance is greatly improved given the results in the multi agent settings. 

Misc: minor typo - the perturbation model takes tau' instead of tau in the Bellman target. Also, CQL (Conservative Q-Learning for Offline RL) is not cited but used as a baseline. I would also discuss how this is a much simpler version of the existing methods, namely CQL and BCQ. Effectively, by applying the constraint implicitly, the authors avoid an additional regularization term (as most offline RL papers use to enforce similarity to the behavior policy) or even training a separate network as BCQ does.

limitations_and_societal_impact: The limitations are addressed in the appendix. It is fairly comprehensive there and does not take away from the papers contributions.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tackles the problem of offline multi-agent reinforcement learning (MARL). The relation between extrapolation error and transition probabilities of unseen states is first derived for the single-agent case. It is then extended to the paradigm of centralized training with decentralized execution (CTDE) in MARL, under the assumption of a linear decomposition of the joint action-value function, such as in methods like Value Decomposition Networks. The derived relations motivate the idea of setting the action probabilities of unseen actions at unseen states to be zero. In contrast to previous work, the proposed method called "ICQ" uses the KKT conditions to reformulate the constrained optimization viewpoint of offline RL, so that unseen state-action pairs are not used in the loss function. This single-agent result is again extended to MARL with linear decomposition of the joint action-value function. Convergence is shown for the finite case. Experiments on a finite synthetic game and the high-dimensional StarCraft II micromanagement environment show that ICQ outperforms the multi-agent extensions of existing single-agent methods, while ablations show that various design choices are necessary for performance. The single-agent version of ICQ is shown to meet or exceed baselines in single-agent environments.

main_review: Overall, the proposed method is well-motivated by theoretical results and appears to have strong experimental evidence, but there is a concern about experimental protocol and there are various claims that need more justification and clarification.

The proposed reformulation of offline RL using the viewpoint of convex optimization appears to be novel, given the accuracy of the summary of related work. This motivates the proposed method, ICQ, to avoid the use of unseen state-action pairs, which would have contributed to error in previous methods. The improvement due to avoiding the use of unseen pairs is shown in a didactic finite game, and further validated in higher dimensional environments.

Theorems 1 and 2 are useful for motivating the method. I am slightly concerned about the author's claim in line 165 that the importance sampling weight does not involve $\pi$. How can $Q^{\pi_k}$ in equation (9) be accurately estimated if not all possible state-action pairs, which involves unseen pairs, are used? This doesn't seem to be a serious issue because $Q^{\pi_k}$ is evaluated only under the behavioral distribution when it appears in equation (11). Nonetheless, the authors may wish to rephrase line 165.

Lines 30-32 says "we demonstrate that unseen state-action pairs will grow exponentially as the number of agents increases...". Where does this paper demonstrate it? The exponential growth is obvious and I don't think it needs justification, but I didn't see the "demonstration" anywhere in the paper (the 2-state game in Figure 1 is just an example). The phrasing makes it seem that the authors are claiming something more than this obvious fact, but I don't think that's the case, so I recommend rewording it.

Line 76-77: it's not clear what is the exact operation that "mask" means. Does BCQ avoid using unseen pairs by "masking" (i.e. setting to those Q values to zero)? If so, how is that fundamentally different from the way ICQ avoids using unseen pairs?

In line 95-96, how is $\epsilon_b$ different from $\epsilon_u$? Are they actually the same? Are you saying that $\epsilon_s$ for seen pairs is set to zero? This is confusing.

Line 162-163: computing the partition function in ICQ seems to be a hard subtask. How is this tractable for continuous state and continuous action spaces?

Line 184: Does $n$-step evaluation strictly lead to zero bias, i.e. "eliminate", as the paper says?

Line 228-231: Since this paper does not compare with the methods AWR and ABM, how can the authors claim that their method has "much more efficient learning"?

I am concerned about the experimental protocol. In section 6.1, the paper says that the hyperparameters for the baseline methods BCQ and CQL were taken from those that the original papers provided. Were the hyperparameters of BCQ and CQL already tuned for StarCraft II? If not, and if this paper did not tune the baselines for the tasks used in this paper, then the comparisons are not fair. Could the authors address this issue?

The organization of the paper needs improvement. Section 3.2 Toy Example compares the proposed method ICQ with the baseline BCQ, but ICQ hasn't even been described yet.

Minor comments:
1. The acronym "MMDP" first occurs in Figure 1 without saying what it stands for.
2. Line 126: "QMIX" appears for the first time here without saying what it stands for, and without a citation to the QMIX paper.

-----------------------------------------------------------------------------
After rebuttal: the authors have addressed all of my original questions and have promised to update the paper with extra experimental results and explanations based on the discussion during this review process, so I am raising the score from 6 to 7.
limitations_and_societal_impact: Limitations were placed in supplementary material, which was not reviewed.
review_title: null

Meta-review: The paper addresses the problem of offline multi-agent reinforcement learning (MARL) and identifies a key challenge in that the accumulated extrapolation error increases with the number of agents. The authors propose a principled approach to address this problem, based on the idea of constraining Q-value estimations to only "seen" state-action pairs observed in the offline data. The approach is well motivated conceptually and shows strong empirical performance, detailed ablations provide deeper insights.

Initial reviews of this paper were positive about the originality of the proposed approach and its strong grounding in the theoretical analysis, in addition to the strong empirical results. Several aspects required clarification, including notation, interpretation of loss terms / derivation of the KL objective. Reviewers suggested several readability improvements. Finally there were questions on whether the approach would be expected to only improve performance on multi-agent tasks, or if improvements could also be expected in single-agent settings.

The authors provided detailed responses to clarification questions and committed to incorporating readability and other improvements in the next version of the paper. They also provided substantial additional empirical evidence for single agent tasks. In the follow up discussion, all reviewers indicated they were satisfied with the responses, and confident that the authors would be able to incorporate the suggestions into the camera ready version. Some reviewers raised their scores, resulting in a consensus recommendation to accept the paper.

The AC recommends acceptance as a spotlight paper, based on the strong theoretical insight and empirical results, as well as the timeliness of this work's focus on multi-agent and offline RL settings.
Decision: Accept (Spotlight)