{'fraction_non_alphanumeric': 0.031132528193233623, 'fraction_numerical': 0.007218267615772215, 'mean_word_length': 4.808036232725583, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
BRExIt: On Opponent Modelling in Expert Iteration

Finding a best response policy is a central objective in game theory and multi-agent learning, with modern population-based training approaches employing reinforcement learning algorithms as best-response oracles to improve play against candidate opponents (typically previously learnt policies). We propose Best Response Expert Iteration (BRExIt), which accelerates learning in games by incorporating opponent models into the state-of-the-art learning algorithm Expert Iteration (ExIt). BRExIt aims to (1) improve feature shaping in the apprentice, with a policy head predicting opponent policies as an auxiliary task, and (2) bias opponent moves in planning towards the given or learnt opponent model, to generate apprentice targets that better approximate a best response. In an empirical ablation on BRExIt's algorithmic variants in the game Connect4 against a set of fixed test agents, we provide statistical evidence that BRExIt learns well-performing policies with greater sample efficiency than ExIt.

I. INTRODUCTION Reinforcement learning has been successfully applied in increasingly challenging settings, with multi-agent reinforcement learning being one of the frontiers that pose open problems [1], [2], [3]. Finding strong policies for multi-agent interactions (games) requires techniques to selectively explore the space of best response policies, and techniques to learn such best response policies from gameplay. We here contribute a method that reduces the required number of episodes for learning approximate best responses in games.
State-of-the-art training schemes such as population based training with centralized control [4], [5] employ a combination of outer-loop training schemes and inner-loop learning agents in a nested loop fashion [6]. In the outer loop, a combination of fixed policies is chosen via game theoretical analysis to act as static opponents. Within the inner loop, a reinforcement learning (RL) agent repeatedly plays against these static opponents, in order to find an approximate best response policy against them. In theory, any arbitrary RL algorithm could be used as such a policy improvement operator/best response oracle in the inner loop. The best response policy found is then added to the training scheme's population, and the outer loop continues, constructing a population of increasingly stronger policies over time. This technique has been successfully applied in highly complex environments such as Dota 2 [7] and Starcraft II [8], where PPO [9] and IMPALA [10] respectively served as policy improvement operators. The large number of training episodes required by modern RL algorithms as policy improvement operators makes the inner loop of such training schemes the computational bottleneck.
In this paper we accelerate approximating best responses by introducing Best Response Expert Iteration (BRExIt). We extend Expert Iteration (ExIt) [11], famously used in Al-phaGo [12], by introducing opponent models in both (1) the apprentice (a deep neural network), with the aim of feature shaping and learning a surrogate model, and (2) the expert (Monte Carlo Tree Search), to bias learning targets towards approximate best responses. BRExIt thus better exploits opponent models that are available in centralized training approaches, or in Bayesian settings where a given set of opponents is assumed [13]. For the case of given opponent models that are computationally too demanding for search, but which can be used to generate training games, we also test a variant of BRExIt that uses learned surrogate opponent models instead. In the game of Connect4, we find that BRExIt learns to achieve target win-rates with statistically significantly fewer episodes compared to ExIt, alleviating the computational bottleneck in training towards a best response.

II. RELATED WORK
BRExIt stands at the confluence of two streams of literature, building on recent efforts of incorporating opponent models within deep reinforcement learning (Section II-A), and on the corpus of work that brings improvements to the sample efficiency of the ExIt framework (Section II-B).

A. Opponent modelling in DRL
Policy reconstruction methods predict agent policies from environment observations [2], which has been shown to be beneficial in collaborative [14], competitive [3] and mixed settings [15]. Deep Reinforcement Opponent Modelling (DRON) was one of the first works combining deep RL (DRL) with opponent modelling [16]. The authors used two networks, one that learns Q-values using Deep Q-Network (DQN) [17], and another that learns an opponent's policy by observing hand-crafted opponent features, such as the frequency of environment specific events. Their key innovation is to combine the output of both networks to compute a Q-function that is conditioned on (a latent encoding of) the approximated opponent's policy. This accounts for a given agent's Q-value dependency on the other agents' policies. Based on this, Deep Policy Inference Q-Network (DPIQN) [15] brings two further innovations: (1) merging both modules into a single neural network, and (2) baking the aforementioned Q function conditioning into the neural network architecture by reusing parameters from the OM module in the Q function. This approach was then extended to on-policy algorithms [18]. We incorporate this approach into the off-policy ExIt framework.

B. Expert Iteration and improvements
Expert Iteration (ExIt) both searches for and generalises policies in games [11]. More specifically, ExIt combines planning and learning during training, with the goal of finding a parameterized policy π θ (where θ ∈ R n ) that maximizes a given reward signal. The resulting trained policy can either be used within a planning algorithm, or alternatively act as a standalone module during deployment, without needing environment models.
ExIt's two main components are (1) the expert, traditionally an MCTS procedure [19], and (2) the apprentice, a parameterized policy π θ , usually a neural network. In short, the expert takes actions in an environment using MCTS, generating a dataset of good quality moves. The apprentice updates its parameters θ to better predict both the expert's actions and future rewards. The expert in turn uses the apprentice inside MCTS to bias its search. Updates to the apprentice yield higher quality expert searches, yielding new and better targets for the apprentice to learn. This iterative improvement constitutes the main ExIt training loop, captured in the top of Figure 1.
Significant effort has been aimed at improving ExIt, e.g. exploring alternate value targets [20], or incorporating prioritized experience replay [21] or informed exploratory measures into ExIt [22]. Other work explored Go-specific auxiliary tasks of predicting (1) ownership of each board position and (2) final game score, leading to improvements [23]. Prior to our work, the use of opponent modelling within ExIt's search has not yet been studied, albeit using opponent models inside of MCTS has already proven beneficial, even if merely partially correct [24]. In this work, opponent models masked the opponents' actions, increasing the depth of the search. While this yields actions specifically targeted to respond to the modelled policies, it makes such actions brittle responses in the face of changes by the modelled policies. In contrast, we propose using opponent models as priors in BRExIt, such that planning also improves upon the opponent policy, as this induces learning targets that are robust to local improvements of the opponent policy. 1

III. BACKGROUND
Following basic multi-agent reinforcement learning and game theoretic constructs presented in Section III-A, we detail both the opponent modelling approach followed by BRExIt in Section III-B as well as the inner workings of ExIt in Section III-C.

A. Multiagent Reinforcement Learning
Let E represent a fully observable stochastic game with n agents, state space S, shared action space A and shared policy space Π. Policies are stochastic mappings from states to actions, with π i : S × A → [0, 1] denoting the ith agent's policy, and π = [π 1 , . . . , π n ] the joint policy vector, which can be regarded as a distribution over the joint action space. T : S × A × S → [0, 1] is the transition model, or environment dynamics, determining how an environment state s changes to a new state s given a joint action a. R i : S × A × S → R is agent i's reward function. G i t ∈ R is the return from time t for agent i, the accumulated reward obtained by agent i from time t until episode termination; γ ∈ (0, 1] is the environment's discount factor. When considering the viewpoint of a specific agent i, we decompose a joint action vector a = (a i , a −i ) and joint policy vector π = (π i , π −i ) into the individual action or policy for agent i, and the other agents denoted by −i.
The state-value function V π i : S → R denotes agent i's expected cumulative reward from state s onwards assuming all agents act as prescribed by π.
Agent i's optimal policy depends on the other policies: Assuming π −i to be stationary, agent i's optimal policy π * i is also called a best response π * i ∈ BR(π −i ), where BR(π −i ) denotes the set of all best responses against π −i . Our goal is to train a system to (1) predict and encode what is knowable about the opponents' policies π −i and (2) compute a best response to that.

B. Opponent modelling in DRL
We follow the opponent modelling approach popularized by DPIQN [15], which uses a neural network to both learn opponent models and an optimal Q-function. The latter is learnt by minimising the loss function L Q of DQN [17]. Opponent modelling is an auxiliary task, trained by minimising the cross-entropy between one-hot encoded observed action for each agent j, a j , and their corresponding predicted opponent policies at state s,π j (·|s), defined as the policy inference loss L P I in Equation 2. These two losses are combined into L DP IQN with an adaptive weight to improve learning stability.
a j log(π j (·|s)) (2a) BRExIt makes use of both the policy inference loss for its OMs and the adaptive learning weight to regularize its critic loss. However, instead of learning a Q-function as a critic, BRExIt learns a state-value function V , as suggested by previous work [18].

C. Expert Iteration
We use an open-loop MCTS implementation [25] as the expert; tree nodes represent environment states s, and edges (s, a) represent taking action a at state s. Each edge stores a set of statistics: {N (s, a), Q(s, a), P (s, a), i, A n } N (s, a) is the number of visits to edge (s, a). Q(s, a) is the mean action-value for (s, a), aggregated from all simulations that have traversed (s, a). P (s, a) is the prior probability of following edge (s, a). ExIt uses the apprentice policy to compute priors, P (s, a) = π θ (a|s). One of our contributions is adding opponent-awareness to the computation of these priors. Finally, index i denotes the player to act in the node and A n indicates the available actions. For every state s encountered by an ExIt agent during a training episode, the expert takes an action a computed by running MCTS rooted at state s and selecting the action corresponding to the root node's most visited edge (s, a). During search, the tree is traversed using the same selection strategy as AlphaZero [25]. Edges (s, a) are traversed following the most promising action according to the PUCT formula: where C P U CT is a tunable constant. The apprentice π θ is a distillation of previous MCTS searches, and provides P (s, a), thus biasing MCTS towards actions that were previously computed to be promising. Upon reaching a leaf node with state s , we backpropagate a value given by a learnt state value function V φ (s ) with parameters φ ∈ R n trained to regress against observed returns. After completing search from a root node representing state s, the policy π M CT S (·|s) can be extracted from the statistics stored on the root node's edges. This policy is stored as a training target for the apprentice's policy head to imitate: As shown in the top right corner of Figure 1 ExIt builds a dataset containing a datapoint for each timestep t: The top left corner of Figure 1 shows an actor-critic architecture, used as apprentice, with a policy head π θ , and a value head V φ . A cross-entropy loss is used to train the actor towards imitating the expert's moves, and a mean-square error loss is used to update the critic's state value function towards observed returns G i t .

IV. BREXIT: OPPONENT MODELLING IN EXIT
We present Best Response Expert Iteration (BRExIt), an extension on ExIt that uses opponent modelling for two purposes. First, to allow the MCTS expert to approximate a best response against a set of opponents: π M CT S ∈ BR(π −i ), see Subsection IV-C. Second, to enhance the apprentice's architecture with opponent modelling heads, acting as feature shaping mechanisms to improve its actor-critic architecture. See subsection IV-A.

A. Learning opponent models in sequential games
Previous approaches to learn opponent models used observed actions as learning targets, coming from a game theoretical tradition where individual actions can be observed but not the policy that generated them [26]. However, the centralized population-based training schemes which motivate our research already require access during training to all policies in the environment, both for the training agent and the opponents policies. Thus, we further exploit this assumption by allowing the use of full distributions over actions, computed by the opponents during play, as learning targets instead of one-hot encoded observed actions in the policy inference loss from Equation 2.
In prior work these approaches have only been applied to fully observable simultaneous games, where a shared environment state is used by all agents to compute an action at every timestep. Thus, if agent i wanted to learn models of its opponents' policies, storing (a) each of i's observed shared states and (b) opponent actions, was sufficient to learn opponent models. We extend this to sequential games, where agents take turns acting based on individual states. For sequential games, BRExIt augments the dataset collected by ExIt, specified in Equation 6, by adding (1) The state which each opponent agent j = i observed and (2) the ground truth action distributions given by the opponent policies in their corresponding turn. The data collection process for sequential environments is described in Algorithm 1. Formally, assuming n o opponents, at every timestep t where BRExIt acts, it builds a dataset, where π n , s t+n correspond to the nth opponent policy and its observed state.

B. Apprentice Representation
BRExIt's three headed apprentice neural network architecture extends ExIt's actor-critic representation with opponent models as per DPIQN's design [18], depicted on the bottom left of Figure 1 for a single opponent. As explained in Section III-B, this architecture reuses parameters from the opponent model to act as feature shaping mechanisms for both the actor and the critic. This neural net takes as input environment states s t ∈ S for a timestep t, which can correspond to the observed state of any agent. It features three outputs (1) The apprentice's actor policy π θ (s t ) (2) The state-value critic V π θ ,π Ψ φ (s t ) (3) The opponent modelŝ π ψj (s t ) ∈π Ψ , where Ψ contains the parameters for all opponent model and ψ j ⊂ Ψ the parameters for opponent model head j.
On certain sequential games the distribution of states encountered by each agent might differ, and so the actor-critic head and each of the opponent model heads might each be trained on different state distributions. In practice this means BRExIt bases the decision on how to compute edge priors based on whose turn a node corresponds to. For opponent nodes, during training, these action priors can come from the true opponent's policy or from the apprentice's opponent model headsπ. BRExIt adds an opponent modelling loss by also gathering the states observed by the opponent st+1 and either the output of their policy π1(·|st+1), or one-hot encoded actions.
that the output of one of these heads might only be usable if the input state s t for a timestep t comes from the distribution it was trained on. This is not the case in simultaneous games, where the encountered states are shared among all agents.
With an understanding of the internal workings of the apprentice's architecture and how to interpret it's outputs, we discuss its usage within the expert's MCTS to bias its search around the vicinity of a best response against given or modelled opponents.

C. Opponent modelling inside MCTS
BRExIt follows Equation 8 to compute the action priors P (s, a) from Equation 4 for a node with player index j, notably using opponent models in nodes within the search tree that correspond to opponents' turns. This process is exemplified in the lower middle half of Figure 1. Such opponent models can be either the ground truth opponent policies, the real opponent policies π −i , by exploiting centralized training scheme assumptions, or otherwise the apprentice's learnt opponent modelsπ ψ . This is a key difference from ExIt, which always uses the apprentice's policy π θ to compute P (s, a).
If using ground truth modelŝ π ψ j (a|s) If using learnt opponent models (8) By using either the ground truth or learnt opponent models, we initially bias the search towards a best response against the actual policies in the environment. In contrast, if the apprentice policy π θ is used to compute P (s, a) at every node in the tree, we would bias the search to compute a best response against π θ . That is, MCTS assumes that all agents follow the same policy as the apprentice, whereas in reality agents might follow any arbitrary policy. However, note that initial P (s, a) values will be overridden by the aggregated simulation returns Q(s, a), as with infinite compute MCTS converges to best response against a perfectly rational player, whose actions may deviate from the underlying opponent's policy. Thus, BRExIt's search maintains MCTS's asymptotic behaviour while simultaneously priming the construction of the tree towards areas which are likely to be explored by the policies in the environment.
Algorithms 1, 2 and 3 depict BRExIt's data collection, model update logic and overarching training loop respectively for a sequential environment. Coloured lines represent our contributions w.r.t ExIt. Figure 1 visually compares BRExIt and ExIt.

Algorithm 1: BRExIt data collection
Sample opp. action: a t+j ∼ π j −i (s t+j ); 10 Act in the game s t+j , _ ∼ P(s t+j , a t+j ) Algorithm 2: BRExIt model update Sample n datapoints from D: CE policy inference loss: Weighted final loss L total = λ(L v + L π ) + L P I ; 8 Backpropagate ∇L total through θ, ψ, φ ; 9 end D. The evolution of AlphaGo's training scheme ExIt was popularized over three publications which presented increasingly stronger playing agents: AlphaGo [12], AlphaGo Zero [27] and Alpha Zero [28]. Every publication kept ExIt's internal workings mostly unchanged except for different hyperparameter choices and the progressive removal of environment specific algorithmic enhancements. Yet, every publication featured meaningful changes to the higher level training scheme that governed ExIt's training, which we discuss here along with their implications for training ExIt or BRExIt agents.
The initial AlphaGo used δ = 0 self-play, where a menagerie was kept with previous versions of the policy network, opponents were randomly sampled at the beginning of each episode from the menagerie, and every 500 generations (model update steps) a fixed checkpoint of the current apprentice's policy network was stored in the menagerie. The authors claimed that this opponent randomization kept the apprentice from overfitting to its own policy. Recall that the underlying ExIt agent biases its expert search towards a best response against the apprentice's own policy, by using the apprentice π θ to compute action priors on every node in the search tree. This means that the expert generated policies targets will not try to exploit the opponents it trained against, choosing instead more conservative searches which regress against a response to a Nash equilibrium. Recent studies show that this conservativeness can be detrimental in terms of finding diverse sets of policies throughout training for populationbased training schemes [29], [5]. Instead, they advocate for a more aggressive computation of best responses against known opponents. Through this practice, a wider area of the policy space is explored by the training agents, allowing the higher level training scheme to better decide on which opponents to use as targets to guide future exploration. We argue that BRExIt has this exploitative property built-in, by actively biasing its search towards a best response against ground truth opponent policies. Future work could focus on empirically verifying this claim.
AlphaGo Zero and AlphaZero differ in similar ways. The former opts for a restricted version of naive self-play in which the learning ExIt agent plays against an identical copy of itself, but if after some amount of training episodes it fails to beat it's previous checkpoint by a set winrate margin its network parameters are rolled back to that of the checkpoint's, enforcing monotonic improvement on saved checkpoints. Finally, Alpha Zero dropped this last constraint, and simply used naive selfplay, as they claimed improved performance. We note that under the setting of naive self-play, BRExIt using ground truth opponent models and ExIt are equivalent, ignoring the feature shaping effects that opponent models have on the apprentice network. This is because in naive self-play, the opponent acts using the same apprentice policy network as the learning agent. Hence, by having the ground truth opponent models being the same as the apprentice policy network, we have π j −i =π ψj , meaning that the computation of P (s, a) will be identical for BRExIt and ExIt. Thus, in this case the learning agent is approximating a best response against its opponents, even in the case of ExIt. We hypothesise that this might be one of the reasons why naive self-play performs better than δ = 0 uniform for the training of ExIt agents.

V. EXPERIMENTS & DISCUSSION
We test the following two hypotheses: Primarily, whether BRExIt is more sample efficient than ExIt at distilling into its apprentice π θ a policy that achieves a target win-rate against fixed opponents. Secondarily, whether using a full distribution as a target for OM learning is more beneficial than one-hot action encodings.
a) The environment:: We conduct experiments in the fully observable, sequential two-player game of Connect4, which is computational amenable and possesses a high degree of skill transitivity [30].
b) Test opponents:: We generated three monotonically stronger agents π weak , π medium , π strong , by freezing copies of a PPO [9] agent trained under δ = 0-Uniform self-play [6] after 200k, 400k and 600k episodes. Motivated by populationbased training schemes, we evaluate an additional opponent policy π mixed , representing a mixture over all previous agents, which uniformly samples one of the three policies to follow at the start of each episode, with details given in Appendix A.

A. Trained agents
We train 7 types of agents, performing an additive construction from ExIt to BRExIt. ExIt defines the original algorithm, ExIt-OMFS denotes ExIt using OMs only for feature shaping. BRExIt-OMS additionally uses learnt OMs during search and BRExIt uses the ground truth OMs during search. Their OMs use full distributions as training targets. For the last three algorithms we also train separate versions using one-hot encoded actions as targets. Each algorithm was independently trained 10 times against the 4 test opponents, yielding a total of 280 training runs. All algorithms use 50 MCTS iterations per search due to computational constraints, with policy updates every 800 games. See Appendix D for a full set of hyperparameters.
Following state-of-the-art statistical practices [31] we use Inter Quartile Metrics (IQM) for all results (graphs and statistics), discarding the worst and best performing 25% runs to obtain performance metrics less susceptible to outliers. Figure 2 shows the number of episodes required by ExIt and algorithms that used full distribution OM targets to train their apprentices to reach a 50% winrate against each test opponent. Figure 3 shows the episodes required by all algorithms using OMs, contrasting the performance between one-hot encoded targets and full distribution targets. Figure 4 shows the probability of improvement (PoI) that one ablation has over another [31] based on results from Figure 2, defined as the probability that algorithm x takes less time to converge to a 50% winrate than algorithm y for an arbitrary training run against an arbitrary test opponent.

