Modeling Strong and Human-Like Gameplay with KL-Regularized Search

Athul Paul Jacobequal,fair,mit
David J. Wuequal,fair
Gabriele Farinaequal,cmu
Adam Lererfair
Hengyuan Hufair
Anton Bakhtinfair
Jacob Andreasmit
Noam Brownfair

fairMeta AI Research, New York, NY, USA
mitCSAIL, MIT, Cambridge, MA, USA
cmuSchool of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA

Athul Paul<EMAIL_ADDRESS>David J<EMAIL_ADDRESS>Gabriele<EMAIL_ADDRESS>Noam<EMAIL_ADDRESS>
Machine Learning, ICML

*Equal Contribution.

We consider the task of building strong but human-like policies in multi-agent decision-making problems, given examples of human behavior. Imitation learning is effective at predicting human actions but may not match the strength of expert humans, while self-play learning and search techniques (e.g. AlphaZero) lead to strong performance but may produce policies that are difficult for humans to understand and coordinate with. We show in chess and Go that regularizing search based on the KL divergence from an imitation-learned policy results in higher human prediction accuracy and stronger performance than imitation learning alone.
We then introduce a novel regret minimization algorithm that is regularized based on the KL divergence from an imitation-learned policy, and show that using this algorithm for search in no-press Diplomacy yields a policy that matches the human prediction accuracy of imitation learning while being substantially stronger.

§ INTRODUCTION

Self-play AI algorithms have matched or exceeded expert human performance in many games, such as chess [Campbell et al., 2002, Silver et al., 2018], Go [Silver et al., 2016, Silver et al., 2017], and poker [Moravčík et al., 2017, Brown & Sandholm, 2017, Brown & Sandholm, 2019]. However, the resulting policies often differ markedly from how humans play [McIlroy-Young et al., 2020].
This is a serious problem for human-computer interactions that involve cooperation rather than purely competition. In such settings, modeling the other participants accurately is important for success. For example, it is important for a self-driving car at a four-way stop sign to conform to existing human conventions rather than its own self-play solution to the problem [Lerer & Peysakhovich, 2019]. Moreover, even in purely adversarial games, the alien nature of AI policies makes it difficult for humans to understand and learn from superhuman bots.

The classic approach toward modeling human behavior is imitation learning (IL) on human data. However, evidence in multiple games indicates that IL on expert human data produces policies that are much weaker than actual expert human play in domains with complex strategic planning.
In this paper, we study the problem of producing policies that are both strong and human-like
in games with complex strategic planning like chess, Go, Hanabi, and Diplomacy. In all four, we find that conducting search with KL-regularization towards an IL policy matches or exceeds the prior state of the art for prediction accuracy of expert humans while also better matching expert human performance.

In Section <ref>, we show that Monte Carlo tree search (MCTS) with a human imitation-learned policy prior and value function surpasses prior state-of-the-art results for human prediction accuracy in chess and Go. As explained by Grill et al., 2020, standard MCTS with a policy prior can be viewed as a form of KL-regularized search, optimizing a value function subject to a KL-divergence term with that prior. Although MCTS has been extensively studied for developing strong agents, it has been explored much less in the context of developing human-like agents.

Section <ref> builds on these findings and shows how to generalize them to a class of imperfect-information games
(in which ordinary MCTS is unsound and cannot be applied) via a new algorithm for KL-regularized regret minimization.
We show that existing regret minimization algorithms achieve low accuracy in predicting expert human actions in no-press Diplomacy. We then introduce the first regret minimization algorithm to incorporate a cost term proportional to the KL divergence between the search policy and a human-imitation learned anchor policy. We call this algorithm policy-regularized hedge, or piKL-hedge. We prove that piKL-hedge converges to an equilibrium in which all players' policies are optimal given the joint policies of the players and the cost of deviating from the anchor policy. We then present results in no-press Diplomacy showing that piKL-hedge produces policies that predict human actions as accurately as imitation learning while also improving head-to-head performance in a population of prior agents.

Appendix <ref> additionally shows that applying KL-regularization toward a human IL policy in the search algorithm SPARTA [Lerer et al., 2020] produces similar or better human prediction accuracy while greatly improving performance in the benchmark domain of Hanabi [Bard et al., 2020].

Our experiments demonstrate the benefits of KL-regularized search in all four of chess, Go, no-press Diplomacy, and Hanabi to producing agents that are simultaneously more human-like and closer in strength to actual human experts than purely imitation-learned models.

§ PRELIMINARIES

We study the problem of learning policies for multiplayer games. Here we briefly introduce the key ingredients of both classes of games we study; <ref> and <ref> give a more formal presentation tailored to individual game types and learning algorithms.

An ($N$-player) game is defined by a state space $S$, an action space $A$, a (deterministic) transition function $T : S \times A^N \to S$, and a collection of reward functions $u_i$. We model the behavior of each player in a game as a policy $\pi_i : S \to \Delta(A)$ (a distribution over actions given states). In every round of a game, each player observes a (possibly incomplete) view $s_i^t$ of the current state. One or more players select actions $a_i^t \sim \pi_i(\cdot \mid s_i^t)$,
then each player receives a reward $u_i^t(s^t, \mathbf{a}^t = a_1^t, \ldots, a_n^t)$, and the game transitions into a new state $s^{t+1} = T(s^t, \mathbf{a}^t)$.
Each player $i$ aims to maximizes its expected reward, and the optimal policies for doing so may depend on the policies $\pi_{-i} = \{ \pi_1, \ldots, \pi_{i-1}, \pi_{i+1}, \ldots, \pi_N \}$ of the other players.

The sequential decision-making problem described above is extremely general, and in this paper we focus on two special cases. In perfect-information games, players make moves sequentially (e.g., $u^1$ and $s^2$ depend only on $a_1$, $u^2$ and $s^3$ depend only on $a^2$, etc.). Many important games, including chess and Go, fall into this category. Next, we study a more general class of imperfect-information, simultaneous-action games that make no assumptions about the dependence of different $u_i$ and $T$ on $\mathbf{a}$; here we focus on games with only a single round, also called matrix games.
Owing to the large differences between these two settings, the tools for computing strong policies are quite different. The remainder of this paper accordingly offers a deeper exploration of each class of games: perfect-information games in <ref> and imperfect-information games in <ref>.

the above can probably be cleaned up / made more consistent with the existing literature / our notation in this paper. the treatment of imperfect information in particular is currently sloppy. but I think this is roughly what we're looking for

§ PERFECT-INFORMATION GAMES: POLICY REGULARIZATION IN MONTE CARLO TREE SEARCH

In this section, we focus on developing strong human-like agents for perfect-information games. Monte Carlo tree search (MCTS) has been highly successful for developing strong, but not necessarily human-like agents in this setting, and is a key component of general learning algorithms such as AlphaZero and MuZero capable of achieving superhuman performance in chess, Go, and similar games [Silver et al., 2018, Schrittwieser et al., 2020]. By contrast, for developing human-like agents, the best prior human move prediction accuracies for chess and Go were all achieved with pure imitation learning on human data [McIlroy-Young et al., 2020, Cazenave, 2017, Silver et al., 2017].

The state of the art for predicting human moves in chess is the Maia engine created by McIlroy-Young et al., 2020 via pure imitation learning without any search.
However, this approach appears to be of limited effectiveness for modeling sufficiently strong humans. Although the weakest Maia models at low temperatures appear to outperform the players they imitate (due to “averaging away” of the imitated players' individual idiosyncratic mistakes [Anderson et al., 2021]) each successive model on data from stronger players improves by much less than the players improve.[See ratings data at https://lichess.org/@/maia1, https://lichess.org/@/maia5, https://lichess.org/@/maia9] The strongest model, trained to predict human 1900-1999 rated players, even with low temperature appears to be clearly below a 1950-average level of performance in all but the minority of bullet-speed games (in which very little time is available for planning and players are forced to rely more heavily on intuition).
Similarly, in Go, pure imitation-learning agents have not exceeded mid-expert level on various online servers despite being trained on top-expert and master-level games [Cazenave, 2017].

In contrast, search-based reinforcement learning (RL) agents such as AlphaZero that do not use a human policy prior play at a superhuman level, but often in non-human ways that humans find difficult to understand even when given access to interactively query and inspect the agent's analysis [Silver et al., 2017, Egri-Nagy & Törmänen, 2020].

However, we show in both chess and Go that if the human-learned model is used in MCTS with appropriate parameters, MCTS outperforms those models' human prediction accuracy while simultaneously reducing the shortcomings in those models' strength.

§.§ Background

We consider sequential games where each player $i$ alternatively chooses action $a$ from a policy $\pi_i$ where, $a \sim \pi_i(\cdot\mid s)$. Each action deterministically transitions the game into a new state $s' = T(s, a)$ and gives rewards $u_i(s, a)$. Notationally, we may elide the player $i$ in some places when it is clear that $i$ is the next player to move in the state being considered.

For this work, following Silver et al., 2016, we implement one of the most common modern forms of MCTS, which uses a value function $V$ predicting the expected total future reward
$V_i(s) = \mathbb{E} [\sum_t u_i(s_t,a_t) \mid \pi_1, \pi_2, s_0=s]$ and a policy prior $\tau$ (typically both the outputs of a trained deep neural net) and attempts to produce an improved policy $\pi$.

Each turn, MCTS builds a game tree over multiple iterations rooted at the current state. Each iteration $t$, MCTS explores a single path down the tree by simulating at each successive state $s$ with player $i$ to move the action:

\begin{equation}
\argmax_a \, Q(s,a) + c_\text{puct}\tau(s,a)\frac{\sqrt{\sum_b N(s,b)}}{N(s,a)+1}
\end{equation}

where $Q(s,a)$ is the estimated expected future reward for $i$ from playing action $a$ in state $s$, the visit count $N(s,a)$ is the number of times $a$ has been explored from $s$, $\tau(s,a)$ is the prior policy probability, and $c_\text{puct}$ is a tunable parameter trading off exploration versus exploitation.

Upon reaching a state $s_t$ not yet seen, MCTS queries the value function $V_i(s_t)$ for each player $i$, and based on $V_i(s_t)$ and any intermediate rewards received, updates all $Q(s,a)$ estimates on the path traversed. The final agent policy is $\pi(s,a) = N(s,a)/\sum_b N(s,b)$ where $s$ is the root state, or optionally we may also have $\pi(s,a) \sim N(s,a)^{1/T}$ where $T$ is a temperature parameter. See also Appendix <ref> for a fuller description of MCTS.

Grill et al., 2020 show that the agent policy $\pi$ computed by this form of MCTS is an approximate solution to the optimization problem:

\begin{equation}
\argmax_{\pi} \sum_a Q(s,a)\pi(s,a) + \lambda \KL{\tau}{\pi}
\end{equation}

where $\lambda \sim c_\text{puct}\sqrt{N}$ and $N$ is the total number of iterations.

In other words, at every node of the tree recursively, MCTS implicitly optimizes its expected future reward subject to KL regularization of its policy towards the prior policy $\tau$ with strength controlled by $\lambda$. For any fixed computational budget $N$, we can therefore tune $c_\text{puct}$ to vary the strength of that prior, with $c_\text{puct} = \infty$ approximating the prior policy before search, and $c_\text{puct} \rightarrow 0$ approaching a greedy argmax of the $Q$ value estimates.

If our goal is a strong human-like agent rather than solely a strong agent, and the KL-regularizing policy is learned from human data, then that policy serves not just as a prior, but also as an anchor policy that regularizing towards is desirable in and of itself. With good choice of $c_\text{puct}$, MCTS can improve that policy while remaining close to human. Our experiments confirm that MCTS improves on the strength and human prediction accuracy of the best existing models in both chess and Go.

§.§ Experiments in Chess and Go

2*Game     2*Model     2* Predicting     2*0.9cm  RawModel     5cModel + MCTS
$c_\text{puct}\!=\!10$                        ${5}$     ${2}$     ${1}$     ${0.5}$

Chess                         Maia1100                            Rating 1100                               51.1                   51.2                                          51.3      50.8      49.5      47.4

Chess                         Maia1500                            Rating 1500                               52.4                   52.7                                          52.9      52.8      51.9      50.1

Chess                         Maia1900                            Rating 1900                               53.2                   53.6                                          54.0      54.3      53.8      52.4

Go                            [Cazenave, 2017]           GoGoD                                     54.7

Go                            <cit.>                 GoGoD                                     55.3

Go                            [Wang et al., 2017]                 GoGoD                                     57.7

Go                            Ours                                GoGoD                                     57.8                   58.1                                          58.3      58.5      58.1      57.1

% top-1 test accuracy predicting human moves in chess and Go using MCTS with 50 playouts and various $c_\text{puct}$, or raw model without MCTS, equivalent to infinite $c_\text{puct}$. In chess, first 10 ply per game and moves with < 30s time left excluded, similar to [McIlroy-Young et al., 2020]. Standard error is approx 0.1 or less on all values. MCTS on top of current state-of-the-art models improves human prediction accuracy significantly.

lbl=[rounded corners=.3mm,draw=gray!40,fill=white,inner ysep=.3mm]
at (0, 0) ;
[lbl] at (-17.5mm, 4.5mm) .8$c_\text{puct}$;
[lbl] at (20mm, -1mm) .6Model;

Improvement in top-1 accuracy of Maia1900 in Chess or our GoGoD model in Go using MCTS, plotted versus winrate of MCTS against the raw model (temperature 1). Error bars indicate $1$ standard error. Many $c_\text{puct}$ values increase both human prediction accuracy and winrate over the raw model in both Chess and Go.

In chess and Go, we ran two main experiments each. First, in chess using the prior state-of-the-art Maia models from McIlroy-Young et al., 2020 and in Go using a model trained on professional games from the GoGoD dataset, we demonstrate that MCTS with that model outperforms the raw model in human prediction accuracy. Second, we also sanity-check that MCTS with the same parameters greatly improves the strength of the same models in chess and Go.

Data and Model Architecture

In chess, for the human-learned anchor policy we use the pre-trained Maia1100, Maia1500, and Maia1900 models from McIlroy-Young et al., 2020, achieving state-of-the-art performance on rating-conditional human move prediction. These models follow a standard AlphaZero-like residual block architecture, including both a policy and a value head, and were trained to imitate players in ratings “buckets” 1100, 1500, and 1900 respectively, based on roughly 10 million games each from the popular Lichess server (each bucket contains games between players from rating N to N+99).

Top-1 % test accuracy in chess for Maia models trained to predict moves by players in rating buckets 1100, 1500, 1900, applied to predict all rating buckets, with and without MCTS. The black bolded outline indicates where the model is predicting the same rating as it was trained on. Standard error is very small, the slight thin shade around each line. MCTS most improves prediction of a model on players of its target rating and higher.

For Go, we trained a deep neural net on the GoGoD professional game dataset[https://gogodonline.co.uk/]. We match Cazenave, 2017 in using games from 1900 through 2014 for training and 2015-2016 as the test set, with roughly 73000 and 6500 games, respectively.
Our architecture matches the 20-block residual net structure used by some versions of AlphaZero [Silver et al., 2017], except adds squeeze-and-excitation layers which have been successful in image processing tasks [Hu et al., 2018] and self-play learning in chess and Go [LC0, 2020, Troisi, 2019]. See Appendix <ref> for additional details.

Improved Human Prediction and Strength
In Table <ref> we show the top-1 accuracy of MCTS at predicting players in chess and Go. MCTS on top of each model tested outperforms that model at predicting human moves.

In chess, the benefit provided increases greatly as the rating of players predicted increases, while the optimal choice for $c_\text{puct}$ appears to decrease (allowing increasingly small value differences to affect the search). This is consistent with the intuitive hypothesis that stronger players plan more deeply, increasing the value of explicitly modeling planning, and that they are more sensitive to small future value differences. In Go, despite our baseline model being equal or better than all prior imitation-learning models on the GoGoD human pro games dataset, MCTS improves it yet further.

In Figure <ref>, for chess we see that while KL-regularized search improves each model's accuracy on players of its target rating, surprisingly, the improvement grows yet larger when each model predicts players of higher rating than it was trained on. This suggests that as human players improve, the incremental average change in their behavior resembles or is correlated with the way that highly-regularized search improves the strength of a baseline policy.

Additionally, in Appendix <ref>, we show that if we apply post-processing to the MCTS policy based on Grill et al., 2020, MCTS improves cross entropy with human moves in both chess and Go, not just top-1 accuracy. In other words, not only does policy-regularized search improve the prediction of the top move, but it also better models the overall distribution of moves that humans may likely play.

We measure the strength impact of regularized search with 1000 games[In Go, we also use the open-source KataGo [Wu, 2020] to determine when the game is over and to score the result. Unlike RL agents, humans which our models imitate universally pass and score the game well before it becomes mechanically scorable, so we use KataGo as a neutral judge.] per $c_\text{puct}$ setting between the raw model policy and the MCTS policy, sampling each at temperature 1.
Figure <ref> shows the change in human prediction accuracy of MCTS in both chess and Go plotted jointly versus winrate of MCTS against the raw model. Rather than solely a tradeoff between strength and accuracy, most $c_\text{puct}$ values in the range we tested increase both, some achieving more than 90% winrate while still improving human prediction. See Appendix <ref> for results at lower temperature and evidence that accuracy improves further at longer time controls.

Although we did not test against humans directly to calibrate, this gives clear evidence that a well-tuned human-regularized MCTS agent would be better able to match the 1900-1999-rated chess players that Maia1900 currently falls hundreds of Elo short of imitating, while simultaneously being more accurate to their move-by-move behavior, and similarly for human-imitation agents in Go.

§ IMPERFECT-INFORMATION GAMES: POLICY-REGULARIZED REGRET MINIMIZATION

While MCTS is a popular search algorithm for perfect-information deterministic games, it is not able to compute optimal policies in imperfect-information games.
Instead, iterative algorithms based on regret minimization are the leading approach to search in imperfect-information games.

Hedge [Littlestone & Warmuth, 1994, Freund & Schapire, 1997] is an iterative regret minimization algorithm that in general converges to a coarse correlated equilibrium (CCE) [Hannan, 1957]. In the special case of two-player zero-sum games, it also converges to a Nash equilibrium (NE) [Nash, 1951].

Regret Matching (RM) [Blackwell et al., 1956, Hart & Mas-Colell, 2000] is another equilibrium-finding algorithm similar to Hedge that has historically been more popular and that we compare our algorithm to in this paper.

The effectiveness of the implicit KL-regularization in MCTS that we study in <ref> motivates us to develop an equilibrium-finding algorithm called piKL-Hedge that similarly biases the search towards an anchor policy. In <ref>, we show that piKL-Hedge achieves better empirical performance against baseline human-imitation models than Hedge and RM in a large imperfect-information game, as well as much higher human prediction accuracy.

§.§ Background

We consider a game with $\mathcal{N}$ players where each player $i$ chooses an action $a$ from a set of actions $\mathcal{A}_i$. We denote the actions of all players other than $i$ as $\vec{a}_{-i}$. After all players simultaneously choose an action, player $i$ receives a reward of $u_i(a, \vec{a}_{-i})$. Players may also choose a probability distribution over actions, where the probability of action $a$ is denoted $\vec{\pi}_i(a)$ and the vector of probabilities is denoted $\vec{\pi}_i$. We also define the fixed policy that we are interested in biasing player $i$ towards as the anchor policy $\vec{\tau}_i \in \Delta(A_i)$.

Each player $i$ maintains a regret for each action. The regret on iteration $t$ is denoted $R_i^t(a)$. Initially, all regrets are zero. On each iteration $t$ of Hedge, $\vec{\pi}^t_i(a)$ is set according to

\begin{equation} \label{eq:hedge}
\vec{\pi}^{t}_i(a) \propto
\exp\big(R^t_i(a)\big)
\end{equation}

Next, each player samples an action $a^*$ from $\mathcal{A}_i$ according to $\pi_i^t$ and all regrets are updated such that

\begin{equation} \label{eq:srm}
R_i^{t+1}(a) = R_i^{t}(a) + u_i(a, \vec{a}^*_{-i}) - \sum_{a' \in \mathcal{A}_i} \vec{\pi}^t_i(a') u_i(a'_i, \vec{a}^*_{-i})
\end{equation}

It is proven that the average policy of Hedge over all iterations converges to a NE in two-player zero-sum games and, more broadly, the players' joint policy distribution converges to a CCE as $t \rightarrow \infty$.

We wish to model agents that seek to maximize their expected reward, while at the same time playing “close” to the anchor policy. The two goals can be reconciled by defining a composite utility function that adds a penalty based on the “distance” between the player policy and their anchor policy, with coefficient $\lambda_i\in[0,\infty)$ scaling the penalty.

For each player $i$, we define $i$'s utility as a function of the the agent policy $\vec{\pi}_i \in \Delta(A_i)$ given policies $\vec{\pi}_{-i}$ of all other agents:

\begin{align}\label{eq:regularized C}
\mathcal{U}_{i}(\vec{\pi}_i, \vec{\pi}_{-i}) &\defeq u_i(\vec{\pi}_i, \vec{\pi}_{-i}) - \lambda_i\,\KL{\vec{\pi}_i}{\vec{\tau}_i}.
\end{align}

When $\lambda$ is large, the utility function is dominated by the KL-divergence term $\lambda_i\,\KL{\vec{\pi}_i}{\vec{\tau}_i}$, and so the agent will naturally tend to play a policy $\vec{\pi}_i$ close to the anchor policy $\vec{\tau}_i$ [The careful reader may observe that the direction of the KL-divergence term, $\KL{\pi}{\tau}$ is the opposite of the direction implicit in MCTS, $\KL{\tau}{\pi}$. We choose this direction for greater ease of theoretical analysis and implementation in the context of regret minimization; for our use cases we have not found the exact form of the loss to be critical so much as simply doing any reasonable regularized search.]. When $\lambda_i$ is small, the dominating term is the rewards $u_i(\vec{\pi}_i, \vec{a}^t_{-i})$ and so the agent will tend to maximize reward without as closely matching the anchor policy $\vec{\tau}_i$. These statements are made precise in  <ref> and <ref>.

§.§ No-Regret Learning for Policy-Regularized Utilities

In this section, we present <ref>, a no-regret algorithm based on Hedge for any player $i$ to learn strong policies relative to the regularized utilities defined in (<ref>).
As we show in <ref> in <ref>, it guarantees that each player $i$ accumulates sublinear regret (of order $\log T$) with respect to the regularized utility functions:

\[
\mathcal{U}^t_{i}(\vec{\pi}_i) \defeq \mathcal{U}_{i}(\vec{\pi}_i, \vec{a}_{-i}^t) = u_i(\vec{\pi}_i, \vec{a}^t_{-i}) - \lambda_i\,\KL{\vec{\pi}_i}{\vec{\tau}_i},
\]

no matter the opponents' actions $\vec{a}_{-i}^t$ at each time $t$.

[H]piKL-Hedge (for Player $i$)
$A_i$ set of actions for Player $i$; $u_i$ reward function for Player $i$; $\eta > 0$ learning rate hyperparameter.
$t \gets 0$

each action $a \in A_i$
$\mathsf{CV}^0_i(a) \gets 0$

$t \gets t + 1$

let $\vec{\pi}^t_{i}$ be the policy such that

\begin{equation}\label{eq:distribution}
\vec{\pi}^t_{i}(a) \propto \exp\mleft\{\frac{\eta\,\mathsf{CV}^{t-1}_i(a) + t\lambda_i\eta\,\log\tau_i(a)}{1+t\lambda_i\eta}\mright\}.
\end{equation}

sample an action $a^t \sim \vec{\pi}^t_{i}$

play $a^t$ and observe actions $\vec{a}^t_{-i}$ played by the opponents

each $a \in A_i$
$\mathsf{CV}^{t}_i(a) \gets \mathsf{CV}^{t-1}_i(a) + u_i(a, \vec{a}^t_{-i})$

As with many other regret-minimization methods, we consider the average policy of each player $i$ over $T$ iterations:

\begin{equation}\label{eq:avg policy}
\vspace{-0.03in}
\bar{\vec{\pi}}_{i}^T \defeq \frac{1}{T}\sum_{t=1}^T \vec{\pi}^t_{i}
\vspace{-0.03in}
\end{equation}

where $\vec{\pi}^t_{i}$ is defined in (<ref>). We take $\bar{\vec{\pi}}^T_i$ to be the final agent policy produced by in no-press Diplomacy (as described in more detail in <ref>).
As shown in <ref>, the KL-divergence of $\bar{\vec{\pi}}^T_i$ from the anchor policy $\vec{\tau}_i$ converges to be inversely proportional to $\lambda_i$:

(piKL stays close to the anchor policy) Upon running <ref> for $T$ iterations in a multiplayer general-sum game, the policy $\bar{\vec{\pi}}_i^T$ is at a distance

\[
\KL{\bar{\vec{\pi}}^T_i}{\vec{\tau}_i} \le \frac{1}{\lambda_i}\mleft(\frac{R_i^T}{T} + D_i\mright),
\]

where $D_i$ is any upper bound on possible rewards for Player $i$.
In particular, if $\eta > 0$ is set so that $R_i^T = o(T)$, then $\KL{\bar{\vec{\pi}}^T_i}{\vec{\tau}_i} \to D_i/\lambda_i$ as $T \to +\infty$.

We can also show (see <ref>) that in the case of a two-player zero-sum game, $\bar{\vec{\pi}}^T_i$ approximates a Nash equilibrium of the original utility functions, with the approximation guarantee controlled by $\lambda$:

Let $(\bar{\vec{\pi}}_1,\bar{\vec{\pi}}_2)$ be any limit point of the average policies $(\bar{\vec{\pi}}_{1}^T, \bar{\vec{\pi}}_2^T)$ of the players. Almost surely, $(\bar{\vec{\pi}}_1,\bar{\vec{\pi}}_2)$ is a $(\max_{i=1,2}\{\lambda_i\beta_i\})$-approximate Nash equilibrium policy with respect to the original utility functions $u_i$, where $\beta_i$ is as defined in (<ref>).
seems like we should probably mention that this is vacuous if any 1/tau(a) is bigger than the greatest difference between rewards. when should we expect this not to be the case? e.g. with a diplomacy-sized action space it's definitely problematic... I think it's “if any $\lambda log(1/tau(a))$ is bigger...”, which is much less of a big deal because of the log and because $\lambda$ is typically small. Plus I think that it's really only among actions $a$ in the support of the equilibrium, although I'm not sure (Gabriele?)
oh, if it's only about the support of the equilibrium we should definitely mention thatAdam: the proof we have right now would not be strong enough to support that, and I'm not 100% the result would hold with what you're saying. But I'm happy to try and think about it if you guys think it would make a substantial difference.Well, I suspect you could at least restrict $\tau(a)$ to non-dominated actions? because if there's an irrelevant awful action that has $\pi(a)=0$ then the bound goes to infinity but the piKL equilibrium should be the same quality. Anyway, even leaving this aside, imagine that $1/\tau \geq 10^{-10}$, then with $\lambda=1e-2$ we still have $\lambda\log(1/\tau(a)) = 0.23.$

Lastly, we remark that in the special case that $\vec{\tau}_i$ is the uniform policy for all players $i$, the above results imply that <ref> converges towards a quantal response equilibrium [McKelvey & Palfrey, 1995], in which an imperfect agent is modeled as choosing actions with probability exponentially decaying in the amount that each action is worse than the best action(s), given that all other agents behave the same way. Our method can be seen as a generalization that takes into account a human-learned prior for what actions may be more likely.

§.§ Diplomacy Experiments

Diplomacy is a benchmark 7-player simultaneous-action game featuring both cooperation and competition. In <ref>, we summarize the rules of the game.
Using piKL-Hedge, we develop an agent piKL-HedgeBot and show that it improves upon prior approaches for the game.
In <ref>, we also illustrate the key features of piKL-Hedge in Blotto, a famous 2-player simultaneous action game.

Algorithms and Models

In no-press Diplomacy, we compare the different equilibrium search algorithms (RM, Hedge and piKL-Hedge) using the procedure introduced by Gray et al., 2020. We perform 1-ply lookahead where on each turn, we sample up to 30 of the most likely actions for each player from a policy network trained via imitation learning on human data (IL policy). We then consider the 1-ply subgame consisting of those possible actions where the rewards for a given joint action are given by querying a value network trained on human game data as in Gray et al., 2020. We play according to the approximate equilibrium computed for that subgame by that algorithm. For piKL-Hedge, the anchor policy is simply the same human-trained policy network. Our baseline policy and value models also contain a few improvements over prior models for no-press Diplomacy, described in Appendices <ref> and <ref>.

In our experiments, we label our RM, Hedge, and piKL-Hedge agents as , HedgeBot, and piKL-HedgeBot respectively. We compare also against SearchBot [Gray et al., 2020] (similar to  but using the models from Gray et al., 2020 rather than our models).
See <ref> for more details about the hyperparameters used.

Strong, human-like play with piKL-Hedge

Similar to Chess and Go, we compare the human prediction accuracy of RMBot, HedgeBot, piKL-HedgeBot (with different $\lambda$s) to the IL anchor policy, as well as testing their head-to-head strength. In particular, we test their ability to predict human moves in 226 no-press Diplomacy games from a validation set, and measure their score against the IL policy across 700 games each.

In <ref> (Left), we present the average top-1 accuracy of unit orders in each action predicted by these methods as well as their average scores against 6 IL anchor policies. The raw IL model ($\lambda = \infty$) predicts human moves with high accuracy but is weak and achieves low average score. Unregularized Hedge and RM ($\lambda = 0$) achieve high score but low human prediction accuracy.
By contrast, piKL-HedgeBot with different $\lambda$ achieves a variety of highly favorable combinations of the two.
$\lambda=10^{-1}$ gives about the same top-1 accuracy as the IL policy but improves score by a factor of 1.4x over the IL anchor policy.
$\lambda=10^{-3}$ outperforms unregularized search methods in both score (by ~5%) and human prediction accuracy (by ~6%). Mild regularization improves average score, rather than harming it.

(Left) Average top-1 accuracy of unit orders in each action predicted by the human IL anchor policy, RM, Hedge and piKL-Hedge, versus head to head score against 6 IL anchor policies.  ($\lambda = 10^{-1}$) predicts human moves as accurately as the anchor policy while achieving a much higher score. At the same time,  ($\lambda = 10^{-3}$) allows for a stronger and more human-like policy than unregularized search methods (hedge, RM). Note that equal performance would imply an average score of 1/7 $\approx 14.3\%$. Error bars indicate 1 standard error.
(Right) Average top-1 accuracy of unit orders in each action predicted by the human policy, RM, and piKL, as a function of pseudo-Elo player rating.

Agent     [1cm][r]Average Score

DipNet$^\dagger$        3.7% $\pm$ 0.3%

DipNet RL$^\dagger$        4.7% $\pm$ 0.3%

Blueprint$^\ddagger$         4.9% $\pm$ 0.3%

BRBot$^\ddagger$           16.1% $\pm$ 0.6%

SearchBot$^\ddagger$      13.4% $\pm$ 0.5%

7.9% $\pm$ 0.4%

31.3% $\pm$ 0.7%

32.9% $\pm$ 0.7%

Average score achieved by agents in a uniformly sampled pool of other agents. piKL-HedgeBot ($\lambda=10^{-3}$) outperforms all other agents in this setting. DipNet agents from [Paquette et al., 2019] use a temperature of 0.1, while and blueprint [Gray et al., 2020] use a temperature of 0.5. The $\pm$ shows one standard error. $^\dagger$[Paquette et al., 2019]; $^\ddagger$[Gray et al., 2020].

We also tested pure RL agents and found they perform poorly in predicting human moves. In particular, the recently proposed DORA and HumanDNVI-NPU algorithms [Bakhtin et al., 2021] achieve top-1 accuracy of only 29.1% and 37.8% respectively.

Next, in <ref> (Right), we compare the top-1 accuracy of these methods across players of different pseudo-Elo ratings. The pseudo-Elo ($e_i$) for player i is constructed based on the logit rating $s_i$ introduced in Gray et al., 2020, where, $e_i = \frac{s_i \cdot 400}{\log(10)} + 1000$. The top-1 accuracy for all the search-based policies increases with pseudo-Elo, indicating that they are better at modeling stronger players than weaker players. piKL-Hedge ($\lambda=10^{-1}$) performs just as well as the anchor policy across pseudo-Elos while being significantly stronger than the anchor, while $\lambda=10^{-3}$ is as strong or stronger than Hedge and RM but matches human play far better.

piKL-HedgeBot performs well against a varied pool of agents

We also develop a new head-to-head evaluation setting, where rather than testing one agent vs 6x of another agent, all 7 agents per game are sampled uniformly from a pool.
The 1v6 head-to-head scores used in prior work [Gray et al., 2020, Bakhtin et al., 2021, Anthony et al., 2020, Paquette et al., 2019] indicate whether a population of 6x agents can be invaded by a 1x agent, and hence whether the 6 agents constitute an Evolutionarily Stable Strategy (ESS) [Taylor & Jonker, 1978, Smith, 1982]. By contrast, assigning the 7 agents per game randomly from a pool studies the robustness of an agent to a variety of other agents.

We experiment with a pool of 8 agents. Five are previously published agents: DipNet, DipNet RL [Paquette et al., 2019], Blueprint, BRBot, SearchBot [Gray et al., 2020] and three are our agents: IL policy,  and . Doing well in this population requires playing well with both human-like policies (DipNet, Blueprint) and equilibrium policies (SearchBot, RMBot). Each experiment only compares one lambda value of piKL-HedgeBot for fairness.

The results of these experiment with piKL-HedgeBot ($\lambda=10^{-3}$) is presented in <ref>. piKL-HedgeBot ($\lambda=10^{-3}$) outperforms all other agents.

Overall, unlike Chess and Go, we do not find that piKL-Hedge clearly improves human prediction accuracy over the IL model. However, unlike Chess and Go, we observe that piKL-Hedge does improve playing strength over prior search methods against various past agents. In general-sum games like Diplomacy, it appears that piKL-hedge with a human anchor policy allows for slightly better play in a population containing human-like agents while still doing well against equilibrium-searchers, or alternatively can improve strength over IL to a lesser degree with no cost at all to prediction accuracy.

§ RELATED WORK

§.§ Regularized Learning and Planning

Several prior works have explored augmenting reinforcement learning with supervised data from expert demonstrations [Vecerik et al., 2017, Nair et al., 2018]. For example, Hester et al., 2018 augment Deep Q Learning with a margin loss on demonstration data that aims to make $Q(a)$ for each demonstration action higher than that of other actions. KL-regularization has also been used successfully to incorporate expert demonstrations into RL training  [Rudner et al., 2021, Ng et al., 2000, Boularias et al., 2011, Wu et al., 2019, Peng et al., 2019, Siegel et al., 2019]. In these settings, the standard RL objective is augmented by a KL divergence penalty that expresses the dissimilarity between the online policy and a reference policy derived from demonstrations. This helps guide exploration in RL or ameliorate inaccurate modeling of the environment in domains such as robotics. AlphaStar [Vinyals et al., 2019], which achieved expert human performance in StarCraft 2, uses self-play RL initialized from supervised policies with a KL penalty term for deviating from the supervised policy during training to "aid in exploration and to preserve strategic diversity". In our work, we use the KL term to better approximate human play during inference-time search.

Prior work has explored entropy-regularized utilities in games. Ling et al., 2018 show that a particular type of entropic regularization in extensive-form games leads to quantal response equilibria. Cen et al., 2021 give fast online optimization algorithms for entropy-regularized utilities in the context of quantal response. Farina et al., 2019 regularize utilities with a KL divergence term from a precomputed Nash equilibrium strategy to design agents that trade off game-theoretic safety and exploitation.  In our work, we leverage the KL divergence term towards a human-imitation learned policy instead, to regularize the utilities. And unlike previous works, we empirically study our approach in a much larger imperfect information game.

§.§ Strong Human-Compatible Policies

Prior work in multi-agent reinforcement learning has emphasized the importance of human-compatible policies in cooperative multi-agent environments. Lerer & Peysakhovich, 2019 demonstrate that self-play policies may perform poorly with other agents if they do not conform to the population equilibrium (social conventions), and propose a combination of policy gradient and imitation loss directly on samples of population data.

Human-compatible policies have also been studied on the benchmark game of Hanabi, where ad hoc play with humans is regarded as an open challenge problem [Bard et al., 2020]. Most work on this challenge has focused on zero-shot coordination with humans, in which an agent must adapt to human play with no prior experience with human partners [Hu et al., 2020, Hu et al., 2021, Cui et al., 2021]. Learning human-compatible policies from a combination of human data and planning are less well-studied in this setting.

MCTS, Chess and Go

Prior work in tree search methods, especially in chess and Go, has typically focused on developing strong agents without concern for accurately modeling human behavior.
For example in Go, a significant body of older work investigates imitation learning (IL) to obtain a baseline policy prior to use with MCTS, but tunes and evaluates the final agent via playing strength alone [Tian & Zhu, 2016, Cazenave, 2017].

Regarding the use of search for human modeling, recent work in chess by McIlroy-Young et al., 2020 found that pure IL outperformed all other approaches and that adding MCTS with the parameters of a standard engine significantly harmed human prediction accuracy. However in our work, using a different range of parameters, we show clear results to the contrary. In Go, Wang et al., 2017 report promising results on human prediction and playing strength using search, albeit with a specialized architecture and rollout method. Baier et al., 2018 report in the card game Spades both excellent human accuracy and playing strength by adding a human policy bias to a variant of MCTS. To our knowledge, our work is the first to demonstrate a clear gain in human prediction accuracy over deep learning models in the highly-studied domains of chess and Go via simple well-established methods of policy-regularized planning.

Diplomacy is a benchmark 7-player game that involves communication, negotiation, cooperation, and competition in a strategic multi-agent setting. While chess and Go are two-player zero-sum games for which optimal play is well-defined and can be computed through self-play [Nash, 1951], Diplomacy has no such guarantees and strong play likely requires modeling other agents, even in the no-press variant where natural-language communication is not allowed [Bakhtin et al., 2021].

Paquette et al., 2019 showed that neural network IL on human data in no-press Diplomacy can reasonably approximate human play, but that bootstrapping RL from this agent leads to a breakdown in cooperation. Anthony et al., 2020 developed new RL methods based on fictitious play that improve the performance of agents in no-press Diplomacy, and Gray et al., 2020 showed that an equilibrium-finding regret minimization search procedure on top of human IL models achieves human-level performance in no-press Diplomacy. However, although both methods rely on the human IL model to generate a restricted action set for RL or search, neither contains any explicit regularization when choosing among those actions, and we show that the equilibrium search in Gray et al., 2020 greatly decreases the accuracy of modeling human players. Similarly, Bakhtin et al., 2021 achieved strong results in no-press Diplomacy via self-play RL both from scratch and initialized with a human-learned policy, but we show that the resulting final agents do not ultimately model humans well.

§ CONCLUSION

In this paper, we showed across several domains that regularizing search policies according to a KL-divergence loss with an imitation learned (IL) policy produces policies that maintain high human prediction accuracy while being far stronger than the original learned policy. In chess and Go, applying standard MCTS regularized toward a human-learned policy
achieves state-of-the-art prediction accuracy, surpassing imitation learning, while also winning more than 85% of games against an IL model.
We then introduced a novel regret minimization algorithm that is regularized based on the KL divergence from an IL policy. In no-press Diplomacy, this algorithm yields both a policy that predicts human play with the same accuracy as imitation learning alone while increasing win rate against state-of-the-art baselines by a factor of 1.4, or alternately a policy that outperforms unregularized search while achieving much higher human prediction accuracy. We presented in Appendix <ref> similar successful results for KL-regularized search in Hanabi.

There are several directions for future work, such as extending piKL-Hedge to handle extensive-form games. Additionally, there may be better ways to regularize search than KL-divergence. Finally, it remains to be seen how KL-regularized search performs when combined with RL.

§ AUTHOR CONTRIBUTIONS

A. P. Jacob was the primary researcher for piKL-hedge and contributed to the direction, experiments, and writing of the entire paper. D. J. Wu was the primary researcher for MCTS in chess and Go, and contributed to the direction, experiments, and writing of the entire paper. G. Farina was the primary formulator of the piKL-hedge algorithm and handled all the theory in the paper. A. Lerer contributed to the direction of the project, the formulation of piKL-hedge, its experimental evaluation, and paper writing. H. Hu was the primary researcher for the extension of piKL to Hanabi covered in Appendix <ref>. A. Bakhtin contributed to the experimental evaluation of piKL-hedge. J. Andreas contributed to the direction of the project and to paper writing. N. Brown initiated the project and contributed to the direction of the project, the formulation of piKL-hedge, its experimental evaluation, and paper writing.

[Abernethy & Rakhlin, 2009]
Abernethy, J. and Rakhlin, A.
Beating the adaptive bandit with high probability.
Technical Report UCB/EECS-2009-10, EECS Department, University of
California, Berkeley, Jan 2009.

[Anderson et al., 2021]
Anderson, A., McIlroy-Young, R., Sen, S., and Kleinberg, J.
Introducing maia, a human-like neural network chess engine, 2021.

[Anthony et al., 2020]
Anthony, T., Eccles, T., Tacchetti, A., Kramár, J., Gemp, I., Hudson, T.,
Porcel, N., Lanctot, M., Perolat, J., Everett, R., Singh, S., Graepel, T.,
and Bachrach, Y.
Learning to play no-press diplomacy with best response policy
In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin,
H. (eds.), Advances in Neural Information Processing Systems,
volume 33, pp.  17987–18003. Curran Associates, Inc., 2020.

[Baier et al., 2018]
Baier, H., Sattaur, A., Powley, E., Devlin, S., Rollason, J., and Cowling, P.
Emulating human play in a leading mobile card game.
IEEE Transactions on Games, PP:0 1–1, 05 2018.

[Bakhtin et al., 2021]
Bakhtin, A., Wu, D., Lerer, A., and Brown, N.
No-press diplomacy from scratch.
In Thirty-Fifth Conference on Neural Information Processing
Systems, 2021.

[Bard et al., 2020]
Bard, N., Foerster, J. N., Chandar, S., Burch, N., Lanctot, M., Song, H. F.,
Parisotto, E., Dumoulin, V., Moitra, S., Hughes, E., et al.
The hanabi challenge: A new frontier for ai research.
Artificial Intelligence, 280:0 103216, 2020.

[Blackwell et al., 1956]
Blackwell, D. et al.
An analog of the minimax theorem for vector payoffs.
Pacific Journal of Mathematics, 60 (1):0 1–8,

[Boularias et al., 2011]
Boularias, A., Kober, J., and Peters, J.
Relative entropy inverse reinforcement learning.
In Proceedings of the Fourteenth International Conference on
Artificial Intelligence and Statistics, pp.  182–189. JMLR Workshop and
Conference Proceedings, 2011.

[Brown & Sandholm, 2017]
Brown, N. and Sandholm, T.
Superhuman AI for heads-up no-limit poker: Libratus beats top
Science, pp.  eaao1733, 2017.

[Brown & Sandholm, 2019]
Brown, N. and Sandholm, T.
Superhuman AI for multiplayer poker.
Science, 3650 (6456):0 885–890, 2019.

[Campbell et al., 2002]
Campbell, M., Hoane Jr, A. J., and Hsu, F.-h.
Deep Blue.
Artificial intelligence, 1340 (1-2):0 57–83,

[Cazenave, 2017]
Cazenave, T.
Residual networks for computer go.
IEEE Transactions on Computational Intelligence and AI in
Games, PP:0 1–1, 03 2017.

[Cen et al., 2021]
Cen, S., Wei, Y., and Chi, Y.
Fast policy extragradient methods for competitive games with entropy
In Neural Information Processing Systems (NeurIPS), 2021.

[Cui et al., 2021]
Cui, B., Hu, H., Pineda, L., and Foerster, J.
K-level resoning for zero-shot coordination in hanabi.
In Thirty-Fifth Conference on Neural Information Processing
Systems, 2021.

[Egri-Nagy & Törmänen, 2020]
Egri-Nagy, A. and Törmänen, A.
The game is not over yet—go in the post-alphago era.
Philosophies, 50 (4):0 37–0, 2020.
ISSN 2409-9287.
URL <https://www.mdpi.com/2409-9287/5/4/37>.

[Farina et al., 2019]
Farina, G., Kroer, C., and Sandholm, T.
Online convex optimization for sequential decision processes and
extensive-form games.
In AAAI Conference on Artificial Intelligence, 2019.

[Fickinger et al., 2021]
Fickinger, A., Hu, H., Amos, B., Russell, S., and Brown, N.
Scalable online planning via reinforcement learning fine-tuning.
CoRR, abs/2109.15316, 2021.
URL <https://arxiv.org/abs/2109.15316>.

[Freund & Schapire, 1997]
Freund, Y. and Schapire, R. E.
A decision-theoretic generalization of on-line learning and an
application to boosting.
Journal of computer and system sciences, 550
(1):0 119–139, 1997.

[Gray et al., 2020]
Gray, J., Lerer, A., Bakhtin, A., and Brown, N.
Human-level performance in no-press diplomacy via equilibrium search.
In International Conference on Learning Representations, 2020.

[Grill et al., 2020]
Grill, J.-B., Altché, F., Tang, Y., Hubert, T., Valko, M., Antonoglou, I.,
and Munos, R.
Monte-carlo tree search as regularized policy optimization.
In International Conference on Machine Learning, pp.  3769–3778. PMLR, 2020.

[Hannan, 1957]
Hannan, J.
Approximation to bayes risk in repeated play.
Contributions to the Theory of Games, 3:0 97–139,

[Hart & Mas-Colell, 2000]
Hart, S. and Mas-Colell, A.
A simple adaptive procedure leading to correlated equilibrium.
Econometrica, 680 (5):0 1127–1150, 2000.

[Hester et al., 2018]
Hester, T., Vecerik, M., Pietquin, O., Lanctot, M., Schaul, T., Piot, B.,
Horgan, D., Quan, J., Sendonaris, A., Osband, I., et al.
Deep q-learning from demonstrations.
In Thirty-second AAAI conference on artificial intelligence,

[Hu et al., 2020]
Hu, H., Lerer, A., Peysakhovich, A., and Foerster, J.
“other-play” for zero-shot coordination.
In International Conference on Machine Learning, pp.  4399–4410. PMLR, 2020.

[Hu et al., 2021]
Hu, H., Lerer, A., Brown, N., and Foerster, J. N.
Learned belief search: Efficiently improving policies in partially
observable settings.
CoRR, abs/2106.09086, 2021a.
URL <https://arxiv.org/abs/2106.09086>.

[Hu et al., 2021]
Hu, H., Lerer, A., Cui, B., Pineda, L., Wu, D., Brown, N., and Foerster, J.
Off-belief learning.
In International Conference on Machine Learning. PMLR,

[Hu et al., 2018]
Hu, J., Shen, L., and Sun, G.
Squeeze-and-excitation networks.
In 2018 IEEE/CVF Conference on Computer Vision and Pattern
Recognition, pp.  7132–7141, 2018.

[Lai, 2018]
Lai, M.
Forum post on alphazero news (post by user matthewlai).
<http://talkchess.com/forum3/viewtopic.php?f=2   t=69175   sid=06ca6a966c29743d765c11b13402be8d   start=70#p781765>,

[LC0, 2020]
Leela chess zero information page on "neural network topology".
<https://lczero.org/dev/backend/nn/>, 2020.

[Lerer & Peysakhovich, 2019]
Lerer, A. and Peysakhovich, A.
Learning existing social conventions via observationally augmented
In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics,
and Society, pp.  107–114. ACM, 2019.

[Lerer et al., 2020]
Lerer, A., Hu, H., Foerster, J., and Brown, N.
Improving policies via search in cooperative partially observable
In AAAI Conference on Artificial Intelligence, 2020.

[Ling et al., 2018]
Ling, C. K., Fang, F., and Kolter, J. Z.
What game are we playing? end-to-end learning in normal and extensive
form games.
International Joint Conferences on Artificial Intelligence
Organization, 2018.

[Littlestone & Warmuth, 1994]
Littlestone, N. and Warmuth, M. K.
The weighted majority algorithm.
Information and computation, 1080 (2):0
212–261, 1994.

[McIlroy-Young et al., 2020]
McIlroy-Young, R., Sen, S., Kleinberg, J., and Anderson, A.
Aligning superhuman ai with human behavior: Chess as a model system.
In Proceedings of the 26th ACM SIGKDD International Conference
on Knowledge Discovery & Data Mining, pp.  1677–1687, 2020a.

[McIlroy-Young et al., 2020]
McIlroy-Young, R., Wang, R., Sen, S., Kleinberg, J., and Anderson, A.
Learning personalized models of human behavior in chess.
Technical report, Microsoft, Inc., August 2020b.

[McKelvey & Palfrey, 1995]
McKelvey, R. D. and Palfrey, T. R.
Quantal response equilibria for normal form games.
Games and Economic Behavior, 100 (1):0 6–38,
ISSN 0899-8256.

[McKelvey & Palfrey, 1995]
McKelvey, R. D. and Palfrey, T. R.
Quantal response equilibria for normal form games.
Games and economic behavior, 100 (1):0 6–38,

[Moravčík et al., 2017]
Moravčík, M., Schmid, M., Burch, N., Lisỳ, V., Morrill, D.,
Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M.
Deepstack: Expert-level artificial intelligence in heads-up no-limit
Science, 3560 (6337):0 508–513, 2017.

[Nair et al., 2018]
Nair, A., McGrew, B., Andrychowicz, M., Zaremba, W., and Abbeel, P.
Overcoming exploration in reinforcement learning with demonstrations.
In 2018 IEEE International Conference on Robotics and
Automation (ICRA), pp.  6292–6299. IEEE, 2018.

[Nash, 1951]
Nash, J.
Non-cooperative games.
Annals of mathematics, pp.  286–295, 1951.

[Ng et al., 2000]
Ng, A. Y., Russell, S. J., et al.
Algorithms for inverse reinforcement learning.
In Icml, volume 1, pp.  2, 2000.

[Paquette et al., 2019]
Paquette, P., Lu, Y., Bocco, S. S., Smith, M., Satya, O.-G., Kummerfeld, J. K.,
Pineau, J., Singh, S., and Courville, A. C.
No-press diplomacy: Modeling multi-agent gameplay.
In Advances in Neural Information Processing Systems, pp.  4474–4485, 2019.

[Peng et al., 2019]
Peng, X. B., Kumar, A., Zhang, G., and Levine, S.
Advantage-weighted regression: Simple and scalable off-policy
reinforcement learning.
arXiv preprint arXiv:1910.00177, 2019.

[Rakhlin, 2009]
Rakhlin, A.
Lecture notes on online learning, 2009.

[Rudner et al., 2021]
Rudner, T. G., Lu, C., Osborne, M., Gal, Y., and Teh, Y. W.
On pathologies in kl-regularized reinforcement learning from expert
In Thirty-Fifth Conference on Neural Information Processing
Systems, 2021.

[Schrittwieser et al., 2020]
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L.,
Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al.
Mastering atari, go, chess and shogi by planning with a learned
Nature, 5880 (7839):0 604–609, 2020.

[Siegel et al., 2019]
Siegel, N., Springenberg, J. T., Berkenkamp, F., Abdolmaleki, A., Neunert, M.,
Lampe, T., Hafner, R., Heess, N., and Riedmiller, M.
Keep doing what worked: Behavior modelling priors for offline
reinforcement learning.
In International Conference on Learning Representations, 2019.

[Silver et al., 2016]
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche,
G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M.,
et al.
Mastering the game of go with deep neural networks and tree search.
Nature, 5290 (7587):0 484, 2016.

[Silver et al., 2017]
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez,
A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al.
Mastering the game of go without human knowledge.
Nature, 5500 (7676):0 354, 2017.

[Silver et al., 2018]
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A.,
Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al.
A general reinforcement learning algorithm that masters chess, shogi,
and go through self-play.
Science, 3620 (6419):0 1140–1144, 2018.

[Siu et al., 2021]
Siu, H. C., Peña, J., Chang, K. C., Chen, E., Zhou, Y., Lopez, V. J.,
Palko, K., and Allen, R. E.
Evaluation of human-ai teams for learned and rule-based agents in
CoRR, abs/2107.07630, 2021.
URL <https://arxiv.org/abs/2107.07630>.

[Smith, 1982]
Smith, J. M.
Evolution and the Theory of Games.
Cambridge university press, 1982.

[Taylor & Jonker, 1978]
Taylor, P. D. and Jonker, L. B.
Evolutionary stable strategies and game dynamics.
Mathematical biosciences, 400 (1-2):0
145–156, 1978.

[Tian, 2019]
Tian, Y.
Github thread for elf opengo, "[suggestion] clarify fpu in paper".
<https://github.com/pytorch/ELF/issues/140>, 2019.

[Tian & Zhu, 2016]
Tian, Y. and Zhu, Y.
Better computer go player with neural network and long-term
prediction, 2016.

[Troisi, 2019]
Troisi, S.
Github thread for minigo "[experiment] squeeze and excitation".
<https://github.com/tensorflow/minigo/issues/683>, 2019.

[Vecerik et al., 2017]
Vecerik, M., Hester, T., Scholz, J., Wang, F., Pietquin, O., Piot, B., Heess,
N., Rothörl, T., Lampe, T., and Riedmiller, M.
Leveraging demonstrations for deep reinforcement learning on robotics
problems with sparse rewards.
arXiv preprint arXiv:1707.08817, 2017.

[Vinyals et al., 2019]
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung,
J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al.
Grandmaster level in starcraft ii using multi-agent reinforcement
Nature, 5750 (7782):0 350–354, 2019.

[Wang et al., 2017]
Wang, J., Wang, W., Wang, R., and Gao, W.
Beyond monte carlo tree search: Playing go with deep alternative
neural network and long-term evaluation.
Proceedings of the AAAI Conference on Artificial Intelligence,
310 (1), Feb. 2017.
URL <https://ojs.aaai.org/index.php/AAAI/article/view/10749>.

[Wu, 2018]
Wu, D.
Go neural net sandbox.

[Wu, 2020]
Wu, D.
Accelerating self-play learning in go.
In AAAI-20 Workshop on Reinforcement Learning in Games, 2020.

[Wu et al., 2019]
Wu, Y., Tucker, G., and Nachum, O.
Behavior regularized offline reinforcement learning.

§ PROOFS

In this Appendix, we present detailed proofs of <ref> and <ref>.

§.§ Known results

We start by recalling a few standard results. First, we recall the follow-the-regularized-leader (FTRL) algorithm, one of the most well-studied algorithms in online optimization. At every time $t$, the FTRL algorithm instantiated with domain $\mathcal{X}$, $1$-strongly-convex regularizer $\phi: \mathcal{X} \to \mathbb{R}$, and learning rate $\eta > 0$, produces iterates according to

\begin{equation}\tag{FTRL}\label{eq:ftrl}
\vec{x}^{t+1} = \argmax_{\vec{x} \in \mathcal{X}} \mleft\{ -\frac{\phi(\vec{x})}{\eta} + \sum_{\tau=1}^t \ell^\tau(\vec{x}) \mright\},
\end{equation}

where $\vec{\ell}^1,\dots,\vec{\ell}^{t}$ are the convex utility functions gave as feedback by the environment. The FTRL algorithm guarantees the following regret bound.

The iterates $\vec{x}^t \in \mathcal{X}$ produced by the FTRL algorithm set up with constant step size $\eta > 0$ and $1$-strongly convex regularizer $\phi$ satisfy the regret bound

\[
\sum_{t=1}^T \ell^t(\vec{u}) - \ell^t(\vec{x}^t) \le \frac{\phi(\vec{u})}{\eta} + \sum_{t=1}^T \ell^t(\vec{x}^{t+1}) - \ell^t(\vec{x}^t) \qquad\forall\,\vec{u} \in \mathcal{X}.
\numberthis{eq:ftrl bound}
\]

In the analysis of <ref> we will also make use of the following technical lemma, a proof of which can be obtained starting using the same techniques as <cit.>

Let $\vec{p}\in\Delta(A)$ be a distribution over a discrete set $A$, $\vec{q}\in\mathbb{R}^{|A|}$ be a vector, and $D > 0$ be any constant such that $\max_{a,a'\in A} \{\vec{q}(a) - \vec{q}(a')\} \le M$. Then,

\[
\frac{\sum_{a \in A} \vec{p}(a)\cdot \exp\{-\vec{q}(a)\}^2}{
\mleft(\sum_{a\in A} \vec{p}(a) \cdot \exp\{-\vec{q}(a)\}\mright)^2
} - 1 \le \frac{\exp\{2M\}}{M^2} \sum_{a\in A} p(a) \vec{q}(a)^2.
\]

Let $q_\text{min} \defeq \min_{a\in A} \vec{q}(a)$ and $\tilde{\vec{q}}(a) \defeq \vec{q}(a) - q_\text{min}$ be a shifted version of $\vec{q}(a)$ so that $0 \le \tilde{\vec{q}}(a) \le M$ for all $a \in A$. Let now $X$ denote a random variable with value $\tilde{\vec{q}}(a)$ with probability $\vec{p}(a)$ for all $a \in A$. Then,

\begin{align*}
\frac{\sum_{a \in A} \vec{p}(a)\cdot \exp\{-\vec{q}(a)\}^2}{
\mleft(\sum_{a\in A} \vec{p}(a) \cdot \exp\{-\vec{q}(a)\}\mright)^2
} - 1 &= \frac{\exp\{q_\text{min}\}^2\sum_{a \in A} \vec{p}(a)\cdot\exp\{\vec{q}(a)\}^2}{
\exp\{q_\text{min}\}^2\mleft(\sum_{a\in A} \vec{p}(a) \cdot \exp\{-\vec{q}(a)\}\mright)^2
} - 1\\
&= \frac{\sum_{a \in A} \vec{p}(a)\cdot\exp\{-\tilde{\vec{q}}(a)\}^2}{
\mleft(\sum_{a\in A} \vec{p}(a) \cdot \exp\{-\tilde{\vec{q}}(a)\}\mright)^2
} - 1\\
&= \frac{\mathbb{E}[\exp(-X)]}{[\mathbb{E}\exp(-X)]^2} - 1.
\end{align*}

Applying Lemma A.4 from Abernethy & Rakhlin, 2009 we obtain

\[
\frac{\sum_{a \in A} \vec{p}(a)\cdot \exp\{-\vec{q}(a)\}^2}{
\mleft(\sum_{a\in A} \vec{p}(a) \cdot \exp\{-\vec{q}(a)\}\mright)^2
} - 1 \le \frac{\exp\{2M\} - 2M - 1}{M^2} (\mathbb{E}[X^2] - \mathbb{E}[X]^2) \le \frac{\exp\{2M\}}{M^2}\mathbb{E}[X^2],
\]

which is exactly the statement.

§.§ Bounding the distance between the iterates of <ref>

At all times $t$ and for all players $i$, the policies $\vec{\pi}_i^t$ produced by the FTRL algorithm set up with constant step size $\eta$ and negative entropy regularizer $\varphi(\vec{x}) \defeq \sum_{a\in A_i} \vec{x}(a)\log\vec{x}(a)$, when observing the utilities $\mathcal{U}^t_i$, match the policies $\vec{\pi}_i^t$ produced by <ref>.

Plugging the particular choices of utilities and regularizer into (<ref>), we obtain

\begin{align*}
\vec{\pi}_{i}^{t+1} &= \argmax_{\vec{\pi}\in\Delta(A_i)}\mleft\{ \mleft(\sum_{t'=1}^{t}\mathcal{U}_{i}^{t'}(\vec{\pi})\mright) - \frac{1}{\eta}\sum_{a\in A_i} \vec{\pi}(a) \log \vec{\pi}(a)\mright\}\\
&= \argmax_{\vec{\pi}\in\Delta(A_i)}\mleft\{\eta\mleft( \sum_{t'=1}^{t}\sum_{a \in A_i} \vec{\pi}(a)\,u_i(a, \vec{a}_{-i}^{t'}) - \lambda_i\,\vec{\pi}(a) \log\mleft(\frac{\vec{\pi}(a)}{\vec{\tau}_i(a)}\mright)\mright) - \sum_{a\in A_i} \vec{\pi}(a) \log \vec{\pi}(a)\mright\}\\
&= \argmax_{\vec{\pi}\in\Delta(A_i)}\mleft\{ \eta\sum_{a\in A_i}\mleft(t\lambda_i \log\vec{\tau}_i(a) + \sum_{t'=1}^{t} u_i(a, \vec{a}_{-i}^{t'})\mright)\vec{\pi}(a) - (1+t\lambda_i\eta) \sum_{a\in A_i}\vec{\pi}(a)\log\vec{\pi}(a)\mright\}\\
&= \argmax_{\vec{\pi}\in\Delta(A_i)}\mleft\{ \frac{\eta}{1+t\lambda_i\eta}\sum_{a\in A_i}\mleft(t\lambda_i \log\vec{\tau}_i(a) + \sum_{t'=1}^{t} u_i(a, \vec{a}_{-i}^{t'})\mright)\vec{\pi}(a) - \sum_{a\in A_i}\vec{\pi}(a)\log\vec{\pi}(a)\mright\}.\numberthis{eq:argmax}
\end{align*}

A well-known closed form solution to the above entropy-regularized problem is given by the softmax function. In particular, let

\[
\vec{w}_i^{t+1}(a) \defeq \frac{\eta}{1+t\lambda_i\eta} \mleft(t\lambda_i \log \vec{\tau}_i(a) + \sum_{t'=1}^t \utilde_i(a, \vec{a}_{-i}^{t'})\mright)\qquad\forall a\in A_i.\numberthis{eq:def w}
\]

\[
\vec{\pi}_i^{t+1}(a) = \frac{\exp\{\vec{w}_i^{t+1}(a)\}}{\sum_{a'\in A_i} \exp\{\vec{w}_i^{t+1}(a')\}} \qquad\forall a \in A_i,
\]

which coincides with the iterate produced by <ref>.

The next observation shows that the iterates $\vec{\pi}_i$ do not change if the utility function $u_i$ is first shifted to be in the range $[0,D_i]$.

Consider the shifted utilities

\[
\utilde_i(a,\vec{a}_{-i}^t) \defeq u_i(a, \vec{a}_{-i}^{t'}) - \min_{\vec{a}\in A_1\times \dots\times A_n} u_i(\vec{a}) \in [0, D_i]\numberthis{eq:def utilde}
\]

and let $\vec{v}$ be defined as (<ref>) using $\utilde_i$ in place of $u_i$, that is,

\[
\vec{v}_i^{t+1}(a) \defeq \frac{\eta}{1+t\lambda_i\eta} \mleft(t\lambda_i \log \vec{\tau}_i(a) + \sum_{t'=1}^t \utilde_i(a, \vec{a}_{-i}^{t'})\mright)\qquad\forall a\in A_i.\numberthis{eq:def v}
\]

Then, the iterates $\vec{\pi}_i$ can be equivalently expressed as

\[
\vec{\pi}_i^{t+1}(a) = \frac{\exp\{\vec{v}_i^{t+1}(a)\}}{\sum_{a'\in A_i} \exp\{\vec{v}_i^{t+1}(a')\}} \qquad\forall a \in A_i.
\]

