Learning to Safely Exploit a Non-Stationary Opponent
Year: 2021

Abstract:
In dynamic multi-player games, an effective way to exploit an opponent’s weak1 nesses is to build a perfectly accurate opponent model. This renders the learning 2 problem a single-agent optimization which can be solved by typical reinforcement 3 learning. However, naive behavior cloning may not suffice to train an exploiting 4 policy because opponents’ behaviors are often non-stationary due to their adapta5 tions in response to other agents’ strategies. On the other hand, overfitting to an 6 opponent (i.e., exploiting only one specific type of opponent) makes the learning 7 player easily exploitable by others. To address the above problems, we propose 8 a method named Exploit Policy-Space Opponent Model (EPSOM). In EPSOM, 9 we model an opponent’s non-stationarity as a series of transitions among different 10 policies, and formulate such a transition process through Bayesian non-parametric 11 methods. To account for the trade-off between exploitation and exploitability, we 12 train a player to learn a robust best response to the opponent’s predicted strategy 13 by solving a modified meta-game in policy space. In this work, we consider a 14 two-player zero-sum game setting and evaluate EPSOM on Kuhn poker; results 15 suggest that our method is capable of exploiting its adaptive opponent, whilst 16 maintaining low exploitability (i.e., achieving safe opponent exploitation). Further17 more, we show that our EPSOM agent has strong performance against unknown 18 non-stationary opponents without further training. 19

