{'fraction_non_alphanumeric': 0.03625479784420182, 'fraction_numerical': 0.013702444166020325, 'mean_word_length': 4.6422800718132855, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning

A fundamental challenge in multiagent reinforcement learning is to learn beneficial behaviors in a shared environment with other simultaneously learning agents. In particular, each agent perceives the environment as effectively non-stationary due to the changing policies of other agents. Moreover, each agent is itself constantly learning, leading to natural non-stationarity in the distribution of experiences encountered. In this paper, we propose a novel meta-multiagent policy gradient theorem that directly accounts for the non-stationary policy dynamics inherent to multiagent learning settings. This is achieved by modeling our gradient updates to consider both an agent's own non-stationary policy dynamics and the non-stationary policy dynamics of other agents in the environment. We show that our theoretically grounded approach provides a general solution to the multiagent learning problem, which inherently comprises all key aspects of previous state of the art approaches on this topic. We test our method on a diverse suite of multiagent benchmarks and demonstrate a more efficient ability to adapt to new agents as they learn than baseline methods across the full spectrum of mixed incentive, competitive, and cooperative domains.


Introduction
Learning in multiagent settings is inherently more difficult than single-agent learning because an agent interacts both with the environment and other agents (Buşoniu et al., 2010). Specifically, the fundamental challenge in multiagent reinforcement learning (MARL) is the difficulty of learning optimal policies in the presence of other simultaneously learning agents because their changing behaviors jointly affect the environment's transition and reward function. This dependence on non-stationary policies renders the Markov property invalid from the perspective of each agent, requiring agents to adapt their behaviors with respect to potentially large, unpredictable, and endless changes in the policies of fellow agents (Papoudakis et al., 2019). In such environments, it is also critical that agents adapt to the changing behaviors of others in a sample-efficient manner as it is likely that their policies could update again after a small number of interactions. Therefore, effective agents should consider the learning of other agents and adapt quickly to their non-stationary behaviors. Otherwise, undesirable outcomes may arise when an agent is constantly lagging in its ability to deal with the current policies of other agents.
Our paper proposes a new framework based on metalearning to address the inherent non-stationarity of MARL. Meta-learning (also referred to as learning to learn) was recently shown to be a promising methodology for fast adaptation in multiagent settings. The framework by Al-Shedivat et al. (2018), for example, introduces a meta-optimization scheme in which a meta-agent can adapt more efficiently to changes in a new opponent's policy after collecting only a handful of interactions. The key idea is to model the meta-agent's own learning process so that its updated policy performs better than an evolving opponent. However, prior work does not directly consider the learning processes of other agents during the meta-optimization process, instead treating the other agents as external factors and assuming the meta-agent cannot influence their future policies. As a result, prior work on multiagent meta-learning fails to consider an important property of MARL: other agents in the environment are also learning and adapting their own policies based on interactions with the meta-agent. Thus, the meta-agent is missing an opportunity to influence the others' future policies through these interactions, which could be used to improve its own performance. directly models the learning processes of all agents in the environment within a single objective function. We achieve this by extending past work that developed the meta-policy gradient theorem (Meta-PG) in the context of a single agent multi-task RL setting  to the full generality of a multiagent game where every agent learns with a Markovian update function.
2) Theoretical analysis and comparisons: Our analysis of Meta-MAPG reveals an inherently added term, not present in Al-Shedivat et al. (2018), closely related to the process of shaping the other agents' learning dynamics in the framework of Foerster et al. (2018a). As such, our work contributes a theoretically grounded framework that unifies the collective benefits of previous work by Al-Shedivat et al. (2018) and Foerster et al. (2018a). Moreover, we formally demonstrate that Meta-PG can be considered a special case of Meta-MAPG if we assume the learning of the other agents in the environment is constrained to be independent of the meta-agent behavior. However, this limiting assumption does not typically hold in practice, and we demonstrate with a motivating example that it can lead to a total divergence of learning that is directly addressed by the correction we derive for the meta-gradient.
3) Empirical evaluation: We evaluate Meta-MAPG on a diverse suite of multiagent domains, including the full spectrum of mixed incentive, competitive, and cooperative environments. Our experiments demonstrate that, in contrast with previous state-of-the-art approaches on this topic, Meta-MAPG consistently results in a superior ability to adapt in the presence of novel agents as they learn.

Understanding Non-Stationarity in MARL
In MARL, when the policies of all other agents in the environment are stationary, they can be considered to be effectively a part of the environment from the perspective of each agent, resulting in a stationary single agent Markov decision process for each agent to learn from. However, in practice, the other agents in the environment are not fixed, but rather always learning from their recent experiences. As we detail in this section, this results in the inherent non-stationarity of MARL because Markovian update functions for each agent induce a Markov chain of joint policies. Indeed, when the policies of other agents constantly change, the problem is effectively non-stationary from each agent's perspective if the other agents are viewed as part of the environment.

