Learning to Safely Exploit a Non-Stationary Opponent
Authors: Zheng Tian
Hang Ren
Yaodong Yang
Yuchen Sun
Ziqi Han
Ian Davies
Jun Wang
Venue: NeurIPS 2021 Submitted (2021)
Keywords: multi-agent learning
reinforcement learning
opponent modeling

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

Learning to Safely Exploit a Non-Stationary Opponent
Anonymous Author(s)
Affiliation Address email
Abstract
In dynamic multi-player games, effective way to exploit opponent's 's weak- nesses is to build a perfectly accurate opponent model. This renders the learning problem single-agent optimization which can be solved by typical reinforcement learning. However, naive behavior cloning may not suffice to train an exploiting policy because opponents' behaviors often non-stationary due to their adapta- tions response to other agents' strategies. On the other hand, overfitting to an opponent (i.e., exploiting only specific type of opponent) makes the learning player easily exploitable by others. To address the above problems, we propose method named Exploit Policy-Space Opponent Model (EPSOM), In EPSOM, we model an opponent's 's non-stationarity as a series of transitions among different policies, and formulate such transition process through Bayesian non- non-parametric methods. To account for the trade-off between exploitation and exploitability, we train player to learn robust best response the opponent's predicted strategy by solving modified meta- meta-game in policy space. In this work, we consider a two-player zero-sum game setting and evaluate EPSOM on Kuhn poker; results suggest that our method is capable of exploiting its adaptive opponent, whilst maintaining low exploitability (i.e., achieving safe opponent exploitation). Further- more, we show that our EPSOM agent has strong performance against unknown non-stationary opponents without further training.
2
4
6
10
11
12
13
14
15
17
18
19
Introduction
20
21 In single agent reinforcement learning (SARL), an agent learns to act by iteratively interacting with an environment. In such setting, agent's learning objective and its performance evaluation are normally clear and straightforward, e.g., its long-term cumulative rewards gained from environment. However, in multi-agent reinforcement learning (MARL.), one agent's performance greatly depends on the behavior of other agents. Hence, finding a reliable learning objective and evaluation method become non-trivial [3, 9, 31, 48]. Naive solutions of the problem using SARL generalize badly [21] and optimizing the joint policy of all agents does not scale. Recent approaches combining game theoretical analysis with deep RL have seen some success in large zero-sum games [4, 44].
23
24
25
27
29
30
Game theory offers mathematical framework to model strategic interactions among players [28]. Under perfect rationality [12], a central solution concept is Nash equilibrium (NE) where no player benefits from deviating from their equilibrium strategy. In a two-player zero-sum game without
31
33 any inherent advantage for either player (e.g. as first mover), NE safe strategy to play (i.e., playing not to lose) NE guarantees tie in the worst case in expectation. However, NE is not the most profitable strategy in many cases. In complex competitive games, such as poker, is common that agents encounter opponents with bounded rationality, in the sense that they may at best play an
35
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 approximate Nash equilibrium strategy and often play dominated actions [5, 33). Therefore, playing
38 a NE can potentially forego significant rewards against sub-optimal opponents. This incentivizes
39 players to deviate from the NE and exploit their opponents" weakness (i.e., playing to win). However, the resulting strategy could render itself exploitable should it overfit to the current opponent. Playing
40
41 to win can therefore lead to exploitation by other opponent strategies. In the case of deceptive opponents such exploitation is known as the "get taught and exploited" problem [35].
42
43
To better balance the trade-off' between playing to win against the current opponents (exploitation) and not losing to unknown opponents (exploitability), Johanson et al. [19] proposed a solution concept, named Restricted Nash Response (RNR). RNR and its variants [18, 19, 33] assume stationary opponents. i.e., the strategies they learn to exploit are unknown but fixed. However, in many real- world applications, opponents may adapt and change their strategies on an ongoing basis. For example,
44
45
46
47
48 in Rock- PPape--Scissone when player learns to best respond by playing Rock to an opponent's 's strategy
49 which always plays Scissors, the opponent may then learn to best respond to your best response by
50 playing Paper. Furthermore, prior RNR approaches only provide one-off solutions in the sense that whenever we need to re-adjust the trade-off between exploitation and exploitability the opponent uses a new fixed policy, we need to re-solve the updated game from scratch.
51
52
59 In this work, we focus on problems with non-stationary opponents. An opponent's 's learning process can be generally modeled as transitions among a mixture of unknown number of policies. This motivates the usage of Dirichlet process mixture model. As we can only collect trajectories produced produccd by the adaptive opponents online, we propose to learn our model in streaming fashion. Given the predicted opponent policy from our model, we provide general framework for training an agent to safely exploit the non-stationary opponent where safe exploitation means exploiting the current opponent with a low probability of being exploited by other opponents in future. We empirically demonstrate the ability of our approach to safely exploit a non-stationary opponent in Kuhn Poker, a simplified Poker game. Furthermore, once trained, our model can produce strong counter strategies
54
55
56
57
58
59
60
61
62 to unseen opponents without any further training in new tournaments.
2 Related Works
63
64 A fundamental ability of an effective AI agent is the capacity to interact with other intelligent
65 agents. Therefore, the capability of reasoning about other agents' goals [34], private information [27],
66
behavior [13] and other characteristics is crucial. The issue of non-stationarity in multi-agent systems
67
resulting from coexisting agents is well-known and well documented [14, 32]. Classical solutions to resolve the issue of non-stationarity include centralized training [24], self-play elf-play [44], meta- meta-learning [1] and opponent modeling [2]. When specifically applied to the issue of non-stationarity, most previous works focusing on opponent modeling which switches between different opponent models when change in opponent(s) is detected. A switch of model may be triggered by a drop in opponent model prediction accuracy [10] when performance in terms of reward received for fixed policy drops [15]. Deep BPR+ [49] combines a measure of opponent model accuracy and reward tracking to decide when to learn new policy. Significantly, most of these works limit the opponents' non-stationarity
68
69
70
71
73
74
75 to periodically changing their policies within a finite pre-defined set of stationary policies.
76 In this work, we consider ota-staaionaritt during the training stage arising from the opponents' concurrent learning dynamics, rather than drawing stationary opponents from a pre-defined set. The entire lifetime of an opponent can generally be modeled as a mixture of an unknown (possibly infinite) number of policies. This motivates the usage of Dirichlet Process (DP) mixture model [6, 42] which can infer the number of mixture components from data and provide incremental model capacity on demand. Various approximate inference methods are reported for DP mixture models, such as Markov chain Monte Carlo [17] and variational inference [6. 16, 45]. However, these inference methods either do not adapt to an online setting or truncate the number of clusters to a finite value. Recently proposed streaming inference algorithms [23, 41] enable the DP mixture model to solve online non-stationary problems in a truly non non-parametric way. Applications have been reported in free- continual learning [22] and model-based reinforcement learning [47]. In this paper, adopt this approach to model and simulate a non-stationary opponent for MARL.
77
78
79
80
81
83
84
85
87
88 It is well known that finding a NE is PPAD-hard even in two-player games [8]. An exception is two- player zero-sum games where the NE can be tractably solved by a linear program (LP) in polynomial time [43]. However, in games with extremely large action spaces, approximate NE solutions, such
89
2

---

91 as fictitious play (FP) [7] and counterfactual regret minimisation (CFR) [50], have to be used. An important design principle that underpins NE approximation is the iterative best-response dynamics. Two representative methods are Double Oracle (DO) [26] and Policy Space Response Oracle (PSRO) 93
92
94 [21]. In the dynamics of DO [26], players are initialized with restricted strategy sets; then at each iteration, a NE will be computed over the current restricted sets. These sets will be expanded by adding the best-response strategy to the NE computed over the full strategy sets. The iterative process continues until the best response is in the restricted strategy pool. PSRO approximates DO by interleaving empirical game-theoretic analysis (EGTA) with deep RL. In contrast with DO, the game with restricted strategy sets has to be estimated through simulation. Furthermore, the exact analytical best-response oracle is replaced in PSRO by a deep RL oracle which calculates an approximate best response. PSRO is general self-play framework for MARL and many approaches built upon it have been proposed to improve its performance [25, 29, 30, 39). Our approach, EPSOM, is not limited to the self-play setting. In addition, although we favor solutions with low exploitability (i.e. solutions close to NE) as PSRO does, our ultimate goal is to find a robust best response to a non-stationary opponent rather than solving the game for (approximate) NE.
95
96
96
100
102
103
104
105
Preliminaries
106
107
We consider the decentralized training and decentralized execution (DTDE) setting in zero-sum games where we have access interaction trajectories т between our agent and the opponent' Whilst our approach can be extended to games with multiple opponents, in this work we focus on 2-player zero-sum games. Before introducing our algorithm, we present some necessary preliminary concepts and notation in the remainder of this section.
108
109
110
111
112
3.1
Meta Normal-Fore Game
113
We consider opponent modeling in policy space and learn to respond to the predicted distribution 114 of the opponents' policies. We formulate this problem as solving a two-player normal-form game (NFG) between our agent and its opponents as whole with notation adapted to our presentation. We denote a 2-player NFG by a tuple (II, U,)) where IT' player i's set of policies and N where as its opponent. We use IT ITE IT' to denote the set of joint policies (strategy profiles). ((T) IT + d² is a payoff table of utilities for each joint policy π played by all players. u' (T) denotes the utility value for player i and joint policy A player can choose policy x' from 112 or sample from mixture tmneta-stratege over them a² E A (IT') where A is a probability simplex. In the terminology of game theory, of is a mixed strategy and each policy zz is a pure strategy.
115
116
117
N = {1,2]. For ease of notation, we take player as the training agent and player 2
118
119
121
122
Each player in the game is assumed to maximize their utility. The most well-known steady-state concept of a game is the Nash equilibrium (NE). NE is strategy profile π such that no player has an incentive to deviate from its current strategy given the strategies of the other players. Namely, each player's s strategy is best response to others' BR( i (1) = arg max u'(T', n i) Vi E N. We call a set of policies e-best responses to a joint opponents' policy π when there exists an e O, such that BR, ( (T= = {T' u' ('(',, π ") 2 u' (BRR "). 1)) - c). An e-Nash equilibrium is a strategy profile that satisfies: u² (x) 2 m u'(
124
126
128
Vi N.
130
3.2
Exploitability and Exploitation
To evaluate our learned policy n/, two metrics. An agent's policy's n! exploitation of an opponent's 's policy n² is the extra gain obtained by the agent compared to its NE value vi:
132
w( 1 =²) = uz (= (²) 2
133 This measures how much the policy x² exploits the weakness of the opponent's policy 2 However, 134 in general, there is no guarantee that the learned policy n' has no weakness. Therefore, we also 135 define the exploitability of a policy n' which measures the loss incurred when the agent faces the
A detailed definition of the trajectory a stochastic game [38] can be found in Appendix A.I.
3

---

best opponent policy x² = (T'())) compared to the agent's Nash equilibrium value u':
138
<(*)) = v² u² (B(()))))
maxmin w² (T x²) min u² ( =²))
(1)
7/ x²
137
From Equation 1 we can see that the exploitability of a policy is non-negative and represents the distance of policy æ² an equilibrium.
138
139
3.3
Restricted Nash Response (RNR)
Johanson et al. [19] consider a modified zero-sum game where an opponent has a restricted strategy
space IT? P. such that plays fixed policy Tix with probability p and plays any possible policy
141
from the original strategy space II? with probability 1 - p. Given (p. Tax), they define a restricted Nash equilibrium strategy profile (s ( ", such that where: p,,, (x**)= arg maxx*ElI,... ,²² It is shown that x is the best response to
142
(R(( and n BR. (x'*),
Tix among strategies which have equal or lower exploitabilities than π n== i.e.: n-* =
where T
Therefore, x1* called p-restricted Nash response (RNR) to Tiix- An RNR can be computed by solving the modified game, we present linear programming solver implementation
146
147
148
for NFGs in Appendix A.2.
Dirichlet Process Mixture Opponent Modeling
149
150
This section presents our non- non-parametric Bayesian method for modeling a non-stationary opponent. We consider an opponent's 's learning process as consecutive transitions from one policy to another such that one opponent can theoretically adopt infinitely many policies during its life-time. Therefore, we propose to use Dirichlet process (DP) mixture to model the learning process as it has the ability to model an infinite number of clusters (policies in this case) while inferring the current number of policies from the data collected thus far. As agent interacts with the opponent online, we learn model with a sequential maximum- a-postrrroo approach.
151
152
154
156
157 We model an opponent policy as parameterized function F and denote the parameter space as 4 To avoid cluttered notation in this section, we use & to represent the modeled opponent's policy.
158
159
DP (a+H) is stochastic process with a concentration parameter and base distribution H over Ø.
180
A random draw G ~ (P(aH) is itself a distribution over Φ satisfying:
Dirichlet
aH.
for every finite measurable partition .i, of 4. The full graphical model for opponent modeling shown in Figure la. illustrates a generative process where at step m, the opponent first samples a policy 2m ~ G and then rolls-out this policy to collect a trajectory Tm-
Ap
182
163
To facilitate Bayesian inference, two representations of DP are considered. The stick-breaking representation Figure 1b reveals the discrete nature of G. G ~ DD((aH) can be constructed random variable sampled
165
as G Σee Br.d.. where 3 GEM(a) is an rnfinite-dimensione (GEM) distribution and {Øv]-= are i.i.d, sampled policies from H. At step m. the opponent samples policy index 2m Categorical(3) and rolls-out the policy é Inference with the stick-breaking representation is required in order to handle the infinite dimensional B. Therefore, the truncation method [6] is commonly used to limit the model capacity to mixture and infer the actual number of policies by collapsing redundant ones. This requires tracking all K policies simultaneously and does not adapt well to online settings.
166
187
from the Seatiths-Engen-MMCloseeee
169
171
173
The Chinese restaurant process (CRP) representation Figure Ie can be obtained by integrating out B. This introduces temporal dependencies between the policies, which can be expressed by the conditional distribution:
174
175
k = Km +1
+
p( (22++1 = k(z1mm) =
(2)
[klm
1 1 k < Km
a

---

178
where 1m/m = = I(2; =
is the total number of trajectories from the k-th policy and Km is the number of realized policies up until step m. Inference with the CRP representation does not need to handle the infinite dimensional B. Furthermore, at step m, we only need to track at most m policies (Kn I m) while all policies beyond Km are independent from the collected trajectories Tim- and thus can be discarded from the model. In addition, the temporal dependencies between policies introduced by CRP can be used to develop an online learning algorithm.
177
179
180
181
182
Given sampled trajectories Tim, the target of our opponent model is to assign each trajectory to a policy and update existing policies with assigned trajectories. This can be achieved by seeking maximum-at posteriori (MAP) estimations of 21:m and K.. To deal with streaming trajectories, the MAP algorithm should operate in an online fashion. Therefore, given the CRP representation, we decompose the posterior into the product of the posterior from the last step, the current priors and the likeli- hood, which leads to recursive form:
183
H
184
185
186
sM
187
Z
188
189
191
(a) DP
(b) Stick Breaking
(c) CRP
193
Figure 1: Dirichlet process mixture model
plzimm KI.K.. (Tem) x
K 8m-14
II
p(Or) ) p(
m II ==2
x 1 2I:Km, 1 (p(()))(())) )p(mml 31:m 1)p(mm $zm);
where p()b)) = H is the base distribution of the DP. 195
196
The opponent model either assigns the current trajectory Tm to previous policy Φi or creates
197
new policy @ to model Tm. The choice made according to the MAP trajectory assignment
198
2m arg max... p(zm: 1 [1:m):
p(zm= k. 2/:m- (mmm x { SSn ap((p))) (Tm (m))) dø,,, k == Km-1 + (((mm = -lz )p( Tm 10 = 10mm-P((mlee)
otherwise
(4)
where | | Eee I(2 = k). Here, the hard assignment 2,, for Tm is based on previous assignments zi:m-1 and policies Φh- which is equivalent to applying assumed density filtering (ADF) [41] to approximate the true posterior in Eq. (3) with a Delta distribution 5(=ī.m) The hard assignment prevents creating a new policy each step if Tm is assigned an existing policy, which
199
201
203
significantly reduces the memory usage. Furthermore, the MAP estimations for all existing policies,
204
except &..,, remain unchanged, which dramatically accelerates the algorithm. We then optimize the
205
policy Φz by maximizing the likelihood of all trajectories assigned to it:
arg log (()...) II p(T|)
(5)
208
Where finding the global optimum is not tractable in conjugaee cases, we take gradient steps to update d
207
as
m- + XV t.
logp(0. ..:))
II p(T.))))))
208
The entire algorithm fits into the general expectation-maximizaii maximization (EM) framework. See Appendix A.4 for detailed derivation.
210
The original CRP in Eq. (2) encapsulates prior that the distribution of the next policy mimics the empirical policy distribution from the history. This prior is not consistent with our knowledge of the policy evolution process since a new opponent policy is commonly updated from the previous one. Therefore, we adopt sticky variant in Eq. (6) to incorporate the belief that the opponent tends to
212
5

---

214
persist in the latest policy [11, 47].
k= Km- +
m 1+a+k*
p(zm ff22mm-1)
(6)
|k kō(Km- m
1 k
215 where &. 2 0 is a 'stickiness' parameter and ê is the Kronecker delta function.
216
Following Eq. (4), the probability of creating a new policy for is given by:
/
p(z =
cp((d))((Tml)) don.
tb
217
where k- = Km-1 1. We use a Monte Carlo method to estimate Eq. (7) by sampling new policies from p({))) However, sampling new policies from data fata-independent prior p ( is likely to yield low trajectory likelihood p( pm ( which prevents the new policy creation. Therefore, we update the sampled policies increase the likelihood p(Tm (xb) by taking few gradient steps before estimating the integration in Eq. (7).
219
220
221
222
According to Eq. (6), the CRP prior encourages the opponent model to create redundant policies at the early stage when the number of trajectories n is small and a dominates. Redundant policies could hurt the algorithm's 's performance
223
incurs extra cost in terms of computation and memory. Trajectories from the same ground truth policy could be assigned to different Φ and these assignments never revisited. Therefore, error correction mechanism has to be introduced. Here, adopt symmetric distance metric between two policies and develop a policy merge procedure based on the metric.
225
227
Given a set of states S, we define d(Ok, Φ3) En--Uniform(S) [JS db (+s))) (155),111111)) (-1s)) where
228
(--I-)) is the Sensen-Shannon divergence and (-Is) is the action distribution given state under the policy Φ2. When the distance between two policies is below a pre-defined threshold 17, the merge procedure simply re-assigns all trajectories of Φx to Φj-
230
231
232
With the opponent model developed this section, at step m, we can construct an opponent policy set K., and distribution 6² over Ii2 The distribution (² = Φx) x |k|m + =8(Kmm) k)
233
If
{ } k=1 essentially the empirical distribution of zi.m altered by the stickiness factor
Exploit Policy- -Sacce Opponent Model
235
236 In this section, we present how to learn a safe best response to this meta strategy, given a predicted distribution 5 over opponent's policies. The advantages of our approach of focusing on policy space are two-fold: first, we do not need to assume the access to the opponent's learning characteristics such as its training algorithm, its neural network's architecture or update frequency; we only require past trajectories. Additionally, the distribution of the types of opponent policy 8² gives us an approximate stable overview of the current opponent's playing behavior compared to the opponent's current policy whose updates greatly depend the opponent's learning characteristics and randomness from playing (e.g. exploration behavior) and training (e.g. stochastic gradient descent). Therefore, learning response to this meta-strategy 8² will rely on less prior knowledge about the opponent's 's learning characteristics and is more robust to noise.
239
240
241
243
245
246
However, there is no guarantee that our learned meta strategy o has no (or at least low) exploitability. has been shown that overfitting to an opponent strategy 82 often renders the resulting learned strategy brittle [19, 21, 46). Such a brittle strategy performs badly when playing against different opponent strategies σ²' Therefore, a more desirable goal is to learn safe best response to an opponent meta-strategy a². RNR solutions consider cases where the game to solve is fixed and
247
249
250
251
known and the opponent's policy stationary. However, when we consider non-stationary opponent exploitation on policy space, the size of the meta-game to solve increases with the number of interactions between the training agent and the adaptive opponent. Furthermore, each player free to leam and update its policy at any time point during the process.
253
"oo simplify notation, we will ignore the subscript & henceforth.

---

Algorithm 1: Exploit Policy-Space Opponent Model (EPSOM)
input pappee-parameter p, H, E,, an adaptive opponent -i
output: :Policy Ti.... and meta-policy o²
Initialize learning agent i's policy Tó
Initialize a memory buffer B Initialize opponent meta-policy (-) =1 for epoch in (1. do
for episode h E (1,2..... H do
Play an episode against the opponent with strategy RRNR Collect the trajectory Te,h and save them into end
82, IT2 opponent opponentt_moelinng (B)
p [m E, (j)
Compute missing entries U from iî = II2 112 by simulations
RNN RLNR_solver(( .p.aa p.0²)
for episode E (1,2,... [1] do
Sample R² from o RNN
Train oracle T² over P (T² 22 end
-1=- IT (m²}
Compute missing entries in / from n II' x 2 by simulations
hNNR RNR__ooRooo solver(U .p,02)
end
To address the above issues, we combine DO with RNR to solve meta-game built from EGTA where the opponent's 's policies are predicted by the opponent model from Section 4. Pseudo-code explaining our approach is presented in Algorithm 1. We maintain a utility table / wherein rows represent learned policies for the training agent and columns represent a modeled policy of the opponent respectively. An epoch is defined as a fixed amount of episodes of games where we play against the opponent holding our strategy I fixed. At each epoch, we run our opponent model to predict the
256
257
258
260
current distribution 6² the opponent's policies. If new policy is detected, we will add it into fT. Given 82, we run p-RNR solver to obtain the opponent's 's RNR meta-strategies o ORNA R which is restricted Nash solution to the current meta-game assuming that the opponent playing according to
261
263
62 with probability at least Then we train an (approximate) best-response policy to of Ryy and add
265
the new policy into II. We re-run a p-RNR solver to obtain our RNR meta- meta-strategies o UNN which we use to mix the policies in population 11 for the next epoch's 's playing policy.
When new type j of modeled policy 2 added by our opponent model, we initialize a p- p-value pd Pinit to this type. Its p-value is incremented proportionally to the probability that the opponent each epoch, we calculate the average p-value p= पान Σ, p² p²0²( o²()) (j) for solving current RNR strategies. In the extreme case where
267
268
269
plays this policy in the following epochs, o²(j), and clipped
p- 0, RRNR is the same as the Nash strategy in the current meta game. At another extreme where 272 p- 1, RNNR = σ² and a PRNn = BR))²). Therefore, when we have low confidence in ō² (p is low), we learn an approximate best response opponent's current Nash mixture which will enlarge
274 our current empirical gamescape [3] and thus help to find strategics with lower exploitability. At the same time, the training agent becomes risk-adverse and the next epoch strategy a RRNR becomes strategy closer to the Nash strategy of the current meta game.
276
When is high, it means that our opponent model has high confidence that the opponent is playing /² and an approximate best counter strategy to 8 will be added into our policy population. The training agent becomes profit-driven and a RNNRR becomes a strategy closer to (RR in the next epoch. Therefore, mixing the playing policy by &RNR flexibly switches the agent between risk-adverse and
277
278
279
280
profit-driven depending on the confidence of the opponent model. In contrast with previous RNR
282
solution, EPSOM can always recover strategy with approximately the lowest exploitability has
seen far maintain population of policies.
7

---

1.50
OPSON
0.5
1.25
0.4
0.3
Exploitabiltyy
1.00
Exploitation
0.2
0.75
0.1
0.50
0.0
0.25
-0.
0.00
-0.2
0
20
40
60
80
100
20
40
60
80
100
# Opponent Updates
# Opponent Updates
Figure Exploitability and exploitation different algorithms against non-stationary opponent implemented by PPO in Kuhn Poker.
Experiments
285
In this section, we empirically investigate whether the proposed method can (1) exploit an unknown non non-stationary opponent while still maintaining strategy with low exploitability, (2) improve its
286
287
performance by continued training against different opponents and (3) exploit previously unseen
286
opponents without further training. We verify EPSOM's performance Kuhn Poker [20], simplified
version of poker which importantly retains strategic elements useful for game-theoretic analysis. We
290
use an agent learning to play using the PPO [37] algorithm as our opponent, which suffices to provide
non-stationary setting. More details about the game and our experiment implementation can be found in Appendix A.3.
292
200
Kuhn Poker
150
PPO
TRPO
EPSOM [0.109]
0.023
(0.189)
0.09
(0.180)
100
CEPSOM [0.080]
0.113
(0.142)
0.140
(0.117)
BC [1.333]
-0.559
(0.232)
-0.223
(0.134)
50
PSRO [0.000]
0.052
(0.072)
0.032
(0.058)
293
PPO [0.477]
-0.407
(0.133)
-0.372
(0.119)
Table 1:
Zero-shot learning exploitation results. Trained agents (row players) play against adaptive opponents (column players) without further training. Adaptive opponents allowed to update 100 times and trained agent's average exploitation are taken over these 100 updates and 5 random seeds. Values in square brackets are each trained agent's 's exploitability and values in parentheses are stds taken over 5 random seeds.
Figure 3: Opponent's learning process mod- eled by trained CEPSOM: (left) CEPSOM adjusts playing strategy online; (right) CEP- SOM plays approximate Nash strategy. Each point is 2-D embedding of modeled policy to which trajectory produced by the opponent assigned by our opponent model. Color bar indicates time sequence.
We select 3 representative algorithms baselines. PSRO is popular algorithm which guarantees the convergence to an approximate NE. PSRO is self-play algorithm, its trained before playing against any adaptive opponents. Behavior cloning (BC) models the opponent's 's policy by taking maximum likelihood estimation of history trajectories stored in a sliding-windor buffer and learns (approximate) best-response policy to it. PPO represents canonical choice among many SARL algorithms. our work, as agents and their opponents update asynchronously, we always evaluate each algorithm's performance right after the opponent's update for more robust evaluation. The following results reported with mean and standard deviation (std) are all obtained by repeating the corresponding experiment over 5 random seeds.
295
297
299
301
305
As shown Figure 2, EPSOM can achieve a safe strategy with relatively low exploitability while still being able exploit its opponent. Though PSRO plays strategy with the lowest exploitability (sx 0)
305
also has very low exploitation against opponent. In contrast, BC can exploit its opponent to
similar extent EPSOM but it comes with the cost of high exploitability. The PPO algorithm has

---

307
large variance and performs badly on average in this non-stationary setting, We also test a continual learning version of EPSOM which we name CEPSOM. is implemented by training an EPSOM agent against 5 different opponents without re-initialization thereby building up a richer set of modeled opponent policies and more robust best-response policy population. Its average performance over
308
309
310
these opponents is also reported in Figure 2. In our experiments, we use an analytical method to calculate a best response to a given policy. We obtain similar results for approximate best response learned by RL which are reported in Appendix A.5.
312
314
Next, we test these agent's 's performance against two adaptive opponents implemented by PPO and TRPO [36] without further training and results are presented in Table 1. Relying on an opponent model to predict the current opponent's 's policy type and flexibly adjusting its playing strategy accordingly,
315
316
317
CEPSOM achieves the highest average exploitation against adaptive opponents. EPSOM also obtains
318
positive average exploitation but with a much lower value, since EPSOM has only ever been trained with one opponent. PSRO plays safe strategy and performs slightly better than EPSOM in terms of opponent exploitation. BC and PPO perform badly as they overfit to one opponent, and thus they are exploited by other adaptive opponents. Note that, in this zero-shot learning tournament, although we do not train EPSOM and CEPSOM, they still need to predict the opponent's policy and solve the meta-game game for a RNR solution given the prediction.
319
320
322
324
Facing an adaptive opponent, trained CEPSOM's opponent model can assign trajectories collected during learning into modeled policies it has built. Therefore, we can visualize an opponent's learning process by presenting a sequence of those modeled policies on a 2-dimensional plot. In Figure 3, we present two opponent's visualized learning process when it faces (a) a trained CEPSOM agent which adjusts its playing strategy online based on its opponent model prediction, and (b) a trained
325
326
327
328
329
CEPSOM agent which always plays an approximate Nash equilibrium strategy. We can see that in a
330
non stationayy environment (left), the opponent's learning exhibits a cyclic pattern. In contrast, the opponent's 's learning is much more transitive (i.e., monotonically moving in one direction in the 2D space) in a stationary environment (right).
332
333
7
Conclusion
334
In this work, we propose framework for training an agent to safely exploit its opponent. Compared to RNR and its variants, our work focuses on non-stationary opponents. We consider the opponent's learning as a series of policy transitions and model such a process by Dirichlet Process. Safe exploitation means that an agent can exploit an opponent's 's weakness to maximize our utility while
335
336
337
simultaneously maintaining strategy which has low exploitability. This property is desirable as naively overfitting to one type of opponent could easily lead to exploitation by other opponents. We empirically verify our algorithm's 's performance on Kuhn Poker, simplified version of Poker.
339
341
Opponent modeling based MARL algorithms typically require extra computation for learning a good opponent model. This cost often scales dramatically with the number of opponents, action space dimensionality and the complexity of the problem. It can be a heavy burden on an agent it learns an opponent model from scratch online. Therefore, a more realistic way for utilizing the power of an opponent model offline training and online prediction. We build CEPSOM based on this idea where we train one EPSOM agent across different opponents and aggregate knowledge by maintaining a never-reinitialized opponent model and policy population. Our experiment results show that CEPSOM can achieve high exploitation against new adaptive opponent without further training, outperforming other representative basclines from SARL and MARL. In complex competitive games, strong player can often encounter sub-optimal opponents and playing Nash strategy can potentially forego signíficant profit. EPSOM, alongside many prior works, shows the potential of an opponent modeling based approach for solving this problem, and our preliminary results from CEPSOM demonstrate the possibility of a trained agent beating an as yet unseen adaptive opponent.
342
343
344
345
347
349
351
353
354
EPSOM is limited by its computation and memory complexity. Naively applying EPSOM to more complex problems requires a great amount of resources. To alleviate this problem, we introduce
355
policy merge to remove redundant policies in our opponent model. This approach could be improved by applying game theoretic analysis to our policy populations (agent's self policies and modeled opponent policies). We leave the study of improving EPSOM's scalability to future work.
357

---

References
359
360
[1] M. Al-Shedivat, T. Bansal, Y. Burda, I. Sutskever, I. Mordatch, and P. Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. arXiv preprint 171.0:1710.03641, 2017.
362
[2] Stefano V. Albrecht and Peter Stone. Autonomous agents modelling other agents: A compre- hensive survey and open problems. Artificial Intelligence, 258:66-95, 2018. ISSN 0004-3702. doi: https://doi.org/1100/ http:///oo..o//1..1.0100 2010: URL https:/ //tp:://wwwwwwe/ scienceirreccct................. com/
364
366
367
[3] David Balduzzi, Marta Gamelo,, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. In Interna- tional Conference on Machine Learning, pages 434 443. PMLR, 2019.
368
369
370
[4] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, Rafal Józefowicz. Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto. Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang. Filip Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning. CoRR, abs/1912.06680, 2019. URL http://arx: org/ 1912 06680.
371
372
373
374
375
378
377
[5] Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, Terence Schauenberg, and Duane Szafron. Approximating game-theoretic optimal strategies for full- scale poker. pages 661-668, 01 2003.
378
379
[6] David M Blei, Michael I Jordan, et al. Variational inference for Dirichlet Process mixtures. Bayesian analysis. 1 1(1):121-143) 2006.
381
382
77] GW Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation (TC Koopmans, Ed.), pages 374-376, 1951.
383
384
[8] Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (F)CS'06), pages 261-272. IEEE, 2006.
385
386
[9] Wojciech Marian Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafici. David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. arXiv preprint a004 09468, 2020.
388
390
[10] R. Everett and Roberts.
Learning against non-stationary agents with opponent modelling and deep reinforcement learning. In 2018 AAAI Spring Symposium Series, 2018.
392
[1]] Emily Fox, Erik B Sudderth, Michael Jordan, and Alan S Willsky, An HDP-HMM for systems with state persistence. In Proceedings of the 25th international conference on Machine learning, pages 31 312-319, 2008
393
394
395
[12] Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, Cambridge, MA, 1991.
396
[13] H. He, J. Boyd-Graber, K. Kwok, and H. Daumé III. Opponent modeling in deep reinforcement learning. In ICML. '16 volume 48, pages 1804-1813, 2016.
397
398
[14] P. Hernandez- M. Kaisers, T Baarslag, and E.M. de Cote. A survey of learning in multi-
399
agent environments: Dealing with non- statiionatn arXiv preprint arXiv:1707.09188 2017.
400
[15] Pablo Hernandez- and Michael Kaisers. Learning against sequential opponents in repeated stochastic games. In The 3rd Multi fuuti-ddsscilinary Conference on Reinforcement Learning and Decision Making, 2017.
402
[16] Michael C Hughes and Erik B Sudderth. Memoized online variational inference for dirichlet Process mixture models. Technical report, BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE, 2014.
404
10

---

408
[17]
Hemant Ishwaran and Lancelot F James. Gibbs sampling methods for stick-breaking priors. Journal of the American Statistical Association, 161453) 2001.
407
408
[18]
Michael Johanson and Michael Bowling. Data biased robust counter strategies. In David van Dyk and Max Welling, editors, Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, pages 264 271. PMLR, 2009. URL httpp://proceedings mlr. press/v5/
410
moass/vv/joaansooS5.. johanson09a. html.
412
[19]
Michael Johanson, Martin Zinkevich, and Michael Bowling. Computing ro- bust counter- strateess In J. Platt, D. Koller, Y. Singer, and S. Roweis, edi- tors, Advances in Neural Information Processing Systems, volume 20. Curran As- sociates, Inc., 2008. URL https: https://pren peroceedings.neuripe co/ wwtppp/pe//////////// 6e7b33rlea2adce00eaa444 (f Papeer........ haper..df..
413
414
415
416
417
[20] Harold W Kuhn. A simplified two-person poker. Contributions to the Theory of Games, 1: 97-103, 1950.
419
[21]
Marc Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. CoRR, abs/1711.00832 2017. URL http: //appi//////i.///aaaeeaeeae http://aaxvv..g/aaaa//// wwwg/aa//////////oo/ 00832.
420
421
422
[22] Soochan Lee, Junsoo Ha, Dongsu Zhang, and Gunhee Kim. A neural Dirichlet Process mixture model for task-free continual learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Abuba, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
424
[23] Dahua Lin. Online learning of nonparametric mixture models via sequential variational approx- imation. Advances in Neural Information Processing Systems, 26:395-403, 2013.
427
428
[24] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch. Multi-agent actor-critic for mixed cooperative-compettiee environments. In Advances in Neural Information Processing Systems, pages 6379-6390, 2017.
429
430
[25] Stephen McAleer, John B. Lanier, Roy Fox, and Pierre Baldi. Pipeline PSRO: A scalable approach for finding approximate Nash equilibria in large games. CoRR, abs/2006.08555, 2020. URL https::///axiii http::/::///aa....oo////oo///
432
ab0/ 08555.
434
[26] H Brendan McMahan, Geoffrey Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 536-543, 2003.
435
436
437
[27] R. Mcaling and J. L. Shapiro. Opponent modeling by expectation- cnxeratioonmmmxiiizatiii and sequence prediction in simplified poker. IEEE Transactions Computational Intelligence and Al in Games, 91):11-24, 2017. doi: 20.1000TCIAIG2220552299906
439
440
[28] Oskar Morgenstern and John Von Neumann. Theory of games and economic behavior. Princeton university press, 1953.
442
[29] Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Pérolat, Siqi Liu, Daniel Hennes, Luke Marris, Mare Lanctot, Edward Hughes, Zhe Wang, Guy Lever, Nicolas Heess, Thore Graepel, and Rémi Munos. A generalized training approach for multiagent learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, net/ cest/forum?cc
444
446
April 26-30, 2020. OpenReview.net, 2020. URL ptttss//oppnreeee Bk15kxrKDr.
[30] Nicolas Perez Nieves, Yaodong Yang, Oliver Slumbers, David Henry Mguni, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. CoRR, abs/2103.07927,, 2021. URL https: //ta////a.iii/aa org/ /tt///bb///11/////
449
450
451
[31] Shayegan Omidshafiei, Christos H. Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Row- land, Jean-Baptiste Lespiau, Wojciech M. Czarnecki, Mare Lanctot, Julien Pérolat, and Rémi Munos. a-rank: Multi-agent evaluation by evolution. CoRR, abs/1903.0137,, 2019. URL.
453
http://arxe org wowg//aa///aee /9t.///////..//.. 00t.//9111300.1....1

---

455
[32] G. Papoudakis, F. Christianos, A. Rahman, and S. Albrecht. Dealing with non-stationarity in multi-agent deep reinforcement learning. arXiv preprint arXiv:/906.04770 2019.
456
457
[33] Mare J. V. Ponsen, Steven de Jong, and Mare Lanctot. Computing approximate Nash equilibria and robust best-responses using sampling. CoRR, abs/1401.4591, 2014. URL http: httt:///rxiv. org/abs/ 1401. 4591.
459
460
[34] Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling others using oneself multi-agent reinforcement learning. In International conference on machine learning, pages 4257-4266. PMLR, 2018.
461
[35]
Tuomas Sandholm. Perspectives multiagent learning. Intellggene, 171(7):382- 3,1, 2007. ISSN 0004-3702. doi: / //www/a. www.eeceeeeeett............... com/ htt.://aaaaatttt////////////1/a0 Foundations of Multi-Agent Learning.
484
020000000.........00000000000000 URL https:
465
486
[36] John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region policy optimization. CoRR, abs/1502.05577, 2015. URL http://arxiv, org/abs/ 1502.05477.
468
470
[37] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. CoRR, abs/1707.00347, 2017. URL http://arxiv org/ abs11707066347.
471
472
473
[38] L. Shapley, Stochastic games. Proceedings of the national academy of sciences, 39(10):
1095-1100, 1953.
475
[39] Max Smith, Thomas Anthony, and Michael Wellman. Iterative empirical game solving via single policy best response. In International Conference on Learning Representations, 2021. URL https::/ net/
478
477
478
[40] Finnegan Southey, Michael P Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. arXiv preprint 1XX7:1207.1410 2012.
480
481
[41] Alex Tank, Nicholas Foti, and Emily Fox. Streaming variational inference for Bayesian nonparametric mixture models. In Artificial Intelligence and Statistics, pages 968-976. PMLR, 2015.
482
483
[42]
Yee whye Teh. Dirichlet Process, pages 280-287. Springer US, Boston, MA, 2010. ISBN 978-0-387-30164-8 doi: 10.
485
219. URL https://doi /ttp://///oooo////././///
486
0- 1111//978---87--0000
487
[43]
Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 259-278. SIAM, 2020.
488
489
490
[44] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)
492
2019.
494
[45] Chong Wang and David Blei. Truncation free stochastic variational inference for Bayesian nonparametric models. Advances in neural information processing systems, 25:422-430, 2012.
[46] Zhe Wu, Kai Li, Enmin Zhao, Hang Xu, Meng Zhang, Haobo Fu, Bo An, and Junliang Xing. I 12F: Learning to exploit your opponent, 2021.
487
498
[47] Mengdi Xu, Wenhao Ding, Jiacheng Zhu, Zuxin Liu, Baiming Chen, and Ding Zhao. Task- agnostic online reinforcement learning with an infinite mixture of Gaussian Processes. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
439
501
12

---

503
[48] Yaodong Yang, Rasul Tutunov, Phu Sakulwongtana, and Haitham Bou Ammar. a Practi- cally scaling a-rank through stochastic optimisation. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '20, page 1575-1583, Richland, SC, 2020. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450375184
504
505
506
507
508
[49] Y. Zheng, Z. Meng, J. Hao. Z. Zhang, T. Yang, and C. Fan. A deep Bayesian policy reuse approach against non-stationary agents. In Advances in Neural Information Processing Systems, 2018.
509
510
[50] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret mini- mization in games with incomplete information. Advances in neural information processing systems, 20: 11117779766... 2007.
512
Checklist
514
515
1. For all authors...
516
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
517
518
(b) Did you describe the limitations of your work? [Yes] See the first paragraph of Section and the last paragraph of Section 7.
519
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not see potential negative societal impacts of our work.
521
522
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results... 524
525
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
526
(b) Did you include complete proofs of all theoretical results? [N/A]
527
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See Ap- pendix A.3
529
530
531
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A.3
532
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
534
535
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No]
536
537
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
538
(a) If your work uses existing assets, did you cite the creators? [N/A]
539
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
541
542
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
545
546
5. If you used crowdsoureing or conducted research with human subjects...
547
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
548
549
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
550
551
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "yxFkhuxyzNE", "reviewer": "Reviewer_8Pgk", "summary": "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.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The problem of opponent modeling in games has been extensively studied before. The idea to use the Dirichlet process (DP) to solve it may be new and is well motivated in the paper.\n\nClarity: The paper is reasonably clear and understandable. However, it would be further improved by use of examples to demonstrate the notions and algorithms on a specific tiny game.\n\nQuality: The notation and basic claims in the paper seem sound. My main concern is with the positioning with respect to the related work and the quality of the empirical evaluation.\n\n(1) Related work. Opponent modelling in games is a classical problem with many solutions. This paper reviews a part of this literature, but it does not provide theoretical or empirical arguments on superiority of the proposed approach to the existing ones. A natural candidate for the context of the paper would be, for example, the implicit agent modelling framework [A], but at least a compelling argument of superiority to [10,15,49] either theoretically or empirically should be provided.\n\n(2) Computational complexity. There is no discussion of the computational complexity of the proposed method. It looks much more expensive than some of the alternatives mentioned above and the evaluation is only on a tiny game. How well scalable would the approach be to larger games?\n\n(3) Experimental evaluation. The experiments are performed on one small game against one opponent on 5 runs of the system, without any statistical analysis of the confidence intervals. It is not sufficient to make any conclusions.\n\nSignificance: The proposed approach might be a good idea. However, without a clear comparison to competing methods, I do not think someone would choose to implement and use it on some practical problem. From the theoretical perspective, I understand the paper as an application of an existing method of DP to the problem of opponent modelling. Hence, there is no theoretical advancement. If it is not so, I assume the authors will argue for the theoretical novelty in the rebuttal. \n\n\n\nReferences:\n\n[A] Bard, N., Johanson, M., Burch, N., & Bowling, M. (2013, May). Online implicit agent modelling. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems (pp. 255-262).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is not much discussion on limitations or societal impact. Thorough discussion of computational costs would certainly be an improvement. I do not believe the paper has substantial societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "sEb-cOo49XJ", "reviewer": "Reviewer_hxK1", "summary": "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.\n\nThe 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.\n\nThe approach seems novel and improving previous works. I have some questions about experiments and limitations.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n-I think a relevant work that is missed is \"Safe Opponent Exploitation\"\n-I also would like to understand more about your contribution and previous work related to: \n\"Recently proposed streaming inference algorithms [23, 41] enable the DP mixture model to solve online non-stationary problems in a truly non-parametric way.  In this paper, we adopt this approach to model and simulate a non-stationary opponent for MARL.\"\n\nQuality\n- I would have liked to see ablation results for the \"correction\" mechanism, how robust are the result with respect to the hyperparameter $eta$\n- The paper mentions many times that the approach learns online, however in the conclusions\n\"It can be a heavy burden on an agent if it learns an opponent model from scratch online. Therefore, a more realistic way for utilizing the power of an opponent model is offline training and online prediction\"\n I'm a bit confused which parts are online, which parts offline.\n\n\nClarity\n- \"Our approach, EPSOM, is not limited to the self-play setting.\"\n I think EPSOM should *not* be used in self-play?\n- Figure 1 needs a better a more descriptive caption\n- I really like the exploitability and exploitation measures, I think you can add another result where those are the axes and you plot the results of different algorithms.\n- Figure 3 is a bit hard to interpret\n- Line 275: \"the training agent becomes risk-adverse\"  why?\n\nSignificance\n- Would this approach work for general sum games?\n- Would be interesting to see more experiments with more opponents and see how it scales\n- Both PPO and TRPO are algorithms that limit the change in the policy from one step to another, I would be interested to see EPSOM with more \"drastic\" changes.\n- \"EPSOM is limited by its computation and memory complexity. Naively applying EPSOM to more\n complex problems requires a great amount of resources.\" I appreciate the comment, however, I think more details would improve the paper.\n\nMinor:\nLine 290: \"use an agent learning\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussion on this topic", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "WCvxBjNajAW", "reviewer": "Reviewer_kzxK", "summary": "The paper presents a new approach for learning to play against an opposing agent in a two-player zero-sum game that can transition among an arbitrary set of strategies. Experiments in two-player Kuhn poker demonstrate that the approach obtains high degrees of exploitation and low values of exploitability compared to several benchmark approaches.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There appears to be a major problem with the paper. The main algorithm uses an RNR solver based on an LP formulation that is provided in the appendix, but this formulation is incorrect.\n\nIn particular, the first LP on page 579 on page 14 is incorrect, since the vector y_a is defined incorrectly on line 578. It should be y_a(j) = p pi_fix(a)  for j != a, not y_a(j) = 0 for j != a (the j=a case is correct).\n\nThere also should not be a need for the second LP, since player 1’s strategy should correspond to the dual variables from the first LP.\n\nThe second LP does appear correct, though the second set of constraints (pi^2(a) <= p pi_fix(a) + 1 – p) is redundant and implied by the final two constraints. \n\nSince the algorithms are based on an incorrect formulation, I assume all the experiments are incorrect, so I can’t really assess them further.\n\nI think that overall the problem is important and the approach is promising.\n\nSome other minor comments:\n37: dominated actions are not the only forms of irrationality in games. In fact, dominated actions are very rare in realistic poker games. See “Mistakes in Games” Ganzfried DAI 2019.\n\n38: a NE -> an NE \n\nnaive -> naïve \n\n90: Seems weird to cite a recent 2020 paper for the result that two-player zero-sum games can be solved in polynomial time by an LP.\n\n109: States that the approaches can be extended to multiplayer games, but RNR is defined only for two-player zero-sum games, so it should be elaborated on how the approach is applicable to multiplayer games.\n\nSection 3.1 seems to just present the standard definition of a normal-form game. I’m not sure why it is called a “meta normal-form game.” What is the “meta” part referring to that differentiates from a standard NFG?\n\nFootnote i refers to stochastic games, while the model in the paper is just for normal-form games. Why is there a reference to stochastic games here?\n\nThe game model described is for normal-form games, but experiments are on Kuhn poker, which is an extensive-form imperfect-information game. \n\n152: life-time -> lifetime\n\n156: why use a maximum-a-posteriori approach instead of alternatives?\n\n163: rolls-out -> rolls out\n\nIt would be helpful if some more information about the PPO algorithm is included, since it is the opposing agent as well as one of the benchmark algorithms.\n\nI think it might be helpful to include a static Nash equilibrium strategy as an additional benchmark strategy (there are multiple equilibria in this game, so perhaps some of the extreme point NE can be used).\n\nDoes “stds” mean “standard deviations”?\n\nIn Table 1 the standard deviations seem very large compared to the payoff values, which indicate that additional experiments should be run.\n\nAdditional comments after the responses and discussion:\n\nBased on the response it is likely that the authors probably used the correct LP formulation in the experiments and just wrote it wrong in the paper.\n\nThe authors claim that they have done additional experiments that achieve the same result. I'm not sure if we can just take their word. I think it is necessary to obtain statistical significance, and the current results do not come near this. In the response to 8Pgk they state that they also have comparisons against other benchmark agents SAM and MCCFR that show superiority of the new approach. But again I'm not sure if we can take into account results not in the paper. I would lean towards marginal acceptance if results showing statistical significance as well as comparisons against SAM and MCCFR were included.\n\nI would still be interested in seeing a comparison against static NE strategies (there are multiple NE). I think this is a very important benchmark to include.\n\nAuthor response:\n\"Mistakes in Games (Ganzfried 2019): Thank you for pointing out this interesting work. We will reword “dominated actions” to “dominated strategies” and discuss the difference between the two terms with reference to the work.\"\n\nThat paper actually shows that both dominated actions and strategies are very rare in realistic poker games, and proposes a new concept of a \"mistake\" that is more prevalent.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6qekFg96lf6", "reviewer": "Reviewer_oaZz", "summary": "This paper presents an algorithm for playing 2-player zero-sum repeated games that attempts to effectively balance the ability to model and exploit other agents while not opening one’s self to exploitation.  Limited results in Khun Poker when paired with three different algorithms are presented, with comparison to a handful of other methods.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Initial reflection for context: The paper addresses an old problem that has, from my perspective, been re-hashed repeatedly over the last several decades.  Despite being foundational and somewhat simple, the answers remain extremely difficult and hard to come by (I argue that the problem itself is ill-posed).  It is within this view that I base my review.\n\nStrengths:\n\n+ The paper is, for the most part, well-written and polished.  The technical description of the algorithm is detailed and seems solid (albeit I found the algorithm description difficult to follow).\n\n+ I really like the two measures the paper analyzes: ability to exploit and exposure to exploitation.  This trade-off is central to the problem at hand.  (I expound on this a bit in the weaknesses portion of the paper).\n\n+ For the empirical results that are presented, the algorithm appears to perform well.  The results are limited, and in some sense can be viewed as simply anecdotal.  However, I also do not want to diminish the strength of this contribution, as getting an algorithm to do this even in this limited context is no small accomplishment.\n\nWeaknesses:\n\n- I read the results differently than how they are discussed in the text of the paper (which seems to be bent on advocating, perhaps understandably so, for the algorithm presented in the paper).  To me, the key insight of the paper is the trade-off between exploitability and exploitation.  I’m not sure what the ideal trade-off between these measures is, but we could (for example) weight them equally.   If we do that, Figure 2 clearly shows that exploitability has higher magnitude across the algorithms than does exploitation.  If we simply subtract exploitability from exploitation, it appears to me that only PSRO has a positive value, suggesting it may be the best algorithm in this case among the 5 presented (though, again, the trade-off assessment of equal value between the metrics is subjective).  In the second set of results shown in Table 1, a similar trend continues, except that CEPSOM also has positive weight.  But the results don’t seem to be telling me that CEPSOM necessarily obtains a better trade-off than PSRO (which is essentially minimax in this game, as I understand it).\n\n- In all honesty, it is hard to make any general assessment about EPSOM and CEPSOM from these limited results.  Is there some opponent that could really exploit CEPSOM.  If so, when and how?  If not, when and how?  The authors state at the outset of the paper that they are not interested in self play.  But self play is a foundational comparison in this domain, as any good algorithm would be adopted by other agents over time necessitating a successful algorithm to be good (in some sense) in self play.  But modeling copies of one’s self is often problematic.\n\n- I do not understand Figure 3.\n\nAgain, this topic has been addressed for decades now, and I don’t know that we are any closer now to solving the problem than we were decades ago.  Perhaps that is because the problem itself is, in a loose sense, ill-posed — claiming algorithms are better than each other in this domain with trade-offs are largely subjective.  That is why I like the set of metrics (exploitation and exploitability) present in this paper — it looks at the (messy) trade-off of the problem.  I wish the authors had taken that trade-off further in their analysis.  If they are will to do that, I can envision the paper as a worthy contribution.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper doesn't explicitly address these aspects.  The limitations of the evaluation need to be further stated.  I don't think there is anything really to say about societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "?"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was a detailed discussion about this paper, and the relationship to Bard et al. was controversial, with some reviewers considering this a necessary benchmark and others agreeing with the authors that it isn't (necessarily).  Since it's controversial, I'm inclined to not make the decision based on the Bard et al. concern (though I encourage the authors to make sure to have really thought this through before a next submission).  Even so, the overall level of excitement among the reviewers is a bit low for acceptance, lacking any real advocate for the paper.  The additional experiments provided by the authors are appreciated and will be good to include in detail in a future version.  

I'll mark the paper as "reject but could be bumped up to accept" though I understand this means it's very likely to be rejected.
Decision: Reject