B. Results
1) On BRExIt's sample efficiency: Figure 2 shows that BRExIt consistently requires the least samples to reach the target winrate. BRExIt regularly outperforms BRExIt-OMS (80% PoI), successfully exploiting the centralized assumption (an opponent policy available during search) for extra performance. If opponent policies can only be sampled for training games but not during search, using learnt OMs during search is still beneficial, as we see that BRExIt-OMS consistently outperforms ExIt (79 % PoI). While BRExIt-OMS does not show a statistical difference compared to ExIt against π mixed with the results from Figure 2, we ran 10 additional training runs, after which the difference appears significant p = 0.03. Surprisingly, ExIt-OMFS performs worse than ExIt by a significant margin (the latter has a 80% PoI against the former), providing empirical evidence that OM with static opponents is detrimental for ExIt if OMs are not exploited within MCTS. This goes against previous results [23], which explored OM within ExIt merely as a feature shaping mechanism and claimed modest improvements when predicting the opponent's policy on the next state. Differences may be attributed to the fact that we instead model the opponent policy on the current state.
We observe that BRExIt updates feature both larger winrate increases and are on average less likely to result in destructive model updates. With BRExIt and the less constraining BRExIt-OMS featuring a > 93% and > 79% PoI respectively against vanilla ExIt, our empirical results warrant the use of our novel algorithmic variants instead of ExIt whenever opponent policies are available for training.
2) Full distribution VS one-hot targets: We observe no statistical difference between agents trained with algorithms using one-hot encoded OM targets when compared to using full action distributions. To assess this, we independently compare each pair containing an algorithm from Figure 3 and its respective one-hot target counterpart by running a twosample Kolmogorov-Smirnov test. The samples to compare are the sets of elapsed episodes (one datapoint per training run) required to reach the experiment's target winrate. We obtain p 0.05 for each algorithmic combination, so we cannot reject the null hypotheses that both data samples come from the same distribution; the only exception being ExIt-OMFS, which shows a statistically significant decrease in performance when using one-hot encoded targets, as detailed in Appendix C.
This runs against the intuition that richer targets for OMs will in turn improve the quality of the apprentice. However, we observed that full distributional targets do yield OMs with better prediction capabilities, as indicated by lower loss of the OM during training. This hints at the possibility that OM's usefulness increases only up to a certain degree of show the number of episodes required to reaches the threshold (lower is better). Bottom-halfs show progression of mean winrates during training (higher is better). Whiskers (top) and shaded areas (bottom) show 95% bootstrap confidence intervals. A datapoint is computed every policy update (i.e every 800 episodes) by evaluating the winrate of the apprentice policy against the opponent over 100 episodes. Note that runs terminate when crossing the target, and thus mean winrates cover fewer training runs for high episode numbers. accuracy, echoing recent findings [24]. Hence, while BRExIt does require access to ground truth policies during search, search in BRExIt-OMS merely needs opponent models trained on action observations, which is promising for transferring BRExIt-OMS into practical applications.

