# Unified Policy Optimization
for Continuous-action Reinforcement Learning
in Non-stationary Tasks and Games

Rong-Jun Qin National Key Laboratory for Novel Software Technology, Nanjing
University, China  Polixir.ai  Fan-Ming Luo National Key Laboratory for Novel
Software Technology, Nanjing University, China  Polixir.ai  Hong Qian School
of Computer Science and Technology, East China Normal University, China  Yang
Yu† National Key Laboratory for Novel Software Technology, Nanjing University,
China  Polixir.ai

###### Abstract

This paper addresses policy learning in non-stationary environments and games
with continuous actions. Rather than the classical reward maximization
mechanism, inspired by the ideas of follow-the-regularized-leader (FTRL) and
mirror descent (MD) update, we propose a no-regret style reinforcement
learning algorithm PORL for continuous action tasks. We prove that PORL has a
_last-iterate_ convergence guarantee, which is important for adversarial and
cooperative games. Empirical studies show that, in stationary environments
such as MuJoCo locomotion controlling tasks, PORL performs equally well as, if
not better than, the soft actor-critic (SAC) algorithm; in non-stationary
environments including dynamical environments, adversarial training, and
competitive games, PORL is superior to SAC in both a better final policy
performance and a more stable training process.

†††: Corresponding author.

## Introduction

Reinforcement learning (RL) (Sutton and Barto, 2018) as a policy optimization
tool has endowed many systems with a superhuman performance (Mnih et al.,
2015). These environments for training an RL agent are often stationary, i.e.,
the transition and reward function is fixed. Thus, the objective of policy
optimization is simply to maximize the episodic reward. However, the
transition function of learning environments may constantly change over time.
Such non-stationary environments include dynamical scenarios from the real
world, adversarial training scenarios (e.g., GAN (Goodfellow et al., 2014),
GAIL (Ho and Ermon, 2016)), and games. The nonstationarity in adversarial
training and games is not induced by the change of the environment itself but
is mainly caused by the changing policies of adversaries and opponents (or
teammates in the cooperative multi-agent systems). Consequently, RL algorithms
that are tailored to stationary environments can easily fluctuate or even
diverge in non-stationary environments. From some practical observations, the
learning process of RL algorithms may also fluctuate in stationary
environments, possibly due to the multiple near-optimal solutions. Maximum
entropy is a popular technique to guarantee that the soft optimal solution is
unique and close to the original solution. One of the representative maximum
entropy algorithms SAC (Haarnoja et al., 2018a), is shown to be very stable
across many continuous control tasks on MuJoCo (Todorov et al., 2012).
Nevertheless, a reward maximization algorithm like SAC does not necessarily
converge in non-stationary environments or adversarial training in theory. In
these domains, techniques for stabilizing the training and guaranteeing the
convergence are expected, such as averaging the historical policies as done in
NFSP (Heinrich and Silver, 2016). Besides, population-based techniques from
empirical game theory (Wellman, 2006) have been employed in training GAN (Ge
et al., 2018; Aung et al., 2021) to achieve a better convergence property.

On the contrary, online learning provides techniques for learning against non-
stationary distributions, which are sourced from the no-regret learning (also
Hannan consistency) principle (Cesa-Bianchi and Lugosi, 2006). Intuitively,
the no-regret principle minimizes the cumulative regret iteratively, and the
learning algorithm will remedy current policy based on past plays or
historical policies and thus can adapt to the non-stationary environment.
Online learning often assumes the decision space is finite, e.g., the policy
is a probability distribution over the discrete action space, which is a
probability vector. While in continuous action space, the policy is a
probability density function, thus the solution is a functional which can be
viewed as an infinite dimensional vector. A fundamental change is that the
convex property with respect to the action, which is a key to the proof of the
no-regret learning, may not generally hold with functionals. Besides, we
noticed that the convergence of online learning is often established for the
average policy, while the average of historical policies is non-trivial for
neural network policies, thus we resort to the last-iterate convergence. In
the experiments, we did observe the learning of average policy in NFSP can be
less efficient.

This work is then motivated by the celebrated no-regret learning framework,
follow-the-regularized-leader (FTRL). Employing the FTRL framework with the
entropy regularizer on the regularized MDP, we derive a policy update rule
tailored for the continuous action space. It can also be applied in discrete
action space seamlessly. In continuous action space, the proposed method has
the last-iterate convergence that converges to the soft optimal policy in
single-player tasks and the quantal response equilibrium (McKelvey and
Palfrey, 1995) in two-player tasks, under some mild assumptions. The
experiments on stationary MuJoCo environments with continuous action space are
competitive with the state-of-the-art model-free algorithm, SAC. While in the
non-stationary environments and adversarial training, the experimental results
suggest the proposed method can achieve more robust performance and a stable
learning process. Finally, in two-player competitive games, the proposed
method achieves higher expected returns when pitting against SAC and NFSP, and
is more robust against the exploiter.

## Preliminaries

Consider a stochastic game (Markov game) $G$ with a set $N$ of $n$ players
with finite horizon $H$. $n\in\\{1,2\\}$ in this work and it reduces to
single-agent MDP when $n=1$. Each player $i$ has a state space $S_{i}$, an
action space $A_{i}=A(S_{i})$ and a reward function $r_{i}:S\times
A_{1}\times\cdots\times A_{n}\rightarrow\mathbb{R}$, which is in the range
$[-R_{\max},R_{\max}]$. If the action space is discrete, we assume that the
cardinality of the action space for each player $i$ is the same, i.e.,
$|A_{i}|=d$. When the action space is continuous, it is assumed to be compact.
The transition function $P(s^{\prime}|s,\mathbf{a})$ transits from $s$ to
$s^{\prime}$ after all the agents take the joint action $\mathbf{a}$ (also $a$
for simplicity). We denote
$\mathbf{\pi}=(\mathbf{\pi}_{1},\cdots,\mathbf{\pi}_{n})$ as the joint policy.
Let $-i$ denote the players except $i$. For player $i$, the state value
function is defined as
$V_{i}^{\pi}(s)=\mathbf{E}_{(a_{i},a_{-i})\sim\pi}[\sum_{t=0}\gamma^{t}r_{i}(s_{t},a_{t},{a}_{-i})|s_{t}=s]$
and state-action value function defines as
$Q_{i}^{\pi}(s,a_{i})=\mathbf{E}_{(a_{i},a_{-i})\sim\pi}[\sum_{t=0}\gamma^{t}r_{i}(s_{t},a_{i,t},{a}_{-i})|s_{t}=s,a_{i,t}=a_{i}]$,
where $\gamma\in[0,1)$ is the discount factor. The index $i$ of the player
will be omitted in either $V_{i}$ or $\pi_{i}$ when it is clear. With function
approximations, the solution concept of a stochastic game often shifts to the
$\epsilon$-approximate Nash equilibrium ($\epsilon$-NE). For some
$\epsilon\geq 0$, a joint policy $\pi$ is $\epsilon$-NE, if $\forall
i,\max_{\pi_{i}^{\prime}}V_{i}(\pi_{i}^{\prime},\pi_{-i})-V_{i}(\pi)\leq\epsilon$.

While in an online learning problem, the agent makes decisions based on the
historical plays and the observed utility. The online learning algorithm
minimizes the regret by repeatedly playing with the opponent, thus online
learning is naturally formulated by repeated games. The general setting of
online learning mainly tackles single-state case (akin to the normal-form
games) with finite action space, thus the utility function which is akin to
the $Q$ function for player $i$ is denoted as $u_{i}:A_{1}\times\cdots\times
A_{n}\rightarrow\mathbb{R}$. The cumulative regret after $T$ rounds for the
player $i$ is defined as

$R_{i}(a_{i})=\sum_{t=1}^{T}u_{i}(a_{i},a_{-i,t})-u_{i}(a_{i,t},a_{-i,t}).$

The cumulative regret (of action $a_{i}$) measures the difference between the
cumulative utility of the constant action (or policy) and actual plays. If the
regret of a learning algorithm satisfies
$Pr[\frac{1}{T}\lim_{T\rightarrow\infty}\max_{a_{i}\in A_{i}}R_{i}(a_{i})\leq
0]=1$ no matter how the opponents play, then this algorithm is said to be no-
regret (or Hannan consistency (Hannan, 1957)). Conversely, a no-regret
learning algorithm can approximate the optimal policy when pitting against a
fixed opponent. Besides, if the average regret satisfies
$\frac{R_{i}}{T}\leq\epsilon$ in two-player zero-sum games for all players,
then the empirical play of the players converges to a $2\epsilon$-NE. Note the
empirical play is equivalent to an average policy as
$\frac{1}{T}\sum_{t=1}^{T}a_{i,t}$, thus no-regret learning inherently
establishes the convergence of the average policy.

Other notations. In a compact space $A$, let
$\int_{\mathrm{d}\mathbf{a}}f(\mathbf{a})=\int_{\mathbf{a}\in
A}f(\mathbf{a})\mathrm{d}\mathbf{\mu(a)}$ for short, where $\mu$ is the
Lebesgue measure and $\int{\mathrm{d}\mathbf{a}}=\text{vol}(A)$ is the volume
of the compact space $A$. We will use $\mathrm{d}a$ for simplicity if there is
no ambiguity. The inner product of two functions $f,g$ is defined as $\langle
f,g\rangle=\int_{\mathrm{d}a}f(a)g(a)$. If $f,g$ are vectors, then $\langle
f,g\rangle$ is the inner product of vectors. In the following,
$\|f\|_{p}=(\int_{\mathrm{d}a}|f(a)|^{p})^{\frac{1}{p}}$ is the $L_{p}$ norm
of a function $f$. By default, $\|f\|$ is the $L_{2}$ norm. The (differential)
entropy of a density function $p$ is $\mathcal{H}(p)=-\int_{a}p(a)\log
p(a)\mathrm{d}a$ and Kullback-Leibler divergence
$KL(p,q)=\int_{a}p(a)\log\frac{p(a)}{q(a)}\mathrm{d}a$.

## Related Work

### Online learning, optimization and mirror descent

The notion of no-regret can trace back to the seminal work (Hannan, 1957) for
two-player games. Because of the close relationship between the no-regret
property and Nash equilibrium (NE) in two-player zero-sum games or coarse
correlated equilibrium in general-sum games, techniques from online learning
(or no-regret learning) are also widely used as tools for learning in games.
For example, regret matching (RM) (Hart and Mas-Colell, 2000) is a simple no-
regret learning algorithm with a $O(\sqrt{T})$ worst-case regret, which later
becomes the most widely used regret minimization component to solve large
extensive-form games like Texas Hold’em (Zinkevich et al., 2007; Lanctot et
al., 2009). The follow-the-leader framework (Kalai and Vempala, 2005), most
notably the regularized leader, captures many of the no-regret algorithms.
Hedge (also multiplicative weights update, MWU) can be instantiated with the
entropy regularization under the FTRL framework. An interesting result of
NeuRD (Hennes et al., 2020) reveals Hedge can also be recovered from the
perspective of replicator dynamics. A faster convergence than $O(\sqrt{T})$
can be obtained with the predictive or optimistic version of FTRL (OFTRL)
(Syrgkanis et al., 2015; Chen and Peng, 2020) for the average policy. Besides,
OFTRL can also prove to have the last-iterate convergence (Daskalakis and
Panageas, 2019) with different techniques. A recent work (Pérolat et al.,
2021) investigates the FTRL dynamics and shows that the policy-independent
reward can not lead to convergence for the last-iterate policy if the
equilibrium is a fully mixed strategy. Thus, the authors transform the
original reward function to a policy-dependent one by adding a regularization
term and then prove the convergence for the last-iterate policy. Another line
of work follows the online optimization (Hazan, 2016), especially for linear
or convex optimization. For two-player zero-sum games, the perturbed
formulation from the perspective of online optimization is

$\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}f(x,y)+\eta_{1}h_{1}(x)-\eta_{2}h_{2}(y),$
(1)

where $h_{1},h_{2}$ are usually strongly-convex functions. When $f$ satisfied
the zero-sum property and $\eta_{1}=\eta_{2}=0$, then the solution of Eq.(1)
is a NE. If $f(x,\cdot)$ is convex and $f(\cdot,y)$ is concave, the above
problem can be solved by gradient descent ascent (GDA) with adaptive stepsize.
Mirror descent (MD) can be viewed as a general-form regularized variant of
vanilla GDA to solve (1), where the policy update in iteration $t$ is
regularized with a Bregman divergence term
$B_{\phi}(z,z_{t})=\phi(z)-\phi(z_{t})-\langle\nabla\phi(z_{t}),z-z_{t}\rangle$
with $z_{t}=(x_{t},y_{t})$. MD can update with a fixed step size and often
results in faster or last-iterate convergence (Cen et al., 2021; Lee et al.,
2021; Cai et al., 2022).

Online learning and online optimization share many similarities and sometimes
are equivalent (Waugh and Bagnell, 2015). For instance, RM and RM+ can result
from running FTRL and online MD respectively (Farina et al., 2021). With the
choice of the distance function in Bregman divergence to be $\phi(x)=\sum
x\log x$ or choosing the entropy regularizer in FTRL, Hedge/MWU can be
obtained. Recent work (Zhang et al., 2022) proposes a unified framework for
stochastic games under OFTRL, and another concurrent work MMD (Sokota et al.,
2022) proposes a unified algorithm based on MD to solve RL and two-player
zero-sum games. Although the connection between FTRL and MD is very close, MD
sometimes results in coupled learning dynamics (an implicit update form),
i.e., the player is aware of the utility function or policy of himself or even
the opponent, while FTRL often updates in uncoupled learning dynamics.
Nevertheless, FTRL and MD can both be both coupled and uncoupled, where the
uncoupled dynamics only update policy on the observed or learned utility
vector.

### Entropy regularized RL and regularizer in games

The entropy term in single-agent RL plays the role for better exploration or
to guarantee a unique solution (Haarnoja et al., 2017, 2018a; Ziebart et al.,
2008; Ho and Ermon, 2016). RAC (Yang et al., 2019) studies a general framework
for regularized MDP and analyses some properties of regularized MDP. Kullback-
Leibler (KL) divergence, which is the relative entropy, is also widely used in
RL (Schulman et al., 2015, 2017). The philosophy of KL regularization is to
avoid the large step size of the policy gradient and guarantee monotone policy
improvement. While for games, the notion of quantal response equilibrium (QRE)
(McKelvey and Palfrey, 1995) is introduced in entropy regularized normal-form
games. Smooth fictitious play (Fudenberg and Kreps, 1993) proposed a
regularized version of the fictitious play (FP) (Brown, 1951) and becomes
easier to analyse the learning dynamics. The regularization in smooth FP is a
random utility model and is well studied learning in games (Fudenberg and
Levine, 1998). More general regularization may refer to (Mertikopoulos and
Sandholm, 2016; Savas et al., 2019).

It should be noted that for stochastic games, no-regret algorithms for normal-
form games can not be readily applied. The approximate dynamic programming
(ADP) (Pérolat et al., 2015) extends value iteration in RL to stochastic
games, thus we can focus on the per state regret. Besides the theoretical
research, regret minimization techniques with deep neural networks have been
applied to facilitate the training of RL(Jin et al., 2018; Srinivasan et al.,
2018). However, to our knowledge, current regret minimization algorithms on
continuous control tasks are less competitive than state-of-the-art RL
algorithms.

## Methods

We first focus on the single state $s$ to derive the objective. Akin to QRE,
we solve the following regularized objective ($s$ is omitted) in this work:

$\displaystyle\min_{\pi_{2}}\max_{\pi_{1}}Q^{\pi_{1},\pi_{2}}+\alpha\mathcal{H}(\pi_{1})-\alpha\mathcal{H}(\pi_{2}),$
(2)

where
$Q^{\pi_{1},\pi_{2}}=\int\int\pi_{1}\pi_{2}Q(a_{1},a_{2}){\mathrm{d}a_{1}}{\mathrm{d}a_{2}}$.
Consider the game is played for multiple iterations, where both players evolve
their policies respectively. Denote

$Q^{1}_{t}(a_{1})=\int\pi_{2,t}(a_{2})Q(a_{1},a_{2})\mathrm{d}a_{2},$

and

$Q^{2}_{t}(a_{2})=\int\pi_{1,t}(a_{1})Q(a_{1},a_{2})\mathrm{d}a_{1}.$

We can perform the MD update to get $\pi_{1,t+1}$ and $\pi_{2,t+1}$ as

$\displaystyle\arg\max_{\pi_{1}}\langle\pi_{1}(a),Q^{1}_{t}(a)\rangle+\alpha\mathcal{H}(\pi_{1})-\frac{KL(\pi_{1},\pi_{1,t})}{\eta},$
(3)
$\displaystyle\arg\min_{\pi_{2}}\langle\pi_{2}(a),Q^{2}_{t}(a)\rangle-\alpha\mathcal{H}(\pi_{2})+\frac{KL(\pi_{2},\pi_{2,t})}{\eta}$
(4)

for the max player and the min player respectively, where
$Q^{i}_{t}(a)=\int_{a_{-i}}\pi_{-i,t}\cdot
Q_{t}(a_{i},a_{-i})\mathrm{d}{a_{-i}}$. Let
$F_{1}=\langle\pi_{1}(a),Q^{1}_{t}(a)\rangle+\alpha\mathcal{H}(\pi_{1})-\frac{KL(\pi_{1},\pi_{1,t})}{\eta}$
and
$F_{2}=\langle\pi_{2}(a),Q^{2}_{t}(a)\rangle-\alpha\mathcal{H}(\pi_{2})+\frac{KL(\pi_{2},\pi_{2,t})}{\eta}$.
The Eq.(4) can be converted to a maximization problem by adding a minus sign
to $F_{2}$, thus we can solve for the joint objective $F=(F_{1},-F_{2})$ and
the joint policy $\pi_{t}=(\pi_{1,t},\pi_{2,t})$. The maximum integral
functional can be solved by the Euler-Lagrange equation, and we can get

$\displaystyle\pi_{t+1}(a)$ $\displaystyle\propto\exp(\frac{\eta
Q_{t}(a)+\log\pi_{t}(a)}{\eta\alpha+1})$ (5)
$\displaystyle=\pi_{t}(a)\exp(\frac{\eta
Q_{t}(a)}{\eta\alpha+1})\exp(\frac{-\eta\alpha\log\pi_{t}(a)}{\eta\alpha+1})$
(6)
$\displaystyle\overset{\eta^{\prime}=\frac{\eta}{\eta\alpha+1}}{=}\pi_{t}(a)\exp(\eta^{\prime}Q_{t}(a))\exp(-\eta^{\prime}\alpha\log\pi_{t}(a))$
(7)

The above formulation is closely related to the FTRL, especially MWU, from the
no-regret learning perspective. The MWU algorithm updates in a simple
incremental way that only depends on the expected performance and policy from
the previous round, while other no-regret learning dynamics may depend on all
the historical expected performances and policies. Denote $\nu_{t}=Q_{t}(a)$
on a given state $s$ for simplicity. Then for the regularized objective
Eq.(2), the behavior policy $\pi_{t+1}$ on a given state $s$ in the next
iteration satisfies

$\displaystyle\pi_{t+1}(a)=\arg\max_{\pi}\int_{\mathrm{d}a}\pi(a)(\sum_{k=1}^{t}\nu_{k}-\alpha\log\pi_{k}-\frac{\log{\pi(a)}}{\eta})$
(8)

Similarly, we can derive the maximum of the above integral functional as
follows:

$\displaystyle\pi_{t+1}(a)$
$\displaystyle=\frac{\exp(\eta(\sum_{k=1}^{t}\nu_{k}-\alpha\log\pi_{t}(a)))}{\int_{\mathrm{d}a}\exp(\eta(\sum_{k=1}^{t}\nu_{k}-\alpha\log\pi_{t}(a)))}$
(9)
$\displaystyle=\frac{\pi_{t}(a)\exp(\eta(\nu_{t}-\alpha\log\pi_{t}(a)))}{\int_{\mathrm{d}a}\pi_{t}(a)\exp(\eta(\nu_{t}-\alpha\log\pi_{t}(a)))}$
(10) $\displaystyle\propto\pi_{t}(a)\exp(\eta(\nu_{t}-\alpha\log\pi_{t}(a)))$
(11)
$\displaystyle=\pi_{t}(a)\exp(\eta\nu_{t})\exp(-\eta\alpha\log\pi_{t}(a)).$
(12)

When $\alpha=0$ in Eq.(7) and Eq.(12), both equations recover standard MWU
algorithm. Otherwiese, Eq.(7) and Eq.(12) are equivalent with a rescaling of
$\eta$.

We can use Kullback-Leibler divergence to approximate $\pi_{t+1}$ (Eq.(5)) as
follows:

$\displaystyle\pi^{t+1}=\mathop{\text{argmin}}_{\pi}D_{\text{KL}}(\pi||\frac{\exp(\frac{\eta
Q_{t}(a)+\log\pi_{t}}{\eta\alpha+1})}{Z(s)}),$ (13)

where $Z(s)$ is the normalization function. Parameterizing $\pi,Q$ with
$\theta,\phi$ respectively, expanding the goal in (13) and ignoring $Z(s)$
which is a constant for $\theta$, the overall objective (multiplied by
$\frac{\eta\alpha+1}{\eta}$) becomes

$\displaystyle J(\pi_{\theta})=\mathbb{E}_{a\sim\pi_{\theta}}[$
$\displaystyle\frac{1}{\eta}(\log\pi_{\theta}(a)-\log\pi_{t}(a))-Q_{t}(s,a)+\alpha\log\pi_{\theta}(a)].$
(14)

The parameterized objective for Eq.(12) (multiplied by $\frac{1}{\eta}$) can
be obtained by replacing the $\alpha\log\pi_{\theta}$ in Eq.(14) with
$\alpha\log\pi_{t}$. Eq.(14) can be viewed as an eager update of the
regularized $Q$ function. When the action space is discrete, we can enumerate
every valid action when calculating the inner expectation. If the action space
is continuous, it is common to use the reparameterization trick which results
in lower variance estimation. Thus, the action $a$ is transformed with the
output of the policy network from a noisy vector $\epsilon$, i.e.,

$a=f_{\psi}(\epsilon;s),$

where $\epsilon$ is usually sampled from a fixed Gaussian distribution. The
objective resembles the form of SAC (Haarnoja et al., 2018a) in some aspects,
except that the objective in Eq.(14) contains an extra
$\log\pi_{\theta}-\log\pi_{t}$, which is an estimation of KL. The objective
Eq.(14) more naturally extends SAC with a fixed $\alpha$ and the KL
regularizer.

When both players follow MD to act, we have the following theorem

######  Theorem 1.

When the action space is compact and if the two players follow Eq. (3), Eq.
(4) respectively and $\forall a,\pi,0\leq\pi(a)<\infty$, with the choice of
the $\eta\leq\min\\{\frac{1}{b^{2}},\frac{\alpha^{2}}{b^{2}L^{4}}\\}$, the
following relations holds:

$KL(\pi^{\star},\pi_{t})\leq(\frac{1}{1+\eta\alpha})^{t}KL(\pi^{\star},\pi_{0}),$
(15)

where $\pi^{\star}$ is the solution to Eq.(2), $\pi_{t}=(\pi_{1,t},\pi_{2,t})$
and $L=\frac{R_{\text{max}}}{1-\gamma}$.

Theorem 1 discloses that $\alpha>0$ is necessary for the last-iterate
convergence. A non-zero $\alpha$ also guarantees that the $\pi^{\star}$ is a
Boltzmann policy that is bounded, thus $KL(\pi^{\star},\pi_{0})$ can be
bounded if $\pi_{0}$ is the uniform distribution. This implies the convergence
to a QRE in two-player zero-sum games. On the other hand, $\alpha$ should be
small to make the regularized optimal solution close to the original. $\eta$
should be very small to strictly match the condition, however, a too small
$\eta$ will incur a very large $1/\eta$, which can be numerically unstable,
thus we simply let $1/\eta$ much larger than $\alpha$. Here, both $\alpha$ and
$\eta$ are fixed. A time-vanishing $\alpha$ can also be adopted as done in
(Pérolat et al., 2021; Cen et al., 2021).

Note that when $\pi_{t}$ is a density function on a compact set, it turns into
solving an extremum of a functional rather than solving for the probability
vector in discrete action space. Thus, the objective function $F_{1},F_{2}$
are not necessarily concave/convex with respect to the action $a$. We need to
slightly fix some of the proof steps that are direct conclusions from the
convex and strongly convex properties. See Appendix D for the detailed proof.

Algorithm 1 Policy Optimization with Regularized Leader

1:Initialize
$t=0,\pi_{\theta}=\pi^{t}_{\theta},Q^{t}_{\phi},Q^{\text{target}}_{\bar{\phi}}$,
target network mixture coefficient $\tau$, learning rate $\alpha$ and $\beta$

2:for each iteration $t$ do

3: for $T$ rounds do

4: Sample $M$ steps with $\pi_{\theta}$ and store
$(s,a,r,s^{\prime},a^{\prime})$ and whether $s^{\prime}$ is terminal in Buffer
$B$

5: for $i=1,\cdots,K_{1}$ do $\triangleright$ Policy Evaluation

6:
$\phi\leftarrow\phi-\alpha\nabla_{\phi}\mathbb{E}_{(s,a,r,s^{\prime},a^{\prime})\sim
B}[(Q^{t}_{\phi}(s,a)-(r(s,a)+\gamma\cdot
Q^{\text{target}}_{\bar{\phi}}(s^{\prime},a^{\prime})-\alpha\log\pi_{\theta}(s^{\prime},a^{\prime})))^{2}]$

7: $\bar{\phi}^{t}\leftarrow(1-\tau)\bar{\phi}^{t}+\tau\phi^{t}$

8: for $i=1,\cdots,K_{2}$ do $\triangleright$ Policy Learning

9:
$\theta\leftarrow\theta-\beta\nabla_{\theta}\mathbb{E}_{a\sim\pi_{\theta}}[\frac{1}{\eta}(\log\pi_{\theta}(a)-\log\pi_{t}(a))-Q_{t}(s,a)+\alpha\log\pi_{\theta}(a)]$
$\triangleright$ as Eq.(14)

10: Update $Q^{t-1}\leftarrow Q^{t}_{\phi},\pi^{t-1}\leftarrow\pi_{\theta}$

11: $t\leftarrow t+1$

With approximate dynamic programming techniques (Pérolat et al., 2015), we can
move to RL and stochastic games. The learning process (named PORL) of the
joint optimization is summarized in Algorithm 1. PORL can be applied in
single-agent RL and two-player games. For single-agent RL problem, the min
player is simply omitted. In broad strokes, the proposed procedure consists of
two steps: (1) evaluating the expected value function of the behavior policy
and then (2) learning the behavior policy for the next iteration.

Figure 1: Return curves in $4$ stationary MuJoCo tasks. The curves are shaded
with standard errors. Figure 2: Return curves in $4$ non-stationary MuJoCo
tasks The curves are shaded with standard errors. For every $0.125$M training
time steps, we change the gravity of the environments. Figure 3: Return curves
in $4$ adversarial imitation learning MuJoCo tasks. We replace the policy
optimization method in GAIL with PORL and SAC to conduct these comparisons.
The curves are shaded with standard errors.

## Experiments

In this part, we compare PORL with baseline methods in stationary and non-
stationary scenarios. We first conducted the experiments in stationary MuJoCo
tasks to evaluate the data efficiency of PORL in typical RL benchmarks. Then,
we assess the robustness of PORL in three non-stationary scenarios, i.e.,
dynamical environments, adversarial training environments, and competitive
games. Each experiment is conducted with $5$ distinct random seeds unless
explicitly mentioned in the text.

Continuous MuJoCo tasks. First, we evaluate the proposed algorithm on four
stationary Gym-MuJoCo tasks. Since these environments are stationary, the KL
constraint is relaxed a little ($1/\eta=0.1,\alpha=0.2,T=1000$) in PORL. For
SAC, $\alpha$ is auto-tuned as (Haarnoja et al., 2018b).

We instantiate the policy network and the value networks by MLPs with 2 hidden
layers. The hidden units are $[256,64]$. The activation functions of the
hidden layers are leaky_relu. No activation function is added to the output
layer. The policy outputs a mean vector $\mathbf{\mu}$ and a logarithmic
standard deviation $\mathbf{\sigma}$ of a diagonal Gaussian distribution
$\mathcal{N}(\cdot\mid\mathbf{\mu},\mathbf{\sigma})$, from which an action
vector will be sampled. After squashing the action vector with tanh to make
the action falls into the valid compact action space, we will apply the
squashed action to the environment. This resembles SAC (Haarnoja et al.,
2018a) as the authors showed that squashing can stabilize the training
process. We use Adam (Kingma and Ba, 2015) as the optimizer. The learning
rates of the policy network and the value networks are $3e-4$ and $1e-3$,
respectively. Every policy is trained with $1$M environment steps.

Figure 1 shows the performance of PORL in $4$ stationary MuJoCo tasks. We can
find that PORL is much better on Ant-v2. The learning process shows few or no
sudden performance drops. The performance is competitive to SAC, a SOTA reward
maximization algorithm on the other MuJoCo domains. These results imply the
potential of PORL for tackling RL problems.

Non-stationary environments. In addition to stationary tasks, we also compare
PORL with SAC in non-stationary environments. The hyper-parameters for both
algorithms keep exactly the same. We construct $4$ dynamical MuJoCo tasks by
changing the parameters (the gravity) of the environment dynamics
periodically. Specifically, before training, we opt $8$ values,
$\\{-1,-2,-5,-10,-15,-20,-25,-30\\}$, as the candidate environment parameters,
thus each non-stationary task consists of $8$ stationary environments. For
every $0.125$M time steps, we change the gravity of the environment to one of
the candidate values. Every value is sampled without replacement during the
full training process. In Figure 2, we report the comparison of PORL and SAC
in terms of the averaged return in the $8$ environments. Both PORL and SAC
suffer from performance drops because of the non-stationarity. However, we
find that the performance drop of SAC is significantly heavier except on
Walker2d. These results reveal the robustness of PORL to the environment non-
stationarity, which is benefited from the no-regret and last-iterate
convergence properties.

Adversarial environments. We also test PORL in the scenario of adversarial
training. Specifically, we compare PORL with SAC in the framework of
adversarial imitation learning (AIL), which is a fully adversarial training
scenario. The target of AIL is to recover the expert policy from a set of
expert data. AIL learns two networks simultaneously, a policy network and a
discriminator network. The discriminator is trained to discriminate the expert
data from the fake data generated by the policy. While the policy (the
generator) learns to mimic the expert to fool the discriminator. In each task,
we first train a policy by SAC and use the policy at convergence to collect
the expert dataset. The performance of the expert data is listed in Table 1.
We use GAIL (Ho and Ermon, 2016) as the AIL algorithm. GAIL typically uses
TRPO Schulman et al. (2015) or PPO Schulman et al. (2017) as the policy
optimization methods. In order to compare the performance of PORL and SAC in
the AIL scenario, we replace the policy optimization method in GAIL with PORL
and SAC. The hyper-parameter for SAC keeps the same as stationary and non-
stationary MuJoCo tasks. Since the dynamics changes faster, we take
$\alpha=0.01$, $1/\eta=0.1$ and the gradient updates $T=10$ for adversarial
training.

Table 1: Environment return of the expert data. Ant-v2 | HalfCheetah-v2 | Hopper-v2 | Walker2d-v2
---|---|---|---
4813.04 | 10545.93 | 3557.87 | 3975.29
Table 2: Final return $\pm$ standard errors in 4 stationary MuJoCo tasks in
the adversarial imitation learning scenarios. We replace the policy
optimization method in original GAIL with PORL and SAC to make these
comparisons.

| PORL | SAC
---|---|---
Ant-v2 |  $\mathbf{4450.39}$ $\pm$ | $\mathbf{103.9}$ |  $4384.35$ $\pm$ | $96.62$
HalfCheetah-v2 |  $\mathbf{10179.53}$ $\pm$ | $\mathbf{177.93}$ |  $6575.59$ $\pm$ | $1724.85$
Hopper-v2 |  $\mathbf{3509.43}$ $\pm$ | $\mathbf{59.8}$ |  $3494.53$ $\pm$ | $54.44$
Walker2d-v2 |  $\mathbf{4790.49}$ $\pm$ | $\mathbf{36.75}$ |  $4573.75$ $\pm$ | $19.14$

We present the return curves and the final returns of the policies in Figure 3
and Table 2. The result reveals that PORL is superior to SAC in adversarial
scenarios. From Figure 3, it can be observed that as the training proceeds,
PORL achieves a more stable performance on Ant and HalfCheetah. This result
also discloses that PORL takes the advantage of the no-regret and the last-
iterate convergence property, and thus is more robust in adversarial training
scenarios.

Remarks on MuJoCo domains. We follow the same hyper-parameters of SAC for PORL
if they have exactly the same functionality. The extra hyper-parameters
$\alpha,\eta$, and $T$ are mostly decided based on the theory part and the
changing speed of the dynamics. The robustness of SAC in some of the non-
stationary MuJoCo environments and adversarial training scenarios is
intriguing. Besides, the Eq.(14) can also be implemented in an on-policy way
without changing too much, which resembles the objective of PPO as done in MMD
(Sokota et al., 2022). However, PORL extends SAC which achieves higher rewards
and has shown the potential and benefit of no-regret learning in both
stationary and non-stationary environments for continuous action domains.

Continuous action space competitive environments. Finally, we choose two
competitive scenarios from the multi-agent particle environments (MPE)
(Mordatch and Abbeel, 2017), i.e., SimplePush and SimpleAdversary. In
SimplePush, the main agent (player 2) is rewarded based on the Euclidean
distance to a landmark. The adversary (player 1) is rewarded if it is close to
the landmark, and if the agent is far from the landmark. So the adversary
learns to push the agent away from the landmark. In SimpleAdversary, there are
two landmarks, and the main agent (player 2) is rewarded based on how close
one of them is to the target landmark, but negatively rewarded if the
adversary (player 1) is close to the target landmark. The adversary is
rewarded based on how close it is to the target, but it doesn’t know which is
the target landmark. So the main agent has to learn to split up and cover all
landmarks to deceive the adversary, which is the most strategic policy among
all these agents. The original environment contains a main window of size
$[-1,1]\times[-1,1]$ and the agents are allowed to exit the window. The
landmarks and the agents are randomly spawned on the main window. We slightly
modify the original scenarios to make the two environments more competitive.
The number of agents is set as two, and they are restricted to stay in a
region $[-2,2]\times[-2,2]$. The environment terminates when one of the agents
exits the region or the time steps reach 100. These two scenarios are not
strictly two-player zero-sum games, but are fully competitive.

We compare PORL with SAC and NFSP in the competitive games. Instead of fully
independent learning, we alternate the learning player every 1000 gradient
updates (i.e., $1K$ time steps) and the total steps is $1M$. The policies and
value networks are both MLPs with 2 hidden layers, which do not share
parameters. The hidden units are $[64,64]$ on two MPE scenarios. Since the
main agent and the adversary are not symmetric, we use separate parameters for
the two players. The learning rates are $1e-3$ for both networks. We set the
policy update interval $T=10$, which better fits MPE tasks. The value of
$\alpha$ in SAC is auto-tuned, while we set the initial $\alpha_{0}=0.01$ and
slowly decay $\alpha=\min(0.999*\alpha,0.1\alpha_{0})$ every 1000 gradient
updates, and $\eta=0.1$ for PORL. We also evaluated $\alpha=0$ for PORL to
verify the necessity of a non-zero $\alpha$. We do find the PORL performs a
bit worse when $\alpha=0$ (see Appendix E for details). For NFSP, we replace
DQN by SAC as the best response for continuous action space, and anticipatory
parameter $\eta=0.2$ which is the best chosen from $\\{0.1,0.2,0.5\\}$ (see
Appendix E for the full learning curves). The buffer for the average policy is
10 times the size of the replay buffer as done in (Heinrich and Silver, 2016).
For NFSP, we evaluate the average policy. The learning curves of the best
hyper-parameters are shown in Fig.4. Both PORL and SAC converge stably, while
the average policy of NFSP is rather unstable. We then evaluate the converged
policies of both algorithms. As the two scenarios are asymmetric, we use a
cross-play evaluation protocol. We let player 1 trained by algorithm 1 (Alg1)
pit against player 2 trained by algorithm 2 (Alg2) for 200 episodes and record
the returns of each player, and repeat the above process by exchanging the
players trained from the algorithms. Then the total returns obtained by the
same algorithm is the final score. We report the final results in Table.3.
PORL can obtain higher scores when pitting against either SAC or NFSP in both
scenarios. We notice that the main agent of SimpleAdversary trained by PORL
has a larger advantage over the main agents of SAC and NFSP. This reveals that
PORL is more likely to deceive the adversaries than SAC and NFSP in
competitive games. Detailed scores can be found in Appendix F.

Figure 4: Return curves in $2$ MPE tasks. The returns for player 1 (the
adversary) and 2 (the main agent) are plotted respectively. The curves are
shaded with standard errors. Table 3: Cross-play returns on MPE environments.
Push and Adv stand for SimplePush and SimpleAdversary tasks respectively. In
each task, the score $S_{\text{row},\text{col}}$ denotes the total returns of
$\text{Alg}_{\text{row}}$ pits against $\text{Alg}_{\text{col}}$. If
$S_{\text{row},\text{col}}>S_{\text{col},\text{row}}$, then
$\text{Alg}_{\text{row}}$ is better than $\text{Alg}_{\text{col}}$.

Task |  | PORL | NFSP | SAC
---|---|---|---|---
Push | PORL | - | $12.36\pm 4.85$ | $-3.30\pm 0.97$
NFSP | $-49.35\pm 9.75$ | - | $-50.11\pm 10.92$
SAC | $-6.06\pm 1.67$ | $11.64\pm 3.89$ | -
Adv | PORL | - | $12.86\pm 8.57$ | $5.15\pm 1.29$
NFSP | $-6.33\pm 6.73$ | - | $-3.42\pm 8.91$
SAC | $0.72\pm 2.72$ | $11.74\pm 9.38$ | -

Figure 5: Approximate exploitability learning curves in $2$ multi-agent
particle environment competitive tasks. The exploitability of player 1 and 2
are plotted respectively. A lower average exploitability means the
corresponding algorithm is more robust against exploiters.

We also invoke a SAC as the best response oracle to get the approximate
exploitability. However, we observed SAC fails to exploit the trained agents
well, especially the main agent on SimplePush. Nevertheless, the learning
curves of the exploiter in Fig.5 demonstrate that PORL is harder to be
exploited. We argue the slow convergence of NFSP is due to the mixed learning
of the best response oracle and the average policy. In NFSP, the main behavior
policy is the average policy (with probability $1-\eta$, where $\eta$ should
be small). Following the practical observations in (Fujimoto et al., 2019), if
the behavior policy and the learning policy are very different, off-policy RL
algorithms cannot efficiently learn the optimal policy, thus samples for the
average policy are not from the real BR.

Ablation studies. We ablate two hyper-parameters in PORL, i.e., the gradient
steps for each iteration ($T$) and $\eta$. We evaluate different hyper-
parameters in non-stationary HalfCheetah-v2. We first fix $\eta$ and vary $T$
to different values. We report the final return of the policy trained with
$1$M environment interactions in Table 4 in Appendix E. Each experiment is
repeated with $3$ seeds. We can find the performance will benefit from a
smaller $T$. The smallest $T$ ($10$) obtains the highest final return. This
result originates from the fact that $\log\pi_{\theta}(a)-\log\pi_{t}(a)$ in
Eq.(14) will be large when $\pi_{t}(a)$ is very old. A larger discrepancy
could introduce instability in sample-based policy learning. We then fix $T$
and vary $\eta$. The result is summarized in Table 5 in Appendix E. The
experiments are also repeated with $3$ seeds. We find that PORL is relatively
robust to $\eta$, and $1/\eta=0.1$ performs well in all the experiments.

## Conclusion

In this paper, we propose a practical no-regret style RL algorithm, PORL, to
solve stationary MDP, dynamic MDP, and adversarial training, in continuous
action space. We show PORL can extend to handle continuous action space and
has the last-iterate convergence property. The experimental results
demonstrate the proposed PORL is superior (at least competitive) to SAC and
more robust in stationary, dynamical environments and adversarial training
scenarios. PORL is superior to SAC and NFSP in competitive games.

We currently used a small and fixed $\alpha$ for the regularized MDP which
only converges to the QRE. In the future, we will investigate the vanishing
version. Besides, the regularization term is limited to the entropy, which has
some nice properties in implementation. Other regularizers may also be
available.

## References

  * Aung et al. [2021] A. P. P. Aung, X. Wang, R. Yu, B. An, S. Jayavelu, and X. Li.  DO-GAN: A double oracle framework for generative adversarial networks.  _CoRR_ , 2021.
  * Brown [1951] G. W. Brown.  Iterative solutions of games by fictitious play.  In _Activity Analysis of Production and Allocation_ , Wiley, NY, 1951\.
  * Cai et al. [2022] Y. Cai, A. Oikonomou, and W. Zheng.  Tight last-iterate convergence of the extragradient method for constrained monotone variational inequalities.  _CoRR_ , abs/2204.09228, 2022.
  * Cen et al. [2021] S. Cen, Y. Wei, and Y. Chi.  Fast policy extragradient methods for competitive games with entropy regularization.  In _Advances in Neural Information Processing Systems 34_ , pages 27952–27964, virtual, 2021.
  * Cesa-Bianchi and Lugosi [2006] N. Cesa-Bianchi and G. Lugosi.  _Prediction, learning, and games_.  Cambridge University Press, 2006.
  * Chen and Peng [2020] X. Chen and B. Peng.  Hedging in games: Faster convergence of external and swap regrets.  In _Advances in Neural Information Processing Systems 33_ , virtual, 2020.
  * Daskalakis and Panageas [2019] C. Daskalakis and I. Panageas.  Last-iterate convergence: Zero-sum games and constrained min-max optimization.  In _10th Innovations in Theoretical Computer Science Conference_ , San Diego, California, 2019.
  * Farina et al. [2021] G. Farina, C. Kroer, and T. Sandholm.  Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent.  In _Thirty-Fifth AAAI Conference on Artificial Intelligence_ , Virtual Event, 2021. AAAI Press.
  * Fudenberg and Kreps [1993] D. Fudenberg and D. M. Kreps.  Learning mixed equilibria.  _Games and Economic Behavior_ , 5(3):320–367, 1993.
  * Fudenberg and Levine [1998] D. Fudenberg and D. K. Levine.  _The Theory of Learning in Games_.  MIT Press, 1998.
  * Fujimoto et al. [2019] S. Fujimoto, D. Meger, and D. Precup.  Off-policy deep reinforcement learning without exploration.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2052–2062, Long Beach, California, 2019.
  * Ge et al. [2018] H. Ge, Y. Xia, X. Chen, R. Berry, and Y. Wu.  Fictitious GAN: training gans with historical models.  In _Computer Vision 15th European Conference_ , Munich, Germany, 2018\.
  * Goodfellow et al. [2014] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. C. Courville, and Y. Bengio.  Generative adversarial nets.  In _Advances in Neural Information Processing Systems 27_ , Montreal, Quebec, Canada, 2014.
  * Haarnoja et al. [2017] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine.  Reinforcement learning with deep energy-based policies.  In _Proceedings of the 34th International Conference on Machine Learning_ , Sydney, NSW, Australia, 2017. PMLR.
  * Haarnoja et al. [2018a] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _Proceedings of the 35th International Conference on Machine Learning_ , Stockholmsmässan, Stockholm, Sweden, 2018a. PMLR.
  * Haarnoja et al. [2018b] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel, and S. Levine.  Soft actor-critic algorithms and applications, 2018b.  URL http://arxiv.org/abs/1812.05905.
  * Hannan [1957] J. Hannan.  Approximation to bayes risk in repeated play.  _Contributions to the Theory of Games_ , 3:97–139, 1957\.
  * Hart and Mas-Colell [2000] S. Hart and A. Mas-Colell.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(7540):1127–1150, 2000.
  * Hazan [2016] E. Hazan.  Introduction to online convex optimization.  _Foundations and Trends in Optimization_ , 2(3-4):157–325, 2016.
  * Heinrich and Silver [2016] J. Heinrich and D. Silver.  Deep reinforcement learning from self-play in imperfect-information games, 2016.
  * Hennes et al. [2020] D. Hennes, D. Morrill, S. Omidshafiei, R. Munos, J. Pérolat, M. Lanctot, A. Gruslys, J. Lespiau, P. Parmas, E. A. Duéñez-Guzmán, and K. Tuyls.  Neural replicator dynamics: Multiagent learning via hedging policy gradients.  In _Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems_ , Auckland, New Zealand, 2020.
  * Ho and Ermon [2016] J. Ho and S. Ermon.  Generative adversarial imitation learning.  In _Advances in Neural Information Processing Systems 29_ , Barcelona, Spain, 2016.
  * Jin et al. [2018] P. H. Jin, K. Keutzer, and S. Levine.  Regret minimization for partially observable deep reinforcement learning.  In _Proceedings of the 35th International Conference on Machine Learning_ , Stockholmsmässan, Stockholm, Sweden, 2018.
  * Kalai and Vempala [2005] A. T. Kalai and S. S. Vempala.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Kingma and Ba [2015] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In _Proceedings of the 3rd International Conference on Learning Representations_ , 2015.
  * Lanctot et al. [2009] M. Lanctot, K. Waugh, M. Zinkevich, and M. H. Bowling.  Monte carlo sampling for regret minimization in extensive games.  In _Advances in Neural Information Processing Systems 22_ , pages 1078–1086, Vancouver, British Columbia, Canada, 2009.
  * Lee et al. [2021] C. Lee, C. Kroer, and H. Luo.  Last-iterate convergence in extensive-form games.  In _Advances in Neural Information Processing Systems 34_ , pages 14293–14305, virtual, 2021.
  * McKelvey and Palfrey [1995] R. D. McKelvey and T. R. Palfrey.  Quantal response equilibria for normal form games.  _Games and Economic Behavior_ , 10(1):6–38, 1995\.
  * Mertikopoulos and Sandholm [2016] P. Mertikopoulos and W. H. Sandholm.  Learning in games via reinforcement and regularization.  _Mathematics of Operations Research_ , 41(4):1297–1324, 2016.
  * Mnih et al. [2015] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. A. Riedmiller, A. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Mordatch and Abbeel [2017] I. Mordatch and P. Abbeel.  Emergence of grounded compositional language in multi-agent populations, 2017.
  * Pérolat et al. [2015] J. Pérolat, B. Scherrer, B. Piot, and O. Pietquin.  Approximate dynamic programming for two-player zero-sum markov games.  In _Proceedings of the 32nd International Conference on Machine Learning_ , Lille, France, 2015. JMLR.
  * Pérolat et al. [2021] J. Pérolat, R. Munos, J. Lespiau, S. Omidshafiei, M. Rowland, P. A. Ortega, N. Burch, T. W. Anthony, D. Balduzzi, B. D. Vylder, G. Piliouras, M. Lanctot, and K. Tuyls.  From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization.  In _Proceedings of the 38th International Conference on Machine Learning_ , Virtual Event, 2021.
  * Savas et al. [2019] Y. Savas, M. Ahmadi, T. Tanaka, and U. Topcu.  Entropy-regularized stochastic games.  In _58th IEEE Conference on Decision and Control_ , pages 5955–5962, Nice, France, 2019. IEEE.
  * Schulman et al. [2015] J. Schulman, S. Levine, P. Abbeel, M. I. Jordan, and P. Moritz.  Trust region policy optimization.  In _Proceedings of the 32nd International Conference on Machine Learning_ , Lille, France, 2015. JMLR.org.
  * Schulman et al. [2017] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov.  Proximal policy optimization algorithms.  _CoRR_ , 2017.
  * Sokota et al. [2022] S. Sokota, J. Z. K. Ryan D’Orazio, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer.  A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games, 2022.
  * Srinivasan et al. [2018] S. Srinivasan, M. Lanctot, V. F. Zambaldi, J. Pérolat, K. Tuyls, R. Munos, and M. Bowling.  Actor-critic policy optimization in partially observable multiagent environments.  In _Advances in Neural Information Processing Systems 31_ , Montréal, Canada, 2018.
  * Sutton and Barto [2018] R. S. Sutton and A. G. Barto.  _Reinforcement learning: An introduction_.  MIT Press, 2018.
  * Syrgkanis et al. [2015] V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire.  Fast convergence of regularized learning in games.  In _Advances in Neural Information Processing Systems 28_ , pages 2989–2997, Montreal, Quebec, Canada, 2015.
  * Todorov et al. [2012] E. Todorov, T. Erez, and Y. Tassa.  MuJoCo: A physics engine for model-based control.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 5026–5033, Vilamoura, Algarve, Portugal, 2012.
  * Waugh and Bagnell [2015] K. Waugh and J. A. Bagnell.  A unified view of large-scale zero-sum equilibrium computation.  In _Computer Poker and Imperfect Information, Papers from the 2015 AAAI Workshop_ , Austin, Texas, 2015. AAAI Press.
  * Wellman [2006] M. P. Wellman.  Methods for empirical game-theoretic analysis.  In _Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference_ , pages 1552–1556, Boston, Massachusetts, 2006\. AAAI Press.
  * Yang et al. [2019] W. Yang, X. Li, and Z. Zhang.  A regularized approach to sparse optimal policy in reinforcement learning.  In _Advances in Neural Information Processing Systems 32_ , Vancouver, BC, Canada, 2019.
  * Zhang et al. [2022] R. Zhang, Q. Liu, H. Wang, C. Xiong, N. Li, and Y. Bai.  Policy optimization for markov games: Unified framework and faster convergence.  _CoRR_ , abs/2206.02640, 2022.
  * Ziebart et al. [2008] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey.  Maximum entropy inverse reinforcement learning.  In _Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence_ , Chicago, Illinois, 2008. AAAI Press.
  * Zinkevich et al. [2007] M. Zinkevich, M. Johanson, M. H. Bowling, and C. Piccione.  Regret minimization in games with incomplete information.  In _Advances in Neural Information Processing Systems 20_ , pages 1729–1736, Vancouver, British Columbia, Canada, 2007.

##  Appendix A Recap of Notations

In a compact space $A$, let
$\int_{\mathrm{d}\mathbf{a}}f(\mathbf{a})=\int_{\mathbf{a}\in
A}f(\mathbf{a})\mathrm{d}\mathbf{\mu(a)}$ for short, where $\mu$ is the
Lebesgue measure and $\int{\mathrm{d}\mathbf{a}}=\text{vol}(A)$ is the volume
of the compact space $A$. We will use $\mathrm{d}a$ for simplicity if there is
no ambiguity. The inner product of two functions $f,g$ is defined as $\langle
f,g\rangle=\int_{\mathrm{d}a}f(a)g(a)$. If $f,g$ are vectors, then $\langle
f,g\rangle$ is the inner product of vectors. In the following,
$\|f\|_{p}=(\int_{\mathrm{d}a}|f(a)|^{p})^{\frac{1}{p}}$ is the $L_{p}$ norm
of a function $f$. By default, $\|f\|$ is the $L_{2}$ norm. The (differential)
entropy of a density function $p$ is $\mathcal{H}(p)=-\int_{a}p(a)\log
p(a)\mathrm{d}a$ and Kullback-Leibler divergence
$KL(p,q)=\int_{a}p(a)\log\frac{p(a)}{q(a)}\mathrm{d}a$.

##  Appendix B Calculus of Variation and Euler-Lagrange Equation

We consider the following integral functional, where the argument $x$ can be a
real number or a vector, i.e., $x\in R^{n}$,

$F(y)=\int_{A}L(x,y(x),y^{\prime}(x))\mathrm{d}x.$

For calculus of variation, the variation of $y(x)$ is often denoted as
$\eta(x)$. The first variation of the functional $F$ is $\delta
F(\eta,y)=\int\frac{\delta F}{\delta y(x)}\eta(x)\mathrm{d}x$, where
$\frac{\delta F}{\delta y(x)}$ is the functional derivative. The above
integral functional has functional derivative (Euler-Lagrange Equation) given
by

$\frac{\delta F}{\delta y(x)}=\frac{\partial L}{\partial
y}-\sum_{i=1}^{n}\frac{\partial}{\partial x_{i}}\frac{\partial L}{\partial
y_{x_{i}}}$

By setting the Euler-Lagrange equation to zero, we can find an extrema of
$F(y)$. Also, we can add a Lagrange multiplier to cope with the following form
of constraints

$G(y)=\int_{A}M(x,y(x),y^{\prime}(x))\mathrm{d}x=C.$

We can solve the constrained problem by building a new functional in the same
vein of the method of Lagrange multipliers:

$H(y)=\int_{A}(L(x,y,y^{\prime})-\lambda M(x,y,y^{\prime}))\mathrm{d}x.$

For example, consider the following functional $L$ with the constraint that
$g$ is a density function, i.e., $\int_{x\in A}g(x)\mathrm{d}x=1$ and $\forall
x\in A,g(x)\geq 0$

$L(g)=\int_{x\in A}g(x)(-u(x)+\frac{\log g(x)}{\eta})\mathrm{d}x$

We can rewrite the above functional with constraint as follows:

$F(g)=\int_{x\in A}g(x)(-u(x)+\frac{\log g(x)}{\eta}-\lambda)\mathrm{d}x$ (16)

Noticed this functional does not depend on any partial derivative of $g(x)$,
the functional derivative is:

$\frac{\delta F}{\delta g}=(-u(x)+\frac{\log g(x)+1}{\eta}-\lambda).$ (17)

##  Appendix C Finding the Extrema of a Functional by the Euler-Lagrange
Equation

The necessary condition for $y$ being a minimum of a functional is that the
Euler-Lagrange equation is 0 and the second variation

$\delta^{2}F(\eta,y)=\int[\frac{\partial^{2}F}{\partial
y^{2}}\eta^{2}(x)+2\frac{\partial^{2}F}{\partial y\partial
y^{\prime}}\eta(x)\eta^{\prime}(x)+\frac{\partial^{2}F}{\partial(y^{\prime})^{2}}(\eta^{\prime}(x))^{2}]\mathrm{d}x\geq
0,\forall\eta(x).$

For instance, let the Euler-Lagrange equation of Eq.(16) be 0, we can get

$g(x)=\exp(\eta\cdot(u(x)+\lambda))\text{ and }\frac{\partial^{2}F}{\partial
g^{2}}=\frac{1}{\eta g(x)}>0.$

Note that Eq.(16) does not depend on $g^{\prime}(x)$, thus the second
variation $\delta^{2}F(\eta,g)=\int\frac{\partial^{2}F}{\partial
g^{2}}\eta^{2}(x)\mathrm{d}x=\int\frac{\eta^{2}(x)}{\eta^{2}g^{2}(x)}\mathrm{d}x\geq
0$. So $g(x)=\exp(\eta\cdot(u(x)+\lambda))$ is a (local) minimum. From the
constraint that $\int g(x)\mathrm{d}x=1$, we can remove $\lambda$ and obtain

$g(x)=\frac{\exp(\eta\cdot u(x))}{\int\exp(\eta\cdot u(x))\mathrm{d}x}.$

Similarly, it can be easily verified that $g(x)=\frac{\exp(\eta\cdot
u(x))}{\int\exp(\eta\cdot u(x))\mathrm{d}x}$ is a maximum of

$L(g)=\int_{x\in A}g(x)(u(x)-\frac{\log g(x)}{\eta})\mathrm{d}x$

where $g(x)$ is a density function.

##  Appendix D Proof Details

### Proof of Theorem 1

######  Lemma 1.

Given two density functions $p,q$ on a compact set $\mathcal{X}$, where we
assume that $0<a\leq p(x)\leq b$ and $0<a\leq q(x)\leq b$, then

$KL(p,q)\geq\frac{1}{2b}\cdot\|p(x)-q(x)\|^{2}_{2}=\frac{1}{2b}\int_{x}(p(x)-q(x))^{2}\mathrm{d}x$
(18)

###### Proof.

Let $h(t)=2(2+t)(t\log t-t+1)-3(t-1)^{2},t>0.$ We have

$h^{\prime}(t)=2(t\log t-t+1)+2(2+t)\log t-6(t-1)=4\big{(}(1+t)\log
t-2(t-1)\big{)},h^{\prime\prime}=4(\frac{1}{t}+\log t-1).$

Notice that $h^{\prime\prime}(1)=0$ which is the minimum of
$h^{\prime\prime}$, thus $h(t)$ is convex. Also notice that $h^{\prime}(1)=0$,
so $h(t)\geq h(1)=0$. We have that

$t\log t-t+1\geq\frac{3(t-1)^{2}}{2(2+t)}.$ (19)

Taking $t(x)=\frac{p(x)}{q(x)}>0$ into Eq.(19), we get

$\frac{p(x)}{q(x)}\log\frac{p(x)}{q(x)}-\frac{p(x)}{q(x)}+1\geq\frac{3(\frac{p(x)}{q(x)}-1)^{2}}{2(2+\frac{p(x)}{q(x)})}.$
(20)

Multiplying by $q(x)$ and taking integral on both sides, we have

$\int_{x\in\mathcal{X}}\big{(}p(x)\log\frac{p(x)}{q(x)}-p(x)+q(x)\big{)}\mathrm{d}x=KL(p,q)\geq\int_{x\in\mathcal{X}}\frac{3(p(x)-q(x))^{2}}{2(p(x)+2q(x))}\mathrm{d}x.$
(21)

By the assumption that $p(x)$ and $q(x)$ are bounded, we have $p(x)+2q(x)\leq
3b$. So we get

$KL(p,q)\geq\frac{1}{2b}\cdot\int_{x\in\mathcal{X}}(p(x)-q(x))^{2}\mathrm{d}x.$
(22)

∎

Then we proceed the proof of Theorem 1.

###### Proof of Theorem 1.

When we use the $\max\min$ objective, we often assume the game is zero-sum,
i.e., $Q^{1}(a_{1},a_{2})=Q(a_{1},a_{2})=-Q^{2}(a_{1},a_{2})$. Equivalently,
both players maximize their own value function. Let
$Q_{t}(a)=Q^{\pi_{1,t},\pi_{2,t}}(a)=(Q^{1}_{t}(a_{1}),-Q^{2}_{t}(a_{2}))$ for
short, where

$Q^{1}_{t}(a_{1})=\int\pi_{2,t}(a_{2})Q(a_{1},a_{2})\mathrm{d}a_{2}\text{ and
}Q^{2}_{t}(a_{2})=\int\pi_{1,t}(a_{1})Q(a_{1},a_{2})\mathrm{d}a_{1}.$

Thus, we consider the joint policy $\pi_{t}=(\pi_{1,t},\pi_{2,t})$
optimization in the main text. That is,

$\displaystyle\langle\pi(a),Q_{t}(a)\rangle=\int\pi_{1}(a_{1})Q^{1}_{t}(a_{1})\mathrm{d}a_{1}+\int\pi_{2}(a_{2})(-Q^{2}_{t}(a_{2}))\mathrm{d}a_{2}=\int\pi_{1}(a_{1})Q^{1}_{t}(a_{1})\mathrm{d}a_{1}-\int\pi_{2}(a_{2})Q^{2}_{t}(a_{2})\mathrm{d}a_{2},$
$\displaystyle=\int\pi_{1}(a_{1})\int\pi_{2,t}(a_{2})Q(a_{1},a_{2})\mathrm{d}a_{1}\mathrm{d}a_{2}-\int\pi_{2}(a_{2})\int\pi_{1,t}(a_{1})Q(a_{1},a_{2})\mathrm{d}a_{1}\mathrm{d}a_{2}$
(23)
$\displaystyle\int_{a}\pi(a)\log\pi(a)\mathrm{d}a=\int\pi_{1}(a_{1})\log\pi_{1}(a_{1})\mathrm{d}a_{1}+\int\pi_{2}(a)\log\pi_{2}(a)\mathrm{d}a_{2},$
(24) $\displaystyle
KL(\pi,\pi_{t})=KL(\pi_{1},\pi_{1,t})+KL(\pi_{2},\pi_{2,t}).$ (25)

Denote

$\displaystyle G(\pi)$
$\displaystyle=\langle\pi(a),Q(a)\rangle-\alpha\int\pi(a)\log\pi(a)\mathrm{d}a,$
(26) $\displaystyle F(\pi)$
$\displaystyle=\langle\pi(a),Q_{t}(a)\rangle-\alpha{\int_{a}\pi(a)\log\pi(a)\mathrm{d}a}-\frac{1}{\eta}\int_{a}\pi(a)\log\frac{\pi(a)}{\pi_{t}(a)}\mathrm{d}a.$
(27)

The _soft_ optimal joint policy

$\displaystyle\pi^{\star}=(\pi^{\star}_{1},\pi^{\star}_{2})=\arg\max_{\pi^{1}}\arg\min_{\pi^{2}}G(\pi^{1},\pi^{2}).$
(28)

Recall that $\pi_{t+1}=\arg\max_{\pi}F_{t}(\pi).$ By the first-order
optimality condition, we have

$\displaystyle\forall\pi,$ $\displaystyle-\nabla
F(\pi_{t+1})(\pi-\pi_{t+1})\geq 0\Leftrightarrow$ (29) $\displaystyle\langle
Q_{t}(a)-\alpha\cdot\log\pi_{t+1}(a)-\frac{1}{\eta}(\log\frac{\pi_{t+1}(a)}{\pi_{t}(a)}+1),\pi-\pi_{t+1}\rangle\leq
0\Leftrightarrow$ (30) $\displaystyle\langle
Q_{t}(a)-\alpha\cdot\log\pi_{t+1}(a),\pi-\pi_{t+1}\rangle\leq\frac{1}{\eta}\langle\log\frac{\pi_{t+1}(a)}{\pi_{t}(a)},\pi-\pi_{t+1}\rangle$
(31)

We can also decompose the KL as

$KL(\bar{z},y)-KL(z,y)+KL(z,\bar{z})=\langle\log\bar{z}-\log
y,\bar{z}-z\rangle.$ (32)

By Eq.(32), we have

$\displaystyle\langle
Q_{t}(a)-\alpha\cdot\log\pi_{t+1}(a),\pi^{\star}-\pi_{t+1}\rangle\leq\frac{1}{\eta}(KL(\pi^{\star},\pi_{t})-KL(\pi_{t+1},\pi_{t})-KL(\pi^{\star},\pi_{t+1})).$
(33)

Rearrange the above, we can get

$\displaystyle KL(\pi^{*},\pi_{t+1})$ $\displaystyle\leq
KL(\pi^{*},\pi_{t})-KL(\pi_{t+1},\pi_{t})-\eta\langle
Q_{t}(a)-\alpha\cdot\log\pi_{t+1}(a),\pi^{\star}-\pi_{t+1}\rangle\Leftrightarrow$
(34) $\displaystyle KL(\pi^{*},\pi_{t+1})$ $\displaystyle\leq
KL(\pi^{*},\pi_{t})-KL(\pi_{t+1},\pi_{t})+\eta\langle
Q_{t}(a)-\alpha\cdot\log\pi_{t+1}(a),\pi_{t+1}-\pi^{\star}\rangle$ (35)
$\displaystyle=KL(\pi^{*},\pi_{t})-KL(\pi_{t+1},\pi_{t})+\eta\langle
Q_{t}(a)-Q_{t+1}(a),\pi_{t+1}-\pi^{\star}\rangle+\eta\langle
Q_{t+1}(a)-\alpha\log\pi_{t+1}(a),\pi_{t+1}-\pi^{\star}\rangle$ (36)

Taking the last term $\eta\langle
Q_{t+1}(a)-\alpha\log\pi_{t+1}(a),\pi_{t+1}-\pi^{\star}\rangle$ and denoting
$\tilde{Q}^{\star}=(\langle Q,\pi^{\star}_{2}\rangle,-\langle
Q,\pi^{\star}_{1}\rangle)$, we have

$\displaystyle\eta\langle
Q_{t+1}(a)-\alpha\log\pi_{t+1}(a),\pi_{t+1}-\pi^{\star}\rangle$ (37)
$\displaystyle=\eta\underbrace{\langle
Q_{t+1}-\tilde{Q}^{\star},\pi_{t+1}-\pi^{\star}\rangle}_{=0,\text{ by
definition}}+\eta\alpha\langle\log\pi^{\star}-\log\pi_{t+1},\pi_{t+1}-\pi^{\star}\rangle+\underbrace{\eta\langle\tilde{Q}^{\star}-\alpha\log\pi^{\star},\pi_{t+1}-\pi^{\star}\rangle}_{\leq
0,\text{by the optimality of }\pi^{\star}}$ (38)
$\displaystyle\leq\eta\alpha\langle\log\pi^{\star}-\log\pi_{t+1},\pi_{t+1}-\pi^{\star}\rangle$
(39)
$\displaystyle=-\eta\alpha(KL(\pi^{\star},\pi_{t+1})+KL(\pi_{t+1},\pi^{\star})).$
(40)

Plugging back to Eq.(36), we get

$\displaystyle KL(\pi^{*},\pi_{t+1})$ $\displaystyle\leq
KL(\pi^{*},\pi_{t})-KL(\pi_{t+1},\pi_{t})+\eta\langle
Q_{t}(a)-Q_{t+1}(a),\pi_{t+1}-\pi^{\star}\rangle-\eta\alpha(KL(\pi^{\star},\pi_{t+1})+KL(\pi_{t+1},\pi^{\star})).$
(41)

By Cauchy-Schwarz inequality for functions, $\langle
Q_{t}(a)-Q_{t+1}(a),\pi_{t+1}-\pi^{\star}\rangle\leq\|Q_{t}-Q_{t+1}\|_{2}\|\pi_{t+1}-\pi^{\star}\|_{2}$,
we have

$\displaystyle KL(\pi^{*},\pi_{t+1})$ $\displaystyle\leq
KL(\pi^{\star},\pi_{t})-KL(\pi_{t+1},\pi_{t})+\eta\|Q_{t}-Q_{t+1}\|_{2}\|\pi_{t+1}-\pi^{\star}\|_{2}-\eta\alpha(KL(\pi^{\star},\pi_{t+1})+KL(\pi_{t+1},\pi^{\star}))$
(42) $\displaystyle\leq
KL(\pi^{*},\pi_{t})-KL(\pi_{t+1},\pi_{t})+\eta\underbrace{L\|\pi_{t}-\pi_{t+1}\|_{2}}_{L\leq\frac{R_{\max}}{1-\gamma}}\|\pi_{t+1}-\pi^{\star}\|_{2}-\eta\alpha(KL(\pi^{\star},\pi_{t+1})+KL(\pi_{t+1},\pi^{\star}))$
(43) $\displaystyle\leq
KL(\pi^{*},\pi_{t})-KL(\pi_{t+1},\pi_{t})+\frac{\eta^{1/2}\|\pi_{t}-\pi_{t+1}\|_{2}^{2}}{2}+\frac{\eta^{3/2}L^{2}\|\pi_{t+1}-\pi^{\star}\|_{2}^{2}}{2}$
$\displaystyle\quad-\eta\alpha(KL(\pi^{\star},\pi_{t+1})+KL(\pi_{t+1},\pi^{\star}))$
(44) $\displaystyle\overset{\text{by Lemma
\ref{kl_l2_ineq}}}{\leq}KL(\pi^{*},\pi_{t})-KL(\pi_{t+1},\pi_{t})+\eta^{1/2}b\cdot
KL(\pi_{t+1},\pi_{t})+\eta^{3/2}L^{2}b\cdot KL(\pi_{t+1},\pi^{\star})$
$\displaystyle\quad-\eta\alpha(KL(\pi^{\star},\pi_{t+1})+KL(\pi_{t+1},\pi^{\star}))$
(45)

Ineq.(44) is obtained by the elementary inequality $2a\cdot b\leq
a^{2}+b^{2}$. By letting
$\eta\leq\min\\{\frac{1}{b^{2}},\frac{\alpha^{2}}{b^{2}L^{4}}\\}$,

$KL(\pi^{*},\pi_{t+1})\leq KL(\pi^{\star},\pi_{t})-\eta\alpha
KL(\pi^{\star},\pi_{t+1}).$ (46)

Repeat the above recursion, we have

$KL(\pi^{\star},\pi_{t})\leq(\frac{1}{1+\eta\alpha})^{t}KL(\pi^{\star},\pi_{0}).$
(47)

∎

##  Appendix E Ablation Study

New hyper-parameters specific to PORL are $\alpha,\eta$ and the policy
replacement interval $T$. According to Eq.(2), $\alpha$ should be small to
guarantee that the _soft_ optimal solution is close to the original optimal
solution. We conduct ablation studies on the non-stationary HalfCheeta-v2 with
3 seeds, mainly varying $\eta$ and $T$. We keep the default $\alpha=0.2$ in
non-stationary tasks. We first fix $\eta=10$, i.e., $1/\eta=0.1$ and vary $T$
in $\\{10,100,500,1000,2000\\}$. The final performances of the last policy are
reported in Table 4. This implies that a large policy update interval may
hinder the policy improvement, while smaller intervals can help achieve higher
final performance. Although the best final performance becomes better as $T$
becomes smaller in Table 4, we find $T=1000$ works well for stationary and
non-stationary tasks, and $T=10$ works better for adversarial training and
competitive games. Intuitively, when the learning environments change more
frequently, a smaller $T$ is more suitable.

Table 4: Ablation studies on gradient steps for each iteration (fix $\eta=10$). | $T=2000$ | $T=1000$ | $T=500$ | $T=100$ | $T=10$
---|---|---|---|---|---
HalfCheetah-v2 |  $3187.9$ $\pm$ | $1082.91$ |  $3901.09$ $\pm$ | $448.84$ |  $4207.02$ $\pm$ | $136.25$ |  $4281.62$ $\pm$ | $101.01$ |  $\mathbf{4545.25}$ $\pm$ | $\mathbf{237.32}$

From theorem 1, $\eta$ can be rather small. However, as the coefficient in
Eq.(14) is $1/\eta$, a very small $\eta$ will raise instability when we use
neural network models. We then fix $T=1000$ and vary $\eta$ in
$\\{10,5,2,1,0.1\\}$. The results are listed in Table 5. We find PORL is not
very sensitive to the choice of $\eta$ if $1/\eta$ is not too large. However,
if $1/\eta$ becomes large, the policy can fail to converge and perform very
badly.

Table 5: Ablation studies on $\eta$ (fix $T=1000$). | $\eta=10.0$ | $\eta=5.0$ | $\eta=2.0$ | $\eta=1.0$ | $\eta=0.1$
---|---|---|---|---|---
HalfCheetah-v2 |  $3901.09$ $\pm$ | $448.84$ |  $\mathbf{4759.63}$ $\pm$ | $\mathbf{134.32}$ |  $4243.37$ $\pm$ | $91.41$ |  $4465.8$ $\pm$ | $150.72$ |  $-572.36$ $\pm$ | $9.09$

We also verify that a non-zero $\alpha$ is necessary for the last-iterative
convergence. We simply set $\alpha=0$ in the two MPE competitive games and
plot the returns of the learning policy in Figure 6. As these two games are
not rigorously zero-sum, the performance gap of a joint policy will reduce but
not necessarily vanish. As shown in Figure 6, the newest joint policy can
fluctuate when $\alpha=0$, while for $\alpha=0.01$, the performance gap stably
reduces.

Figure 6: Return curves in $2$ multi-agent particle environment competitive
tasks. The returns for player 1 (the adversary) and 2 (the main agent) are
plotted respectively. The curves are shaded with standard errors. If an
algorithm can converge, the performance between the two players necessarily
becomes smaller as the training proceeds.

We perform an extra ablation on the anticipatory parameter $\eta$ in NFSP. As
we observe from [Fujimoto et al., 2019], if the behavior policy and the
learning policy are too disjoint, the off-policy algorithm cannot easily
obtain an effective best response policy from the replay buffer. When $\eta$
in NFSP is small, the learning of BR is less effective, while when $\eta$ is
large, the average policy converges more slowly. As shown in Figure 7, a small
$\eta$ does fail to converge and a large $\eta$ converges slowly.

Figure 7: Return curves in $2$ multi-agent particle environment competitive
tasks. The returns for player 1 (the adversary) and 2 (the main agent) are
plotted respectively. The curves are shaded with standard errors.

##  Appendix F Hyper-parameters and Implementation Details

For SAC, PORL, and NFSP’s best response oracle, which is also SAC, we all use
double $Q$ and target $Q$ nets. For Line 5 and 8 in algorithm 1, we only
perform one gradient update, i.e., $K_{1}=K_{2}=1$ in all the experiments.
Then we replace the $Q$ function and previous round policy (Line 10 in
algorithm 1) every $T$ gradient updates. All the value networks and policy
networks share the same parameters in the same task. The network architecture
and learning rates are referenced from openAI baselines for MuJoCo and MPE
[Mordatch and Abbeel, 2017]. The shared parameters are listed in Table 6 and
7. The parameters used in the final experiments are list in Table 8, 9, and
10. We also perform a simple grid search for PORL in adversarial training and
MPE, and for NFSP in MPE. The search space are listed in Table 11 and 12.

Table 6: Shared hyper-parameters of PORL and SAC on MuJoCo domains. Attributes | Value
---|---
policy learning rate | $3e-4$
value learning rate | $1e-3$
discount factor $\gamma$ | $0.99$
batch size | $256$
target value updating factor $\tau$ | $0.995$
# policy gradient steps per sample | 1
# policy hidden units | $[256,64]$
activation function of policy hidden layers | leaky_relu
# value gradient steps per sample | 1
# value hidden units | $[256,64]$
activation function of policy hidden layers | leaky_relu
# replay buffer | $1e6$
Table 7: Shared hyper-parameters of PORL, SAC and NFSP on MPE domains. Attributes | Value
---|---
policy learning rate | $1e-3$
value learning rate | $1e-3$
discount factor $\gamma$ | $0.95$
batch size | $256$
target value updating factor $\tau$ | $0.995$
# policy gradient steps per sample | 1
# policy hidden units | $[64,64]$
activation function of policy hidden layers | leaky_relu
# value gradient steps per sample | 1
# value hidden units | $[64,64]$
activation function of policy hidden layers | leaky_relu
# replay buffer | $2e5$
Table 8: Hyper-parameters of PORL used in the experiments. Attributes | Value
---|---
$\eta$ | $10.0$
value of $T$ | $\begin{cases}10\text{ (MPE, GAIL)}\\\ 1,000\text{ ((non-)stationary MuJoCo)}\end{cases}$
$\alpha$ | $\begin{cases}0.01\text{ (MPE, GAIL)}\\\ 0.2\text{ ((non-)stationary MuJoCo)}\end{cases}$
Table 9: Hyper-parameters of SAC used in the experiments. Attributes | Value
---|---
target entropy for auto-tuning $\alpha$ | #Dim($\mathcal{A}$)$\times 1.5$
Table 10: Hyper-parameters of NFSP used in the experiments. Attributes | Value
---|---
target entropy for auto-tuning $\alpha$ | #Dim($\mathcal{A}$)$\times 1.5$
anticipatory parameter $\eta$ | $0.2$
# average policy buffer | $2e6$
learning rate for average policy | $1e-3$
Table 11: Grid search range for $\eta$, $T$, and $\alpha$ of PORL on adversarial training and MPE. Attributes | Value
---|---
$\alpha$ | $\\{0.01,0.02,0.05,0.1\\}$
$\eta$ | $\\{10.0,5.0,2.5\\}$
$T$ | $\\{10,100\\}$
Table 12: Grid search range for $\eta$ of NFSP on MPE. Attributes | Value
---|---
$\eta$ | $\\{0.1,0.2,0.5\\}$