Model-Based Opponent Modeling

If the opponent is also learning during the interaction, the opponent model fitted with historical experiences always lags behind, making the agent hard to adapt to the opponent. Moreover, if the opponent could adjust its policy according to the actions, intentions, or goals of the agent, then recursive reasoning may occur between agent and opponent. However, based on the lagged opponent model, the agent would struggle to keep up with the learning of opponent. To adapt to the learning and reasoning opponent, the agent should predict the current opponent policy and reason more deeply than the opponent.

MBOM explicitly simulates the recursive reasoning process utilizing the environment model, called recursive imagination, to generate a series of opponent models, called Imagined Opponent Policies (IOPs). First, we pretrain the agent’s policy $\pi$ using PPO [32] while interacting with $\nu$ different opponents with diverse policies that can be learned for example by [37]. and collects a buffer $\mathcal{D}$ which contains the experience $\left<s,a,a^{o},s^{\prime},\bm{r}\right>$, where $\bm{r}=\left<r,r^{o}\right>$. For zero-sum game ($r+r^{o}=0$) and fully cooperative game ($r=r^{o}$), $r^{o}$ can be easily obtained, while for general-sum game we make an assumption that $r^{o}$ can be accessed during experience collection. Then, using the experience buffer $\mathcal{D}$, we can train the environment model $\Gamma(s^{\prime},\bm{r}|s,a,a^{o};\zeta)$ by minimizing the mean square error

where $\hat{s}^{\prime},\hat{\bm{r}}=\Gamma(s,a,a^{o};\zeta)$, and obtain the level-0 IOP $\tilde{\pi}^{o}_{0}(\cdot|s;\phi_{0})$ by maximum-likelihood estimation,

To imagine the learning of the opponent, as illustrated in Figure 1, we use the rollout algorithm [38] to get the best response of the opponent to the agent policy $\pi$. For each opponent action $a^{o}_{t}$ at timestep $t$, we uniformly sample the opponent action sequences in the next $k$ timesteps, simulate the trajectories using the learned environment model $\Gamma_{\zeta}$, and select the best response with the highest rollout value

During the simulation, the agent acts according to the policy conditioned on the modeled opponent policy, $a_{t}\sim\pi(\cdot|s_{t},\tilde{a}_{t}^{o}\sim\tilde{\pi}^{o}_{0}(\cdot|s_{t};\phi_{0});\theta)$, and the learned environment model provides the transition $s_{t+1},\bm{r_{t}}=\Gamma(s_{t},a_{t},a_{t}^{o};\zeta)$. With larger $k$, the rollout has a longer planning horizon, and thus could evaluate the action $a^{o*}$ more accurately, assuming a perfect environmental model. However, the computation cost of rollout increases exponentially with the planning horizon to get an accurate estimate of $a^{o*}$, while in practice the compounding error of the environmental model also increases with the planning horizon [15]. Therefore, the choice of $k$ is a tradeoff between accuracy and cost. Specifically, for zero-sum game and fully cooperative game, we can approximately estimate the opponent state value $V^{o}(s)$ as $-V(s)$ and $V(s)$, respectively, and modify the rollout value like $n$-step return [36] to obtain a longer horizon (see Appendix C for the empirical effect of $k$)

By imagination, we can obtain the best response of the opponent to the agent policy $\pi$ and construct the simulated data $\{\left<s,a^{o*}\right>\}$. Then, we use the data to finetune the level-0 IOP $\tilde{\pi}^{o}_{0}(\cdot|s;\phi_{0})$ by maximum-likelihood estimation, and obtain the level-1 IOP $\tilde{\pi}^{o}_{1}(\cdot|s;\phi_{1})$. The level-1 IOP can be seen as the best response of the opponent to the response of the agent conditioned on level-0 IOP. In the imagination, it is the nested form as “the opponent believes [that the agent believes (that the opponent believes …)].” The existing imagined opponent policy is the innermost “(that the opponent believes),” while the outermost “the opponent believes” is $a^{o*}$ which is obtained by the rollout process. Recursively repeating the rollout and finetuning, where the agent policy is conditioned on the IOP $\tilde{\pi}^{o}_{m-1}(\cdot|s;\phi_{m-1})$, we could derive the level-$m$ IOP $\tilde{\pi}^{o}_{m}(\cdot|s;\phi_{m})$.

By recursive imagination, we get $M$ IOPs with different reasoning levels. However, since the learning and reasoning of the opponent are unknown, a single IOP might erroneously estimate the opponent. To obtain stronger representation capability and accurately capture the learning of the opponent, we linearly combine the IOPs to get a mixed IOP,

where $\alpha_{m}$ is the weight of level-$m$ IOP, which is taken as $p(\tilde{\pi}^{o}_{m}|a^{o})$, also denoted as $p(m|a^{o})$, the probability that the opponent action $a^{o}$ is generated from the level-$m$ IOP. Thus, $p(m|a^{o})$ indicates the similarity between the level-$m$ IOP $\tilde{\pi}^{o}_{m}$ and the opponent policy $\pi^{o}$ in the most recent stage. By Bayesian rule, we have

Updating $p(m|a^{o})$ during interaction can obtain a more accurate estimate of the improving opponent policy.

In practice, we use the moving average of $p(m|a^{o})$ as the prior $p(m)$, take the decayed moving average of $p(m|a^{o})$ as $\Psi_{m}$, and obtain $\bm{\alpha}$ by the IOPs mixer,

Softer-softmax [12] is a variant of softmax, which uses higher temperature to control a softy of the probability distribution. The IOPs mixer is non-parametric, which could be updated quickly and efficiently without parameter training and too many interactions (see Appendix B for empirical analysis on $\bm{\alpha}$). Therefore, the IOPs mixer could adapt to the fast-improving opponent.

For completeness, the full procedure of MBOM in given in Algorithm 1.

MBOM consists of several components, including a conditional policy, an environment model, and $M$ IOPs. They all interact with each other through model rollouts, which however makes it extremely hard to give an error analysis based on each component of MBOM. Therefore, we instead focus mainly on recursive imagination and Bayesian mixing, and give a profound understanding of MBOM. Proofs are available in Appendix A.

Without loss of generality, we define $\delta_{m}$ as the discrepancy between level-$m$ and $m$-$1$ IOPs in terms of estimated value function given the IOP, and $\varepsilon_{m}$ as the error of level-$m$ IOP compared to the true value function given the opponent policy, i.e., $\delta_{m}\doteq|\widehat{V}_{m}-\widehat{V}_{m-1}|$, $\varepsilon_{m}\doteq|\widehat{V}_{m}-V|$, and $\delta_{0}\doteq\varepsilon_{0}$. Then, we have the following two lemmas.

According to (6) and (7), we can express $\alpha_{m}$ as the following

where $d(s,a^{o})$ is the stationary distribution of pairs of state and action of opponent. Then, based on Lemma 1 and 2, we can obtain the following theorem, where $\widehat{\mathcal{M}}_{-1}$ denotes $\mathcal{P}(\cdot|s,a,a^{o})\cdot\pi^{o}(a^{o}|s)$, the true transition dynamics of agent.

Theorem 1 tells us the error accumulates as level $M$ increases. However, larger $M$ also has advantages. To analyze, we first define the benefit using the mixed IOP as In the error bound of Theorem 1, it is easy to see that the error accumulates as level $M$ increases, but at the same time, higher level also has advantages. To analyze, we need to define the benefit of using the mixed IOP as the optimization. We use the negative distribution distance $\eta\doteq-\|\hat{\pi}-\pi\|$ to denote the benefit of using policy in different levels, where $\hat{\pi}$ is the estimated opponent policy, $\pi$ is the true opponent policy and $\|\cdot\|$ is a general form of distribution distance function. For a mixing policy, we can define the benefit as:

Then, we have the following lemma and theorem.

According to Theorem 2, we know that the estimated probability distribution of the opponent converges to the true distribution of the opponent. It is obvious that larger $M$ improves the representation capability of IOPs and thus better satisfies the assumption in Lemma 3, but also increases the error bound in Theorem 1. Therefore, the selection of $M$ is a tradeoff between them (see Appendix C for empirically study on $M$).

We evaluate MBOM in two competitive tasks: (1) Triangle Game is an asymmetric zero-sum game implemented on Multi-Agent Particle Environments (MPE) [21]. When facing different policies of the opponent, the agent has to adjust its policy to adapt to the opponent for higher reward. (2) One-on-One is a two-player competitive game implemented on Google Research Football [18]. The goalkeeper controlled by the agent could only passively react to the strategies of the shooter controlled by the opponent and makes policy adaptation when the shooter strategy changes.

Baselines. In the experiments, we compare MBOM with the following methods:

• •

  LOLA-DiCE [9] is an expansion of the LOLA, which uses Differentiable Monte-Carlo Estimator (DiCE) operation to consider how to shape the learning dynamics of other agents.

• •

  Meta-PG [1] uses trajectories from the current opponents to do multiple meta-gradient steps and construct a policy that is good for the updated opponents.

• •

  Meta-MAPG [16] includes an additional term that accounts for the impact of the agent’s current policy on the future policies of opponents, compared with Meta-PG.

• •

  PPO [32] is a classical single-agent RL algorithm, without any other modules.

Opponents. We construct three types of opponents:

• •

  Fixed policy. The opponents are pre-trained but not updated during interaction.

• •

  Naïve learner. The opponents are pre-trained and updated using PPO during interaction.

• •

  Reasoning learner. The opponents are pre-trained and can model the behavior of the agent. The model is finetuned during interaction and their policy is conditioned on the predicted action of the model.

Performance. The experimental results against test opponents in Triangle Game and One-on-One are shown in Figure 2(f), and the mean performance with standard deviation over all test opponents is summarized in Table 1. Without explicitly considering opponent policy, PPO achieves poor performance. The learning of LOLA-DiCE depends on the gradient of the opponent model. However, the gradient information cannot clearly reflect the distinctions between diverse opponents, which leads to that LOLA-DiCE cannot adapt to the unseen opponent quickly and effectively. Meta-PG and Meta-MAPG show mediocre performance in Triangle Game. In One-on-One, since Meta-PG and Meta-MAPG heavily rely on the reward signal, adaptation is difficult for the two methods in this sparse reward task. MBOM outperforms Meta-MAPG and Meta-PG, because the opponent model of MBOM improves the ability to adapt to different opponents. And the performance gain becomes more significant when the opponent is naïve learner or reasoning learner, which is attributed to the recursive reasoning capability brought by recursive imagination in the environment model and Bayesian mixing that quickly captures the learning of the opponent.

Ablation Studies. The opponent modeling module of MBOM is composed of both recursive imagination and Bayesian mixing. We respectively test the functionality of the two components.

In recursive imagination, MBOM generates a sequence of different levels of IOPs finetuned by the imagined best response of the opponent in the environment model. For comparison, we use only $\phi_{0}$ as the opponent model (i.e., without recursive imagination), denoted as MBOM w/o IOPs, and use random actions to finetune the IOPs rather than using the best response, denoted as MBOM-BM. Note that MBOM w/o IOPs is essentially the same as the simple opponent modeling methods that predict opponents’ actions, like [11, 13, 10]. The experimental results of MBOM, MBOM w/o IOPs, and MBOM-BM are shown in Figure 3(a) and 3(b). MBOM w/o IOPs obtains similar results to MBOM when facing fixed policy opponents because $\phi_{0}$ could accurately predict the opponent behaviors if the opponent is fixed, which corroborates the empirical results in [11, 13, 10]. However, if the opponent is learning or reasoning, $\phi_{0}$ cannot accurately represent the opponent, thus the performance of MBOM w/o IOPs drops. The methods with IOPs perform better than MBOM w/o IOPs, which means that a variety of IOPs can capture the policy changes of learning opponents. When facing the reasoning learner, MBOM outperforms MBOM-BM, indicating that the IOPs finetuned by the imagined best response have a stronger ability to represent the reasoning learner.

In Bayesian mixing, MBOM mixes the generated IOPs to obtain a policy that is close to the real opponent. As a comparison, we directly use the individual level-$m$ IOP generated by recursive imagination without mixing, denoted as MBOM-$\phi_{m}$, and use uniformly mixing instead of Bayesian mixing, denoted as MBOM-$\rm unif$. The experimental results are illustrated in Figure 3(c) and 3(d). Benefited from recursive imagination, MBOM-$\phi_{1}$ and MBOM-$\phi_{2}$ show stronger performance than MBOM-$\phi_{0}$. MBOM consistently outperforms the ablation baselines without mixing when fighting against reasoning learners. The middling performance of MBOM-$\rm unif$ is due to not exploiting the more representative IOPs, indicating that Bayesian mixing could obtain a more accurate estimate of reasoning opponents.

We additionally provide analysis on the weight $\bm{\alpha}$ and ablation studies on hyperparameters including the rollout length $k$ and the level of recursive imagination $M$, which are available in Appendix B and C, respectively.

When facing multiple opponents, MBOM takes them as a joint opponent, which is consistent with the single-opponent case. We perform experiments in Predator-Prey [21]. We control the prey as the agent and take the three predators as opponents. In this task, the agent tries not to be touched by the three opponents. When the policies of opponents are fixed (e.g., enveloping the agent), it is difficult for the agent to get high reward. However, if the policies of opponents change during interaction, there may be changes for the agent to escape. The results are shown in Figure 4(a). When facing learning opponents, MBOM achieves performance gain, especially competing with the reasoning learner, which indicates that MBOM adapts to the learning and reasoning of the opponents and responds effectively. Meta-MAPG and Meta-PG do not effectively adapt to the changes of opponents’ policies and are prone to be touched by the opponents many times in a small area, resulting in poor performance. LOLA-DiCE, Meta-PG and Meta-MAPG underperforms PPO when against multiple reasoning learners, indicating their adaptation may induce a negative affect on the agent performance. Detailed experimental results with different opponents are available in Appendix D.

MBOM could also be applied to cooperative tasks. We test MBOM on a cooperative scenario, Coin Game, which is a high-dimension expansion of the iterated prisoner dilemma with multi-step actions [20, 8]. Both agents simultaneously update their policies using MBOM or the baseline methods to maximize the sum of rewards. The experiment results are shown in Figure 4(b). Meta-PG and Meta-MAPG degenerate to Policy Gradients for this task as there is no training set. Both learn a greedy strategy that collects any color coin, which leads to a zero total score of two players. LOLA-DiCE learns too slow and does not learn to cooperate within 200 iterations, indicating the inefficiency of estimating the opponent gradients. PPO learns to cooperate quickly and successfully, which corroborates the good performance of independent PPO in cooperative multi-agent tasks as pointed out in [6, 44]. MBOM slightly outperforms PPO, which indicates that MBOM can also be applied to cooperative tasks without negative effects. Note that we do not compare other cooperative MARL methods like QMIX [31], as they require centralized training.