Stochastic Games
Interactions between multiple agents can be represented by stochastic games (Shapley, 1953). Specifically, an n-agent stochastic game is defined as a tuple M n = I, S, A, P, R, γ ; I = {1, . . ., n} is the set of n agents, S is the set of states, A = × i∈I A i is the set of action spaces, P : S × A → S is the state transition probability function, R = × i∈I R i is the set of reward functions, and γ ∈ [0, 1) is the discount factor. We typeset sets in bold for clarity. Each agent i executes an action at each timestep t according to its stochastic policy a i t ∼ π i (a i t |s t , φ i ) parameterized by φ i , where s t ∈ S. A joint action a t = {a i t , a −i t } yields a transition from the current state s t to the next state s t+1 ∈ S with probability P(s t+1 |s t , a t ), where the notation −i indicates all other agents with the exception of agent i. Agent i then obtains a reward according to its reward function r i t = R i (s t , a t ). At the end of an episode, the agents collect a trajectory τ φ under the joint policy with parameters φ, where τ φ := (s 0 , a 0 , r 0 , . . ., r H ), φ = {φ i , φ −i } represents the joint parameters of all policies, r t = {r i t , r −i t } is the joint reward, and H is the episode horizon.

A Markov Chain of Joint Policies
The perceived non-stationarity in multiagent settings results from a distribution of sequential joint policies, which can be represented by a Markov chain. Formally, a Markov chain of policies begins from a stochastic game between agents with an initial set of joint policies parameterized by φ 0 = {φ i 0 , φ −i 0 }. We assume that each agent updates its policy leveraging a Markovian update function φ i 1 ∼ U i (τ φ0 , φ i 0 ) that changes the policy after every K trajectories. After this time period, each agent i updates its policy in order to maximize the expected return expressed as its value function: where G i denotes agent i's discounted return from the beginning of an episode with initial state s 0 . The joint policy update results in a transition from φ 0 to the updated set of joint parameters φ 1 . The Markov chain continues for a maximum chain length of L (see Figure 1a). This Markov chain perspective highlights the following inherent aspects of the experienced non-stationarity: 1) Sequential dependency: The future joint policy parameters φ 1:L = {φ 1 , . . ., φ L } sequentially depend on φ 0 since a change in τ φ0 results in a change in φ 1 , which in turn affects τ φ1 and all successive joint policy updates up to φ L .
2) Controllable levels of non-stationarity: As in Al-Shedivat et al. (2018) and Foerster et al. (2018a), we assume stationary policies during the collection of K trajectories, and that the joint policy update happens afterward. In such a setting, it is possible to control the non-stationarity by adjusting the K and H hyperparameters: smaller K and H increase the rate that agents change their policies, leading to a higher degree of non-stationarity in the environment.

Learning to Learn in MARL
This section explores learning policies that can adapt quickly to non-stationarity in the policies of other agents in the environment. To achieve this, we leverage meta-learning and devise a new meta-multiagent policy gradient theorem that exploits the inherent sequential dependencies of MARL discussed in the previous section. Specifically, our meta-agent addresses this non-stationarity by considering its current policy's impact on its own adapted policies while actively influencing the future policies of other agents as well by inducing changes to the distribution of trajectories. In this section, we first outline the meta-optimization objective of MARL and then derive our policy gradient theorem to optimize this objective. Finally, we discuss how to interpret our meta-policy gradient theorem with respect to prior work.

Gradient Based Meta-Optimization in MARL
We formalize the meta-objective of MARL as optimizing meta-agent i's initial policy parameters φ i 0 so that it maximizes the expected adaptation performance over a Markov chain of policies drawn from a stationary initial distribution of policies for the other agents p(φ −i 0 ): where τ φ 0: = {τ φ0 , . . ., τ φ } and V i φ 0: +1 (s 0 , φ i 0 ) denotes the meta-value function. This meta-value function generalizes the notion of each agent's primitive value function for the current set of policies V i φ0 (s 0 ) over the length of the Markov chain of policies. In this work, we assume that the Markov chain of policies is governed by a policy gradient update function that corresponds to what is generally referred to as the inner-loop optimization in the literature: where α i and α −i denote the learning rates.

The Meta-Multiagent Policy Gradient Theorem
A meta-agent needs to account for both its own learning process and the learning processes of other peer agents in the environment to fully address the inherent non-stationarity of MARL. We will now demonstrate that our generalized meta-policy gradient includes terms that explicitly account for the effect a meta-agent's current policy will have on its own adapted future policies as well as the future policies of peers interacting with it.

Theorem 1. (Meta-Multiagent Policy Gradient Theorem)
For any stochastic game M n , the gradient of the meta-value function for agent i at state s 0 with respect to current policy parameters φ i 0 evolving in the environment along with other peer agents using initial parameters φ −i 0 is: Proof. See Appendix A for a detailed proof.
In particular, Meta-MAPG has three primary terms. The first term corresponds to the standard policy gradient with respect to the current policy parameters used during the initial trajectory. Meanwhile, the second term This enables a metaagent to model its own learning dynamics and account for the impact of φ i 0 on its eventual adapted parameters φ i +1 . By contrast, the last term ∇ φ i 0 log π(τ φ +1 |φ −i +1 ) aims to additionally compute gradients through the sequential dependency between the meta-agent's initial policy φ i 0 and the future policies of other agents in the environment φ −i 1: +1 . As a result, the peer learning term enables a meta-agent to learn to change τ φ0 in a way that influences the future policies of other agents and improves its adaptation performance over the Markov chain of policies.
Interestingly, the peer learning term that naturally arises when taking the gradient in Meta-MAPG is similar to a term previously considered in the literature by Foerster et al. (2018a). However, for the Learning with Opponent Learning Awareness (LOLA) approach (Foerster et al., 2018a), this term was derived in an alternate way following a first order Taylor approximation with respect to the value function. Moreover, the own learning term previously appeared in the derivation of Meta-PG . Indeed, it is quite surprising to see how taking a principled policy gradient while leveraging a more general set of assumptions leads to a unification of the benefits of key prior work Foerster et al., 2018a) on adjusting to the learning behavior of other agents in MARL.