Let $\gamma \defeq \\min_{\vec{a}\in A_1\times \dots\times A_n} u_i(\vec{a})$ denote the minimum utility that Player $i$ can get against the actions of the opponents. Since the argmax of a function does not change if a constant is added to the objective, from (<ref>) we can write

\begin{align*}
\vec{\pi}_{i}^{t+1} &= \argmax_{\vec{\pi}\in\Delta(A_i)}\mleft\{ -\frac{\eta}{1+t\lambda_i\eta}\gamma + \frac{\eta}{1+t\lambda_i\eta}\sum_{a\in A_i}\mleft(t\lambda_i \log\vec{\tau}_i(a) + \sum_{t'=1}^{t} u_i(a, \vec{a}_{-i}^{t'})\mright)\vec{\pi}(a) - \sum_{a\in A_i}\vec{\pi}(a)\log\vec{\pi}(a)\mright\}\\
&= \argmax_{\vec{\pi}\in\Delta(A_i)}\mleft\{ \frac{\eta}{1+t\lambda_i\eta}\sum_{a\in A_i}\mleft(t\lambda_i \log\vec{\tau}_i(a) + \sum_{t'=1}^{t} (u_i(a, \vec{a}_{-i}^{t'}) - \gamma)\mright)\vec{\pi}(a) - \sum_{a\in A_i}\vec{\pi}(a)\log\vec{\pi}(a)\mright\}\\
&= \argmax_{\vec{\pi}\in\Delta(A_i)}\mleft\{ \sum_{a\in A_i}\vec{v}_i^{t+1}(a)\vec{\pi}(a) - \sum_{a\in A_i}\vec{\pi}(a)\log\vec{\pi}(a)\mright\},
\end{align*}

where the second equality follows from the fact that $\vec{\pi}\in\Delta(A_i)$.

A solution is again given by softmax function

\[
\vec{\pi}_i^{t+1}(a) = \frac{\exp\{\vec{v}_i^{t+1}(a)\}}{\sum_{a'\in A_i} \exp\{\vec{v}_i^{t+1}(a')\}} \qquad\forall a \in A_i.\numberthis{eq:pi fn v}
\]

In the rest of the proof we will use (<ref>) to analyze the iterates $\vec{\pi}_i$ produced by the algorithm.

Let $\eta \le 1/(\lambda_i\beta_i + 2D_i)$. Then, at all times $t$,

\[
\|\vec{\pi}_i^{t+1} - \vec{\pi}_i^t\|_{\nabla^2 \varphi(\vec{\pi}_i^t)} \le \frac{\sqrt{3}\,e}{t\lambda_i\eta}.
\]

At all times $t$, introduce the vector $\vec{\xi}^t_i \in \mathbb{R}^{|A_i|}$ defined as

\begin{equation}
\vec{\xi}^{t}_i(a) \defeq \frac{\eta}{1+t\lambda_i\eta} \mleft(  - \lambda_i \vec{v}^t(a) + \lambda_i \log\vec{\tau}_i(a) + \utilde_i(a, \vec{a}_{-i}^t) \mright) \qquad\forall a\in A_i.\label{eq:def xi}
\end{equation}

At all times $t$ and for all $a$, it holds that

\begin{align*}
\vec{v}_i^{t+1}(a) &= \frac{\eta}{1+t\lambda_i\eta}\mleft(\frac{1+(t-1)\lambda_i\eta}{\eta}\vec{v}^t(a) + \lambda_i \log\vec{\tau}_i(a) + \utilde_i(a, \vec{a}_{-i}^t)\mright)\\
&= \frac{\eta}{1+t\lambda_i\eta}\mleft(\frac{1+t\lambda_i\eta}{\eta}\vec{v}^t(a) - \lambda_i \vec{v}^t(a) + \lambda_i \log\vec{\tau}_i(a) + \utilde_i(a, \vec{a}_{-i}^t)\mright)\\
&= \vec{v}^t(a) + \vec{\xi}_i^t(a).\numberthis{eq:v t plus 1}
\end{align*}

Substituting (<ref>) we can write

\[
\vec{\pi}_i^{t+1}(a) = \frac{\exp\{\vec{v}_i^t(a)\}\cdot\exp\{\vec{\xi}_i^t(a)\}}{\sum_{a'\in A_i}\exp\{\vec{v}_i^t(a')\}\cdot\exp\{\vec{\xi}_i^t(a')\}} = \frac{\vec{\pi}_i^t(a) \exp\{\vec{\xi}_i^t(a)\}}{\sum_{a' \in A_i} \vec{\pi}_i^t(a') \exp\{\vec{\xi}_i^t(a')\}}.
\numberthis{eq:pi t plus 1}
\]

Expanding the definition of the local norm induced by $\nabla^2 \varphi(\vec{\pi}_i^t)$ we find

\begin{align*}
\|\vec{\pi}_i^{t+1} - \vec{\pi}_i^t\|^2_{\nabla^2 \varphi(\vec{\pi}_i^t)} &= \sum_{a\in A_i} \frac{1}{\vec{\pi}_i^t(a)} \mleft(\vec{\pi}_i^{t+1}(a) - \vec{\pi}_i^t(a)\mright)^2\\
&= \sum_{a\in A_i} \vec{\pi}_i^t(a) \mleft( \frac{\exp\{\vec{\xi}_i^t(a)\}}{\sum_{a' \in A_i} \vec{\pi}_i^t(a') \exp\{\vec{\xi}_i^t(a')\}} -1\mright)^2 \numberthis{eq:norm expansion 1}\\
&= \sum_{a\in A_i} \vec{\pi}_i^t(a) \mleft[ \mleft(\frac{\exp\{\vec{\xi}_i^t(a)\}}{\sum_{a' \in A_i} \vec{\pi}_i^t(a') \exp\{\vec{\xi}_i^t(a')\}}\mright)^2 - 2\mleft(\frac{\exp\{\vec{\xi}_i^t(a)\}}{\sum_{a' \in A_i} \vec{\pi}_i^t(a') \exp\{\vec{\xi}_i^t(a')\}}\mright) +1\mright]\\
&=\frac{\sum_{a\in A_i} \vec{\pi}_i^t(a)\exp\{\vec{\xi}_i^t(a)\}^2}{\mleft(\sum_{a' \in A_i} \vec{\pi}_i^t(a') \exp\{\vec{\xi}_i^t(a')\}\mright)^2} - 2\frac{\sum_{a\in A_i} \vec{\pi}_i^t(a)\exp\{\vec{\xi}_i^t(a)\}}{\sum_{a' \in A_i} \vec{\pi}_i^t(a') \exp\{\vec{\xi}_i^t(a')\}} +\sum_{a\in A_i} \vec{\pi}_i^t(a)\\
&=\frac{\sum_{a\in A_i} \vec{\pi}_i^t(a)\exp\{\vec{\xi}_i^t(a)\}^2}{\mleft(\sum_{a' \in A_i} \vec{\pi}_i^t(a') \exp\{\vec{\xi}_i^t(a')\}\mright)^2} -1\numberthis{eq:norm expansion 2},
\end{align*}

where (<ref>) follows from substituting (<ref>). We now apply <ref>, applied with $\vec{q} = \vec{\xi}_i^t$, $\vec{p} = \vec{\pi}_i^t$, and $A = A_i$. First, we study the range $D_i = \max_{a,a'\in A_i} \{\vec{\xi}_i^t(a) - \vec{\xi}_i^t(a')\}$ used in the statement of the Lemma. In particular, using (<ref>) we have

\begin{align*}
\max_{a,a'\in A_i} \{\vec{\xi}_i^t(a) - \vec{\xi}_i^t(a')\} &= \max_{a,a'\in A_i} \{\vec{v}_i^{t+1}(a) - \vec{v}_i^{t}(a) - \vec{v}_i^{t+1}(a') + \vec{v}_i^{t}(a')\}\\
&=\max_{a,a'\in A_i} \mleft\{(\log\vec{\tau}_i(a)-\log\vec{\tau}_i(a')) \cdot \mleft(\frac{t\lambda_i\eta}{1+t\lambda_i\eta} - \frac{(t-1)\lambda_i\eta}{1+(t-1)\lambda_i\eta}\mright) \mright.\\&\hspace{5cm}
+\ \frac{\eta}{1+t\lambda_i\eta}\mleft(\sum_{t'=1}^t \utilde_i(a, \vec{a}_{-i}^{t'}) - \utilde_i(a',\vec{a}_{-i}^{t'})\mright) \\&\hspace{5cm}
\mleft. -\ \frac{\eta}{1+(t-1)\lambda_i\eta}\mleft(\sum_{t'=1}^{t-1} \utilde_i(a, \vec{a}_{-i}^{t'}) - \utilde_i(a',\vec{a}_{-i}^{t'})\mright)\mright\}\\
&=\max_{a,a'\in A_i} \mleft\{\frac{\lambda_i\eta}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}(\log\vec{\tau}_i(a)-\log\vec{\tau}_i(a')) \mright.\\&\hspace{4cm}
+\ \frac{\lambda_i\eta^2}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}\mleft(\sum_{t'=1}^{t-1} \utilde_i(a, \vec{a}_{-i}^{t'}) - \utilde_i(a',\vec{a}_{-i}^{t'})\mright)\\&\hspace{4cm}
\mleft.+\ \frac{\eta}{1+t\lambda_i\eta}(\utilde_i(a,\vec{a}_{-i}^t) - \utilde_i(a',\vec{a}_{-i}^t))\mright\}\\
&\le\max_{a,a'\in A_i} \mleft\{\frac{\lambda_i\eta}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}(\log\vec{\tau}_i(a)-\log\vec{\tau}_i(a')) \mright\}\\&\hspace{2cm}
+\ \max_{a,a'\in A_i} \mleft\{\frac{\lambda_i\eta^2}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}\mleft(\sum_{t'=1}^{t-1} \utilde_i(a, \vec{a}_{-i}^{t'}) - \utilde_i(a',\vec{a}_{-i}^{t'})\mright)\mright\}\\&\hspace{4cm}
+\ \max_{a,a'\in A_i} \mleft\{\frac{\eta}{1+t\lambda_i\eta}(\utilde_i(a,\vec{a}_{-i}^t) - \utilde_i(a',\vec{a}_{-i}^t))\mright\}\\
&\le \eta(\lambda_i\beta_i + 2D_i),\numberthis{eq:xi bound}
\end{align*}

where the first inequality follows from upper bounding the max of a sum with the sum of max of each term, and the second inequality follows from noting that

\[
\frac{\lambda_i\eta}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)} \le \frac{\eta}{1+t\lambda_i\eta} \le \eta,
\]

\[\frac{\lambda_i\eta^2}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)} \le \frac{\eta}{t}
\mleft(\sum_{t'=1}^{t-1} \utilde_i(a, \vec{a}_{-i}^{t'}) - \utilde_i(a',\vec{a}_{-i}^{t'})\mright) \le \frac{\lambda_i\eta^2}{t\lambda_i\eta}\cdot tD_i = \eta D_i.
\]

Applying <ref> to the right-hand side of (<ref>) using the bound on the range of $\vec{\xi}_i^t$ shown in (<ref>) yields

\begin{align*}
\|\vec{\pi}_i^{t+1} - \vec{\pi}_i^t\|^2_{\nabla^2 \varphi(\vec{\pi}_i^t)} &\le \frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2} \sum_{a\in A_i} \vec{\pi}_i^t(a)\mleft(\vec{\xi}_i^t(a)\mright)^2.\numberthis{eq:after lemma 2}
\end{align*}

Using the fact that any convex combination of values is upper bounded by the maximum value, we can further bound the right-hand side of (<ref>) as

\begin{align*}
\|\vec{\pi}_i^{t+1} - \vec{\pi}_i^t\|^2_{\nabla^2 \varphi(\vec{\pi}_i^t)}
&\le \frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2}\max_{a\in A_i} (\vec{\xi}_i^t(a))^2\\
&= \frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2}\max_{a\in A_i} \mleft(\vec{v}_i^{t+1}(a) - \vec{v}_i^t(a)\mright)^2,
\end{align*}

where the equality follows from (<ref>). Hence, expanding the definition of $\vec{v}^t_i$ and $\vec{v}_i^{t+1}$,

\begin{align*}
\|\vec{\pi}_i^{t+1} - \vec{\pi}_i^t\|^2_{\nabla^2 \varphi(\vec{\pi}_i^t)}
&\le\frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2}\max_{a\in A_i} \mleft\{ \mleft(\frac{t\lambda_i\eta}{1+t\lambda_i\eta} - \frac{(t-1)\lambda_i\eta}{1+(t-1)\lambda_i\eta}\mright)\log\vec{\tau}_i(a) \mright.\\&\hspace{5cm}
\mleft.+\ \frac{\eta}{1+t\lambda_i\eta}\sum_{t'=1}^t \utilde_i(a, \vec{a}_{-i}^{t'}) - \frac{\eta}{1+(t-1)\lambda_i\eta}\sum_{t'=1}^{t-1} \utilde_i(a, \vec{a}_{-i}^{t'})\mright\}^2\\
&= \frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2}\max_{a\in A_i} \mleft\{\frac{\lambda_i\eta}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}\log\vec{\tau}_i(a) + \frac{\eta}{1+t\lambda_i\eta}\utilde_i(a,\vec{a}_{-i}^{t})\mright.\\&\hspace{6.9cm} - \mleft.\frac{\lambda_i\eta^2}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}\sum_{t'=1}^{t-1}\utilde_i(a,\vec{a}_{-i}^{t'})\mright\}^{\!2}\\
&\le 3\frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2}\max_{a\in A_i} \mleft\{\mleft(\frac{\lambda_i\eta}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}\log\vec{\tau}_i(a)\mright)^2 + \mleft(\frac{\eta}{1+t\lambda_i\eta}\utilde_i(a,\vec{a}_{-i}^{t})\mright)^2 \mright.\\&\hspace{6.7cm} + \mleft.\mleft(\frac{\lambda_i\eta^2}{(1+t\lambda_i\eta)(1+(t-1)\lambda_i\eta)}\sum_{t'=1}^{t-1}\utilde_i(a,\vec{a}_{-i}^{t'})\mright)^2\mright\}\\
&= \frac{3}{(1+t\lambda_i\eta)^2}\frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2}\max_{a\in A_i} \mleft\{\mleft(\frac{\lambda_i\eta}{1+(t-1)\lambda_i\eta}\log\vec{\tau}_i(a)\mright)^2 + \mleft({\eta}\utilde_i(a,\vec{a}_{-i}^{t})\mright)^2 \mright.\\&\hspace{6.7cm} + \mleft.\mleft(\frac{\lambda_i\eta^2}{(1+(t-1)\lambda_i\eta)}\sum_{t'=1}^{t-1}\utilde_i(a,\vec{a}_{-i}^{t'})\mright)^2\mright\}\\
&\le \frac{3}{(1+t\lambda_i\eta)^2}\frac{\exp\{2 \eta(\lambda_i\beta_i + 2D_i)\}}{\eta^2(\lambda_i\beta_i + 2D_i)^2}(\lambda^2\eta^2\beta_i^2 + 2\eta^2 D_i^2) \\
&\le 3\frac{\exp\{2\eta(\lambda_i\beta_i + 2D_i)\}}{(1+t\lambda_i\eta)^2}\\
&\le 3\frac{\exp\{2\eta(\lambda_i\beta_i + 2D_i)\}}{(t\lambda_i\eta)^2} = \mleft(\sqrt{3}\cdot\frac{\exp\{\eta(\lambda_i\beta_i + 2D_i)\}}{t\lambda_i\eta}\mright)^2.
\end{align*}

Using the hypothesis that $\eta \le 1/(\lambda_i \beta_i + 2D_i)$ and taking square roots yields the statement.

§.§ Completing the analysis

Fix a player $i \in \{1, \dots, n\}$. The regret

\[
R_{i}^T \defeq \max_{\vec{\pi}^* \in \Delta(A_i)}\sum_{t=1}^T\mathcal{U}_{i}^t(\vec{\pi}^*) - \sum_{t=1}^T\mathcal{U}_{i}^t(\vec{\pi}^t_{i})
\]

incurred up to any time $T$ by policies $\vec{\pi}^t_{i}$ defined in (<ref>) where the learning rate is set to any value $0 < \eta \le 1/(\lambda_i\beta_i + 2D_i)$, satisfies

\[
R_{i}^T \le \frac{\log |A_i|}{\eta} + \frac{3\,e ( 1+ \log T)}{\lambda_i\eta}(D_i+\lambda_i\beta_i+\lambda_i\sqrt{|A_i|}),
\]

where $D_i$ is any upper bound on the range of the possible rewards of Player $i$, and

\begin{equation}
\beta_i \defeq \max_{a\in A_i} \log(1/\vec{\tau}(a)).
\label{eq:def beta i}
\end{equation}

\[
\vec{q}^t_i \defeq \Big(\utilde_i(a, \vec{a}^t_{-i})\Big)_{a\in A_i},
\]

and note that, by definition of the regularized utilities $\mathcal{U}_i$,

\begin{align*}
\mathcal{U}_i^t(\vec{\pi}^{t+1}_i) - \mathcal{U}_i^t(\vec{\pi}^t_i)
&=  \vec{q}_i^\top \mleft(\vec{\pi}^{t+1}_i - \vec{\pi}^t_i\mright) - \lambda_i \KL{\vec{\pi}^{t+1}_i}{\vec{\tau}} + \lambda_i\KL{\vec{\pi}^t_i}{\vec{\tau}}\\
&=  \vec{q}_i^\top \mleft(\vec{\pi}^{t+1}_i - \vec{\pi}^t_i\mright) - \lambda_i \varphi(\vec{\pi}^{t+1}_i) + \lambda_i\varphi(\vec{\pi}^t_i) - \lambda_i \nabla\varphi(\vec{\tau}_i)^\top (\vec{\pi}^t_i - \vec{\pi}^{t+1}_i)\\
&=  \mleft(\vec{q}_i - \nabla \varphi(\vec{\tau}_i)\mright)^\top \mleft(\vec{\pi}^{t+1}_i - \vec{\pi}^t_i\mright) - \lambda_i \varphi(\vec{\pi}^{t+1}_i) + \lambda_i\varphi(\vec{\pi}^t_i)\\
&\le  \mleft(\vec{q}_i + \nabla \varphi(\vec{\tau}_i)\mright)^\top \mleft(\vec{\pi}^{t+1}_i - \vec{\pi}^t_i\mright) - \lambda_i \varphi(\vec{\pi}^{t}_i) - \lambda_i \nabla\varphi(\vec{\pi}^t_i)^\top (\vec{\pi}^{t+1}_i - \vec{\pi}^t_i) + \lambda_i\varphi(\vec{\pi}^t_i)\\
&=  \mleft(\vec{q}_i + \lambda_i\nabla \varphi(\vec{\tau}_i) - \lambda_i\nabla\varphi(\vec{\pi}^t_i)\mright)^\top \mleft(\vec{\pi}^{t+1}_i - \vec{\pi}^t_i\mright)\\
&\le \mleft\|\vec{q}_i + \lambda_i\nabla \varphi(\vec{\tau}_i) - \lambda_i\nabla\varphi(\vec{\pi}^t_i)\mright\|_{\nabla^{-2}\varphi(\vec{\pi}^t_i)}\cdot \mleft\|\vec{\pi}^{t+1}_i - \vec{\pi}^t_i\mright\|_{\nabla^2\varphi(\vec{\pi}^t_i)},
\end{align*}

where the first inequality follows by convexity and the second inequality by the generalized Cauchy-Schwarz inequality with the primal-dual norm pair $\|\cdot\|_{\nabla^2\varphi(\vec{\pi}^t_i)}$ and $\|\cdot\|_{\nabla^{-2}\varphi(\vec{\pi}^t_i)}$.
A bound for the second term in the product if given by <ref>. We now bound the first norm. First,

\begin{align*}
\mleft\|\vec{q}_i + \lambda_i\nabla \varphi(\vec{\tau}_i) - \lambda_i\nabla\varphi(\vec{\pi}^t_i)\mright\|_{\nabla^{-2}\varphi(\vec{\pi}^t_i)}^2 &= \sum_{a\in A_i} \vec{\pi}^t(a) \cdot\mleft( \tilde u_i(a, \vec{a}_{-i}^t) + \lambda_i \log \vec{\tau}_i(a) - \lambda_i \log\vec{\pi}^t_i(a)\mright)^2        \\
&\le 3\sum_{a\in A_i} \vec{\pi}^t(a) \cdot\mleft( \tilde u_i(a, \vec{a}_{-i}^t)^2 + \lambda_i^2 (\log \vec{\tau}_i(a))^2 + \lambda_i^2 (\log\vec{\pi}^t_i(a))^2\mright)\\
&\le 3\mleft(D_i^2 + \lambda_i^2\beta_i^2 + \lambda_i^2|A_i|\mright)\\
&\le 3\mleft(D_i + \lambda_i\beta_i + \lambda_i \sqrt{|A_i|}\mright)^2,
\end{align*}

where the second inequality follows from the fact that $x \log^2 x \le 1$ for all $x\in [0,1]$.
Taking square roots, we find

\[
\mleft\|\vec{q}_i + \lambda_i\nabla \varphi(\vec{\tau}_i) - \lambda_i\nabla\varphi(\vec{\pi}^t_i)\mright\|_{\nabla^{-2}\varphi(\vec{\pi}^t_i)} \le \sqrt{3}\mleft(D_i + \lambda_i\beta_i + \lambda_i \sqrt{|A_i|}\mright).
\]

So, using <ref>, we can write

\[
\mathcal{U}_i^t(\vec{\pi}^{t+1}_i) - \mathcal{U}_i^t(\vec{\pi}^t_i) \le \frac{3\,e}{t\lambda_i\eta}(D_i+\lambda_i\beta_i+\lambda_i\sqrt{|A_i|}).
\]

Plugging in the above expression into <ref> yields

\begin{align*}
R^T_i &\le \frac{\log |A_i|}{\eta} + \sum_{t=1}^T \frac{3\,e}{t\lambda_i\eta}(D_i+\lambda_i\beta_i+\lambda_i\sqrt{|A_i|})\\
&\le \frac{\log |A_i|}{\eta} + \frac{3\,e ( 1+ \log T)}{\lambda_i\eta}(D_i+\lambda_i\beta_i+\lambda_i\sqrt{|A_i|}),
\end{align*}

which is the statement.

§.§ Proof of <ref>

By definition of regret,

