Computer Science
Computer Science-2021.gz:143424
Computer Science
c1f387518be7b94e80fdda1e58cf11de5469f1c3
Optimize Neural Fictitious Self-Play in Regret Minimization Thinking

Optimization of deep learning algorithms to approach Nash Equilibrium remains a significant problem in imperfect information games, e.g. StarCraft and poker. Neural Fictitious Self-Play (NFSP) has provided an effective way to learn approximate Nash Equilibrium without prior domain knowledge in imperfect information games. However, optimality gap was left as an optimization problem of NFSP and by solving the problem, the performance of NFSP could be improved. In this study, focusing on the optimality gap of NFSP, we have proposed a new method replacing NFSP's best response computation with regret matching method. The new algorithm can make the optimality gap converge to zero as it iterates, thus converge faster than original NFSP. We have conduct experiments on three typical environments of perfect-information games and imperfect information games in OpenSpiel and all showed that our new algorithm performances better than original NFSP.


Introduction
With the rapid development of deep reinforcement learning, AI algorithms have already beaten human experts in most perfect-information games like Go [Silver et al., 2016;Silver et al., 2017]. But still there remains challenges to solve imperfect-information dynamic games. In the recent years, many efforts have been made, professional players were beaten by AI in StarCraft2 [Arulkumaran et al., 2019] and Dota (OpenAI-Five) [Berner et al., 2019]. Though such researches exhibit remarkable performances, there are few works to learn an optimal policy from a view of game theory. Game theory is essential for proving and guaranteeing the quality of learned policies.
Game theory [Nash, 1951] is a study about real world competitions. It studies how to maximize the benefits with different and dynamic policies. Nowadays, game theory plays a more and more important role in designing algorithms to solve real-world competition problems such as transaction and traffic control [Sandholm, 2010;Bosanský et al., 2014].
In game theory, Nash Equilibrium [Nash, 1951] would be a choice of optimal policy profile in a game. Nash Equilibrium is a state where all players select their optimal strategies and no one can gain extra profit by changing their policies. Finding and reaching Nash Equilibrium in imperfect information games need particular algorithm designs. There are two commonly used methods to reach Nash Equilibrium: game tree search method and fictitious play (FP) method. Tree search methods such as counterfactual regret minimization (CFR) [Bowling et al., 2015] and Monte Carlo Tree Search (MCTS) [Browne et al., 2012] traverse the game tree and calculate the value of each nodes. Tree search methods always cost a lot of time to sample enough data and require large space to ensure the recursive tree search process. In a different way, fictitious play method improves its knowledge while agents play against with each other, which requires less space.
In fictitious play(FP) [Brown, 1951], a player iteratively improves its best response strategy by fighting against its opponents in timesteps of simulated games. Then the average strategy of its history best responses will converge to Nash Equilibrium after enough iterations. Heinrich et al. [Heinrich et al., 2015] extended the FP algorithm to solving extensiveform games and then introduced a sampling based machine learning approach called Fictitious Self-Play (FSP) to make training easier. FSP updates the average strategy with sampling based supervised learning methods and approximates the best response with reinforcement learning methods. Reinforcement learning have been demonstrated to achieve excellent results on a range of complex tasks including games [Oh et al., 2016] and continuous control [Schulman et al., 2015;Levine et al., 2016].
Heinrich and Silver [Heinrich and Silver, 2016] developed FSP with deep neural network. Neural Fictitious Self-Play, which introduce Deep Q-network (DQN) [Mnih et al., 2015;Meng et al., 2018] to approximate its best response and supervised learning network to update its average strategy. In NFSP, player produce best responses according to a mixture of opponents' average policies and best responses. NFSP is the first end-to-end reinforcement learning method that learns approximate Nash Equilibrium in imperfect information games without any prior knowledge like ELF [Tian et al., 2017;Kawamura and Tsuruoka, 2019].
Because NFSP update strategies according to opponents' average strategy iteratively, there exists optimality gap which best response (reinforcement learning) needs to improve at every update. In this study, we find and prove that the optimality gap could be transferred into a monotonical form by applying regret matching [Sergiu et al., 2000] methods. In practice, we use Advantage-based Regret Minimization (ARM) [Jin et al., 2018] as the regret matching method replacing the computation of NFSP's best response We have conduct experiments in 3 different environments provided by OpenSpiel [Lanctot et al., 2019] and all experiments show that the new algorithm outperforms NFSP and converges faster than NFSP.

