title: The Advantage Regret-Matching Actor-Critic
authors: Audrūnas Gruslys Marc Lanctot Rémi Munos Finbarr Timbers Martin Schmid Julien Perolat Dustin Morrill Vinicius Zambaldi Jean-Baptiste Lespiau John Schultz Mohammad Gheshlaghi Azar Michael Bowling Karl Tuyls
text: 
  
  Nonmagnetic ground state, Crystal field effects and Heavy-fermion behaviour in the Remeika Phase: Pr_3Ir_4Ge_13
      [
      Received XXX 2019 / Accepted XXX 2020
  ===============================================================================================================
  
  
  
  
  
  
  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.
  We propose a model-free RL algorithm, the Advantage Regret-Matching Actor-Critic ():
  rather than saving past state-action data, 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, shows an interesting form of exploration by keeping past policies intact.
  In the multiagent setting, 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.
  
  
  
  
  
  § INTRODUCTION
  
  
  
  
  The notion of regret is a key concept in the design of many decision-making algorithms. 
  Regret minimization drives most bandit algorithms, is often used as a metric for performance of reinforcement learning (RL) algorithms,
  and for learning in games <cit.>. When used in algorithm design, the common application is to accumulate values and/or regrets and derive
  new policies based on these accumulated values. One particular approach, counterfactual regret (CFR) minimization <cit.>, has been the core algorithm behind 
  super-human play in Computer Poker research <cit.>.
  
  
  We investigate the problem of generalizing these regret minimization algorithms over large state spaces in the sequential setting using end-to-end function approximators, such as deep networks.
  There have been several approaches that try to predict the regret, or otherwise, simulate the regret minimization: Regression CFR (RCFR) <cit.>, advantage regret 
  minimization <cit.>, regret-based policy gradients <cit.>, Deep Counterfactual Regret minimization <cit.>, and 
  Double Neural CFR <cit.>. All of these approaches have focused either on the multiagent or single-agent problem
  exclusively, some have used expert features, while others tree search to scale. Another common approach is based on fictitious play <cit.>, a simple iterative self-play algorithm based on best response.
  A common technique among several of these algorithms is to use reservoir sampling to maintain a
  buffer that represents a 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 <cit.>, and in Deep CFR this method was shown to approach an approximate equilibrium in a large subgame of Hold'em poker.
  A generalization of fictitious play, policy-space response oracles (PSRO) <cit.>, stores past policies and a meta-distribution over them, replaying policies
  against other policies, incrementally adding new best responses to the set, which can be seen as a population-based 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; as a result,
  it was able to scale to a very large real-time strategy game <cit.>.
  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 policies 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 as CFR would do.
  In the single-agent setting, is related to  <cit.>, except that it is based on regret-matching <cit.> and 
  it predicts average quantities 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 requiring importance sampling as in standard Monte Carlo CFR <cit.>, hence it does not suffer from excessive variance in large environments.
  This is achieved by using critics (value estimates) of past policies that are trained off-policy using standard policy evaluation techniques.
  In particular, we introduce a novel training regime that estimates a conditional advantage W_i(s,a), which is the cumulative counterfactual regret R_i(s,a), scaled by factor B(s) that depends on the information state s only; hence, using regret-matching over this quantity yields the policy that CFR would compute when applying regret-matching to the same (unscaled) regret values.
  By doing this entirely from sampled trajectories, the algorithm is model-free and can be done using any black-box simulator of the environment; hence, inherits the scaling potential of PSRO without requiring a best-response training regime, driven instead by regret minimization.
  
  
  
  
  § 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 <cit.>.
  A single-player game represents the single-agent case where histories are aggregated appropriately based on the Markov property.
  
  
  
  A game is a tuple (, , , , , u, τ), where = { 1, 2, ⋯, n} is the set of players.
  By convention we use i ∈ to refer to a player, and -i for the other players ( - { i }).
  There is a special player c called chance (or nature) that plays with a fixed stochastic strategy (chance's fixed strategy determines the transition function).
   is a finite set of actions.
  Every game starts in an initial state, and players sequentially take actions leading to histories of actions h ∈.
  Terminal histories, z ∈⊂, are those which end the episode.
  The utility function u_i(z) denotes the player i's return over episode z.
  The set of states  is a partition of  where histories are grouped into information states
  s = { h, h', …} such that the player to play at s, τ(s), cannot distinguish among the possible histories (world states)
  due to private information only known by other players [Information state is the belief about the world that a given player can infer based on her limited observations and may correspond to many possible histories (world states)].
  Let Δ(X) represent all distributions over X: each player's (agent's) goal is to learn a policy π_i : _i  →Δ(), where _i = {s |  s ∈, τ(s) = i}.
  For some state s, we denote (s) ⊆ as the legal actions at state s, and all valid state policies π(s) assign probability 0 to illegal actions a ∉(s).
  
  Let π denote a joint policy. Define the state-value v_π,i(s) as the expected (undiscounted) return for player i
  given that state s is reached and all players follow π. Let q_π,i be defined similarly except also
  conditioned on player τ(s) taking action a at s. Formally, v_π,i(s) = ∑_(h,z) ∈(s)η^π(h | s) η^π(h,z) u_i(z),
  where (s) are all terminal histories paired with their prefixes that pass through s, η^π(h | s) = η^π(h)/η^π(s), where η^π(s)=∑_h'∈ sη^π(h'), and η^π(h,z) is the product of probabilities of
  each action taken by the players' policies along h to z. The state-action values q_π,i(s,a) are defined analogously.
  Standard value-based RL algorithms estimate these
  quantities for policy evaluation.
  
  Regret minimization in zero-sum games uses a different
  notion of value, the counterfactual value: v^c_π,i(s) = ∑_(h,z) ∈(s)η^π_-i(h) η^π(h,z) u_i(z),
  where η^π_-i(h) is the product of opponents' policy probabilities along h.
  We also write η^π_i(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'∈ s, η^π_i(h)=η^π_i(h'). Thus 
  counterfactual values are formally related to the standard values <cit.>:
  v_π,i(s) =  v^c_π,i(s) /β_-i(π, s),
  where β_-i(π, s) = ∑_h ∈ sη^π_-i(h). 
  
  Also, q^c_π,i(s,a) is defined similarly except over histories (ha, z) ∈(s),
  where ha is history h concatenated with action a.
  
  Counterfactual regret minimization (CFR) is a tabular policy iteration algorithm that has been at the core of
  the advances in Poker AI <cit.>. On each iteration t, CFR computes
  counterfactual values q_π,i^c(s, a) and v_π,i^c(s) for each state s and action a ∈(s) 
  and the regret of not choosing action a (or equivalently the advantage of choosing action a)
  at state s, r^t(s,a) = q_π^t,i^c(s, a) - v_π^t,i^c(s).
  CFR tracks the cumulative regrets for each state and action, R^T(s,a) = ∑_t=1^T r^t(s,a).
  Define (x)^+ = max(0, x); regret-matching then updates the policy of each action a ∈(s) as follows <cit.>:
  
      π^T+1(s,a) = NormalizedReLU(R^T, s, a) =
      R^T,+(s,a)/∑_b ∈(s) R^T,+(s,b)   if ∑_b ∈(s) R^T,+(s,b) > 0
      1/|(s)|   otherwise
      ,
  
  In two-player zero-sum games, the mixture policy π̅^T converges to the set of Nash equilibria as T →∞.
  
  Traditional (off-policy) Monte Carlo CFR (MCCFR) is a generic family of sampling variants <cit.>.
  In outcome sampling MCCFR, a behavior policy μ_i is used by player i, while players -i
  use π_-i, a trajectory ρ∼ (μ_i, π_-i) is sampled, and the sampled
  counterfactual value is computed:
  
      q̃_π,i^c(s,a | ρ) = 1/η^(μ_i, π_-i)_i(z)η^(μ_i, π_-i)_i(ha,z) u_i(z),
  
  if (s,a) ∈ρ, or 0 otherwise. 
  q̃_π,i^c(s,a | ρ) is an unbiased estimator of q^c_π,i(s,a) <cit.>. 
  
  However, since these quantities are divided by η^(μ, π_-i)_i(z), the product of player i's probabilities, 
  (i) there can be significant variance introduced by sampling, especially in problems involving long sequences of decisions, and (ii) the ranges of the ṽ_i^c 
  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 <cit.>. 
  Deep CFR and Double Neural 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 of which require a perfect game model and enumeration of the tree. This is unfeasible in very large environments or in the RL setting where full 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.
  
  
  
  
  § RETROSPECTIVE POLICY IMPROVEMENT
  
  
  Retrospective policy improvement focuses on learning from past behavior, by storing complete descriptions of value functions and/or policies, deriving a new policy from them via aggregation, rather than e.g. greedily optimizing a current policy. 
  Specifically, a retrospective agent finds a new policy by playing back through past policies, rather than maintaining a buffer of past data.
  
  The general idea is common in learning partially-observable multiagent games, where algorithms are built upon regret minimization and learning from expert advice <cit.>.
  
  
  
  Regret minimization in self-play can approximate various forms of equilibria <cit.>. In single-agent settings, they can also approximate optimal policies in Markov decision processes <cit.>, even when the reward function changes over time <cit.>, and solve a general class of robust optimization problems <cit.>.
  We also show some appealing properties in the single-agent case via some illustrative examples (Section <ref>).
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ The Advantage Regret-Matching Actor-Critic
  
  
  is a model-free RL algorithm motivated by CFR.
  Like algorithms in the CFR framework, uses a centralized training setup and operates in epochs that correspond to CFR iterations.
  Like RCFR, uses function approximation to generate policies.
  was designed so that as the number of samples per epoch increases and the expressiveness of the function approximator approaches a lookup table, the generated sequence of policies approaches that of CFR.
  Instead of accumulating cumulative regrets– which is problematic for a neural network– the algorithm learns a conditional advantage estimate W̅(s, a) by regression toward a history-dependent advantage A(h,a), for h∈ s, and uses it 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) up to a multiplicative factor which is a function of the information state s only, and thus cancels out during the regret-matching step.
  is a Monte Carlo algorithm in the same sense as MCCFR: value estimates are trained from full episodes. It uses off-policy learning for training the value estimates (critics), which we show is sufficient to derive W̅. However, contrary to MCCFR, it does not use importance sampling.
  is summarized in Algorithm <ref>.
  
  
  
  
  [35]R0.6
  0.6
  
  
  [H]
  InputinputOutputoutput
  initial set of parameters ^0, number of players n
  Advantage Regret-Matching Actor-Critic
  i ← 1  
  epoch t ∈{0, 1, 2, ⋯}
    reset ←∅  
    Let π^t(s) = NormalizedReLU(W̅_^t(s)) (Eq. <ref>) 
    Let v_^t(h) = ∑_a ∈(h)π^t(h,a) q_^t(h,a)  
    Let μ_i^t be a behavior policy for each player i  
    episode k ∈{1, …, K_act}
          i ← (i + 1)  mod n  
          Sample j ∼Unif({ 0, 1, ⋯, t-1})  
          Sample trajectory ρ∼ (μ_i, π_-i^j)  
          let d ← (i, j, { u_i(ρ) }_i ∈)  
          history h ∈ρ where player i acts
              let s be the state containing h  
              let r⃗ = { q_^j(h,a') - v_^j(h) }_a' ∈(s)  
              let a be the action that was taken in ρ  f
              append (h, s, a, r⃗, π^j(s)) to d  
          
          add d to  
    
    learning step k ∈{ 1, …, K_learn}
      Sample a random episode/batch d ∼Unif():  
      history and corresponding state (h,s) ∈ d
          Use Tree-Backup(λ) to train the critic q_^t(h,a)  
          If τ(s) = i: train W̅_^t to predict A(h,a)  
          If τ(s) ∈ -i: train π̅_^t to predict π^t(s)  
      
    
    Save ^t for future retrospective replays  
    ^t+1←^t  
  
  
  
  
  
  runs over multiple epochs t and produces a joint policies π^t+1 at the end of each epoch.
  Each epoch starts with an empty data set  and simulates a variety of joint policies executing multiple training iterations of relevant function approximators. 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 q_π^t,i(h, a) = ∑_z∈(h,a)η^π^t(h,z)u_i(z).
  This estimator[In practice, rather than using h as input to our approximators, we use a concatenation of all players' observations, i.e. an encoding of the augmented information states or action-observation histories <cit.>. In some games this is sufficient to recover a full history. In others there is hidden state from all players, we can consider any chance event to be delayed until the first observation 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, remains model-free: we never enumerate chance moves explicitly nor evaluate their probabilities which may be complex for many practical applications.]
  can be trained on all previous data by using any off-policy policy evaluation algorithm  from experiences stored in replay memory (we use Tree-Backup(λ) <cit.>).
  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 W̅_i^t(s,a) that estimates the expected advantage A_μ^t,i(h,a)=q_μ^t,i(h,a)-v_μ^t,i(h) conditioned on h∈ s when following some mixture policy μ^t (which will be precisely defined in Section <ref>). It happens that W̅_i^t(s,a) is an estimate of the cumulative regret R^t(s,a) multiplied by a (non-negative) function which depends on the information state s only, thus does not impact the policy improvement step by regret-matching (see Lemma <ref>).
  Once W̅_i^t(s, a) is trained, the next joint policy π^t+1(s, a) can be produced by normalizing the positive part as in Eq. <ref>.
  After each training epoch the joint policy π^t is saved into a past policy reservoir, as it will have to be loaded and played during future epochs.
  Lastly, an average policy head π̅^t is also trained via a classification loss to predict the policy π^t' over all time steps t' ≤ t.
  We explain its use in Section <ref>.
  
  Using a history-based critic allows 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 IW 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.
  
  
  
   §.§ Theoretical Properties
  
  
  
  Each epoch t estimates
  q_π^t,i(h,a) = ∑_z∈(h,a)η^π^t(h,z)u_i(z)
  and value v_π^t, i(h)=∑_aπ^t(h,a)q_π^t,i(h,a) for the current policies (π^t). Let us write the advantages A_π^t,i(h,a) = q_π^t,i(h,a) - v_π^t, i(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_i^T(s,a). As already discussed, directly estimating R_i^T using sampling suffers from high variance due to the inverse probability η^(μ, π_-i)_i(z) in  (<ref>). Instead, trains a network
  W̅_i^T(s,a) that estimates a conditional advantage along
  
  trajectories generated in the following way: For player i we select a behavior policy μ_i^T providing a good state-space coverage, a mixture of past policies (π^t_i)_t ≤ T, with some added exploration (Section <ref> provides more details). For the other players -i, for every trajectory, we choose one of the previous opponent policies π_-i^j played at some epoch j chosen uniformly at random from { 1, 2, ⋯ T }. Thus at epoch T, several trajectories ρ^j are generated by following policy (μ^T_i,π^j_-i), where 
  j∼ U({ 1, 2, ⋯ T }).
  
  Then at each step (h,a) along these trajectory ρ^j, the neural network estimate W̅_i^T(s,a) (where s ∋ h) is trained to predict the advantage A_π^j,i(h,a) using the empirical ℓ_2 loss:  L̂= [W̅_i^T(s,a) - A_π^j,i(h,a)]^2. 
  Thus the corresponding average loss is 
  
      L=1/T∑_j=1^T_ρ^j∼ (μ_i^T,π_-i^j)[ L̂]= 1/T∑_j=1^T ∑_s∈_i∑_h∈ sη^(μ_i^T,π_-i^j)(h) μ_i^T(s,a) [W̅_i^T(s,a) - A_π^j,i(h,a)]^2.
  
  Thus if the network has sufficient capacity, it will minimize this average loss, thus our estimate W̅_i^T(s,a) will converge (when the number of trajectories goes to infinity) in each state-action pair (s,a), such that the reach probability 1/T∑_t η^(μ_i^T,π_-i^t)(s) μ_i^T(s,a)>0, to the conditional expectation
  
      W^T_i(s,a)= ∑_h∈ s1/T∑_j=1^T η^(μ_i^T,π_-i^j)(h)A_π^k, i(h,a)/1/T∑_j=1^T η^(μ_i^T,π_-i^t)(s)=_perfect recall∑_h∈ s1/T∑_j=1^T η^π^j_-i(h)A_π^k, i(h,a)/1/T∑_j=1^T η^π^t_-i(s)
  
  Notice that W_i^T does not depend on the exploratory policy μ_i^T for player i chosen in round T. After several trajectories ρ^j our network W̅^T_i provides us with a good approximation of the W^T_i values and we use it in a regret matching update to define the next policy, π_i^T+1(s) = NormalizedReLU(W̅_i^T), Equation <ref>.
  The following lemma (proved in Appendix <ref>) shows that if W̅^T_i(s,a) is sufficiently close to the W^T_i(s,a) values, then this is equivalent to CFR, i.e., doing regret-matching using the cumulative counterfactual regret R^T.
  
  
  
  The policy defined by NormalizedReLU(W_i^T) is the same as the one produced by CFR when regret matching is employed as the information-state learner:
  
      π^T+1_i(s,a) = R_i^T,+(s,a)/∑_b R_i^T,+(s,b) = W_i^T,+(s,a)/∑_b W_i^T,+(s,b).
  
  
  
  The W̅^T(s,a) estimate the expected advantages 1/T∑_j=1^T A_π^j(h,a) conditioned on h∈ s. Thus does not suffer from the variance of estimating the cumulative regret R^T(s,a), and in the case of infinite capacity, we can prove that, from any (s,a), the estimate W̅^T(s,a) is unbiased as soon as the  (s,a) has been sampled at least once (see Lemma <ref> in the Appendix).
  
  
  
  
  
   §.§ Adaptive Policy Selection
  
  
  
  
  
  dynamically switches between what policy to use based on estimated returns. 
  For every t 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 <ref> over the current epoch's regret only (q_^t(h,a) - v_^t(h)), with different levels of random uniform exploration: ϵ∈0.0, 0.01, 0.05 . 
  (iii) several policies defined by the mean regret, π^t as stated in Algorithm <ref>, also with the same level of exploration.
  (iv) the average policy π̅^t trained via classification.
  The purpose of generating experiences using those policies is to facilitate the problem of exploration and to help produce meaningful data at initial stages of learning before average regrets are learnt.
  Each epoch, the candidate policies are ranked by cumulative return against an opponent playing π̅_^t. The one producing highest rewards is used half of the times. When sub-optimal policies are run for players -i, they are not used to train mean regrets for player i, but can be used to train the critic. Typically (but not always), (ii) produces the best policy initially and allows to bootstrap the learning process with the best data (Fig. <ref>). In later stages of learning, (iii) with the lowest level of ϵ starts providing 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 μ_i^T is constructed by taking the most recent neural network with 50% probability or otherwise sampling one of the past neural networks from replay memory uniformly and modulating it by the above described method. Such sampling method provides both on-policy trajectories for learning q_^j^T(h,a) while also making sure that previously visited states get revisited.
  
  
  
   §.§ Single-Agent Environments
  
  
  
  
  Despite being based on commonly-used multiagent algorithms, it has properties that may be desirable in the single-agent setting.
  First, similar to policy gradient algorithms in the common “short corridor example” <cit.>, stochastic policies are representable by definition, since they are normalized positive mean regrets over the actions. This could have a practical effect that entropy bonuses typically have in policy gradient methods, but rather than simply adding arbitrary entropy, the relative regret over the set of past policies is taken into account.
  
  
  
  Second, a retrospective agent uses a form of directed exploration of different exploration policies <cit.>. Here, this is achieved by the simulation (μ_i^T, π_-i^t), which could be desirable whenever there is overlapping structure in successive tasks. μ_i^T here is an exploratory policy, which consists of a mixture of all past policies (plus random uniform) played further modulated with different amounts of random uniform exploration (more details are given in Section <ref>). Consider a gridworld illustrated in Fig. <ref>(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, a policy would quickly learn to approach it, and finding reward +2 would be problematic. , 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 . For example, (another retrospective policy improvement algorithm <cit.>) has similar properties by keeping its past approximators intact.
  Like , we show an initial investigation of in Atari in Appendix <ref>. Average strategy sampling MCCFR <cit.> 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 as it requires a model of the game.
  
  
  
  
   §.§ Network architecture
  
  
  can be used with both feed-forward (FF) and recurrent neural networks (RNN) (Fig. <ref>(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. The critic was evaluated by feeding both player observations, but to the respective sides of the network. Policies only get their own observations to the respective side of the network. Both sides of the network in Fig. <ref>(a) share weights. More details can be found in Appendix in Section <ref>.
  
  
  
  § EMPIRICAL EVALUATION
  
  
  
  For partially-observable multiagent environments, we investigate Imperfect Information (II-) Goofspiel, Liar's Dice, and Leduc Poker and betting-abstracted no-limit Texas Hold'em poker (in Section <ref>).
  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 on the dice values.
  Leduc poker is a two-round poker game with a 6-card deck, fixed bet amounts, and a limit on betting.
  Longer descriptions of each games can be found in <cit.>.
  We use OpenSpiel <cit.> implementations with default parameters
  for Liar's Dice and Leduc 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 incentive to deviate to their best response
  unilaterally <cit.>, which can be interpreted as an empirical distance from Nash
  equilibrium (reaching Nash at 0).
  
  
  
  
  
  
  
  
  
  We compare empirical convergence to approximate Nash equilibria using a model-free sampled form of
  regression CFR <cit.> (MC-RCFR). Trajectories are obtained
  using outcome sampling MCCFR <cit.>,
  which uses off-policy importance sampling to obtain unbiased estimates of immediate regrets r̂,
  and average strategy updates ŝ, and individual (learned) state-action baselines <cit.>
  to reduce variance.
  A regressor then predicts R̂̅̂ and a policy is obtained via Eq. <ref>,
  and similarly for the average strategy.
  Each episode, the learning player i plays with an ϵ-on-policy behavior policy (while opponent(s) play
  on-policy) and adds every datum
  (s, r̂, π(R̂̅̂)) to a data set, , with a 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, a variant of DeepCFR <cit.> based on outcome sampling (OS-DeepCFR) <cit.>. Our results differ significantly from the OS-DeepCFR results reported in <cit.>, and we discuss differences in assumptions and experimental setup from previous work in Appendix <ref>.
  As with , the input is raw bits with no expert features. 
  We use networks with roughly the same number of parameters as the experiments: feed-forward with 4 hidden
  layers of 128 units with concatenated ReLU <cit.> activations, and train using the Adam optimizer.
  We provide details of the sweep over hyper-parameters in
  Appendix <ref>.
  
  Next we compare to NFSP <cit.>, which combines fictitious play with deep neural network function
  approximators. Two data sets, ^RL and ^SL, store transitions of sampled experience for reinforcement learning and
  supervised learning, respectively. ^RL is a sliding window used to train a best response policy to π̅_-i via DQN.
  ^SL uses reservoir sampling to train π̅_i, 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 an approximate Nash equilibrium. Like and MC-RCFR, NFSP does not use any expert features. 
  
  Convergence
  plots for MC-RCFR and NFSP are shown in Figure <ref>, and for in Figure <ref>.
  NashConv values of are lower (Liar's Dice) and higher (Goofspiel) than NFSP, but significantly lower than MC-RCFR in all cases.
  MC-RCFR results are consistent with the outcome sampling results in DNCFR <cit.>. 
  Both DNCFR and Deep CFR compensate for this problem by instead using external and robust sampling, which require a forward model.
  As with NFSP, and RL more generally, introducing bias to reduce variance may be worthwhile when scaling to large environments.
  So, next we investigate the performance of in a much larger game.
  
  
  
  
   §.§ No-Limit Texas Hold'em
  
  
  
  
  
  We ran on the game of no-limit Texas Hold'em poker, using the common { Fold, Call, Pot, All-in } (FCPA) action/betting
  abstraction. This game is orders of magnitude larger than benchmark games used above (≈ 4.42 · 10^13 information states).
  Action abstraction techniques were used by all of the state-of-the-art Poker AI bots up to 2017.
  Modern search-based techniques of DeepStack <cit.> and Libratus <cit.> still include action abstraction, albeit in the search tree.
  
  Computing the NashConv requires traversing the whole game and querying the network at each information state, 
  which becomes computationally infeasible as the game grows. So, to assess the quality of the resulting policy, we use local best-response (LBR) <cit.>. LBR is an exploiter agent that produces a lower-bound on the exploitability: given some policy π_-i 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 competition-winning abstraction-based Poker bots  were far more exploitable 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-FC12-FCPA34 which has a limited action set of { Fold, Call } for the first two rounds and FCPA for the rest.
  
  We first computed the average return that an -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-FC12-FCPA34 by 867 ± 87 (95% c.i.) . Interestingly, ARMAC learned to beat those two versions of LBR surprisingly quickly. A randomly initialized ARMAC network lost against LBR-FCPA by -704 ± 191 (95% c.i.) and against LBR-FC12-FCPA34 by -230 ± 222 (95% c.i.), but was beating both after a mere 1 hour of training by 561 ± 163 (95% c.i.) and 427 ± 140 (95% c.i.) respectively ( 3 million acting steps,  11 thousand learning steps). [We verified both implementations LBR against random uniform opponent to make sure that the number matched the ones in <cit.>.]
  
  However, counter-intuitively, ARMAC was exploited by LBR-FC which uses a 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. The trend over training time is shown in Figure <ref>.
  To the best of our knowledge, this is the first time a bound on exploitability has been reported for any form of no-limit Texas Hold'em among this class of algorithms.
  
  
  
  § CONCLUSION AND FUTURE WORK
  
  
  was demonstrated to work on both single agent and multi-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; 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 <cit.>.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   
  
  
  plain
  
  
  Appendices
  
  
  
  
  § BASELINE DETAILS AND HYPERPARAMETERS
  
  
  
  For MC-RCFR, we sweep over all combinations of the
  exploration parameter,
  using a (learned) state-action baseline <cit.>,
  and learning rate
  (ϵ, b, α) ∈{ 0.25, 0.5, 0.6, 0.7, 0.9, 0.95, 1.0 }×{True, False}×{ 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 ϵ = 1) presented in <cit.> 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 a set of hyperparameters fixed, in line with <cit.> and  <cit.>: anticipatory parameter η = 0.1, ϵ-greedy decay duration 20M steps, reservoir buffer capacity 2M entries, replay buffer capacity 200k entries, while sweeping over a combination of the following hyperparameters: ϵ-greedy starting value {0.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 was averaged over three seeds. Agents were trained with the ADAM optimizer, using MSE loss for DQN and one gradient update step using mini-batch size 128, every 64 steps in the game.
  
  Finally, note that there are at least four difference in the results, experimental setup, and assumptions between MC-RCFR and OS-DeepCFR reported in <cit.>:
  
  
    * <cit.> uses domain expert input features which do not generalize outside of poker. The neural network architecture we use is a basic MLP with raw input representations, whereas <cit.> uses a far larger network. Our empirical results on benchmark games compare the convergence properties of knowledge-free algorithms across domains.
  
    * The amount of training per iteration is an order of magnitude larger in OS-DeepCFR than our training. In <cit.>, 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.
  
    * MC-RCFR uses standard outcome sampling rather than Linear CFR <cit.>.
  
    * MC-RCFR's strategy is approximated by predicting the OS's average strategy increment rather than sampling from a buffer of previous models.
  
  Our NFSP also does not use any extra enhancements.
  
  
  
  
  § INITIAL INVESTIGATION OF IN THE ATARI LEARNING ENVIRONMENT
  
  
  
  While performance on Atari is not the main contribution, it should be treated as a 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 Revenge, are well-known hard exploration problems. It is interesting to see that 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 may be advantageous for exploration, as it provides naturally stochastic policies which stay 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 as a basic sanity check showing that could in principle work in this domain.
  
  
  
  
  
  
  § TRAINING
  
  
  
  Training is done by processing a batch of 64 of trajectories of length 32 at a 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.
  
  Adam optimized with β_1=0.0 and β_2=0.999 was used for optimization. Hyperparameter selection was done by trying only two learning rates: 5 · 10^-5 and 2 · 10^-4. The results reported use 5 · 10^-5 in all games, including Atari.
  
  
  
  § PROOF OF LEMMA <REF>
  
  
  
  
  
  First, let us notice that 
  
      W_i^T(s,a)   =   ∑_h∈ s∑_t=1^T η^π^t(h)/∑_t=1^T η^π^t(s) A_π^t, i(h,a),
         =   ∑_h∈ s∑_t=1^T η^π^t_-i(h)/∑_t=1^T η^π^t_-i(s) A_π^t, i(h,a)
         =   1/w^T(s)∑_t=1^T ∑_h∈ sη^π^t_-i(h) A_π^t, i(h,a),
  
  where we used the perfect recall assumption in the first derivation, and we define w^T(s) =∑_tη^π^t_-i(s). Notice that w^T(s) depends on the state only (and not on h).
  Now the cumulative regret is:
  
      R_i^T(s,a)   =   ∑_t=1^K q_π^t,i^c(s, a) - v_π^t,i^c(s)
         =   ∑_t=1^T η^π^t_-i(s) ( q_π^t,i(s, a) - v_π^k,i(s) )
         =   ∑_t=1^T η^π^t_-i(s) ∑_h∈ sη^π^t_-i(h)/η^π^t_-i(s)( q_π^t,i(h, a) - v_π^t,i(h) )
         =   ∑_t=1^T
      ∑_h∈ sη^π^t_-i(h) A_π^t,i(h,a)
         =    w^T(s) W_i^T(s,a).
  
  Finally, noticing that regret matching is not impacted by multiplying the cumulative regret by a positive function of the state, we deduce 
      R_i^T,+(s,a)/∑_b R_i^T,+(s,b) = (w^T(s)W_i^T(s,a))^+/∑_b ( w^T(s)W_i^T(s,b))^+ =  W_i^T,+(s,a)/∑_b W_i^T,+(s,b).
  
  
  
  
  
  § UNBIASEDNESS OF Ŵ^T_I(S,A)
  
  
  Consider the case of a tabular representation and define the estimate Ŵ^T_i(s,a) as the minimizer (over W) of the empirical loss defined over N trajectories  
  
      L̂_(s,a)(W)=1/N∑_n=1^N [ W - A_π^j_n,i(h,a)]^2{(h,a)∈ρ^j_n h∈ s},
  
  where ρ^j_n is the n-th trajectory generated by the policy (μ_i^T,π_-i^j_n) where j_n∼ U({1,…, T}). Define N(s,a) = ∑_n=1^N {(h,a)∈ρ^j_n h∈ s} to be the number of trajectories going through (s,a). Then Ŵ^T_i(s,a) is an unbiased estimate of W^T_i(s,a) conditioned on (s,a) being traversed at least once:
  
      [ Ŵ^T_i(s,a) | N(s,a)>0] = W^T_i(s,a).
  
  
  
  
  The empirical loss being quadratic, under the event {N(s,a)>0}, its minimum is well defined and reached for 
  
      Ŵ^T_i(s,a)=1/N(s,a)∑_n=1^N(s,a) A_π^j_n,i(h_n,a),
  
  where h_n∈ s is the history of the n-th trajectory traversing s.
  Let us use simplified notations and write A_n=A_π^j_n,i(h,a){(h,a)∈ρ^j_n h∈ s} and b_n = {(h,a)∈ρ^j_n h∈ s}. Thus
  
      [ Ŵ^T_i(s,a) {∑_m=1^N b_m>0 }]    =   [ ∑_n=1^N A_n {∑_m=1^N b_m>0 }/∑_m=1^N b_m]
         =   ∑_n=1^N [ [  A_n {∑_m=1^N b_m>0 }/∑_m=1^N b_m| ∑_m=1^N b_m] ]
         =   ∑_n=1^N [ [ A_n | ∑_m=1^N b_m]{∑_m=1^N b_m>0 }/∑_m=1^N b_m]
      .
  
  Now, [ A_n | ∑_m=1^N b_m]  = [ A_n | b_n ] [ b_n | ∑_m=1^N b_m] since given b_n, A_n is independent of ∑_m=1^N b_m. Thus
  
      [ Ŵ^T_i(s,a){∑_m=1^N b_m>0 }]    =   ∑_n=1^N [ A_n | b_n ] [ [ [b_n| ∑_m=1^N b_m] {∑_m=1^N b_m>0 }/∑_m=1^N b_m]
         =   ∑_n=1^N [ A_n | b_n ] [  b_n {∑_m=1^N b_m>0 }/∑_m=1^N b_m]
  
  Since ∑_n=1^N [ b_n {∑_m=1^N b_m>0 }/∑_m=1^N b_m] = [ ∑_n=1^N b_n/∑_m=1^N b_m{∑_m=1^N b_m>0 }]=ℙ(∑_m=1^N b_m>0 ), by a symmetry argument we deduce [ b_n {∑_m=1^N b_m>0 }/∑_m=1^N b_m] = 1/Nℙ(∑_m=1^N b_m>0 ) for each n. Thus
  
      [Ŵ^T_i(s,a) | N(s,a)>0 ]   =   [Ŵ^T_i(s,a) | ∑_m=1^N b_m>0 ] 
         =   [Ŵ^T_i(s,a) {∑_m=1^N b_m>0 }]/ℙ(∑_m=1^N b_m>0 )
         =   1/N∑_n=1^N [A_n|b_n] = [A_1|b_1]
  
  which is the expectation of the advantage A_π^j,i(h,a) conditioned on the trajectory ρ^j going through h∈ s, i.e. W^T_i(s,a) as defined in (<ref>). 
  
  
  
  
  
  
  
  
  § NEURAL NETWORK ARCHITECTURE
  
  
  
  The following recurrent neural network was used for no-limit Texas Hold'em experiments. Two separate recurrent networks with shared parameters were used, consuming observations of each player respectively. Each of those networks consisted of a single linear layer mapping input representation to a vector of size 256. This was followed by a double rectified linear unit, producing a representation of size 512 then followed by LSTM with 256 hidden units. This produced an information state representation for each player a_0 and a_1.
  
  Define architecture B(x), which will be reused several times. It consumes one of the information state representations produced by the previously mentioned RNN: h_1 = Linear(128)(x), h_2 = DoubleReLU(h_1), h_3 = h1 + Linear(128)(h2), B(a) = DoubleReLU(h_3).
  
  The immediate regret head is formed by applying B(s) on the information state representation followed by a 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 in the following way.   n_A = Linear(128), n_B = Linear(128), a_0 = n_A(s_0) + n_B(s_1), a_0 = n_B(s_0) + n_A(s_1), h_1=Concat(a_0, a_1), h_2 = B(h_1) and finally q_0(s_1, s_2) and q_1(s_1, s_2) are evaluated by a two linear layers on top of h_2. B(x) shares architecture but does not share parameters with the ones used previously.
  
  
  
  
  