Connection to the Meta-Policy Gradient Theorem
The framework of Al-Shedivat et al. (2018) derived the meta-policy gradient theorem for optimizing a setup like this. However, it is important to note that they derived this gradient while making the implicit assumption to ignore the sequential dependence of the future parameters of other agents on φ i 0 , resulting in the missing peer learning term: Remark 1. Meta-PG can be considered as a special case of Meta-MAPG when assuming that other agents' learning in the environment is independent of the meta-agent's behavior.
Proof. See Appendix B for a corollary.
Specifically, Meta-PG treats other agents as if they are external factors whose learning it cannot affect. For example, a meta-agent in Al-Shedivat et al. (2018) competes against an opponent that has been pre-trained with self-play. The next agent after the current interaction is then loaded as the same opponent with one more step of training with self-play. As a result of this contrived setup, the opponent's policy update is based on data collected without a meta-agent presented in the environment and Meta-PG can get away with assuming that the peer's learning process is not a function of a meta-agent's behavior. However, we note that this assumption does not hold in practice for the general multi-agent learning settings we explore in this work. As highlighted in Section 2, every agent's policy jointly affects the environment's transition and reward functions, resulting in the inherent sequential dependencies of MARL. Therefore, a meta-agent's behavior can affect the future policies of its peers, and these cannot be considered as external factors.
Probabilistic model perspective. Probabilistic models for Meta-PG and Meta-MAPG are depicted in Figure 1b. As shown by the own learning gradient direction, a metaagent i optimizes φ i 0 by accounting for the impact of φ i 0 on its updated parameters φ i 1: +1 and adaptation performance G i (τ φ +1 ). However, Meta-PG considers the other agents as external factors that cannot be influenced by the meta-agent, as indicated by the absence of the sequential dependence between τ φ 0: and φ −i 1: +1 in Figure 1b. As a result, the meta-agent loses an opportunity to influence the future policies of other agents and further improve its adaptation performance, which can cause undesirable learning failures as highlighted by the following motivating example.
Example 1. Failure to consider our influence on the learning of other agents can result in biased and sometimes even counterproductive optimization.
For example, consider a stateless zero-sum game played between two agents based off the one shown by Letcher et al. (2019). A meta-agent i and an opponent j maximize simple value functions We assume a maximum Markov chain length L of 1 and focus on meta-agent i's adaptation performance V i φ1 . Given an opponent's initial policy parameters randomly sampled from p(φ −i 0 ), we compare training a meta-agent i with either Meta-PG or Meta-MAPG. As Figure 2 shows, Meta-PG performs biased updates that actually make its performance worse over the course of meta-training. In contrast, by considering the opponent's learning process, Meta-MAPG corrects for this bias, displaying smooth convergence to a winning strategy. See Appendix C for more details, including the meta-gradient derivation.

Algorithm
We provide pseudo-code for Meta-MAPG in Algorithm 1 for meta-training and Algorithm 2 for meta-testing in Appendix D. Note that Meta-MAPG is centralized during metatraining as it requires the policy parameters of other agents to compute the peer learning gradient. For settings where a meta-agent cannot access the policy parameters of other agents during meta-training, we provide a decentralized meta-training algorithm with opponent modeling, motivated by the approach used in Foerster et al. (2018a), in Appendix D.1 that computes the peer learning gradient while leveraging only an approximation of the parameters of peer agents. Once meta-trained in either case, the adaptation to new agents during meta-testing is purely decentralized such that the meta-agent can decide how to shape other agents with its own observations and rewards alone.

