Response to Reviewer YkYd

Thank you very much for your recognition of our paper's problem setting, paper writing, experimental results, and the valuable feedback you provided. In response to your comments, we would like to make the following clarifications and feedback. We hope our explanations and analyses can eliminate concerns and make you find our work stronger.

W1. Lack of novelty: … However, I hardly find these two ideas or the combination of these two ideas applied to marl novel.

We all know that learning and search are two major “magic keys” in machine learning, as well as common paradigms in MARL. We argue that the novelty of OMIS lies in using in-context learning (ICL) and in-context search (ICS) to address the challenges of OM, with "in-context" being the core aspect. In other words, we offer a new perspective that learning and search should be in-context (adaptive). We utilize ICL-based pretraining to respond to opponents based on in-context data (ICD) adaptively. Building upon this foundation, we further improve this adaptive capability through ICS. Our ICS is capable of inferring opponent actions, making responses, and estimating corresponding values based on the opponent's ICD. Lastly, both our proposed ICL and ICS are theoretically well-grounded, whereas many existing OM approaches lack theoretical analysis. To end with, we would like to argue that novelty is not always about creating entirely new methodologies. Offering a systematic approach that effectively addresses a long-standing problem in a field is also a form of innovation.

W2. Strong assumptions: OMIS relies on the access to the environment dynamics … it may give an unfair advatange to OMIS when compared to other baselines.

We include results and corresponding analyses for the version of OMIS where the dynamics are learned. Please refer to the Global Response.

(1) W2. In addition, … (2) Q1. Could you clarify if OMIS needs to know the exact time points when opponents switch policies during the test stage?

OMIS does not require knowing the exact time points when opponents switch policies, as demonstrated in Figure 7, where the timing of policy switches is strictly unknowable to OMIS. Even in this situation, OMIS works well and generally outperforms other baselines (see Figures 3 and 4).

If the switch times were precisely known, it might be able to further enhance OMIS. Detecting whether opponents have switched policies is an independent research problem [1,2]. In fact, we could leverage these methods for detecting opponent switches to make $D^{\text{epi}}$ as pure as possible, thereby achieving better result.

[1] Efficiently detecting switches against non-stationary opponents. AAMAS, 2017.

[2] A deep bayesian policy reuse approach against non-stationary agents. NIPS, 2018.

W3. Scalability: The experiments conducted in the paper are relatively simple, …

As you mentioned, the experiments in our paper are generally not that complex. Despite this, current algorithms in the OM domain still struggle to work well, facing challenges such as having difficulty generalizing to unknown opponent policies and performing unstably (see Figures 3 and 4). In contrast, our approach performs well in these commonly used benchmarks. Furthermore, we would like to emphasize that OverCooked (OC) is a relatively complex environment with a high-dimensional state space where all states are image-like. Training even a workable policy on OC is actually challenging and requires more than a few computational resources.

Q2. Is it possible to provide OMIS-dyna under all ratio settings?

We provide the results for OMIS-dyna under all ratio settings. Please refer to the Global Response.

Q3. For OMIS w/o S, … why it can still outperform other baselines in LBF and OC but falls behind in competitive PP when the ratio of unseen opponents is high?

The possible reason for this result is that PP is a continuous environment with an uncountable state space, exacerbating the degree of out-of-distribution of unseen opponents' states. OMIS w/o S relies on $(s, a^{-1})$ tuples for generalization, whereas other baselines do not depend on this for generalization. This reliance introduces additional challenges for OMIS w/o S. In contrast, the state spaces of LBF and OC environments are countable, and many of the states of unseen opponents can be familiar (though the actions in those states may be novel). This makes generalization for OMIS w/o S easier.

(1) Q4. … why OMIS can outperform other baselines while the in-context components of OMIS do not estimate very accurately in PP and LBF? (2) Q5. … , I wonder how the results of deep search can benefit from the pre-training of the in-context components of OMIS, especially the opponent imitator.

We argue that the necessity of search arises precisely because there are estimation errors in the opponent's actions and value predictions. Otherwise, we could directly solve for the best response to the current opponent's policy, and there would be no need for search.

The search domain generally does not emphasize the concept of compound errors; rather, it focuses on the trade-off between exploration and exploitation. In fact, the inaccuracy of the opponent imitator can be viewed as accurately sampling the opponent's actions most of the time while exploring other actions occasionally, meeting the trade-off need for search. Given that OMIS's critic is relatively accurate, combined with the reward signal during search, we can consider our value estimates to have relatively high confidence.

All your questions and feedback have greatly contributed to improving our manuscript. We welcome further comments from you and will seriously consider your suggestions for revisions. If you feel that we have addressed your concerns, we hope you will reconsider your rating.

Dear Reviewer,

We sincerely appreciate your thorough reading and the valuable feedback you provided during the review process. Your constructive comments have helped us strengthen our manuscript, particularly in clarifying our work's novelty and validating our approach's effectiveness when the environment model is unavailable.

We are eager to have the opportunity to have a further discussion with you and will do our best to address any remaining concerns or questions you may have. We sincerely request your feedback so that we can conduct additional experiments or make revisions to further improve the current version of our submission promptly.

---

Here is a summary of our rebuttal, which we hope adequately addresses all the concerns you raised:

1. We clarified that the novelty of OMIS lies in using in-context learning (ICL) and in-context search (ICS) to address the challenges of opponent modeling (OM), with “in-context” being the core aspect, to address your concerns about “our contributions on novelty”. Additionally, we presented our argument that novelty is not always about creating entirely new methodologies. Offering a systematic approach that effectively addresses a long-standing problem in a field is also a form of innovation.
2. We have supplemented our rebuttal with experimental results for OEOM under learned dynamic transitions to address your concern regarding “OEOM's strong dependence on the environment model”, as detailed in the Global Response. These results support the effectiveness of OEOM under such conditions, and we will include them in the experimental section of the revision.
3. We have provided the “results for OMIS-dyna under all ratio settings” as you requested, as detailed in the Global Response.
4. To address your concern about “why OMIS w/o S was unable to outperform other baselines in the PP environment”, we provided a detailed explanation based on the characteristics of the environment and the principles underlying the OMIS w/o S algorithm.
5. Regarding your concern about “how search can improve OMIS w/o S even when the opponent imitator's estimates are inaccurate”, we clarified that the necessity of search arises because there are estimation errors in the opponent's actions and value predictions. Additionally, we explained that OMIS's inaccurate estimates can be seen as equivalent to a search mechanism that balances exploration and exploitation, which is needed in the search domain to refine the original policy.

However, if OMIS request these many computation resources for achieving SOTA on "relatively simple and conceptual" games (offline: pretraining on there mouldes each is a GPT2 decoder composed of 3 self-attention blocks, building opponent policies pool for training, corresponding training data preparation, learning environment dynamics and online search + inference), how will OMIS contribute to the community?

Regarding computation resources, we would like to clarify that we did not train three separate Transformer networks offline. Instead, we trained a single Transformer backbone and used three output heads for the actor, critic, and opponent imitator, all of which share this Transformer backbone. In fact, the Transformer model we used is very lightweight, with a memory footprint of only ≤3MB, so it requires minimal computational resources.

Regarding the complexity of the algorithmic process, during the pretraining stage, our approach only requires straightforward supervised training using data generated by any RL algorithm. During the testing stage, the pretrained Transformer can either be directly used (which already outperforms most baselines in our experiments, see Fig. 3 and Fig. 4 in the main text) or further enhanced with our very simple search method. In contrast, other approaches involve a lot of complex procedures. Take MBOM [11] as an example. In our implementation, MBOM also uses a Transformer backbone of the same scale. However, its overall process includes several complex steps: building an opponent policies pool for training, generating training data using opponent policies and conducting pretraining, learning environment dynamics (if necessary), online learning and finetuning multiple nested opponent models, conducting online planning and inference, and finally, using explicit Bayesian methods to mix the nested opponent models. Another example is Meta-MAPG [7], where our implementation also uses a Transformer backbone of the same scale. Its overall process is as follows: building an opponent policies pool for training, generating training data using opponent policies, and conducting pretraining with meta-gradient methods (which involves both outer and inner loops of meta-learning). The online stage requires continuous inference and finetuning sample collection from the opponent, followed by gradient updates to the learned model for continuous finetuning (which is highly sensitive to hyperparameters, making it challenging to work effectively in practice).

---

We hope our detailed response has addressed the remaining concerns you had regarding novelty and scalability. We believe that OMIS offers a simple, scalable, and effective solution for the opponent modeling community. Even with limited time remaining, we are more than willing to engage in further discussions if you have any remaining concerns. If we have resolved your concerns, we sincerely hope you will reconsider your score.

Best regards,

All authors

Response to Reviewer eKwk

Thank you very much for your recognition of our paper's methodologies, theories, empirical results, paper writing, and the valuable feedback you provided. In response to your comments, we would like to make the following clarifications and feedback. We hope our explanations and analyses can eliminate concerns and make you find our work stronger.

The theoretical explanations in Section 3 are dense. It’s unclear if this section provides additional benefit within the Methodology section. You may consider moving Section 4.3 to the beginning of the Methodology section …

Thank you very much for your valuable suggestions. The connection between our methodology and experiments is indeed not smooth. In the revision, we will move Section 4.3 to the beginning of the Methodology section to make the transition between the methods and experiments clearer.

Why do you specifically select 10 policies from the MEP population to form the training policies?

Selecting 10 policies from the MEP population is just one of the possible reasonable design choices. We follow this choice for the following reasons:

(1) MEP is an efficient approach for generating a diverse and high-strength population of policies, making it a reasonable method for opponent policy generation.

(2) For all opponent modeling approaches, we use the same 10 policies from the MEP population as training opponent policies, facilitating fair comparison with other baselines.

(3) The specific selection of which 10 policies from the MEP population does not matter, as all policies have appropriate differences between each other, as can be observed from the quantitative analysis of policy diversity in Appendix G.

(4) Considering computational resource constraints, we select only 10 policies as training opponent policies.

Why do the test policies need to contain seen policies? When testing, why not have all unseen policies?

Although testing against seen opponents may seem trivial, existing opponent modeling approaches still struggle to handle even seen opponents, as can be observed in Figures 3 and 4. This is because their methodological designs often rely heavily on intuition but lack rigorous theoretical analysis. In contrast, OMIS provides good theoretical properties in terms of generalization (see Theorems 4.2 and 4.3), ensuring accurate recognition of seen opponent policies during pretraining and providing the most appropriate responses. Our experimental results (Figures 3 and 4) further validate the effectiveness of our approach, as it generally outperforms other baselines against seen opponents.

All your questions and feedback have greatly contributed to improving our manuscript. With the valuable input from you and all other reviewers, the quality of our work can be significantly enhanced. We welcome further comments from you and will seriously consider your suggestions for revisions. If you feel that we have addressed your concerns, we hope you will reconsider your rating.

Response to Reviewer G1Ke

Thank you very much for your recognition of our paper's writing, methodologies, literature reviews, and the valuable feedback you provided. In response to your comments, we would like to make the following clarifications and feedback. We hope our explanations and analyses can eliminate concerns and make you find our work stronger.

(1) This work implicitly assumes the presence of a perfect transition model. OMIS relies on this transition model …, making OMIS inapplicable. (2) OMIS requires virtual transition dynamics ... However, if the virtual transition dynamics need to be learned from data, …, how will OMIS perform under these conditions?

We include results and corresponding analyses for the version of OMIS where the dynamics are learned. Please refer to the Global Response.

The mixing technique in Equation 10 is quite simple and …, the hyperparameter requires fine-tuning for different environments.

Thank you for pointing that out. In fact, more complex hybrid techniques combining both search and original policies have been proposed by others as well, such as [1]. However, their technique also introduces hyperparameters, and our experimental verification found that the approach proposed by [1] yielded comparatively poorer results. In contrast, our proposed mixing technique is a simple yet effective approach. Additionally, we empirically found that it is quite straightforward to find suitable values for the hyperparameter $\epsilon$. The value of $\epsilon$ only needs to follow one principle: it should be slightly smaller than the absolute value of the sparse rewards in the environment. We argue that our technique has an advantage building upon its simplicity and effectiveness.

[1] Modeling strong and human-like gameplay with KL-regularized search. ICML, 2022.

Lemma 4.1 assumes that … sampling from $\mathcal{T}_{\text{pre}}^{-1}$ should be correlated with the opponent's policy. So is the assumption reasonable?

Thank you for carefully reading our paper and raising this interesting question. We also hope you understand that such a gap between theoretical analysis and practical algorithms is quite common in deep reinforcement learning.

Yes, opponent policies do influence the distribution $\mathcal{T} _ {\text{pre}}^{-1}$. Here, we assume that sampling states $s$ from the distribution $\mathcal{T} _ {\text{pre}}^{-1}$ is independent of opponent policies. This is not a strong assumption. During the pretraining stage, we generate many trajectories w.r.t. each opponent policy. Therefore, given any opponent policy $\pi^{-1}$ in $\Pi^{\text{train}}$, sampling $s$ from $\mathcal{T} _ {\text{pre}}^{-1}(·;\pi^{-1})$ can be approximately considered as sampling over the entire state space $\mathcal{S}$, thus making it independent of the opponent policy.

In our practical implementation, we made every effort to approximate this assumption. For example, we generated 1000 trajectories w.r.t. each opponent policy, utilized MEP to ensure sufficient diversity among opponent policies, etc. Despite these approximations, we found that both OMIS w/o S and OMIS achieved impressive results empirically. This suggests that they are not heavily reliant on this assumption to a certain extent.

Equation 10 considers the expected return ... How does this design address the issue of value function overestimation?

This is an important question, and we greatly appreciate you bringing it up.

Generally, when optimizing the Bellman optimality equation in RL, using the max operation for temporal difference bootstrapping can lead to maximization bias, which further causes overestimation issues. However, our search does not use the max operation for bootstrapping, so there should be no overestimation problem.

Even if overestimation occurs, we also utilized a search-specific discount factor $\gamma _ {\text{search}}$ (see Eq. 8) to balance the negative impact of overestimation in the value function. When $\gamma _ {\text{search}}$ is small, we rely more on relatively reliable rewards to estimate the action value $\hat{Q}$ and less on the value function. Our experiments found that this approach effectively addresses the overestimation issue in the value function, resulting in stable performance improvements from the search process.

All your comments have greatly contributed to the improvement of our paper. If you have any new comments, please feel free to provide them, and we will promptly address them. If you find that we have addressed your concerns, we hope you will reconsider your rating.

Dear Reviewer,

We are deeply grateful for your thoroughness and the constructive feedback you provided during the review process. Your valuable insights have helped us improve our paper, especially in validating the effectiveness of our approach when the ground-truth environment model is unavailable.

We would love the opportunity to have an active discussion with you and address any remaining concerns or questions you may have. We sincerely request your feedback so that we can conduct additional experiments or make revisions to further improve our submission promptly.

---

Here is a summary of our rebuttal, which we hope adequately addresses all the concerns you raised:

1. We have supplemented our rebuttal with experimental results for OEOM under learned dynamic transitions to address your concern regarding “OEOM's strong dependence on the environment model”, as detailed in the Global Response. These results support the effectiveness of OEOM under such conditions, and we will include them in the experimental section of the revision.
2. We clarified that the hyperparameters for OEOM's mixing technique are easy to find and provided guidelines for setting them to address your concern about “its reliance on hyperparameter optimization”. Specifically, the hyperparameter $\epsilon$ only needs to be slightly smaller than the absolute value of the sparse rewards in the environment.
3. To address your question about “the reasonableness of the assumption in Lemma 4.1”, we provided a detailed explanation of the assumption's meaning and clarified how we conducted experiments to ensure that this assumption was met as closely as possible.
4. Regarding your concern about “the issue of value function overestimation”, we analyzed the scenarios where value overestimation might occur and clarified that our approach does not fall into this category. Additionally, we explained and analyzed how OEOM's search-specific discount factor $\gamma_{\text{search}}$ mechanism helps to further avoid overestimation.

Response to Reviewer xSNm

Thank you very much for your valuable feedback. In response to your comments, we would like to make the following clarifications and feedback. We hope our explanations and analyses can eliminate concerns and make you find our work stronger.

the proposed method is somewhat limited by the need of dynamics

We include results and corresponding analyses for the version of OMIS where the dynamics are learned. Please refer to the Global Response.

The proposed method requires transition dynamics while the baselines compared with it do not require, which makes experiments unfair …

We compare our work with the paper [1] you mentioned. Please refer to the Global Response.

[1] https://arxiv.org/pdf/2305.13206

The presentation is unclear …

In fact, the presentation of our paper received consistent approval from reviewers G1Ke, eKwk, and YkYd. However, as you mentioned, there is still significant room for improvement in terms of clarity. We apologize for any inconvenience this may have caused and appreciate your suggested advice. We will reorganize the logic and simplify the mathematical symbols in the revision. We will address your concerns one by one in our subsequent responses.

(1) Line 39: … How does pre-training with a transformer model deal with any of the issue abovementioned? (2) Line 41: How is in-context learning related to pre-training issues? (3) Line 42: How are these three components related to pre-training issues? …

Your suggestion is very pertinent; the transition in Lines 39-42 is indeed not smooth. Actually, we explained the motivation for our approach at the beginning of the methodology section (Lines 106-120). In the revision, we will move the overview of the motivation to Lines 39-42 to emphasize the rationale behind our work rather than its implementation.

The in-context-learning (ICL)-based pretraining we used theoretically provides good generalization guarantees: the pretrained model can accurately recognize seen opponents and recognize unseen opponents as the most familiar seen ones to some extent. This theoretical property endows our approach with the potential to address pretraining issues effectively.

For the three components: the actor is the core of the ICL-based pretraining, ensuring good generalization to handle pretraining issues. The critic and opponent imitator are indispensable modules for OMIS search during testing.

Line 48: Again, what issues are you talking about there? What are limited generalization abilities? What are good properties? What are performance instability issues? …

We apologize for the misunderstanding caused by our unclear expression. In the revision, we will clarify that "limited generalization abilities" refers to the lack of theoretical guarantees for generalization during the pretraining stage in existing approaches. "Good properties" refer to the characteristics of OMIS described in Theorem 4.2—accurately recognizing seen opponents and recognizing unseen opponents as the most similar to the seen ones. "Performance instability issues" refer to the problem mentioned in Line 38, as you guessed, which is also reflected in the results of our experiments, such as Figure 3.

Line 147: … What do you mean by true policy is unclear. Isn't $\bar{\pi}^{-1}$ just a policy chosen by a non-stationary player?

Here, $\pi^{-1}$ can be understood as the non-stationary opponent agent, while $\bar{\pi}^{-1}$ is a mnemonic representing the actual policy used by $\pi^{-1}$ at a given time, which is unknown to the self-agent. We will emphasize the distinction between the two symbols in the revision.

Line 158: What are $D^{\text{epi}}$ and $D^{\text{step}}_t$?

Both $D^{\text{epi}}$ and $D^{\text{step}} _ t$ are generated from the interactions between OMIS and the non-stationary opponent $\pi^{-1}$ during testing. $D^{\text{epi}} = \{(\tilde{s} _ h, \tilde{a} _ h^{-1})\} _ {h=1}^{H}$ is episode-wise in-context data, constructed similarly to the process in Appendix C, except that $(s, a^{-1})$ tuples are sampled from the most recent $C$ trajectories in which $\pi^{-1}$ participated. $D^{\text{step}} _ t = (s _ 0, a _ 0^{-1}, \dots, s _ {t-1}, a _ {t-1}^{-1})$ is step-wise in-context data. We will add these explanations to the revision.

Line 159: $D^{\text{epi}}$ samples segments? …

The expression here is indeed inaccurate. We mean that $D^{\text{epi}}$ is constructed by sampling several consecutive segments from the opponent's trajectories.

Section 5.2: How many random seeds do you train? What does the error bar represent?

We trained with 5 random seeds, as stated in the "Specific settings" paragraph of Section 5.1. The error bars represent the standard deviation of the test results across these above 5 random seeds.

Line 311, Section 5.2: … Since this claim is only backed up by qualitative observation, I don't think you can say the results imply OMIS can …

We incorporate your suggestion and add a quantitative analysis of attention weights learned by OMIS. Please refer to the Global Response.

Line 319: I initially had a question, "What do you mean by using opponent actions and true RTGs as labels?" …

Your suggestion is beneficial; we will emphasize the meaning of each symbol before it appears in the revision.

All your comments have greatly contributed to the improvement of our paper. If you have any new comments, please feel free to provide them, and we will promptly address them. If you find that we have addressed your concerns, we hope you will reconsider your rating.

(1) how the author will make the writing clearer is unclear in the rebuttal (it'd be great if the author could provide a more detailed revision plan, …)

We carefully review your feedback and summarize the areas in our initial version where clarity was lacking:

1. Lines 39-41: We did not clearly explain how in-context learning addresses the pretraining issues mentioned in Lines 33-36; Line 45: We failed to clarify the roles and problem-solving contributions of the three components mentioned.
2. Line 45: We used some ambiguous phrases, such as "limited generalization abilities," "good properties," and "performance instability issues," without providing adequate explanations for them.
3. Line 147: We introduced two symbols, $\bar{\pi}^{-1}$ and $\pi^{-1}$, which are easily confused and difficult to understand.
4. Lines 148-159: We used somewhat redundant symbols $D^{\text{epi}}$ and $D^{\text{step}}_t$ without clearly explaining their specific meanings.

To address these unclear areas, we have developed a detailed revision plan:

1. We will simplify Lines 106-119, move them before the original Line 39, and then optimize the logic to ensure a smoother connection with the surrounding paragraphs.
2. In Lines 32-38, we will clearly define "limited generalization abilities" and "performance instability issues" before referencing them in the original Line 45 to avoid ambiguity. In Line 50, we will provide an objective description of OMIS's theoretical properties, avoiding the use of vague terms like "good properties."
3. We will introduce new symbols to represent the non-stationary opponent agent, replacing $\pi^{-1}$ to prevent confusion with $\bar{\pi}^{-1}$.
4. We will follow your suggestion to use time-slice indices to represent partial trajectories, simplifying the notation for in-context data.

Additionally, through our discussions with you, we've learned a lot from your excellent taste in writing and identified other areas that could be improved:

1. Line 122: We did not clearly explain how training against different opponent policies to learn BRs ensures that the actor acquires high-quality knowledge for responding to various opponents.
2. Line 120: Although we provided a schematic diagram and pseudocode for OMIS, the specific process of the OMIS remains unclear.

For these areas, we have also developed the following revision plans:

1. We will briefly overview the main idea and process of ICL-based Pretraining before Line 122 to clarify the motivation behind Line 122.
2. We will provide a step-by-step summary of the overall OMIS process in Line 120, using Figure 1 as a reference, and refine the logic to make the approaches described in Sections 4.1 and 4.2 clearer.

We will diligently implement these revision plans.

(2) I'm not sure about the significance of this method since I'm not update-to-date on opponent modeling literature.

At the methodological level, our work is built on an up-to-date and extensive overview of existing work, which reviewers like G1Ke and YkYd have appreciated. For instance, G1Ke mentioned, "The paper provides a comprehensive review of existing literature, showcasing a deep understanding of the relevant background." We logically categorized the various existing approaches into two major categories (PFA and TFA) and analyzed the issues associated with them. Based on this analysis, we proposed a new algorithm, OMIS, which effectively addresses the specific problems inherent in these two categories of approaches.

At the theoretical level, most existing work lacks theoretical guarantees regarding generalization. In contrast, we have proven that our approach possesses the following properties: (1) When the opponent's policy is a seen one, OMIS w/o S can accurately recognize the opponent's policy and converge to the best response against it; When the opponent's policy is an unseen one, OMIS w/o S recognizes the opponent policy as the seen opponent policy with the smallest KL divergence from this unseen opponent policy and produces the best response to the recognized opponent policy. (2) OMIS's search is guaranteed to improve OMIS w/o S, without any gradient updates.

At the experimental level, we selected a sufficient number of representative opponent modeling baselines from both the PFA and TFA categories. OMIS consistently outperformed these baselines, regardless of whether the opponents were seen or unseen. Our supplementary experiments confirmed that OMIS can also work effectively when the transition dynamics are unknown and learned.

In summary, whether at the methodological, theoretical, or experimental level, we believe our work has significantly contributed to advancing the domain of opponent modeling.

---

Again, Thank you for your extensive and valuable comments, which have greatly improved our paper. We hope we have addressed all your concerns. We look forward to your continued feedback and further support for our work.