C. A reflection on the evolution of training schemes
ExIt was popularized over three publications which presented increasingly stronger playing agents: AlphaGo [12], AlphaGo Zero [27] and Alpha Zero [28]. Each publication kept ExIt's internal workings mostly unchanged except for hyperparameter choices and the progressive removal of environment specific enhancements. Yet, every publication meaningfully changed the higher level training scheme that governed ExIt's training, which we discuss here along with their implications for training ExIt or BRExIt agents.
The initial AlphaGo used δ = 0 self-play [6], where a population kept previous versions of the policy network from which opponents were randomly sampled at the beginning of each episode. The latest version of the policy network was added to the population after a set number of model updates. The authors claimed that this opponent randomization kept the apprentice from overfitting to its own policy. Recall that the underlying ExIt agent biases its expert search towards a best response against the apprentice's own policy, by using the apprentice π θ to compute action priors on every node in the search tree. This means that the expert generated policies targets will not try to exploit the opponents it trained against, choosing instead more conservative searches which regress against a response to a Nash equilibrium. Recent studies show that this conservativeness can be detrimental in terms of finding diverse sets of policies throughout training for population-based training schemes [29], [5]. Instead, they advocate for a more aggressive computation of best responses against known opponents. Through this practice, a wider area   Fig. 4: Each row shows the probability (vertical marker) that the algorithm X (left) trains its apprentice's policy to reach a 50 % winrate with fewer episodes than the algorithm Y (right). Higher is better for algorithm X; colored bars indicate 95% bootstrap confidence intervals. Note that because every BRExIt run finished earlier than ExIt-OMFS, their comparison has a 100% PoI. of the policy space is explored by the training agents, allowing the higher level training scheme to better decide on which opponents to use as targets to guide future exploration. We argue that BRExIt has this exploitative property built-in, by actively biasing its search towards a best response against ground truth opponent policies. Future work could focus on empirically verifying this claim.