Related Work
The standard approach for addressing non-stationarity in MARL is to consider information about the other agents and reason about the effects of their joint actions (Hernandez-Leal et al., 2017). The literature on opponent modeling, for instance, infers opponents' behaviors and conditions an agent's policy on the inferred behaviors of others (He et al., 2016;Raileanu et al., 2018;Grover et al., 2018). Studies regarding the centralized training with decentralized execution framework (Lowe et al., 2017;Foerster et al., 2018b;Yang et al., 2018;Wen et al., 2019), which accounts for the behaviors of others through a centralized critic, can also be classified into this category. While this body of work alleviates non-stationarity, it is generally assumed that each agent will have a stationary policy in the future. Because other agents can have different behaviors in the future as a result of learning (Foerster et al., 2018a), this incorrect assumption can cause sample inefficient and improper adaptation. In contrast, Meta-MAPG models each agent's learning process, allowing a meta-learning agent to adapt efficiently.
Our approach is also related to prior work that considers the learning of other agents in the environment. This includes Zhang & Lesser (2010) who attempted to discover the best response adaptation to the anticipated future policy of other agents. Our work is also related, as discussed previously, to LOLA (Foerster et al., 2018a) and more recent improvements (Foerster et al., 2018c). Another relevant idea explored by Letcher et al. (2019) is to interpolate between the frameworks of Zhang & Lesser (2010) and Foerster et al. (2018a) in a way that guarantees convergence while influencing the opponent's future policy. However, all of these approaches only account for the learning processes of other agents and fail to consider an agent's own non-stationary policy dynamics as in the own learning gradient discussed in the previous section. Additionally, these papers do not leverage meta-learning. As a result, these approaches may require many samples to properly adapt to new agents.
Meta-learning (Schmidhuber, 1987;Bengio et al., 1992) has recently become very popular as a method for improving sample efficiency in the presence of changing tasks in the deep RL literature (Wang et al., 2016a;Duan et al., 2016b;Finn et al., 2017;Mishra et al., 2017;Nichol & Schulman, 2018). See Vilalta & Drissi (2002) and Hospedales et al. (2020) for in-depth surveys of meta-learning. In particular, our work builds on the popular model-agnostic metalearning framework (Finn et al., 2017), where gradientbased learning is used both for conducting so called innerloop learning and to improve this learning by computing gradients through the computational graph. When we train our agents so that the inner loop can accommodate for a dynamic Markov chain of other agent policies, we are leveraging an approach that has recently become popular for supervised learning called meta-continual learning (Riemer et al., 2019;Javed & White, 2019;Spigler, 2019;Beaulieu et al., 2020;Caccia et al., 2020;Gupta et al., 2020). This means that our agent trains not just to adapt to a single set of policies during meta-training, but rather to adapt to a set of changing policies with Markovian updates. As a result, we avoid an issue of past work  that required the use of importance sampling during meta-testing (see Appendix F.1 for more details).

Experiments
We demonstrate Meta-MAPG's efficacy on a diverse suite of domains, including the full spectrum of mixed incentive, competitive, and cooperative settings. The code is available at https://git.io/JZsfg, and video highlights are available at http://bit.ly/2L8Wvch. The mean and 95% confidence interval computed for 10 seeds are shown in each figure.

Experimental Setup for Meta-Learning in MARL
Training protocol. In our experiments, we evaluate a metaagent i's adaptability with respect to a peer agent j learning in the environment. Specifically, agent j is sampled from a population of initial peer policy parameters p(φ −i 0 ). Then, both agents adapt their behavior following the policy gradient with a linear feature baseline (Duan et al., 2016a) (see Figure 3). Importantly, the population captures diverse behaviors of j, such as varying expertise in solving a task, and j's initial policy is hidden to i. Hence, a meta-agent i should: 1) adapt to a differently initialized agent j with varying behaviors and 2) continuously adapt with respect to j's changing policy.
During meta-training, a meta-agent i interacts with peers drawn from the distribution and optimizes its initial policy parameters φ i 0 . At the end of meta-training, a new peer j is sampled from the distribution, and we measure i's performance throughout the Markov chain.
Adaptation baselines. We compare Meta-MAPG with the following baseline adaptation strategies for an agent i: : A meta-learning approach that only considers how to improve its own learning. We detail our implementation of Meta-PG and a low-level difference with the original method in Appendix F.1.
2) LOLA-DiCE (Foerster et al., 2018c): An approach that only considers how to shape the learning dynamics of other agents in the environment through the Differentiable Monte-Carlo Estimator (DiCE) operation. Note that LOLA-DiCE is an extension of the original LOLA approach.  Figure 3. Experimental setup for meta-learning. A peer j's policy is initialized randomly from a population p(φ −i 0 ) and is updated based on the policy gradient optimization, requiring a meta-agent i to adapt to differently initialized j and its changing policy.
3) REINFORCE (Williams, 1992): A simple policy gradient approach that considers neither an agent's own learning nor the learning processes of other agents. This baseline represents multiagent approaches that assume each agent leverages a stationary policy in the future.
Implementation. We implement each adaptation method's policy leveraging an LSTM and use the generalized advantage estimation (Schulman et al., 2016) with a learned value function for the meta-optimization. We also apply DiCE during the inner-loop optimization (Foerster et al., 2018c) to compute the peer learning gradients, and we learn dynamic inner-loop learning rates during meta-training as suggested in Al-Shedivat et al. (2018). We refer to Appendices E, F, G, I for the remaining details including hyperparameters.
Experiment complexity. We study various aspects of Meta-MAPG based on two repeated matrix games (see Figures 4a and 4b). We note that the repeated matrix domains we consider match the environment complexity of previous work on the topic of peer learning awareness in MARL (Foerster et al., 2018a;Letcher et al., 2019). We also considered the RoboSumo domain from Al-Shedivat et al. (2018). However, the training performance was very sensitive to the relative weights between the shaped reward functions and we could not reproduce the results from Al-Shedivat et al. (2018) with the default weights. Instead, we experimented with another challenging environment leveraging the multi-agent MuJoCo benchmark (de Witt et al., 2020) to demonstrate the scability of Meta-MAPG. Specifically, the environment shown in Figure 4c has high complexity: 1) the domain has continuous and large observation/action spaces, and 2) the agents are coupled within the same robot, resulting in a more challenging control problem than controlling the robot alone with full autonomy.

IPD Environment: Mixed Incentive
Question 1. Is it essential to consider both an agent's own learning and the learning of others? To address this question, we consider the classic iterated prisoner's dilemma (IPD) domain. In IPD, agents i and j act Agent j by either (C)ooperating or (D)efecting and receive rewards according to the mixed incentive payoff defined in Figure 4a. As in Foerster et al. (2018a), we model the state space as s 0 = ∅ and s t = a t−1 for t ≥ 1. For meta-learning, we construct a population of initial personas p(φ −i 0 ) that include cooperating personas (i.e., having a probability of cooperating between 0.5 and 1.0 at any state) and defecting personas (i.e., having a probability of cooperating between 0 and 0.5 at any state). Figure 7a in Appendix shows the population distribution utilized for training and evaluation.
The adaptation performance during meta-testing when an agent i, meta-trained with either Meta-MAPG or the baseline methods, interacts with an initially cooperating or defecting agent j is shown in Figure 5a and Figure 5b, respectively. In both cases, our meta-agent successfully infers the underlying persona of j and adapts throughout the Markov chain obtaining higher rewards than the baselines. We observe that performance generally decreases as the number of joint policy updates increases across all adaptation methods. This decrease in performance is expected as each model is playing with another reasonable agent that is also constantly learning. As a result, j realizes it could potentially achieve more reward by defecting more often. Hence, to achieve good adaptation performance in IPD, an agent i should attempt to shape j's future policies toward staying cooperative as long as possible such that i can take advantage, which is achieved by accounting for both an agent's own learning and the learning of other peer agents in Meta-MAPG.
We explore each adaptation method in more detail by visualizing the action probability dynamics throughout the Markov chain. In general, we observe that the baseline methods have converged to initially defecting strategies, attempting to get larger rewards than a peer agent j in the first trajectory τ φ0 . While this strategy can result in better initial performance than j, the peer agent will quickly change its policy so that it is defecting with high probability as well (see Figures 9 to 11 in Appendix). By contrast, our meta-agent learns to act cooperatively in τ φ0 and then take advantage by deceiving agent j as it attempts to cooperate at future steps (see Figure 12 in Appendix). Question 2. How is adaptation performance affected by the number of trajectories between changes? We control the level of non-stationarity by adjusting the number of trajectories K between updates (refer to Section 2.2).
The results in Figure 6a shows that the area under the curve (AUC) (i.e., the reward summation during φ 1:L ) generally decreases when K decreases in IPD. This result is expected since the inner-loop updates are based on the policy gradient, which can suffer from a high variance. Thus, with a smaller batch size, policy updates have a higher variance and lead to noisier policy updates. As a result, it is harder to anticipate and influence the future policies of peers. Nevertheless, Meta-MAPG achieves the best AUC in all cases. Question 3. How does Meta-MAPG perform with decentralized meta-training? We compare the performance of Meta-MAPG with and without opponent modeling (OM) in Figure 6b. We note that Meta-MAPG with opponent modeling can infer policy parameters for peer agents and compute the peer learning gradient in a decentralized manner, performing better than the Meta-PG baseline. However, opponent modeling introduces noise in predicting the future policy parameters of peer agents because the parameters must be inferred by observing the actions they take alone without any supervision about the parameters themselves. Thus, as expected, a meta-agent experiences difficulty in correctly considering the learning process of a peer, which leads to lower performance than Meta-MAPG with centralized meta-training. Question 4. Can Meta-MAPG generalize its learning outside the meta-training distribution?
We have demonstrated that a meta-agent can generalize well and adapt to a new peer. However, we would like to investigate this further and see whether a meta-agent can still perform well when the meta-testing distribution is drawn from a significantly different distribution in IPD. We thus evaluate Meta-MAPG and Meta-PG using both in distribution (as in the previous questions) and out of distribution personas for j's initial policies (see Figures 7a and 7b in Appendix). Meta-MAPG achieves an AUC of 13.77 ± 0.25 and 11.12±0.33 for the in and out of distribution evaluation, respectively. Meta-PG achieves an AUC of 6.13 ± 0.05 and 7.60 ± 0.07 for the in and out of distribution evaluation, respectively. Variances are based on 5 seeds and we leveraged K = 64 for this experiment. We note that Meta-MAPG's performance decreases during the out of distribution evaluation, but still consistently performs better than the baseline.

RPS Environment: Competitive
Question 5. How effective is Meta-MAPG in a fully competitive scenario?
We have demonstrated the benefit of our approach in the mixed incentive scenario of IPD. Here, we consider another classic iterated game, rock-paper-scissors (RPS) with a fully competitive payoff table (see Figure 4b). In RPS, at each time step agents i and j can choose an action of either (R)ock, (P)aper, or (S)cissors. The state space is defined as s 0 = ∅ and s t = a t−1 for t ≥ 1. For meta-learning, we consider a population of initial personas p(φ −i 0 ), including the rock/paper/scissors persona (with a rock/paper/scissors actions probability between 1/3 and 1). Figure 5c shows the adaptation performance during metatesting. Similar to the IPD results, we observe that the baseline methods have effectively converged to win against the opponent j in the first few trajectories. For instance, agent i has a high rock probability when playing against j with a high initial scissors probability (see Figures 13 to 15 in Appendix). This strategy, however, results in the opponent quickly changing its behavior toward the mixed Nash equilibrium strategy of (1/3, 1/3, 1/3) for the rock, paper, and scissors probabilities. In contrast, our meta-agent learned to lose slightly in the first two trajectories τ φ0:1 to achieve much larger rewards in the later trajectories τ φ2:7 while relying on its ability to adapt more efficiently than its opponent (see Figure 16 in Appendix). Compared to the IPD results, we observe that it is more difficult for our meta-agent to shape j's future policies in RPS possibly due to the fact that RPS has a fully competitive payoff structure, while IPD has a mixed incentive structure. Question 6. How effective is Meta-MAPG in settings with more than one peer? Our meta-multiagent policy gradient theorem is general and can be applied to scenarios with more than one peer. To validate this, we experiment with 3-player and 4-player RPS, where we consider sampling peers randomly from the entire persona population. We note that the domain becomes harder as the number of agents n increases, because the state space dimension grows exponentially as a function of n and a meta-agent needs to consider more peers in shaping their future policies. Figure 6c shows a comparison against the Meta-PG baseline. We generally observe that the peer agents change their policies toward the mixed Nash equilibrium more quickly as the number of agents increases, which results in decreased performance for all methods. Nevertheless, Meta-MAPG achieves the best performance in all cases and can clearly be easily extended to settings with a greater number of agents.
Question 7. What happens if a meta-agent is trained without the own learning gradient? Our meta-multiagent policy gradient theorem inherently includes both the own learning and peer learning gradient, but is it necessary to have both terms? To answer this question, we conduct an ablation study and compare Meta-MAPG to two methods: one trained without the peer learning gradient and another trained without the own learning gradient. Note that not having the peer learning term is equivalent to Meta-PG, and not having the own learning term is similar to LOLA-DiCE but alternatively trained with a metaoptimization procedure. Figure 6d shows that a meta-agent trained without the peer learning term cannot properly exploit the peer agent's learning process. Also, a meta-agent trained without the own learning term cannot change its own policy effectively in response to anticipated learning by peer agents. By contrast, Meta-MAPG achieves superior performance by accounting for both its own learning process and the learning processes of peer agents.

2-Agent HalfCheetah Environment: Cooperative
Question 8. Does considering the peer learning gradient always improve performance? To answer this question, we experiment with a fully cooperative setting of the the 2-Agent HalfCheetah domain (de Witt et al., 2020), where the first and second agent control three joints of the back and front leg with continuous action spaces, respectively (see Figure 4c). Both agents receive a joint reward corresponding to making the cheetah robot run to the right as soon as possible. Note that two agents are cou-pled within the cheetah robot, requiring close cooperation and coordination between them.
For meta-learning, we consider a population of teammates with varying degrees of expertise in running to the left direction. Specifically, we pre-train a teammate j and build a population based on checkpoints of its parameters during learning. Figure 8 in Appendix shows the distribution of j's expertise. Note that we construct the distribution with a significant gap to ensure that the meta-testing distribution is sufficiently different from the meta-training/validation distribution. This allows us to effectively evaluate the ability of our approach to generalize its learning. During metalearning, j is randomly initialized from this population of policies. Importantly, j must adapt its behavior in this setting because the agent has achieved the opposite skill during pre-training compared to the true objective of moving to the right. Hence, a meta-agent i should succeed by both adapting to differently initialized teammates with varying expertise in moving the opposite direction, and guiding j's learning process to coordinate the eventual right movement.
Our results are displayed in Figure 5d. There are two notable observations. First, influencing peer learning does not help much in cooperative settings and Meta-MAPG performs similarly to Meta-PG. The peer learning gradient attempts to shape the future policies of other agents so that the metaagent can take advantage. In IPD, for example, the metaagent influenced j to be cooperative in the future such that the meta-agent can act with a high probability of the defect action and receive higher returns. However, in cooperative settings, due to the joint reward, j is already changing its policies in order to benefit the meta-agent, resulting in a less significant effect with respect to the peer learning gradient. Second, Meta-PG and Meta-MAPG outperform the other approaches of LOLA-DiCE and REINFORCE, achieving higher rewards when interacting with a new teammate.

Conclusion
In this paper, we have introduced Meta-MAPG, a metalearning algorithm that can adapt quickly to non-stationarity in the policies of other agents in a shared environment. The key idea underlying our proposed meta-optimization is to directly model both an agent's own learning process and the non-stationary policy dynamics of other agents. We evaluated our method on several multiagent benchmarks and showed that Meta-MAPG is able to adapt more efficiently than previous state of the art approaches. We hope that our work can help provide the community with a theoretical foundation to build off for addressing the inherent nonstationarity of MARL in a principled manner.

A. Derivation of Meta-Multiagent Policy Gradient Theorem
Theorem 1. (Meta-Multiagent Policy Gradient Theorem) For any stochastic game M n , the gradient of the meta-value function for agent i at state s 0 with respect to current policy parameters φ i 0 evolving in the environment along with other peer agents using initial parameters φ −i 0 is: Proof. We begin our derivation from the meta-value function defined in Equation (2) and expand it with the state-action value and joint actions, assuming the conditional independence between agents' actions (Wen et al., 2019): where Q i φ +1 (s 0 , a 0 ) is the state-action value under the joint policy with parameters φ +1 at state s 0 with joint action a 0 .
In Equation (6), we note that both φ i 1: and φ −i 1: depend on φ i 0 . Considering the joint update from φ 0 to φ 1 , for simplicity, we can write the gradients in the inner-loop (see Equation (3)) based on the multiagent stochastic policy gradient theorem (Wei et al., 2018): where ρ φ0 denotes the stationary distribution under the joint policy with parameters φ 0 . Importantly, the inner-loop gradients for an agent i and its peers are a function of φ i 0 . Hence, the updated joint policy parameter φ 1 depends on φ i 0 . Following Equation (7), the successive inner-loop optimization until φ +1 results in dependencies between φ i 0 and φ i