In dynamic multi-player games, an effective way to exploit an opponent’s weak-1 nesses is to build a perfectly accurate opponent model. This renders the learning2 problem a single-agent optimization which can be solved by typical reinforcement3 learning. However, naive behavior cloning may not suffice to train an exploiting4 policy because opponents’ behaviors are often non-stationary due to their adapta-5 tions in response to other agents’ strategies. On the other hand, overfitting to an6 opponent (i.e., exploiting only one specific type of opponent) makes the learning7 player easily exploitable by others. To address the above problems, we propose8 a method named Exploit Policy-Space Opponent Model (EPSOM). In EPSOM,9 we model an opponent’s non-stationarity as a series of transitions among different10 policies, and formulate such a transition process through Bayesian non-parametric11 methods. To account for the trade-off between exploitation and exploitability, we12 train a player to learn a robust best response to the opponent’s predicted strategy13 by solving a modified meta-game in policy space. In this work, we consider a14 two-player zero-sum game setting and evaluate EPSOM on Kuhn poker; results15 suggest that our method is capable of exploiting its adaptive opponent, whilst16 maintaining low exploitability (i.e., achieving safe opponent exploitation). Further-17 more, we show that our EPSOM agent has strong performance against unknown18 non-stationary opponents without further training.19
1 Introduction20
In single agent reinforcement learning (SARL), an agent learns to act by iteratively interacting with21 an environment. In such a setting, an agent’s learning objective and its performance evaluation22 are normally clear and straightforward, e.g., its long-term cumulative rewards gained from the23 environment. However, in multi-agent reinforcement learning (MARL), one agent’s performance24 greatly depends on the behavior of other agents. Hence, finding a reliable learning objective and25 evaluation method become non-trivial [3, 9, 31, 48]. Naive solutions of the problem using SARL26 generalize badly [21] and optimizing the joint policy of all agents does not scale. Recent approaches27 combining game theoretical analysis with deep RL have seen some success in large zero-sum28 games [4, 44].29
Game theory offers a mathematical framework to model strategic interactions among players [28].30 Under perfect rationality [12], a central solution concept is Nash equilibrium (NE) where no player31 benefits from deviating from their equilibrium strategy. In a two-player zero-sum game without32 any inherent advantage for either player (e.g. as a first mover), a NE is a safe strategy to play (i.e.,33 playing not to lose) – NE guarantees a tie in the worst case in expectation. However, NE is not the34 most profitable strategy in many cases. In complex competitive games, such as poker, it is common35 that agents encounter opponents with bounded rationality, in the sense that they may at best play an36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
approximate Nash equilibrium strategy and often play dominated actions [5, 33]. Therefore, playing37 a NE can potentially forego significant rewards against sub-optimal opponents. This incentivizes38 players to deviate from the NE and exploit their opponents’ weakness (i.e., playing to win). However,39 the resulting strategy could render itself exploitable should it overfit to the current opponent. Playing40 to win can therefore lead to exploitation by other opponent strategies. In the case of deceptive41 opponents such exploitation is known as the “get taught and exploited” problem [35].42
To better balance the trade-off between playing to win against the current opponents (exploitation) and43 not losing to unknown opponents (exploitability), Johanson et al. [19] proposed a solution concept,44 named Restricted Nash Response (RNR). RNR and its variants [18, 19, 33] assume stationary45 opponents, i.e., the strategies they learn to exploit are unknown but fixed. However, in many real-46 world applications, opponents may adapt and change their strategies on an ongoing basis. For example,47 in Rock-Paper-Scissors when a player learns to best respond by playing Rock to an opponent’s strategy48 which always plays Scissors, the opponent may then learn to best respond to your best response by49 playing Paper. Furthermore, prior RNR approaches only provide one-off solutions in the sense that50 whenever we need to re-adjust the trade-off between exploitation and exploitability or the opponent51 uses a new fixed policy, we need to re-solve the updated game from scratch.52
In this work, we focus on problems with non-stationary opponents. An opponent’s learning process53 can be generally modeled as transitions among a mixture of unknown number of policies. This54 motivates the usage of a Dirichlet process mixture model. As we can only collect trajectories produced55 by the adaptive opponents online, we propose to learn our model in a streaming fashion. Given the56 predicted opponent policy from our model, we provide a general framework for training an agent57 to safely exploit the non-stationary opponent where safe exploitation means exploiting the current58 opponent with a low probability of being exploited by other opponents in future. We empirically59 demonstrate the ability of our approach to safely exploit a non-stationary opponent in Kuhn Poker, a60 simplified Poker game. Furthermore, once trained, our model can produce strong counter strategies61 to unseen opponents without any further training in new tournaments.62
2 Related Works63
A fundamental ability of an effective AI agent is the capacity to interact with other intelligent64 agents. Therefore, the capability of reasoning about other agents’ goals [34], private information [27],65 behavior [13] and other characteristics is crucial. The issue of non-stationarity in multi-agent systems66 resulting from coexisting agents is well-known and well documented [14, 32]. Classical solutions to67 resolve the issue of non-stationarity include centralized training [24], self-play [44], meta-learning [1]68 and opponent modeling [2]. When specifically applied to the issue of non-stationarity, most previous69 works focusing on opponent modeling which switches between different opponent models when a70 change in opponent(s) is detected. A switch of model may be triggered by a drop in opponent model71 prediction accuracy [10] or when performance in terms of reward received for a fixed policy drops72 [15]. Deep BPR+ [49] combines a measure of opponent model accuracy and reward tracking to decide73 when to learn a new policy. Significantly, most of these works limit the opponents’ non-stationarity74 to periodically changing their policies within a finite pre-defined set of stationary policies.75
In this work, we consider non-stationarity during the training stage arising from the opponents’76 concurrent learning dynamics, rather than drawing stationary opponents from a pre-defined set. The77 entire lifetime of an opponent can generally be modeled as a mixture of an unknown (possibly infinite)78 number of policies. This motivates the usage of a Dirichlet Process (DP) mixture model [6, 42] which79 can infer the number of mixture components from data and provide incremental model capacity80 on demand. Various approximate inference methods are reported for DP mixture models, such as81 Markov chain Monte Carlo [17] and variational inference [6, 16, 45]. However, these inference82 methods either do not adapt to an online setting or truncate the number of clusters to a finite value.83 Recently proposed streaming inference algorithms [23, 41] enable the DP mixture model to solve84 online non-stationary problems in a truly non-parametric way. Applications have been reported in85 task-free continual learning [22] and model-based reinforcement learning [47]. In this paper, we86 adopt this approach to model and simulate a non-stationary opponent for MARL.87
It is well known that finding a NE is PPAD-hard even in two-player games [8]. An exception is two-88 player zero-sum games where the NE can be tractably solved by a linear program (LP) in polynomial89 time [43]. However, in games with extremely large action spaces, approximate NE solutions, such90
as fictitious play (FP) [7] and counterfactual regret minimisation (CFR) [50], have to be used. An91 important design principle that underpins NE approximation is the iterative best-response dynamics.92 Two representative methods are Double Oracle (DO) [26] and Policy Space Response Oracle (PSRO)93 [21]. In the dynamics of DO [26], players are initialized with restricted strategy sets; then at each94 iteration, a NE will be computed over the current restricted sets. These sets will be expanded by95 adding the best-response strategy to the NE computed over the full strategy sets. The iterative96 process continues until the best response is in the restricted strategy pool. PSRO approximates DO by97 interleaving empirical game-theoretic analysis (EGTA) with deep RL. In contrast with DO, the game98 with restricted strategy sets has to be estimated through simulation. Furthermore, the exact analytical99 best-response oracle is replaced in PSRO by a deep RL oracle which calculates an approximate best100 response. PSRO is a general self-play framework for MARL and many approaches built upon it have101 been proposed to improve its performance [25, 29, 30, 39]. Our approach, EPSOM, is not limited to102 the self-play setting. In addition, although we favor solutions with low exploitability (i.e. solutions103 close to NE) as PSRO does, our ultimate goal is to find a robust best response to a non-stationary104 opponent rather than solving the game for an (approximate) NE.105
3 Preliminaries106
We consider the decentralized training and decentralized execution (DTDE) setting in zero-sum107 games where we have access to interaction trajectories ⌧ between our agent and the opponenti .108 Whilst our approach can be extended to games with multiple opponents, in this work we focus on109 2-player zero-sum games. Before introducing our algorithm, we present some necessary preliminary110 concepts and notation in the remainder of this section.111
3.1 Meta Normal-Form Game112
We consider opponent modeling in policy space and learn to respond to the predicted distribution113 of the opponents’ policies. We formulate this problem as solving a two-player normal-form game114 (NFG) between our agent and its opponents as a whole with notation adapted to our presentation. We115 denote a 2-player NFG by a tuple (⇧, U,N ) where ⇧i is player i’s set of policies and i 2 N where116 N = {1, 2}. For ease of notation, we take player 1 as the training agent and player 2 as its opponent.117 We use ⇧ = Q i2N ⇧
i to denote the set of joint policies (strategy profiles). U(⇡) : ⇧ ! <n is a118 payoff table of utilities for each joint policy ⇡ played by all players. ui(⇡) denotes the utility value119 for player i and joint policy ⇡. A player can choose a policy ⇡i from ⇧i or sample from a mixture120 (meta-strategy) over them i 2 ⇧i
where is a probability simplex. In the terminology of game121 theory, i is a mixed strategy and each policy ⇡i is a pure strategy.122
Each player in the game is assumed to maximize their utility. The most well-known steady-state123 concept of a game is the Nash equilibrium (NE). NE is a strategy profile ⇡ such that no player has an124 incentive to deviate from its current strategy given the strategies of the other players. Namely, each125 player’s strategy is a best response to others’ BR(⇡ i) = argmax⇡i ui(⇡i,⇡ i) 8i 2 N . We call a126 set of policies ✏-best responses to a joint opponents’ policy ⇡ i, when there exists an ✏ > 0, such127 that BR✏(⇡ i) = {⇡i : ui(⇡i,⇡ i) ui(BR(⇡ i),⇡ i) ✏}. An ✏-Nash equilibrium is a strategy128 profile that satisfies: ui(⇡) max⇡i0 ui(⇡i0,⇡ i) ✏ 8i 2 N .129
3.2 Exploitability and Exploitation130
To evaluate our learned policy ⇡1, we use two metrics. An agent’s policy’s ⇡1 exploitation of an131 opponent’s policy ⇡2 is the extra gain obtained by the agent compared to its NE value v1:132
!(⇡1,⇡2) = u1(⇡1,⇡2) v1.
This measures how much the policy ⇡1 exploits the weakness of the opponent’s policy ⇡2. However,133 in general, there is no guarantee that the learned policy ⇡1 has no weakness. Therefore, we also134 define the exploitability of a policy ⇡1 which measures the loss incurred when the agent faces the135
iA detailed definition of the trajectory in a stochastic game [38] can be found in Appendix A.1.
best opponent policy ⇡2 = BR(⇡1) compared to the agent’s Nash equilibrium value v1:136
✏(⇡1) = v1 u1 ⇡1,BR(⇡1)
= max ⇡10 min ⇡2 u1(⇡10,⇡2) min ⇡2 u1(⇡1,⇡2). (1)
From Equation 1 we can see that the exploitability of a policy is non-negative and represents the137 distance of policy ⇡1 to an equilibrium.138
3.3 Restricted Nash Response (RNR)139
Johanson et al. [19] consider a modified zero-sum game where an opponent has a restricted strategy140 space ⇧2p,⇡fix such that it plays a fixed policy ⇡fix with probability p and plays any possible policy141 from the original strategy space ⇧2 with probability 1 p. Given (p,⇡fix), they define a restricted142 Nash equilibrium as a strategy profile (⇡1⇤,⇡2⇤) such that ⇡1⇤ 2 BR(⇡2⇤) and ⇡2⇤ 2 BRp,⇡fix(⇡1⇤),143 where: BRp,⇡fix(⇡1⇤) = argmax⇡22⇧2p,⇡fix u
2(⇡1,⇡2). It is shown that ⇡1⇤ is the best response to144 ⇡fix among strategies which have equal or lower exploitabilities than ⇡1⇤, i.e.: ⇡1⇤ = BR✏(⇡fix),145 where ✏ = ✏(⇡1⇤). Therefore, ⇡1⇤ is called a p-restricted Nash response (RNR) to ⇡fix. An RNR can146 be computed by solving the modified game, we present a linear programming solver implementation147 for NFGs in Appendix A.2.148
4 Dirichlet Process Mixture Opponent Modeling149
This section presents our non-parametric Bayesian method for modeling a non-stationary opponent.150 We consider an opponent’s learning process as consecutive transitions from one policy to another151 such that one opponent can theoretically adopt infinitely many policies during its life-time. Therefore,152 we propose to use a Dirichlet process (DP) mixture to model the learning process as it has the ability153 to model an infinite number of clusters (policies in this case) while inferring the current number of154 policies from the data collected thus far. As our agent interacts with the opponent online, we learn a155 model with a sequential maximum-a-posteriori approach.156
We model an opponent policy as a parameterized function ⇡2 and denote the parameter space as157 . To avoid cluttered notation in this section, we use to represent the modeled opponent’s policy.158 DP(↵H) is a stochastic process with a concentration parameter ↵ and a base distribution H over .159 A random draw G ⇠ DP(↵H) is itself a distribution over , satisfying:160
(G(A1), ..., G(Ar)) ⇠ Dirichlet ↵H(A1), ...,↵H(Ar)
for every finite measurable partition A1, ..., Ar of . The full graphical model for opponent modeling161 is shown in Figure 1a. It illustrates a generative process where at step m, the opponent first samples a162 policy ̂m ⇠ G and then rolls-out this policy to collect a trajectory ⌧m.163
To facilitate Bayesian inference, two representations of DP are considered. The stick-breaking164 representation in Figure 1b reveals the discrete nature of G. G ⇠ DP(↵H) can be constructed165 as G = P1 k=1 k k where ⇠ GEM(↵) is an infinite-dimensional random variable sampled166 from the Griffiths-Engen-McCloskey (GEM) distribution and { k}1k=1 are i.i.d. sampled policies167 from H . At step m, the opponent samples a policy index zm ⇠ Categorical( ) and rolls-out the168 policy zm . Inference with the stick-breaking representation is required in order to handle the infinite169 dimensional . Therefore, the truncation method [6] is commonly used to limit the model capacity170 to a K mixture and infer the actual number of policies by collapsing redundant ones. This requires171 tracking all K policies simultaneously and does not adapt well to online settings.172
The Chinese restaurant process (CRP) representation in Figure 1c can be obtained by integrating173 out . This introduces temporal dependencies between the policies, which can be expressed by the174 conditional distribution:175
p zm+1 = k|z1:m =
8 >>><
>>>:
↵
m+ ↵ , k = Km + 1
|k|m m+ ↵ , 1  k  Km
(2)
where |k|m = Pm
i=1 I(zi = k) is the total number of trajectories from the k-th policy and Km is176 the number of realized policies up until step m. Inference with the CRP representation does not177 need to handle the infinite dimensional . Furthermore, at step m, we only need to track at most m178 policies (Km  m) while all policies beyond Km are independent from the collected trajectories179 ⌧1:m, and thus can be discarded from the model. In addition, the temporal dependencies between180 policies introduced by CRP can be used to develop an online learning algorithm.181
Given sampled trajectories ⌧1:m, the target182 of our opponent model is to assign each183 trajectory to a policy and update existing184 policies with assigned trajectories. This185 can be achieved by seeking maximum-a-186 posteriori (MAP) estimations of z1:m and187 1:Km . To deal with streaming trajectories,188 the MAP algorithm should operate in an189 online fashion. Therefore, given the CRP190 representation, we decompose the posterior191 into the product of the posterior from the192 last step, the current priors and the likeli-193 hood, which leads to a recursive form:194
p(z1:m, 1:Km |⌧1:m) /
✓Km 1+1Y
k=1
p( k) ◆ p(z1)p(⌧1| z1) ✓ mY
i=2
p(zi|z1:i 1)p(⌧i| zi)
◆ ,
/ p(z1:m 1, 1:Km 1 |⌧1:m 1)p( Km)p(zm|z1:m 1)p(⌧m| zm), (3)
where p( k) = H is the base distribution of the DP.195
The opponent model either assigns the current trajectory ⌧m to a previous policy k or creates a196 new policy Km 1+1 to model ⌧m. The choice is made according to the MAP trajectory assignment197 z⇤m = argmaxzm p(zm, z ⇤ 1:m 1|⌧1:m):198
p(zm = k, z ⇤ 1:m 1|⌧1:m) /
(R k ↵p( k)p(⌧m| k) d k, k = Km 1 + 1
p(zm = k|z⇤1:m 1)p(⌧m| m 1 k ) = |k| ⇤ m 1p(⌧m| m 1 k ), otherwise
(4) where |k|⇤m 1 = Pm 1 i=1 I(z ⇤ i = k). Here, the hard assignment z⇤m for ⌧m is based on previous199
assignments z⇤1:m 1 and policies m 1 k , which is equivalent to applying assumed density filtering200 (ADF) [41] to approximate the true posterior in Eq. (3) with a Delta distribution (z⇤1:m). The hard201 assignment prevents creating a new policy at each step if ⌧m is assigned to an existing policy, which202 significantly reduces the memory usage. Furthermore, the MAP estimations for all existing policies,203 except z⇤m , remain unchanged, which dramatically accelerates the algorithm. We then optimize the204 policy z⇤m by maximizing the likelihood of all trajectories assigned to it:205
mz⇤m = argmax z⇤m
log p( z⇤m) Y
z⇤i =z ⇤ m
p(⌧i| z⇤m). (5)
Where finding the global optimum is not tractable in non-conjugate cases, we take gradient steps to206 update nz⇤m as207
nz⇤m = m 1 z⇤m + r z⇤m log p( z ⇤ m ) Y
z⇤i =z ⇤ m
p(⌧i| z⇤m).
The entire algorithm fits into the general expectation-maximization (EM) framework. See Appendix208 A.4 for a detailed derivation.209
The original CRP in Eq. (2) encapsulates a prior that the distribution of the next policy mimics the210 empirical policy distribution from the history. This prior is not consistent with our knowledge of the211 policy evolution process since a new opponent policy is commonly updated from the previous one.212 Therefore, we adopt a sticky variant in Eq. (6) to incorporate the belief that the opponent tends to213
persist in the latest policy [11, 47].214
p zm = k z1:m 1 =
8 >>><
>>>:
↵
m 1 + ↵+  , k = Km 1 + 1
|k|m 1 + ̂(Km 1, k)
m 1 + ↵+  , 1  k  Km 1
(6)
where  0 is a ‘stickiness’ parameter and ̂ is the Kronecker delta function.215
Following Eq. (4), the probability of creating a new policy for ⌧n is given by:216
p(z⇤m = k) /
Z
k
↵p( k)p(⌧m| k) d k, (7)
where k = Km 1 + 1. We use a Monte Carlo method to estimate Eq. (7) by sampling new policies217 from p( k). However, sampling new policies from a data-independent prior p( k) is likely to yield a218 low trajectory likelihood p(⌧m| k), which prevents the new policy creation. Therefore, we update the219 sampled policies to increase the likelihood p(⌧m| k) by taking a few gradient steps before estimating220 the integration in Eq. (7).221
According to Eq. (6), the CRP prior encourages the opponent model to create redundant policies at the222 early stage when the number of trajectories n is small and ↵ dominates. Redundant policies could hurt223 the algorithm’s performance as it incurs extra cost in terms of computation and memory. Trajectories224 from the same ground truth policy could be assigned to different ks and these assignments never225 revisited. Therefore, an error correction mechanism has to be introduced. Here, we adopt a symmetric226 distance metric between two policies and develop a policy merge procedure based on the metric.227 Given a set of states S, we define d( k, j) = Es⇠Uniform(S) h JS ⇣ k(·|s) j(·|s) ⌘i
, where228 JS(·||·) is the Jensen–Shannon divergence and k(·|s) is the action distribution given state s under229 the policy k. When the distance between two policies is below a pre-defined threshold ⌘, the merge230 procedure simply re-assigns all trajectories of k to j .231
With the opponent model developed in this section, at step m, we can construct an opponent policy set232 ⇧̃2 = { mk } Km k=1 and a distribution ̃
2 over ⇧̃2. The distribution ̃2( = k) / |k|m + ̂(Km, k)233 is essentially the empirical distribution of z⇤1:m altered by the stickiness factor .234
5 Exploit Policy-Space Opponent Model235
In this section, we present how to learn a safe best response to this meta strategy, given a predicted236 distribution ̃2
ii over opponent’s policies. The advantages of our approach of focusing on policy space237 are two-fold: first, we do not need to assume the access to the opponent’s learning characteristics such238 as its training algorithm, its neural network’s architecture or its update frequency; we only require past239 trajectories. Additionally, the distribution of the types of opponent policy ̃2 gives us an approximate240 stable overview of the current opponent’s playing behavior compared to the opponent’s current241 policy whose updates greatly depend on the opponent’s learning characteristics and randomness from242 playing (e.g. exploration behavior) and training (e.g. stochastic gradient descent). Therefore, learning243 a response to this meta-strategy ̃2 will rely on less prior knowledge about the opponent’s learning244 characteristics and is more robust to noise.245
However, there is no guarantee that our learned meta strategy 1 has no (or at least low) exploitability.246 It has been shown that overfitting to an opponent strategy ̃2 often renders the resulting learned247 strategy brittle [19, 21, 46]. Such a brittle strategy performs badly when playing against different248 opponent strategies ̃20. Therefore, a more desirable goal is to learn a safe best response to an249 opponent meta-strategy ̃2. RNR solutions consider cases where the game to solve is fixed and250 known and the opponent’s policy is stationary. However, when we consider non-stationary opponent251 exploitation on policy space, the size of the meta-game to solve increases with the number of252 interactions between the training agent and the adaptive opponent. Furthermore, each player is free to253 learn and update its policy at any time point during the process.254
iiTo simplify our notation, we will ignore the subscript henceforth.
Algorithm 1: Exploit Policy-Space Opponent Model (EPSOM) input :Hyper-parameter p,H,E, an adaptive opponent i output :Policy ⇡i1,...,E and meta-policy i Initialize learning agent i’s policy ⇡i0 Initialize a memory buffer B Initialize opponent meta-policy i(·) = 1 for epoch e in {1, 2, . . . , E} do
for episode h 2 {1, 2, . . . , H} do Play an episode against the opponent with strategy 1RNR Collect the trajectory ⌧e,h and save them into B
end
̃2, ⇧̃2 = opponent_modeling(B) p̄ = 1|⇧̃2| P j p j ̃2(j)
Compute missing entries in U ⇧̃ from ⇧̃ = ⇧1 ⇥ ⇧̃2 by simulations _, 2RNR = RNR_solver(U
⇧̃, p̄, ̃2) for episode h 2 {1, 2, . . . , H} do
Sample ⇡̃2 from 2RNR Train oracle ⇡1 over ⇢ ⇠ ⇡1, ⇡̃2
end
⇧1 = ⇧1 [ ⇡1
Compute missing entries in U ⇧̃ from ⇧̃ = ⇧1 ⇥ ⇧̃2 by simulations 1RNR, _ = RNR_solver(U
⇧̃, p̄, ̃2) end
To address the above issues, we combine DO with RNR to solve a meta-game built from EGTA where255 the opponent’s policies are predicted by the opponent model from Section 4. Pseudo-code explaining256 our approach is presented in Algorithm 1. We maintain a utility table U ⇧̃ wherein rows represent257 learned policies for the training agent and columns represent a modeled policy of the opponent258 respectively. An epoch is defined as a fixed amount of episodes of games where we play against the259 opponent holding our strategy 1 fixed. At each epoch, we run our opponent model to predict the260 current distribution ̃2 of the opponent’s policies. If a new policy is detected, we will add it into ⇧̃2.261 Given ̃2, we run a p-RNR solver to obtain the opponent’s RNR meta-strategies 2RNR which is a262 restricted Nash solution to the current meta-game assuming that the opponent is playing according to263 ̃2 with probability at least p. Then we train an (approximate) best-response policy to 2RNR and add264 the new policy into ⇧1. We re-run a p-RNR solver to obtain our RNR meta-strategies 1RNR which265 we use to mix the policies in population ⇧1 for the next epoch’s playing policy.266
When a new type j of modeled policy ⇡2,j is added by our opponent model, we initialize a p-value267 pj = pinit to this type. Its p-value is incremented proportionally to the probability that the opponent268 plays this policy in the following epochs, ̃2(j), and clipped at 1. At each epoch, we calculate the269 average p-value p̄ = 1|⇧̃2| P j p
j ̃2(j) for solving current RNR strategies. In the extreme case where270 p̄ = 0, iRNR is the same as the Nash strategy in the current meta game. At another extreme where271 p̄ = 1, 2RNR = ̃ 2 and 1RNR = BR(̃ 2). Therefore, when we have low confidence in ̃2 (p̄ is272 low), we learn an approximate best response to opponent’s current Nash mixture which will enlarge273 our current empirical gamescape [3] and thus help to find strategies with lower exploitability. At the274 same time, the training agent becomes risk-adverse and the next epoch strategy 1RNR becomes a275 strategy closer to the Nash strategy of the current meta game.276
When p̄ is high, it means that our opponent model has high confidence that the opponent is playing ̃2277 and an approximate best counter strategy to ̃2 will be added into our policy population. The training278 agent becomes profit-driven and 1RNR becomes a strategy closer to BR(̃
2) in the next epoch.279 Therefore, mixing the playing policy by 1RNR flexibly switches the agent between risk-adverse and280 profit-driven depending on the confidence of the opponent model. In contrast with previous RNR281 solution, EPSOM can always recover a strategy with approximately the lowest exploitability it has282 seen so far as we maintain a population of policies.283
6 Experiments284
In this section, we empirically investigate whether the proposed method can (1) exploit an unknown285 non-stationary opponent while still maintaining a strategy with low exploitability, (2) improve its286 performance by continued training against different opponents and (3) exploit previously unseen287 opponents without further training. We verify EPSOM’s performance in Kuhn Poker [20], a simplified288 version of poker which importantly retains strategic elements useful for game-theoretic analysis. We289 use an agent learning to play using the PPO [37] algorithm as our opponent, which suffices to provide290 a non-stationary setting. More details about the game and our experiment implementation can be291 found in Appendix A.3.292
Figure 3: Opponent’s learning process modeled by trained CEPSOM: (left) CEPSOM adjusts playing strategy online; (right) CEPSOM plays an approximate Nash strategy. Each point is 2-D embedding of a modeled policy to which a trajectory produced by the opponent is assigned by our opponent model. Color bar indicates time sequence.
We select 3 representative algorithms as baselines. PSRO is a popular algorithm which guarantees the294 convergence to an approximate NE. As PSRO is a self-play algorithm, its is trained before playing295 against any adaptive opponents. Behavior cloning (BC) models the opponent’s policy by taking296 maximum likelihood estimation of history trajectories stored in a sliding-window buffer and learns297 an (approximate) best-response policy to it. PPO represents a canonical choice among many SARL298 algorithms. In our work, as agents and their opponents update asynchronously, we always evaluate299 each algorithm’s performance right after the opponent’s update for a more robust evaluation. The300 following results reported with mean and standard deviation (std) are all obtained by repeating the301 corresponding experiment over 5 random seeds.302
As shown in Figure 2, EPSOM can achieve a safe strategy with relatively low exploitability while still303 being able to exploit its opponent. Though PSRO plays a strategy with the lowest exploitability (⇡ 0)304 it also has very low exploitation against its opponent. In contrast, BC can exploit its opponent to a305 similar extent as EPSOM but it comes with the cost of high exploitability. The PPO algorithm has306
large variance and performs badly on average in this non-stationary setting. We also test a continual307 learning version of EPSOM which we name CEPSOM. It is implemented by training an EPSOM agent308 against 5 different opponents without re-initialization thereby building up a richer set of modeled309 opponent policies and a more robust best-response policy population. Its average performance over310 these opponents is also reported in Figure 2. In our experiments, we use an analytical method to311 calculate a best response to a given policy. We obtain similar results for approximate best response312 learned by RL which are reported in Appendix A.5.313
Next, we test these agent’s performance against two adaptive opponents implemented by PPO and314 TRPO [36] without further training and results are presented in Table 1. Relying on an opponent model315 to predict the current opponent’s policy type and flexibly adjusting its playing strategy accordingly,316 CEPSOM achieves the highest average exploitation against adaptive opponents. EPSOM also obtains317 positive average exploitation but with a much lower value, since EPSOM has only ever been trained318 with one opponent. PSRO plays a safe strategy and performs slightly better than EPSOM in terms of319 opponent exploitation. BC and PPO perform badly as they overfit to one opponent, and thus they are320 exploited by other adaptive opponents. Note that, in this zero-shot learning tournament, although we321 do not train EPSOM and CEPSOM, they still need to predict the opponent’s policy and solve the322 meta-game for a RNR solution given the prediction.323
Facing an adaptive opponent, a trained CEPSOM’s opponent model can assign trajectories collected324 during learning into modeled policies it has built. Therefore, we can visualize an opponent’s learning325 process by presenting a sequence of those modeled policies on a 2-dimensional plot. In Figure 3,326 we present two opponent’s visualized learning process when it faces (a) a trained CEPSOM agent327 which adjusts its playing strategy online based on its opponent model prediction, and (b) a trained328 CEPSOM agent which always plays an approximate Nash equilibrium strategy. We can see that in a329 non-stationary environment (left), the opponent’s learning exhibits a cyclic pattern. In contrast, the330 opponent’s learning is much more transitive (i.e., monotonically moving in one direction in the 2D331 space) in a stationary environment (right).332
7 Conclusion333
In this work, we propose a framework for training an agent to safely exploit its opponent. Compared334 to RNR and its variants, our work focuses on non-stationary opponents. We consider the opponent’s335 learning as a series of policy transitions and model such a process by a Dirichlet Process. Safe336 exploitation means that an agent can exploit an opponent’s weakness to maximize our utility while337 simultaneously maintaining a strategy which has low exploitability. This property is desirable as338 naively overfitting to one type of opponent could easily lead to exploitation by other opponents. We339 empirically verify our algorithm’s performance on Kuhn Poker, a simplified version of Poker.340
Opponent modeling based MARL algorithms typically require extra computation for learning a341 good opponent model. This cost often scales dramatically with the number of opponents, action342 space dimensionality and the complexity of the problem. It can be a heavy burden on an agent if343 it learns an opponent model from scratch online. Therefore, a more realistic way for utilizing the344 power of an opponent model is offline training and online prediction. We build CEPSOM based on345 this idea where we train one EPSOM agent across different opponents and aggregate knowledge by346 maintaining a never-reinitialized opponent model and policy population. Our experiment results show347 that CEPSOM can achieve high exploitation against a new adaptive opponent without further training,348 outperforming other representative baselines from SARL and MARL. In complex competitive games,349 a strong player can often encounter sub-optimal opponents and playing a Nash strategy can potentially350 forego significant profit. EPSOM, alongside many prior works, shows the potential of an opponent351 modeling based approach for solving this problem, and our preliminary results from CEPSOM352 demonstrate the possibility of a trained agent beating an as yet unseen adaptive opponent.353
EPSOM is limited by its computation and memory complexity. Naively applying EPSOM to more354 complex problems requires a great amount of resources. To alleviate this problem, we introduce355 policy merge to remove redundant policies in our opponent model. This approach could be improved356 by applying game theoretic analysis to our policy populations (agent’s self policies and modeled357 opponent policies). We leave the study of improving EPSOM’s scalability to future work.358
References359
[1] M. Al-Shedivat, T. Bansal, Y. Burda, I. Sutskever, I. Mordatch, and P. Abbeel. Continuous360 adaptation via meta-learning in nonstationary and competitive environments. arXiv preprint361 arXiv:1710.03641, 2017.362
[2] Stefano V. Albrecht and Peter Stone. Autonomous agents modelling other agents: A compre-363 hensive survey and open problems. Artificial Intelligence, 258:66–95, 2018. ISSN 0004-3702.364 doi: https://doi.org/10.1016/j.artint.2018.01.002. URL https://www.sciencedirect.com/365 science/article/pii/S0004370218300249.366
[3] David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max367 Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. In Interna-368 tional Conference on Machine Learning, pages 434–443. PMLR, 2019.369
[4] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak,370 Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, Rafal371 Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé372 de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon373 Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota 2 with large scale deep374 reinforcement learning. CoRR, abs/1912.06680, 2019. URL http://arxiv.org/abs/1912.375 06680.376
[5] Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, Terence377 Schauenberg, and Duane Szafron. Approximating game-theoretic optimal strategies for full-378 scale poker. pages 661–668, 01 2003.379
[6] David M Blei, Michael I Jordan, et al. Variational inference for Dirichlet Process mixtures.380 Bayesian analysis, 1(1):121–143, 2006.381
[7] GW Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and382 Allocation (TC Koopmans, Ed.), pages 374–376, 1951.383
[8] Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In 2006384 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 261–272.385 IEEE, 2006.386
[9] Wojciech Marian Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafiei,387 David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. arXiv preprint388 arXiv:2004.09468, 2020.389
[10] R. Everett and S. Roberts. Learning against non-stationary agents with opponent modelling and390 deep reinforcement learning. In 2018 AAAI Spring Symposium Series, 2018.391
[11] Emily B Fox, Erik B Sudderth, Michael I Jordan, and Alan S Willsky. An HDP-HMM for392 systems with state persistence. In Proceedings of the 25th international conference on Machine393 learning, pages 312–319, 2008.394
[12] Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, Cambridge, MA, 1991.395
[13] H. He, J. Boyd-Graber, K. Kwok, and H. Daumé III. Opponent modeling in deep reinforcement396 learning. In ICML ’16, volume 48, pages 1804–1813, 2016.397
[14] P. Hernandez-Leal, M. Kaisers, T Baarslag, and E.M. de Cote. A survey of learning in multi-398 agent environments: Dealing with non-stationarity. arXiv preprint arXiv:1707.09183, 2017.399
[15] Pablo Hernandez-Leal and Michael Kaisers. Learning against sequential opponents in repeated400 stochastic games. In The 3rd Multi-disciplinary Conference on Reinforcement Learning and401 Decision Making, 2017.402
[16] Michael C Hughes and Erik B Sudderth. Memoized online variational inference for dirichlet403 Process mixture models. Technical report, BROWN UNIV PROVIDENCE RI DEPT OF404 COMPUTER SCIENCE, 2014.405
[17] Hemant Ishwaran and Lancelot F James. Gibbs sampling methods for stick-breaking priors.406 Journal of the American Statistical Association, 96(453):161–173, 2001.407
[18] Michael Johanson and Michael Bowling. Data biased robust counter strategies. In David van408 Dyk and Max Welling, editors, Proceedings of the Twelth International Conference on Artificial409 Intelligence and Statistics, pages 264–271. PMLR, 2009. URL http://proceedings.mlr.410 press/v5/johanson09a.html.411
[19] Michael Johanson, Martin Zinkevich, and Michael Bowling. Computing ro-412 bust counter-strategies. In J. Platt, D. Koller, Y. Singer, and S. Roweis, edi-413 tors, Advances in Neural Information Processing Systems, volume 20. Curran As-414 sociates, Inc., 2008. URL https://proceedings.neurips.cc/paper/2007/file/415 6e7b33fdea3adc80ebd648fffb665bb8-Paper.pdf.416
[20] Harold W Kuhn. A simplified two-person poker. Contributions to the Theory of Games, 1:417 97–103, 1950.418
[21] Marc Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls,419 Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent420 reinforcement learning. CoRR, abs/1711.00832, 2017. URL http://arxiv.org/abs/1711.421 00832.422
[22] Soochan Lee, Junsoo Ha, Dongsu Zhang, and Gunhee Kim. A neural Dirichlet Process423 mixture model for task-free continual learning. In 8th International Conference on Learning424 Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.425
[23] Dahua Lin. Online learning of nonparametric mixture models via sequential variational approx-426 imation. Advances in Neural Information Processing Systems, 26:395–403, 2013.427
[24] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch. Multi-agent actor-critic for428 mixed cooperative-competitive environments. In Advances in Neural Information Processing429 Systems, pages 6379–6390, 2017.430
[25] Stephen McAleer, John B. Lanier, Roy Fox, and Pierre Baldi. Pipeline PSRO: A scalable431 approach for finding approximate Nash equilibria in large games. CoRR, abs/2006.08555, 2020.432 URL https://arxiv.org/abs/2006.08555.433
[26] H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost434 functions controlled by an adversary. In Proceedings of the 20th International Conference on435 Machine Learning (ICML-03), pages 536–543, 2003.436
[27] R. Mealing and J. L. Shapiro. Opponent modeling by expectation–maximization and sequence437 prediction in simplified poker. IEEE Transactions on Computational Intelligence and AI in438 Games, 9(1):11–24, 2017. doi: 10.1109/TCIAIG.2015.2491611.439
[28] Oskar Morgenstern and John Von Neumann. Theory of games and economic behavior. Princeton440 university press, 1953.441
[29] Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Pérolat, Siqi Liu, Daniel442 Hennes, Luke Marris, Marc Lanctot, Edward Hughes, Zhe Wang, Guy Lever, Nicolas Heess,443 Thore Graepel, and Rémi Munos. A generalized training approach for multiagent learning. In444 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia,445 April 26-30, 2020. OpenReview.net, 2020. URL https://openreview.net/forum?id=446 Bkl5kxrKDr.447
[30] Nicolas Perez Nieves, Yaodong Yang, Oliver Slumbers, David Henry Mguni, and Jun Wang.448 Modelling behavioural diversity for learning in open-ended games. CoRR, abs/2103.07927,449 2021. URL https://arxiv.org/abs/2103.07927.450
[31] Shayegan Omidshafiei, Christos H. Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Row-451 land, Jean-Baptiste Lespiau, Wojciech M. Czarnecki, Marc Lanctot, Julien Pérolat, and Rémi452 Munos. ↵-rank: Multi-agent evaluation by evolution. CoRR, abs/1903.01373, 2019. URL453 http://arxiv.org/abs/1903.01373.454
[32] G. Papoudakis, F. Christianos, A. Rahman, and S. Albrecht. Dealing with non-stationarity in455 multi-agent deep reinforcement learning. arXiv preprint arXiv:1906.04737, 2019.456
[33] Marc J. V. Ponsen, Steven de Jong, and Marc Lanctot. Computing approximate Nash equilibria457 and robust best-responses using sampling. CoRR, abs/1401.4591, 2014. URL http://arxiv.458 org/abs/1401.4591.459
[34] Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling others using oneself460 in multi-agent reinforcement learning. In International conference on machine learning, pages461 4257–4266. PMLR, 2018.462
[35] Tuomas Sandholm. Perspectives on multiagent learning. Artificial Intelligence, 171(7):382–463 391, 2007. ISSN 0004-3702. doi: https://doi.org/10.1016/j.artint.2007.02.004. URL https:464 //www.sciencedirect.com/science/article/pii/S0004370207000525. Foundations465 of Multi-Agent Learning.466
[36] John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust467 region policy optimization. CoRR, abs/1502.05477, 2015. URL http://arxiv.org/abs/468 1502.05477.469
[37] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal470 policy optimization algorithms. CoRR, abs/1707.06347, 2017. URL http://arxiv.org/471 abs/1707.06347.472
[38] L. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):473 1095–1100, 1953.474
[39] Max Smith, Thomas Anthony, and Michael Wellman. Iterative empirical game solving via475 single policy best response. In International Conference on Learning Representations, 2021.476 URL https://openreview.net/forum?id=R4aWTjmrEKM.477
[40] Finnegan Southey, Michael P Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse478 Billings, and Chris Rayner. Bayes’ bluff: Opponent modelling in poker. arXiv preprint479 arXiv:1207.1411, 2012.480
[41] Alex Tank, Nicholas Foti, and Emily Fox. Streaming variational inference for Bayesian481 nonparametric mixture models. In Artificial Intelligence and Statistics, pages 968–976. PMLR,482 2015.483
[42] Yee Whye Teh. Dirichlet Process, pages 280–287. Springer US, Boston, MA, 2010. ISBN484 978-0-387-30164-8. doi: 10.1007/978-0-387-30164-8_219. URL https://doi.org/10.485 1007/978-0-387-30164-8_219.486
[43] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time.487 In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages488 259–278. SIAM, 2020.489
[44] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun-490 young Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster491 level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350–354,492 2019.493
[45] Chong Wang and David Blei. Truncation-free stochastic variational inference for Bayesian494 nonparametric models. Advances in neural information processing systems, 25:422–430, 2012.495
[46] Zhe Wu, Kai Li, Enmin Zhao, Hang Xu, Meng Zhang, Haobo Fu, Bo An, and Junliang Xing.496 L2E: Learning to exploit your opponent, 2021.497
[47] Mengdi Xu, Wenhao Ding, Jiacheng Zhu, Zuxin Liu, Baiming Chen, and Ding Zhao. Task-498 agnostic online reinforcement learning with an infinite mixture of Gaussian Processes. In Hugo499 Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin,500 editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural501 Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.502
[48] Yaodong Yang, Rasul Tutunov, Phu Sakulwongtana, and Haitham Bou Ammar. ↵2-rank: Practi-503 cally scaling ↵-rank through stochastic optimisation. In Proceedings of the 19th International504 Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’20, page 1575–1583,505 Richland, SC, 2020. International Foundation for Autonomous Agents and Multiagent Systems.506 ISBN 9781450375184.507
[49] Y. Zheng, Z. Meng, J. Hao, Z. Zhang, T. Yang, and C. Fan. A deep Bayesian policy reuse508 approach against non-stationary agents. In Advances in Neural Information Processing Systems,509 2018.510
[50] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret mini-511 mization in games with incomplete information. Advances in neural information processing512 systems, 20:1729–1736, 2007.513
Checklist514
1. For all authors...515 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s516 contributions and scope? [Yes]517 (b) Did you describe the limitations of your work? [Yes] See the first paragraph of Section 3518 and the last paragraph of Section 7.519 (c) Did you discuss any potential negative societal impacts of your work? [No] We do not520 see potential negative societal impacts of our work.521 (d) Have you read the ethics review guidelines and ensured that your paper conforms to522 them? [Yes]523 2. If you are including theoretical results...524
(a) Did you state the full set of assumptions of all theoretical results? [N/A]525 (b) Did you include complete proofs of all theoretical results? [N/A]526
3. If you ran experiments...527 (a) Did you include the code, data, and instructions needed to reproduce the main ex-528 perimental results (either in the supplemental material or as a URL)? [Yes] See Ap-529 pendix A.3530
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they531 were chosen)? [Yes] See Appendix A.3532
(c) Did you report error bars (e.g., with respect to the random seed after running experi-533 ments multiple times)? [Yes]534
(d) Did you include the total amount of compute and the type of resources used (e.g., type535 of GPUs, internal cluster, or cloud provider)? [No]536
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...537 (a) If your work uses existing assets, did you cite the creators? [N/A]538 (b) Did you mention the license of the assets? [N/A]539 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]540
541
(d) Did you discuss whether and how consent was obtained from people whose data you’re542 using/curating? [N/A]543
(e) Did you discuss whether the data you are using/curating contains personally identifiable544 information or offensive content? [N/A]545
5. If you used crowdsourcing or conducted research with human subjects...546 (a) Did you include the full text of instructions given to participants and screenshots, if547 applicable? [N/A]548 (b) Did you describe any potential participant risks, with links to Institutional Review549 Board (IRB) approvals, if applicable? [N/A]550 (c) Did you include the estimated hourly wage paid to participants and the total amount551 spent on participant compensation? [N/A]552

Review summaries:
This work proposes an approach to learning against non-stationary opponents, where the non-stationarity comes from the learning dynamics in contrast to previous work which assumes a set of possible strategies over the opponents.  The opponent model is learned with Dirichlet Process and from it it's used together with a previous work (RNR) and meta learning  to produce a safe strategy.  The approach seems novel and improving previous works. I have some questions about experiments and limitations. 

The paper proposes to use the Dirichlet process for opponent modelling in games. It argues that the approach is particularly suitable for non-stationary opponents. It then proposes an algorithm to compute a counter-strategy to the model based on the restricted Nash response. Empirical evaluation on Kuhn poker shows that this approach can exploit a non-stationary learning opponent similarly to one of pre-existing methods, while maintaining relatively slow exploitability.