Preliminaries
In our work, intending to reduce optimality gap, we apply regret matching method to NFSP's best response computation and make best response optimized at every update iteration. Optimized best response would improve behavioural strategy and then make it better of approaching nash equilibrium.
Therefore, in this section we will briefly introduce some backgrounds of our method and strategy update process of NFSP. At last, we will point out the focus of our paper, optimality gap.

Backgrounds
This subsection provides some background knowledge of our method, including extensive-form game and best response.
Extensive-form game is a model of sequential interaction involving multiple agents. Each player's goal is to maximize his payoff in the game. A player's behavioural strategy π i determines a probability distribution over actions given an information state. Each player choose a behavioural strategy while playing games. We assume games with perfect recall, i.e. each player's current information state s i t implies knowledge of the sequence of his information states and actions, s i 1 , a i 1 , s i 2 , a i 2 , . . . , s i t , that led to this information state. A strategy profile π = (π 1 , . . . , π n ) is a collection of strategies for all players. π −i refers to all strategies in π except π i . Based on the game's payoff function R, R i (π) is the expected payoff of player i if all players follow the strategy profile π.
The set of best response of player i to their opponents' strategies π −i is b i (π −i ) = arg max π i (R i (π i , π −i )). The set of -best response to the strategy profile π −i is defined as A Nash equilibrium of an extensive-form game is a strategy profile π such that π i ∈ b i (π −i ) for all player i. An -Nash equilibrium is a strategy profile π that π i ∈ b i (π −i ) for all player i.

Neural Fictitious Self-Play (NFSP)
Neural Fictitious Self-Play (NFSP) is an effective end-to-end reinforcement learning method that learns approximate Nash Equilibrium in imperfect information games without any prior knowledge. NFSP's strategy consists of two strategies: best response and average strategy. Average strategy averages past responses and is the exact strategy to approach Nash Equilibrium, equivalent to behavioural strategy. NFSP iteratively updates best response and average strategy to approach approximate Nash Equilibrium. Our method replaces best response computation in Neural Fictitious Self-Play (NFSP) with regret matching, based on the strategy update rule of NFSP. In this subsection, we will introduce NFSP and provide details of the strategy update process of NFSP. For a more detailed exposition we refer the reader to [Heinrich et al., 2015;Heinrich and Silver, 2016].
NFSP extends fictitious self-play (FSP) with deep neural networks based on fictitious play (FP) theorem. In NFSP, fictitious players choose best response to their opponents' average behaviour. NFSP approximates best response in extensive-form games, it replaces the best response computation and the average strategy updates with reinforcement learning and supervised learning respectively. NFSP agent's strategy update process at iteration t + 1 follows the rule of generalized weakened fictitious play [Leslie and Collins, 2006] which is guaranteed to approach approximate Nash Equilibrium: where B i is the -best response of player i, Π i is the average strategy of player i, and α t+1 < 1 is a mix probability of best response and average strategy. As figure shows, NFSP maintains two strategy networks, B t+1 to learn the best response to the average policy Π t , and Π t+1 to learn the average policy of the best response B t+1 and Π t in a determined proportion.
The resulting NFSP algorithm is as follows. Each agent i has its reinforcement learning network B i as its best response, supervised learning network Π i as its average strategy, and supervised learning replay buffer M i SL . At the very start of a game, each agent decides whether it chooses B i or Π i as its current strategy in this episode, with probability α and 1 − α respectively. At each timestep in this episode, agents sample an action from the selected strategy and if the selected startegy is best response, a tuple of observation and action taken is stored in M i SL . B i is trained as it maximizes the expected cumulative reward against Π −i and Π i is trained as it demonstrates the average strategy over the past best responses. The two networks update after a set number of episodes if the replay buffer size is bigger than a certain number.
Though NFSP is an efficient end-to-end algorithm, there still exists a problem of optimality gap that makes convergence not fast as expected.
Optimality gap refers to -best response at every update. It is expected that optimality gap monotonically reduces as iteration goes, but is actually asymptotically decaying according to [Heinrich et al., 2015]. In the result, optimality gap is not reducing in a monotonical way. In section 3, we explain why optimaligy gap reduces asymptotically and propose a method to make it reduce monotonically, faster than original method.

Optimization
In this section we will discuss details of optimality gap under NFSP's stratrgy update rule, introduce the method to make optimality gap reduce monotonically and provide theoretical guarantee.

Optimality Gap
In this subsection, we will explain the detail of optimality gap of approximated -best response in NFSP. [Heinrich et al., 2015] has dicussed the optimality gap and left a corollary as corollary 1. Theorem 1. Let Γ be a two-player zero-sum extensive-form game with maximum payoff range R = max π R 1 (π) − min π R 1 (π). Consider a fictitious play proess in this game. Let Π t be the avearage strategy profile at iteration t, B t+1 a profile of t -best responses to Π t , and Π t+1 = (1 − α t+1 )Π t +α t+1 B t+1 the usual fictitious play update for some stepsize α t+1 ∈ (0, 1). Then for each player As the authors mentioned in [Heinrich et al., 2015], the value [(1 − α t+1 ) t + α t+1 R] bounds the absolute amount by which reinforcement learning needs to improve the best response profile to achieve a monotonic decay of the optimality gap t . The authors relies t decaying asymptotically on α t → 0.
The optimization of optimality gap is the focus of our work. We find that optimality gap could be reduced monotonically by utilizing regret matching method, thus let the optimality gap decay in a faster way than original NFSP, leading to better performance.

Method and Proof
Focusing on optimality gap , we have found a new method that can make decay monotonically instead of asymptotically by replacing NFSP's best response computation with regret matching method. Optimality gap is formed in a way of regret ω and by making regret decaymonotonically, optimality gap reduces monotonically. Regret is the mdimension regret vector of the algorithm at a specified iteration, where A is the action profile on this information state and m is the dimension of actions that could be taken. Regret has a similar definition with optimality gap : , the overall regret of ω forms optimality gap .
Therefore, minimizing the overall regret of ω could lead to the convergence of optimality gap.
Here we provide our proof of convergence of regret: At first, we would like to provide two definitions about potential function and P -regret-based strategy as as definition 1 and definition 2. They are basis of our proof. Definition 1. Given D = R m the closed nagative orthant associated to the set of moves of player 1 and R the regret space. P is a potential function for D if it satisfies the following set of conditions: |∇P (ω)| ∈ X whereverω / ∈ D and ϕ(ω) = X otherwise, X is the set of probabilities of actions, and |∇P (ω)| stands for the L 1 norm of ∇P (ω).
Note that the update of ϕ(ω) is the same as regret matching method, and the P -regret-based strategy can also refer to the strategy update rule of NFSP if ϕ(ω) forms the best response.
Under potential function ∇P (ω) = 2ω + and ϕ(ω), we provide theorem 2 of blackwell's framework. This theorem is summarized from [Benaïm et al., 2006], which has been proved that if theorem 2 is satisfied, the strategy's regret will converge to 0.
Theorem 2. Blackwell's framework makes the P -regretbased strategy approach the orthan D. In other words: If the potential function is defined as P (ω) = k (ω + k ) 2 , and the strategies of the players are independent, and the average strategy of a player statisfies Π t+1 − Π t = 1 t+1 [ϕ t+1 − Π t ], then the regret ω converges to zero.

Now that the update process of NFSP is
t+1 , we replace best response B with ϕ. The blackwell's framework is then satisfied, and as a result, regret ω is able to converge to zero.
Not like corollary 1 relying optimality gap 's decay on the decay of α, our method applies regret matching to satisfy blackwell's framework (theorem 2) to make regret and optimality gap converge to zero, which has a stronger guarantee than R and the decay of α.
Involving regret matching method could lead our strategy update to a stronger guarantee to converge and reach smaller regret every iteration, which is not guaranteed by NFSP framework itself. Therefore, we find a possability to compute our best response using regret minimization based method.

Introducing Regret Matching to NFSP
This section is about the details of our method and algorithm. As is proved in section 3, our method is to replace best response computation with regret matching method. We applay Advantage-based Regret Minimization (ARM) [Jin et al., 2018]--a regret-matching-based reinforcement learning algorithm--as the regret matching method. It is simple to apply ARM to NFSP for ARM is a deep reinforcement learning method, similar to DQN in NFSP. In the fictitious self-play update process, we let ARM produce best response to the opponents' average strategy.
To make it clear, unlike NFSP, ARM follows a strict update rule of fictitious self-play. At iteration k, we sample from a mixture policy of (1 − α) Π k + αB k+1 , where Π k is the average policy at iteration k, B k+1 is the best response to Π k (produced by ARM). Then ARM learns and optimizes the best policy B k+2 to Π k+1 = (1 − α) Π k + αB k+1 , which is the average policy profile of next sampling iteration. Note that the α is a fixed number corresponding to the anticipatory parameter α of NFSP. We maintain numbers counting the recorded episodes and the update iterations. The number of episode refers to the hands of games, when a game is played and finished, the number of episode counts. The number of update iterations refers to the iteration of the algorithm's update. The number of update iteration counts when a particular number of timesteps are recorded, at the same time, the two networks will update to new best response and new average policy. After 10K episodes or an update iteration, the evaluation is executed.
As for ARM's update detail, we would like to refer the reader to [Jin et al., 2018].
Our algorithm is summarized in Algorithm 1, where RL refers to reinforcement learning and SL refers to supervised learning.

Experiments
In this section, we will describe details of the experiments and make some analysis about the results.
We aim to evaluate our method on both perfect-information games and imperfect-information games, considering evaluating the applicability on these two different types of games. Since the optimality gap is produced in -best response, the exploitability would somehow be a form of ( 1 + 2 )/2 where ( 1 is player1's optimality gap. Our method reachs smaller optimality gap at every update iteration, which means the exploitability will be lower than original NFSP.
We have conducted several experiments mainly in three multi-agent environments in OpenSpiel, published by Deepmind. OpenSpiel is a platform containing a huge amount of multi-agent games like Go, Leduc Poker, breakthrough, etc, where algorithms can play against each other. In addition to several evaluating methods for algorithms, the platform also provides a substantial number of typical algorithms from Observe initial information state s 1 and reward r 1 10: for t = 1, T do 11: Sample action a t from policy π 12: Execute action a t in game 13: Observe reward r t+1 , information state s t+1 14: Store (s t , a t , r t+1 , s t+1 ) in M RL

15:
if agent follows best response policy then  The three environments we chose are Leduc Poker, Liar's Dice and Tic Tac Toe. Introductions of these environments are along with the details of each experiment.

Experiments on Leduc Poker
We have examined exploitability and winning-rate of the different algorithms in Leduc Poker. The curves of exploitability show that our method converges faster and better than NFSP, and is more stable than ARM.
Leduc Poker is a small poker variant similar to kuhn poker [Kuhn, 1950]. With two betting rounds, a limit of two raises per round and 6 cards in the deck it is much smaller. In Leduc Poker, players usually have 3 actions to choose from, namely fold, call, raise,and depending on context, calls and raises can be referred to as checks and bets respectively. The betting history thus can be represented as a tensor with 4 dimensions, namely player, round, number of raises, ac- tion taken. In Leduc Poker which contains 6 cards with 3 duplicates, 2 rounds, 0 to 2 raises per round and 2 actions, the length of the betting history vector is 30, considering the game will end if one player folds, the actions in information state is reduced from 3 to 2. We trained the 3 algorithms separately to get their models and curves of exploitability, then let our trained algorithm play against trained NFSP to get the winning rate data to evaluate the performance of playing. While training, the hyper parameters of NFSP are set corresponding to the parameters mentioned in [Heinrich and Silver, 2016], which are the best settings of NFSP in Leduc Hold'em. The curves of exploitability while training is shown in Figure 3. As the curves show, to reach the same exploitability, our method costs much less time than original NFSP. Additionally, It is obvious that origin ARM's strategy is highly exploitable, our work successfully transfers ARM from single agent imperfect-information games to zero-sum two-player imperfect information games. As well as exploitability, the result of agents playing against each other is also examined to evaluate the performance of algorithms. Therefore, in this part we let trained algorithms play against each other. To test the player position of the game whether an affact factor, we conduct 2 experiments. In each experiment, algorithms play for 40M hands of Leduc Poker and payoffs are recorded. Table 1 shows the winning rate of player1 and loss rate, average payoffs as well. Note that in experiment 1, NFSP gets winning rate 46.7%, and average payoff 0.01 (in zero-sum games), in experiment 2, our method gets winning rate 43.2% and average payoff 0.15, it is obvious that our method is more likely to reduce loss when loses and maximize gains when wins.

Experiments on Liar's Dice
Experiment conduct on Liar's Dice is to evaluate if our method can outperform NFSP on other imperfect information environments. Liar's Dice is a 1-die vesus 1-die variant of the popular game where players alternate bidding on the dice vlaues. The experiment design is similar to Leduc. Since the two turn-bases imperfect information game is similar while playing, we conduct this experiment following the settings in Leduc section.
The result of this experiment is also obvious. The training exploitability is as figure 4 shows. Our method shows a greate advantage over NFSP, not only our method converges faster than the baseline, but also outperforms the baseline.

Experiments on Tic Tac Toe
We have examined exploitability and winning-rate of the different algorithms in Tic Tac Toe to see the algorithms' performance under perfect-information games, what's more, we have also examined the average reward playing against random agents every 1K episodes. In practice it presents an apparent difference between algorithms as this perfectinformation board game environment is not that easy to be diturbed by random actions. The exploitability curves also show that our method converges faster and better than NFSP. In the meanwhile, our method outperforms NFSP at any player position of the two-player game.
Tic Tac Toe is a popular perfect-information board game. The game consists of a three by three grids and two different types of token, X and O. Each of the two players places his own token in order. The goal is to create a row of three tokens, which can be very tricky with both players blocking each other's token to prevent each one from making a threerow of tokens. Once the three by three grids are full with tokens and nobody has created a row of three token, then the game is over and no one wins. In implementation, at the end of a game, an agent gets 1 if he wins and -1 for another agent, gets 0 if the game draws.
Apparently, there exsits an advantage of playing in first place. While the first player intends to form the three-tokenline all the time, the second player often has to defend from player1, therefore, for player2 the best strategy is to draw sometimes. That's why we consider draw rate when the algorithm plays at in disadvantageous position. We have trained our algorithm and NFSP in tic tac toe and the result is shown in Figure 5. It is clear that our methods outperforms NFSP in exploitability convergence.
Since there exists an advantage of player who places his token first, we decided to examine the learning curves of the 2 conditions. A learning curve is a sequence of average rewards produced by playing against random agent at every 1K episodes. Figure 6 shows the learning curves with the first player position and Figure 7 shows the learning curves with the second player position. It is easy to see that our method performs better than NFSP in this type of game, including stability, convergence speed. After the algorithms are well trained, we let them fight against each other in different positions. Table 2 is the result of fighting part. Obviously, when our method plays at the player 1 position, the average reward could reach as high as 0.80 and the winning rate reaches 83.7%. The more exciting thing is that even the first-player-advantage exists when our method plays at player 2 position, the average reward could still reach 0.658 and the winning rate is 67.4% of wins and 30.9% of draws. Note that considering the first-player-  advantage, the goal for player2 is to win or to prevent player1 from winning. Therefore, a proportion of draw rate would be taken into account, which means the actual winning rate of player2 is more than pure winning rate. But even we use pure winning rate to evaluate the player 2 algorithm, our method still wins more than 50% times.

Conclusion
In this paper, we focus on the optimality gap of NFSP and prove that this value could be guaranteed to decay monotonically by utilizing regret minimization methods. Following the proof, we present our method by placing best response computate of NFSP with ARM. In our method, ARM applies regret matching to calculating best response to the opponents' strategy. As a result of this combination, the convergence speed is fastened and in practice the performance of our method is also better than original NFSP implemented in OpenSpiel.
Our work is an attempt to combine the two mainstream solutions Self-Play and CFR to approach approximate Nash equilibrium. It is proved that the performance of self-play methods could be optimized by utilizing a regret matching methods. That is, the application of regret minimization method to FSP framework algorithms is effective and could certainly increase the performance.
There is still a lot remained to explore. Our further study is to evaluate more algorithms combining FSP and regret minimization reinforcement learning methods. Moreover, ARM applies to image-input games like Minecraft, Doom mentioned and we could also try to extend our methods to imageinput environments, thus make it suitable for a larger range of games.