Algorithm Y
AlphaGo Zero and AlphaZero differ in similar ways. The former opts for a restricted version of naive self-play in which the learning ExIt agent plays against an identical copy of itself; but if after some amount of training episodes it fails to beat its previous checkpoint by a set winrate margin, its network parameters are rolled back to that of the checkpoint's, enforcing monotonic improvement on saved checkpoints. Finally, AlphaZero dropped this last constraint, and simply used naive self-play, as they claimed improved performance. We note that under naive self-play as training scheme, BRExIt using ground truth opponent models and ExIt are equivalent (ignoring the feature shaping effects that opponent models have on the apprentice network). This is because in naive self-play, the opponent acts using the same apprentice policy network as the learning agent. Hence, by having the ground truth opponent models being the same as the apprentice policy network, we have π j −i =π ψj , meaning that the computation of P (s, a) will be identical for BRExIt and ExIt. In this case the learning agent is approximating a best response against its opponents, even in the case of ExIt. We hypothesise that this might be one of the reasons why naive self-play performs better than δ = 0 uniform for the training of ExIt agents.

VI. CONCLUSION
This paper investigates the use of opponent modelling within the ExIt framework, introducing the BRExIt algorithm. BRExIt augments ExIt by introducing opponent models both within the expert planning phase to bias its search towards a best response against models, and within the apprentice's model, to use opponent modelling as an auxiliary task. In the game of Connect4, we demonstrate BRExIt's sample efficiency over ExIt at training a well performing policy against fixed agents.
Our results open multiple avenues for future work. Given the achieved sample efficiency, BRExIt could be integrated and tested as a policy improvement operator in populationbased training schemes. In addition, search methods often struggle with complex simultaneous games due to the high branching factor stemming from combinatorial action spaces, which could be alleviated by using BRExIt's opponent models to narrow down the search space.

A. Training & Benchmarking opponents
We used δ = 0-Uniform self-play [6], also to train our test PPO agents. This self-play scheme makes a copy of the learning agent at the end of each episode, and adds it to the population, the set of available policies to be used as opponents in the environment. At the beginning of each episode, a policy is randomly sampled from the population. This selfplay scheme is effective for relatively simple games like Connect4, because it ensures that the learning agent continues to face all policies discovered during training, preventing catastrophic forgetting and cyclic policy evolution, which leads to transitively better strategies. As previously mentioned, we generated three internally monotonically stronger agents π test = [π 1 , π 2 , π 3 ], by freezing a copy of a PPO [9] agent trained under δ = 0-Uniform self-play [6] after 200k, 400k and 600k episodes respectively.  [2,3], [3,4] Table I shows the hyperparameters used to train the test agents. No formal hyperparameter sweep was conducted, and the final values were chosen after a few manual trials. We experimented with frame stacking to add a temporal dimension to the state space, but it was ultimately discarded as it lead to weaker agents for our compute budget.
To evaluate the relative strength of the test agents we computed their corresponding winrate evaluation matrix to study pair-wise agent performances, as shown in Figure 5. We see that older agents (age is represented by agent ID) can consistently beat previous versions of themselves. This shows a transitive improvement within the population of agents that emerges from our single training run. However, the nature of PPO agents is reactive, as there is no planning involved during their training. This means that agents are internally better because they learn how to exploit specific weaknesses of previous agents, which might not be present in other agents generated via planning based methods such as BRExIt. Because BRExIt during training uses planning to choose its actions, we ultimately want to give a ranking to our test agents against MCTS based methods. In order to label our test agents with the labels of weak, medium and strong used in the main text, we use MCTS equivalent strength. Which we define as the computational budget (number of internal MCTS iterations) required for an MCTS agent to reach a w% winrate against a given agent π. Figure 6 shows a sweep of MCTS equivalent strength up to 80% winrate. Surprisingly, we see that the test agent with only 200K training episodes, even though it is the weakest when matched uniquely against other agents from the test population as seen in Figure 5, is the strongest against MCTS. We hypothesize that in the relatively low computational budgets that we have used for our agents, the heavily stochastic behaviour of the 200K agent can thwart shallow plans made by low budget MCTS agents. For the remaining two agents, the agent trained the longest at 600K episodes consistently stays below the 400K agent in Figure 6. This denotes that it requires a higher MCTS budget to be beaten and is thus stronger against MCTS than the 400K agent. It is from these strength analysis against MCTS that we label the 400K, 600K and 200K agents as weak, medium and strong respectively as seen in the main paper.

B. Test agents neural network architecture
In order to level the playing field to compare all algorithms, we have adjusted the actor-critic architecture, used by ExIt, and the opponent modelling enhanced actor-critic architecture, used by the rest, to feature a similar number of parameters (approximately 27.000 trainable parameters). All parameters are randomly initialized.
The game of Connect4 is played on a 6 × 7 grid, and each grid position can either be empty, occupied by one of player 1's chips, or by one of player 2's chips. Thus the input to PPO and BRExIt's neural network model was a 3 × 6 × 7 tensor (a 3 channeled 6 × 7 grid).  This input tensor was put through 5 convolutional layers, with residual connections skipping every other layer. Extra details are present on Table I. The output embedding found at the end of the last convolutional layer was fed into two parallel layers. One, a fully connected layer with a softmax activation function which represented the agent's policy (the actor). The other, a single neuron and no activation function representing a state-value function (the critic). Table III shows the p-values corresponding to the different two-sided Kolmogorov-Smirnov tests. This test measures if there is a significant statistical difference between 2 distributions f (x) and g(x). In our case, f, g correspond to an algorithmic ablation, x to a test agent policy and f (x), g(x) to the stochastic functions that determine how many episodes are required to achieve the target winrate of 50% against policy x. Each of the 6 training runs used for each algorithm f (originally 10, but we discard the top and bottom 2 performing runs as per [31]) gives us one data point for f (x). Thus, our comparisons are between sets of 6 data-

D. Hyperparameters and general performance improvements
Deep reinforcement learning algorithms require a large amount of simulated experiences to train policies, and more so for deep multi-agent reinforcement learning. This is further exacerbated when planning based algorithms are used as part of RL algorithms, as is the case with MCTS within BRExIt. A single step in the main game requires many simulated games inside of MCTS. On top of this, RL methods tend to not be robust to hyperparameters, requiring a lot of manual tuning and stabilizing implementation details. Because of this, it is common place to add ad-hoc or environment specific methods to reduce the amount of compute required to train policies and to increase their robustness. Here we present some performance improvements shared across all algorithmic ablations, which are orthogonal to the novel contributions presented in this paper but were nonetheless required to train our agents within our computational budget. We argue that these improvement methods benefit all ablations equally, and thus do not affect our comparisons. We present them here for completeness and to aid reimplementations efforts. The set of hyperparameters used for all algorithmic ablations during the final training run is present in Table II. 1) Reducing exploration: removing Dirichlet noise on MCTS root priors: The algorithm AlphaGo [25] introduced the notion of adding noise to the prior probabilities in the root note. By adding noise, we modify the priors over actions used in the selection phase, given by the apprentice's statevalue function. This is used as an exploration mechanism, by redistributing some probability weight given by the priors over all valid actions. The Dirichlet distribution is used to sample that noise: P (s, a) = 0.25 * Dirichlet(α) + 0.75 * P (s, a), where α = √ 2. This ensures that moves that the apprentice's policy would ignore are visited at least a few times by MCTS. During an MCTS search with thousands of iterations (as was the case with AlphaZero), the effects of this Dirichlet noise on the root node's priors would be washed out by state evaluations propagated upwards from further down the tree. However, in our usecase, due to our relatively low MCTS budget of 50, we cannot afford to use Dirichlet noise, as this exploratory noise would randomize too much the search's output policy π M CT S .
2) Sample efficiency: Data augmentation via exploiting state space symmetries: The board of Connect4, a 6 × 7 matrix, is symmetrical over the vertical axis. We can exploit this to reduce the complexity of the environment. Let's define a function over states σ(S) → S which swaps columns with indexes {1, 2, 3} with those with index {5, 6, 7}; and also over policies σ(Π) → Π by also swapping the probability weight over those column indices. Strategically speaking, those two situations are identical, because of the symmetry on the state space. Alpha Zero was shown to be able to naturally learn this symmetry over enough training episodes [25]. We add this symmetry prior into our algorithm to reduce computational costs. This is done by augmenting every datapoint at the time it is going to be appended to the replay buffer by adding a copy with a corresponding symmetric transformation, on both the state and the policy target (and the opponent policy target in case of BRExIt). The value target remains the same. More formally, for every datapoint we obtain a tuple:  in a replay buffer {s t , π M CT S (·|s t ), G i t }, where G i t denotes player i's total reward observed at the end of the episode. What this means for our state value function V (s t ) is that we are regressing all observed states in an episode [s 0 , s 1 , . . .] to the same value G i t . This target features a lot of variance, as we are mapping potentially dozens of states to the same target value. We can reduce the variance, with the downside of introducing bias, by re-using state-dependant computation from each state-dependant MCTS call, meaning that we won't use the same value target for each state. For every datapoint we substitute G i t by another variable z i t , for which we try three different alternatives: Definition of V π M CT S (s) First, averaging the original original target with MCTS's root node value. Due to the Monte Carlo nature of MCTS, this includes the value of sub-optimal actions that were discarded during simulations as part of its exploration. This in turn induced pessimism in V (s) estimations by our learnt critics V φ (s), where they would consistently estimate lower winrates than those observed in practice.
Greedy w.r.t Q(s, ·) Instead, we tried using the value of the root node's most valued child. This also introduced a bias, although this time in a positive direction, because the policy that will be followed corresponds to MCTS's normalized child visitations, Equation 5, which will put some probability weight on actions which are not the most valuable.

MCTS action selection
Ultimately, we decided to average the episode returns with the Q(s, a) value associated with the action used in the real environment, or equivalently, the action selected by MCTS selection phase. We used a standard action selection phase which given the root node, picks the most visited action. Theoretically this still yields biased targets, as our actors π θ imitate an MCTS derived policy π M CT S while our critic V φ will regress against state-values which will not exactly match the actions taken π M CT S . However, not only did this seem to work well in practice, we saw little to no bias in our critic's estimations compared to the real episode returns using this bootstrapped estimations. 4) Extra exploitation: Temperature parameter: It is beneficial to have a high degree of exploration on the initial states of an environment, specially during early stages of training. The intuition being that exploratory policies that feature non-zero probability of taking many different actions will cover a larger volume of S when compared to deterministic policies, the former allowing the discovery of good performing policies. This is specially important early in an episode, where exploration is much more likely to find undiscovered states rather than nearing the end of an episode. Nearing the end of an episode, more exploratory policies can fail to exploit opportunities to perform a coup de grâce to obtain large rewards which would be readily gathered by more exploitative policies.
The policy targets derived from MCTS's normalized child visitations π M CT S feature a high degree of exploration, especially with our low computational budget, as MCTS would discard low quality moves given larger computational budgets. This is convenient early during training for the aforementioned exploration on initial states, but is detrimental when learning exploitative policies against fixed agents, as it slows learning. Thus, ideally we would like to focus initial moves on exploration, and switch to exploitation later into an episode.
The way we achieve this is by having a temperature parameter τ , which we use to exponentiate MCTS' child visitations before they are normalized: We set τ = 1 for the first 10 moves, after which we reduce it to τ = 0.01, which effectively moves all probability weight to the most visited action, generating a highly exploitative policy. Therefore, the first 10 moves will contain MCTS's exploration, and the rest will feature only the most-visited action. We note that there exists research on this area, with a focus on removing exploration elements from MCTS policy targets with the hope of aiding interpretability [32]. 5) Parallel data generation: Parallelized MCTS with centralized apprentice: We simulate multiple games of Connect4 in parallel, With every MCTS procedure running on an individual CPU core. A single process hosts the apprentice's neural network, acting as a server, whose only function is to receive states from all MCTS processes. These are evaluated for (1) node priors P (s, a) and (2) state evaluations V (s). It busy polls all connections to MCTS processes for incoming states, batching all requests into a single neural network forward pass. This allows us to scale horizontally, theoretically linearly with the number of available CPUs. Because of the size of the network, Connect4's small state size and the average batch size, we saw no performance improvement hosting the apprentice in CPU vs GPU. Surprisingly, our bottleneck came from Python's communication of PyTorch tensors among processes.
6) Growing Replay Buffer size: When observing the rate of improvement of RL agents with respect to conventional metrics, such as reward for single agent scenarios or winrate versus opponents for multi-agent RL settings, it is common to see exponential initial improvements which eventually slow down into relative plateaus. We make the observation that, given a sufficiently large experience replay, the initial experiences generated by policies that were exponentially outclassed by later policies will remain in the experience buffer for a long time. This can be of some benefit for learning a critic V (s), as large replay buffers will almost certainly increase their coverage of the state space. However, we argue that the imitation-based nature of the actor in ExIt based algorithms distinctively suffers from the inclusion of datapoints within their replay buffer at early stages of training. This is because early expert policy targets π M CT S will be copied directly. These will bias the apprentice's policy towards early bad play until these early targets are removed from the experience replay.
Taking this effect into account, we implemented a slowly increasing replay buffer, where the size of the dataset would begin small, and then slowly increase as more training generations elapsed. This allowed us to quickly phase out very early data before settling to our fixed window size. We start with a replay buffer which holds only the latest 5 generations of experiences. Every 5 generations, we increase the replay buffer capacity by 5 extra generations, until a seldom reached maximum of 200 generations. This yielded modest performance improvments.
7) Gradient norm clipping: Many RL algorithms which involve computing gradients with respect to a loss function suffer from high variance in the estimation of these gradients. If the parameters of a model are updated by applying gradients of a large magnitude, these might move the model's parameters into poor performing sections of the parameter space. A proposed solution is to introduce gradient clipping [33]. It's most naive implementation involves clipping the value of each individual gradient to a hyperparameter threshold c. A more nuanced alternative is gradient norm clipping. It involves concatenating all gradients of all parameters into a single vector g. If the vector's nth norm is greater than a threshold value c, then the vector is normalized according to: For all experiments we used the L 2 norm. We tried thresholds of 5, 3 and 1. Even though we found that higher thresholds yielded a sharper increase in performance early on, a threshold of c = 1 ended up achieving better stability and final performance than the other values.