\begin{align*}
\frac{1}{T}R_i^T &= \frac{1}{T}\max_{{\vec{\pi}}^*_i\in\Delta(A_i)}\mleft\{\sum_{t=1}^T \mathcal{U}^t_i({\vec{\pi}}^*_i) - \mathcal{U}^t_i({\vec{\pi}}^t_i) \mright\}\\
&=\max_{{\vec{\pi}}^*_i\in\Delta(A_i)}\mleft\{\mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^*_i, \vec{\pi}_{-i}^t)\mright) - \mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^t_i, \vec{\pi}_{-i}^t)\mright) - \frac{\lambda_i}{T}\sum_{t=1}^T \KL{\vec{\pi}_i^*}{\vec{\tau}_i} + \frac{\lambda_i}{T}\sum_{t=1}^T \KL{\vec{\pi}_i^t}{\vec{\tau}_i} \mright\}\\
&=\max_{{\vec{\pi}}^*_i\in\Delta(A_i)}\mleft\{\mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^*_i, \vec{\pi}_{-i}^t)\mright) - \mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^t_i, \vec{\pi}_{-i}^t)\mright) - \lambda_i \KL{\vec{\pi}_i^*}{\vec{\tau}_i} + \frac{\lambda_i}{T}\sum_{t=1}^T \KL{\vec{\pi}_i^t}{\vec{\tau}_i} \mright\}\\
&\ge\max_{{\vec{\pi}}^*_i\in\Delta(A_i)}\mleft\{\mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^*_i, \vec{\pi}_{-i}^t)\mright) - \mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^t_i, \vec{\pi}_{-i}^t)\mright) + \frac{\lambda_i}{T}\sum_{t=1}^T \KL{\vec{\pi}_i^t}{\vec{\tau}_i} \mright\}\\
&\ge\max_{{\vec{\pi}}^*_i\in\Delta(A_i)}\mleft\{\mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^*_i, \vec{\pi}_{-i}^t)\mright) - \mleft(\frac{1}{T}\sum_{t=1}^T u_i({\vec{\pi}}^t_i, \vec{\pi}_{-i}^t)\mright) + \lambda_i  \KL{\bar{\vec{\pi}}_i^T}{\vec{\tau}_i} \mright\}\\
&=\max_{{\vec{\pi}}^*_i\in\Delta(A_i)}\mleft\{\mleft(\frac{1}{T}\sum_{t=1}^T (u_i({\vec{\pi}}^*_i, \vec{\pi}_{-i}^t)- u_i({\vec{\pi}}^t_i, \vec{\pi}_{-i}^t)\mright) + \lambda_i  \KL{\bar{\vec{\pi}}_i^T}{\vec{\tau}_i} \mright\}\\
&\ge \max_{{\vec{\pi}}^*_i\in\Delta(A_i)}\mleft\{\mleft(\frac{1}{T}\sum_{t=1}^T -D_i\mright) + \lambda_i  \KL{\bar{\vec{\pi}}_i^T}{\vec{\tau}_i} \mright\} = -D_i + \lambda_i  \KL{\bar{\vec{\pi}}_i^T}{\vec{\tau}_i},
\end{align*}

where the first inequality holds since the KL divergence is nonnegative, the second inequality by convexity of the KL divergence, and the third inequality by definition of $D_i$. Rearranging yields the inequality in the statement.

§.§ Relationship with Nash Equilibrium

In this subsection, we show that when all players play according to <ref> in a two-player zero-sum game, then the average policies $\bar{\vec{\pi}}_{i}^T$ converge to a Nash equilibrium of the regularized game whose utilities are $\mathcal{U}_i$.

For any $T \in \mathbb{N}$, $\eta > 0$, and $\delta \in (0,1)$, define the quantity

\[
\xi^T(\delta) \defeq
\frac{R_1^T+ R_2^T}{T} + (\max_i D_i)\sqrt{\frac{32}{T}\log\frac{2\max_i |A_i|}{\delta}}.
\]

Upon running <ref> for any $T$ iterations with learning rate $\eta > 0$, the average policies
$\bar{\vec{\pi}}_{i}^T$ of each player form a $\xi^T(\delta)$-approximate Nash equilibrium with respect to the regularized utility functions $\mathcal{U}_{i}$ with probability at least $1-\delta$, for any $\delta \in (0,1)$.

Fix a player $i\in\{1,2\}$, and any policy $\vec{\pi}^*\in\Delta(A_i)$, and introduce the discrete-time stochastic process

\begin{align*}
w^t &\defeq \Big(\ut{\vec{\pi}^*}{\tildepi{-i}} - \ut{\pit}{\tildepi{-i}}\Big) - \Big(\ut{\vec{\pi}^*}{a_{-i}^t} - \ut{\pit}{a_{-i}^t}\Big).
\end{align*}

Since the opponent player $-i$ plays according to <ref>, its action $a_{-i}^t$ at all times $t$ is selected by sampling (unbiasedly) an action from the policy $\vec{\pi}^t_{-i}$. Therefore, $w^t$ is a martingale difference sequence. Furthermore, by expanding the definition of $\mathcal{U}_i$, the absolute value of $w^t$ satisfies

\begin{align*}
|w^t| &= \mleft|\Big(u_i(\vec{\pi}^*,  \tildepi{-i}) - u_i(\pit, \tildepi{-i})\Big) - \Big(u_i(\vec{\pi}^*, a_{-i}^t) - u_i(\pit, a_{-i}^t)\Big)\mright| \\
&\le \mleft|u_i(\vec{\pi}^*,  \tildepi{-i}) - u_i(\pit, \tildepi{-i})\mright| - \mleft|u_i(\vec{\pi}^*, a_{-i}^t) - u_i(\pit, a_{-i}^t)\mright| \le 2D_i.
\end{align*}

Hence, using Azuma-Hoeffding's inequality, for any $\delta \in (0,1)$,

\begin{align*}
1-\delta &\le \mathbb{P}\mleft[ \sum_{t=1}^T w^t \le D_i\sqrt{8T \log \frac{1}{\delta}}\mright]\\
&= \mathbb{P}\mleft[ \mleft(\sum_{t=1}^T \ut{\vec{\pi}^*}{\tildepi{-i}} - \sum_{t=1}^T \ut{\pit}{\tildepi{-i}}\mright) - \mleft(\sum_{t=1}^T u_i(\vec{\pi}^*, a^t_{-i}) - \sum_{t=1}^T \ut{\pit}{a_{-i}^t}\mright) \le \sqrt{8T \log \frac{1}{\delta}}\mright]\\
&= \mathbb{P}\mleft[ \sum_{t=1}^T \ut{\vec{\pi}^*}{\tildepi{-i}} - \sum_{t=1}^T \ut{\pit}{\tildepi{-i}} \le R^T_{i} + D_i\sqrt{8T \log \frac{1}{\delta}}\mright],
\end{align*}

where $R^T_{i}$ is as defined in <ref>.
Since the above expression holds for any $\vec{\pi}^*\in\Delta(A_i)$, in particular, using the union bound on each $a \in A_i$,

\begin{equation}\label{eq:regret tilde}
\mathbb{P}\mleft[ \max_{\vec{\pi}^* \in \Delta(A_i)}\sum_{t=1}^T \ut{\vec{\pi}^*}{\tildepi{-i}} - \sum_{t=1}^T \mathcal{U}_i(\vec{\pi}_{i}^t, {\vec{\pi}}_{-i}^t) \le R^T_{i} + D_i\sqrt{8T \log \frac{|A_i|}{\delta}}\mright] \ge 1-\delta
\end{equation}

for any player $i\in\{1,2\}$ and any $\delta\in (0,1)$.

Summing Inequality (<ref>) for $i\in\{1,2\}$ and using the union bound, we can further write

\begin{align}
&\mathbb{P}\mleft[ \max_{\vec{\pi}_1^* \in \Delta(A_1)}\mleft\{\sum_{t=1}^T \mathcal{U}_1(\vec{\pi}_1^*,\tildepi{2})\mright\} +
\max_{\vec{\pi}_2^* \in \Delta(A_2)}\mleft\{\sum_{t=1}^T \mathcal{U}_2(\tildepi{1},\vec{\pi}_2^*)\mright\}
- \mleft(\sum_{t=1}^T \mathcal{U}_1(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t) + \mathcal{U}_2(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t)\mright)\mright. \nonumber\\
&\hspace{7cm}\mleft.\le R^T_{1} + R^T_2 + (\max_i D_i)\sqrt{32T \log \frac{\max_i |A_i|}{\delta}}\mright] \ge 1-2\delta.\nonumber
\end{align}

Dividing by $T$ and noting that for any player $i\in\{1,2\}$

\begin{align*}
\frac{1}{T} \sum_{t=1}^T \ut{\vec{\pi}^*}{\tildepi{-i}} &= \mathcal{U}_{i}\mleft(\vec{\pi}^*, \frac{1}{T}\sum_{t=1}^T \tildepi{-i}\mright) = \mathcal{U}_{i}\mleft(\vec{\pi}^*, \bar{\vec{\pi}}^T_{-i}\mright)
\end{align*}

further yields

\begin{align}
&\mathbb{P}\mleft[ \max_{\vec{\pi}_1^* \in \Delta(A_1)}\mleft\{\mathcal{U}_1(\vec{\pi}_1^*,\bar{\vec{\pi}}^T_{2})\mright\} +
\max_{\vec{\pi}_2^* \in \Delta(A_2)}\mleft\{\mathcal{U}_2(\bar{\vec{\pi}}^T_1,\vec{\pi}_2^*)\mright\}
- \frac{1}{T}\mleft(\sum_{t=1}^T \mathcal{U}_1(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t) + \mathcal{U}_2(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t)\mright)\mright. \nonumber\\
&\hspace{10cm}\mleft.\le \frac{R^T_{1} + R^T_2}{T} + D_i\sqrt{\frac{32}{T} \log \frac{\max_i |A_i|}{\delta}}\mright] \ge 1-2\delta.\label{eq:regret sum 2}
\end{align}

We now analyze the term in parenthesis, that is,

\[
(\clubsuit) \defeq -\frac{1}{T}\mleft(\sum_{t=1}^T \mathcal{U}_1(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t) + \mathcal{U}_2(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t)\mright)
\]

Plugging in the definition of $\mathcal{U}_1$ and $\mathcal{U}_2$, that is,

\begin{align*}
\mathcal{U}_1(\vec{\pi}_1,\vec{\pi}_2) &\defeq u_1(\vec{\pi}_1,\vec{\pi}_2) - \lambda_1 \KL{\vec{\pi}_1}{\vec{\tau}_1}\\
\mathcal{U}_2(\vec{\pi}_1,\vec{\pi}_2) &\defeq u_2(\vec{\pi}_1,\vec{\pi}_2) - \lambda_2 \KL{\vec{\pi}_2}{\vec{\tau}_2} = -u_1(\vec{\pi}_1,\vec{\pi}_2) + \lambda_2 \KL{\vec{\pi}_2}{\vec{\tau}_2}
\end{align*}

into $(\clubsuit)$ yields

\begin{align}
(\clubsuit) = -\frac{1}{T}\mleft(\sum_{t=1}^T \mathcal{U}_1(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t) + \mathcal{U}_2(\vec{\pi}_{1}^t, {\vec{\pi}}_{2}^t)\mright) &= \frac{1}{T}\mleft(\sum_{t=1}^T\lambda_1 \KL{\tildepi{1}}{\vec{\tau}_1} + \lambda_2\KL{\tildepi{2}}{\vec{\tau}_2}\mright) \nonumber\\
&\ge \lambda_1 \KL{\bar{\vec{\pi}}_1^T}{\vec{\tau}_1} + \lambda_2 \KL{\bar{\vec{\pi}}_2^T}{\vec{\tau}_2}\label{eq:step1x}\\
&= -\mleft(\mathcal{U}_1(\bar{\vec{\pi}}_1^T, \bar{\vec{\pi}}_2^T) + \mathcal{U}_2(\bar{\vec{\pi}}_1^T, \bar{\vec{\pi}}_2^T)\mright),\label{eq:step2x}
\end{align}

where (<ref>) follows from convexity of the KL divergence function, and (<ref>) follows again from the definition of $\mathcal{U}_1$ and $\mathcal{U}_2$. Substituting (<ref>) back into (<ref>), we find

\begin{align}
&\mathbb{P}\mleft[ \max_{\vec{\pi}_1^* \in \Delta(A_1)}\mleft\{\mathcal{U}_1(\vec{\pi}_1^*,\bar{\vec{\pi}}^T_{2}) - \mathcal{U}_1(\bar{\vec{\pi}}^T_1, \bar{\vec{\pi}}^T_2)\mright\} +
\max_{\vec{\pi}_2^* \in \Delta(A_2)}\mleft\{\mathcal{U}_2(\bar{\vec{\pi}}^T_1,\vec{\pi}_2^*) - \mathcal{U}_2(\bar{\vec{\pi}}^T_1, \bar{\vec{\pi}}^T_2)\mright\}\mright. \nonumber\\
\le \frac{R^T_{1} + R^T_2}{T} + (\max_i D_i)\sqrt{\frac{32}{T} \log \frac{\max_i |A_i|}{\delta}}\mright] \ge 1-2\delta.
\end{align}

\[
\max_{\vec{\pi}_1^* \in \Delta(A_1)}\mleft\{\mathcal{U}_1(\vec{\pi}_1^*,\bar{\vec{\pi}}^T_{2}) - \mathcal{U}_1(\bar{\vec{\pi}}^T_1, \bar{\vec{\pi}}^T_2)\mright\} \ge 0,\quad\text{and}\quad
\qquad
\max_{\vec{\pi}_2^* \in \Delta(A_2)}\mleft\{\mathcal{U}_2(\bar{\vec{\pi}}^T_1,\vec{\pi}_2^*) - \mathcal{U}_2(\bar{\vec{\pi}}^T_1, \bar{\vec{\pi}}^T_2)\mright\} \ge 0,
\]

the inequality above in particular implies that

\begin{align}
&\mathbb{P}\mleft[ \max\mleft\{\max_{\vec{\pi}_1^* \in \Delta(A_1)}\mleft\{\mathcal{U}_1(\vec{\pi}_1^*,\bar{\vec{\pi}}^T_{2}) - \mathcal{U}_1(\bar{\vec{\pi}}^T_1, \bar{\vec{\pi}}^T_2)\mright\},
\max_{\vec{\pi}_2^* \in \Delta(A_2)}\mleft\{\mathcal{U}_2(\bar{\vec{\pi}}^T_1,\vec{\pi}_2^*) - \mathcal{U}_2(\bar{\vec{\pi}}^T_1, \bar{\vec{\pi}}^T_2)\mright\}\mright\}\mright. \nonumber\\
\le \frac{R^T_{1} + R^T_2}{T} + (\max_i D_i)\sqrt{\frac{32}{T} \log \frac{\max_i |A_i|}{\delta}}\mright] \ge 1-2\delta,
\end{align}

which is equivalent to the statement after making the variable substitution $\delta \defeq \delta'/2$.

In particular, when $\eta \le 1/(\lambda_i\beta_i + 2D_i)$ for both players $i\in\{1,2\}$, <ref> implies that the average strategy profile is a $O(1/\sqrt{T})$-Nash equilibrium with respect to the regularized utility functions $\mathcal{U}_i$.

A standard application of the Borel-Cantelli lemma enables to convert from the high-proability guarantees of <ref> at finite time to almost-sure convergence in the limit. Specifically,

Let $(\bar{\vec{\pi}}_1,\bar{\vec{\pi}}_2)$ be any limit point of the average policies $(\bar{\vec{\pi}}_{1}^T, \bar{\vec{\pi}}_2^T)$ of the players. Almost surely, $(\bar{\vec{\pi}}_1,\bar{\vec{\pi}}_2)$ is a Nash equilibrium with respect to the regularized utility functions $\mathcal{U}_{1},\mathcal{U}_2$, respectively.

From there, it is immediate to give guarantees with respect to the original (i.e., unregularized) game, and <ref> follows.

From <ref>, almost surely $(\bar{\vec{\pi}}_1,\bar{\vec{\pi}}_2)$ is a Nash equilibrium of the regularized game whose players' utilities are $\mathcal{U}_1$ and $\mathcal{U}_2$, respectively. Expanding the definition of Nash equilibrium relative to Player $1$, we have that

\begin{align*}
0 &=\max_{\vec{\pi}^*_1 \in \Delta(A_1)}\mleft\{\mathcal{U}_1(\vec{\pi}^*_1, \bar{\vec{\pi}}_2) - \mathcal{U}_1(\bar{\vec{\pi}}_1, \bar{\vec{\pi}}_2)\mright\}\\
&= \max_{\vec{\pi}^*_1 \in \Delta(A_1)}\mleft\{u_1(\vec{\pi}^*_1, \bar{\vec{\pi}}_2) - \lambda_1\KL{\vec{\pi}^*_1}{\vec{\tau}_1} - u_1(\bar{\vec{\pi}}_1, \bar{\vec{\pi}}_2) + \lambda_1\KL{\bar{\vec{\pi}}_1}{\vec{\tau}_1} \mright\}\\
&\ge \max_{\vec{\pi}^*_1 \in \Delta(A_1)}\mleft\{u_1(\vec{\pi}^*_1, \bar{\vec{\pi}}_2) - u_1(\bar{\vec{\pi}}_1, \bar{\vec{\pi}}_2) \mright\} - \lambda_1\KL{\vec{\pi}^*_1}{\vec{\tau}_1}\\
&= \max_{\vec{\pi}^*_1 \in \Delta(A_1)}\mleft\{(u_1(\vec{\pi}^*_1, \bar{\vec{\pi}}_2) - u_1(\bar{\vec{\pi}}_1, \bar{\vec{\pi}}_2))  - \lambda_1\sum_{a\in A_1} \vec{\pi}^*_i(a) \log(\vec{\pi}^*_i(a))-\lambda_1\sum_{a\in A_1} \vec{\pi}^*_1(a) \log(1/ \vec{\tau}_1(a))\mright\}\\
&\ge \max_{\vec{\pi}^*_1 \in \Delta(A_1)}\mleft\{(u_1(\vec{\pi}^*_1, \bar{\vec{\pi}}_2) - u_1(\bar{\vec{\pi}}_1, \bar{\vec{\pi}}_2)) -\lambda_1\sum_{a\in A_1} \vec{\pi}^*_1(a) \log(1/ \vec{\tau}_1(a))\mright\}\\
&\ge \max_{\vec{\pi}^*_1 \in \Delta(A_1)}\mleft\{u_1(\vec{\pi}^*_1, \bar{\vec{\pi}}_2) - u_1(\bar{\vec{\pi}}_1, \bar{\vec{\pi}}_2)\mright\} - \lambda_1\beta_1,
\end{align*}

where the first inequality follows since the KL divergence is alwasy nonnegative, the second inequality since the negative entropy function is nonpositive on the simplex, and the third inequality follows from the definition of $\beta_1$. Symmetrically, for Player $2$ we find that

\[
0 \ge \max_{\vec{\pi}^*_2 \in \Delta(A_2)}\mleft\{u_2(\bar{\vec{\pi}}_1, \vec{\pi}^*_2) - u_2(\bar{\vec{\pi}}_1, \bar{\vec{\pi}}_2)\mright\} - \lambda_2\beta_2.
\]

Hence, the exploitability of $\bar{\vec{\pi}}_1$ is at most $\lambda_1\beta_1$, while the exploitability of $\bar{\vec{\pi}}_2$ is at most $\lambda_2\beta_2$, which immediately implies the statement.

§ ILLUSTRATIONS OF PIKL-HEDGE IN BLOTTO

Comparison of piKL and regret matching as a function of $\lambda$ in Colonel Blotto(10, 3). As $\lambda$ increases in piKL-hedge, piKL moves closer to the anchor policy at the cost of increased exploitability. The scale of $\lambda$ is related to the scale of the payoffs in the game, which are [0, 1] in Blotto.

Colonel Blotto is a famous 2-player simultaneous action game that has a large action space but has rules that are short and simple. In Blotto, each player has $c$ coins to be distributed across $f$ fields. The aim is to win the most fields by allocating the player's coins across the fields. A field is won by contributing the most coins to that field (and drawn if there is a tie). The winner receives a reward of +1 and the loser receives -1. Both receive 0 in the case of a tie.

In Figure <ref> we illustrate the key features of piKL-Hedge in Blotto, using a uniform anchor policy for convenience. Incidentally, piKL-Hedge with a uniform anchor policy converges to a quantal response equilibrium [McKelvey & Palfrey, 1995]. piKL-Hedge finds policies that play close to the anchor policy while having low regret, with $\lambda$ controlling the relative optimality of these two desiderata.

§ HUMAN POLICY KL-REGULARIZED SEARCH ALSO IMPROVES CROSS-ENTROPY

Model     Dataset     (raw model)     $c_\text{puct} = 10$     $c_\text{puct} = 5$     $c_\text{puct} = 2$     $c_\text{puct} = 1$     $c_\text{puct} = 0.5$

Maia1500 (Chess)     Lichess 1500 Rating Bucket     1.476     1.469     1.465     1.470     1.504     1.598

Maia1900 (Chess)     Lichess 1900 Rating Bucket     1.440     1.429     1.422     1.418     1.443     1.529

Our Model (Go)     GoGoD     1.388     1.362     1.359     1.362     1.391     1.478

Cross-entropy predicting human moves in chess and Go using smooth KL optimization post-processing of MCTS with various $c_\text{puct}$. Largest standard error of any value is around 0.0033.

Average cross-entropy of per-unit order prediction in Diplomacy, comparing the human-imitation-learned anchor policy, regret matching, hedge, and piKL-Hedge, as a function of pseudo-Elo player rating.

Here we show that not only does policy-regularized search improve top-1 accuracy, it also improves cross entropy for a reasonable range of parameter values in both chess and Go, as well as performing well in Diplomacy.

For Chess and Go, to obtain the policy distribution with which to compute its cross entropy with the human data, unlike for top-1 accuracy or for play we cannot directly use the MCTS visit distribution because occasionally simply due to discretization MCTS may give zero visits to the actual move that a human played, resulting in an undefined (i.e. infinite) cross-entropy. Instead, we leverage the result of Grill et al., 2020 that PUCT-style MCTS with a policy prior can be seen as a discrete approximation to solving a smooth optimization:

$$ \argmax_{\pi} \sum_a Q(s,a)\pi(s,a) + \lambda \KL{\tau}{\pi} $$

$$\lambda = c_\text{puct} \frac{\sqrt{\sum_a n_a}}{(k + \sum_a n_a)}$$

where $Q$ is the current value estimate from search for each action, $\tau$ is the anchor or prior policy,  $\lambda$ controls the strength of the regularization towards that prior as a function of the number of visits, $c_\text{puct}$ is the MCTS exploration coefficient, $n_a$ is the number of times $a$ was explored and $k$ is an arbitrary constant not affecting the asymptotic results.

We perform MCTS exactly the same as normal, the only difference is that at the very end, rather than using visit counts, we compute $\pi$ optimizing the above objective using the human imitation-learned anchor policy for $\tau$ and the MCTS-estimated Q-values for $Q$ (and using the same unweighted average child value for moves that lack a Q-value estimate due to having zero visits as described in Appendix <ref>). We use this resulting smooth $\pi$ as the final policy prediction and compute its cross entropy with the actual human moves.

Note that the authors choose $k = |A|$, the number of legal actions, for mathematical convenience, corresponding to adding one extra visit per every possible action [Grill et al., 2020], but since in our experiments we use only use 50 visits including the root visit (i.e. $\sum_a n_a = 49$), and the branching factor can be as large as 362 in Go, adding one extra visit per legal action in our case greatly overestimates the total number of visits, which in practice gives a less accurate correspondence between MCTS and this smoother regularized solution, so we instead choose $k = 0$.

In Table <ref> we show the results. Across roughly the same parameter ranges, the regularized search policy using this smoothed MCTS postprocessing achieves lower cross-entropy with human moves than the raw imitation-learned policy without search. This suggests that not only does search improve on the raw imitation-learned policy at pinpointing the top action, it also gives a more accurate model of the overall distribution of likely human actions.

Similarly, in <ref>, we show that piKL-Hedge achieves better average cross entropy of unit orders in no-press Diplomacy compared to unregularized search methods, and matches that of imitation learning at $\lambda = 0.1$. This corroborates the results of Section <ref> and shows that piKL-Hedge provides the same benefits in modeling the overall distribution of human actions as it does on predicting the top move - outpredicting unregularized search (while playing as well or slightly better against human-like opponents), or equaling the prediction quality of imitation learning (while playing much more strongly than IL).

§ MORE EXPERIMENTS IN CHESS AND GO

2*Game     2*$c_\text{puct}$     2cMCTS Win% vs raw model

$\text{temp}=1$     $\text{temp}=0.3$

Chess     10.0     72.2% $\pm$ 1.2%      62.4% $\pm$ 1.3%

Chess     5.0     79.5% $\pm$ 1.1%      72.3% $\pm$ 1.2%

Chess     2.0     88.0% $\pm$ 0.8%     86.1% $\pm$ 0.9%

Chess     1.0     92.2% $\pm$ 0.7%      92.9% $\pm$ 0.6%

Chess     0.5     94.4% $\pm$ 0.6%      94.7% $\pm$ 0.5%

Go     10.0     73.2% $\pm$ 1.4%      63.3% $\pm$ 1.5%

Go     5.0     80.5% $\pm$ 1.3%     74.1% $\pm$ 1.4%

Go     2.0     87.6% $\pm$ 1.0%      85.3% $\pm$ 1.1%

Go     1.0     94.6% $\pm$ 0.7%      94.4% $\pm$ 0.7%

Go     0.5     96.4% $\pm$ 0.6%      97.0% $\pm$ 0.5%

Winrate of base model + MCTS vs base model at temperature 1 and 0.3. Base model is Maia1900 in chess, and our GoGoD model in Go. 1000 games per figure, draws count as half a win, $\pm$ indicates one standard error. Go uses Japanese rules with 6.5 komi. MCTS greatly improves strength in Chess and Go, the smallest $c_\text{puct}$ values improve it most.

Model     Predicting     Main Time     Increment     Raw Model Acc %     MCTS Acc %     Acc Gain from MCTS     Approx Stderr

Maia1500     1500	    3m	    0s	    51.9	    52.1	    0.2     0.17

Maia1500     1500	    5m	    0s	    52.7	    53.2	    0.5     0.16

Maia1500     1500	    10m	    0s	    52.4	    53.1	    0.7     0.20

Maia1500     1500	    3m	    2s	    53.1	    53.7	    0.6     0.31

Maia1500     1500	    5m	    3s	    52.5	    53.4	    0.9     0.35

Maia1500     1500	    15m	    15s	    51.9	    52.6	    0.7     0.37

Maia1900     1900	    3m	    0s	    53.0	    53.9	    0.8     0.12

Maia1900     1900	    5m	    0s	    53.2	    54.5	    1.3     0.17

Maia1900     1900	    10m	    0s	    52.9	    54.6	    1.7     0.24

Maia1900     1900	    3m	    2s	    54.1	    55.5	    1.4     0.27

Maia1900     1900	    5m	    3s	    53.1	    55.1	    2.0     0.51

Maia1900     1900	    15m	    15s	    53.7	    55.9	    2.2     0.56

Difference in top-1 accuracy between raw model and MCTS using the best $c_\text{puct}$ in predicting human moves for chess players in rating buckets 1500 and 1900 using Maia1500 and Maia1900, split by time control of the games, excluding all time controls with fewer than 100 games. Approx Stderr indicates the rough standard error of raw accuracy values on that row given the number of games of that time control. Despite the statistical uncertainty on some individual values, overall the improvement of MCTS vs the raw model does clearly tend to be larger on the games with longer time controls.

This section summarizes the results of a small number of additional experiments in chess and Go. Whereas Figure <ref> used a temperature of 1.0 when sampling from the agent policy, we show in Table <ref> that MCTS also achieves similar winrates versus the raw model when both are sampled using a much lower temperature of 0.3.

Additionally, we confirm in Go the same result that McIlroy-Young et al., 2020 reported in chess, that current top RL agents are far worse at matching human moves than even just imitation learning. We tested the current top open-source Go program KataGo [Wu, 2020] using its final 6, 10, and 15 block models[from https://katagotraining.org] which range from upper-amateur to superhuman level, and found that they achieve accuracies of about 35%, 43%, and 43%, all more than 10% lower than the results in Table <ref>.

Lastly, in Table <ref> we show that in chess the amount of improvement given by MCTS over the raw model in predicting human players on the Lichess test set tends to be larger for games with longer time controls than for shorter time controls, going from about 0.2% to about 0.7% between the shortest and longer time controls for 1500-1599-rated players, and going from about 0.8% to around 2.0% for 1900-1999-rated players. This is consistent with the intuition that humans rely more heavily on planning when they have more time to think, increasing the gain from modeling that planning.

§ BASELINE MODEL ARCHITECTURE AND TRAINING FOR GO

As summarized in Section <ref>, for training baseline imitation-learning models to play on the 19x19 board in Go, our architecture follows the same 20-block 256-channel residual net described in Silver et al., 2017, except with the addition of squeeze-and-excitation layers at the end of each residual block [Hu et al., 2018]. In particular, the following additional operations are inserted just prior to each skip connection that adds the output $R$ of a residual block to the trunk $X$:

* Channelwise global average pooling of $R$ from 19 $\times$ 19 $\times$ 256 channels to 256 channels.

* A fully connected layer including bias from 256 channels to 64 channels.

* A ReLU nonlinearity.

* A fully connected layer including bias from 64 channels to 512 channels, which are split two vectors $S$ and $B$ of 256 channels each.

* Output $R$ $\times$ sigmoid($S$) + $B$ to be added back to the trunk $X$, instead of $R$ as in a normal residual net.

In other words, the final result of the residual block as a whole is ReLU($X$ + $R$ $\times$ sigmoid($S)$ + $B$) instead of ReLU($X$ + $R$).

Additionally, some games are played with a komi (compensation given to White for playing second) that is not equal to the value of 7.5 used by Silver et al., 2017. Therefore, for the final feature of the input encoding, rather than a binary-valued feature equalling 1 if the player to move is White and 0 if the player to move is Black, we instead use the real-valued feature of komi/10 if the player to move is White or -komi/10 if the player to move is Black. We additionally exclude a very tiny number of games with extreme komi values, outside of the range [-60,60].

We train using a mini-batch size of 2048 distributed as 8 batches of 256 across 8 GPUs, and train for a total of 64 epochs - roughly 475000 minibatches for the GoGoD dataset. We use SGD with momentum 0.9, weight decay coefficient of 1e-4, and a learning rate schedule of of 1e-1, 1e-2, 1e-3, 1e-4 for the first 16, next 16, next 16, and last 16 epochs respectively.

We train both the policy and values heads jointly, minimizing the cross entropy of the policy head with respect to the one-hot move made in the actual game, and the MSE of the value head with respect to the game result of -1 or 1, except similarly to Silver et al., 2017 we weight the MSE value loss by 0.01 to avoid overfitting of the value head.

§ MCTS ALGORITHMIC DETAILS

In this appendix, we summarize the details of the version of MCTS used in our experiments, including one often-overlooked detail. We follow a standard MCTS implementation very similar to that of [Silver et al., 2017].

Each turn, the algorithm builds and expands a game tree over multiple iterations rooted at the current state for that turn. On each iteration $t$ MCTS starts at the root and descends the tree by exploring at each state $s$ an action $a$ according to some exploration method. Upon reaching a state $s_t$ not yet explored, it adds $s_t$ to the tree, queries the value function $V_i(s_t)$ for each $i$ to estimate the total expected future reward, and updates the statistics of all nodes traversed based on $V_i(s_t)$ and any intermediate rewards received. Subsequent iterations begin again from the root. For our work in chess and Go, we follow the convention where win, loss, and draw have reward 1,-1, and 0.

The statistics tracked at the node for each state $s$ where player $i$ is to move include the visit counts $N(s,a)$ which are the number of iterations that reached state $s$ and tried action $a$, and $Q(s,a)$ the average value of those iterations from the perspective of player $i$, i.e. $Q(s,a) = (1/N(s,a)) \sum_{t} V_i(s_t) + U_i(s,s_t)$ where the sum ranges only over those iterations $t$ that reached state $s$ and tried action $a$ and $U_i(s,s_t)$ is the total intermediate reward on the path from $s$ to $s_t$. When descending the tree, the exploration method is to always select the action:

\begin{equation}
\argmax_a \, Q(s,a) + c_\text{puct}\tau(s,a)\frac{\sqrt{\sum_b N(s,b)}}{N(s,a)+1}
\end{equation}

where $\tau(s,a)$ is the prior policy probability for action $a$ in state $s$, and $c_\text{puct}$ is a tunable parameter controlling the tradeoff between exploration and exploitation. The final agent policy $\pi$ is simply proportional to the visit counts for the root, i.e. $\pi(s,a) = N(s,a)/\sum_b N(s,b)$ where $s$ is the root state, or optionally we may also have $\pi(s,a) \sim N(s,a)^{1/T}$ where $T$ is a temperature parameter.

One final often-overlooked detail concerns how to evaluate states for which there is no $Q(s,a)$ estimate. Since the tree policy depends on the $Q(s,a)$ estimates of the possible actions, there is a nontrivial choice of what $Q$ value to use for an action $a$ that has been tried zero times and therefore never estimated. Since the tree branches exponentially, deeper in the MCTS tree there will always be many actions with zero visits, and so this choice can affect the behavior of MCTS even in the limit of large amounts of search. Unfortunately, the details of this choice have sometimes been left undiscussed and undocumented in major past work, and as a result major MCTS implementations have not standardized on it, variously choosing game-loss [Lai, 2018], the current running average parent $Q$ or a $Q$-value minus a heuristic offset parameter [Tian, 2019], or many other options.

In our work, we use the equal-weighted average value of all actions at the parent node that have been visited at least once, i.e. $\sum_a Q(s,a) I(N(s,a) > 0) / \sum_a I(N(s,a) > 0)$ . This can be viewed as corresponding to a naive prior that the values of actions are i.i.d draws from an unknown distribution. While not perfect, our choice is simple, parameter-free, behaves in a way that is invariant to any global translation or scaling of the game's rewards, and works reasonably in practice for our purposes.

§ BRIEF DESCRIPTION OF DIPLOMACY

We briefly summarizing the rules of Diplomacy. See Paquette et al., 2019 for a more detailed description. The board is a map of Europe partitioned into 75 regions, 34 of which are supply centers (SCs) that players compete to control. Players command multiple units and each turn privately issue orders for each unit they own (to hold, move, support another unit, or convoy). These orders are revealed at the same time, thereby making Diplomacy a simultaneous-action game. A player wins the game by controlling a majority (18) of the SCs.
A game may also end in a draw if all remaining players agree. In this case, we use the Sum-of-Squares (SoS) scoring system as used in prior works [Paquette et al., 2019, Gray et al., 2020, Bakhtin et al., 2021]. If no player wins, SoS defines the score of player $i$ as $C_i^2 /\sum_{i'}C_{i'}^2$, where $C_i$ is the SC count for player $i$.

Diplomacy is specifically designed so that a player is unlikely to achieve victory without help from other players. The full game allows unrestricted private natural-language communication between players
each turn prior to choosing orders,
but we focus on the simpler no-press variant, in which no such communication is allowed, but modeling how opponents will behave
continues to be important.

§ DIPLOMACY HYPER-PARAMETERS

We describe the describe the search parameters used in this work and compare it to those in previous works. As compared to Gray et al., 2020, we use a much less expensive set of search parameters for all results in the main section of this paper (See, <ref>). In <ref>, we show that these tuned-down set of parameters, slightly reduces piKL-HedgeBot's performance but allows us to make similar conclusions when comparing against SearchBot [Gray et al., 2020] and supervised learning-based bots from prior works. Additionally, in <ref>, we also show that when our agent (piKL-HedgeBot ($\lambda = 10^{-3}$)) uses the same search parameters as Gray et al., 2020, it outperforms SearchBot by a big margin.

In our experiments, to compare against DipNet [Paquette et al., 2019] we use the original model checkpoint[DipNet SL from <https://github.com/diplomacy/research>.
] and we sample from the policy with temperature $0.1$ (as used in prior works). Similarly, to compare against SearchBot [Gray et al., 2020] agent we use the released checkpoint[blueprint from <https://github.com/facebookresearch/diplomacy_searchbot/releases/tag/1.0>.
] and agent configuration[<https://github.com/facebookresearch/diplomacy_searchbot/blob/master/conf/common/agents/searchbot_02_fastbot.prototxt>].

The only other search parameter unique and new to our  algorithm is $\eta$ in Algorithm <ref>, which we heuristically set on each Hedge iteration $t$ to $c / (\sigma \sqrt{t})$ where $\sigma$ is the standard deviation across iterations of the average utility experienced by the agent $i$ being updated. We find $c=10/3$ works well for no-press Diplomacy.

Model     Temperature

DipNet [Paquette et al., 2019]     0.1

DipNet RL [Paquette et al., 2019]     0.1

Blueprint [Gray et al., 2020]     0.1

IL Policy (Ours)     0.5

Sampling temperatures used in the models across prior works. For our imitation learning model (IL Policy), we use a temperature of 0.5 in all experiments to encourage stochasticity.

Parameter    [Gray et al., 2020]     Ours

Number candidate actions ($N_c$)     50     30

Max candidate actions per unit     3.5     3.5

Number search iterations     256     512

Policy sampling temperature for rollouts     0.75     N/A

Policy sampling top-p     0.95     0.95

Rollout length, move phases     2     0

Search parameters used in Gray et al., 2020 compared to the search parameters used in our work. All experiments in the main body of this work uses search settings that are much cheaper to run. We use a rollout length of 0 and $N_c = 30$ while increasing the number of search iterations to 512.

1x $\downarrow$ 6x $\rightarrow$     DipNet     DipNet RL    Blueprint    BRBot     SearchBot

DipNet [Paquette et al., 2019]     -     6.7% $\pm$ 0.9%     11.6% $\pm$ 0.1%     0.1% $\pm$ 0.1%     0.7% $\pm$ 0.2%

DipNet RL [Paquette et al., 2019]     18.9% $\pm$ 1.4%     -     10.5% $\pm$ 1.1%     0.1% $\pm$ 0.1%     0.6% $\pm$ 0.2%

Blueprint [Gray et al., 2020]     20.2% $\pm$ 1.3%     7.5% $\pm$ 1.0%     -     0.3% $\pm$ 0.1%     0.9% $\pm$ 0.2%

BRBot [Gray et al., 2020]     67.3% $\pm$ 1.0%     43.7% $\pm$ 1.0%     69.3% $\pm$ 1.7%     -     11.1% $\pm$ 1.1%

SearchBot [Gray et al., 2020]     51.1% $\pm$ 1.9%     35.2% $\pm$ 1.8%     52.7% $\pm$ 1.3%     17.2% $\pm$ 1.3%     -

piKL-HedgeBot ($\lambda=0.001$)     54.8% $\pm$ 1.8%     31.4% $\pm$ 1.8%     50.3% $\pm$ 1.8%     19.2% $\pm$ 1.4%     16.6% $\pm$ 1.3%

piKL-HedgeBot ($\lambda=0.001$) ([Gray et al., 2020] parameters)     60.1% $\pm$ 1.8%     33.3% $\pm$ 1.8%     58.1% $\pm$ 1.8%     23.6% $\pm$ 1.6%     20.3% $\pm$ 1.4%

Average SoS scores achieved by the 1x agent against the 6x agents.
This table compares the performance of SearchBot [Gray et al., 2020] and other agents from prior work with piKL-HedgeBot ($\lambda = 10^{-3}$) that uses a much cheaper search setting. Using the much cheaper search setting, comes at relatively small cost in its performance as we use improved value and policy models (See, <ref> and <ref> for more details). When using the same parameters as Gray et al., 2020, piKL-HedgeBot ($\lambda = 10^{-3}$) significantly outperforms SearchBot under most settings. Note that equal performance would be 1/7 $\approx$ 14.3%. The $\pm$ shows one standard error.

§ DIPLOMACY MODEL ARCHITECTURE AND INPUT FEATURES

Our imitation learning policy model for Diplomacy uses the same transformer-encoder LSTM-decoder architecture as Bakhtin et al., 2021 for reinforcement learning in Diplomacy, but applied to imitation learning over human games. This architecture also resembles the architecture used by a significant amount of past work [Gray et al., 2020, Anthony et al., 2020, Paquette et al., 2019] but replaces the graph-convolution encoder with a transformer, which we find to produce good results.

Additionally, we slightly modify the input feature encoding relative to Gray et al., 2020, removing a small number of redundant channels and adding channels to indicate the “home centers” of each of the 7 powers (Austria, England, France,... etc), which are the locations where that power is allowed to build new armies or fleets. See Table <ref> for the new list of input features. By adding the home centers to the input encoding instead of leaving them implicit, the game becomes entirely equivariant to permutations of those powers - e.g. if one swaps all the units of England and France, and all their centers, and which centers are their home centers, the resulting game is isomorphic to the original except with the two powers renamed.

This allows us to then augment the training data via equivariant permutations of the seven possible powers in the encoding. Every time we sample a position from the dataset for training, we also choose among all 7-factorial permutations of the powers uniformly at random, and correspondingly permute both the input and output, to reduce overfit and improve the model's generalization given the limited human data available.

Feature     Type     Number of Channels

Location has unit?     One-hot (army/fleet), or all zero     2

Owner of unit     One-hot (7 powers), or all zero     7

Buildable, Removable?     Binary     2

Location has dislodged unit?     One-hot (army/fleet), or all zero     2

Owner of dislodged unit     One-hot (7 powers), or all zero     7

Area type     One-hot (land,coast,water)     3

Supply center owner     One-hot (7 powers or neutral), or all zero     8

Home center     One-hot (7 powers), or all zero     7

Per-location input features used

§ IMPROVED VALUE MODEL IN DIPLOMACY

For no-press Diplomacy, we note that Gray et al., 2020 observed that their search agent benefits from short rollouts using the trained human policy before applying the human-learned value model to evaluate the position. Doing so appears to result in more accurate evaluations reflecting the likely outcomes from a given game state, which the raw value model may failed to learn sufficiently accurately on the limited human dataset. Since expectation of the learned value model after a short rollout appears to be better than the learned value model itself, this motivates training a model to directly approximate the former.

In a fashion broadly similar to Silver et al., 2016 generating rollout games to train a more accurate value head for Go, we therefore generated a large stream of data by uniformly sampling positions from the human game dataset for Diplomacy, rolling them forward between 4-8 phases of game play via the same rollout settings as Gray et al., 2020, i.e. policy sampling temperature 0.75, top-p 0.95, and training a new value model to predict the resulting post-rollout value estimate of the old value model. Samples were continuously and asynchronously added to a replay buffer of 10000 batches, and the buffer was continuously sampled to train the same transformer-based architecture as the human-trained model from Appendix <ref> initialized with the weights of that model. Training was constrained to never exceed the rate of data generation by more than a factor of 2 (i.e. using each sample twice in expectation) and proceeded for 128000 mini-batches of 1024 samples each using the ADAM optimizer with a fixed learning rate of 1e-5.

§ MORE EXPERIMENTS IN DIPLOMACY

This section compiles additional performance results from evaluation games.

§.§ Head-to-Head Performance

In Table <ref>, we compare the performance of in 1v6 head-to-head games against the underlying imitation anchor policy, following prior work [Gray et al., 2020, Bakhtin et al., 2021, Paquette et al., 2019, Anthony et al., 2020]. We find that the $\lambda=10^{-1}$ policy is substantially stronger than the imitation policy while matching the accuracy in predicting human moves, while the $\lambda=10^{-3}$ policy outperforms unregularized search methods while playing much closer to the human policy.

1x     6x     Average SoS Score

7*     piKL-HedgeBot ($\lambda=10^{-1}$)                8.3$\pm$0.9%

piKL-HedgeBot ($\lambda=10^{-2}$)           2.5$\pm$0.4%

piKL-HedgeBot ($\lambda=10^{-3}$)           1.8$\pm$0.3%

piKL-HedgeBot ($\lambda=10^{-4}$)           2.1$\pm$0.3%

piKL-HedgeBot ($\lambda=10^{-5}$)           1.6$\pm$0.2%

HedgeBot           1.5$\pm$0.2%

1x     6x     Average SoS Score

piKL-HedgeBot ($\lambda=10^{-1}$)          7*      21.1$\pm$1.4%

piKL-HedgeBot ($\lambda=10^{-2}$)               44.2$\pm$1.7%

piKL-HedgeBot ($\lambda=10^{-3}$)              52.7$\pm$1.7%

piKL-HedgeBot ($\lambda=10^{-4}$)               49.7$\pm$1.7%

piKL-HedgeBot ($\lambda=10^{-5}$)              46.9$\pm$1.7%

HedgeBot                             46.5$\pm$1.7%

Average SoS score attained by the 1x agent against the 6x agent. ($\lambda=10^{-1}$) policy is substantially stronger than IL Policy, while the ($\lambda=10^{-2}$) policy is almost as strong as . The $\pm$ shows one standard error. Note that equal performance would be 1/7 $\approx$ 14.3%.

§.§ piKL-HedgeBot's performance in population-based experiments

In this section, we provide all the results from the population experiments across various piKL-HedgeBot's lambda values. <ref> and <ref> show the results. piKL-HedgeBot with $\lambda=10^{-3}$ performs best across individual population experiments with an SoS score of 32.9%. The performance drops as we continue to increase $\lambda$ past $1e-3$. Error bars indicate 1 standard error.

Average SoS score achieved by piKL-HedgeBots in uniformly sampled pools of other agents as a function of $\lambda$. piKL-HedgeBot ($\lambda = 10^{-3}$) performs best across individual sweeps with an SoS score of 32.9%.

Agent     Average SoS Score

DipNet [Paquette et al., 2019]        4.9% $\pm$ 0.3%

DipNet RL [Paquette et al., 2019]       5.6% $\pm$ 0.4%

Blueprint  [Gray et al., 2020]       7.1% $\pm$ 0.4%

BRBot [Gray et al., 2020]           18.2% $\pm$ 0.6%

SearchBot [Gray et al., 2020]      36.1% $\pm$ 0.8%

10.2% $\pm$ 0.6%

36.8% $\pm$ 1.1%

piKL-HedgeBot ($\lambda=10^{-1}$)               15.6% $\pm$ 0.6%

Agent     Average SoS Score

DipNet [Paquette et al., 2019]        3.8% $\pm$ 0.3%

DipNet RL [Paquette et al., 2019]       4.2% $\pm$ 0.3%

Blueprint  [Gray et al., 2020]       5.8% $\pm$ 0.4%

BRBot [Gray et al., 2020]           16.3% $\pm$ 0.6%

SearchBot [Gray et al., 2020]      14.1% $\pm$ 0.6%

8.5% $\pm$ 0.4%

31.7% $\pm$ 0.8%

piKL-HedgeBot ($\lambda=10^{-2}$)               29.9% $\pm$ 0.7%

Agent     Average SoS Score

DipNet [Paquette et al., 2019]        3.7% $\pm$ 0.3%

DipNet RL [Paquette et al., 2019]       4.7% $\pm$ 0.3%

Blueprint  [Gray et al., 2020]       4.9% $\pm$ 0.3%

BRBot [Gray et al., 2020]           16.1% $\pm$ 0.6%

SearchBot [Gray et al., 2020]      13.4% $\pm$ 0.5%

7.9% $\pm$ 0.4%

31.3% $\pm$ 0.7%

piKL-HedgeBot ($\lambda=10^{-3}$)               32.9% $\pm$ 0.7%

Agent     Average SoS Score

DipNet [Paquette et al., 2019]        3.5% $\pm$ 0.3%

DipNet RL [Paquette et al., 2019]       4.6% $\pm$ 0.3%

Blueprint  [Gray et al., 2020]       5.7% $\pm$ 0.3%

BRBot [Gray et al., 2020]           14.3% $\pm$ 0.6%

SearchBot [Gray et al., 2020]      13.6% $\pm$ 0.5%

8.8% $\pm$ 0.4%

31.8% $\pm$ 0.7%

piKL-HedgeBot ($\lambda=10^{-4}$)              31.8% $\pm$ 0.7%

Agent     Average SoS Score

DipNet [Paquette et al., 2019]        3.6% $\pm$ 0.3%

DipNet RL [Paquette et al., 2019]       4.4% $\pm$ 0.3%

Blueprint  [Gray et al., 2020]       5.3% $\pm$ 0.3%

BRBot [Gray et al., 2020]           15.0% $\pm$ 0.6%

SearchBot [Gray et al., 2020]      13.0% $\pm$ 0.5%

8.9% $\pm$ 0.4%

32.2% $\pm$ 0.7%

piKL-HedgeBot ($\lambda=10^{-5}$)               31.9% $\pm$ 0.7%

Agent     Average SoS Score

DipNet [Paquette et al., 2019]        3.6% $\pm$ 0.3%

DipNet RL [Paquette et al., 2019]       3.9% $\pm$ 0.3%

Blueprint  [Gray et al., 2020]       5.5% $\pm$ 0.3%

BRBot [Gray et al., 2020]           14.7% $\pm$ 0.6%

SearchBot [Gray et al., 2020]      14.1% $\pm$ 0.6%

8.7% $\pm$ 0.4%

32.2% $\pm$ 0.7%

HedgeBot              31.7% $\pm$ 0.7%

Average SoS score achieved by agents in uniformly sampled pools of other agents. piKL-HedgeBot with $\lambda=10^{-3}$ performs best across individual sweeps with an SoS score of 32.9%. The $\pm$ shows one standard error.

§ DEC-POMDP GAMES: POLICY-REGULARIZED SPARTA ON HANABI

In this section, we extend KL-regularized search to decentralized partially observable Markov decision processes (Dec-POMDP) and test it on the Hanabi benchmark [Bard et al., 2020]. We first train an imitation learning policy (IL policy) from human data. We then use the IL policy as the blueprint policy in SPARTA [Lerer et al., 2020], a search technique for Dec-POMDPs, and apply KL-regularization toward the IL policy in SPARTA. We call this new algorithm piKL-SPARTA. We show that piKL-SPARTA matches or even slightly improves the original IL policy in human move prediction accuracy while greatly improving self-play performance.

§.§ Background

A Dec-POMDP is an $N$-player fully cooperative game with state space $S$ that is partially observed by each player $i$ through their individual observation function $o_i = \Omega_i(s)$ for $s \in S$, with joint action space $A = A_1 \times A_2 \times \cdots \times A_N$ and transition function $\mathcal{T} \colon S \times A \to P(S)$ that returns the distribution of next state given current state and joint action.
The reward function $R \colon S \times A \to \mathbb{R}$ assigns a scalar reward for the entire team at each time step.
A trajectory is denoted as $\tau^t = (s^0, \textbf{a}^0, r^0, \ldots, s^t)$ while the action-observation history (AOH) of each player is defined as $\tau^t_i = (o^0, \textbf{a}^0, r^0, \ldots, o^t)$. A full trajectory or full AOH that reaches the terminal state may be denoted more simply as $\tau$ or $\tau_i$ respectively. The policy for each individual player $\pi_i(a_i^t | \tau^t_i)$ takes as input the AOH and returns a distribution over valid actions. The joint policy $\pi = (\pi_1, \ldots, \pi_N)$ is a tuple containing all players' policies. The goal is to find a policy to maximize the expected total return $\pi^{*} = \argmax_{\pi} J(\pi) =  \mathbb{E}_{\tau \sim P(\tau | \pi)} R^0(\tau)$ where $R^t(\tau) = \sum_{t' \geq t} \gamma^{(t' - t)} r_t'$ is the forward looking return with optional discount factor $\gamma \leq 1$.

Hanabi is a well-established large-scale Dec-POMDP benchmark [Bard et al., 2020]. It is a 2 to 5 player card game with a deck of 50 cards equally divided into 5 color suits. Each color consists of five ranks with three 1s, two 2s, two 3s, two 4s, and one 5. Each player draws five cards from a randomly shuffled deck to start the game. The goal of the team is to play cards in order of increasing rank from 1 to 5 for every color suit. Players take turns to either play a card, discard a card, or give a hint to another player about their cards. When giving a hint, the acting player picks a receiver of the hint and a rank or color of any card in the receiver's hand. The recipient will then learn exactly which cards in their hand match the given rank or color. Hinting costs one information token. The team starts with eight information tokens and they can recoup one information token after discarding a card or successfully playing a 5 of any color. If a player makes an invalid play, e.g. playing a red 3 when a red 2 is not played yet, the team loses one life token. After each play or a discard, a player draws a new card if possible. The game ends when three life tokens are lost, in which case the team receives 0 points, or one round after the entire deck is exhausted, in which case the score equals the number of cards successfully played.

The majority of existing works in the Hanabi domain focus on learning human compatible policies without using human data [Bard et al., 2020, Siu et al., 2021, Hu et al., 2021]. Fewer works have explored better modeling human policies using human game data, partly due to the lack of publicly available datasets. To the best of our knowledge, the strongest supervised learning agent trained from human data was done by [Hu et al., 2021] where the authors use it as an unseen test-time partner agent in evaluation to estimate how well their agents might collaborate with humans. No prior work has been done to better predict human moves in Hanabi.

A few search techniques such as SPARTA [Lerer et al., 2020] and RL-search [Fickinger et al., 2021] have been proposed for large scale Dec-POMDPs and have specifically been applied in Hanabi. In this work we choose SPARTA as our backbone for simplicity, while noting that our KL-regularization methods may also be generalized to other search techniques. SPARTA is a test-time policy improvement algorithm that can be applied on top of any policy. SPARTA assumes that a blueprint policy (BP) $\pi$ is common knowledge in the Dec-POMDP and all players play their part of the blueprint unless they should deviate according to the SPARTA rule. Here we briefly discuss the single-agent variant where the search agent assumes that other agents will always play the blueprint. Given blueprint $\pi$, SPARTA first defines a belief function that tracks the distribution of the real trajectory given the search agent's own AOH $\mathcal{B}_i(\tau^t) = P(\tau^t | \tau_i^t, \pi)$. Then the search agent $i$ computes the expected value for each action $a$ using Monte Carlo rollouts:

\begin{align}
Q_{\pi}(\tau_i^t, a) &= \mathbb{E}_{\tau^t \sim \mathcal{B}_i(\tau^t)} Q_{\pi}(\tau^t, a), \label{eq:sparta-q}
\end{align}

\begin{align*}
Q_{\pi}(\tau^t, a) &= \mathbb{E}_{\tau \sim P(\tau |\mathcal{T}, \tau^t, a_i^t = a, a^t_{j\neq i} \sim \pi, \textbf{a}^{t' > t} \sim \pi)} R^t(\tau)
\end{align*}

is the expected forward looking return on $\tau^t$ assuming that the search agent will perform the action $a$ for the current step and follow the blueprint afterwards while other agents always follow the blueprint. SPARTA computes the belief $\mathcal{B}_i(\tau_t)$ analytically. It maintains a distribution of all possible trajectories and adjusts it at every step by removing the trajectories that contradict public knowledge or would have led to different joint actions according to the known joint policy $\pi$.

§.§ Method

We start with an imitation learning policy (IL policy) trained from human gameplay data collected from an online Hanabi game platform. The IL policy is used as both the baseline for predicting human moves as well as the blueprint policy for our piKL-SPARTA.
The analytical belief update procedure in SPARTA requires full knowledge of the partners' policy. This is challenging when predicting human moves and playing with humans because our IL policy models the average behavior of the entire population of players in the training dataset and a player at test time may perform actions that the IL policy will never do, leading to a null belief space that will terminate the search. Therefore, we follow the practice in [Hu et al., 2021] and train an approximate neural network belief model on self-play data generated by the IL policy.

Given the IL policy $\pi$ as blueprint and the approximate belief model $\hat{\mathcal{B}}_i$ that replaces the $\mathcal{B}_i$ in Eq. <ref>, piKL-SPARTA selects actions for the search player $i$ following

\begin{align}
P(a) \propto \pi(a | \tau_i^t) \cdot \exp \left[\frac{Q_{\pi}(\tau_i^t, a)}{\lambda}\right].
\label{eq:pikl-sparta}
\end{align}

§.§ Experimental Setup