1: +1
and between φ i 0 and φ −i 1: +1 (see Figure 1b). Having identified which terms are dependent on φ i 0 , we continue from Equation (6) and derive the gradient of the meta-value function with respect to φ i 0 by applying the product rule: We first focus on the derivative of the trajectories τ φ 0: in Term A: where the probability of collecting a trajectory under the joint policy with parameters φ is given by: Using Equation (10) and the log-derivative trick, Equation (9) can be further expressed as: where the summations of the log-terms, such as ∇ φ i 0 log π(τ φ |φ i )+log π(τ φ |φ −i ) are inherently included due to the sequential dependencies between φ i 0 and φ 1: . We use the result of Equation (11) and organize terms to arrive at the following expression for Term A in Equation (8): Coming back to Term B-D in Equation (8), repeatedly unrolling the derivative of the Q-function ∇ φ i 0 Q i φ +1 (s 0 , a 0 ) by following Sutton & Barto (1998) yields: which adds the consideration of future joint policy φ +1 to Equation (12). Finally, we summarize Equations (12) and (13) together and express in expectations:

B. Derivation of Meta-Policy Gradient Theorem
Remark 1. Meta-PG can be considered as a special case of Meta-MAPG when assuming that other agents' learning in the environment is independent of the meta-agent's behavior.
Proof. The framework by Al-Shedivat et al. (2018) makes the implicit assumption that there exist no sequential dependencies between the future parameters of other agents φ −i 1:L and φ i 0 . This assumption implies that the peers' policy updates in Equation (7) are not a function of a meta-agent's policy. As a result, the gradients of the peers' log-terms with respect to φ i 0 in Appendix A, such as ∇ φ i 0 log π(τ φ |φ −i ) , become zero. Specifically, Term A in Equation (8) simplifies to: Similarly, Term B-D in Equation (8) become: Finally, summarizing Equations (14) and (15) together, and expressing in expectations results in Meta-PG: Own Learning .

C. Stateless Zero-Sum Game Details
Derivation of Meta-MAPG. In the stateless zero-sum game, a meta-agent i and an opponent j maximize simple value We note that this domain has the episode horizon H of 1 with a deterministic and continuous action space, where the action is equivalent to the policy parameter: a i = φ i and a j = φ j . Because there are no stochastic factors in this domain, the meta-value function defined in Equation (2) can be simplified without the expectations: Assuming the maximum chain length L of 1 for clarity, the inner-loop updates from φ 0 to φ 1 are: where α is the inner-loop learning rate. Then, the meta-multiagent policy gradient can be directly computed without using the log-derivative trick: During meta-training, the initial policy parameter φ i 0 will be updated with the outer-loop learning rate β: Derivation of Meta-PG. For Meta-PG , the framework assumes that there is no dependency between φ i 0 and φ j 1 . Thus, the term ∇ φ i 0 φ j 1 in Equation (18) becomes zero, resulting in the meta-update of: Hyperparameter. We used the following hyperparameters: 1) randomly sampled initial opponent policy parameter from −1 to 1 (i.e., p(φ −i 0 ) = [−1, 1]), 2) α = 0.75, and 3) β = 0.01.

E.1. Network Structure
Our neural networks for the policy and value function consist of a fully-connected input layer with 64 units followed by a single-layer LSTM with 64 units and a fully-connected output layer. We reset the LSTM states to zeros at the beginning of trajectories and retain them until the end of episodes. The LSTM policy outputs a probability for the categorical distribution in the iterated games (i.e., IPD, RPS). For the 2-Agent HalfCheetah domain, the policy outputs a mean and variance for the Gaussian distribution. We empirically observe that no parameter sharing between the policy and value network results in more stable learning than sharing the network parameters.

E.2. Optimization
We detail additional important notes about our implementation: • We apply the linear feature baseline (Duan et al., 2016a) and generalized advantage estimation (GAE) (Schulman et al., 2016) during the inner-loop and outer-loop optimization, respectively, to reduce the variance in the policy gradient.
• We use DiCE (Foerster et al., 2018c) to compute the peer learning gradient efficiently. Specifically, we apply DiCE during the inner-loop optimization and save the sequential dependencies between φ i 0 and φ −i 1:L in a computation graph. Because the computation graph has the sequential dependencies, we can compute the peer learning gradient by the backpropagation of the meta-value function via the automatic-differentiation toolbox.
• Learning from diverse peers can potentially cause conflicting gradients and unstable learning. In IPD, for instance, a strategy to adapt against cooperating peers can be completely opposite to the adaptation strategy against defecting peers, resulting in conflicting gradients. To address this potential issue, we use the projecting conflicting gradients (PCGrad) (Yu et al., 2020) during the outer-loop optimization. We also have tested the baseline methods with PCGrad.
• We use a distributed training to speed up the meta-optimization. Each thread interacts with a Markov chain of policies until the chain horizon and then computes the meta-optimization gradients using Equation (4). Then, similar to Mnih et al. (2016), each thread asynchronously updates the shared meta-agent's policy and value network parameters.

