Offline Equilibrium Finding
Authors: Shuxin Li
Xinrun Wang
Jakub Cerny
Youzhi Zhang
Pengdeng Li
Hau Chan
Bo An
Venue: Submitted to ICLR 2023 (2023)

Abstract: Offline reinforcement learning (Offline RL) is an emerging field that has recently begun gaining attention across various application domains due to its ability to learn behavior from earlier collected datasets. Offline RL proved very successful, paving a path to solving previously intractable real-world problems, and we aim to generalize this paradigm to a multi-agent or multiplayer-game setting. To this end, we formally introduce a problem of offline equilibrium finding (OEF) and construct multiple datasets across a wide range of games using several established methods. To solve the OEF problem, we design a model-based method that can directly apply any online equilibrium finding algorithm to the OEF setting while making minimal changes. We focus on three most prominent contemporary online equilibrium finding algorithms and adapt them to the OEF setting, creating three model-based variants: OEF-PSRO and OEF-CFR, which generalize the widely-used algorithms PSRO and Deep CFR to compute Nash equilibria (NEs), and OEF-JPSRO, which generalizes the JPSRO to calculate (Coarse) Correlated equilibria ((C)CEs). We further improve their performance by combining the behavior cloning policy with the model-based policy. Extensive experimental results demonstrate the superiority of our approach over multiple model-based and model-free offline RL algorithms and the necessity of the model-based method for solving OEF problems. We hope that our efforts may help to accelerate research in large-scale equilibrium finding. 

Under review as a conference paper at ICLR 2023
OFFLINE EQUILIBRIUM FINDING
Anonymous authors
Paper under double- blind review
ABSTRACT
Offline reinforcement learning (Offline RL) is an emerging field that has recently begun gaining attention across various application domains due to its ability learn behavior from earlier collected datasets. Offline RL proved very success- ful, paving a path to solving previously intractable woal-world problems, and we aim to generalize this paradigm to a multi-agent or multiplayer- -aam setting. To this end, formally introduce problem of offline equilibrium finding (OEF) and construct multiple datasets across a wide range of games using several estab- lished methods. To solve the OEF problem, we design a model- method that can directly apply any online equilibrium finding algorithm to the OEF setting while making minimal changes. We focus on three most prominent contempo- rary online equilibrium finding algorithms and adapt them to the OEF setting, creating three model- variants: OEF-PSRO and OEF-CFR, which general- ize the widely-used algorithms PSRO and Deep CFR to compute Nash equilibria (NEs), and OEF-JPSRO, which generalizes the JPSRO to calculate (Coarse) Cor- related equilibria ((C)CEs). We further improve their performance by combining the behavior cloning policy with the model- policy. Extensive experimental results demonstrate the superiority of our approach over multiple model-based and model-free offfine RI. algorithms and the necessity of the model-based method for solving OEF problems. We hope that our efforts may help to accelerate research in large-scale equilibrium finding.
INTRODUCTION
Game theory provides a universal framework for modeling interactions among cooperative and competitive players (Shoham & -cyton-Brown, 2008). The canonical solution concept is Nash equilibrium (NE), describing a situation when no player increases their utility by unilaterally de- viating. However, computing NE in two-player or multi-player general-sum games is PPAD- complete (Daskalakis al., |206] [Cen & Deng (006), which makes solving games both exactly and approximately difficult. The situation remains non-trivial even in two-player zero-sum games, no matter whether the players may perceive the state of the game perfectly (c.g., in Go (Silver et al. 2016 imperfectly (c.g., in poker (Brown & Sandholm 2018) or StarCraft II (Vinyals et al, 2019). ). In recent years, learning algorithms have demonstrated their superiority in solving large- extensive-for form games over traditional optimization methods, including linear or nonlinear programs. The most successful learning algorithms belong either to the line of research counterfactual regret minimization (CFR) (Brown & Sandholm 2018), or policy space response oracles (PSRO) (Lanctot et al. 2017). CFR is an iterative algorithm approximating NEs using repeated self-play. Several
scale imperfect-informalee
campling-basee CFR variants (Lanctot et al. 2009 Gibson al. 2012) were proposed to solve large games efficiently. To scale up to even larger games, CFR could be embedded with neural network function approximation (Brown et al. 2019 Steinberger 2019 Li et al., 2019; Agarwal et al. 2020). The other algorithm, PSRO, generalizes the double oracle method (McMahan et al. 2003 Bošanský et al. 2014) by incorporating (deep) reinforcement learn- ing (RL) methods as a best-response oracle (Lanctot et al., 2017 Muller al. 2019). The neural fictitious self-play (NFSP) can be seen as a special case of PSRO (Heinrich et al. 2015). Both CFR and PSRO achieved great performance in solving large-scale imperfect-infoone information games, e.g., poker (Brown & Sandholm (0188; |cAAlerr et al. 2020). In this paper, we only focus on the Imperfect-informatiie extensive-form games.

---

Under review as a conference paper at ICLR 2023
One of the critical components of these successes is the existence of efficient and accurate simu- lators. A simulator serves as an environment that allows an agent to collect millions to billions of trajectories for the training process. The simulator may be encoded using rules as in different poker variants (Lanctot et al. 2019), or a video-game suite like StarCraft II (Vinyals et al. 2017). How-
ever, in many real-works games such football (Kurach al., 2020 TTuyls al.] 2021) table tennis (Ji et al., (021), constructing sufficiently accurate simulator may not be feasible because of a plethora of complex factors affecting the game-play. These factors include the relevant laws of physics, environmental circumstances (e.g., wind speed), or physiological limits of (human) bod- ies rendering certain actions unattainable. Therefore, the football teams or the table tennis players may resort to watching previous matches to alter their strategies, which semantically corresponds to offline equilibrium finding (OEF). Recent years have witnessed several (often domain- ) attempts to formalize offline learning in the context of games. For example, the StarCraft II Un- plugged (Mathicu et al. 202I) offers a dataset of human game-plays in this two-player zero-sum symmetric game. A concurrent work (Cui & Du 2022 investigates the necessary properties of offline datasets of two-player zero-sum games to successfully infer their NEs.
However, neither work considers the significantly more challenging field of multi-player games. To this end, we propose a general problem offline equilibrium finding (OEF) which aims to find the equilibrium strategy of the underlying game, given fixed dataset collected by an unknown behavior strategy. It is a big challenge since it needs to build the relationship between an equilibrium strategy and an offline dataset. To solve this problem, we introduce an environment model as the intermedi- ary between them. More specifically, our main contributions include i) proposing a novel problem OEF, and constructing OEF datasets from widely accepted game domains using different behavior strategies; ii) proposing a model- based method that can generalize any online equilibrium finding algorithm to the OEF setting by introducing an environment model; iii) adapting several existing online equilibrium finding algorithms to the OEF setting for computing different equilibrium solu- tions; iv) applying the behavior cloning technique to further improve the performance; v) conducting extensive experiments to verify the effectiveness of algorithms. The experimental results sub- stantiate the superiority of our method over model-based and model-free offline RL algorithms and the effectiveness and the necessity of the model-base method for solving the OEF problem.
2 RATIONALE BEHIND OFFLINE EQUILIBRIUM FINDING
We begin by providing a motivating scenario of OEF and comparing it to three related lines of re- search - opponent modeling, empirical game theoretic analysis, and offline RL- in order to highlight the rationale behind the introduction of OEF, We then justify the choice of model-based methods for OEF, A more detailed overview of related works is provided in Appendix A
Motivating scenario. Assume that a table tennis player A will play against player B whom they never faced before. What may A do to prepare for the match? In this case, though A knows the rules of table tennis, they remain un- aware of specific circumstances of playing against B, such as which moves or actions B prefers or their subjective pay- off function. Without this detailed game information, self- play or other online equilibrium finding algorithms cannot work. If player A simply play the best response strategy against player B's previous strategy, the best response strat- egy may be exploited if player B change his strategy. There- fore, player A has to watch the matches that player B played
The game of table tennis. against other players to learn their style and compute the equilibrium strategy, which minimizes ex- ploitation. This process corresponds to the proposed OEF methodology.
Figure 1:
Why offfine equilibrium finding? In games with complex dynamics like table tennis games or football games (Kurach et al., 2020), it is difficult to build realistic simulator or learn the policy during playing the game. A remedy is to learn the policy from the historical game data. Therefore, propose the offline equilibrium finding (OEF) problem, which can be defined as
Given a fixed dataset D collected by an unknown behavior strategy o, find an equilibrium strategy profile o" of the underlying game.
2

---

Under review as a conference paper at ICLR 2023
The OEF is similar Offline RL but poses several unique challenges: i) the canonical solution concept is the game-theoretic mixed Nash equilibrium, which requires an iterative procedure of computing responses; ii) the games have least two players who play against each other, which increases sensitivity to distribution shift and other uncertainties when compared with traditional Offline RI; and tii) the distribution shifts of the opponents' actions and the game are coupled, which brings difficulties to distinguish and address them.
Why Opponent Modeling (OM) is not enough? Opponent modeling is used to predict the oppo- nents' behavior strategies, in both single and multi-agent reinforcement learning (He et al.. 2016). However, predicting the opponents' behaviors only is not enough since the opponents in the OEF setting are not fixed but always best responding to the agent's 'ss strategy. In this work, we apply imi- tation learning, which is also used in opponent modeling, to learn the behavior cloning policy, and the experimental results show that simply applying the behavior cloning technique is not enough.
Why does Empirical Game Theoretic Analysis (EGTA) cannot work? The EGTA was proposed to reduce the complexity of large economic systems in electronic commerce (Wellman| 2006). It games (Wellman) 2006)
evolved into two main directions: strategic reasoning for simulation-
and evolutionary dynamical analysis of agent behavior inspired by evolutionary game theory (Tuyls ct al. 2018). The basic idea of EGTA is to use a sampled strategy to interact with a game simulator and estimate the empirical game from the simulation's 's results. It should consequently provide in- sights into the structure of the original game. PSRO (Lanctot et al.) 2017) is a specific case of EGTA. In offline equilibrium finding problem, only offline dataset collected by an unknown strategy is available, while the game simulator and sampled strategy are not provided. Therefore, EGTA cannot be applied find the equilibrium strategy only based on the offline dataset. Therefore, we propose a new model-based approach to find the equilibrium from an offline dataset. Our algorithm only relies on an offline dataset and does not require a game simulator or any known strategy.
Why naive Offline RL is not enough? The offline RL aims to Iearn a good behavior policy from previously collected datasets which can achieve the highest utility for the agent (Levine et al., 2020). However, maximizing the utility of each player in the game independently is not sufficient or prac- tical, because the utility of one player depends not only on its action but also on the actions of other players. Therefore, if we use the offline RL algorithm to learn the best strategy for each player in the game, it may cause huge loss since the computed best strategies for players may be exploitable. In other words, other players may play their best response strategies against the computed best strategy for the player instead of their behavior strategies in the offline dataset. Therefore, to compute the equilibrium strategy of the game, offline RL is not enough since it can only learn the best strategy for one agent independently. We also substantiate this claim empirically in the experiment section.
Why model-based methods? In traditional offline RL, the data of two actions may be used to determine which action is better (Levine et al. 2020). In contrast, the data of two action tuples in OEF are not enough decide which tuple is closer an equilibrium strategy as equilibrium identification requires other action tuples to serve as references (Cui & Du 2022). For computing equilibrium strategies. we hence need be able to evaluate any action tuple, and the data of some may be missing from the dataset. It prevents us from learning using model-free methods from the dataset directly. Therefore, we have to resort to simulating the game dynamies by a model give the agents their utilities. In this context, model-based methods, rather than other model-free methods, are arguably the most appropriate choices for solving the OEF problem. Unfortunately, most known model-based methods for single-agent reinforcement learning cannot be directly applied to games for equilibrium finding. The main reason is their inherent reliance on the existence of no strategic opponents in the environment. Though MuZero (Schrittwieser et al. 2020) can be applied to sym- metric two-player zero-sum games (e.g., Go) and solve the game with self-play, for heterogeneous players, it requires either a model for each agent separately or model for all agents. Training these agents' models is challenging in OEF due to the limited game data.
PRELIMINARIES
3.1 IMPERFFECT-INFORMATUE GAMES
An imperfect-informatie game (IIG) (hohaa & 2008) is represented as a tuple
(N, H. A, P, u), where N (1, (1..... n) set of players and A is set of histories (i.e., the
3

---

Under review as a conference paper at ICLR 2023
possible action sequences). The empty sequence 0 corresponds to unique root node of game tree included in H, and every prefix of a sequence in H is also in H. Z c H is the set of the terminal histories. A(h) {a (h, a) E H) is the set of available actions at any non-terminal history h E H. P the player function. P(h) is the player who takes an action at the history h, i.e., P(h) + N U {c}. denotes the "chance player", which represents stochastic events outside of the players' controls. If P(h) then chance determines the action taken at history h. Information sets I, form a partition over histories h where player i N takes action. Therefore, every information set I; E I corresponds to one decision point of player i which means that P(h1) = P(h2) and A(h1) = A(h2) for any h1, h2 E I, For convenience, we use A(I,) to represent the action set ((h) and P(T+) to represent the player P(h) for any h E I,. For i E N, a utility function u; Z IR specifies the payoff of player i for every terminal history.
A player's behavior strategy is function mapping every information set of player i to a probabil- ity distribution over A(T,) and Σ, is the set of strategies for player i. A strategy profile a is a tuple of strategies, one for each player. (T1,, O2..... Tn), with o-i referring to all the strategies in a except o; Let क (h) = ILeN T5 (h) be the probability of history h occurring if all players choose actions according to a. x (h) is the contribution of to this probability. Given a strategy profile o, the value to player the expected payoff of these resulting terminal nodes, u,(o)) Exez 'T" (z)u,(2).
The canonical solution concept is Nash equilibrium (NE). The strategy profile a forms an NE if u,(or) 2 maxa (1 a-x), Vi E N. To measure of the distance between a and the NE, we define NAsHCONV,(o) max;; uy M - u.(a) for each player and NASHCONV(a) = EieN NASHCONV;(O)) Except for the NE, some other solution concepts for extensive-form games exist conditional to different situations. For example, (Coarse) Correlated Equilibrium ((C)CE) is another popular solution concept for n-player general-sum games. A correlated equilibrium (CE) is joint mixed strategy such that no player has the incentive to deviate from it. Coarse correlated equilibrium (CCE) (Moulin& & Vial 1978) is a simpler solution concept that contains CE as a subset: NE C CE C CCE. A strategy profile is in CCE if no player wishes deviate before receiving a rec- ommended signal. Similar to NE, to measure of the gap between joint strategy a and the (C)CE, we use the (C)CE Gap Sum which describes how close joint policies
(C)CE under a (Marris) cet al. 2021 In this paper, we focus not only on the NE solution but also on the CCE solution.
3.2 EQUILIBRIUM FINDING ALGORITIMM
PSRO. PSRO is initialized with set of aandomly-geeraate policies E. for each player i. At each iteration of PSRO, a meta-gama game M is built with all existing policies of players and then a meta- solver computes a meta-strategy, i.e., a distribution over policies of each player (e.g.. Nash, o-rank or uniform distributions). The joint meta-strategy for all players is denoted as a, where a;(o) is the probability that player takes o as their strategy. After that, an oracle computes at least one policy for each player, which added to Σ. We note when computing the new policy for one player, all other players' policies and the meta-strategy are fixed, which corresponds to single-player opti- mization problem and can be solved by DQN (Mnih et al., 2015) or policy gradient reinforcement learning algorithms. NFSP can be seen special case of PSRO with uniform distributions as meta-strategies (Heinrich et al. 2015). Joint Policy Space Response Oracles (JPSRO) is a novel ex- tension to PSRO with full mixed joint policies to enable coordination among policies (Marris al., 2021]. JPSRO is proven to converge to a (C)CE over joint policies in extensive- games.
CFR. CFR is a family of iterative algorithms for approximately solving large imperfect-informee informaatonn games. Let of be the strategy used by player in round We define u,(o, h) as the expected utility of player given that the history h is reached, and then all players act according to strategy a from that point on. Let us define u, u,(a, h - a) as the expected utility of player i given that the history h is reached and then all players play according to strategy except player i who selects action a in history ht Formally, (a h) Erez x" ("h =2)x(2) and uz(o, h a) = Σrez T² T a, 2 =))((=). The counterfactual value vf (I) is the expected value of information set I given that player i attempts to reach it. This value the weighted average of the value of each history in an information set. The weight is proportional to the contribution of all players other than to reach each history. Thus, of (T) = Σner -_ T2,(h) Exez TO (h, z 2));(z). For any action a E A(T), the counterfactual value of action a is (1, = Eher
her (h) ELez T" a, 2) 2));(2). The instantaneous regret for action a in information set I of iteration 1 is r² (T,aa) up(1) (T,a) uiin (T). The counterfactual
4

---

Under review as a conference paper at ICLR 2023
BC policy
St
State Embedding
Rebu
Hiddlen layer
Output layer
St+1
Datasets
Model
Policy
Traa
Tr+1
MB policy
Figure 2: The flow of OEF algorithms.
Figure 3: Environment model structure.
Algorithm 1: General Framework of Offline Equilibrium Finding
Given an offline dataset D, train an environment model E;
Learn equilibrium policy x nh on E' using any model-based OEF algorithm;
(Optional) Based on D, train behavior policy nhe using BC technique;
(Optional) Combine n be and mb with appropriate weights get final policy
regret for action in 1 of iteration T is (T, Regret Matching to pick distribution actions an information set proportional the positive cumulative regret those actions. Formally, in iteration T + player selects action a A(I) according to probabilities
- (T. In vanilla CFR, players use
(T,a) Eseach (2.)
E ([ DEΛ(T)
(T,a)
otherwise,
where (1, max{R²" (1, 0} because are concerned about the cumulative regret when is positive only. If player acts according to regret matching in on every iteration, then in iteration T, (1) S A A.AAT where A; max, (2) min, u2(2) is the range of utilities of player i. Moreover, R. & ElEI, (T) S IIA A.IVT. Therefore, limy T 0. In two- Rº player zero-sum games, if both players' average regret 7 S their average strategies (of, oo) form a 2c-equilibrium (Waugh et al.] 2009). Most previous works focus on tabular CFR, where counterfactual values stored in table, Recent works adopt deep neural networks approximate the counterfactual values and outperform their tabular counterparts (Brown el al. 2019 Steinberger 2019
al. 2019 202T).
4
ALGORITHMS FOR OFFLINE EQUILIBRIUM FINDING
In real life, offline datasets may be collected using different behavior strategies. To simulate real- world cases, we focus on four types of datasets: expert dataset, learning dataset, random dataset, and hybrid dataset. Based on the offline datasets, we give the formal definition of the offline equilibrium finding problem. Details of offline datasets, the relationship between the information set and game state 8t, and some theoretical analysis the OEF problem be found in Appendix B
(St, a, 88+1; Tt+1) where 8t and 8t+1 refer to the game state, refer to the action played al and T141 refer to the reward after performing action a at st. The behavior strategy used to collect the dataset D is unknown. The OEF problem is to find approximate equilibrium strategy profile o² that achieves small gap between a² and equilibrium, i.e., the NASHCONV for NE and (C)CE Gap Sum for (C)CE, only based on D.
Definition (OEF). Given a game's 's offline dataset
Then, we introduce our proposed model- method (MB) for solving the OEF problem, which can adapt any online equilibrium finding algorithm into the context of the offline setting. Since the behavior cloning (BC) technique can learn good policy when the behavior policy of the dataset close to the equilibrium policy, which makes up for the deficiency the model-based algorithm in this aspect, apply the BC technique further improve the performance of the model-based algorithm. To do this, we combine these two methods (BC+MB) by assigning different weights to trained policies using these two methods to get the final strategy (see the experiments for details).
Figure 2 and Algorithm I show the general procedure the OEF algorithm. Given the offline dataset, first train environment model E. based these game data. Then perform
5

---

Under review as a conference paper at ICLR 2023
equilibrium finding algorithm on the trained environment model to learn model-based policy (MB policy). To further improve the performance, we first adopt the behavior cloning technique to learn policy (BC policy) directly from the offline dataset. Then we combine these two policies, i..,, the BC policy and the MB policy, by assigning proper weights to these two policies to obtain the final policy under different cases. We leave two unexplored options for future research: i) whether we can learn an MB policy with the regularization of the BC policy, as well as interacting with the dataset, and ii) if we can use the learned model to get the proper weights when combining the two policies. Next, we move to introduce the details of our model- method. The details of the behavior cloning technique can be found in Appendix D
4.1 ENVIRONMENT MODEL
In this part, we first focus on how to train an environment model based on an OEF dataset. The ultimate goal of OEF is to learn the approximate equilibrium strategy only based on an offline dataset. However, if we directly use the data in the offline dataset to compute the equilibrium strategy, we may not be able to evaluate the game states not included in the dataset. One possibility to deal with this issue is to train an intermediate environment model using the offline dataset to capture the game information which is necessary for computing the equilibria. In other words, the purpose of the trained environment model is to learn the dynamics of the game environment and output the next game state information based on the current game state and action. Since deep neural networks have powerful generalization abilities, the neural network model may provide approximate results for game states not sufficiently captured in the data. Figure 3 shows the structure of the environment model. The environment model E parameterized by 8g takes the game state St and action a of the player, who played at the state st, as inputs and outputs the next game state S141, the rewards T(+1 of all players, and other information such as the next legal action set and whether the game ends. We use stochastic gradient descent (SGD) optimizer to perform parameter updates when training the environment model. We can employ any loss function that satisfies the conditions of Bregman divergence (Banerjee et al. 20005), such mean squared error loss as below:
Lenv
(MSE) (MM((((5(11111)M P141, F(st, a; 0a))]-
4.2 MODEL-BASED ALGORIHTMM
After training the environment model, we aim to compute the equilibrium strategy based on this model. To this end, we generalize existing online equilibrium finding algorithms to the context of the OEF setting by replacing the actual environment used in these online algorithms with the trained environment model. In this paper, we propose three model-based algorithms: Offline Equilibrium Finding-Policy Space Response Oracles (OEF-PSRO) and Offline Equilibrium Finding- CFR (OEF-CFR) algorithms, which generalize PSRO and Deep CFR to compute NEs, and Offline Equi- librium Finding-Joint Policy Space Response Oracles (OEF-JPSRO), which generalize JPSRO to compute (C)CEs. Then we move to introduce these algorithms in detail.
In PSRO or JPSRO, a meta-game is represented as an empirical game starting with a single policy (uniform random) and iteratively enlarged by adding new policies (oracles) that approximate the best responses to the meta-strategies of other players. It is clear that when computing the best response policy oracle, interactions with the environment are required to gain game information. In the OEF setting, only an offline dataset is provided, and directly applying PSRO JPSRO is not feasible. In OEF-PSRO and OEF-JPSRO, we use the trained environment model to replace the actual envi- ronment to provide the game information. It is a common knowledge that when computing the best response policy using DQN or other reinforcement learning algorithms, the next state and reward based on the current state and the action are required. Our environment model can provide such information. The model can also offer additional information for approximating the missing entries in the meta- game matrix using the same manner. Deep CFR variant of CFR which uses neural networks to approximate counterfactual regret values and average strategies. During this approxi- mation, the game tree has to be partially traversed to arrive at the counterfactual regret value. This process requires an environment to provide the necessary game information. Akin to OEF-PSRO, also in OEF-CFR, we use the trained environment model to replace the actual environment. During the traversal, the environment needs to identify the next game state and utility for the terminal game state, for which we may employ our trained environment model. These algorithms are described in detail in Appendix D

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENTS
In this section, we evalutate our algorithms on the OEF datasets collected from various games. Firstly, we conduct two offline RL algorithms to verify their performance. Then, we evaluate the performance of our algorithms in computing NEs based on the OEF datasets via experiments on different offline datasets. Finally, assess the performance of our algorithm in computing CCEs based on the OEF datasets, we conduct the OEF-JPSRO algorithm on two three-player games.
5.1 EXPERIMENTAL SETTING
OpenSpiel is collection of environments and algorithms for research in general reinforcement learning and search/planning in games (Lanctot et al. 2019). is widely accepted and implements many different games. We use it as our experimental platform and opt for Kuhn poker, Leduc poker, Liar's Dice, and Phantom Tic- Toe, which are all widely used in previous works (Lisý et al.) 2015 Brown & Sandholm 2019). as experimental domains. To get the OEF datasets, generate three datasets for every game as introduced in Appendix B and mix the random and the expert datasets in different proportions to get hybrid datasets. Then we conduct our experiments offline datasets. NashConv (exploitability) is adopted for measuring the strategy of how close to NEs, and (C)CE Gap Sum is used measurement of the closeness (C)CEs. All the experiments are performed on server with a 10-core 3.3GHz Intel i9-9820X CPU and an NVIDIA RTX 2080 Ti GPU. All results are averaged over three seeds, and the error bars are also reported. Only selected results are shown here. The rest is deferred to Appendix
these
5.2 COMPARISON WITH OFFLINE RL
In this section, we empirically show that naive offline RL algorithms are not enough for the OEF setting. To this end, we select one model-based offline RL algorithm -ooee-bbsed Offline Policy Optimization (MOPO) (Yu et al. 2020) and one model-free offline RL. algorithm - Best-Action Imitation Learning (BAIL) (Chen et al.] (020)) as the representative of offline RL algorithms. Figures 4(b) and 5(b] show the comparison results of two-player Kuhn poker and two-player Leduc poker games. The x-axis represents the proportion of random data in the hybrid dataset. If the ratio is zero, the dataset equals the expert dataset, and if the percentage is one, it indicates that the hybrid dataset is the random dataset. We can find that in these hybrid datasets, our algorithm performs better than these two offline RL algorithms. It also shows that the performance of the MOPO algorithm varies widely regardless of the type of the dataset. Compared to the MOPO, the performance of BAIL. is somewhat related to the quality of the dataset. However, neither of these offline RI. algorithms can get a strategy profile close enough to the equilibrium strategy, which may be due to the players' policies being optimized independently. These offline RL algorithms cannot perform well in the OEF setting, which verifies the claim that offline RL is not enough for the OEF setting.
5.3 NASH EQUILIBRIUM
Before running our OEF algorithms, we first analyze the OEF datasets. We count the frequency of leaf nodes and perform Fourier transform on Figures 4(a) and 5(a) show the analysis results for different datasets. It can be found that there are more high-frequency data in the expert dataset than in the random dataset. And the learning dataset and other hybrid datasets are intermediate between the expert dataset and random dataset. More analysis results of datasets can be found in Appendix C
We first run the behavior cloning technique and model- based algorithms solely on several games based on their hybrid datasets to assess their performance. Figures [[c and [(c) show the results of BC on two-player Kuhn poker and Ledue poker games. We can see that as the proportion of the random dataset increases, the performance of BC policy decreases in these two games. The finding intuitive since the BC technique can mimic the behavior strategy in the dataset and performs well only on datasets containing more expert data. It also shows that with the increase in the size of offline data, the performance evolves more stable while the improvement is not very significant. Therefore, the performance of BC policy depends the quality of datasets, i.e., the quality of the behavior policy used to generate the dataset. Figures 4(d) and 5(d) show the results of MB. From
https://gi tht.ggttthhh..... com www.///wwwww.../.cc...t..t.....a nd/ htt.eemmiind/peeesppepp.pe

---

Under review as a conference paper at ICLR 2023
Amplhauleccs
NaahOunn
Nashtoon
BC: Rati Man 1006
Nasht
Daa cm thai Isea nee mato Bata forr Loko
La
0..
Proportion Random Datuset
Propection Random Dataset
Proportion Randem
(a) Dataset Analysis
(b) Offline RL
(c) Behavior Cloning
(d) Model Based Method
BC--eee: Data the
IECaNn thde Mer 3000
tasa Siw 200
NtahCun
NeathConn
His your (PR) Tata iree
NaalCCom
60
64
26
66
Dutuset
1s
60
02
2/
6o
Dutaset
10
66
244
0a 10
Number Players
(e) BC+MB
(I) BC+MB
Weight
(h) Learning Dataset
Figure 4: Experimental results on two-player Kuhn poker.
33.0
M
11.3
KC Daks
ose con Polo doa toap
Nadiioaa
NichCaan
Iota 2000
2.3-
Frequensyttte
Proportion Random Dataset
Proportion of Random Datanet
Proportion of Random Dataset
(a) Dataset Analysis
(b) Offline RL
(c) Behavior Cloning
(d) Model Based Method
11.
13.0
Dute Kiw Teaas
NachCoon
22.5
Iec. Buto 1969
12.5
Mr: Bela Alo 2ane
Weightt of nC
NuahCou
BC-HEE
7.5
Propertion of Random Dataset (c) BC+MB
Propoction of Random Dutaect
Propection of Random Dataset
Number of Players
(f) BC+MB
g
Weight
(h) Learning Dataset
Figure 5: Experimental results on two-player Ledue poker.
Figure 4(d) we find that OEF-CFR and OEF-PSRO can get almost the same results. It indicates that the performance of MB mainly depends on the quality of the trained environment model, and we can use either algorithm to calculate MB policy. Another finding is that with the increase in the size of offline data, the performance becomes better. It indicates that if the dataset includes enough data, the trained environment model is closer to the actual environment (test environment). From the above results, we can know that the BC policy performs poorly in the random dataset and performs well in the expert dataset. However, the MB method performs slightly poorly in the expert dataset. To further improve the performance of the final strategy, straightforward way to merge these two policies by assigning proper weights to them in different cases.
Let us first introduce the combination method BC+MB, i.e. how combine these two policies. Let be the weight of BC policy. Then the weight of the MB policy is 1 a. We preset 11 weight assignment plans, i.e., a E (0, 0., 0.9, 1}. Next, we use these 11 weight assignment plans to combine these two policies to get set of final policies. Then test these final policies in a real game to get the best final policy according to the exploitability. Another more complex method is to leam the weights using few-shot interactions with the real game. We left this future work.
Figures 4(e) 4(1) and ((c) 5(1) show the results of BC+MB on two-player Kuhn and Leduc poker games. We also plot the results of BC and MB methods for comparison. We found that the BC+MB method performs better than both BC and MB methods in all cases, which indicates that the com- bination is useful. The weights of BC policy (a) which make these combined policies perform best
8

---

Under review as a conference paper at ICLR 2023
0.044
Kuhn Polce
Kuhn Paker
Lodut Poker
Tedoc Polcer
Angllitdecon
0L003
Inarsheo Polaod
Hatk Max sam
200 Con Suum
Blus taur Jeam
Frequency(itt
10 Propection Random Datuset
Frequencytit
Propection ol Random Datastt
64
10
(a) Dataset Analysis
(b) OEF-JPSRO
(c) Dataset Analysis
(d) OEF-JPSRO
Figure 6: Experimental results on multi- games.
on these datasets are shown in Figures gg) and 5(g)
As the proportion of the random dataset de- creases, the weight of the BC policy in the final policy increases. It adheres to the intuition that BC policy performs well when the dataset includes many expert data. In that case, the weight of the BC policy in the final policy is high. We also test the BC+MB algorithm on poker games with different players under the learning datasets which can be viewed as datasets produced by unknown strate- gies. Figures 4hh and 5(h) show that BC+MB outperforms other methods in all games including multi-player Kuhn poker and Ledue poker. It indicates that given a dataset generated by an unknown strategy, the BC+MB algorithm can always get good policy closing to the equilibrium strategy.
5.4 COARSE CORRELATED EQUILIBRIUM
To evaluate the performance of the OEF-JPSRO algorithm in computing the CCE strategy, we per- form experiments on two three-player poker games under hybrid datasets. In these multi-player games, although there is guarantee to converge to NE, we can still use PSRO with a-rank as meta-game to get a good strategy (low exploitability) to generate the expert dataset. Here, we did not perform the behavior cloning technique since the offline dataset is collected using indepen- dent strategy of every player instead of a joint strategy. Figure shows the results on three-player Kuhn and Ledue poker games. The analysis of datasets shows the same result before. As the size of the used offline data increases, we find that the performance of OEF-JPSRO improves. It further verifies that the performance of the model-based method mainly depends on the environ- ment model, which may need more data to get well trained. We also run OEF-CFR algorithm on these three-player poker games (Appendix EE. Since the strategy learned by OEF- DEF-CFR not a joint strategy, we only compute the NashConv to measure how close it is to the NE.
6 CONCLUSION
We initiated an investigation of offline equilibrium finding (OEF), i.e., equilibrium finding on offline datasets. We constructed OEF datasets from four widely-used games using three data-collecting strategies. To solve the OEF problem, we proposed model-based method that can generalize any online equilibrium finding algorithm with mere changes by introducing an environment model. Specifically, we adapted several existing online equilibrium finding algorithms to the OEF setting for computing different equilibrium solution concepts. To further improve the performance, we combined the behavior cloning technique with the model-based method. Extensive experimental results demonstrated that our proposed algorithm performs better than existing offline RI. algorithhss and the -ased method is necessary for the OEF setting. We hope our efforts may open new directions in equilibrium finding and accelerate the research in game theory.
Future works. There are several limitations of this work that we intend to tackle in the future. First, the games we considered are rather smaller and large-scale games like Texas Hold'en em poker (Brown) & Sandholm, 2018) were postponed till future work. Second, the types of generated offline datasets are limited. For future work, we plan to collect datasets using large-scale games and connect our library to StarCraft II Unplugged (Mathieu et al. 202T). We will also include more data-collecting strategies (e.g., bounded rational agents) as well as additional human expert data to diversify the provided datasets. Moreover, we will investigate the relations between data distributions and OEF algorithms to characterize the influence of the data on the performances of OEF algorithms.
3
http:://pcken cs. ua wwwabbetaaccom wtw.
html

---

Under review as a conference paper at ICLR 2023
REFERENCES
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Mar- tin Riedmiller. Maximum posteriori policy optimisation. arXiv preprint arXiv:1806. arX.v:1806.06920, 2018.
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective offline reinforcement learning. In ICML, pp. 104-114, 2020.
Maruan Al-Shedivat, Trapit Bansal, Yuri Burda. Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. arXiv preprint arXiv: (oXXv::111000344111 2017.
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Cluster- ing with bregman divergences. Journal of Machine Learning Research, 6(10), 2005.
Branislav Bošanský, Christopher Kiekintveld, Viliam Lisý, and Michal Péchouček. An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information. Jour- nal of Artificial Intelligence Research, 51:829-866 2014.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, S 359(6374):4418-424, 2018.
Noam Brown and Tuomas Sandholm. Solving imperffect-informatio games via discounted regret minimization. In AAAI, pp. 1829-1836, 2019.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In JCML, pp. 793-802, 2019.
Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. FOCS, pp- 261-272, 2006.
Xinyue Chen, Zijian Zhou, Zheng Wang, Che Wang, Yanqiu Wu, and Keith Ross. Bail: Best- action imitation learning for batch deep reinforcement learning. Advances in Neural Information Processing Systems, 33: 13353-311,,,, 2020.
Qiwen Cui and Simon S. Du. When is offline two-player zero-sum markov game solvable? arXiv preprint arXiv:2201.03333 2022.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a Nash equilibrium. In STOC, pp. 71-78, 2006.
Jakob N Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. arXiv preprint arXiv:1709.04322 2017.
Scott Fujimoto and Shixiang Gu. A minimalist approach to offline reinforcement learning. In NeurlPS, 2021.
Richard Gibson, Mare Lanctot, Neil Burch, Duane Szafron, and Michael Bowling. Generalized sampling and variance in counterfactual regret minimization. In AAAI, pp. 1355-1361, 2012.
Aditya Grover, Maruan Al-Shedivat, Jayesh Gupta, Yuri Burda, and Harrison Edwards. Learning policy representations in multiagent systems. In International Conference on Machine Learning, pp. 1802,1811, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International Confer- ence on Machine Learning, pp. 1861-1870, 2018.
He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daumé III. Opponent modeling in deep rein- forcement learning. ICML, pp. 1804-1813, 2016.
Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games. In ICMI, pp. 805-813, 2015.
10

---

Under review as a conference paper at ICLR 2023
Zhang-We Wei Hong, Shih- Yang Su, Tzu- Yun Shann, Yi-Hsiang Chang, and Chun- Yi Lee. A deep policy inference q q-network for multi-agent systems. arXiv preprint arXiv: 2017.
Yunfeng Ji, Xiaoyi Hu, Yutao Chen, Yue Mao, Gang Wang. Qingdu Li, and Jianwei Zhang. Model- based trajectory prediction and hitting velocity control for new table tennis robot. In IROS, pp- 2728-2734, 2021.
Patrick Jordan, Julian Schvartzman, and Michael P Wellman. Strategy exploration in empirical games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pp. 1131-1138 2010.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. Advances Neural Information Processing Systems, 33: 11810-21823, 2020.
Dong Ki Kim, Miao Liu, Matthew D Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sehastian Lopez-Cot, Gerald Tesauro, and Jonathan How. A policy gradient algorithm for learning to learn in multiagent reinforcement learning. In International Conference Machine Learning, pp. 5541-5550, 2021.
Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yoga- mani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transsportttinn Systems, pp. 4909 2022.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33:1 179-11999 2020.
Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Car- los Riquelme, Damien Vincent, Marein Michalski, Olivier Bousquet, football: A novel reinforcement learning environment. In AAAI, pp. 4501-4510, 2020.
Google research
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte Carlo sampling for regret minimization in extensive games. NeurlPS, pp. 1086-1066, 2009.
Mare Lanctot, Vinieius Zambaldi, Audrũnas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent rein- forcement learning. In NeurIPS, pp. 4193-4206, 2017.
Mare Lanctot, Edward Lockhart, Jean- San-tBatistt Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafici, et al. OpenSpiel: A framework for reinforcement learning in games. arXiv preprint arXiv: 094.094,3, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01644, 2020.
Hui Li, Kailiang Hu, Shaohua Zhang, Yuan Qi, and Le Song. Double neural counterfactual regret minimization. In ICLR, 2019.
Shuxin Li, Youzhi Zhang, Xinrun Wang. Wanqi Xue, and Bo An. CFR-MIX: Solving imperfect information extensive-form games with combinatorial action space. In IJCAI, pp. 3663-3669, 2021.
Viliam Lisý, Mare Lanctot, and Michael Bowling. Online Monte Carlo counterfactual regret mini- mization for search in imperfect information games. In AAMAS, pp. 27-36, 2015.
Siqi Liu, Kay Choong See, Kee Yuan Ngiam, Leo Anthony Celi, Xingzhi Sun, Mengling Feng, et al. Reinforcement learning for clinical decision support in critical care: comprehensive review. Journal of Medical Internet Research, 22(7)ee1447)) 2020.
Luke Marris, Paul Muller, Mare Lanctot, Karl Tuyls, and Thore Grapael. Multi-agent training beyond zero-sum with correlated equilibrium solaes. arXiv preprint arXiv:2106.091 09435,, 2021.
11

---

Under review as a conference paper at ICLR 2023
Michael Mathieu, Sherjil Ozair, Srivatsan Srinivasan, Caglar Gulcehre, Shangtong Zhang, Ray Jiang. Tom Le Paine, Konrad Zolna, Richard Powell, Julian Schrittwieser, et al. StarCraft II Unplugged: Large scale offline reinforcement learning. In Deep RL Workshop NeurIPS 2021, 2021.
Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. arXiv preprint arXiv:2006.03647, 2020.
Stephen McAleer, John Lanier, Roy Fox, and Pierre Baldi. Pipeline psro: a scalable approach for finding approximate nash equilibria large games. In NeurIPS, pp. 20238 20244,, 2020.
Stephen McAleer, Kevin Wang, Mare Lanctot, John Lanier, Pierre Baldi, and Roy Fox. Anytime optimal psro for two-player pero-sum games. arXiv preprint arXiv:2201.07700 2022.
Stephen Marcus McAleer, John Banister Lanier, Kevin Wang, Pierre Baldi, and Roy Fox. Xdo: A double oracle algorithm for extensive-form games. Advances Neural Information Processing Systems, 2021.
H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In ICML, pp. 536-543, 2003.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529-333. 2015.
Hervé Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3):011-22,, 1978.
Paul Muller, Shayegan Omidshafici, Mark Rowland, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Mare Lanctot, Edward Hughes, al. generalized training approach for multiagent learning. In ICLR, 2019.
Rafael Figueiredo Prudencio, Marcos ROA Maximo, and Esther Luna Colombini. A survey on offline reinforcement learning: Taxonomy, review, and open problems. arXiv preprint arXiv:2203.01387. 2022.
Martin Schmid, Neil Burch, Marc Lanctot, Matej Moraveik, Rudolf Kadlec, and Michael Bowl- ing. Variance reduction in Monte Carlo counterfactual regret minimization (VR-MCCFR) for extensive form games using baselines. In AAAI, pp. 2157-2164. 2019.
Julian Schrittwesser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering Atari, Go, chess and shogi by planning with learned model. Nature, 588(7839):604 2020.
L Julian Schvartzman and Michael Wellman. Exploring large strategy spaces in empirical game modeling. Agent Mediated Electronic Commerce (AMEC 2009), pp. 139, 2009a.
L Julian Schvartzman and Michael P Wellman. Stronger cda strategies through empirical game- theoretic analysis and reinforcement learning. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, pp. 246,2556.22999 2009b.
Yoav Shoham and Kevin Brown. Multiagent Systems: Algorithmic, Game-Theoree and Logical Foundations. Cambridge University Press, 2008
Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp. Abbas Abdolmaleki, Michael Ne- unert, Thomas Lampe, Roland Hafner, Nicolas Heess, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint arXiv:2002.08336, 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
12

---

Under review as a conference paper at ICLR 2023
Bharat Singh, Rajesh Kumar, and Vinay Pratap Singh. Reinforcement learning in robotic applica-
tions: a comprehensive survey. Artificial Intelligence Review, pp. 1-46, 2021.
Adish Singla, Anna N Rafferty, Goran Radanovic, and Neil T Heffernan. Reinforcement learning for education: Opportunities and challenges. arXiv preprint arXiv:2107.08828, 2021.
Eric Steinberger. Single deep counterfactual regret minimization. arXiv preprint vrXiv::901.0762. 2019.
K Tuyls, J Perolat, M Lanctot, JZ Leibo. and T Graepel. A generalised method for empirical game theoretic analysis. In AAMAS, pp. 77-85, 2018.
Karl Tuyls, Shayegan Omidshafiei, Paul Muller, Zhe Wang, Jerome Connor, Daniel Hennes, Ian Graham, William Spearman, Tim Waskett, Dafydd Steel, et al. Game plan: What Al can do for football, and what football can do for AI. Journal of Artificial Intelligence Research, 71:41-88, 2021.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Star- Craft A new challenge for reinforcement learning. arXiv preprint arXiv: 708.0478727 2017.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaöl Mathieu, Andrew Dudzik, Juny- oung 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):350-334 2019.
Kevin Waugh, David Schnizlein, Michael H Bowling, and Duane Szafron. Abstraction pathologies in extensive games. In AAMAS, pp. 781-788, 2009.
Michael Wellman. Methods for empirical game-theoretic analysis. In AAAI, pp. 1552-1556, 2006.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 33: 14111119114142 2020.
Tianhe Yu. Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. Combo: Conservative offline model-based policy optimization. Advances in Neural Information Processing Systems, 34, 2021a.
Xiaopeng Yu, Jiechuan Jiang, Haobin Jiang, and Zongqing Lu. Model-based opponent modeling. arXiv preprint 2rXiv:2108.008: 2021b.
Yan Zheng, Zhaopeng Meng, Jianye Hao, Zongzhang Zhang, Tianpei Yang, and Changjie Fan. A deep bayesian policy reuse approach against non non-stationary agents. Advances in neural informa- tion processing systems, 31, 2018.
13

---

Under review as a conference paper at ICLR 2023
A RELATED WORK OVERVIEW
Offline Reinforcement Learning (Offtine RL). Offline RL is a data-driven paradigm that learns exclusively from static datasets of previously collected interactions. making it feasible to extract policies from large and diverse training datasets (Levine et al. 2020). This paradigm can be ex- tremely valuable in settings where online interaction is impractical, either because data collection is expensive or dangerous (e.g., in robotics (Singh et al. (021). education (Singla et al., 202T). health- care (Liu et al. (020), and autonomous driving (Kiran et al., (022)). Therefore. efficient offline RL algorithms have much broader range of applications than online RL. and are particularly appealing for weal-woldd applications (Prudencio et al., (022). Due to its attractive characteristics, there have been a lot of recent studies. Here, we can divide the research of Offline RL into two categories: model-based and model-free algorithms.
Model-free algorithms mainly use the offline dataset directly to learn a good policy, When learn- ing the strategy from an offline dataset, we have two types of algorithms: actor-critic and imitation learning methods. Those actor-critic algorithms focus on implementing policy regularization and value regularization based existing reinforcement learning algorithms. Haarnoja al. (Haarnoja jet al., 2018) propose soft actor-critic (SAC) by adding an entropy regularization term to the pol- icy gradient objective. This work mainly focuses on policy regularization. For the research of value regularization, an offline RL method named Constrained Q- Q-Learning (CQL) (Kumar et al.) 2020) learns a lower bound of the true Q-function by adding value regularization terms its objec- tive. Another line of research on learning a policy is imitation learning which mimics the behavior policy based on the offline dataset. Chen et al. (Chen et al. 2020) propose a method named Best- Action Imitation Learning (BAIL), which fits a value function, then uses it to select the best actions. Meanwhile, Siegel et al. (Siegel et al. 2020) propose a method that learns an Advantage-weighted Behavior Model (ABM) and uses it as prior in performing Maximum a-posteriori Policy Opti- mization (MPO) (Abdolmaleki et al. 2018). It consists of multiple iterations of policy evaluation and prior learning until they finally perform a policy improvement step using their Iearned prior to extracting the best possible policy. Model-based algorithms rely on the offline dataset to learn a dynamics model induced by models to determine the best set of actions to take at each given time step. Kidambi et al. (Kidambi et al., 2020) propose a method named Model-based Offline Reinforcement Learning (MOReL), which measures their model's 's epistemic uncertainty through an ensemble of dynamics models. Meanwhile, Yu et al. (Yu al.] 2020) propose another method named boseel-baed Offline Policy Optimization (MOPO), which uses the maximum prediction uncertainty from an ensemble of models. Concurrently, Matsushima et al. (Matsushima et al., 2020) propose the BehaviorkFFgu- larized Mosel-EN (BREMEN) method, which learns an ensemble of models of the behavior MDP, as opposed to a pessimistic MDP. In addition, it implicitly constrains the policy to be close to the behavior policy through trust-region policy updates. More recently, Yu et al. (Yu al. 202 proposed a method named Conservative Offline Model-Based policy Optimization (COMBO), a model- version of CQL. The main advantage of COMBO concerning MOReL and MOPO is that it removes the need for uncertainty quantification in model-based offline RL approaches, which is challenging and often unreliable. In the OEF setting, these above Offline RL algorithms can not directly apply to it, which we have described in section 2 and experimental results empirically verify this claim.
trajectory distribution used for planning. We use the trajectory distribution
Empirical Game Theoretic Analysis (EGTA). Empirical Game Theoretic Analysis is an empir- ical methodology that bridges the gap between game theory and simulation for practical strategic reasoning (Wellman 2006). In EGTA, game models are iteratively extended through a process of generating new strategies based on learning from experience with prior strategies. The strategy exploration problem (Tordan et al. (010) that how to efficiently assemble an efficient portfolio of policies for EGTA is the most challenging problem in EGTA.
Schvartzman & Wellman (Schvartzman & Wellman 2009b) deploy tabular RL as a best-response oracle in EGTA for strategy generation. They also build the general problem of strategy explo- ration in EGTA and investigate whether better options exist beyond best-responding to an equilib- rium (Schvartzman & Wellman| 2009a). Investigation of strategy exploration was advanced signif- icantly by the introduction of the Policy Space Response Oracle (PSRO) framework (Lanctot al.) 2017) which is a flexible framework for iterative EGTA, where at each iteration, new strategies generated through reinforcement learning. Note that when employing NE as the meta-strategy
14

---

Under review as a conference paper at ICLR 2023
solver, PSRO reduces to the double oracle (DO) algorithm (McMahan et al. 2003). In the OEF setting, only an offline dataset is provided, and there is no accurate simulator. In EGTA, a space of strategies is examined through simulation, which means that it needs simulator, and the policies are known in advance. Therefore, techniques in EGTA cannot directly apply to OEF.
Opponent Modeling (OM) in Multi-Agent Learning. Opponent modeling algorithm is necessary in multi-agent settings where secondary agents with competing goals also adapt their strategies, yet it remains challenging because policies interact with each other and change (He et al.) 2016). One simple idea of opponent modeling is to build a model each time a new opponent or group of opponents is encountered (Zheng et al. 2018). However, it is infeasible learn a model every time. A better approach is to represent an opponent's 's policy with an embedding vector. Grover et al. (Grover et al.) 2018) use a neural network as an encoder, taking the trajectory of one agent as input. Imitation learning and contrastive learning are also used to train the encoder. Then, the learned encoder can be combined with RL by feeding the generated representation into the policy or/and value network. DRON (He et al.) 2016) and DPIQN (Hong et al. 2017) are two algorithms based on DQN, which use a secondary network that takes observations as input and predicts opponents' actions. However, if the opponents can also learn, these methods become unstable. So it is necessary to take the learning process of opponents into account.
Foerster et al. (Foerster al. 2017) propose method named Learning with Opponent-Learning Awareness (LOLA)), in which each agent shapes the anticipated learning of the other agents in the environment. Further, the opponents may still be learning continuously during execution. Therefore, Al-Shedivat et al. (Al-Shedivat et al. (017) propose method based on a meta policy gradient named Mata-MPG. It uses trajectories from current opponents to perform multiple meta-gradien steps and constructs a policy that favors updating the opponents. Meta-MAPG (Kim et al.) (02T)) extends this method by including an additional term that accounts for the impact of the agent's current policy on the future policies of opponents, similar to LOLA. Yu et al. (Yu et al. (021b) propose model- based opponent modeling (MBOM), which employs the environment model to adapt to various opponents. In the OFF setting, our goal is to compute the equilibrium strategy based on the offline dataset. Applying opponent modeling is not enough for calculating the equilibrium strategy in the OEF setting since the opponent will always best respond to the agent.
Equilibrium Finding Algorithms. The contemporary state-of-the-art algorithms for solving imperfect- innfrfeatiinnoooooiinnnn extensive-form games may be roughly divided into two groups: no-regret methods derived from CFR, and incremental strategy-space generation methods of the PSRO frame- work. For the first group, some variants are proposed solve large-scale imperfecttinformation extensive-form games. Some sampling-basee 2012 (ccmmd al. 2019) of the game tree instead of the whole game tree. With the development of deep learning techniques, neural network function approximation is also applied CFR algorithm. Deep CFR (Brown al.) 2019). Single Deep CFR (Steinberger, 2019) and Double Neural CFR (Li et al. 2019) are algo- rithms using deep neural networks replace the tabular representation in the CFR algorithm. For the second group. PSRO (Lanctot et al., 2017) is a general framework that scales Double Oracle (DO) (MeMahan et al., 2003) to large extensive-form games via using reinforcement learning to compute the best response strategy approximately. To make PSRO more effective in solving large- scale games, Pipeline PSRO (P2SRO) (MeAleer et al. 2020) is proposed by parallclizing PSRO with convergence guarantees. Extensive- of PSRO where the restricted game allows mixing population strategies not only at the root of the game but every information set. It can guarantee converge of iterations that are linear in the number of information sets, while PSRO may require a number of iterations exponential in the number of information sets. Neural XDO (NXDO) as a neural ver- sion of XDO learns approximate best response strategies through any deep reinforcement learning algorithm. Recently, Anytime Double Oracle (ADO) (McAleer et al. 2022), a tabular double or- acle algorithm for 2-player zero-sum games is proposed to converge to a Nash equilibrium while decreasing exploitability from one iteration to the next. Anytime PSRO (APSRO) as version of ADO calculates best responses via reinforcement learning algorithms. Except for NEs, other equi- librium solution concepts, for example, (Coarse) Correlated equilibrium (CC)CE) are considered. Joint Policy Space Response Oracles (JPSRO) (Marris et al. (021) is proposed for training agents in n-player, general-sum extensive- formm games, which provably converges to (C)CEs. The excellent performance of these equilibrium finding algorithms depends on the existence of efficient and accu-
CFR variants (Lanctot et al. 2009) Gibson et al.) 2019) are proposed effectively solve large-scale games by traversing a subset
Double Oracle (XDO) (McAleer et al. 202 is version
approximate NE in number
15

---

Under review as a conference paper at ICLR 2023
rate simulators. However, constructing a sufficiently accurate simulator may not be feasible very expensive. In this case, we may resort to offline equilibrium finding (OEF) where the equilibrium strategy is computed based the previous game data.
B DATASET
In this section, we describe four types of data sets and how to collect them.
Random dataset. This type of dataset is collected using a random strategy. The motivation behind this is that when do not know how play a game, we may try explore randomly. The process of collecting is akin to that of a beginner familiarizing themselves with the game for the first time. The dataset collected in three steps. First, we assume that every player plays uniform strategy. Second, the players engage in the game repeatedly. Finally, we collect the generated game data. Note that in imperficttinformmaiion extensive-form games, the definition of information sets corresponds to the decision points of players. Here, we take the information sets of all players in the game as a game state, Therefore, the game data include the transition information such as current game state game information, e.g., whether the game ends and players' rewards r2+1 = (r) 1-1 1+1 1.
(Tf ..,, 12)), action a, next game state 8t+1 (7++1 12+1 ..... T(+1), and other
Learning dataset. This type of dataset collected when learning the Nash equilibrium strategy. When solving a game using some existing equilibrium finding algorithm, the players have to inter- act with the game environment. During the course learning, we may gather these intermediate interaction game data and store them learning dataset. In contrast the random dataset, the players' strategies gradually improve as we get closer to Nash equilibria.
Expert dataset. This type of dataset is collected using NE strategy. The motivation behind the dataset that when learning a game, we often prefer to observe more experienced players at play. We simulate the expert players using the NE strategy and collect the interaction data. We follow a similar methodology as with the random dataset. First, we compute the NE strategies using any existing equilibrium finding algorithm. As second step, the Nashian players repeatedly interact in the game. Finally, we gather the generated data and store them as the expert dataset. In multi- player or general-sune sum games, although CFR or PSRO cannot converge NE, we also apply these algorithm for collecting the expert dataset. Although there is no guarantee, we can still get a good strategy using these algorithms, for example, PSRO with a-rank as the meta-solver Muller et al. 2019 can get pretty good strategy (low exploitability) under general-sum many many-player games.
Hybrid dataset. In addition to the three types of datasets mentioned above, we also consider hybrid datasets consisting of random and expert interactions mixed in different ratios to simulate offline datasets generated by unknown strategies.
We collect the data from player engagements in the most frequently used benchmarking imperfect- information extensive-fome games in contemporary research on the equilibrium finding. These games include poker games (two-player and multi-player Kuhn poker, two-player and multi-player Ledue poker), Phantom Tic-Tac-Toe, and Liar's Dice.
B. INFLUENCE OF DATASET COVERAGE
The concurrent work Cui & Du 2022 investigates the necessary properties of offline datasets of two-player zero-sum Markov games to successfully infer their NEs. To do this, they proposed sev- eral dataset coverage assumptions. Following the work by Cui & Du (2022). we can also define two assumptions on the dataset coverage of offline datasets. These theorem results are all for computing Nash equilibria in two-player zero-sum games.
Assumption 1. The NE strategy a* covered by the expert dataset.
Assumption 2. For Vst. a A(s:), (st, a, S141) is covered by the random dataset.
From the empirical analysis, we know that the performance of the model-based algorithm mainly depends the gap between the trained environment model and the actual game environment. It means that if the trained environment model can recover all the dynamics of the actual game, then the performance is good. Otherwise, the performance is worse. Then we have the following theorem.
16

---

Under review as a conference paper at ICLR 2023
Theorem 1. Assuming that the environment model is well on the offline dataset. the OEF- CFR/OEF-PSRO can converge to equilibrium strategy under the random dataset satisfying assump- tion 2 and cannot guarantee to converge under the expert dataset satisfying assumption I.
Proof. Since the environment model well-trained on the offline dataset, the environment model can fully represent the information of the offline dataset. If the random dataset is the offline dataset, the game defined by the trained environment model the same as the actual game. The reason is that every state transition is covered by the random dataset according assumption 2. Then the strategy learned by OEF- CER/OCFREEEEEEEE PSRO is the approximate equilibrium strategy of the actual game due to the convergence property of CFR/PSRO. Therefore, the DEF-CFR/OEF-PSRE can converge to an equilibrium strategy under the random dataset satisfying assumption 2.
If the offline dataset is the expert dataset, then the dataset only covers these state transitions related to the NE strategy according to assumption 1. Therefore, the state transition of the actual game may not be covered by the expert dataset. The environment model trained based on the expert dataset would produce different transition information on these states not shown in the dataset compared with the actual game. It would cause gap between the trained environment model and the actual game. Although DEF-CER/OEF-PPE PFRO can learn an approximate equilibrium strategy of the game defined by the environment model, there is no guarantee that the learned strategy is the equilibrium strategy of the actual game.
Theorem 1 is consistent with the conclusion in Cui Du 2022 that dataset coverage satisfying assumption 1 is insufficient for NE identification, and dataset coverage satisfying assumption 2 is sufficient for NE identification. And our empirical results also verify this conclusion. The OFF- CER/OEF-PSRO performs best under the random dataset and worst under the expert dataset.
In this paper, to offset the drawback of the model-based algorithm under the expert dataset, we propose to combine the behavior cloning technique. From the introduction of the behavior cloning technique, we know that BC can mimic the behavior policy in the dataset. Therefore, we have the following theorem describing the power of the BC technique.
Theorem 2. Assuming that the behavior cloning policy is well-trained the offline dataset, the behavior cloning technique can get the equilibrium strategy under the expert dataset satisfying as- sumption 1, and cannot get the equilibrium strategy under the random dataset satisfying assumption
Proof. The assumption that the behavior cloning policy is well-trained on the offline dataset means that the behavior cloning policy can precisely mimic the behavior strategy used to generate the offline dataset. If the offline dataset is the expert dataset, according to assumption 1, the behavior strategy of the dataset is the NE strategy. Therefore, applying the behavior cloning algorithm on the expert dataset can get NE strategy.
If the offline dataset is the random dataset, according to the generation process of the random dataset and assumption 2, the behavior strategy of the random dataset is the random strategy. Therefore, the behavior cloning algorithm can only get a random strategy instead of the equilibrium strategy under the random dataset.
Our experimental results also show the same outcomes as Theorem 2. The performance of the behavior cloning technique mainly depends on the quality of the behavior strategy. The behavior cloning technique only performs well under the expert dataset. Based on the above two theorems, propose to combine two techniques, the model-based algorithm and behavior cloning algorithm, to get better results under these datasets with unknown behavior strategies.
Theorem 3. Under the assumptions in Theorem and 2, there exists a parameter a such that BC+MB can get the equilibrium strategy under either the random dataset satisfying assumption or the expert dataset satisfying assumption I.
Proof. In the BC+MB algorithm, the weight of the BC policy is represented by The weight of the MB policy is L-a. The a ranges from 0 to 1. When under the random dataset satisfying assumption 2, let equal 0. Then the policy of BC+MB would equal MB policy, i.e., the policy trained using
17

---

Under review as a conference paper at ICLR 2023
the model-based algorithm. According to Theorem the model-based algorithm (OEF- DEF-CCR//EEF PSRO) can converge to an equilibrium strategy under the random dataset satisfying assumption 2. Therefore, BC+MB can also converge to equilibrium strategy under the random dataset satisfying assumption 2.
When under the expert dataset satisfying assumption 1, let a equal to 1. Then the policy of BC+MB would be equal to BC policy, i.e, the policy trained by behavior cloning. Similarly, according to Theorem 2, BC+MB can get an equilibrium strategy in the expert dataset satisfying assumption 1.
Let's move to more general case in which the offline dataset is generated by a behavior strategy a. Then we have the following theorems under the general case.
Theorem 4. Assuming that the offline dataset Da generated by the behavior strategy covers
(st, a, S141), Vst. a E A(ss) and the environment model is well-trained on Da. the model-based algorithu (OEF-CH) SEFF-CCR/OEF--PSE even better than a.
converge to equilibrium strategy that performs equal
Proof. According to the proof of Theorem 1, since every state transition of the actual game is cov- ered by Dr,, the trained environment model would be the same as the actual game under the assump- tion that the environment model is well-trained on the offline dataset. Then according to Theorem 1, the model-based algorithm can converge to an equilibrium strategy. If sigma used to generate the dataset is not the equilibrium strategy, then the model-based algorithm can get better strategy (equilibrium strategy) than And if is an equilibrium strategy, then the strategy trained using model-based algorithm would perform equal to a.
Theorem 5. Assuming that the behavior cloning policy is well-trained on the offline dataset Do generated by the behavior strategy a, the performance of behavior cloning policy Te would be as good as the performance of a.
Proof. According to the assumption, behavior cloning can precisely mimic the behavior strategy in the offline dataset. Therefore, tee would be same Consequently, the performance of the would have the same performance as a.
Theorem 6. Assuming that the environment model and the behavior cloning policy are well-trained, under the offline dataset Do generated using BC+MB can get the strategy which is at least as good as a. If the offline dataset DD covers (St, a, S141), 48t, a E A(ss), BC+MB can get an equal or better strategy than
Proof. Following the proof of Theorem 3, let a equal 1. Then BC+MB would reduce to Then according to Theorem 5, the performance of BC policy is at least as good as a. Therefore, BC+MB can get strategy that is at least good as
In another extreme case in which D2 covers (s1, a, 8t41), Va,, a E A(x)), let a equal to 0. Then BC+MB would reduce to MB. Then according to Theorem 4, the MB policy performs equal or better than a. Therefore, in this case, BC+MB can get an equal or better strategy than a.
In conclusion, under the above assumptions, BC+MB can perform at least equal to the behavior strategy used to generate the offline dataset. The improvement over the behavior strategy mainly depends on the performance of the model-basee based algorithm under the offline dataset.
C VISUALIZATION OF DATASETS
In this section, we describe the visualization methods of the datasets. First, we plot the game tree. 7 an example of the game tree. Then, traverse the game tree using depth-first search (DFS) and index each leaf node according to the DFS results. Finally, we count the frequency of the leaf node in each dataset.
Figure X show the frequency of leaf node in datasets. We can find that in the random dataset, the frequency of leaf nodes is almost uniform, while in the expert dataset, the frequency distribution of
18

---

Under review as a conference paper at ICLR 2023
Figure 7: 2-player Kuhn poker
Lioiia lataue
Lesr siug Austent
Eide
Enerehay tackraal
00008
5.00
Leaf Node Lndox
Loaf Nodi Lodes
Leaf Node Node Indox
Leaf Node Lndex
(a) Kuhn Poker-2 Player (b) Kuhn Poker-3 Player (c) Kuhn Poker-4 Player
(d) Kuhn Poker-5 Player
Expert Bataset
6.0025
Expert Bataset
Expert Dotaset
0.023
Learning Dotaset
0.0030
Learning Dotaset
Learaing Dalasel
Frequency
Randont Datanet
0.0025
Randore Datanet
Prsquency
6,135
Randim Bataset
8.013
0.010
0.010
0.003
0.1005
0,000
6.0000
6.000
1000
2000
3000
4000 5000
0.0
0.2
0.4
0.0
1.0
50000
100000
150000
Leaf Node Index
Leaf Node Index
Leaf Node Index
(e) Ledue Poker-2 Player
(I) Leduc Poker-3 Player
(g) Liars Dice-2 Player
Figure 8: DataSet Visualization
Comnohater
Cumuiaativn
Tourt Dakcee Aasdica Evrket
Expar Dulaed
Expert Tokce
kandon (wisen
Naatic Faland
2
18
190
266 306
201
172
1824 7am
(a) Kuhn Poker-2 Player (b) Kuhn Poker-3 Player (c) Kuhn Poker-4 Player (d) Kuhn Poker-5 Player
Cumuuattiv Erequency
aaluulative Erequeacy
1.0
Aammlaative Frequeenyy
8.8
6.6
0.4
0.4
Learning Dataset
Leaming Datanet
0.
Eppri Dutses
Handers Dalase
0.0
Hander Delaset
1000
2000
3900
4050
5000
0.
0.2
94
08
0.8
1.0
37000 Sedeo 75460 tode0ozzazz
Index
Index
Leaf Node Index
(c) Leduc Poker-2 Player
(f) Leduc Poker-3 Player
Liars Dice-2 Player
Figure DataSet Visualization
leaf nodes is uneven. The distribution of the learning dataset is between the expert dataset and the random dataset. Figure shows the cumulative frequency of leaf nodes. These figures also exhibit the same result.
19

---

Under review as a conference paper at ICLR 2023
D IMPLEMENTATION DETAILS
Behavior Cloning. Behavior cloning (BC) is a method that mimics the behavior policy in the dataset. Behavior cloning technique is used frequently in Offline RL (Fujimoto & Gul (021). In the OEF setting, we also the BC technique to learn behavior cloning strategy of every player from the offline dataset. More specifically, we can use the imitation learning algorithm to train policy network o; parameterized by 0 for every player i to predict the strategy given any information set 1,. Only the information sets and actions data are needed when training the behavior cloning strategy. We employ the cross-entropy loss as the training loss, defined as
K Lbe E (1:a)))D(laa 0)) [B]]]]][[,,,,)- Eu,a)=nl Σ a- log(o,
where K is the number of actions. Figure shows the structure of the behavior cloning policy net- work. Because equilibrial strategies in most information sets are non-trivial probability distributions, we apply a softmax layer after the output layer to obtain the final mixed strategy.
I
neg Bund Suggpesd
uppao
Relu
Output layer
syyor
layer
Figure 10: Structure of Behavior Cloning policy network.
Model-based Method. Next, we introduce our offline model-based algorithms: OFF-PSRO and OFF-CFR, which are adaptions from two widely-used online equilibrium finding algorithms PSRO and Deep CFR, and OEF-JPSRO, which is an adaption from JPSRO. These three algorithms per- form on the well-trained environment model E. We first introduce the OEF-PSRO algorithm, and the whole flow is shown in Algorithm| 2 Firstly, we need the well-trained environment model E as input and initialize policy sets II for all players using random strategies. Then, need to esti- mate a meta-game matrix by computing expected utilities for each joint strategy profile π E II. In vanilla PSRO, to get the expected utility for æ, it needs to perform the strategy æ in the actual game simulator. However, the simulator is missing in the OEF setting. Therefore, we use the well-trained environment model E' to replace the game simulator to provide the information needed in the algo- rithm. Then we initialize meta-strategies using uniform strategy. Next, we need to compute the best response policy oracle for every player and add the best response policy oracle to their pol- icy sets. When training the best response policy oracle using DQN or other reinforcement learning algorithms, we sample the training data based on the environment model E. After that, we com- pute missing entries in the meta-game matrix and calculate veta-strategies for the meta-game, To calculate the meta-strategy a of the meta-game matrix, we can use the Nash solver or o-rank algo- rithm. Here, use the a-rank algorithm as the meta solver because multi-player games. Finally, we repeat the above process until satisfying the convergence condi- tions. Since the process of JPSRO is similar PSRO except for the best response computation and meta distribution solver, OEF-JPSRO is also similar to OEF-PSRO. We do not cover OFF-JPSRO in detail here.
algorithm needs to solve
Algorithm ssoows the process of OEF-CFR. It also needs the well-trained environment model E as input. We first initialize regret and strategy networks for every player and then initialize regret and strategy memories for every player. Then we need to update the regret network for every player. To do this, we can perform the traverse function to collect corresponding training data. The traverse function can be any sampling- basedd based CFR algorithm. Here, we use the external sampling algorithm. Note that we need to perform the traverse function on the game tree. OFF-CFR, the trained environment model can replace the game tree. Therefore, the trained environment model is the input of the traverse function. Algorithm 4 shows the process of the traverse function. In this traverse function, we collect the regret training data of the traveler, and the strategy training data of other players are also gathered. After performing the traverse function several times, the regret network is updated using the regret memory. We need to repeat the above processes iterations. Then the average strategy network for every player is trained based on its corresponding strategy memory. Finally, the trained average strategy networks are output the approximate NE strategy.
20

---

Under review as a conference paper at ICLR 2023
Algorithm 2: Offline Equilibrium Finding Policy-Space Response Oracles Trained environment model E;
Input:
Initial policy sets IT for all players;
Compute expected utilities l for each joint и E Il based on the environment model E;
3 Initialize mate-strategies o; UNIFORM(LI))
repeat
for player i [l.... nl do for best response episodes p E [O,.... []] do
Sample π-j ~ a-i:
Train best response oracle ni over p (m/4s m-1), which samples the environment model E;;
end
II, II, ( end
Compute missing entries in U from II based the environment model E;
Compute meta-strategy from U using o-rank algorithm;
until Meet convergence condition; Output: current solution strategy o; for player
Algorithm 3: Offline Equilibrium Finding- Deep Counterfactual Regret Minimization
Input: Trained environment model E;
Initialize regret network R(I, a pr.p) for every player p;
2 Initialize average strategy network S alpp,)) for every player p;
Initialize regret memory Mr and strategy memory M for every player p; to do for player p E [i, do for traverse episodes k E [1,.., K] do
for CFR Iteration
TRVERSE(O, p, pr 0x.pp.Mr.p Mn.-p. E); # use sample algorithm to traverse game tree and record regret and strategy end Train Or, from scratch based regret memory Mr
10
end
12
end
13
Train f. based on strategy memory Mx.p for every player p:
Output: 0x.p for every playerp p
E ADDITIONAL EXPERIMENTAL. RESULTS
In this part, we provide more experimental results. First. we provide the experimental results of the behavior cloning method and model-based method (OEF-CFR) based on hybrid datasets, and then the results of our OEF algorithm (BC+MC) are given. We also test the BC+MB on two-player Phantom Tic-Tac- Toe game using the learning dataset. Finally, we provide the setting of hyper- parameters used in our experiments.
Figure II shows the results of the behavior cloning technique on several multi-player poker games and one two-player Liar's Dice game. It shows that as the proportion of random datasets increases, the performance decreases.
consistent with the results of previous experiments. Therefore, the behavior cloning technique is inefficient for solving the OEF problem since can only perform well in the expert dataset.
The experimental results of the model-based algorithm (OEF-CFR) on these games are shown in Figure [2 Since the strategy learned by OEF-CFR is not joint strategy, we only use NashConv to measure how it is close NEs. We found that the performance of the MB method is not stable in these games but still shows a slight decrease tendency with the increase of the proportion of the random dataset. Since the performance of the MB method mainly depends the trained environ-
21

---

Under review as a conference paper at ICLR 2023
Algorithm 4: TRTEESSESS, p. Or.p, Oz, p. - Mr, E)-External Sampling Algorithm
if 8 is terminal state then
Get the utility (8(8) from environment model E:; return us)
else if is a chance state then
Sample an action a based on the probability (e(s), which is obtained from model E;
s' = (((s,a) a);
return TRAVERSE(S' -p Or.ps Dr..p..rs. M=.-p- F.)
else if P())=
then
+ s sip]; game state is formed by information sets of every player;
10
(I) < strategy of I computed using regret values R(I, a(0r.p) based on regret matching;
for a E A(s) do
12
= ())
u(a)= t TRAVERSE(s', Pr.p. -p. Mn. -p- E);
14
end
EBEA(S) (I,a)a(a): for a E A(8) do 16
15
Ug
17
r(1, a) - u(a) Uo: end
18
19
Insert the infoset and its action regret values (I,r(T) into regret memory Mr,s return
20
21
else
+- sipl;
23
(s) + strategy of computed using regret value R[I, all,,)) based on regret matching;
24
Insert the infoset and its strategy (I,o(s) (s)) into strategy memory Mz.-pi
25
Sample an action from the probability distribution (s);
26
E(s, a);
27
return TRAVERSE(S' Pp, Orgp 0x Ox.-puMap Ma, E);
28 end
ment model, indicates that in these games, the trained environment model is far from the actual game environment which is also the test game environment. Therefore, learning good enough environment model a big challenge these games with more uncertain factors.
Figure (3()) (3() show the experimental results of BC+MB on various games. We also test our OBF algorithm BC+MB in Phantom Tic-Tac- Tac-Toe game based on the learning dataset (Figure 13()). The
NashConv values in Phantom Tic-Tac-Toc are approximate results since the best response policy is trained using DQN, and the utilities are obtained by simulation. It shows that the BC+MB performs better than BC and MB, which implies that combination method can perform well in any game under any unknown dataset. The proper weights in the BC+MB algorithm under different datasets shown Figure 14
22

---

Under review as a conference paper at ICLR 2023
2.0
3.5
3.0
NashConv
1.5
NashCoav
2.5
NashConv
2.0
1.0
0.5
ICC 1000 Size 5000
1.0
5000
3000 Size 10000
0.3
10000
0.0
0.0
0.0
0.2
0.4
0.6
0.0
1.0
0.0
0.2
0.4
Proportion of Random Dataset
Proportion Random Dataset
Proportion of Random Dataset
(a) Kuhn Poker-3 Player
(b) Kuhn Poker-4 Player
(c) Kuhn Poker-5 Player
10
1.75
1.30
Nash Conv
12
1.00
10.
0.75
Data Size
BC-Blets 10000
Data Size 20000
BC-Data Size 20000
BC Data Sizee 50000
0.25
BC-Datt Size 30000
0.0
0.2
0.4
0.8
0.5
1.0
0.0
0.4
0.6
0,5
Proportion of Random Dataset
Proportion of Random Dataset.
(d) Ledue Poker-3 Player
Liar's Dice-2 Player
Figure 11: Experimental results for the BC method
OEF-CFF Data Size 1000
OEF-CER. Data Size 5900
OEF-CFR. Duta Size 5000
OEF-CIR Duta Size 3000
OLF-CEL Data Size 10000
14:
OEF-CER- Data Siae 10000
NashCouv
ORF-CIR: Dats Size 10000
NashCouv
orr-CIR Data Sime 20000
NashConv
OFF-CER- Data Size 20080
0.22
0.4
01.6
0.5
1.0
Proportion of Random Dataset
Proportion Random Dataset
Proportion Random Dataset
(a) Kuhn Poker-3 Player
(b) Kuhn Poker-4 Player
(c) Kuhn Poker-5 Player
15
1.8
Size
NashConv
1.6
13
12
OLR-PSHO
10000
OEF-PSRO Data 20000
OEF-PSRO Date Size 50000
0.9
0.2
0.4
0.5
0.3
1.0
0.0
0.2
0.4 0.6
0.8
Proportion of Random Dataset
Proportion of Random Dataset
(d) Ledue Poker-3 Player
Liar's Dice-2 Player
Figure 12: Experimental results for the MB method
23

---

Under review as a conference paper at ICLR 2023
NC- MIB Bela far 3000
HOME ULA4 Mee 1368 1883
BOHOR Ber 6e-1883 1388
NachCann
Dake
NathCann
Raio 20000
fut
44
60
ax
Proportion
Proportion
(a) Kuhn Poker-3 Player
(b) Kuhn Poker-3 Player
(c) Kuhn Poker-4 Player (d) Kuhn Poker-4 Player
Bhn den Heree
tues Reitesss
Naahton
MC tid Man 1006
Date 1i 20083
Proportion Random Dalaset
o' (f) Kuhn Poker-5 Player (g) Ledue Poker-3 Player (h) Ledue Poker-3 Player
02
1o
Preportion Random Dataset
OLD
Randem
(c) Kuhn Poker-5 Player
Results Learning Dataset
2.00
Nosh
NashConv
1.5
1.00
0.75
BC Sian 18080
BC-MB Size
10000
0.30
BC- 20080
MB--att Stzn 18008
M0B-Bata Stze 20000
0.2
0.6
8.
0.0
022
05
0.0
5000
10000
20000
Proportion of Random Dataset
Proportion Random Dataset
Size of Dataset
(i) Liar's Dice-2 Player
Liar's Dice-2 Player
Phantom ttt-2 Player
Figure 13: Experimental results for the benchmark algorithm BC+MB
1.2
1.0
Weight of BC (e)
0.6
Data Size 1000
Welght
0.4-
Data Size 5000
Weight
0.4
0.2
10000 -0.2
20090
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
8-1
0.6
0.0
1.0
0.9
0.2
0.1
0,5
0n
1.01
Proportion of Random Dataset
Proportion of Random Dataset
Proportion of Random Dataset
(a) Kuhn-3 Player
Kuhn-4 Player
(c) Kuhn-5 Player
1.0-
Data Size 10000
Weight of BC (a)
Data Size 20000
Weight of BC (e)
0.8
0.6
8.4
22
Data Size 10809
Data Size 20000
0.8
1.0
6.4 0.6
Proportion Random Dataset
Proportion Random Dataset
(d) Leduc-3 Player
(e) Liar's Dice
Figure 14: Experimental Results for Proper Weight
24

---

Under review as a conference paper at ICLR 2023
Ablation Study. To figure out the influence of hyperparameters, conduct some ablation exper- iments on two-player Kuhn poker and Ledue poker games. We consider different model structures with various hidden layers. Specifically, for the 2-Player Kuhn poker game, we different envi- ronment models with 8, 16, 32, and 64 hidden layers. For the 2-Player Leduc poker game, which more complicated game, the numbers of hidden layers for different models are 32, 64, and 128. Besides, we train the environment models for different epochs to evaluate the robustness of our approach. Figures 15 16 show these ablation results. We can find that the hidden layer size and the number of train epochs have little effect on the performance of the BC algorithm. These results further verify that the performance of the BC algorithm mainly depends on the quality of the dataset. As we know that the performance of the model-based algorithm mainly depends on the trained en- vironment model. Since the size of the hidden layer and the number of train epochs will influence the training phase of the environment model, the size of the hidden layer and the number of train epochs have slight influence on the performance of the model-based algorithm. As long as the size of the hidden layer and the number of train epochs guarantee that the model is well-trained, the performance of the model-base -base algorithm will not be affected.
ORL CRL masee Caree
NuvaCeey
Hiliva Eayerit
BC Widd Lowe 13k
Proportion of Random Dabasn
Proportion of Randem Dataset
Proportien Random Datusnt
Proportion Random Dataset
(a) Kuhn-2 Player
(b) Kuhn-2 Player
(c) Leduc-2 Player
(d) Leduc-2 Player
Figure 15: Ablation results for different hidden layer size
OEE-FR- Unis Epech 500 OEC-FE- Taia Opech 2oce
OUE ORR- Thaie Eaach 1899 our cen- truto Earc teeoo
L30
SaaiCuu
L21
KC Tralk Tradh 300 Trals Toach
Thes Fouth 1830
Fowet 1930
C4 Propottion Dutuset
15
Propoction
Propottion Randomn
Proportion Random
(a) Kuhn-2 Player
(b) Kuhn-2 Player
(c) Leduc-2 Player
(d) Ledue-2 Player
Figure 16: Ablation results for different train epoch
25

---

Under review as a conference paper at ICLR 2023
Parameter Setting. We list the parameters used to train the behavior cloning policy and environ- ment model for all games used in our experiments in Table and Table
Table 1: Parameters for Behavior Cloning algorithm
Games
Data size
Hidden layer
Batch size
Train epoch
2-paaerr Kuhn poker
500
32
32
1000
2-player Kuhn poker
1000
32
32
2000
2-player Kuhn poker
5000
32
32
2000
3-player Kuhn poker
1000
32
32
5000
3-player Kuhn poker
5000
32
32
5000
3-player Kuhn poker 10000
64
128
5000
4 player Kuhn poker
5000
64
64
5000
4-pyyrr Kuhn poker 10000
64
128
5000
player Kuhn poker 20000
64
128
5000
5-player Kuhn poker
5000
64
64
5000
5-player Kuhn poker
10000
64
128
5000
5-player Kuhn poker 20000
64
128
5000
2-player Ledue poker
10000
128
128
10000
2- 2-plaeer Ledue poker
20000
128
128
10000
2-player Leduc poker 50000
128
128
10000
3- 3-player Ledue poker
10000
128
128
10000
3- 3-player Ledue poker
20000
128
128
10000
3- 3-player Leduc poker
50000
128
128
10000
Liar's Dice
10000
64
64
5000
Liar's Dice
20000
64
128
5000
Liar's Dice
50000
64
128
5000
Phantom Tic-Tac- Tac-Toe
5000
128
128
5000
Phantom Tic- Tac-Toe
10000
128
128
5000
Phantom Tic-Tac-Toe
20000
128
128
5000
26

---

Under review as a conference paper at ICLR 2023
Table 2:
Parameters for training Environment Model
Games
Data size
Hidden layer
Batch size
Train epoch
2- plaayer Kuhn poker
500
32
32
1000
player Kuhn poker
1000
32
32
2000
2- 2-player Kuhn poker
5000
32
32
2000
3-player Kuhn poker
1000
32
32
2000
3-player Kuhn poker
5000
32
32
5000
3-player Kuhn poker 10000
64
128
5000
4-player Kuhn poker 5000
64
64
5000
4-player Kuhn poker 10000
64
128
5000
4 player Kuhn poker 20000
64
128
5000
5-player Kuhn poker
5000
64
64
5000
5 5-player Kuhn poker
10000
64
128
5000
5-player Kuhn poker 20000
64
128
5000
2-player Leduc poker
5000
64
64
5000
2- 2-player Ledue poker
10000
64
64
5000
2- 2-player Ledue poker 20000
128
128
10000
3 3-player Leduc poker
10000
128
128
10000
3-player Ledue poker
20000
128
128
10000
3- 3-player Leduc poker
50000
128
128
10000
Liar's Dice
10000
64
64
5000
Liar's Dice
20000
64
128
5000
Liar's Dice
50000
64
128
5000
Phantom Tic-Tac-Toe
5000
128
128
5000
Phantom Tic-Tac Tac-Toe
10000
128
128
5000
Phantom Tic-Tac-Tos
20000
128
128
5000
27


Reviews:
[{"review_id": "zQyIuakgLX", "reviewer": "Reviewer_ZPQh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "", "summary_of_the_paper": "The paper studies offline multi-agent reinforcement learning. The authors propose a framework for offline equilibrium finding, where the learner first trains a model $E$ by the offline dataset, and then compute an equilibrium using the model and some proper online algorithms. The authors also consider to set the behavior cloning policy as the regularization for the online equilibrium.", "summary_of_the_review": "Overall I think this paper is incremental, and the motivation is not clear. I consider to reject this paper.", "strength_and_weaknesses": "Strength: The paper focuses on offline multi-agent reinforcement learning, which is a very challenging problem in related fields. The authors consider model-based framework for finding the equilibrium, which is even more challenging, since estimating the model in multi-agent learning problems is essentially hard.\n\n\n\nWeaknesses:  1) The motivation is not clear. In the example in Section 2, by watching the replays of the other player $B$, the learner $A$ could only find the best response to $B$'s policy, instead of an equilibrium. I am confused that how to connect this scenario with equilibrium finding. 2) The contribution in algorithm design is incremental, where no useful insights about multi-agent learning is provided.  3) It is unfair to compare the proposed algorithm with the offline RL algorithms for single agent, since the target of those algorithms is not to find an equilibrium. 4) This paper is lack of theorectical insights. It would be much better by providing the sample complexity analysis.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TbQOXYF2dPi", "reviewer": "Reviewer_APEF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "This paper looks at the problem of applying offline RL to learning solutions to games. The complication that arises is that the demonstration data may not exhibit a solution to the game, and as we're offline we cannot collect new equilibrium demonstrations. This question that is investigated in this paper is exactly this: how can one learn an equilibrium in an offline fashion. They propose an algorithmic solution that is a simple two-step approach: learn a game-model, and apply a game-solving algorithm on the game-model as an approximation solution to the underlying game. They empirically demonstration their approach on several small games. ", "summary_of_the_review": "This work demonstrated that learned game-models can be solved as a proxy for the true game in an offline setting (wrt. the true game). The paper is framed as formally introducing a new problem (ie., offline equilibrium finding), but I found this component of the exposition absent. Moreover, the empirical results are all in an exceptionally idealized setting for the method: the equilibrium state-action is likely covered by any arbitrarily bad demonstration profile. Despite these concerns, the work contains a straightforward/trivial (in a good way) approach to a reasonable problem and provides a nice set of preliminary experiments in the space. \n\nIn its current state due to unsupported/incorrect claims and misaligned problem framing I would not advocate for its publication, but with moderate revisions to the text believe it could be ready.", "strength_and_weaknesses": "**Strengths**\n - Their approach is intuitively simple, in a good way, and sensible for solving a real problem. \n - The authors include a nice set of diverse baselines to understand the limitations of most current approaches including BC and offline model-based RL, alongside combinations of them. \n - The authors perform a nice sensitivy analysis to the quality of the offline data across all methods. \n - The problem is introduced and framed in English well such that a reader from any of the diverse positions of background could understand well the main point they're investigating. Despite this, I would recommend condensing this as it resulted in less technical details from being included in the main body of the paper. \n\n**Weaknesses**\n - I do not believe they've correctly positioned this paper within the literature. This work is an example of an EGTA algorithm sat at the extrema of the algorithmic design space: a high-fidelity game-model is constructed alongside allowing no further queries to the simulator (that is exact). The authors claim that EGTA is precluded from being used in this case, but at the core of their work is a game-model that's being solved through game-theory, which is precisely EGTA. I am further skeptical of the claim \"offline RL is not enough since it can only learn the best strategy for one agent independently\", could the authors explain or cite evidence as to why this must be true? Moreover, I'm surprised at the lack of discussion on behavioural cloning. If the demonstration data is exactly displaying an equilibrium then there is no issue; whereas, the more off-equilibrium the demonstration data, the more this approach matters alongside the difficulty of the correction.\n - The abstract claims a formal introduction to the proposed problem of offline equilibrium finding; however, the text contains only an informal one-sentence definition. The paper could be improved by formally defining the problem and characterizing interesting properties or questions within the space (e.g., approximation errors, selecting a single equilibrium when many exist, etc.).\n - The success of their method (game-model, then solving) strongly depends on the state-action space covered during demonstration versus the space covered by the desired solution. This is because the game-model cannot reasonably exhibit entirely novel transitions. I raise this point because in the games demonstrated in this paper it is possible that the state-action space is exceptionally well covered. I would be curious to know how this approach works outside of this domain and wonder if the authors have investigated this at all.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Oe29tyf5gVw", "reviewer": "Reviewer_XR74", "summary": "", "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": "", "summary_of_the_paper": "The authors introduced a new problem called offline equilibrium finding and designed a model-based method to apply any online equilibrium finding algorithm to the OEF setting.", "summary_of_the_review": "Considering the high quality and novelty of the paper, I would recommend the acceptance of this work.\n\n----------\nI have read the authors' responses and would like to keep the same score.", "strength_and_weaknesses": "Strength\n1. The problem is relatively new and the method is novel.\n2. The authors gave a thorough literature review of the equilibrium-finding algorithms and give a sensible discussion on why introducing the offline equilibrium finding. \n3. The experimental results are also extensive.\n\nWeakness\n1. The proposed method is model-based but the environment model is hard to learn. Specifically, the dynamics of the game environment may be time-variant and stochastic and cannot easily be characterized by a DNN proposed by the authors. It is worth exploring how the OEM performs when the model is perfectly known in simulation and how its performance will be degraded when the model is not well learned.\n2. In Fig 4(h), why does the NashConv not exist for MB when the number of players is 2 and 3 and the same issue for BC when the number of plays is 4 and 5? Similar question for MB when the number of players is 3 in Fig 5(h).\n3. The parameters used in the OEM are only briefly discussed in the Appendix (Tables 1 for BC and 2 for the model). It will be helpful to conduct some ablation study on these parameters and demonstrate how the performance is affected by these parameters.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8qtskp9HYGL", "reviewer": "Reviewer_2VY7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "The authors propose offline equilibrium finding, which can essentially be summarized as a method of equilibrium finding in unknown games using only a training set of gameplay--by first building an approximate model of the game from the training set and then computing an equilibrium of the model. Experiments are run to demonstrate the efficacy of the method.", "summary_of_the_review": "An interesting concept, but I'm not sure of novelty, as the main ideas of the paper are fairly natural and not analyzed very deeply. ", "strength_and_weaknesses": "I find the premise of the paper interesting--offline RL is of obvious interest, and applying it to games causes additional issues as the authors rightfully point out. For example, the fact that independent offline RL (e.g., the tested algorithms MOPO and BAIL) fails in this setting is fairly clear: given strategy profile $\\sigma$ in an extensive-form game, even if each player $i$ builds a perfect environment (i.e., game + opponent) model and independently computes a perfect strategy in that model (i.e., a best response $\\sigma_i'$ to $\\sigma_{-i}$), it would be quite surprising if somehow the profile $\\sigma'$ turned out to be close to equilibrium. Thus, other methods are required.\n\nMy main issue is that the paper is very light on theory and new ideas. I concede that to some extent this is my own theoretical background seeping through, but in any case I found the technical section of the paper to be straightforward. It seems to boil down to: \"to solve a game you don't know, first approximate the game and then solve the approximated game\", applying known techniques in turn to each of the two subproblems.\n\nThe experimental section of the paper is fairly robust, but basically verifies what one would expect from the methods tested, and to me contained no surprises. I would also like to see larger experiments--perhaps in a game large enough that directly computing an equilibrium is hard, and in which the BC+MB method outperforms pure BC. \n\nQuestions:\n\n1. Why should we expect a Fourier transform of node frequencies to be illuminating? Are the nodes ordered in some meaningful way such that, say, the \"amplitude at frequency 2\" is a meaningful thing?\n\n1. I did not understand Figures 4(h) and 5(h). In particular, what's a \"player\" for those figures? Aren't Kuhn and Leduc both two-player games? \n\n1. In the experiments in Section 5.4, how was a Nash equilibrium computed for the purpose of collecting the OEF dataset? The games seem too large to use an actual algorithm that is guaranteed to compute general-sum Nash.\n\n1. The experiments in the paper are all with approximate equilibrium finders (namely, based on deep learning), despite the fact that some of the games are small enough that better equilibrium finders (e.g., tabular CFR+) could have been used instead. Given this, to what extent are the experimental observations dependent on the quality of the equilibrium found vs. the quality of the approximated game model? For example, the NashConv values in (2p) Leduc poker seem rather large, and my first guess would be that this is due to equilibrium finder failure--Leduc poker is a fairly simple game, so I would guess that 20000 data points is plenty to build a decent game model.\n\n1. How is $\\alpha$ selected for BC+MB? In particular, you state that $\\alpha$ is selected by \"testing the final policies in a real game to get the best final policy\"--against what opponent(s) were the policies optimized? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject