Optimize Neural Fictitious Self-Play in Regret Minimization Thinking

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 $\pi^{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},\ldots,s^{i}_{t}$, that led to this information state. A strategy profile $\pi=(\pi^{1},\ldots,\pi^{n})$ is a collection of strategies for all players. $\pi^{-i}$ refers to all strategies in $\pi$ except $\pi^{i}$. Based on the game’s payoff function $R$, $R^{i}(\pi)$ is the expected payoff of player $i$ if all players follow the strategy profile $\pi$.

The set of best response of player $i$ to their opponents’ strategies $\pi^{-i}$ is $b^{i}(\pi^{-i})=\arg\max_{\pi^{i}}(R^{i}(\pi^{i},\pi^{-i}))$. The set of $\epsilon$-best response to the strategy profile $\pi^{-i}$ is defined as $b^{i}_{\epsilon}(\pi^{-i})=\{\pi^{i}:R^{i}(\pi^{i},\pi^{-i})\geq R^{i}(b^{i}(\pi^{-i}),\pi^{-i})-\epsilon\}$ for $\epsilon>0$. A Nash equilibrium of an extensive-form game is a strategy profile $\pi$ such that $\pi^{i}\in b^{i}(\pi^{-i})$ for all player $i$. An $\epsilon$-Nash equilibrium is a strategy profile $\pi$ that $\pi^{i}\in b^{i}_{\epsilon}(\pi^{-i})$ for all player $i$.

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:

$\Pi^{i}_{t+1}\in(1-\alpha_{t+1})\Pi_{t}^{i}+\alpha_{t+1}B^{i}_{\epsilon_{t}}(\Pi_{t}^{-i})$

where $B^{i}_{\epsilon}$ is the $\epsilon$-best response of player $i$, $\Pi^{i}$ is the average strategy of player $i$, and $\alpha_{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 $\Pi_{t}$, and $\Pi_{t+1}$ to learn the average policy of the best response $B_{t+1}$ and $\Pi_{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 $\Pi^{i}$ as its average strategy, and supervised learning replay buffer $\mathcal{M}^{i}_{SL}$. At the very start of a game, each agent decides whether it chooses $B^{i}$ or $\Pi^{i}$ as its current strategy in this episode, with probability $\alpha$ and $1-\alpha$ 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 $\mathcal{M}^{i}_{SL}$. $B^{i}$ is trained as it maximizes the expected cumulative reward against $\Pi^{-i}$ and $\Pi^{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 $\epsilon$ refers to $\epsilon$-best response at every update. It is expected that optimality gap $\epsilon$ monotonically reduces as iteration goes, but $\epsilon$ 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.

In this subsection, we will explain the detail of optimality gap $\epsilon$ of approximated $\epsilon$-best response in NFSP. Heinrich et al. (2015) has dicussed the optimality gap $\epsilon$ and left a corollary as corollary 1.

As the authors mentioned in Heinrich et al. (2015), the value $[(1-\alpha_{t+1})\epsilon_{t}+\alpha_{t+1}\overline{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 $\epsilon_{t}$. The authors relies $\epsilon_{t}$ decaying asymptotically on $\alpha_{t}\rightarrow 0$.

The optimization of optimality gap $\epsilon$ 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.

Focusing on optimality gap $\epsilon$, we have found a new method that can make $\epsilon$ decay monotonically instead of asymptotically by replacing NFSP’s best response computation with regret matching method. Optimality gap $\epsilon$ is formed in a way of regret $\omega$ and by making regret decaymonotonically, optimality gap reduces monotonically.

Regret $\omega=\{R^{i}(a,\pi^{-i})-R^{i}(\pi^{i},\pi^{-i})\}_{a\in A}$ is the $m$-dimension 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 $\epsilon$: $\epsilon\geq R^{i}(b^{i}_{\epsilon}(\pi^{-i}),\pi^{-i})-R^{i}(\pi^{i},\pi^{-i})$, the overall regret of $\omega$ forms optimality gap $\epsilon$.

Therefore, minimizing the overall regret of $\omega$ 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.

Note that the update of $\varphi(\omega)$ is the same as regret matching method, and the $P$-$regret$-$based$ $strategy$ can also refer to the strategy update rule of NFSP if $\varphi(\omega)$ forms the best response.

Let $\omega^{+}$ be the vector with components $\omega^{+}_{k}=max(\omega_{k},0)$. Define potential function $P(\omega)=\sum_{k}(\omega^{+}_{k})^{2}$. Note that $\nabla P(\omega)=2\omega^{+}$, hence, $P$ satisfies the conditions (i)-(iv) of definition 1.

Under potential function $\nabla P(\omega)=2\omega^{+}$ and $\varphi(\omega)$, 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.

Now that the update process of NFSP is $\Pi_{t+1}-\Pi_{t}=\alpha_{t+1}[B_{\epsilon_{t+1}}-\Pi_{t}]$ where $\alpha_{t+1}=\frac{1}{t+1}$, we replace best response $B$ with $\varphi$. The blackwell’s framework is then satisfied, and as a result, regret $\omega$ is able to converge to zero.

Not like corollary 1 relying optimality gap $\epsilon$’s decay on the decay of $\alpha$, 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 $\overline{R}$ and the decay of $\alpha$.

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.

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, action 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.

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.

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 perfect-information 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 three-row 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-token-line 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.