F. Additional Baseline Details
We train all adaptation methods based on a meta-training set until convergence. We then measure the adaptation performance on a meta-testing set using the best-learned policy determined by a meta-validation set.

F.1. Meta-PG
We have improved the Meta-PG baseline itself beyond its implementation in the original work  to further isolate the importance of the peer learning gradient term. Specifically, compared to Al-Shedivat et al. (2018), we make the following theoretical contributions to build on: 1) Underlying problem statement: Al-Shedivat et al. (2018) bases their problem formulation off that of multi-task / continual single-agent RL. In contrast, ours is based on a general stochastic game between n agents (Shapley, 1953).
2) A Markov chain of joint policies: Al-Shedivat et al. (2018) treats an evolving peer agent as an external factor, resulting in the absence of the sequential dependencies between a meta-agent's current policy and the peer agents' future policies in the Markov chain. However, our important insight is that the sequential dependencies exist in general multiagent settings as the peer agents are also learning agents based on trajectories by interacting with a meta-agent (see Figure 1b).
3) Meta-objective: The meta-objective defined in Al-Shedivat et al. (2018) is based on single-agent settings. In contrast, our meta-objective is based on general multiagent settings (see Equations (2) and (3)). 4) Meta-optimization gradient: Compared to Al-Shedivat et al. (2018), our meta-optimization gradient inherently includes the additional term of the peer learning gradient that considers how an agent can directly influence peer's learning. 5) Importance sampling: Compared to Al-Shedivat et al. (2018), we avoid using the importance sampling during metatesting by modifying the meta-value function. Specifically, the framework uses a meta-value function on a pair consecutive joint policies, denoted V i φ : +1 (s 0 , φ i 0 ), which assumes initializing every φ i from φ i 0 . However, as noted in Al-Shedivat et al. (2018), this assumption requires interacting with the same peers multiple times and is often impossible during meta-testing.
To address this issue, the framework uses the importance sampling correction during meta-testing. However, the correction generally suffers from high variance (Wang et al., 2016b). As such, we effectively avoid using the correction by initializing from φ i 0 only once at the beginning of Markov chains for both meta-training and meta-testing.

F.2. LOLA-DiCE
We used an open-source PyTorch implementation for LOLA-DiCE: https://github.com/alexis-jacq/LOLA DiCE. We make minor changes to the code, such as adding the LSTM policy and value function.
G. Additional Experiment Details G.1. IPD We choose to represent the peer agent j's policy as a tabular representation to effectively construct the population of initial personas p(φ −i 0 ) for the meta-learning setup. Specifically, the tabular policy has a dimension of 5 that corresponds to the number of states in IPD. Then, we randomly sample a probability between 0.5 and 1.0 and a probability between 0 and 0.5 at each state to construct the cooperating and defecting population, respectively. As such, the tabular representation enables us to sample as many as personas but also controllable distribution p(φ −i 0 ) by merely adjusting the probability range. We sample a total of 480 initial personas, including cooperating personas and defecting personas, and split them into 400 for meta-training, 40 for meta-validation, and 40 for meta-testing. Figure 7a and Figure 7b visualize in and out of distribution, respectively, where we used the principal component analysis (PCA) with two components.
(a) (b) Figure 7. (a) and (b) Visualization of j's initial policy for in distribution and out of distribution meta-testing, respectively, where the out of distribution split has a smaller overlap between the policies used for meta-training/validation and those used for meta-testing.

G.2. RPS
In RPS, we follow the same meta-learning setup as in IPD, except we sample a total of 720 initial opponent personas, including rock, paper, and scissors personas, and split them into 600 for meta-training, 60 for meta-validation, and 60 for meta-testing. Additionally, because RPS has three possible actions, we sample a rock preference probability between 1/3 and 1 for building the rock persona population, where the rock probability is larger than the other two action probabilities. We follow the same procedure for constructing the paper and scissors persona population. We used an open source implementation for multiagent-MuJoCo benchmark: https://github.com/schroederdewitt/multiagent mujoco. Agents in our experiments receive state observations that include information about all the joints. For the metalearning setup, we pre-train a teammate j with an LSTM policy that has varying expertise in moving to the left direction. Specifically, we train the teammate up to 500 train iterations and save a checkpoint at each iteration. Intuitively, as the number of train iteration increases, the teammate gains more expertise. We then use the checkpoints from 0 to 300 iterations as the meta-train/val (randomly split them into 275 for meta-training and 25 for meta-validation) and from 475 and 500 iterations as the meta-test distribution (see Figure 8). We construct the distribution with the gap to ensure that the meta-testing distribution has a sufficient difference to the meta-train/val so that we can test the generalization of our approach. As in IPD and RPS, the teammate j updates its policy based on the policy gradient with the linear feature baseline.

H. Analysis on Joint Policy Dynamics
H.1. IPD Figure 9. Action probability dynamics with Meta-PG in IPD with a cooperating persona peer

I. Hyperparameter Details
We report our hyperparameter values that we used for each of the methods in our experiments: