Opponent Modeling based on Subgoal Inference

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 14:28:18

Abstract: When an agent is in a multi-agent environment, it may face previously unseen opponents, and it is a challenge to cooperate with other agents to accomplish the task together or to maximize its own rewards. Most opponent modeling methods deal with the non-stationarity caused by unknown opponent policies via predicting the opponent’s actions. However, focusing on the opponent’s action is shortsighted, which also constrains the adaptability to unknown opponents in complex tasks. In this paper, we propose opponent modeling based on subgoal inference, which infers the opponent’s subgoals through historical trajectories. As subgoals are likely to be shared by different opponent policies, predicting subgoals can yield better generalization to unknown opponents. Additionally, we design two subgoal selection modes for cooperative games and general-sum games respectively. Empirically, we show that our method achieves more effective adaptation than existing methods in a variety of tasks.

Main paper: 
 introduction: 
 Figure 1 : Infer the goal of others Reinforcement learning (RL) has achieved remarkable success in games involving multiple agents, such as Al-phaGo (Silver et al., 2016) , OpenAI Five (OpenAI, 2018), and AlphaStar (Vinyals et al., 2019) . The non-stationarity of multi-agent environments has brought many difficulties to problem-solving, and this has always been the case. In cooperative scenarios, many multi-agent reinforcement learning (MARL) methods (Lowe et al., 2017; Sunehag et al., 2017; Rashid et al., 2020; Son et al., 2019) aim to bridge the information gap between agents by training agents in a centralized manner, called centralized training with decentralized execution, enabling agents to work together seamlessly to accomplish cooperative tasks. Alternatively, fully decentralized methods (Jiang & Lu, 2022; Su & Lu, 2022) seek to break free from the constraints of centralized training, allowing agents to reach collaboration in a simpler and decentralized manner. In competitive scenarios, NFSP (Heinrich & Silver, 2016) , PSRO (Lanctot et al., 2017) , and DeepNash (Perolat et al., 2022) employ self-play to train agents for equilibrium strategies, allowing agents to adapt and improve their policy. By considering how the agent affects the expected learning progress of other agents, LOLA (Foerster et al., 2017) and COLA (Willi et al., 2022) apply opponent shaping to this setting. In these methods, all agents are jointly trained in the same scenario.Autonomous agents, different from those jointly trained, can act autonomously in complex and dynamic environments, sense the influence of the environment and other agents, and accomplish their own goals or tasks. Such agents can analyze the behavior of opponents1 by building models that make predictions about some core properties of the agents being modeled, such as their actions, goals, and beliefs, in a method called opponent modeling (Albrecht & Stone, 2018) . By modeling the intentions and policies of other agents, the training process of the agent might be stabilized (Papoudakis et al., 2019) . Many studies rely on predicting the actions (He et al., 2016; Hong et al., 2018; Grover et al., 2018; Papoudakis & Albrecht, 2020) , goals (Raileanu et al., 2018) , and returns (Tacchetti et al., 2018) of opponents during training. The autonomous agent adapts to different or unseen opponents by using the predictions or representations that are produced by the relevant modules. However, in some scenarios, opponents may continuously learn during interaction. Meta-MAPG (Kim et al., 2021) combines Meta-PG(Al-Shedivat et al., 2017) and LOLA, and focuses on the problem of the non-stationary environment caused by the continuous learning of opponents. MBOM (Yu et al., 2022) simultaneously targets a variety of adversaries, fixed policy, or continuous learning, by modeling the possible policies that an opponent may form, combined with Bayesian inference to generate an opponent's imagined policy. Some methods focus on figuring out the opponent's goal, e.g., ToMnet (Rabinowitz et al., 2018) and SOM (Raileanu et al., 2018) . SOM infers the opponent's goal through its own policy, in other words, "what would I do if I were the opponent?" LIAM (Papoudakis et al., 2021; Papoudakis & Albrecht, 2020) builds the opponent's policy from its own partial observations and uses it to anticipate the opponent's actions and make decisions. GSCU (Fu et al., 2022) chooses online between a real-time greedy strategy and a fixed conservative strategy through Bayesian belief in competitive environments. The greedy strategy is conditioned RL, while the conservative strategy is a bandit algorithm.Although a lot of the existing methods concentrate on modeling the opponent's actions, such an approach is short-sighted, pedantical, and highly complex. Generally, modeling an opponent's actions is just predicting what it will do at the next step. Intuitively, it is more beneficial for the agent to make decisions if it knows the situation of the opponent several steps ahead. Predicting the actions over a few steps is not elegant. For example, to reach the goal point of (2, 2), an opponent moves from (0, 0) following the action sequence <↑, ↑, →, →> by four steps (Cartesian coordinates). There are also 5 other action sequences, i.e., <↑, →, ↑, →>, <↑, →, →, ↑>, <→, ↑, ↑, →> , <→, ↑, →, ↑>, <→, →, ↑, ↑>, that can lead to the same goal. Obviously, the complexity of the action sequence is much higher than the goal itself. Other methods that claim to predict the opponent's goal (Rabinowitz et al., 2018; Raileanu et al., 2018) , without explicitly making a connection to the opponent's goal or just predicting the goal at the next step, are essentially as shortsighted as modeling actions.Inspired by the fact that humans can predict the opponent's goal by observing the opponent's actions for several steps as illustrated in Figure 1 , in this paper, we propose Opponent Modeling based on subGoals inference (OMG), which uses variational inference to predict the opponent's future subgoals from historical trajectories. The trajectory of an opponent's policy consists of a set of subgoals, and the trajectories of different policies may contain the same subgoal. This combinatorial property of the subgoals facilitates the generalization of the agent to unseen opponents' policies. Moreover, we design two manners for selecting subgoals, which are applied to cooperative games and general sum games, respectively. Empirically, OMG outperforms existing opponent modeling methods in a variety of complex multi-agent environments, demonstrating the superiority of inferring subgoals over predicting actions. 
related work: 
 Opponent modeling. Opponent modeling plays a crucial role in enhancing the robustness and stability of reinforcement learning (Papoudakis et al., 2019) . Given the presence of diverse opponent policies in multi-agent environments, the autonomous agent faces a significant challenge in learning resilient policies. When an agent perceives an opponent as part of the environment, the resulting environment becomes inherently unstable and intricate. To address this challenge, one straightforward method involves equipping the agent with the ability to incorporate information about its opponent, including aspects like the opponent's behavior, goals, and beliefs (Albrecht & Stone, 2018) , i.e., opponent modeling. It gives the agent a deeper insight and prediction ability about the opponent's policy. Thus, the autonomous agent views the environment as less unstable and can simply use single-agent reinforcement learning methods.A common approach to modeling the policy of an opponent is predicting the opponent's actions. DRON (He et al., 2016) and DPIQN (Hong et al., 2018) extend DQN (Mnih et al., 2015) by adding another network that estimates the opponents' actions from the observations. The DQN uses the hidden layer of this network to improve its policy. Variational auto-encoders can also be used to model the opponent's policy (Papoudakis & Albrecht, 2020) , which results in probabilistic repre- In the interaction phase, OMG deduces subgoals from historical trajectories to enhance decision-making. In the update phase, OMG employs the subgoal selector to choose the state among those within the next few steps as the subgoal.sentations instead of fixed vectors. PR2 (Wen et al., 2019) , MBOM (Yu et al., 2022) , and TP-MCTS (Weil et al., 2023) combine the idea of recursive reasoning, nested form as "the agent believes [that the opponent believes (that the agent believes ...)]", based on modeling the action of the opponent. Some works focus on modeling beliefs. Zintgraf et al. (2021) combined the sequential and hierarchical variational auto-encoders to construct a belief inference model using meta-learning, for belief inference. Zhang et al. (2023) introduced landmarks into the behavior model and improve the model by the action sequence of the opponents, so as to recognize and compare the opponent's intention.Another key aspect of opponent modeling is to infer the opponent's goal. Baker et al. (2009) formulated the goal recognition as a Markov decision process (MDP) and calculate the posterior probability of the goal by Bayes rule based on a prior goal library. ToMnet (Rabinowitz et al., 2018) aims to give the agent a human-like Theory of Mind. It uses three networks to infer the agent's goal and action from previous and present information. SOM (Raileanu et al., 2018) implements the Theory of Mind with a goal library from a different perspective. SOM uses its own policy, the opponent's observation, and the opponent's action to work backward to learn the opponent's goal distribution by gradient ascent. These methods either require a prior goal library or infer implicit "goals" that are not supervised by ground truth goals.Goal-conditioned RL. Goal-conditioned reinforcement learning is an extension of the single-agent algorithm. Most works focus on learning a goal-conditioned policy, where the goals are usually predefined (Plappert et al., 2018; Zhu et al., 2021) . Some works consider acquiring subgoals automatically to accelerate learning. Paul et al. (2019) proposed a method that uses expert trajectories to generate subgoals, while (Chane-Sane et al., 2021) proposed to incorporate imaginary subgoals into policy learning to facilitate learning complex tasks, where subgoals are measured by value functions. Unlike existing goal-conditioned RL methods, we aim to infer the subgoal of the opponent and condition the agent policy on the inferred subgoal. 
preliminaries: 
 In general, we consider an n-agent stochastic game M = (S, A 1 , . . . , A n , P, R 1 , . . . , R n , γ), where S is the state space, A i is the action space of agent i ∈ [1, . . . , n], A = n i=1 A i is the joint action space of agents, P : S × A × S → [0, 1] is a transition function, R i : S × A → R is the reward function of agent i , and γ is the discount factor. The policy of agent i is π i , and the joint policy of other agents is π o (a o |s) = j̸ =i π j (a j |s), where a o is the joint action except agent i. All agents interact with the environment simultaneously without communication. The historical trajectory is available, i.e., for agent i at timestep t, τ t = {s 0 , a i 0 , a o 0 , . . . , s t-1 , a i t-1 , a o t-1 } is observable. 0.4 0.7 0.8 0.9 1.0 D1 0.0 0.0 0.0 0.0 0.0 0.6 0.7 0.7 0.8 0.9 1.0 0.0 0.0 0.0 0.0 0.0 0.5 0.6 0.6 0.7 0.8 0.9 0.0 0.0 0.0 0.0 0.0 0.4 0.5 0.6 0.7 0.7 0.8 0.0 0.0 0.0 0.0 0.0 0.4 0.4 0.5 0.6 0.6 0.4 0.0 0.0 0.0 0.0 0.0 S1 0.4 0.5 0.5 0.6 0.4 0.0 0.0 0.0 0.0 S2 0.4 0.5 0.5 0.6 0.7 0.2 0.0 0.0 0.0 0.0 0.0 0.5 0.5 0.6 0.7 0.7 0.2 0.0 0.0 0.0 0.0 0.0 0.5 0.6 0.7 0.7 0.8 0.4 0.0 0.0 0.0 0.0 0.0 0.6 0.7 0.7 0.8 0.9 0.9 0.0 0.0 0.0 0.0 0.0 0.6 0.7 0.8 0.9 1.0 D2 0.0 0.0 0.0 0.0 0.0 0.7 0.7 0.8 0.9 1.0 D1 0.1 0.0 0.0 0.0 0.0 0.6 0.7 0.7 0.8 0.9 1.0 0.0 0.0 0.0 0.0 0.0 0.5 0.6 0.7 0.7 0.8 0.9 0.0 0.0 0.0 0.0 0.0 0.5 0.5 0.6 0.7 0.7 0.8 0.0 0.0 0.0 0.0 0.0 0.4 0.5 0.5 0.6 0.7 0.7 0.0 0.0 0.0 0.0 0.0 S1 0.4 0.5 0.5 0.6 0.7 0.1 0.0 0.0 0.0 S2 0.4 0.5 0.5 0.6 0.7 0.6 0.0 0.0 0.0 0.0 0.0 0.5 0.5 0.6 0.7 0.7 0.8 0.2 0.0 0.0 0.0 0.0 0.5 0.6 0.7 0.7 0.8 0.9 0.6 0.0 0.0 0.0 0.0 0.6 0.7 0.7 0.8 0.9 1.0 0.9 0.2 0.0 0.0 0.0 0.3 0.7 0.8 0.9 1.0 D2 1.0 0.0 0.0 0.0 0.0 0.7 0.7 0.8 0.9 1.0 D1 0.4 0.0 0.0 0.0 0.0 0.6 0.7 0.7 0.8 0.9 1.0 0.9 0.2 0.0 0.0 0.0 0.5 0.6 0.7 0.7 0.8 0.9 0.8 0.1 0.0 0.0 0.0 0.5 0.5 0.6 0.7 0.7 0.8 0.7 0.4 0.0 0.0 0.0 0.4 0.5 0.5 0.6 0.7 0.7 0.7 0.5 0.3 0.0 0.0 S1 0.4 0.5 0.5 0.6 0.7 0.6 0.4 0.1 0.0 S2 0.4 0.5 0.5 0.6 0.7 0.7 0.6 0.6 0.3 0.0 0.0 0.5 0.5 0.6 0.7 0.7 0.8 0.7 0.7 0.1 0.0 0.0 0.5 0.6 0.7 0.7 0.8 0.9 0.8 0.2 0.0 0.0 0.0 0.6 0.7 0.7 0.8 0.9 1.0 0.9 0.3 0.0 0.0 0.0 0.7 0.7 0.8 0.9 1.0 D2 0.8 0.0 0.0 0.0 0.0 The goal of the agent i is to maximize its expected cumulative discount rewards:EQUATIONFor convenience, the learning agent treats all other agents as a joint opponent with the joint action a o ∼ π o (•|s) and reward r o . The action and reward of the learning agent are respectively denoted as a ∼ π(•|s) and r for notation simplicity.An agent treats other agents as part of the environment and ignores the non-stationarity posed by the change of other agents' policies as independent Q-learning (Tampuu et al., 2017; Tan, 1993) . Its policy is updated by:EQUATIONwhere Q is Q-network. Opponent modeling typically predicts the actions of other agents to address the non-stationary problem. The opponent model uses historical trajectory as input to predict ão ∼ π(•|τ ), where ão is the estimate of a o . Its policy is updated as:EQUATIONNote that we cast our discussion here to Q-learning. All can be similarly applied to other RL methods, such as PPO (Schulman et al., 2017) .The opponent's subgoal is the representation of the state that the opponent may have in the future based on the opponent's policy. Like "All roads lead to Rome", the opponent may perform different sequences of actions but eventually reach the same state. Instead of focusing on the details of each of the opponent's actions, the agent should focus on the state the opponent wants to reach.The opponent's subgoal distribution probability is based on the opponent's action sequence, that is, the opponent's policy, but its sample space is still the representation of the state. Here we decouple the subgoal from the opponent's policy and just consider decision-making problems conditioned on the opponent's subgoal. Formally, we transform the original stochastic game M into a stateaugmented MDP, defined by M G = (S, G, A i , P, R i , γ), where G is the subgoal space. Since G is a representation of future states the opponent may go, |G| is finite and less than or equal to |S|.The state-augmented MDP's state space S extends to the MDP with state-subgoal pairs < S, G >. Therefore, the policy based on the opponent's subgoal is updated as:EQUATIONHere s t+1 , g t is used instead of s t+1 , g t+1 , because of we assume that the next state of s t , g t follows the same goal. In the framework of OMG, g t and g t+1 will reach the same at the end of the episode. Observe state s and last opponent's action a o 8:Infer the subgoal ĝ by subgoal inference model q ϕ (g|τ )9:Choose action a by max a Q(s, ĝ, a) with ϵ-greedy Calculate prior subgoal ḡ by ( 6) or ( 7)14:Calculate subgoal g by ( 8)15:Update Q-network by (4)16:Update subgoal inference model q ϕ and p θ by ( 5) 17:end if 18: until convergence To demonstrate the difference between learning Q-values using the opponent's action Equation (3) and using the opponent's subgoal Equation (4), we carry out an experiment in an 11 × 11 gridworld with two agents, as detailed in Figure 3 . The Q-value using the opponent's action learns slower than the Q-value with the opponent's subgoal in Figure 3 (a), resulting from the tuple (s, a o , a) is more numerous than (s, g, a) in the Q-table. After convergence, the Q-value increases as it gets closer to the reward point, indicating a meaningful Q-value with the opponent's subgoal, as shown in Figure 3(b) .When there are fewer (s, g, a) than (s, a o , a), the method using (s, g, a) naturally holds the advantage of faster learning than the method of (s, a o , a). The quantity of (s, g, a) is contingent upon the goal selection, and we present an analysis of the quantitative relationship between pair (s, g) and (s, a o ), see Appendix A.1. In short, the number of (s, g) is significantly smaller than that of (s, a o ) in our method.In this part, we elaborate on the opponent modeling module, which is divided into two components: the subgoal inference model and the subgoal selector. The subgoal inference model utilizes the historical trajectory to predict opponent's subgoal, which act as the policy's input to make decisions during interaction phase. Meanwhile, the subgoal selector is responsible for scrutinizing the entire historical trajectory and choosing the suitable subgoal for training the subgoal inference model during the update phase.Subgoal inference model. The subgoal g is a representation of future states. Specifically, for a trajectory {s 0 , a 0 , a o 0 , . . . , s t , a t , a o t , . . . , s T }. The state corresponding to subgoal g t is one of future states N t = {s t+1 , s t+2 , . . . , s T }, denoted as s g t . We denote the mapping between states and subgoals by f ψ , where ψ is the parameters and ḡt = f ψ (s g t ). The objective of the subgoal inference model is to infer s g t from the historical trajectory τ t = {s 0 , a 0 , a o 0 , . . . , s t-1 , a t-1 , a o t-1 } at timestep t, even though s g t may be a state at timestep t + 1 or further. This is in accordance with the intuitive hypothesis, implying that the opponent's intention is often inferred after just a few initial actions.Here, we introduce variational inference and use a conditional variational auto-encoder (CVAE) as the subgoal inference model. In this model, we represent the posterior probability as q ϕ (ĝ|τ ) and the likelihood estimate as p θ (τ |g) with θ, ϕ denoting network parameters. Additionally, the condition vector of the model is encoded using an RNN. The subgoal's prior model, denoted as p ψ (ḡ|s g ), is constructed using a pre-trained variational autoencoder (VAE), with the prior subgoal state s g being derived from the subgoal selector as its input. The distribution of subgoal prior p ψ , subgoal posterior probability q ϕ and subgoal's prior p ψ (ḡ|s g ) are used normal distribution. The mapping f ψ represents sampling subgoal ḡ from p ψ using reparameterization trick. The detailed network architecture is presented in Figure 2 . The optimization objective of the subgoal inference model is:< θ, φ >= arg max θ,ϕE g∼q ϕ (ĝt|τt,st) log p θ (s t |ĝ t , τ t ) -KL q ϕ (ĝ t |τ t , s t )||p ψ (ḡ t |s g ) .(5)Subgoal selector. The objective of the subgoal selector is to choose the appropriate future state from N t as prior model's input. The selection of subgoal states plays a pivotal role in shaping the behavior of an agent, as it significantly impacts the pattern of the agent's policy, either leaning towards optimism or conservatism. This critical decision-making process becomes especially pertinent when dealing with cooperative games and general-sum games, where the dynamics of interaction are complex and multifaceted. In these contexts, we provide two distinct manners to guide the agent's decision-making:EQUATION)EQUATIONwhere V (s, g) = E a Q(s, g, a), N H t is the set of future states {s t+1 , • • • , s t+H }. We use states within the next H timesteps instead of all future steps because the subgoals of different trajectory fragments may have combinatorial properties. It gives the agent better generalization ability when facing different policy opponents. However, if we adopt the full horizon, the agent may prefer the goals near the terminal state, which is not conducive to the exploration of goal space.When utilizing the subgoal g as indicated in Equation ( 6), we pinpoint the state within a H-horizon that maximizes the V-value. The agent incorporates this as the subgoal to optimize the Q-function, thus adopting an optimistic strategy akin to the maximax strategy (Ben-Haim, 2006) , which applies to cooperative games. Conversely, if we choose the subgoal as presented in Equation ( 7), it corresponds to the state yielding the lowest value. The agent then employs this as the subgoal for Q-function optimization, leading to a conservative strategy similar to the minimax strategy, which is usually used in general-sum games.In conclusion, the subgoal selector and the subgoal inference model as a whole constitute the opponent modeling module. During the interaction phase, the subgoal inference model is used to get the inferred subgoal ĝ, which is combined with the state as the input to the Q-network. During the update phase, the prior subgoal ḡ generated by the subgoal selector provides the inference model for training. When policy updating, the subgoal inference model is unstable at the beginning, which disturbs the updating of the Q-network. Therefore, we use the following combination of the prior subgoal ḡ and the inferred subgoal ĝ,EQUATION)where ϵ is a hyperparameter that decreases to zero over training.For completeness, the full procedure of OMG is given in Algorithm 1. 
experiments: 
 First, we evaluate OMG's training performance in two environments (discrete and continuous state spaces) and then test its generalization against opponents with various policies in a complex environment. In all the experiments, the baselines have the same neural network architectures as OMG.All the methods are trained for five runs with different random seeds, and results are presented using mean and standard deviation. More details about experimental settings and hyperparameters are available in Appendix A.2. players and three foods are randomly generated in the environment. The goal of the agent is to collect all foods as quickly as possible. The agent can move in four directions or pick up the food. The agent must judge the opponent's target food as soon as possible to avoid futile actions for the same food.Predator-Prey (Lowe et al., 2017) is a three-against-one multi-agent environment with a continuous space. Three predators coordinate to touch the prey. The agent acts as one of the predators, and the opponents are the other two predators and the prey, which leads to the non-stationarity of the environment from the agent's view despite not belonging to one camp. The agent aims to maximize its reward and therefore needs to collaborate with the other two predators to complete the encirclement and cut the prey's escape route.) is a high-dimensional complex environment for research in the field of collaborative MARL based on StarCraft II. The agent joins a set of agents with unknown policies to accomplish the task. The only way to accomplish the task is to collaborate with the other agents. The agent's goal is to complete the task with a group of opponents controlled by unknown policies.In the experiments, we implement two variants of OMG, OMG-optimistic and OMG-conservative, based on the subgoal selection patterns in Equation ( 6) and Equation ( 7), respectively. OMG compared with the following methods:• Naïve OM (He et al., 2016) uses observation to directly model the opponent's policy, which assists the agent in decision-making by predicting the opponent's actions.• LIAM (Papoudakis et al., 2021) uses the observations and actions of the modeling agent with an encoder-decoder architecture, and the model learns to extract representations about the modeling agent, conditioned only on the local observations of the controlled agent. • D3QN & PPO & IQL (Wang et al., 2016; Schulman et al., 2017; Tampuu et al., 2017) are classical RL algorithms without opponent modeling.We use D3QN, PPO, and IQL as the backbone algorithms in Foraging, Predator-prey, and SMAC, respectively, to reproduce the performance of baselines. The versions of OMG that are based on D3QN and IQL incorporate "dueling" and "double" tricks over Algorithm 1. For OMG based on PPO, please refer to Appendix A.3 for details.We evaluate the performance of OMG on foraging and predator-prey, and the results are shown in Figure 4 . In the foraging environment, our method attains comparable scores to the baseline methods, and both the agent and the opponent achieve similar scores. OMG has a shorter episode length compared to other methods as demonstrated in Figure 4 (b), because OMG can predict the subgoal that the opponent is heading to and thus avoid wasting steps in the same direction. In addition, the results show that OMG-conservative is more suitable than OMG-optimistic in this scenario since this is a general-sum game. The action modeling-based methods, LIAM and Naïve OM, demonstrate comparable performance, whereas D3QN without opponent modeling, exhibits subpar results. In the predator-prey environment, the agent acts as the predator and collaborates with the other two uncontrolled predators to catch the prey. The results in Figure 4 (c) show that OMG obviously learns faster than action modeling methods, which demonstrates that OMG can also work efficiently in continuous state space. PPO without opponent modeling can hardly improve performance in training due to the non-stationarity caused by opponents. OMG-optimistic performs better than OMG-conservative because OMG-optimistic is suitable for the cooperative game.We evaluate the generalization of OMG in a complex multi-agent environment, SMAC, which enables the opponent to exhibit more diverse policies. The experimental results of 8m and 3s vs 5z are shown in Figure 5 . The test set consists of 30 opponents with different policies, trained by the IQL, VDN (Sunehag et al., 2017) , and QMIX (Rashid et al., 2020) . In 8m, the opponents are reorganized into three groups: 7 homologues, 6 homologues, and 7 non-homologues. In 3s vs 5z, the opponents falls into two groups: 2 homologues and 2 non-homologues. Here, homologue refers to the policy from the same algorithm with the same parameters, and non-homologue represents the policy from two different algorithms. The remained agents are controlled by OMG or baseline algorithms. Without opponent modeling, IQL struggles to adapt to various opponents, resulting in poor performance, especially when the opponent is non-homologue. This underscores the effectiveness of opponent modeling in autonomous agent tasks. LIAM and Naïve OM are the opponent's action modeling methods that contributed to the team's improved win rate to some extent. The mediocre performance of OMG-conservative is attributed to its overly cautious subgoal selection, but there is no significant performance drop compared to IQL, which is consistent with the "conservative". OMG-optimistic surpasses the baseline methods in cooperative tasks. OMG-optimistic cooperates with unknown opponents through positive subgoal selection, which is easier to win in hard scenarios.For opponents and training details, please refer to Appendix A.2.The results of the ablation study in Foraging are presented in Figure 6 . Specifically, Figure 6 excessively high nor excessively low. When H = 1, it is essentially equivalent to combining with QSS (Edwards et al., 2020) and opponent modeling. However, if H is set too high, such as H = 10, the agent may skip important states in the trajectory, leading to a degradation in performance. Therefore, selecting an appropriate value for H is crucial in achieving satisfactory results.In Figure 7 (a), we plot the ratio of that an opponent's future trajectory passes through the opponent's subgoal inferred by the agent, termed subgoal hit ratio. The subgoal hit ratio is calculated by reconstructing the subgoal state f -1 ψ (ĝ). The subgoal hit rate gradually improves during training, which indicates that the subgoal-based opponent modeling is able to predict the future state of the opponent. OMG tends to predict goals multiple steps ahead, making it difficult for opponents to reach immediately, resulting in a modest value that hit ratio convergence. There is a small gap between the subgoal hit rates of OMG-conservative and OMG-optimistic, which leads to longer episode length for OMG-optimistic than OMG-conservative, as illustrated in Figure 7(b) . The root cause lies in the differences in subgoal selection between OMG-conservative and OMG-optimistic. 
conclusion: 
 In this work, we introduce OMG, a novel method for opponent modeling based on subgoal inference. OMG is a simple and efficient opponent modeling method and can be combined with different RL algorithms. Unlike most opponent modeling methods, which primarily focus on predicting the opponent's actions, OMG focuses on modeling the opponent's subgoals. Specifically, it leverages the value function of the policy to guide the selection of subgoals, which yields two variants of OMG for cooperative and general-sum games, respectively. Empirical results demonstrate the remarkable performance achieved by OMG, as compared to baselines which are based on action modeling, and that OMG exhibits better generalization when cooperating with opponents with unknown policies. We analyze the subgoals obtained by the inference model, and the results show that they closely correlate with the opponent's trajectory. The limitation of OMG is it cannot handle open multiagent systems where agents may enter and leave the system during the interaction. This is left for our future work. 
 
 Appendix: A.1 ANALYSIS OF (s, g)In opponent modeling, we usually build (s, g) and (s, a o ) by observing the opponent's action trajectories. We construct a tree to describe the trajectories of the opponent's action sequences, as Figure 8 . The non-leaf nodes and edges represent the state and opponent's action respectively. Without loss of generality, we simplify the problem by using a complete tree with the leaf node as goal. The length of the action sequences is k and the opponent action space is denoted as A. We compare the number of (s, a) and (s, g) that can be observed via trajectories, and their sets are denoted as S a and S g respectively. The sizes of S a and S g as:card(S a ) = k-1 l=0 s∈S (l) n A = n k A -1 n A -1 n A card(S g ) = k-1 l=0 s∈S (l) g∈G I(s → g) ≤ |G| + n A • |G| n A + • • • + n k-1 A • |G| n k-1 A = k|G|where S (l) represents the set of all states of depth l in the tree. s → g means g is reachable from s. n A is the size of A. Let card(S g ) ≤ card(S a ), we get a bound over |G|, as (9). When the goal number of our method is within the bound, the number of expanded states can be significantly reduced, which means the RL algorithm learns faster than those methods based on action modeling.EQUATION)When |G| is below n A /k times the number of observed states, the goal-based opponent modeling method proves more advantageous compared to the methods based on action modeling. Consequently, this criterion can be met by maintaining a relatively modest value for k. Due to our method favoring the adoption of extreme values as goal states, a limited quantity of such states exist. So, it is loosely bound of |G| for OMG. Observe state s and last opponent's action a o 8:Infer the subgoal ĝ by subgoal inference model q ϕ (g|τ )9:Choose action a by π δ k (•|s, ĝ) Update value parameters by 12) 16:EQUATIONUpdate inference model q ϕ and p θ by Equation (5) 17: end forWe call any agent other than the autonomous agent itself "opponent," whether it is a teammate or rival. 


Decision: This multi-agent RL paper is on ad hoc teamwork and is built around the idea of inferring co-player subgoals. Reviewers mostly appreciated the paper's clear presentation, though one identified specific presentation issues which they said should be fixed in the final version. I also had a minor nitpick with the presentation too in that I noticed that the following reference, while deeply relevant to the paper, was missing from the discussion:

Vezhnevets, Alexander, et al. "Options as responses: Grounding behavioural hierarchies in multi-agent reinforcement learning." International Conference on Machine Learning. PMLR, 2020.

But presentation aside, no one raised very significant concerns with the novelty of the approach. Moreover, the model and its evaluation were seen as technically sound, and the reviewers appreciated the author's detailed responses during the rebuttal period.

Reviews: review: paper_summary: paper_summary: This paper introduces a multi-agent reinforcement learning algorithm focused on opponent modelling through subgoal inference, termed Opponent Modelling based on Subgoal Inference (OMG). Unlike traditional models that predict immediate actions of opponents, OMG leverages historical trajectories to infer an opponent's future subgoals. This method is designed to enhance generalisation across various unseen opponent policies and includes distinct mechanisms for cooperative and general-sum games. The authors report that their approach outperforms traditional action prediction models in several multi-agent benchmarks.
strength_weakness: strength_weakness: 1. “The subgoal prior model, denoted as $p_{\psi}$, is a pre-trained variational autoencoder (VAE) using the states previously collected in the environment”: What policy was used to collect these states to pre-train the prior model? This policy will have a huge impact on the coverage of the state space, and hence the subgoal inference model and final policy of OMG.

2. I have concerns about the generalizability and scalability of this approach. The authors test their approach on SMAC as a complex domain with one easy map (8m) and one medium map (3s_vs_5z). A number of SMAC maps have been shown to be solvable by independent learning methods such as IQL [1] and IPPO [2]. Can the authors showcase performance on hard SMAC maps such as 6h_vs_8z, corridor, 27m_vs_30m which requires learning more complex strategies and have a higher number of agents?

3. Experimental Concerns:

    3a. Why do the authors use different baselines for each environment i.e. D3QN, PPO, and IQL for Foraging, Predator-Prey, and SMAC respectively? Each of these baselines have been used for these environments. [4]

    3b. What variant of PPO was used for the Predator-Prey environment? Both IPPO [2] with individual agent critics and MAPPO [3] with centralised critics have shown to exhibit strong performance in a lot of cooperative benchmarks including predator-prey.

    3c. It would be helpful to assess the impact of the approach if the authors can compare their approach to state-of-the-art CTDE techniques in MARL i.e. QMIX.


[1] QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning

[2] Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?

[3] The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games

[4] Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks
questions: questions: 1. Could the authors provide more insight into how the subgoal predictor's performance might degrade or improve when scaling to environments with significantly more complex or numerous agents?
2. Are there specific types of multi-agent environments where OMG might not perform as expected? What limitations in the model's assumptions should be considered?
3. How does the model handle highly dynamic environments where the opponent's strategies evolve more rapidly than the model's training updates?
4. Please see weaknesses.
limitations: limitations: While the authors have discussed the technical validation of their model, there could be more emphasis on practical limitations, such as computational overhead and real-time applicability in fast-paced environments.
paper_summary: paper_summary: The paper is positioned within the ad-hoc teamwork problem in multi-agent systems, where an agent faces partners it has not seen before in training, and must learn to cooperate with them towards performing a task that benefits from cooperation. Authors deal with a specific requirement of ad-hoc teamwork that is opponent modelling: an agent's ability to model other agents in the system. They propose to model other agents at the level of their subgoals, inferred from the observed trajectories of interaction. They propose to learn a Q-function that also takes the inferred opponent sub-goal as input, thus making the policy of the protagonist agent conditioned on the sub-goal of the opponent. The empirical results seem to suggest minor improvements over previous opponent modelling works.
strength_weakness: strength_weakness: **Originality**
- I do not believe that goal and sub-goal inference for modelling agents is original. The paper is missing an entire line of research in their related works here, namely the inverse planning literature. This community has been studying inferring goals and sub-goals from trajectories through probabilistic modelling of other agents for a long time now (e.g. see [1,2] as a starting point and follow the thread of references and citations).  In addition, inferring and modelling goals of others is not original also in the ad-hoc teamwork literature (see [3,4]). Others also considered goal recognition between agents actively [5]. These are only some of the papers in this line of work, as there are many more. I am surprised to see none of these works are cited. I would like to see a discussion on what is the novelty/originality left after this literature is accounted for. Conditioning the Q-function on the goal of other is also not an original idea, but this is not the main claim any way.

Additionally, the problem of learning to cooperate with previously unseen teammates has been defined and named as "ad-hoc teamwork" in 2010 [6]. Since it is literally the problem setting of the authors, I am surprised there is no mention of this and the original paper is not cited.

[1] Zhi-Xuan T, Mann J, Silver T, Tenenbaum J, Mansinghka V. Online bayesian goal inference for boundedly rational planning agents. Advances in neural information processing systems. 2020;33:19238-50

[2] Ying L, Zhi-Xuan T, Mansinghka V, Tenenbaum JB. Inferring the goals of communicating agents from actions and instructions. InProceedings of the AAAI Symposium Series 2023 (Vol. 2, No. 1, pp. 26-33).

[3] Melo FS, Sardinha A. Ad hoc teamwork by learning teammates’ task. Autonomous Agents and Multi-Agent Systems. 2016 Mar;30:175-219.

[4] Chen S, Andrejczuk E, Irissappane AA, Zhang J. ATSIS: achieving the ad hoc teamwork by sub-task inference and selection. InProceedings of the 28th International Joint Conference on Artificial Intelligence 2019 Aug 10 (pp. 172-179).

[5] Shvo M, McIlraith SA. Active goal recognition. InProceedings of the AAAI Conference on Artificial Intelligence 2020 Apr 3 (Vol. 34, No. 06, pp. 9957-9966).

[6] Stone P, Kaminka G, Kraus S, Rosenschein J. Ad hoc autonomous agent teams: Collaboration without pre-coordination. InProceedings of the AAAI Conference on Artificial Intelligence 2010 Jul 5 (Vol. 24, No. 1, pp. 1504-1509).

**Quality**
- The experimental section only compares to two relatively simple opponent modelling works LIAM and "Naive OM". However, the authors for instance literally cite the "Machine Theory of Mind" paper and the "Modelling others using oneself in multi-agent reinforcement learning" in related works. Surely these are the closest competitors to their method. Additionally, some of the papers listed above under originality are also close competitors. I believe you need more than two methods in opponent modelling baselines. Especially the two methods compared are by no means considered the state-of-the-art.
questions: questions: Q1: "_However, focusing on the opponent’s action
is shortsighted, which also constrains the adaptability to unknown opponents in complex tasks_"  

What do you mean by "shortsighted"? How does that _constrain_ the adaptability? These are strong statements but are not concretised at all.

Q2: "_...bridge the information gap between agents_"

This concept of _information gap_ appeared out of nowhere. It is not explained either. What does this even mean? It needs to be clarified.

Q3: "_Autonomous agents, different from those jointly trained, can act autonomously in complex and dynamic environments..._"

You seem to be conflating autonomy with decentralized training or being self-interested here. The definition of autonomy does not preclude centralised training. I can have a set of autonomous agents train with privileged information, yet deploy them to act autonomously. 

Q4: "_Although a lot of the existing methods concentrate on modeling the opponent’s actions, we argue that such an approach is short-sighted, pedantical, and highly complex._"

Again, lots of sweeping and strong statements with no backing or clarification. What does short-sighted, pedantical, and highly complex mean? This does not sound professional or scientific. If you are going to actually complain about an entire line of literature, you need to make your statement more concrete. 

Q5: "_Generally, modeling an opponent’s actions just predicts what it will do at the next step. Intuitively, it is more beneficial for the agent to make decisions if it knows the situation of the opponent several steps ahead_"

This statement seems to ignore the trajectory prediction literature entirely, and tries to get away with it by saying "generally". 

Q6: "_Other methods that claim to predict the opponent’s goal [28 , 29], but without explicitly making a connection to the opponent’s goal..._" 

What does this even mean? Also, see the inverse planning / goal recognition works cited in Weaknesses and their references/citations for works that predict goals explicitly.

Q7: "_Unlike these methods, in this paper, we consider the most common..._"

I would argue that the setting where other _autonomous_ agents are also learning and adapting to our agent is the more common setting, and the fixed opponent policy is a big simplification of it. This can be justified in certain cases, but it certainly is not the _most common,_ except that it is more common in literature because it is simpler. But if the harder and more realistic problem is already being tackled, I do not see why this point is a plus. 

Q8: The $\pi^o, a^o$ notation is confusing. I would recommend using the pre-established notational norms in game theory / MARL, $\pi^{-i} , a^{-i}$ for all agents except $i$.

Q9: "_Opponent modeling typically predicts the actions of other agents to address the non-stationary problem_." 

At this point, I am a little confused. You have said "_Unlike these methods, in this paper, we consider the most common setting where opponents have unseen, diverse, but **fixed policies** during test_." So the opponents have fixed policies during test. Then there is absolutely no non-stationarity during test time. In fact, since $\pi^o$ is fixed within a test episode, the problem the agent is facing in test time is in fact an MDP. So you are only dealing with the setting where at each episode the agent might be facing a new MDP. How is this different from online single-agent reinforcement learning then?
limitations: limitations: Yes.
paper_summary: paper_summary: For cooperative games and general-sum games, this paper proposes opponent modeling by inferring an opponent’s subgoals, rather than inferring actions. They empirically verify that this leads to either similar or better scores over baselines in Foraging (discrete grid game), Predator-Pray (continuous game), and SMAC (high dimensional), as well as a reduction in required timesteps per episode to reach comparable scores to baseline.
strength_weakness: strength_weakness: - Improvements over scores in baselines are minor in Foraging. The main difference between the baselines appears to be in the reduction of the episode steps. It would be interesting to see if there is a reduction in the average time steps towards the end of training in Predator-Prey. 
- Minor typos and clarifications requested in Questions.
questions: questions: - L152 — missing word?  “will reach the same ” → “will reach the same state”
- L159-160 — confusing sentence: “...resulting from the tuple (s, a^o, a) is more than numerous than (s,g,a) in the Q-table”
- L190 — confusing preposition: “state as…” → “state of”? 
- L204 and L206-207 — both sentences here claim seemingly contradictory statements: “...adopting an optimistic strategy akin to the minimax strategy, which applies to cooperative games” seems to contradict the following statement “...leading to a conservative strategy similar to the minimax strategy, which is commonly used for general-sum games”. Are these both similar to minimax? 
- Section 4.2: Subgoal Selector. This section is a bit hard to follow the reasoning for Eq. 6 and Eq. 7 for OMG-optimistic and OMG-conservative, even after referring to 4.1 Can you clarify in this section why you provide these two distinct manners for subgoal selection? 
- Section 5, Figure 5 — It is not immediately clear what the X-axis is representing. The numbers in front of “non-homologue” and “homologue” do not have context (they are only clear from reading the Appendix). Can you add a sentence to the description of the Figure? Can you expand on the sentence: “The X-axis represents the opponent’s policies, and “homologue” refers to the policy learned by the same algorithm, while “non-homologue” represents different ones”? 
- L294 — possible typo: “interrupted” → “interpreted”
- Figure 7b — OMG-conserv shows step 1, 5, 6, and 8; OMG-optim shows steps 1, 5, 8, 10. Is there a reason the steps are not matched? (i.e both showing 1,5,6,8 or 1,5,8,10) 
- L299-300 — the wording of the definition for hit ratio is a bit unclear. Is this essentially the ratio of predicted opponent trajectory to actual opponent trajectory? 
- Section 5.5: How do you determine the hit ratio if the subgoal is several steps ahead of the current state? For example, if a predicted subgoal is 3 steps north, the opponent could reach the subgoal in 3 steps or more steps. How many steps can an opponent take between the subgoal prediction state in order for it to still count as a hit? 
- L479 — Typo: “ovservation” → “observation” 
- L504 — Typo: “remained” → “remaining”
limitations: limitations: Yes.
paper_summary: paper_summary: The paper proposes an algorithm for learning policy in a multi-agent environment that predicts subgoal intents of other agents. In this way, the authors address the non-stationarity problem in multi-agent learning. Experiments in three environments show an advantage of the approach over baselines.
strength_weakness: strength_weakness: - Experiments: It's a bit disappointing that in most of the presented experiments, the confidence intervals of OMG and baselines generally overlap (except in the predator-prey environment). I understand that controlling a single agent makes it hard to jump from 10% to 90%. However, I suggest choosing environments that amplify the impact of a single agent. For instance, the 3s_vs_5z environment seems well-chosen (hence the highest advantage). In either case, increasing the number of trials to make confidence intervals tighter would also help.

- The authors are sometimes overconfident in their claims. "Obviously, the complexity and uncertainty of predicting the action sequence are much higher than the goal itself" -- this is not always obvious. I agree that in some cases it is true, but there are also many domains where minor action changes lead to completely different states, resulting in much higher uncertainty in predicting subgoals. Instead of suggesting that OMG is always better, I recommend analyzing in which contexts OMG is better. Also, "... the results show they closely correlate with the opponent's trajectory" -- I acknowledge the reported 12-14% hit ratio, particularly given that the intents may change, but I'm not convinced that's enough evidence to claim "closely correlated".

- Equations 6-7: It's confusing that g in V(s_t, g) is the opponent's subgoal, while the notation resembles the standard goal-conditioned value function. I suggest replacing it with V(s_t, g^o), similar to a^o, or using any other indication that it's the opponent's subgoal. Additionally, to analyze the impact of choosing either (6) or (7), you should include an ablation (even a single experiment with just the results provided) in which you compare to naive choices, such as a random state or a fixed-distance state (e.g., s_t+3). This is especially important given that in Appendix D you report that 80% of subgoals are <=3 steps.

Minor comments:

- l.139: Technically, by modeling the opponents' subgoals, you don't gain any new information because everything is computed from the observation.

- l.148: Why is |G| finite? I think you didn't assume the finiteness of anything, including the action space.

- l.154-157: This claim needs stronger support to be that general. The experiment you show here is an illustrative example, too small to frame the takeaway so broadly.

- l.160: Why are there fewer subgoal tuples? I understand that both methods create exactly one datapoint for every step. If that's because of duplicates in the buffer, then this example may not be fully relevant (as in other environments, it is nearly impossible to repeat exactly the same state).

- l.297: I'd also mention here which value of H you've chosen.
questions: questions: What is the speed of training and inference of OMG compared to Naive OM and standard RL baselines (wall time)?
limitations: limitations: One limitation is mentioned in Section 6. Actually, I don't see why OMG cannot handle open systems. However, I'd add other limitations, such as: modeling subgoals instead of actions is much harder if the state space is much more complex than the action space (e.g., in video games). Additionally, predicting future states may be prohibitively challenging if the policy strongly depends on the opponent's moves (e.g., chess).

There is no potential negative societal impact of this work.

Comments: title: Response to reviewer FFHk
Response to reviewer fQcX
Response to reviewer FFHk
Response to reviewer fQcX
Response to reviewer FFHk
Response to reviewer gEZB
Thanks for the rebuttal
To reviewer gEZB
Response to Reviewer FFHk
Response to reviewer fQcX (Part Ⅱ)
Response to reviewer fQcX (Part Ⅰ)
Response to reviewer FFHE
Response to reviewer gEZB
Response to Reviewer FFHk
Rebuttal (Part Ⅲ)
Rebuttal(Part Ⅱ)
comment: Thank you for your detailed response. I am updating my score to a 5.
We apologize for not being able to complete the experiments you suggested before the discussion ended. However, the current results show that OMG-optimistic plays a significant role in such small team cooperation tasks. We will finish the remaining tests and include them in the revision. We hope you might consider adjusting the score. Thank you again for your insightful suggestions.
We apologize for not receiving your feedback before the discussion ended. We'd like to share our responses to your concerns once more.

**Originality:**

Our method introduces a new framework in opponent modeling. While modeling opponent' subgoal may seem intuitive, it differs significantly from previous methods and from works in plan recognition, inverse planning, and goal recognition.

**Quality:**

We've addressed the potential ambiguities you pointed out and enriched the references to relevant literature. Details are in our second response.

We hope this clarifies our work, and thank you again for your thoughtful review.
Thank you for your review.

I'd like to add another experiment result: On the 2s_vs_1sc map, OMG, LIAM, and Naive OM all achieved 100% win rate.
Has my latest response addressed your concerns? If you have any further questions, please let me know. Your feedback is very important to us. Thank you again for your review.
Thank you again for your valuable suggestions. Indeed, OMG achieves better results on this kind of map. We haven't run OMG-conservative yet. According to previous experiments, OMG-optimistic usually performs better than OMG-conservative on SMAC. We'll complete the experiment but will exceed the discussion deadline.
Thank you for the additional results. As you can see, this kind of evaluation amplifies the difference between OMG and other methods, hence allowing for more meaningful conclusions. Have you also checked the performance of OMG-conservative in the 2c_vs_64zg task?
Thank you sincerely again for your comments and appreciation.
Thank you for your rebuttal. I appreciate the additional clarifications provided and have decided to update my score, provided the additional experiments are added to the final version of the paper.
Has my response addressed your concerns? If there are any remaining issues, please let me know. If everything is clear, could you consider adjusting the score? Thank you sincerely for your review.
Thank you for your acknowledgement of the previous reply. Some experimental results are as follows:

|   | OMG-optim | LIAM | Naive OM |
|:-----:|:-----:|:-----:|:-----:|
| corridor | 0% | 0% | 0% |
| 2c_vs_64zg | 64.4% ± 8.1% | 48.4% ± 6.2% | 41.2% ± 15.2% |

On the corridor map, both OMG and the baseline models had a 0% win rate because the teammate policies trained by QMIX failed to master this hard task.

On the 2c_vs_64zg map, OMG perform better than the baseline algorithms and even over QMIX's 58% win rate. We noticed that OMG often led to the unit sticking closer to the teammate to avoid getting surrounded by enemies.

Other experiments are still running and we will provide them as soon as possible. Thank you again for your acknowledgement.
Thank you for your response. I acknowledge the clarifications by increasing my rating. I'd be happy to increase it even further if the experiments were extended as I suggested, with a proper discussion of the results.
Sec 2 Para 6: 

Plan Recognition[58] involves understanding and predicting hidden aspects of an observed entity's trajectory, such as its goals, plans, and underlying policies. Among its key methods are inverse planning [59,60], which emphasizes deducing the decision-making process, and goal recognition [61], which focuses on predicting the ultimate goal or desired final state. DUP[62] approaches plan recognition by using distributed representations of actions to discover plans not found in existing plan libraries. Some works focus on improving the ability of goal recognition instead of RL policies[63,64]. PRP[65] uses model-based algorithm to handle unreliable observations and recognize plans. Unlike existing plan recognition methods, our method aims to enhance policy by opponent modelling, specifically within multi-agent scenarios where no prior knowledge is available.

References

[58] Carberry, Sandra. "Techniques for plan recognition." User modeling and user-adapted interaction 11 (2001): 31-48.

[59] Zhi-Xuan T, Mann J, Silver T, Tenenbaum J, Mansinghka V. Online bayesian goal inference for boundedly rational planning agents. Advances in neural information processing systems. 2020;33:19238-50

[60] Ying L, Zhi-Xuan T, Mansinghka V, Tenenbaum JB. Inferring the goals of communicating agents from actions and instructions. InProceedings of the AAAI Symposium Series 2023 (Vol. 2, No. 1, pp. 26-33).

[61] Blaylock, N., Allen, J., 2006. Fast hierarchical goal schema recognition. In: Proceedings of the 21st AAAI National Conference on Artificial Intelligence. pp. 796–801.

[62] Tian, X., Zhuo, H., Kambhampati, S., 2016. Discovering underlying plans based on distributed representations of actions. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. pp. 1135–1143.

[63] Vered, M., Kaminka, G., 2017. Heuristic online goal recognition in continuous domains. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence. pp. 4447–4454.

[64] Shvo M, McIlraith SA. Active goal recognition. InProceedings of the AAAI Conference on Artificial Intelligence 2020 Apr 3 (Vol. 34, No. 06, pp. 9957-9966).

[65] Sohrabi, S., Riabov, A., Udrea, O., 2016. Plan recognition as planning revisited. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence. pp. 3258–3264.

Other minor modifications are not listed in detail here, such as the use of symbols $\pi^o, a^o \rightarrow \pi^{-i}, a^{-i}$.
Thank you for your acknowledgement of the previous reply. Openreview is currently unable to continue uploading the revision version. We have included the major revisions in this reply.

Sec 1 Para 1-2: 

Autonomous agents are systems capable of making decisions and acting independently in their environment, often operating without direct human intervention [3]. These agents can either cooperate with or compete against each other, depending on the context. In cooperative scenarios, many multi-agent reinforcement learning (MARL) methods [18,36,30,34] aim to bridge the information gap between agents [49] by training agents in a centralized manner, called centralized training with decentralized execution, enabling agents to work together seamlessly to accomplish cooperative tasks. Alternatively, fully decentralized methods[15,35] seek to break free from the constraints of centralized training, allowing agents to reach collaboration in a simpler and decentralized manner. In competitive scenarios, NFSP[13], PSRO[17], and DeepNash[26] employ self-play to train agents for equilibrium strategies, allowing agents to adapt and improve their policy. By considering how the agent affects the expected learning progress of other agents, LOLA[9] and COLA[44] apply opponent shaping to this setting. Overall, these methods focus on training agents in a way that accounts for their interactions, resulting in a set of policies that enable effective collaboration or competition within a group of agents.

While the above methods emphasizes the collective behavior of agents, it is also crucial to consider the role of individual agents, particularly self-interested agents, in these multi-agent environments. A self-interested agent[50,51] operates with the primary goal of maximizing its own benefits, even when interacting with other agents. When the objectives of a self-interested agent align with those of the team, this scenario falls under ad-hoc teamwork[52,53,54]; however, in more general cases, these interactions are framed as noncooperative games [56,55]. A key technique for self-interested agents in such settings is *opponent modeling*[3,57], which enables them to analyze and predict the actions, goals, and beliefs of other agents. By modeling the intentions and policies of other agents, the training process of the agent might be stabilized [24]. Many studies rely on predicting the actions [12,14,11,22,23], goals [29,28], and returns [37] of opponents during training. Then, the autonomous agent can adapt to different or unseen opponents by using the predictions or representations that are produced by the relevant modules.

References

[1-48] References from the original text.

[49] Tan, M. . "Multi-Agent Reinforcement Learning : Independent vs. Cooperative Agents." Proc. of 10th ICML (1993).

[50] Shoham, Yoav, and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.

[51] Gintis, Herbert. "Modeling cooperation among self-interested agents: a critique." The journal of socio-economics 33.6 (2004): 695-714.

[52] Melo FS, Sardinha A. Ad hoc teamwork by learning teammates’ task. Autonomous Agents and Multi-Agent Systems. 2016 Mar;30:175-219.

[53] Chen S, Andrejczuk E, Irissappane AA, Zhang J. ATSIS: achieving the ad hoc teamwork by sub-task inference and selection. InProceedings of the 28th International Joint Conference on Artificial Intelligence 2019 Aug 10 (pp. 172-179).

[54] Stone P, Kaminka G, Kraus S, Rosenschein J. Ad hoc autonomous agent teams: Collaboration without pre-coordination. InProceedings of the AAAI Conference on Artificial Intelligence 2010 Jul 5 (Vol. 24, No. 1, pp. 1504-1509). 

[55] Russell, Stuart J., and Peter Norvig. Artificial intelligence: a modern approach. Pearson, 2016.

[56] Nash, John F. "Non-cooperative games." (1950).

[57] Nashed, Samer, and Shlomo Zilberstein. "A survey of opponent modeling in adversarial domains." Journal of Artificial Intelligence Research 73 (2022): 277-327.
Thank you sincerely for your comments and appreciation.
The test performance on 27m_vs_30m as follows:

|   | OMG-optim | LIAM | Naive OM |
|:-----:|:-----:|:-----:|:-----:|
| win rate | 47.4% ± 14.1% | 39.0% ± 9.3% | 38.6% ± 15.0% |

The homogeneous agents collaborating with the baselines are trained using the QMIX algorithm, achieving a win rate of 49%. OMG outperforms these baselines and reaches a win rate close to that of the well-trained QMIX team, demonstrating its effectiveness even in environments with a larger number of opponents.
You have addressed my concerns and I have no further comments. I would like to maintain my score.
The response only partially address some of reservations. I choose to increase my score to acknowledge this, however I still do not think the paper is ready for publication and _at least_ must have a strong writing revision.
Thanks for your valuable comments.

> Actually, the predator-prey results were fine, I was more concerned about the results in foraging (where the confidence intervals are by an order of magnitude larger than the difference between OMG, naive OM, and LIAM) and partially about 8m. Could you please clarify what are the takeaways from the experiments in Foraging? If the algorithms differ mostly in terms of the number of solution steps, I'm not sure whether this is uniformly reinforced across the methods, or just a chance (given similar scores).

The results of Foraging experiments are shown in the following table:
|   | score | episode_step |
|:-----:|:-----:|:-----:|
| Naive OM  | 6.95 ± 0.33 | 11.61 ± 0.41 |
| LIAM | 6.99 ± 0.27 | 11.34 ± 0.37 |
| D3QN | 6.35 ± 0.2 | 12.57 ± 0.19 |
| OMG-conserv | 7.15 ± 0.31 | 10.91 ± 0.15 |
| OMG-optim	 | 6.83 ± 0.14 | 11.45 ± 0.26 |

In fact, the confidence intervals are not orders of magnitude apart. The chart may look a bit more exaggerated. 

The ability to predict opponent's action/subgoal is not the only factor that determines the performance. In the Foraging, the suboptimal strategy adjusts its trajectory towards the correct target after 1-2 steps of hysteresis. The baseline algorithms may realize that the target is invalid until the opponent reaches the target point near it, our method predicts this earlier, allowing for a earlier switch to an alternative target. However, due to the random initial positions, not every episode presents a dominant opportunity. A statistical difference of 0.5 at episode steps indicates a substantial advantage in this context.

> Since you provide some experiments in SMAC, I suggest trying more of them instead, particularly: 2m_vs_1z, corridor, 2s_vs_1sc, 2c_vs_64zg. In those tasks the impact of a single agent would be much more visible, and, usually, crucial for the success of the whole team. It would be exciting to see that two agents learn a cooperative tactic to win, and then OMG enters and it's able to adapt to that tactic. Especially in corridor, where precise coordination is crucial. Do you think it should be the case? I'm not sure if OMG would be able to follow a subtle tactic off-the-shelf (and hence it may be worse than the original team of agents, which is totally fine), but based on your motivation it should perform better than other variants of opponent modelling, right?

Thank you for your suggestion! OMG's advantage over other opponent modeling algorithms that predict actions lies essentially in its ability to predict further steps. Admittedly, not all tasks require this level of prediction. We'll follow your advice by testing on more maps and will share the results here.
Thank you for the clarifications and additional experiments.

> ... the confidence intervals of OMG and baselines generally overlap ...
> We have increased the number of runs to 10 seeds for Predator-prey ...

Actually, the predator-prey results were fine, I was more concerned about the results in foraging (where the confidence intervals are by an order of magnitude larger than the difference between OMG, naive OM, and LIAM) and partially about 8m. Could you please clarify what are the takeaways from the experiments in Foraging? If the algorithms differ mostly in terms of the number of solution steps, I'm not sure whether this is uniformly reinforced across the methods, or just a chance (given similar scores).

Since you provide some experiments in SMAC, I suggest trying more of them instead, particularly: 2m_vs_1z, corridor, 2s_vs_1sc, 2c_vs_64zg. In those tasks the impact of a single agent would be much more visible, and, usually, crucial for the success of the whole team. It would be exciting to see that two agents learn a cooperative tactic to win, and then OMG enters and it's able to adapt to that tactic. Especially in corridor, where precise coordination is crucial. Do you think it should be the case? I'm not sure if OMG would be able to follow a subtle tactic off-the-shelf (and hence it may be worse than the original team of agents, which is totally fine), but based on your motivation it should perform better than other variants of opponent modelling, right?
Thank you for your response to my comments. I have read your rebuttal and will provide further comments soon, as needed.
## Part Ⅲ

> Q5: "Generally, modeling an opponent’s actions just predicts what it will do at the next step. Intuitively, it is more beneficial for the agent to make decisions if it knows the situation of the opponent several steps ahead". This statement seems to ignore the trajectory prediction literature entirely, and tries to get away with it by saying "generally".

To the best of our knowledge, current literature on plan recognition [1, 2, 3], including the trajectory prediction methods you mentioned, requires substantial prior knowledge, such as hierarchical plan libraries or domain models. These methods, which depend on prior knowledge, are outside the scope of our discussion.

[1] Blaylock, N., Allen, J., 2006. Fast hierarchical goal schema recognition. In: Proceedings of the 21st AAAI National Conference on Artificial Intelligence. pp. 796–801.

[2] Sohrabi, S., Riabov, A., Udrea, O., 2016. Plan recognition as planning revisited. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence. pp. 3258–3264.

[3] Vered, M., Kaminka, G., 2017. Heuristic online goal recognition in continuous domains. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence. pp. 4447–4454.

[4] Tian, X., Zhuo, H., Kambhampati, S., 2016. Discovering underlying plans based on distributed representations of actions. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. pp. 1135–1143.

> Q6: "Other methods that claim to predict the opponent’s goal [28 , 29], but without explicitly making a connection to the opponent’s goal...". What does this even mean? Also, see the inverse planning / goal recognition works cited in Weaknesses and their references/citations for works that predict goals explicitly.

In the domain of inverse planning, goals are indeed explicitly predicted. We want to emphasize that this paper discusses methods for predicting an opponent's goals within the context of opponent modeling. While both inverse planning and opponent modeling involve understanding other agents' behaviors, inverse planning focuses on inferring goals and intentions, whereas opponent modeling is concerned with predicting opponent behavior and gaining an advantage in the scenario.

> Q7: "Unlike these methods, in this paper, we consider the most common...". I would argue that the setting where other autonomous agents are also learning and adapting to our agent is the more common setting, and the fixed opponent policy is a big simplification of it. This can be justified in certain cases, but it certainly is not the most common, except that it is more common in literature because it is simpler. But if the harder and more realistic problem is already being tackled, I do not see why this point is a plus.

Thank you for your suggestion. We acknowledge that the term "most common" might be ambiguous, and we will revise it to avoid confusion. In reality, due to the high costs of continuous learning, it is rare for deployed agents to continually learning and adapting. Instead, periodic updates are more common. We believe that the setting where opponents have unseen, diverse, but fixed policies during testing is more prevalent at present.

> Q8: The $\pi^o, a^o$ notation is confusing. I would recommend using the pre-established notational norms in game theory / MARL, $\pi^{-i}, a^{-i}$ for all agents except $i$.

Thank you for your suggestion. We will revise it in the revision.

> Q9: "Opponent modeling typically predicts the actions of other agents to address the non-stationary problem." At this point, I am a little confused. You have said "Unlike these methods, in this paper, we consider the most common setting where opponent s have unseen, diverse, but fixed policies during test." So the opponents have fixed policies during test. Then there is absolutely no non-stationarity during test time. In fact, since is fixed within a test episode, the problem the agent is facing in test time is in fact an MDP. So you are only dealing with the setting where at each episode the agent might be facing a new MDP. How is this different from online single-agent reinforcement learning then?

Firstly, the sources of non-stationarity differ. In single-agent RL, non-stationarity arises from changes in the environment. In MARL, an additional challenge is the uncertainty from opponents' policies. These different sources lead to varying degrees and forms of non-stationarity, which should not be conflated. Secondly, online reinforcement learning is a broader concept. In our setting, the agent must quickly adapt to opponents' policy changes, which aligns with the goal of online RL to enable agents to adapt rapidly.
## Part Ⅱ

> Q1: "However, focusing on the opponent’s action is shortsighted, which also constrains the adaptability to unknown opponents in complex tasks". What do you mean by "shortsighted"? How does that constrain the adaptability? These are strong statements but are not concretised at all.

Generally, modeling an opponent’s actions just predicts what it will do at the next step. A lot of opponent modeling papers[1,2,3] predict the next step action. Intuitively, it is more beneficial for the agent to make decisions if it knows the situation of the opponent several steps ahead. Predicting future states of the opponent have an advantage over predicting future actions. Just like our example in Sec 1 Para 3:

*For example, to reach the goal point of $(2, 2)$, an opponent moves from $(0, 0)$ following the action sequence $<\uparrow,\uparrow,\rightarrow,\rightarrow>$ by four steps (Cartesian coordinates). There are also 5 other action sequences, \textit{i.e.,} $<\uparrow,\rightarrow,\uparrow,\rightarrow>, <\uparrow,\rightarrow,\rightarrow,\uparrow>, <\rightarrow,\uparrow,\uparrow,\rightarrow>, <\rightarrow,\uparrow,\rightarrow,\uparrow>, <\rightarrow,\rightarrow,\uparrow,\uparrow>$, that can lead to the same goal. Obviously, the complexity of the action sequence is much higher than the goal itself.*

Similar conclusions are also verified by the experiments in Figure 3, and the corresponding analysis is given in Appendix A.1.

[1] Georgios Papoudakis, Filippos Christianos, and Stefano Albrecht. Agent modelling under partial observability for deep reinforcement learning. Advances in Neural Information Processing Systems, 34:19210–19222, 2021.

[2] Georgios Papoudakis and Stefano V Albrecht. Variational Autoencoders for Opponent Modeling in Multi-Agent Systems. arXiv preprint arXiv:2001.10829, 2020.

[3] Haobo Fu, Ye Tian, Hongxiang Yu, Weiming Liu, Shuang Wu, Jiechao Xiong, Ying Wen, Kai Li, Junliang Xing, Qiang Fu, et al. Greedy when sure and conservative when uncertain about the opponents. In International Conference on Machine Learning, pages 6829–6848. PMLR, 2022.

> Q2: "...bridge the information gap between agents". This concept of information gap appeared out of nowhere. It is not explained either. What does this even mean? It needs to be clarified.

In Multi-Agent Reinforcement Learning (MARL), "bridging the information gap between agents" refers to enhancing communication and information sharing among agents. This process involves reducing the uncertainty or lack of information each agent has about the environment, as well as the states, actions, or intentions of other agents. By effectively bridging this gap, agents can make more informed decisions, coordinate better, and ultimately achieve more optimal outcomes in their collective tasks. The following literature [1] explores the importance and impact of information sharing among agents.

[1] Tan, M. . "Multi-Agent Reinforcement Learning : Independent vs. Cooperative Agents." Proc. of 10th ICML (1993).

> Q3: "Autonomous agents, different from those jointly trained, can act autonomously in complex and dynamic environments...". You seem to be conflating autonomy with decentralized training or being self-interested here. The definition of autonomy does not preclude centralised training. I can have a set of autonomous agents train with privileged information, yet deploy them to act autonomously.

We will reorganize the discussion on "Autonomous agents and jointly trained" to eliminate any ambiguity. The aim here is to distinguish our method from those that are "jointly trained," as such methods struggle to generalize against opponents with varying policies, as results in Appendix C.

> Q4: "Although a lot of the existing methods concentrate on modeling the opponent’s actions, we argue that such an approach is short-sighted, pedantical, and highly complex.". Again, lots of sweeping and strong statements with no backing or clarification. What does short-sighted, pedantical, and highly complex mean? This does not sound professional or scientific. If you are going to actually complain about an entire line of literature, you need to make your statement more concrete.

These words "short-sighted, pedantical, and highly complex" are used to describe the weakness of "predicting action" in opponent modeling, which is also the advantage of our proposed "predicting subgoals". For example, A and B play the prophecy game, A can predict the next step of other agents, and B can predict the next 5 steps. Obviously, A is short-sighted compared with B.

We give intuitive examples that illustrate the advantages of predicting subgoals. That example is detailed in Sec 1 Para 3. Similar conclusions are also verified by the experiments in Figure 3, and the corresponding analysis is given in Appendix A.1.