Opponent Modeling based on Sub-Goal Inference

In appendix A. 2, this paper uses a set of identical states to acquire the action vectors of the policy in the test set. What is the detailed process of obtaining the set of identical states? Are these states sampled by a certain policy?

These states are stored when the policies in the test set are used, just to verify that the policies in the test set are the same. The states can be collected with any policy, and this does not affect the results.

The reason of baseline method choice is unclear. Why not compare with some newer opponent modeling methods, e.g., [1] and [2]?

[1] Greedy when sure and conservative when uncertain about the opponents. ICML 2022.

[2] Model-based opponent modeling. NeurIPS 2022.

OMG is a new exploration in the opponent modeling method, which is different from the previous opponent modeling ideas, so we choose the classic opponent modeling methods as the baselines.

[1] was not suitable for our testing environment for two reasons. Firstly, it is designed to work in a competitive environment. Secondly, it is essentially a fusion of LIAM-VAE and EXP3, where EXP3 is a bandit algorithm.

[2] is a method to deal with a constantly learning opponent. When the opponent’s policy remains unchanged, the method that degenerates to naive action of opponent modeling yields similar results to Naive OM in baselines.

Thanks for your comments. The minor issues you raised, we have addressed them in the revision. As follows, we address your concerns in detail.

In Section 3.2, this paper adopts a state-extended MDP. Therefore, for the next state, the Q-value equation should be $Q(s_{t+1}, g_{t+1}, a)$. However, the Eq. (4) writes it as $Q(s_{t+1}, g_{t}, a)$. It should be explained that why $g_t$ is the same as $g_{t+1}$.

We extend the state space of the MDP with state-subgoal pairs to form a state-augmented MDP $\mathcal{S}$. We assume that the next state of $s_t, g_t$ follows the same goal, so it is $s_{t+1}, g_t$. The $g_t$ is selected from $\mathcal{N}_t$. When the trajectory terminates, $g_t$ and $g_{t+1}$ reach the final state.

In algorithm 1, the action is sampled based on $Q(s,\hat{g},a)$ given $\hat{g}$ (line 9). However, when updating Q-network, the subgoal may be $\bar{g}$ instead of $\hat{g}$ based on Eq. (8). That means given the same experience tuple $(s, a, a^o, r)$, the Q-network input may be different for the sampling and learning phase, which does not conform with the canonical RL theory. What would the theoretical impacts be?

The hyperparameter $\epsilon$ is decreased during training. The probability of $g$ taking $\hat{g}$​ increases linearly up to 50,000 episodes. It does produce better results than just using $\hat{g}$​, as shown in Section 4.5.

We do not focus on the theoretical analysis of this problem, because the non-stationary problem is complex and the inference error of opponent modeling is intractable and unavoidable.

In Eq. (5), $\bar{g}$ is output by a prior model $p_{\psi}$ while in Eq. (6) and Eq. (7), it is from $f_{\psi}$. What is the relationship between $p_{\psi}$ and $f_{\psi}$? Moreover, when $f_{\psi}$ first appears in Page 5, it outputs $\bar{g}_t$ given $s_t^g$. However, in Eq. (6) and Eq. (7), its input format becomes $\mathcal{N}_t^H$. Why?

In essence, $f_\psi$ and $p_\psi$ are the same functions. The subgoal probability uses a normal distribution, with $p_{\psi}(\bar{g}|s^g)$ describes the probability distribution of subgoals. The mapping from state $s^g$ to subgoal $\bar{g}$ is expressed as $\bar{g} = f_\psi(s^g)$. This process involves encoding the state $s^g$ into the distribution and sampling from the distribution to derive $\bar{g}$. Apologies for the confusion, we makes it clearer in the revision.

Why in a general-sum game, a conservative strategy is more suitable? Given the opponents' subgoal, shouldn't we just maximize our own Q-value?

There are some misunderstandings here. That is the intention of the opponent, that to maximize or minimize our Q-value, which is just used to choose opponents' subgoal. The agent's policy is always to maximize the Q-value.

How to get the $f^{-1}_{\psi}$ in Section 4.6?

$f^{-1}_{\psi}$refers to the decoder in the VAE, which is trained using the states data in the pre-training phase.

How to compute $card(\mathcal{S}_g)$ in Appendix A.1? Based on my understanding, if we assume every state can be transit to a goal state after a certain action sequence, $card(\mathcal{S}_g)$ should be $\frac{n_A^k-1}{n_A-1}|G|$. In addition, the sentence "Moreover, a lower $k$ value, signifying predicted subgoals, facilitates generalization. So, it is loosely bound of $|G|$ for OMG. Due to our method favoring the adoption of extreme values as goal states, a limited quantity of such states exist" is confusing.

It's important to note that not every state can be transit to every goal, so $\frac{n_A^k-1}{n_A-1}|G|$ is not correct. Intuitive explanation for $card(\mathcal{S}_g) \leq k|G|$ is that each goal as a leaf node in a tree of depth k, have at most k ancestor state. Only each ancestor state can transition to the corresponding goal state after a certain sequence of actions. Therefore, there are at most $k|G|$ of these ancestor states.

We modified the confusing statement in the revision, as follows: "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."

Thanks for your comments. Below is our detailed explanation of your concerns.

I don't think predicting subgoals itself alone can be claimed as a significant contribution in comparison to previous work on opponent modelling. [1] predicts the opponent’s goal as well. Also, the subgoals discussed in OMG are essentially future states of the opponent, and predicting future states are not necessarily better than predicting future actions.

The immediate idea is that predicting state contains more information than predicting action. We must acknowledge the fact that each method has its specific conditions of application and also has certain limitations. There is no guarantee that OMG will perform better than any method predicting future actions in any environment. In this paper, we empirically demonstrate that OMG has a general advantage over methods that predict actions of opponents. In addition, the method of [1] is to model the opponent's goal, but these goals need to be manually preset, discrete and low-dimensional, which obviously cannot be applied in such environments as Predator-Prey and SMAC.

Intuitively, 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, 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.

I don't think it is a correct statement to say that most previous work on opponent modeling predicting the opponent's actions. For instance, [2] predicts a policy embedding. [3] is a meta-learning method for opponent modelling. [4] predicts which type of policy. very related work on opponent modeling are missing in the literature review. For instance, [2] [3] [4]. A full literature review on opponent modeling is suggested.

We revise this statement to be more rigorous and add those related work in the revision.

The general architecture of OMG that uses VAE to predict something is quite similar to many previous opponent modelling methods that use VAE as well: for instance [5] and [6].

From the level of method and algorithm idea, our method OMG has no similarity with [5] [6]. It is just that the same VAE network is used, but for the different purpose.

Firstly, [6] is the paradigm of CTDE, which is different from our setting of Autonomous agent. Although VAE is used in [6], it is still an action modeling method in essence. [5] is LIAM's previous work, which used supervised learning methods to construct mapping $<o_t, a_{t-1}, r_{t-1}, d_{t-1}>$ to $<a_t^{-1}>$ via VAE. OMG use VAE to encode future state as subgoal prior. It is worth noting that the future state is associated with the Q-value, which is novelty.

the last sentence of section 3.2. "In short, the number of (s,g) is significantly smaller than that of (s,a)". Please provide strong evidence for this, as I do think it is domain-dependent whether the number of (s,g) is larger or smaller than (s,a).

"In short, the number of (s,g) is significantly smaller than that of (s,a)" does not always hold, depending on the method of GOAL selection. In the framework of our method, this is a reasonable conclusion. We prove our point in Appendix A.1. It is a well-known fact that no one method is suitable for all domains. Although OMG is not a panacea, its conditions are not strict and verified by experiments.

Except for the experimental results, I am not convinced why predicting subgoals (i.e., future states) as OMG does are better than predicting something else about the opponents (e.g., actions, policy embeddings, policy categories, etc.). Could you please provide more justifications on this?

Your examples of opponent modeling methods [1]-[6] have all been verified by experimental results to demonstrate the effectiveness of the algorithm, which is the standard paradigm in the field of opponent modeling. We conducted comprehensive experimental verification by comparing with modeling action of opponent methods (Sec 3.2), performance of training (Sec 4.3), generalization to unknown opponents (Sec 4.4), and inferred subgoal analysis(Sec 4.6). The conclusions also show that our method has certain advantages than modeling action of opponent methods. In addition, our method is intuitive, as agreed by other reviewer.

I think I understand why I was confused about $p_\phi$ now... It's not predicting subgoals, it's just a state embedding that's used to encode goal states compactly for the Q-function. I think the "g" notation confused me, because during the pre-training phase, the states being fed to the autoencoder aren't really "goals"; they're just arbitrary states to be encoded. Do correct me if I'm wrong... If I'm correct, I'd suggest altering the notation in the paper, since I don't think I was the only reviewer confused by this.

OMG consists of three phases: pre-training, training and execution. In the pre-training phase, an autoencoder $p_{\psi}$ is trained with arbitrary states. In the training phase, an inference model $p_{\phi}$ is trained with prior subgoals encoded by $p_{\psi}$, which act as hindsight samples. Note that all the notations $g$ in the text refer to the subgoals in the training stage, not in the pre-training stage. Therefore, the states fed to the autoencoder $p_{\psi}$ are on the trajectory and are also the future states. Hence, we use the term "goal" to denote the embedding of the future state. In the execution phase, $p_{\phi}$ predicts the subgoal given the history trajectory without hindsight. I hope this solves your confusion.

Thanks for your responses. I think I need time to process the above, but some aspects make more sense to me now.

There are some misunderstandings here. OMG is an episodic off-policy method and the training update phase is performed on the replay buffer $\mathcal{D}$.

Oh right, this is kind of obvious in hindsight.

I think I understand why I was confused about $p_\phi$ now... It's not predicting subgoals, it's just a state embedding that's used to encode goal states compactly for the Q-function. I think the "g" notation confused me, because during the pre-training phase, the states being fed to the autoencoder aren't really "goals"; they're just arbitrary states to be encoded. Do correct me if I'm wrong... If I'm correct, I'd suggest altering the notation in the paper, since I don't think I was the only reviewer confused by this.

Thank you for acknowledging our novel contributions as well as raising valuable questions. Regarding the minor issues you raised, we have addressed them in the revision. Below is our detailed explanation of your concerns.

One of the main points of confusion I have is that I'm not sure what $f_\psi$ and $p_\psi$ are supposed to be. They share the same parameters, $\psi$, so are they the same function, related functions, or is the notation accidentally overloaded? How are goals represented to the Q-function? Are they encoded via $f_\psi$?

In essence, $f_\psi$ and $p_\psi$ are the same functions. The subgoal probability uses a normal distribution, with $p_{\psi}(\bar{g}|s^g)$ describes the probability distribution of subgoals. The mapping from state $s^g$ to subgoal $\bar{g}$ is expressed as $\bar{g} = f_\psi(s^g)$. This process involves encoding the state $s^g$ into the distribution and sampling from the distribution to derive $\bar{g}$. Apologies for the confusion, we makes it clearer in the revision.

Yes, the subgoals encoded via $f_\psi$, and concatenate with the state as the input of Q-function.

I don't follow how $p_\psi(\bar{g}|s^g)$ can be pre-trained "with the prior subgoal state $s_g$ being derived from the subgoal selector". Doesn't the subgoal selector leverage the value function? How do we already know the value function during the pre-training phase?

$p_\psi(\bar{g}|s^g)$ represents a pre-trained variational autoencoder.

In the pre-training phase, the value function is unnecessary. We utilize data, namely states collected from any policy, to train the encoder capability of $p_\psi$. This phase does not involve a subgoal selector, rendering the need for a value function unnecessary.

In the training phase, the parameters of $p_\psi$ is fixed, and the prior subgoal state $s^g$ derived from the subgoal selector is encoded as the subgoal $\bar{g}$.

I'm assuming that the training update at line 15 in Algorithm 1 can only be performed using the experience at time $t$ after $\bar{g}$ has later been inferred at time $t+H$. Is this correct? If so then it should be spelled out -- I got very confused at first trying to figure out how $\bar{g}$ could be known when performing the update.

There are some misunderstandings here. OMG is an episodic off-policy method and the training update phase is performed on the replay buffer $\mathcal{D}$. That is to say, lines 6-10 in Algorithm 1 is executed repeatedly to collect the trajectories. Then, lines 11-15 in Algorithm 1 represent that OMG is trained on the replay buffer $\mathcal{D}$, where the state of the trajectory at timestep $t+H$ can be get to figure out the $\bar{g}$ at timestep $t$.

As the authors have not addressed the points of uncertainty regarding their method, I have reduced my score to reflect the unclear presentation. The new score also reflects the fact that the authors have not addressed the connections to previous work on opponent modelling brought up by reviewer W6q1.