The Advantage Regret-Matching Actor-Critic
Authors: Audrunas Gruslys
Marc Lanctot
Remi Munos
Finbarr Timbers
Martin Schmid
Julien Perolet
Dustin Morrill
Vinicius Zambaldi
Jean-Baptiste Lespiau
John Schultz
Mohammad Gheshlaghi Azar
Michael Bowling
Karl Tuyls
Venue:  (2021)
Keywords: Nash Equilibrium
Games
CFR

Abstract: Regret minimization has played a key role in online learning, equilibrium computation in games, and reinforcement learning (RL). In this paper, we describe a general model-free RL method for no-regret learning based on repeated reconsideration of past behavior: Advantage Regret-Matching Actor-Critic (ARMAC). Rather than saving past state-action data, ARMAC saves a buffer of past policies, replaying through them to reconstruct hindsight assessments of past behavior. These retrospective value estimates are used to predict conditional advantages which, combined with regret matching, produces a new policy. In particular, ARMAC learns from sampled trajectories in a centralized training setting, without requiring the application of importance sampling commonly used in Monte Carlo counterfactual regret (CFR) minimization; hence, it does not suffer from excessive variance in large environments. In the single-agent setting, ARMAC shows an interesting form of exploration by keeping past policies intact. In the multiagent setting, ARMAC in self-play approaches Nash equilibria on some partially-observable zero-sum benchmarks. We provide exploitability estimates in the significantly larger game of betting-abstracted no-limit Texas Hold'em.

Under review as a conference paper at ICLR 2021
THE ADVANTAGE REGRET-MATCHING ACTOR- CRITIC
A Anonymous authors Paper under double-blind review
ABSTRACT
Regret minimization has played key role in online learning, equilibrium computation in games, and reinforcement learning (RL). In this paper, we describe a general model-free RL method for no-regret learning based repeated reconsideration of past behavior: Advantage Regret-Matching Actor-Critic (ARMAC). Rather than saving past state-action data, AR- MAC saves buffer of past policies, replaying through them to reconstruct hindsight assessments past behavior. These retrospective value estimates used to predict conditional advantages which, combined with regret matching, produces a new policy. In particular, ARMAC learns from sam- pled trajectories in & centralized training setting, without requiring the application of importance sampling commonly used in Monte Carlo counter- factual regret (CFR) minimization; hence, it does not suffer from excessive variance in large environments. In the single-agent setting, ARMAC shows an interesting form of exploration by keeping past policies intact. In the multiagent. setting, ARMAC in self-play approaches Nash equilibria on some partiall-obbeervable zero-sum benchmarks. We provide exploitability estimates in the significantly larger game of betting- abstracted no- no-limit Texas Hold'en em.
INTRODUCTION
The notion of regret is key concept in the design of many drcision-making algorithms. Regret minimization drives most bandit algorithms, is often used as a metric for performance of reinforcement learning (RI) algorithms, and for learning in games (3). When used in algorithm design, the common application is to accumulate values and/on /or/rr regrets and derive new policies based on these accumulated values. One particular approach, counterfactual regret (CFR) minimization (35) has been the core algorithm behind super-human play in Computer Poker research
CFR computes an approximate Nash equilibrium by having players minimize regret in self-play, producing an average strategy that is guaranteed to converge to an optimal solution in two-player zero-sum games and single agent games.
25
We investigate the problem of generalizing these regret minimization algorithms state spaces in the sequential setting using end-to-ond function approximators, such as deep networks. There have been several approaches that try to predict the regret, otherwise, simulate the regret mininization: Regression CFR (RCFR) 3.], advantage regret minimization (17), regret-based policy gradients (30), Deep Counterfactual Regret minimization 5 and Double Neural CFR (22). All of these approaches have focused either dingleagentt problem exclusively, some have used expert features, while
large
on the multiagent others tree search to scale. Another common approach is based on fictitious play (15) [6]] 21 24), a simple iterative self-play algorithm based on best response. A common technique is to use reservoir sampling to maintain a buffer that represents uniform sample over past data, which is used to train a classifier representing the average policy. In Neural Fictitious Self-Play (NFSP), this produced competitive policies in limit Texas Hold'em (6 and in Deep CFR this method was shown to approach an approximate equilibrium in a large subgame of Hold's em poker. A generalization of fictitious play, policy-space response oracles (PSRO) (2D), stores past policies and a meta-distribution over them, replaying policies against other policies, incrementally adding best responses to the set, which be

---

Under review as a conference paper at ICLR 2021
seen as population-base learning approach where the individuals are the policies and the distribution is modified based on fitness. This approach only requires simulation of the policies and aggregating data; result, it was able to scale to very large real-time strategy game (33) In this paper, we describe an approximate form of CFR in a training regime that we call retrospective policy improvement. Similar to PSRO, our method stores past policies. However, it does not store meta-distributions or reward tables, nor do the policies have to be approximate best responses, which can be costly to compute or learn. Instead, the policics are snapshots of those used in the past, which are retrospectively replayed to predict a conditional advantage, which used in a regret matching algorithm produces the same policy CFR would do. In the single-agent setting, ARMAC is related to POLITEX (I), (14) and it predicts average quantílies rather than explicitly summing over all the experts to obtain the policy. In the multiagent setting, it is a sample-based model-free variant of RCFR with one important property: it uses trajectory samples to estimate quantities without reguiring importance sampling as in standard Monte Carlo CFR (20), hence it does not suffer from excessive variance in large environments. This is achieved by using critics (value estimates) of past policies that trained off-policy using standard policy evaluation techniques. In particular, we introduce a novel training regime that estimates conditional advantage (s a); which is the cumulative counterfactual regret R,(s,a, a), scaled by factor (s)) that depends on the information state s only; hence, using gegret-matching over this quantity yields the policy that CFR would compute when applying regret- gegret-matching to the same (unscaled) regret values. By doing this entirely from sampled trajectorics, the algorithm is model-free and can be done using any black-box simulator of the environment; hence, ARMAC inherits the scaling potential of PSRO without requiring a best-response training regime, driven instead by regret minimization.
except. that. it is based on regret-
Problem Statement. CFR is tabular algorithm that enumerates the entire state space, and has scaled to large games through domain-specific (hand-crafted) state space reductions. The problem is to define a model-free variant of CFR using only sampled trajectories and general (domain-indeeendenn) independent) generalization via functional approximation, without the use of importance sampling commonly used in Monte Carlo CFR, as it can cause excessive variance in large domains.
2 BACKGROUND
In this section, we describe the necessary terminology. Since we want to include the (partially- observable) multiagent case and we build on algorithms from regret minimization we use extensive-form games notations (29.. A single-player game represents the single-agent case where histories are aggregated appropriately based on the Markov property.
A game is a tuple (W.A, H, u, r), where N = 21, ... n) is the set of players. By convention we use i N to refer to a player, and -i for the other players (W- (1)). There is a special player e called chance (or nature) that plays with fixed stochastic strategy (chance's ' fixed strategy determines the transition function). A is a finite set of actions. Every game starts in an initial state, and players sequentially take actions leading to histories of actions E H. Terminal histories, = E Z C H, are those which end the episode. The utility function (2) denotes the player i's return over episode 2. The set of states S is partition of H. where histories are grouped into information states s = (h, h'..... such that the player to play at 8, 7(8), cannot. distinguish among the possible histories (world states) due to private information only known by other players Let AXX) represent all distributions over X: each player's (agent's) goal is learn a policy म. : S + A(A), where S, = {s E S, Ts)) = i}. For some state s, we denote A(s) C A as the legal actions at state s, and all valid state policies x(s) assign probability to illegal actions a & A(s).
We now show a diagram to illustrate the key ideas. Kuhn poker, shown in Figure is a poker game with 3-card deck: Jack (J), Queen (Q), and King (K). Each player antes a single chip and has one more chip to bet with, then gets a single priavte card at random and one is left. face down, and players proceed to bet (b) or pass (p). Initially the game
Information state is the belief about the world that given player can infer based on her limited observations and may correspond to many possible histories (world states)
2

---

Under review as a conference paper at ICLR 2021
starts in the empty history hu 0 where actions have been taken, and it is chance's turn to play. Suppose chance samples, according to a fixed distribution, one of its six actions, which corresponding to of the size-2 permutations of deals (one card to each player). For example, suppose outcome 1Q2J is sampled, corresponding to the first player getting the queen and second player getting the jack. This would correspond to new history h = (192J). Label the information state corresponding to this history as depicted by the grey joined circles: h' = (1Q2K). At this information state s = {h, it the fist player's turn (T(s) = 1) and it includes every history consistent with their information (namely, that they were dealt the jack).
1:K 2J
1:K
1:023
1:Q 2:K
1:K2:0
bett
passa
bot
peet
bat
pass
Pldd
ber
paess
2
call
call
Figure 1: A part of Kuhn poker. Terminal utilities shown for the first player.
The legal actions are now A(s) {p,by b). Suppose the first player chooses p and the second player chooses h, then the history is part of 8', the second information state shown in the figure. Finally, suppose the first player chooses to bet (call), then the first player would win gaining 2 chips since they have the higher ranking card. Each player i's goal is to compute ma that achieves maximal reward in expectation, where the expectation is taken over all players' policies, even though player i controls only their own policy. Hence, idcally, the player would learn a safe policy that guarantees the best worst-case scenario.
Let denote a joint policy. Define the state-value vra(s)) as the expected (undiscounted) return for player given that state s reached and all players follow и. Let yr, be defined similarly except also conditioned player r(s) taking action a at Formally, (s, E(.,)Ez())) 77" (h|s)))" (h, 22), where Z(s) are all terminal histories paired with their (h)
prefixes that pass through 8, 17 (h|s) = ()) where (s) - 17" (h',, and v7" (h, 2) is the product of probabilities of each action taken by the players' policies along h to The state- action values (x, a) are defined analogously. Standard value-based RL algorithms estimate these quantities for policy evaluation. Regret minimization in vero-sum games uses different notion value, the counterfactual value: (s) = -(h,))e((s) (h)m" (h, (2), where (h) is the product of opponents policy probabilities along h. We also write ny (h) the product of player i's own probabilities along h. Under the standard assumption of perfect recall, we have that for any h, h' n7. (h) (h"). Thus counterfactual values are formally
(=)(
related to the standard values (30): Us,((s) = )_, where 3_,(T, 8) = Σnex (h). Also, (s, a) is defined similarly except over histories (ha, 2) Z(s), where ha is history h concatenated with action a.
Counterfactual regret minimization (CFR) is tabular policy iteration algorithm that has facilitated many advances in Poker AI (5). On each iteration t, CFR computes counterfactual values (8, and of (s) for each state and action E A(s) and the
3

---

Under review as a conference paper at ICLR 2021
regret of not choosing action (or equivalently the advantage of choosing action at state s, (sss = Ce (s, a) una (s). CFR tracks the cumulative regrets for each state and action,
R (*, Σi= (8, a). Define (x)+ max(0, 2);; regret-malcchnn then updates the policy
of each action A(s) follows 14h
(etit(s))) Eoca(o) 1 (s,b)
if EEEA()) RT (s,
I 21+1 (s. = NORMALIZEDRELU(R s,,))
otherwise
[ta]]
(1) In two-player zero-sum games, the mixture policy x" converges to the set of Nash equilibria. as 7 00.
Traditional (off-policy) Monte Carlo CFR (MCCFR) a generic family of sampling vari- ants (20). In outcome sampling MCCFR, behavior policy μi is used by player i, while players -i use n-i a trajectory p ~ (Mi, T-;) )) sampled, and the sampled counterfactual value is computed:
(s, = ni ((,,m-)))))
(uin- (i 2));())
(2)
if ()) E or 0 otherwise. (s, a p) is an unbiased estim. of (s.aa
20 Lemma 1).
However, since these quantities are divided by furt (2),, the product of player i's probabil- ities, (i) there can be significant variance introduced by sampling, especially in problems involving long sequences of decisions, and (ii) the ranges of the ey can vary wildly (and unboundedly if the exploration policy is insufficiently mixed) over iterations and states, which could make approximating the values in a general way particularly challenging (34). Doep CFR and Double Ncural CFR are successful large-scale implementations of CFR with function approximation, and they get around this variance issue by using external sampling or a robust sampling technique, both which require a perfect game model and enumeration of the tree. This is unfeasible in very large environments trajectories are generated from beginning to the end without having access to a generative model which could be used to generate transitions from any state.
in the RL setting where full
2.1 EQUILIBRIA, EXPLOITABILITY, AND NASHCONV
In two-player zero-sum games (and, trivially, single-agent games) a Nash equilibrium policy is optimal because it maximizes a player's worst-case payoff (2 Success in Poker AI, leading to super-human ability, has largely been driven by computing approximate equilibria and playing the strategies against humans.
A Nash equilibrium is a joint policy x² (mi. m²) such that no player has incen- tive to deviate from their respective policy because there is no policy that can achieve higher utility against the opponent's policy. A best response for player i is by(m=x) argmax,; ue(T[, --)). Finally define player i's incentive to deviate (to a best response) as (,())) uz (b)((T)))) x-1) uz(T)) Then, æ is a Nash equilibrium if and only if deviating to best response does not raise a player's 's utility:
Vi, (T) =.
Here, the zero on the right-hand side represents not having any incentive to deviale. However, how about if there is small amount of incentive? The definition naturally extends to the approximate case where the right-hand size non-zero. An empirical metric to compute how far an aribtrary policy is to Nash equilibrium is then the sum over players:
NASHCONV(T) Σ (((T))
Note that the maximal value for NashConv is twice the utility range (this would occur if each player uses policy achieving the minimum utility, and there exists a best response which gets the maximum utility). In the poker literature there is commonly metric called
4

---

Under review as a conference paper at ICLR 2021
exploitability which computes the average rather than the sum: EXPLOITABILITY(()) E.4(()
2
These metrics measure the empirical distance equilibrium over time leading to assessment of an algorithm's convergence rate in practice.
3 THE ADVANTAGE REGRET-MATCHING ACTOR-CRITIC
ARMAC is a model-free RL al- gorithm motivated by CFR. Like algorithms in the CFR framework, ARMAC uses centralized train- ing setup and operates in epochs that correspond to CFR iterations. Like RCFR, ARMAC uses func- tion approximation to generale policies. ARMAC was designed so that as the number of sam- ples per epoch increases and the expressiveness of the function ap- proximator approaches lookup ta- ble, the generated sequence of poli- cies approaches that of CFR. In- stead of accumulating cumulative regrets- which is problematic for neural network- the algorithm learns a conditional advantage es- timate W(s, a) by regression to- ward a history-dependent advan- tage A(h, a), for h E 8, and uses to derive the next set of joint policies that CFR would produce. Indeed we show that W(s, a) is an estimate of the cumulative regret R(s,a) a) up to a multiplicative fac- which function of the infor- mation state s only, and thus can- cols out during the regret-matchin step. ARMAC is Monte Carlo algorithm in the same sense as MC- CFR: value estimates are trained from full episodes. uses off-policy learning for training the value esti- mates (i.e. critics), which we show is sufficient to derive W. However, contrary to MCCFR, does not use importance sampling. ARMAC is summarizod in Algorithm
Algorithm 1: Advantage Regret-Matchiing Actor-Critic
input initial set of parameters 0", num. players n Set initial learning player i <- for epoch E 1,2...... do reset t
Let r'(s) NORMALIZEDREIU(WW (s))
Let ug. (h) = EMEA(N) T' (h, a) (h, a)
Let μ be behavior policy for player i for episode k {l...., {act) do
i + (i+ mod
Sample j UNIF({O,1,... .t-
13)
Sample trajectory (Mi, xi,)
let d (i, (ur(p))ieN) for history P where player acts do let be the state containing h let F= (Yos (h,a') ug (h)) let be the action that was taken in p append (h, s, a, F, (s)) to end add to D
end for learning step k fl,..., Kiearn do Sample a random episode/balie batch d ~ UNIF(D): for history and corresponding state (h,8) E d do
Use TB(A) to train critic qør (h, a) If (()) train Wg. to predict A(h, a) If (()) E -i: train Ros to predict of r'(s) end end Save 0¹ for future retrospective replays; 0h+1 0¹
end
ARMAC runs over multiple epochs and produces a joint policies x(+1 at the end of each epoch. Each epoch starts with an emply data set. D and simulates a variety of joint policies executing multiple training iterations of relevant function approximators. ARMAC trains several estimators which can be either heads on the same neural network, or separate neural networks. The first one estimate the history-action values a a) =
Σ EvEz(ha) n0d (),))),(2) This estimator can be trained all previous data by using
Inn practice, rather than using h as input to our approximators, we use a concatenation of all players' observations, i.e. encoding of the augmented information states or action observation histories @ 18). In some games this is sufficient to recover full history. In others there is hidden state from all players, we can consider any chance event to be delayed until the first observation
5

---

Under review as a conference paper at ICLR 2021
any off- off-policy policy evaluation algorithm from experiences stored in replay memory (we use Tree- (rec-Backup(A) (26)). If trained until zero error, this quantity would produce the same history value estimates as recursive CFR computes in its tree pass. Secondly, the algorithm also trains a state-action network (1, a) that estimates the expected advantage A M a) = 9u (h, (h))a(h) conditioned on h when following some mixture policy 2² (which will be preciscly defined in Scction B). It happens that (T a) is estimate of the cumulative regret (t's,, a) multiplied by a (non-negative) function which depends on the information stale only, thus does not impact the policy improvement step by regret-matchingg (see Lemma 1 Once Wi(s, a) is trained, the next joint policy x'+ a) can be produced by normalizing the positive part as in Eq. [ After each training epoch the joint policy x' is saved into a past policy reservoir, as it will have to be loaded and played during future epochs. Lastly, an average policy head #² is also trained via classífication loss to predict the policy n" over all time steps t' S We explain its use in Scction
Using a history-based critic allows ARMAC to avoid using importance weight (IW) based off- policy correction as is the case in MCCFR, but at the cost of higher bias due to inaccuracies that the critic has. Using TW may be especially problematic for long games. For large games the critic will inevitably rely on generalization to produce history-value estimates.
To save memory, reservoir sampling with buffer of size of 1024 was used to prune past policies.
The algorithm also works in single agent case by treating all opponent reach probabilities as 1. More details and results are given in Appendix in Sections C.1 and D
Our main theoretical result is that ARMAC learns a function WT which is stand-in replacement for the cumulative regrets of CFR, R See Appendix for an analysis of ARMAC's theoretical properties.
A worked out example is given in Appendix in Section A
3.1
ADAPTIVE POLICY SELECTION
0.62
61-
605
0.2
005
022
03-
435
431-
055
.000
shepl
(a) Goofspiel
(b) Ledue Poker
(c) Liars Dice
Figure 2: An average reward per modulations scored against opponent #' as function of time (measured in acting steps). The brown curve is random uniform policy (i). Cyan, orange and blue are (ii) with e E 0.0, 0.01, 0.05 respectively. Pink, green and yellow are (iii) with e e 0.0, 0.01, 0.05.
ARMAC dynamically switches between what policy to use based estimated returns. For every / there is a pool of candidate policies, all based on the following four policies: (i) random uniform policy. (ii) several policies defined by applying Eq I over the current epoch's 's regret only (qo: (h, a) ugr (h)), with different levels of random uniform exploration: E 0.0, 0.01, 0.05. (iii) several policies defined by the mean regret, a' as stated in Algorithm [ also with the same level of exploration. (iv) the average policy ø' trained via classification.
A ARMAC generates experiences using those policies is facilitate the problem of exploration and to help produce meaningful data at initial stages of learning before average regrets
of its effects by any of the players in the game. Thus, the critics represent an expectation over those hidden outcomes. Since this does not affect the theoretical results, we choose this notation for simplicity. Importantly, ARMAC remains model-free: never enumerate chance moves explicitly nor evaluate their probabilities which may be complex for many practical applications.

---

Under review as a conference paper at ICLR 2021
are learnt. Each epoch, the candidate policies are ranked by cumulative return against an opponent playing Tgr. The one producing highest rewards is used half of the times. When sub-optimal policies are run for players -2, they are not used to train mean regrets for player i, but are used to train the critic. Typically, (ii) produces the best policy initially and allows to bootstrap the learning process with the best data (Fig. 2 In later stages of learning, (iii) with the smallest of e yields better policies and gets consistently picked over other policies. The more complex the game is, the longer it takes for (iii) to take over (ii..
Exploratory policy pf is constructed by taking the most recent neural network with 50% probability or otherwise sampling one of the past neural networks uniformly and modulating it by the above described method.
3.2 NETWORK ARCHITECTURE
A ARMAC can be used with both ferd-forward (FF) and recurrent neural net (RNN) (Fig. a))) For small games where information states can be easily represented, FF networks were used. For larger games, where consuming observations rather than information states is more natural, RNNs were used. More details can be found in Appendix in Section
4 EMPIRICAL EVALUATION
For partially-observable multiagent environments, we investigate Imperfect Information (II-) Goolspiel, Liar's Dice, and Ledue Poker and betting-abstractel no-limit Texas Hold'em poker (in Section 4.1. Goofspiel is a bidding card game where players spend bid cards collect points from a deck of point cards. Liar's dice is a 1-die versus 1-die variant of the popular game where players alternate bidding game with a 6-card deck, fixed bet amounts, and a limit on betting. Longer descriptions of cach games can be found in (4 We use OpenSpiel (19) implementations with default parameters for Liar's Dice and Ledue poker, and a 5-card deck and descending points order for II-Goofspiel. To show empirical convergence, we use NashConv, the sum over each player's 's incentive to deviate to their best response unilaterally (2I), which can be interpreted as an empirical distance from Nash equilibrium (reaching Nash at 0).
the dice values. Ledue poker is two-round poker
Law dee
KOCI
Mack
10
117
6x10
6.:00
3.30
10
Eshocce
Ephoode
Soloodss
(a) Ledue baselines.
(b) Goofspiel baselines.
(c) Liars Dice baselines.
Figure 3: NFSP and MC-RCFR the Ledue Poker, II-GoofSpiel with cards and Liars Dice
We compare empirical convergence to approximate Nash equilibria using model-free sampled form of regression CFR (34) (MC-RCFR). Trajectorics are obtained using outcome sampling MCCFR (20), which uses off-policy importance sampling to obtain unbiased estimates of immediate regrets f, and average strategy updates 8, and individual (learned) state-action
basclines p7 to reduce variance. regressor then predicts Å and policy obtained via Eq. D and similarly for the average strategy. Each episode, the lcarning player plays with an c-nn-policy behavior policy (while opponent(s) play on-policy) and adds every
datun fs, (ft)) to data set, D, with retention rule based on reservoir sampling so it approximates a uniform sample of all the data ever seen. MC-RCFR is related, but not equivalent to, variant of DeepCFR (5) based outcome sampling (OS-DeepCFR) (3I). Oufar results differ significantly from the OS-DeepCFR results reported in (31), and we discuss differences in assumptions and experimental setup from previous work in Appendix C
7

---

Under review as a conference paper at ICLR 2021
10
30094
4.2
(a) NashCouv on Ledue Poker
(b) NashConv on Goofspiel.
(c) NashConv on Liars Dice
Figure 4: ARMAC results on Leduc, Go-ooossiell, and Liar's Dice. The y-axis is NashConv of the average strategy #*. The x-axis is number of epochs. One epoch consists of 100 learning steps. Each learning step processes 64 trajectories of length 32 sampled from replay memory. The final value reached by the best runs are 0.18 (Leduc), 0.5 (TI-Goofspiel), and 0.095 (Liar's Dice).
As with ARMAC, the input raw bits with no expert features. We use networks with roughly the same number of parameters the ARMAC experiments: feed-forward with 4 hidden layers of 128 units with concatenated ReLU (28) activations, and train using the Adam optimizer. We provide details of the sweep over hyper-parameters in Appendix C
Next we compare ARMAC to NFSP (16), which combincs fictitious play with deep noural network function approximators. Two data sets, DRL and D&L, store transitions of sampled experience for reinforcement learning and supervised learning, respectively. DRL is sliding window used to train best response policy to #_ via. DQN. DSL uses reservoir sampling to train T., an average over all past best response policies. During play, each agent mixes between its best response policy and average policy. This stabilizes learning and enables the average policies to converge to approximate Nash equilibrium. Like A ARMAC and MC-RCFR, NFSP does not use any expert features.
Convergence plots for MC-RCFR and NFSP are shown in Figure 3 and for ARMAC in Figure 4 NashConv values ARMAC are lower (Liar's Dice) and higher (Goofspiel) Ihan NFSP, but siguificantly lower than MC-RCFR in all cases. MC-RCFR results are consistent with the outcome sampling results in DNCFR (22). Both DNCFR and Deep CFR compensate for this problem by instead using external and robust sampling, which require forward model. So, next we investigate the performance of ARMAC a much larger game.
4.1 NO-LIMIT TEXAS HOLD'EM
linit Trows Hns FTPA abermetion
Trane with EEPA wostrartinn
303
23412
107
0/4
50
2.5
3.0
20.2
12.5
33.0
27.5
22a
Figure 5: ARMAC results in No-Limit Texas Hold'em trained with FCPA action abstraction evaluated using LBR-FC metric. The y-axis represents the amount LBR-FC wins agains the ARMAC-trained policy. The x-axis indicate days of training. The left graph shows the learning curve in linear scale, while the right one shows the same curve in log-log scale.
We ran ARMAC no-limit Texas Hold'em poker, using the common Fold, Call, Pot, All-in } (FCPA) action /bettinetngg abstraction. This game is orders of magnitude larger than games used above (+= 4.42 10 information states). Action abstraction techniques were used by all of the state-of-the- the Poker AI bots up to 2017. Modern search-based techniques of DeepStack 25 and Libratus ( still include action abstraction in the search tree.
8

---

Under review as a conference paper at ICLR 2021
Computing the NashConv requires traversing the whole game and querying the network at each information state. This becomes infeasible for large games, Instead, we use local best-response (LBR) (2). LBR is an exploiter agent that produces lower-bound on the exploitability: given some policy т-; it does a shallow search using the policy at opponent nodes, and a poker-specific heuristic evaluation at the frontier of the search. LBR found that previous than first expected. In our experiments, LBR was limited to the betting abstractions: FCPA, and FC. We used three versions of LBR: LBR-FCPA, which uses all 4 actions within the abstraction, LBR-FC, which uses a more limited action set of { Fold, Call } and LBR-FCI2-FCPA3A which uses { Fold, Call for the first two rounds and FCPA for the rest.
winning abstraction- based Poker bots were far more exploitable
We first. computed the average return that an ARMAC-trained policy achieves against uniform random. Over 200000 episodes, the mean value was 516 (chips) + 25 (95% c.i.). Similarly, we evaluated the policy against LBR-FCPA; it won 519 + 81 (95% c.i.) per episode. Hence, LBR-FCPA was unable to exploit the policy. ARMAC also beat LBR-FFCI2-CCP34 by 867 + 87 (95% c.i.) Interestingly, ARMAC learned to beat those two versions LBR surprisingly quickly. A randomly initialized ARMAC network lost against LBR-FCPA by -704 + 191 (95% c.i.) and against LBR-FCC2-FCPA33 by -230 + 222 (95% c.i.), but was beating both after mere 1 hour of training by 561 + 163 (95% c.i.) and 427 + c.i.) respectively (3 million acting steps, 11 thousand learning steps).
140 (95%
Counter-intuitively, ARMAC was exploited by LBR-FC which uses more limited action set. ARMAC scored -46 = 26 (95% c.i.) per episode after 18 days of training on a single GPU, 1.3 billion acting steps (rounds), 5 million learning steps, 50000 CFR epochs (Figure 5). To the best of our knowledge, this is the first time LBR has been used to approximate exploitability in any form of no-limit Texas Hold'en among this class of algorithms.
CONCLUSION AND FUTURE WORK
ARMAC was demonstrated lo work on both single agent and mulli-agent benchmarks. It is brings back ideas from computational game theory to address exploration issues while at the same time being able to handle learning in non-stationary environments. As future work, we intend to apply it to more general classes of multiagent games; A RMAC has the appealing property that it already stores the joint policies and history-based critics, which may be sufficient for convergence one of the classes of extensive-form correlated equilibria 10 12
REFERENCES
[1] Yasin Abbasi- Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellert Weisz. Politex: Regret bounds for policy iteration using expert prediction. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of PMLR, pages 3692-3702 2019.
[2] Adriá Puigdoménech Badia, Pablo Sprechmann, and et al. Never give up: Learning directed exploration strategies. In International Conference on Learning Representations (ICLR), 2020.
[3] A. Blum and Y. Mansour. Learning, regret minimization, and equilibria, In Algorithmic Game Theory, chapter 4. Carnegie Mellon University, 2007.
[4] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up Limit Hold'en eem Poker is solved. Science, 347(6218):1455 149, January 2015.
[5] Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret minimization. CoRR,, abs/ 1811.0011,, 2018.
[6] Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 360(6385), December 2017.
[7] Noam Brown and Tuomas Sandholm. Solving imperfect-infonnen information games via dis- counted regret minimization. CoRR, abs/ 1809.04040, 2018.
9

---

Under review as a conference paper at ICLR 2021
[8] Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, (66(6456)8885--88 890, 2019.
[9] Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In Proceedings of the Twenly- Bightt AAAI Conference on Arlificial Intelligence (AAAT), 2014.
[10] Andrea Celli, Alberto Marchesi, Tommaso Bianchi, and Nicola Gatti. Learning to correlate in multi-player general-sum sequential games, 2019.
[11] Andrea Celli, Alberto Marchesi, Gabricle Farina, and Nicola Gatti. No-regret learning dynamics for extensivc-form correlated and coarse correlated equilibria, 2020.
[12] Gabriele Farina, Tommaso Bianchi, and Thomas Sandholm. Coarse correlation in extensive-form games, 2019.
[13] Richard Gibson, Neil Burch, Mare Lanctot, and Duane Szafron. Efficient monte carlo counterfactual regret minimization in games with many player actions. In Advonces in Neural Information Processing Systems, pages 1880-1888, 2012.
[14] S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127-1150; 2000.
[15] Johannes Heinrich, Marc Lanctot, and David Silver. Fictitious self-play in extensive- form games. In Proceedings of the 32nd International Conference on Machine Learning (ICML 2015), 2015.
[16] Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect-informatinn games. CoRR, abs/1603.0112) 2016.
[17] Peter H. Jin, Sergey Levine, and Kurt Keutzer. Regret minimization for partially observable deep reinforcement learning. ICML, 2018.
[18] Vojtech Kovarík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisy. Re- thinking formal models of partially observable multiagent decision making. CoRR, 1e2//9906.111110 2019.
[19] Mare Lanctot, Edward Lockhart, Jean- Baptise Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, and Finbarr Timbers et al. OpenSpiel: A framework for reinforcement learning in games. CoRR, abs/ 1908. 09045, 2019. http //axxiv.org/ abs/ 1908.09453.
[20] Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte Carlo sampling for regret minimization in extensive games. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1078-1086, 2009.
[21] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In NIPS, 2017.
[22] Hui Li, Kailiang Hu, Zhibang Ge, Tao Jiang, Yuan Qi, and Le Song. Double neural counterfactual regret minimization. CoRR, abs/ 1812.0007, 2018.
[23] Viliam Lisy and Michael H. Bowling. Eqilibrium approximation quality of current no-limit poker bots. CoRR, abs/ (os/1661777547 2016.
[24] Edward Lockhart, Marc Lanctot, Julien Pérolat, Jean-Baptiste Lespiau, Dustin Morrill, Finbarr Timbers, and Karl Tuyls. Computing approximate equilibria in sequential adversarial games by exploitability descent. CoRR, abs 1903.0013. 2019.
[25] Matej Moravëík and Martin Schmid et al. DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 358(6362), 2017.
10

---

Under review as a conference paper at ICLR 2021
[26] D. Precup, R.S. Sutton, and S. Singh. Eligibility traces for off- off-policy policy evaluation. ICML, 2000.
[27] Martin Schmid, Neil Burch, Mare Lanctot, Matej Moravcik, Rudolf Kadlec, and Michael Bowling, Variance reduction in monte carlo counterfactual regret minimization (VR- MCCFR) for extensive form games using baselines. In Proceedings of the The Thirly- Third AAAI Conference on Artificial Intelligence, 2019.
[28] Wenling Shang, Kihyuk Sohn, Diogo Almcida, and Honglak Lec. Undorstanding and improving convolutional neural networks via concatenated rectified linear units. CoRR, abs/ 1603.05201, 2016.
[29] Y. Shoham and K. Leyton-Brown, Multiagent Systems: Algorithmic, Theerehh,ee,,c, and Logical Foundations. Cambridge University Press, 2009.
[30] Sriram Srinivasan, Mare Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environments. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[31] Eric Steinberger, Adam Lerer, and Noam Brown. Dream: Deep regret minimization with advantage baselines and model-free learning, 2020.
[32] R. Sutton and A. Barto. Reinforcement Learning: An. Introduction. MIT Press, 2nd edition, 2018.
[33] Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, and et al. Grandmaster level StarCraft. II using multi-agent reinforcement learning. Nature, 2019.
[34] Kevin Waugh, Dustin Morrill, J. Andrew Baguell, and Michael Bowling. Solving games with functional regret estimation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2015.
[35] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems 20, 2008.
11

---

Under review as a conference paper at ICLR 2021
Appendices
A WORKED-OUT EXAMPLE
We now show an example of how ARMAC works on the simple game of Kuhn poker, shown in Figure I
Suppose ARMAC has already run for t 50 epochs, 50 networks have been saved, and the exploring player is the first player i = 1. The first player uses an exploratory behavior policy nu as described above. The second player uses network j= 17 sampled from 1NI (...( .49)). For this episode, chance samples 102K. This happens with probability one sixth, so n-:(h) = & (chance is always seen as an opponent with a fixes policy) whereas player has not taken any actions so (h()) = 1. Along this episode p, the first player samples actions according to b and the second player according to π Tº7- Suppose then player 1 samples bet and player 2 samples bet (call) leading to 41 (p) = -2 for player 1 and Uz(p) = 2 for player 2. There are two histories traversed, call them and h respectively. For each one, the regret vectors F are determined by the critics qas (h, a') no (h), where a' is one the two legal actions. Trajectory p is added to the buffer D and many similar episodes take place.
Finally, in the learning phase: ARMAC uses all the data collected to train the critics using standard le regression losses on the TD error defined by TB(A); all the data can be used because TB is off-policy, allowing the exploratory behavior n2²0. Suppose examples from the first trajectory p are sampled: only data from the first player (history h) are used to train Wo on the advantage A(h,a) a) using standard regression loss; this is because to asymptotically approach CFR only the exploring player can train regrets leading to a scaling constant that is function only of the information state (for more detail, see Appendix [B. Finally, only the second player's ' actions are used to train the average network ß using a classification loss, as the second player in p was playing according to CFR's average policy across 50 epochs (due to sampling j uniformly and then playing TL, without exploration).
B THEORETICAL PROPERTIES
Each epoch estimates (h) = Exez(h.)) n7 (h, ()), and value (z),(h)
Eo (h, ()),,, a) for the current, policies (7'). Let us write the advantages A a) =
(h, (h),. Notice that we learn functions of the history h and not state s.
At epoch T, in order to deduce the next policy, πT+1 CFR applies regret-matching using the cumulative counterfactual regret R. ax) As already discussed, directly estimating (=) in 2 Instead, A ARMAC trains network (s, that estimates a conditional advantage along trajectories generated in the following way: For player we select a behavior policy nf providing good state-space coverage, e.g. mixture of past policies (#f)esT, with some added exploration (Section 3.1 provides more details). For the other players -i, for every trajectory, we choose one of the previous opponent policies n², played at some epoch chosen uniformly at random from {1. ... Thus at epoch T, several trajectories p are generated by following policy (MT, =_,,, where ~ (((1122....TT))
Rº using sampling suffers from high variance due to the inverse probability -/(x+==)(=))
Then at cach step (h, a) along these trajectory p², the neural network estimate WT[ss, (where 8 3 h) is trained to predict the advantage Am,, a) using the empirical l loss: C - (s,(s,a) - a Thus the corresponding average loss is
T
L
Σ
B B [6]
1 +
ΣΣΣ j=1 AES. hEr
(M - (h.
T
If the network has sufficient capacity, it will minimize this average loss, and WT (s, a) will converge (when the number of trajectories goes to 20) in each state-action pair (s, a); such
12

---

Under review as a conference paper at ICLR 2021
Chat the reach probability
+ En nii (s) (s,)) 0, to the conditional expectation
1 Eラ= 17 n/u x² (h) (h,,a)
(1)
(h,
(s, = Σ
Σ
+ プト n/u at (s)
J -E
hES
perfect recall hes
(3)
Notice that WT does not depend on the exploratory policy pf for player chosen in round T. After several trajectories p² our network W provides us with good approximation of the WT values and we use it in a regret matching update to define the next policy, i.e. Equation | Lemma shows that if W (s,
" (s) NORMALIZEREEIWWW is sufficiently close to the (?(,, values, then this is equivalent to CFR, i.c., doing regret-matching using the cumulative counterfactual regret R
is the same as the one produced by CFR when regret matching employed as the information-state learner:
Lemma 1. The policy defined by NORMALIZEDRELU(N
R. R., ()) = W (s.a)
x T+ (s. a) = (s,b) E. W. ( (s)
(4)
Proof. First, let us notice that
T 17 (h)
(s
A (h,
(5)
1= (s)
T
(h)
(h,
(6)
hE# E1
(s)
ΣΣ
(7)
where we used the perfect recall assumption in the first derivation, and we define w ws)
Ee (s)) Notice that (s) depends on the state only (and not on h). Now the cumulative regret is:
K
RC (s,
Σ (s, (s)
Σ
n (s) Uz
= Σ n (s) (1)
hEr (5) (g (goe,sh,,)) - (h))
n (h) A Are, (h,
REa
= (s) (s, a).
Finally, noticing that regret matching is not impacted by multiplying the cumulative regret by a positive function of the state, we deduce
(w (s),
W.T++ (s)
Σg R (..(++(ss) (s) (wTT)
Σ, ", (s,b)
The WT (s,a) estimates the expected advantages 1 EJ= Ags (h, conditioned on h E 8. Thus ARMAC does not suffer from the variance of estimating the cumulative regret RT a), and in the case of infinite capacity, from any (s, a), the estimate WT (s, a) is unbiased as soon the (s, a) has been sampled at least once:
13

---

Under review as a conference paper at ICLR 2021
Lemma 2. Consider the case of tabular representation and define the estimate WT WT(s, (s,a) as the minimizer (over W of the empirical loss defined over N trajectories
(W)
[ - Agin . (h. a) I[(h, a) p and h E s).
N
where pin is the n-th trajectory generated by the policy m where in u((f...... Define (() = I I((h,a) E p²n and h E 8) to be the number of trajectories going through a). Then (s, is an unbiased estimate of WT(ssa) conditioned (s.a) being traversed at least once:
E [ (s, (s. 0] (s,
Proof. The empirical loss being quadratic, under the event (N) 0}, its minimum is well defined and reached for
N(s.a)
(T,sa)= a)
Σ (hn,
a=1
where hn E is the history of the n-th trajectory traversing 8. Let us simplified notations and write An = Aws,,(le (T) E po and h E 8) and bn I((h,a) E p²n and h E s}. Thus
N
E AnT Em= bm > 0}
E (3)
Σ bm
fam0001 of]
= E
ΣN
1m=1 6m
m=1
N
A
m== bm > 0}
EE
Σ bm
Σm=r dm
m==1
If E
m==1 bm > 0}
E
TE.
A
Σ bm
Em=1 bm
Now, E[[An Em dml |n LE [mml
Em.
dml
since given bn. An is independent of
ΣN 4m- Thus
E
WT (s,
Σ bm off
E
A, [b,]
EE
IE
E
1n
Em=
dm
D I bm > 0}
ΣM bm
N
I
Um >0}
Am [bm]
ΣN
===1 dm
N
n=1
Since
ΣN
E
b.l Em
bm bm)
E
Σ
bn If
Em=1 6m > 00] =P( D bm 0), by
N
ΣN
&m
Σ
bm
a symmetry argument we deduce E.
b
Σ
bm bm>0
1/4 LP . bm > 0) for each n.
2m-1 bm
Thus
N Σ m=1
E
E (s,
6m > 0)
E (T
EN Σm= bm > tOf
DM bm 0)
N
N
B[A, =[A
which is the expectation of the advantage A (h, a) conditioned the trajectory p going through h E 8, i.e. WT (s, a) defined in
14

---

Under review as a conference paper at ICLR 2021
X
0,9,
Deep 2001
Deep
S
Observation
Observatioo clon
(b)
Figure 6: The (a) Multi-headed network architecture, and (b) Exploration example.
C BASELINE DETAILS AND HYPERPARAMETERS
For MC-RCFR, sweep over all combinations of the exploration parameter, using (learned) state-action baseline (27) and learning rate (e, b, a) E {0.25, 0.5, 0.6, 0.7, 0.9, 0.95, 1.0} x (TRUE, FALSE) x (0.0001, 0.00005, 0.00001}, where each combination is averaged over five seeds. We found that higher exploration values worked consistently better, which matches the motivation of the robust sampling technique (corresponding to c= 1) presented in (22) as it leads to reduced variance since part of the correction term is constant for all histories in an information state. The baseline helped significantly in the larger game with more variable-length episodes.
For NFSP, we keep set of hyperparameters fixed, line with (2 and 16] anticipatory parameter 0.1, e-greedy decay duration 20M steps, reservoir buffer capacity 2M entries, replay buffer capacity 200k entries, while swoeping over combination of the following hyperparameters: e-greddy starting value f0.06, 0.24), RL learning rate 0.1, 0.01. 0.001, SL learning rate (0.01, 0.001, 0.005): DQN target network update period of {1000, 19200] steps (the later is equivalent to 300 network-parameter updates). Each combination over three seeds. Agents were trained with the ADAM optimizer, using MSE loss for DQN and one gradient update step using mini-bated size 128, every 64 steps in the game.
averaged
Finally, note that there are at least four difference in the results, experimental setup, and assumptions between MC-RCFR and OS-DeepCFR reported in (1:
1. Bl uses domain expert input features which do not generalize outside of poker. The neural network architecture we use a basic MLP with raw input representations, whereas (81) uses far larger network. Our empirical results benchmark games compare the convergence properties of knowledge-free algorithms across domains.
2. The amount of training per iteration is an order of magnitude larger in OS-DeepCFR than training. In (31), every 346 iterations, the Q-network is trained using 1000 minibatches of 512 samples (512000 examples), whereas every 346 iterations we train 346 batches of 128 samples, 44288 examples.
3. MC-RCFR uses standard outcome sampling rather than Linear CFR
4. MC-RCFR's strategy approximated by predicting the OS's average strategy increment rather than sampling from buffer of previous models.
Our NESP also does not use any extra enhancements.
C.1 SINGLE-AGENT ENVIRONMENTS
Despite ARMAC being based on commonly-used multiagent algorithms, it has properties that may be desirable the single-agent setting. First, similar policy gradient algorithms in the common "short corridor example" (32) Example 13.1), stochastic policies are representable by definition, since they are normalized positive mean regrets over the actions. This could have practical effect hhat entropy bonuses lypically have in policy gradient methods, but rather than simply adding arbitrary entropy, the relative regret. over the of past policies is taken into account.
Second, retrospective agent uses a form directed exploration of different exploration policies 22. Here, this is achieved by the simulation (My mL.), which could be desirable whenever there is overlapping structure in successive tasks. nr here is exploratory
15

---

Under review as a conference paper at ICLR 2021
policy, which consists of mixture of all past policies (plus random uniform) played further modulated with different amounts of random uniform exploration (more details are given in Section 3.1p Consider a gridworld illustrated in Fig. 6 b).. Green squares illustrate positions where the agent i gets a reward and the game terminates. Most of RL algorithms would find the reward of +1 first as it is the closest to the origin S. Once this reward is found, policy would quickly learn to approach it, and finding reward +2 would be problematic. ARMAC, in the meantime, would keep re-running old policies, some of which would pre-date finding reward +1, and thus would have a reasonable chance of finding +2 by random exploration. This behaviour may also be useful if instead of terminating the game, reaching one of those two rewards would start next levels, both of which would have to be explored.
These properties are not necessarily specific to ARMAC. For example, POLITEX (another retrospective policy improvement algorithm ①) has similar properties by keeping its past approximators intact. Like POLITEX, we show an initial investigation of ARMAC in Atari in Appendix D Average strategy sampling MCCFR (3) also uses exploration policies that are a mixture of previous policies and uniform random to improve performance over external and outcome sampling variants. However, this exact sampling method cannot be used directly in ARMAC as it requires a model of the game.
D INITIAL INVESTIGATION OF ARMAC IN THE ATARI LEARNING ENVIRONMENT
While performance Atari is not the main contribution, it should be treated health check of the algorithm. Unlike previously tested multiplayer games, many Atari games have a long term credit assignment problem. Some of them, like Montezuma's 's Revenge, are well-known hard exploration problems. It. is interesting lo see that ARMAC was able to consistently score 2500 points on Montezuma's Revenge despite not using any auxiliary rewards, demonstrations, or distributional RL as critic. We hypothesize that regret matching it provides naturally stochastic policies which stay
may be advantageous for exploration, stochastic until regrets for other actions becomes negative. We also tested the algorithm on Breakout, as it is a fine control problem. We are not claiming that out results on Atari are state of art they should be interpreted basic sanity check showing that ARMAC could in principle work in this domain.
600
rewarts, mean
2.2K
500
2k
1.5k
300
1.4k
200
16-
100
1908
2008"
4b0as"
spar
7onar
eeaer
sasse
1.10
aag
1.0"
1.86
1952
2036
3035
4003
8000
600M
1.20
146"
(a) Breakout
(b) Montezuma Revenge
Figure 7: Performance on Breakont (left)) and Montezuma Revenge (right). Results are shown for two seeds.
E TRAINING
Training is done by processing a batch of 64 of trajectories of length 32 at time. In order to implement a full recall, all unfinished episodes will be continued on the next training iteration by propagating recurrent network states forward. Each time when one episode finishes at a particular batch entry, a new one is sampled and started to be unrolled from the beginning.
16

---

Under review as a conference paper at ICLR 2021
Adam optimized with 81 0.0 and B2 0.999 used for optimization. Hyperparameter selection was done by trying only two learning rates: 5 100 and 2 10 The results reported use 5 10 in all games, including Atari.
F NEURAL NETWORK ARCHITECTURE
The following recurrent neural network was used for no-limit Texas Hold em experiments. Two separate recurrent works with shared parameters were used, consuming observations of each player respectively. Each of those networks consisted of single linear layer mapping imput representation to a vector of size 256. This was followed by a double rectified linear unit, producing representation of size 512 then followed by LSTM with 256 hidden units. This produced an information state representation for cach player dg and 01
Define architecture B(x), which will be reused several times. It consumes one of the informa- tion state representations produced by the previously mentioned RNN: h1 Linear (i)ear(128) h2 = Double Re RLU (h1), ha h1 Linear (12)),,,,,, B(a) Double Re. (UU.U(s)))
The immediate regret head is formed by applying B(s) on the information state representation followed by single linear layer of the size of the number of actions in the game. The same is done for an average regret head and mean policy head. All those B(s) do not share weights between themselves, but share weights with respective heads for another player.
The global critic q(h) is defined the following way. nu Linear(128)) n. = Linear (128) ag = (56) ng(s)), do n)((s) + (s1),, h1 Concat (o, a1), h2 B(1)) and finally 2o 32) and (31, $2) are evaluated by a two linear layers on top of h2. B(x) shares architecture but does not share parameters with the ones used previously.
17


Reviews:
[{"review_id": "uO9OrSPvnrH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors adopt the idea from gaming theory to reinforcement learning and propose a new algorithm that uses the previous policy to update the current training without using importance sampling. Experiments show that the proposed algorithm cannot only work on the single-player setting but also work on the multi-agent (zero-sum) problems. However, I have the following concerns about the algorithms: \n1) To train the critic, how would the sample complexity be? Like vanilla Actor-Critic algorithms, can it be replaced by doing a one-step TD(0) update on the critic to improve the sample efficiency?\n2) Since the original CFR method is solving the multi-agent zero-sum algorithm, it would be interesting why this extension could solve the single-player problem?\n\nAlso, it would make the contribution of this work more clear if the author can compare this exploration method with other exploration methods, such as $\\epsilon$-greedy or UCB. To me, the algorithm uses sample trajectory $\\rho \\sim (\\mu_i, \\pi_{-i}^j)$. If we make all $\\mu$ be random policy, is this exploration similar to $\\epsilon$-greedy to some extent?\n\nConsidering all contributions and concerns mentioned above, I will suggest a borderline accept for this paper. I might change my score after the author's response and discussion.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hEW6ukPgosW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review: \nThis paper proposes a general model-free RL method for no-regret learning based on a repeated reconsideration of past behavior. The ARMAC algorithm using the off-policy policy evaluation algorithm TreeBackup to estimate value function and use regret matching to get the next joint policy.\n\nThis paper idea is origin from DCFR, DNCFR, single CFR.  But those are model-based algorithms. ARMAC is model-free algorithms and it can be used in a more border environment.  If the author compares this paper to the DREAM algorithm(Deep Regret minimization with Advantage baselines and Model-free learning) to state ARMAC advantage, I will update my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CNcFSEXA1dI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of counterfactual regret minimization and proposes an algorithm that does not use the importance sampling procedure. The claim is that this helps in reducing the variance usually introduced by the IS procedure. They propose a new algorithm that uses the previously used policies as a buffer and replays those policies to learn a new policy. The algorithm is also claimed to be highly scalable for games with large state-action pairs.\n\n\nMy overall assessment of this paper is that, the problem considered is an important one and a well-implemented/well-written paper would definitely be a good paper that is significantly impactful for this community. However, my personal opinion is that this paper is not yet there. First, the paper is not well-written for someone who is not familiar with the exact prior literature on CFR using deep learning. In particular, the paper is not organized well, some of the important definitions are omitted and in general the key points aren't sufficiently highlighted. Also I find the experiments to be a bit lacking. In particular, one of the key claims of the paper is that it eliminates the variance introduced by the IS procedure, yet there are no experiments to substantiate this (more below). Also the executed experiments are not explained well. My opinion is that the section of \"theoretical properties\" is totally unhelpful for the main section and can be relegated to the appendix; it does not add value to the understanding of this algorithm. Additionally, I have several comments below that can help with both the writing, the weaker experiments and overall improving this paper to a state that will make it more impactful/easier to understand. My current assessment of this paper is that without a major revision of the writing and execution, this paper is not in a state to be accepted. \n\n\n(1) A self-sufficient description of the problem statement. The paper does describe the problem, but it takes a few readings for a new reader not familiar with the exact line of work to get the setup and the contributions of this paper. Moreover, as an arrangement it is spread over introduction and notations. Finally, the paper doesn't explicitly state what the goal of a CFR algorithm is. Is it to minimize the total average counterfactual regret?\n\n(2) Along those lines, I think the paper would be very informative if the algorithm was evaluated and instantiated on a very simple two-player game with  known Nash equilibria (even simpler than Atari and Montezuma's revenge). In particular, there are many such games known in theory (e.g., the prisoner's dillema) and you can pick one of them and instantiate/evaluate this algorithm to help the reader understand the notations precisely. My opinion is that the notations is intertwined with informal descriptions and it is often hard to parse what the authors are meaning to say. Having such a unified simple game will make this process easier on the reader. This also ensures that the implementation and the algorithm is itself correct.\n\n(3) Some definitions in the empirical section are not defined formally. In particular, the quantity NashConv is not defined in this paper and relegated to a related work. Only the informal description is given. This makes the reading really hard. For instance, we know that it should be close to 0, but how close? For instance, how do I interpret a value of 0.5? What is the range of NashConv? These questions could be easily answered if a precise definition of NashConv was included in this paper.\n\n(4) Issues with experiments: First, in the convergence plot for ARMAC in Figure 3, it would be good to plot the line for what the NashConv is (like in Figure 2). Second, the main claim of this paper is that the variance introduced by importance sampling is not present (because this algorithm does not invoke the IS procedure). However, it is surprising that the empirical evaluation section does not include a convincing experiment to drive this point. In particular, it would be good to have a comparison of the variance of the three algorithms and show that the variance introduced by the IS procedure is indeed a meaningful problem for the final outcome (i.e., variance in the convergence value to the NashConv) and that the proposed method indeed reduces it? If the variance introduced by the IS procedure does not lead to a meaningful variance on NashConv, please motivate better why the variance introduced by IS is a problem?\n\n(5) Some suggestions on plots: I find Figure 1 to have particularly difficult to read color schemes. First, the caption states a Pink line and it took me a while to figure which was Pink (I think it is the violet line which is pink). The same problem with Brown. Overall, the 7 colors used are pretty close and I would suggest either trying to use other markers to distinguish (such as a text on the line, different line type etc) or try and use contrasting color schemes. For instance, some of these lines may be indistinguishable for a person with color blindness. Likewise, the titles of the plots are not meaningful/interpretable. In figure 1, both the x and y axis seem like titles that were used internally by the authors. I do not understand what they mean. In the x-axis title, I don't see what that 1 represents and I quite frankly do not understand what the y-axis is trying to say. Likewise, among the three plots, across Figures 1, 2, 3 if the order of the three environments remained consistent, that would help the readability. This is also important, because I still do not understand how to interpret Figure 1. I think 0 implies that the algorithm is good. But if its negative does it mean that the algorithm is better while if its positive it is worse? Please explain Figure 1 better.\n\n(6) Finally there are many typos throughout the paper. Here is a non-exhaustive list.\n- page 3: heads on the same neural -> I don't understand what this statement is saying and seems grammatically incorrect as stated.\n- Page 3: The first one estimate -> The first one estimates\n- In caption of Figure 1, the word modulations is used. This word is not defined anywhere else in the paper. Please either define this or re-use a word that has been introduced.\n- Page 6: ARMAC generates experiences using those... -> this sentence is grammatically incorrect. Please fix.\n- Page 8: Conclusions. \"It is brings back\" -> grammar check this sentence\n- Page 8: Conclusions: \"for convergence one of the classes\" -> grammar check\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a new algorithm to solve game, more or less similar (in the general idea, yet differences are interesting) than CFR. The concept is to sample from past policies to generate trajectories and update sequentially (via regret matching).

The three reviewers gave rather lukewarm reviews, with possible suggestions of improvements (that were more or less declined by the authors for those proposed by Rev3 and Rev4; the added material focuses more on the clarity of the text than on the content itself).

I have also read the paper, and find it quite difficult to assess. At the end, it is not clear to a reader whether ARMAC is the new state of the art, or just a "variant" of CFR that will be soon forgotten. The performances do not seem astonishing (at least against NSFP) and even though DREAM might not be satisfactory to the authors (EDIT POST DISCUSSION: actually, DREAM is a valid competitor and must be included in the comparative study), it would have been nice to provide some comparison. Maybe the issue is the writing of the paper that could and should be improved so that it is clearer what are the different building blocks of ARMAC (and their respective importance).

If ARMAC is the new state of the art, then I am sure the authors will be able to clearly illustrate it in a forthcoming revision (maybe with more experiments, as suggested by Rev2). Unfortunately, for the moment, I do not think this paper is mature enough for ICLR.
Decision: Reject