# Smoothing Policy Iteration for Zero-sum Markov Games

Yangang Ren#, Yao Lyu#, Wenxuan Wang, Shengbo Eben Li*, Zeyang Li, Jingliang
Duan This work is supported by the National Natural Science Foundation of
China under No. U20A20334. It is also partially supported by Tsinghua
University-Toyota Joint Research Center for AI Technology of Automated
Vehicle. All correspondences should be sent to S. Eben Li with email:
<EMAIL_ADDRESS>Ren, Y. Lyu, W. Wang and S. Eben Li are with State Key Lab
of Automotive Safety and Energy, School of Vehicle and Mobility, Tsinghua
University, Beijing, China. Email: (ryg18, y-lv19, wang-
<EMAIL_ADDRESS><EMAIL_ADDRESS>Z. Li is with the State
Key Laboratory of Tribology, Department of Mechanical Engineering, Tsinghua
University, Beijing, China. Email<EMAIL_ADDRESS>J. Duan is
with the School of Mechanical Engineering, University of Science and
Technology Beijing, China<EMAIL_ADDRESS>
###### Abstract

Zero-sum Markov Games (MGs) has been an efficient framework for multi-agent
systems and robust control, wherein a minimax problem is constructed to solve
the equilibrium policies. At present, this formulation is well studied under
tabular settings wherein the maximum operator is primarily and exactly solved
to calculate the worst-case value function. However, it is non-trivial to
extend such methods to handle complex tasks, as finding the maximum over
large-scale action spaces is usually cumbersome. In this paper, we propose the
smoothing policy iteration (SPI) algorithm to solve the zero-sum MGs
approximately, where the maximum operator is replaced by the weighted
LogSumExp (WLSE) function to obtain the nearly optimal equilibrium policies.
Specially, the adversarial policy is served as the weight function to enable
an efficient sampling over action spaces. We also prove the convergence of SPI
and analyze its approximation error in $\infty-$norm based on the contraction
mapping theorem. Besides, we propose a model-based algorithm called Smooth
adversarial Actor-critic (SaAC) by extending SPI with the function
approximations. The target value related to WLSE function is evaluated by the
sampled trajectories and then mean square error is constructed to optimize the
value function, and the gradient-ascent-descent methods are adopted to
optimize the protagonist and adversarial policies jointly. In addition, we
incorporate the reparameterization technique in model-based gradient back-
propagation to prevent the gradient vanishing due to sampling from the
stochastic policies. We verify our algorithm in both tabular and function
approximation settings. Results show that SPI can approximate the worst-case
value function with a high accuracy and SaAC can stabilize the training
process and improve the adversarial robustness in a large margin.

###### Index Terms:

Approximate dynamic programming, Adversarial robustness, Reinforcement
Learning, Stochastic game.

##  I Introduction

Reinforcement Learning (RL) has achieved tremendous progress in several
notable decision-making problems such as playing the game of Go [1] and
driving an autonomous vehicle[2, 3]. Interestingly, many of these problems can
be formulated as a zero-sum Markov Games (MGs) wherein two opposing players or
teams, called protagonist and adversary respectively, aim to learn jointly
through competition. Formally, zero-sum MGs is usually constructed as a
minimax formulation wherein the protagonist attempts to minimize the
accumulated reward while the adversary tries maximizing it. Thus, they can be
seen as the generalization of both game-theory and the classic Markov Decision
Process (MDP) in traditional RL[4]. Over the past years, zero-sum MGs has been
largely studied in muti-agent systems[5, 6] or robust control[7, 8]. As the
optimal behaviour of a player must take into account the other one, Nash
Equilibrium (NE) policies are always adopted to describe the optimal solutions
at which both players do not have an incentive to vary their current policy
even if they could. Additionally, the adversarial Bellman equation is usually
proposed to ease the solution of this minimax problem, which theoretically
gives a sufficient condition of NE policies[9]. Then, similar to MDP
formulation, there exit two mechanisms to iteratively solve the Bellman
equation: value iteration and policy iteration.

Value iteration aims to solve the adversarial Bellman equation by iteratively
applying the Bellman operator at each iteration, which will produce a sequence
of values and finally converge to the equilibrium value of NE policies[10].
This method is well researched now with the complete convergence proof under
the tabular setting and has been extended widely with function approximations.
Notably, minimax Q-learning was firstly proposed to compute the optimal
policies of both the agents utilizing the state and reward samples obtained
from the environment[5]. After that, minimax TD-learning was proposed to
utilizing the concept of TD-learning [11] and the successive relaxation was
adopted to obtain a faster computation of equilibrium value[12]. Yang _et al._
further proposed minimax-DQN inspired by the huge success of DQN in Atari
games [13] and also characterized its performance in terms of both the
algorithmic and statistical rates of convergence[14]. This method can be
viewed as a combination of the minimax-Q learning for tabular zero-sum MGs and
deep neural networks for function approximation. Meanwhile, Pan _et al._
adopted the similar idea to train the autonomous vehicle in driving simulator,
wherein the vehicle can execute nine discrete actions to steer itself to
finish the whole race [15]. Nevertheless, value-iteration methods can only
handle the simple tasks with discrete action spaces for the reason of
precisely solve the minimax problem in each step.

Policy iteration aims to find the NE policies progressively by conducting
policy evaluation (PEV) and policy improvement (PIM) iteratively. One
straightford method is called the Naive Policy Iteration (NPI) [16], wherein
its PEV attempts to calculate a joint value function related to both
protagonist and adversary. In PIM, it needs to solve a minimax problem w.r.t.
the calculated value function to find another pairs of protagonist and
adversary. Although it has empirically found that NPI is quite efficient in
practice, this algorithm was not proven to converge in all zero-sum MGs. In
fact, it has been showcased that NPI might have cyclic behaviors and fail to
converge to any NE in zero-sum MGs [17]. Regardless of this, many works prefer
to extend this method with function approximation to train the optimal policy
for high-dimensional tasks. Morimoto _et al._ firstly formulated a
differential game with normalized gaussian networks, and derived the gradient-
based method of the update of protagonist and adversary policy based on the
linear dynamic models[7]. Pinto _et al._ combined this method with with deep
neural network to improve the robustness of protagonist, in which the
protagonist and adversary policies are trained alternatively, with one being
fixed whilst the other adapts [18]. Vinitsky _et al._ extended a population-
based augmentation of the one-to-one minimax formulation in which a population
of adversaries were randomly initialized to compete against the protagonist,
showing that this approach results in a more robust policy [19]. Although it
can be easy to implement and can handle high-dimensional and continuous action
spaces, NPI-based methods lack theoretical robustness and optimality
guarantee, and suffer from oscillation during training.

Another more stable policy iteration is the Asynchronous Policy Iteration
(API)[20], which could make sure a strictly converged protagonist policy
motivated by the policy improvement theorem in MDP[21]. This method is
characterized in that PEV step aims to evaluate the worst-case value function
of the protagonist by assuming the adversary always to behave severely.
Afterwards, PIM attempts to solve a minimax problem w.r.t. the calculated
worst-case value function to find another better protagonist policy. Although
having a complete convergence proof, this method is cumbersome in application
resulting from solving an MDP problem exactly in PEV[22]. Therefore, some
works like [23, 24] proposed to evaluate the protagonist approximately under
tabular setting and gave the corresponding error bound in the mild
assumptions. Recently, Wang _et al._ develops the gradient-based method to
solve the robust protagonist policy parameterized with neural networks while
regarding the model uncertainty as an adversary [25]. To provide the
convergence rate, they adopted the LogSumExp (LSE) operator to approximate the
maximum operator and thus provide a surrogate Bellman operator for policy
evaluation[26]. However, the current methods are only applicable for discrete
action space for the sake of traversing all actions to seek the worst-case
adversarial one.

To sum up, the API-based methods enjoys the convergence guarantee, but it
can’t be well applied to conquer large-scale tasks as the exact solution of
maximum operation. Besides, the NPI-based methods have achieved empirical
success in continuous action space domains meanwhile lacking any theoretical
analysis to guarantee the convergence. In this paper, we propose a novel
smoothing policy iteration (SPI) method for zero-sum MGs, which aims to obtain
the nearly optimal policies and is applicable to complex tasks with continuous
action space. The contributions emphasize in three parts:

1) SPI algorithm is proposed by approximating the maximum operator with the
Weighted-LSE (WLSE) function. Specially, the adversarial policy is served as
the weight function of LSE such that we can provably sample the worst
adversarial actions from the large-scale action space. And with the
approximation of worst-case value function in API, SPI accesses the fairly
good training stability and thus provably generates a converged protagonist
policy. Based on the contraction mapping theorem, we prove the convergence of
SPI and analyze its approximation error against API in $\infty-$norm.

2) Based on the developed SPI framework, we propose a model-based RL algorithm
called Smooth adversarial Actor-critic (SaAC) by introducing the deep neural
networks as the function approximators. For the critic update, the WLSE
operator is calculated with the trajectories sampled by protagonist and
adversarial policies, which will serve as the target value and then mean
square error is constructed to optimize the value network. For the actor
update, the minimax formulation is established and the gradient-ascent-descent
methods are developed to optimize the protagonist and adversarial networks
respectively, where we incorporate the reparameterization technique in model-
based gradient backpropgation to prevent the gradient vanishing due to
sampling from the stochastic policies.

3) Extensive simulations are conducted to evaluate the proposed method from
both tabular setting and function approximation setting. The former shows that
SPI can acquire a closely approximation of API and thus has a pretty good
stability, while NPI suffers divergence under some initial conditions. The
latter demonstrates that SaAC algorithm can be more stable to solve the large-
scale and continuous action space tasks, and thus can be widely used to train
adversarially the robust policy for real-world industrial applications.

##  II Preliminary

In this section, we first introduce the basic concepts of the zero-sum MGs and
the adversarial Bellman equation. Under this framework, two mainstream policy
iteration methods are presented, including naive policy iteration (NPI) and
asynchronous policy iteration (API).

###  II-A Zero-sum Markov games

Zero-sum MGs has been an efficient framework for multi-agent learning and
robust learning[27, 28]. Specifically, It can be characterized by a tuple
$<\mathcal{S},\mathcal{A},\mathcal{U},p,r,\gamma>$, where $\mathcal{S}$,
$\mathcal{A}$, and $\mathcal{U}$ indicate the state space, protagonist action
and adversarial action space, respectively. $p(s^{\prime}|s,a,u)$ is the
transition model which determines the distribution of the next state
$s^{\prime}$ depending on the protagonist action $a\in\mathcal{A}$ and the
adversarial action $u\in\mathcal{U}$ at the current state $s\in\mathcal{S}$.
Given the state $s_{t}$ at time $t$, the protagonist policy $\pi(a_{t}|s_{t})$
represents the distribution of the action $a_{t}$, i.e.,
$a_{t}\sim\pi(a_{t}|s_{t})$, while the adversarial policy $\mu(u_{t}|s_{t})$
outputs the distribution of the adversarial action $u_{t}$, i.e.,
$u_{t}\sim\mu(u_{t}|s_{t})$, and both jointly transit the state $s_{t}$ to the
next state $s_{t+1}$, i.e., $s_{t+1}\sim p(s_{t+1}|s_{t},a_{t},u_{t})$. During
this process, the environment feeds the reward $r(s_{t},a_{t},u_{t})$ back to
the protagonist agent, and the adversarial agent receives an opposite reward
$-r(s_{t},a_{t},u_{t})$. Moreover, $\gamma\in[0,1)$ is the discount factor.

In this framework, the state-value function $v^{\pi,\mu}(s)$ depends on both
policies $\pi$ and $\mu$, which represents the long-term accumulated
discounted reward induced by these two policies, i.e.,

$\displaystyle
v^{\pi,\mu}(s_{t})=\mathbb{E}_{\begin{subarray}{c}\pi,\mu\end{subarray}}\left[\sum_{i=0}^{\infty}\gamma^{i}r(s_{t+i},a_{t+i},u_{t+i})\right].$
(1)

And the optimal value function $v^{*}(s)$ is defined as the saddle point of
the state-value function, i.e.,

$\displaystyle v^{*}(s)\overset{{\rm def}}{=}v^{\pi^{*},\mu^{*}}(s)$
$\displaystyle=\min\limits_{\pi}\max\limits_{\mu}v^{\pi,\mu}(s)$ (2)
$\displaystyle=\max\limits_{\mu}\min\limits_{\pi}v^{\pi,\mu}(s),$

which denotes the optimal policies satisfying the NE condition:

$\displaystyle v^{\pi^{*},\mu}(s)\leq v^{\pi^{*},\mu^{*}}(s)\leq
v^{\pi,\mu^{*}}(s),\forall s\in\mathcal{S}.$

It has shown that the optimal NE policies $\pi^{*}$ and $\mu^{*}$ always exit
under the assumption of stochastic policy formulation. Furthermore, they can
be solved directly from the adversarial Bellman equation [9].

######  Definition 1 (Adversarial Bellman equation).

In zero-sum MGs, the solution of adversarial Bellman equation should satisfy
the definition (2) of the optimal value function $v^{*}$, i.e.,

$\displaystyle
v^{*}(s)=\min\limits_{\pi}\max\limits_{\mu}\sum_{a}\pi\sum_{u}\mu\sum_{s^{\prime}}p\left[r+\gamma
v^{*}(s^{\prime})\right].$ (3)

That is, like classical MDP setting, adversarial Bellman equation actually
provides a sufficient condition for the optimal solutions of zero-sum MGs. By
solving it, we can simultaneously obtain both $v^{*}$ and $\pi^{*}$,$\mu^{*}$.

###  II-B Naive Policy Iteration

Naive policy iteration (NPI) is the most straightforward method to solve the
adversarial Bellman equation which is rather similar to the policy iteration
in MDP settings [4]. In PEV, NPI aims to evaluate the joint value function
defined in (1) given current policies $\pi$, $\mu$. wherein the corresponding
Bellman operator $\mathcal{T}^{\pi,\mu}$ can be written as:

$\mathcal{T}^{\pi,\mu}v^{\pi,\mu}(s)=\sum_{a}\pi\sum_{u}\mu\sum_{s^{\prime}}p\left[r+\gamma
v^{\pi,\mu}(s^{\prime})\right].$

It has been proven that $\mathcal{T}^{\pi,\mu}$ is a $\gamma$-contraction
mapping. Thus, we can utilize the iterative manner to find the fixed-point of
this operator starting with a random initialization, i.e.,

$V^{\pi,\mu}_{j+1}(s)=\mathcal{T}^{\pi,\mu}V^{\pi,\mu}_{j}(s)=\sum_{a}\pi\sum_{u}\mu\sum_{s^{\prime}}p\left[r+\gamma
V^{\pi,\mu}_{j}(s^{\prime})\right],$ (4)

where $V^{\pi,\mu}_{j}(s)$ is the estimation of the state value
$v^{\pi,\mu}(s)$ and $j$ denotes iterative step in PEV. And this kind of
iteration will eventually converge to $v^{\pi,\mu}(s)$, i.e.,
$\lim_{j\rightarrow\infty}V^{\pi,\mu}_{j}(s)=v^{\pi,\mu}(s)$. As for PIM, a
minimax formulation will be solved to find another round of policies
$\pi^{\prime}$, $\mu^{\prime}$ based on the calculated $v^{\pi,\mu}$, i.e.,

$\displaystyle\pi^{\prime},\mu^{\prime}=\arg\min\limits_{\pi}\max\limits_{\mu}\sum_{a}\pi\sum_{u}\mu\sum_{s^{\prime}}p\left[r+\gamma
v^{\pi,\mu}(s^{\prime})\right].$ (5)

And this actually formulates a game matrix which can be solve exactly using
two dual linear programming under tabular case, then the solved policies will
be evaluated by another round of PEV as in (4) again.

Although NPI seems intuitive and be efficient in some applications, this
method lacks of convergence guarantee, making it usually unstable and easy to
diverge, especially integrated with nonlinear function approximators such as
neural networks.

###  II-C Asynchronous Policy iteration

Asynchronous policy Iteration (API) is another more stable method to solve the
adversarial Bellman equation. Specially, it will evaluate the worst-case value
function $v^{\pi}$, which can be regarded as the best response of the
adversarial agent to the protagonist policy $\pi$. This worst-case Bellman
operator $\mathcal{T}^{\pi}$ can be defined as:

$\displaystyle
v^{\pi}(s)=\mathcal{T}^{\pi}v^{\pi}(s)=\max\limits_{u\in\mathcal{U}}\sum_{a}\pi\sum_{s^{\prime}}p\left[r+\gamma
v^{\pi}(s^{\prime})\right],$ (6)

In addition, $\mathcal{T}^{\pi}$ is also a $\gamma$-contraction mapping which
has a unique fixed point. Besides, we can attain this fixed point iteratively
using

$\displaystyle
V^{\pi}_{j+1}(s)=\mathcal{T}^{\pi}V^{\pi}_{j}(s)=\max\limits_{u\in\mathcal{U}}\sum_{a}\pi\sum_{s^{\prime}}p\left[r+\gamma
V^{\pi}_{j}(s^{\prime})\right].$ (7)

The PIM of API also attempts to solve the minimax formulation based on
$v^{\pi}$

$\pi^{\prime},\mu^{\prime}=\arg\min\limits_{\pi}\max\limits_{\mu}\sum_{a}\pi\sum_{u}\mu\sum_{s^{\prime}}p\left[r+\gamma
v^{\pi}(s^{\prime})\right].$ (8)

Different with NPI, here $\mu’$ will not participate in the next round of PEV
wherein only the worst adversarial action will be used to evaluate $\pi’$ in
each iteration step.

The above procedure will generate a monotonically decreasing sequence of value
functions, i.e., $v^{\pi^{\prime}}(s)\leq v^{\pi}(s),\forall s\in\mathcal{S}$,
that is, $\pi^{\prime}$ is a better policy than $\pi$. Therefore,
$v^{\pi^{\prime}}$ will strictly converge to $v^{*}$, i.e.,
$\lim_{k\to\infty}v^{\pi_{k}}=v^{*}$, where $k$ represents the iteration round
of PEV and PIM. However, the bottleneck of API lies in that the maximum
operator involved in (7) requires solving a nonlinear equation at each step of
PEV, making API hard to be adopted to problems with continuous adversarial
action space.

##  III Algorithm

In this section, we propose to approximate the maximum operator with the
weight-LSE function and thus design the smoothing policy iteration (SPI). In
addition, we combine SPI with parameterized functions and develop the
gradient-based rules for their update, resulting in the smoothing adversarial
actor-critic (SaAC) to deal with complex tasks with high-dimensional and
continuous state and action spaces.

###  III-A Smoothing Policy Iteration

Intuitively, API methods enjoy the better convergence as the exact solution of
maximum operator, whereas this is non-trivial to implement in large-scale
problems. On the other side, NPI methods have the better efficiency when
converging since both policies are used to sample actions to evaluate the
value function. Therefore, we aim to improve the training stability by
approximating the maximum operator meanwhile using the protagonist and
adversarial policies simultaneously to sample from their arbitrary action
spaces. To this end, we firstly introduce the Weight LogSumExp (WLSE)
function, which can be seen as an extended form of LogSumExp [26] with a
probability density function as the weights.

######  Definition 2 (Weight LogSumExp function).

Suppose $X\in\mathbb{R}^{n}=[x_{1},x_{2},\cdots,x_{n}]^{\top}$ and a positive
real value $\rho$, we define the weight LogSumExp function as

${\rm WLSE}(X)=\frac{1}{\rho}\log\sum_{i=1}^{n}{w_{i}\exp(\rho x_{i})}$ (9)

where $\rho>0$ is the approximation factor, $w_{i}$ is the weight of $x_{i}$
satisfying $\sum_{i=1}^{n}{w_{i}}=1$ and $w_{i}\geq
0,\forall{i}\in\\{1,2,\cdots,n\\}$.

Then, we can see that this function can closely approach to the maximum item
of $X$, i.e., $x_{m}=\max\limits_{i}{X}$, controlled by $\rho$ and the weight
of $x_{m}$.

######  Lemma 1 (Error bound of WLSE function).

Suppose $x_{m}=\max\limits_{i}{X}$ and $w_{m}$ is the weight of $x_{m}$, the
approximate error of WLSE function to the maximum value is

$|\operatorname{WLSE}(X)-x_{m}|\leqslant\left|\frac{\log w_{m}}{\rho}\right|.$
(10)

###### Proof.

Given $\rho>0$, $x_{m}=\max\\{x_{1},x_{2},\cdots,x_{n}\\}$ and $w_{m}\in[0,1]$
is the corresponding weight, we have

$w_{m}\exp\left(\rho x_{m}\right)\leqslant\sum_{i=1}^{n}w_{i}\exp\left(\rho
x_{i}\right)\leqslant\exp\left(\rho x_{m}\right).$

Take the logarithm of the above equation and rearrange it, we have

$\frac{\log
w_{m}}{\rho}\leqslant\frac{1}{\rho}\log\sum_{i=1}^{n}w_{i}\exp\left(\rho
x_{i}\right)-x_{m}\leqslant 0.$

It is obvious that WLSE always makes a lower approximaton to the orginal
maximum, and then we take the absolute value of both sides, i.e.,

$\left|\frac{1}{\rho}\log\sum_{i=1}^{n}w_{i}\exp\left(\rho
x_{i}\right)-x_{m}\right|\leqslant\left|\frac{\log w_{m}}{\rho}\right|.$

∎

Obviously, $\rho$ and $w_{m}$ determines the approximate error bound of WLSE
function respectively, which will approach to zero when $\rho\to\infty$ for
any $w_{m}>0$ and a bigger $w_{m}$ will also lead to a tighter error bound.

######  Corollary 1.

The WLSE function is equivalent to the maximum operator as $\rho$ goes to
infinity, i.e.,

$\lim_{\rho\to\infty}{\rm WLSE}(X)=\max X.$

###### Proof.

If $w_{m}=1$, WLSE will be deduced samely as $x_{m}$ for any $\rho>0$, i.e.,
${\rm WLSE}(X)=\max X$, which accords with the corollary condition. Otherwise,
since $\log w_{m}$ is finite as $w_{m}\in(0,1)$, we have

$\lim_{\rho\to\infty}|\operatorname{WLSE}(X)-\max
X|\leqslant\lim_{\rho\to\infty}\left|\frac{\log w_{m}}{\rho}\right|=0.$

∎

Based on this, we can approximate the maximum operator in (6) with the WLSE
function where the adversarial policy $\mu$ can be served as the weight
function of different trajectories sampled by the protagonist policy $\pi$.
The smoothing worst-case Bellman operator $\widetilde{\mathcal{T}}^{\pi}$ can
be defined as

$\displaystyle\widetilde{\mathcal{T}}^{\pi}v^{\pi}_{\rho}(s)=\frac{1}{\rho}{\log\sum_{u}\mu\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s^{\prime})\big{]}\bigg{\\}}},$ (11)

where $v^{\pi}_{\rho}(s)$ is the state-value function calculated by WLSE
function with some $\rho>0$, and $\widetilde{\mathcal{T}}^{\pi}$ is the
approximation of $\mathcal{T}^{\pi}$. Under this scheme, we primarily prove
that $\widetilde{\mathcal{T}}^{\pi}$ is also a $\gamma$-contraction mapping
such that the iterative manner can be used to find its fixed value in PEV.

######  Lemma 2 (1-Lipschitz property of WLSE).

The WLSE function is 1-Lipschitz. That is

$\left|{\rm WLSE}(X)-{\rm WLSE}(Y)\right|\leq{\lVert
X-Y\rVert}_{\infty},\forall{X,Y\in\mathbb{R}^{n}}.$ (12)

###### Proof.

By the differential mean value theorem, $\forall{X,Y\in\mathbb{R}^{n}}$,
$\exists h\in(0,1)$ such that

$\operatorname{WLSE}(\mathrm{X})-\mathrm{WLSE}(\mathrm{Y})=\nabla\operatorname{WLSE}[X+h(X-Y)](X-Y).$

Noticing that

$\frac{\partial{\rm WLSE(X)}}{\partial x_{i}}=\frac{w_{i}\exp(\rho
x_{i})}{\sum_{i=0}^{n}{w_{i}\exp(\rho x_{i})}},$

we can obtain

$\|\nabla{\rm WLSE(X)}\|_{\infty}\leq 1.$

According to Cauchy-Schwarz inequality, we have

$\displaystyle|\mathrm{WLSE}(X)-\mathrm{WLSE}(Y)|$
$\displaystyle\leqslant\|\nabla\operatorname{WLSE}[Y+h(X-Y)]\|_{\infty}\left\|X-Y\right\|_{\infty}$
$\displaystyle\leqslant\|X-Y\|_{\infty}.$

∎

Then under Lemma 2, we show that $\widetilde{\mathcal{T}}^{\pi}$ is a
$\gamma$-contraction.

######  Theorem 1 ($\gamma$-contraction property of
$\widetilde{\mathcal{T}}^{\pi}$).

$\widetilde{\mathcal{T}}^{\pi}$ is a $\gamma$-contraction mapping, i.e.,

${\lVert\widetilde{\mathcal{T}}^{\pi}V^{\pi}_{j+1}-\widetilde{\mathcal{T}}^{\pi}V^{\pi}_{j}\rVert}_{\infty}\leq\gamma{\lVert
V^{\pi}_{j+1}-V^{\pi}_{j}\rVert}_{\infty}.$ (13)

###### Proof.

According to Lemma 2, we can derive that

$\displaystyle{\left|\widetilde{\mathcal{T}}V^{\pi}_{j+1}(s)-\widetilde{\mathcal{T}}V^{\pi}_{j}(s)\right|}$
$\displaystyle=\Bigg{|}\frac{1}{\rho}{\log\sum_{u}\mu\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j+1}(s^{\prime})\big{]}\bigg{\\}}}-$
$\displaystyle\qquad\frac{1}{\rho}{\log\sum_{u}\mu\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j}(s^{\prime})\big{]}\bigg{\\}}}\Bigg{|}$
$\displaystyle\leq\max_{u}\Big{|}\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j+1}(s^{\prime})\big{]}-$
$\displaystyle\qquad\qquad\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j}(s^{\prime})\big{]}\Big{|}$
$\displaystyle=\gamma\max_{u}\Big{|}\sum_{a}\pi\sum_{s^{\prime}}p\big{[}V^{\pi}_{j+1}(s^{\prime})-V^{\pi}_{j}(s^{\prime})\big{]}\Big{|}$
$\displaystyle\leq\gamma\max_{u}{\Big{|}\sum_{a}\pi\sum_{s^{\prime}}p\max_{s\in\mathcal{S}}\big{[}V^{\pi}_{j+1}(s)-V^{\pi}_{j}(s)\big{]}\Big{|}}$
$\displaystyle=\gamma{\left\|V^{\pi}_{j+1}-V^{\pi}_{j}\right\|}_{\infty}.$

Since the above inequality holds for any state $s\in\mathcal{S}$, we finally
have

${\lVert\widetilde{\mathcal{T}}^{\pi}V^{\pi}_{j+1}-\widetilde{\mathcal{T}}^{\pi}V^{\pi}_{j}\rVert}_{\infty}\leq\gamma{\lVert
V^{\pi}_{j+1}-V^{\pi}_{j}\rVert}_{\infty}.$

∎

Up to now, we can iteratively solve the fixed point of
$\widetilde{\mathcal{T}}^{\pi}$, denoted as $v^{\pi}_{\rho}$, to conduct the
policy evaluation, i.e.,

$\displaystyle V^{\pi}_{j+1}(s)$
$\displaystyle=\widetilde{\mathcal{T}}^{\pi}V^{\pi}_{j}(s)$ (14)
$\displaystyle=\frac{1}{\rho}{\log\sum_{u}\mu\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j}(s^{\prime})\big{]}\bigg{\\}}},$

wherein $j$ is the iterative step and
$v^{\pi}_{\rho}(s)=\lim_{j\to\infty}V_{j}^{\pi}(s)$. Furthermore, the
approximation error of $v^{\pi}_{\rho}$ to the true value function $v^{\pi}$
can be bounded by $\rho$ and maximum value of $\mu$.

######  Theorem 2 (Error bound of PEV).

Suppose $v^{\pi}$, $v_{\rho}^{\pi}$ are the fixed points of
$\mathcal{T}^{\pi}$ and $\widetilde{\mathcal{T}}^{\pi}$ respectively, i.e.,
$v^{\pi}=\mathcal{T}^{\pi}v^{\pi}$,
$v_{\rho}^{\pi}=\widetilde{\mathcal{T}}^{\pi}v_{\rho}^{\pi}$, the approximate
error is

$\displaystyle{\left\|v^{\pi}-v_{\rho}^{\pi}\right\|}_{\infty}\leq\frac{1}{1-\gamma}\left\|\frac{\log\mu_{m}}{\rho}\right\|_{\infty}$
(15)

where $\mu_{m}$ is the maximum value of the adversarial policy $\mu$.

###### Proof.

According to Lemma 1, Theorem 1 and the triangle inequality, we can derive
that

$\displaystyle{\left\|v^{\pi}-v_{\rho}^{\pi}\right\|}_{\infty}$
$\displaystyle={\left\|\mathcal{T}^{\pi}v^{\pi}-\widetilde{\mathcal{T}}^{\pi}v_{\rho}^{\pi}\right\|}_{\infty}$
$\displaystyle\leq{\left\|\mathcal{T}^{\pi}v^{\pi}-\mathcal{T}^{\pi}v_{\rho}^{\pi}\right\|}_{\infty}+{\left\|\mathcal{T}^{\pi}v_{\rho}^{\pi}-\widetilde{\mathcal{T}}^{\pi}v_{\rho}^{\pi}\right\|}_{\infty}$
$\displaystyle\leq\gamma{\left\|v^{\pi}-v_{\rho}^{\pi}\right\|}_{\infty}+\max_{s}\left|\frac{\log\max_{u}\mu(\cdot|s)}{\rho}\right|$
$\displaystyle=\gamma{\left\|v^{\pi}-v_{\rho}^{\pi}\right\|}_{\infty}+\left\|\frac{\log\mu_{m}}{\rho}\right\|_{\infty}.$

Rearrange the above inequality we immediately conclude (15). ∎

Once the smooth value function $v^{\pi}_{\rho}$ is acquired in PEV, the
following PIM aims to find another round of better policies $\pi^{\prime}$ and
$\mu^{\prime}$ by solving the following minimax problem

$\displaystyle\pi^{\prime},\mu^{\prime}=\arg\min\limits_{\pi}\max\limits_{\mu}\sum_{a}\pi\sum_{u}\mu\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s)\big{]}.$ (16)

Thus, PEV in (14) and PIM in (16) constitutes the smoothing policy iteration
(SPI), wherein these two phases iterate to obtain the optimal value function
$v_{\rho}^{*}$ and optimal policise $\pi^{*}$, $\mu^{*}$. As the introducing
of the approximation operator, SPI actually acquires the nearly optimal NE
solution of the adversarial bellman equation in (3), wherein the error bounds
between $v_{\rho}^{*}$ and $v^{*}$optimal solutions can be analysed
explicitly.

######  Lemma 3 (Error bound of Bellman equation[9]).

Suppose $\epsilon$ is the approximate error bound of PEV and
$\widetilde{v}^{*}$ is the corresponding nearly-optimal value function, the
approximate error bound of $\widetilde{v}^{*}$ to $v^{*}$is

$\displaystyle{\left\|\widetilde{v}-v^{*}\right\|}_{\infty}\leq\frac{2\gamma}{(1-\gamma)^{2}}\epsilon,$
(17)

Therefore, we characterize the optimality of SPI by considering the error
bound in Theorem 2:

######  Corollary 2.

Suppose $v_{\rho}^{*}$ is the optimal value function outputed by SPI and
$v^{*}$ is the true optimal value function, the approximate error bound of
$v_{\rho}^{*}$ to $v^{*}$ is

$\displaystyle{\left\|v_{\rho}^{*}-v^{*}\right\|}_{\infty}\leq\frac{2\gamma}{(1-\gamma)^{3}}\left\|\frac{\log\mu_{m}}{\rho}\right\|_{\infty}.$
(18)

It is obvious that SPI converges to the NE solution as $\rho\to\infty$.

###  III-B The influence of weight function

Here, we analyze the influence of weight function choice to the approximation
error under tabular case. Specially, we choose the adversarial policy $\mu$ as
the weight function in (11), which will provably lead to a more accurate
approximation to the maximum operation. To that end, we firstly show that
$\widetilde{\mathcal{T}}^{\pi}$ is a monotonous operator.

######  Lemma 4 (Monotonicity of $\widetilde{\mathcal{T}}^{\pi}$).

Let $V^{\pi}_{j},W^{\pi}_{j}\in\mathbb{R}$ such that $V^{\pi}_{j}(s)\geq
W^{\pi}_{j}(s)$ holds for $s\in\mathcal{S}$ and
$V^{\pi}_{j+1}(s)=\widetilde{\mathcal{T}}^{\pi}V^{\pi}_{j}(s^{\prime}),W^{\pi}_{j+1}(s)=\widetilde{\mathcal{T}}^{\pi}W^{\pi}_{j}(s^{\prime})$.
Then,

$V^{\pi}_{j+1}(s)\geq W^{\pi}_{j+1}(s),\forall s\in\mathcal{S}$

###### Proof.

As $V^{\pi}_{j}(s^{\prime})\geq W^{\pi}_{j}(s^{\prime})$, we can conclude for
any $u\sim\mu$

$\displaystyle\mu(u)\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j}(s^{\prime})\big{]}\bigg{\\}}$
$\displaystyle\geq\mu(u)\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
W^{\pi}_{j}(s^{\prime})\big{]}\bigg{\\}}\geq 0$

Then,

$\displaystyle
V^{\pi}_{j+1}(s)-W^{\pi}_{j+1}(s)=\widetilde{\mathcal{T}}^{\pi}V^{\pi}_{j}(s)-\widetilde{\mathcal{T}}^{\pi}W^{\pi}_{j}(s)$
$\displaystyle=\frac{1}{\rho}\log\frac{\sum_{u}\mu\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j}(s^{\prime})\big{]}\bigg{\\}}}{\mu(u)\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V^{\pi}_{j}(s^{\prime})\big{]}\bigg{\\}}}$ $\displaystyle\geq 0$

∎

Accordingly, as WLSE function provides a lower approximation to maximum as
shown in Lemma 1, a good initialization $V^{\pi}_{0}$ will generate a sequence
of $\\{V^{\pi}_{j}\\}$ whose fixed point $v^{\pi}_{\rho}$ will be closer to
$v^{\pi}$.

On the other side, we can see that $\mu$ is always updated by the minimax
formulation in (16), wherein two dual linear programs will give the solutions
under tabular case. Denoting the NE value of (16) as
$v^{\pi^{\prime},\mu^{\prime}}_{\rho}$, we have

$\displaystyle\min_{\pi^{\prime},\mu^{\prime}}\quad
v^{\pi^{\prime},\mu^{\prime}}$ s.t.
$\displaystyle\sum_{u}\mu^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s^{\prime})\big{]}\geq
v^{\pi^{\prime},\mu^{\prime}},\forall{a\in\mathcal{A}}$
$\displaystyle\sum_{u\in\mathcal{U}}\mu^{\prime}(u)=1$
$\displaystyle\mu^{\prime}(u)\geq 0,\forall{u\in\mathcal{U}}$

Solving this problem will generate $v^{\pi^{\prime},\mu^{\prime}}$ and
$\mu^{\prime}$. And its dual linear programming can be derived as

$\displaystyle\max_{\pi^{\prime},\mu^{\prime}}\quad
v^{\pi^{\prime},\mu^{\prime}}$ s.t.
$\displaystyle\sum_{a}\pi^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s^{\prime})\big{]}\leq
v^{\pi^{\prime},\mu^{\prime}},\forall{u\in\mathcal{U}}$
$\displaystyle\sum_{a\in\mathcal{A}}\pi^{\prime}(a)=1$
$\displaystyle\pi^{\prime}(a)\geq 0,\forall{a\in\mathcal{A}}$

Similarly, we can attain $\mu^{\prime}$ from this programming. According to
the theorem of complementary slackness of dual problems [29], we have

$\displaystyle\mu^{\prime}(u)\big{[}\sum_{a}\pi^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s^{\prime})\big{]}-v^{\pi^{\prime},\mu^{\prime}}\big{]}=0,\forall{u\in\mathcal{U}}$
(19)

We can see if some $u$ makes $\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s^{\prime})\big{]}<v^{\pi^{\prime},\mu^{\prime}}$, then
$\mu^{\prime}(u)=0$ always holds. This means that the adversary policy only
assigns non-zero probability for such adversarial actions satisfying
$v^{\pi^{\prime},\mu^{\prime}}(s)=\sum_{a}\pi^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s^{\prime})\big{]}$.

Additionally, as $v^{\pi^{\prime},\mu^{\prime}}$ is the NE point, any other
policy $\mu^{\\#}$ will correspond to a smaller value function:

$\displaystyle v^{\pi^{\prime},\mu^{\prime}}$
$\displaystyle=\sum_{a}\pi^{\prime}\sum_{u}\mu^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(^{\prime}s)\big{]}$
$\displaystyle\geq\sum_{a}\pi^{\prime}\sum_{u}\mu^{\\#}\sum_{s^{\prime}}p\big{[}r+\gamma
v^{\pi}_{\rho}(s^{\prime})\big{]}$

Specially, we assume $\mu^{\\#}$ as the deterministic policy in which it only
takes the adversarial action resulting in the biggest value function, i.e.,
$\mu^{\\#}(u_{m})=1.0$ where $u_{m}$ satisfies

$\displaystyle
u_{m}=\arg\max\limits_{u\in\mathcal{U}}\bigg{\\{}\sum_{a}\pi^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v_{\rho}^{\pi}(s^{\prime})\big{]}\bigg{\\}}.$

And we can get

$v^{\pi^{\prime},\mu^{\prime}}\geq\max\limits_{u\in\mathcal{U}}\bigg{\\{}\sum_{a}\pi^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v_{\rho}^{\pi}(s^{\prime})\big{]}\bigg{\\}}.$

Meanwhile, as $v^{\pi^{\prime},\mu^{\prime}}$ is the weighted average value
w.r.t. the current $\pi^{\prime}$, that is,

$v^{\pi^{\prime},\mu^{\prime}}\leq\max\limits_{u\in\mathcal{U}}\bigg{\\{}\sum_{a}\pi^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v_{\rho}^{\pi}(s^{\prime})\big{]}\bigg{\\}}.$

Thus, it always holds that

$\displaystyle
v^{\pi^{\prime},\mu^{\prime}}=\max\limits_{u\in\mathcal{U}}\bigg{\\{}\sum_{a}\pi^{\prime}\sum_{s^{\prime}}p\big{[}r+\gamma
v_{\rho}^{\pi}(s^{\prime})\big{]}\bigg{\\}}$ (20)

Combining (19) and (20), we conclude that choosing $\mu$ as the weight
function will assign high probability over the set of the worst adversarial
actions which is closer to maximum operation and thus provide a fair
initialization for the next round of PEV. According to Lemma 4, this will
eventually lead to a more accurate approximation and thus provably enhance the
convergence speed as demonstrated in IV-A.

###  III-C Smoothing Adversarial Actor-Critic (SaAC)

In order to deal with complex tasks with continuous state and action spaces,
we further propose the smoothing adversarial actor-critic (SaAC) algorithm
based on the developed SPI method. We will consider a parameterized value
function $V_{\psi}(s)$, a parameterized protagonist policy
$\pi_{\theta}(\cdot|s)$ and adversarial policy $\mu_{\phi}(\cdot|s)$, wherein
$\psi$, $\theta$ and $\phi$ are their trainable parameters respectively. Based
on PEV step in (11), $V_{\psi}(s)$ can be directly trained by minimizing the
mean square error between the output of value network and the corresponding
target value. Therefore, the objective of $V_{\psi}(s)$ can be written as

$\displaystyle\min_{\psi}J_{V}(\psi)=\frac{1}{2}\mathbb{E}_{s}\big{[}y_{\overline{\psi}}(s)-V_{\psi}(s)\big{]}^{2},$
(21)

where $y_{\overline{\psi}}(s)$ represents the target state value of $s$ and
$\overline{\psi}$ is the parameters of the target network. Concretely, it can
be calculated by using the smoothing bellman operator in (11)

$\displaystyle
y_{\overline{w}}(s)=\frac{1}{\rho}{\log\sum_{u}\mu\exp\bigg{\\{}\rho\sum_{a}\pi\sum_{s^{\prime}}p\big{[}r+\gamma
V_{\overline{w}}(s^{\prime})\big{]}\bigg{\\}}}$ (22)

Obviously, this target value makes a important role for stable training of
value update, which can be estimated by the samples generated by environment
model $p$, and the protagonist policy $\pi_{\theta}$ and adversarial policy
$\mu_{\phi}$, as shown in Algorithm 1. To that end, we sample a bunch of
samples for current initial state corresponding to different adversarial
actions and then the target is calculated by (22) to estimate the expectation.

Then, the parameters of $V_{\psi}$ are updated by

$\displaystyle\psi\leftarrow\psi-\beta_{\psi}\nabla_{\psi}J_{V}(\psi),$ (23)

where $\beta_{\psi}$ is the learning rate of value function and
$\nabla_{\psi}J_{V}({\psi})$ is the gradients of $J_{V}({\psi})$ w.r.t.
${\psi}$, i.e.,

$\nabla_{\psi}J_{V}({\psi})=-\mathbb{E}_{s}\bigg{[}\big{(}y_{\overline{\psi}}(s)-V_{\psi}(s)\big{)}\nabla_{\psi}V_{\psi}(s)\bigg{]}.$

In addition, the target network mentioned above adopts a slow-moving update
rule to stabilize the learning process as

$\displaystyle\overline{\psi}\leftarrow\tau{\psi}+(1-\tau)\overline{\psi},$

where $\tau$ is the temperature to adjust the updating speed.

Algorithm 1 Target State Value

0: policies $\pi_{\theta}$, $\mu_{\phi}$, environment model $p$, Buffer
$\mathcal{B}$, target value network $V_{\overline{\psi}}$

Initialize the initial state from $\mathcal{B}$, $s\sim\mathcal{B}$

Initialize number of trajectories $K$

Initialize value list $\mathbb{L}$

for each sample in $K$ do

Obtain $u\sim\mu_{\phi}(s)$, $a\sim\pi_{\theta}(s)$

Calculate the next state with environment model $s^{\prime}\sim p$

Calculate the target value $y_{i}=r+\gamma V_{\overline{\psi}}(s^{\prime})$
for this sample $<s,a,u,s^{\prime},r>$

Add $y_{i}$ into the value list $\mathbb{L}$

end for

Calculate $y_{\overline{\psi}}$ using the WLSE function over $\mathbb{L}$
$y_{\overline{\psi}}(s)=\frac{1}{\rho}{\log\frac{1}{K}\sum_{i=1}^{K}\exp\big{\\{}\rho\big{(}r+\gamma
V_{\overline{\psi}}(s^{\prime})\big{)}\big{\\}}}$

$y_{\overline{\psi}}$

As for policy update, $\pi_{\theta}$ and $\mu_{\phi}$ formalize a minimax
problem based on (16), i.e.,

$\displaystyle\min\limits_{\theta}\max\limits_{\phi}J_{\pi,\mu}(\theta,\phi)=\mathbb{E}_{s}\left[r+\gamma
V_{\psi}(s^{\prime})\right].$

For this problem, the gradient-descent-ascent methods are widely adopted to
update the networks simultaneously,

$\displaystyle\theta$
$\displaystyle\leftarrow\theta-\beta_{\theta}\partial_{\theta}J_{\pi,\mu}(\theta,\phi),$
(24) $\displaystyle\phi$
$\displaystyle\leftarrow\phi+\beta_{\phi}\partial_{\phi}J_{\pi,\mu}(\theta,\phi),$

where $\beta_{\theta}$ and $\beta_{\phi}$ are the learning rates of
protagonist policy and adversarial policy, respectively. Here, we can further
derive the gradients $\partial_{\theta}J_{\pi,\mu}$ and
$\partial_{\phi}J_{\pi,\mu}$ in SaAC within the model-based framework,

$\displaystyle\partial_{\theta}J_{\pi,\mu}$
$\displaystyle=\partial_{\theta}\mathbb{E}_{s}\left[r+\gamma
V_{\psi}(s^{\prime})\right]$ (25)
$\displaystyle=\mathbb{E}_{s}\left[\frac{\partial{a}^{\rm
T}}{\partial{\theta}}\frac{\partial{r}}{\partial{a}}+\gamma\frac{\partial{a}^{\rm
T}}{\partial{\theta}}\frac{\partial{s^{\prime}}^{\rm
T}}{\partial{a}}\frac{\partial{V_{\psi}}}{\partial{s^{\prime}}}\right]$
$\displaystyle=\mathbb{E}_{s}\left[\frac{\partial{\pi_{\theta}}^{\rm
T}}{\partial{\theta}}\big{(}\frac{\partial{r}}{\partial{a}}+\gamma\frac{\partial{p}^{\rm
T}}{\partial{a}}\frac{\partial{V_{\psi}}}{\partial{s^{\prime}}}\big{)}\right]$

Note that the second equation comes from the fact that $s^{\prime}\sim
p(s,a,u)$ and $a\sim\pi_{\theta}$. Besides, $\frac{\partial{r}}{\partial{a}}$
and $\frac{\partial{p}^{\rm T}}{\partial{a}}$ contribute to the gradient
w.r.t. the parameters of protagonist policy, and their usage can effectively
reduce the computational complexity to estimate policy gradients. Similarly,
the gradient of $\mu_{\phi}$ can be derived as

$\displaystyle\partial_{\phi}J_{\pi,\mu}=\mathbb{E}_{s}\left[\frac{\partial{\mu_{\phi}}^{\rm
T}}{\partial{\phi}}\big{(}\frac{\partial{r}}{\partial{u}}+\gamma\frac{\partial{p}^{\rm
T}}{\partial{u}}\frac{\partial{V_{\psi}}}{\partial{s^{\prime}}}\big{)}\right]$
(26)

However, the issue in calculating (25) and (26) is that we can not directly
obtain $\frac{\partial{\pi_{\theta}}^{\rm T}}{\partial{\theta}}$ and
$\frac{\partial{\mu_{\phi}}^{\rm T}}{\partial{\phi}}$in zero-sum MGs with the
stochastic policy $\pi_{\theta}$ and $\mu_{\phi}$. In this condition, the
sample operation of actions from a distribution will lead to the gradient
fracture and thus the reparameterization trick is proposed [30] to derive the
policy gradient. Assuming

$a=f_{\theta}(\xi;s),u=h_{\phi}(\eta;s)$

where $f_{\theta}$ and $h_{\phi}$ are the reparameterized policies, $\xi$ and
$\eta$ are auxiliary variables which are sampled from some fixed distribution,
we can derive the executable gradient of the protagonist policy,

$\displaystyle\partial_{\theta}J_{\pi,\mu}=\mathop{\mathbb{E}}\displaylimits_{\begin{subarray}{c}s,\xi\end{subarray}}\left[\frac{\partial{f_{\theta}(\xi;s)}^{\rm
T}}{\partial{\theta}}\big{(}\frac{\partial{r}}{\partial{f_{\theta}(\xi;s)}}+\gamma\frac{\partial{p}^{\rm
T}}{\partial{f_{\theta}(\xi;s)}}\frac{\partial{V_{\psi}}}{\partial{s^{\prime}}}\big{)}\right]$
(27)

Similarly, the gradient $\partial_{\phi}J_{\pi,\mu}$ can be derived with the
reparameterization and model-based chain rules:

$\displaystyle\partial_{\phi}J_{\pi,\mu}=\mathop{\mathbb{E}}\displaylimits_{\begin{subarray}{c}s,\eta\end{subarray}}\left[\frac{\partial{h_{\phi}(\eta;s)}^{\rm
T}}{\partial{\theta}}\big{(}\frac{\partial{r}}{\partial{h_{\phi}(\eta;s)}}+\gamma\frac{\partial{p}^{\rm
T}}{\partial{h_{\phi}(\eta;s)}}\frac{\partial{V_{\psi}}}{\partial{s^{\prime}}}\big{)}\right]$
(28)

Finally, we can conclude the details of SaAC in Algorithm 2 and show the
diagram in Fig. 1.

Figure 1: SaAC diagram. Value function, protagonist policy and adversarial
policy are carried by neural networks respectively. SaAC first updates the
smoothing value based on the a bunch of samples collected by both policies.
Then, the output of the value network is used to guide the update of policies
by gradient-descent and ascent. Algorithm 2 Smooth adversarial Actor-Critic
(SaAC)

Initialize $\psi$, $\theta$, and $\phi$

Initialize learning rates $\beta_{\psi},\beta_{\theta}$ and $\beta_{\phi}$

Initialize main iteration step $k=0$

Initialize adversarial policy updating interval $M$

Initialize buffer $\mathcal{B}\leftarrow\emptyset$

repeat

// Sampling

for each environment episode do

$t=0$

Randomly select an initial state $s$

for each environment step do

Sample adversarial action $u_{t}\sim\mu_{\phi}(\cdot|s_{t})$

Sample protagonist action $a_{t}\sim~{}\pi_{\theta}(\cdot|s_{t})$

Obtain $s_{t+1}\sim p$ and $r_{t}$

Add the sample into buffer $\mathcal{B}\cup\\{s_{t},a_{t},r_{t},s_{t+1}\\}$

$t=t+1$

end for

end for

// Optimizing

Fetch a batch of samples from $\mathcal{B}$, compute $y_{\overline{\psi}}$
with Algorithm 1, compute $J_{\pi,\mu}$ with $\mu_{\phi}$, $\pi_{\theta}$ and
$p$

Update the parameters of value function $w\leftarrow
w-\beta_{w}\nabla_{w}J_{V}$

Update the parameters of policy
$\theta\leftarrow\theta-\beta_{\theta}\partial_{\theta}J_{\pi,\mu}$

if $k\%M=0$ then

Update the parameters of adversary policy
$\phi\leftarrow\phi+\beta_{\phi}\partial_{\phi}J_{\pi,\mu}$

end if

$k=k+1$

until Convergence

##  IV Simulation verification

In this section, we carefully design two different tasks, the two-state MGs
and the robust path tracking, which respectively corresponds to the tabular
and function approximation settings, to verify the approximation performance
of SPI and the training stability of SaAC.

###  IV-A Two-state MGs

We demonstrate the approximation performance of SPI by introducing a two-state
zero-sum MGs, which was originally proposed as a classical counterexample to
illustrate the divergence of NPI [17]. With discrete and countable state and
action spaces, SPI is able to solve the value and policies exactly in a state-
by-state manner, making it unnecessary to employ any function approximator. As
shown in Fig. 2, there are only two states in the state space
$\mathcal{S}=\\{s_{1},s_{2}\\}$, and $s_{2}$ is an absorbing state, that is,
the agent will always keep motionless at $s_{2}$ no matter what actions are
adopted. Moreover, there are only two corresponding elements in the
protagonist action and the adversarial action space, i.e.,
$\mathcal{A}=\\{a_{1},a_{2}\\}$ and $\mathcal{U}=\\{u_{1},u_{2}\\}$. If the
current state is $s_{1}$, the agent stays at $s_{1}$ regardless of the action
pair in $\left\\{(a_{1},u_{1}),(a_{2},u_{1}),(a_{2},u_{2})\right\\}$, and
receives rewards -3, -2, and -1 respectively. However, when taking the action
pair $(a_{1},u_{2})$, the agent either stays at $s_{1}$ with probability
$\frac{1}{3}$ or transits to $s_{2}$ with probability $\frac{2}{3}$ and
receives reward -6 in both situations.

Figure 2: Two-state zero-sum MGs.

Since $s_{2}$ is an absorbing state with zero cost, its state value
$v^{\pi}(s_{2})$ is always zero, and thus we only focus on the value function
at $s_{1}$. Here, we firstly explore the difference of API and SPI, wherein
their PEV should be accomplished iteratively according to (7) and (14) given a
pair of policies $\pi$ and $\mu$. Specifically, we consider
$\rho\in\\{1.0,5.0,10.0,20.0\\}$ respectively to further investigate the role
of $\rho$ on the approximation performance. Besides, to verify the influence
of weights, the SPI-u algorithm is introduced under $\rho=10$ wherein a
uniform distribution serves as the weight function regardless of the
adversarial policy. At the beginning, we initialize both the protagonist and
adversarial policy as the stochastic policies, i.e.,

$\pi_{0}(a_{1}|s_{1})=0.50,\pi_{0}(a_{2}|s_{1})=0.50,$
$\mu_{0}(u_{1}|s_{1})=0.45,\mu_{0}(u_{2}|s_{1})=0.55.$

For this policy pair $(\pi_{0},\mu_{0})$, Fig. 3a depicts the value varying
with the iterative step during PEV. We can see that all methods basically
converge to their fixed points when the step reaches more than 10, and SPI-
based methods indeed obtain different approximation value depend on $\rho$ and
weight. Furthermore, we list their convergent values in Table I, wherein API
converges to the true value of current policies for $s_{1}$, i.e.,
$v^{\pi_{0}}(s_{1})=-6.9999$. Obviously, the approximation of SPI becomes more
accurate as $\rho$ increases, which is consistent with our previous
theoretical analysis. SPI estimates the value as $-7.0693$ with $\rho=20.0$,
where the approximation error to the value estimate from API is $\Delta
e=0.98\%$. For the same $\rho=10$, SPI achieves a better performance than
SPI-u indicating the adversarial policy as the weight function will reduce the
error bound efficiently than a random uniform distribution.

(a) PEV for $\pi_{0}(s_{1})$

(b) PEV for $\pi_{1}(s_{1})$

Figure 3: Process of policy evaluation. TABLE I: Approximation error of for $\pi_{0}(s_{1})$. Method | $\rho$ | Value | Error(%)
---|---|---|---
SPI | 1.0 | -7.6243 | 8.92
5.0 | -7.2334 | 3.34
10.0 | -7.1195 | 1.71
20.0 | -7.0598 | 0.86
SPI-u | 10.0 | -7.1385 | 1.98
API | - | -6.9999 | 0.00

Next, with the converged value estimate $v^{\pi_{0}}$, we can conduct the PIM
based on (16) by solving the corresponding game matrix, i.e.,

$\bordermatrix{&u_{1}&u_{2}\cr a_{1}&-8.25&-7.75\cr a_{2}&-7.25&-6.25\cr}$

Clearly, the NE of this game matrix is $(a_{1},u_{2})$ with the equilibrium
value as $-7.75$. Hence, the next policy pair $(\pi_{1},\mu_{1})$ can be
extracted as

$\pi_{1}(a_{1}|s_{1})=1.0,\mu_{1}(u_{2}|s_{1})=1.0,$

and both the policies have degenerated into the deterministic form at this
time. Then, the next round of PEV will be conducted to evaluate
$(\pi_{1},\mu_{1})$ as shown in Fig. 3b, where the true value calculated by
API is $v^{\pi_{1}}(s_{1})=-8.00$. Meanwhile, SPI-based method will always
estimate $v^{\pi_{1}}(s_{1})$ as the $-7.99$ regardless of the value of
$\rho$, because the weight function $\mu_{1}$ only makes a difference at
$u_{2}$. At this moment, their approximation errors are almost 0. However,
SPI-u method still maintains the considerable error about 1.12%, meaning that
the uniform weight function has limited ability to sample the most adversarial
action.

TABLE II: Approximation error of for $\pi_{1}(s_{1})$. Method | $\rho$ | Value | Error(%)
---|---|---|---
SPI | 1.0 | -8.00 | 0.00
5.0 | -8.00 | 0.00
10.0 | -8.00 | 0.00
20.0 | -8.00 | 0.00
SPI-u | 10.0 | -8.09 | 1.12
API | - | -8.00 | 0.00

Subsequently, PIM aims to find the next policy pair by solving the following
game matrix, i.e.,

$\bordermatrix{&u_{1}&u_{2}\cr a_{1}&-9.00&-8.00\cr a_{2}&-8.00&-7.00\cr}$

Since the NE of this matrix is still $(a_{1},u_{2})$, the extracted new policy
$(\pi_{2},\mu_{2})$ is exactly identical to $(\pi_{1},\mu_{1})$, and thus
their PEV will obtain the same $v^{\pi_{2}}(s_{1})$ with $v^{\pi_{1}}(s_{1})$,
i.e., $v^{\pi_{1}}(s_{1})=v^{\pi_{2}}(s_{1})$. Therefore, the algorithm
converges and we can conclude that the optimal NE policies ca be

$\displaystyle\pi^{*}(a_{1}|s_{1})=1.0,$
$\displaystyle\mu^{*}(u_{2}|s_{1})=1.0$ (29)

with the equilibrium value as

$\displaystyle v^{*}(s_{1})=1.0,$ $\displaystyle v^{*}(s_{2})=0.0.$ (30)

The above analysis illustrates the convergence of API and SPI, and the results
suggest that SPI can accurately approximate API by utilizing sufficiently
large $\rho$ as well as a reasonable weight function. Moreover, as for NPI, we
briefly illustrate the fact that value function of different policy pairs
oscillates under some mild initial conditions, resulting in non-convergence at
this two-state zero-sum MGs. To showcase this oscillation, the initial policy
pair $(\pi_{0},\mu_{0})$ can be chosen as the deterministic form

$\displaystyle\pi_{0}(a_{1}|s_{1})=1.0,\mu_{0}(u_{1}|s_{1})=1.0.$

Using the PEV process in (4), the joint value function esitimated by NPI is
$v^{\pi_{0},\mu_{0}}(s_{1})=-12.00$, and the corresponding game matrix for PIM
is

$\bordermatrix{&u_{1}&u_{2}\cr a_{1}&-12.00&-9.00\cr a_{2}&-11.00&-10.00\cr}$

Therefore, we can obtain the next policy pair $(\pi_{1},\mu_{1})$ as

$\displaystyle\pi_{1}(a_{2}|s_{1})=1.0,\mu_{1}(u_{2}|s_{1})=1.0.$

Similarly, its joint value function can be evaluated by PEV as
$v^{\pi_{1},\mu_{1}}=-4.00$ and the corresponding game matrix is

$\bordermatrix{&u_{1}&u_{2}\cr a_{1}&-6.00&-7.00\cr a_{2}&-5.00&-4.00\cr}$

Consequently, the new policy pair $(\pi_{2},\mu_{2})$ extracted by PIM become

$\displaystyle\pi_{1}(a_{1}|s_{1})=1.0,\mu_{1}(u_{1}|s_{1})=1.0.$

which is identical to $(\pi_{0},\mu_{0})$ and we further conclude
$v^{\pi_{0},\pi_{0}}(s_{1})=v^{\pi_{2},\pi_{2}}(s_{1})=-12.0$ and
$v^{\pi_{1},\pi_{1}}(s_{1})=v^{\pi_{3},\pi_{3}}(s_{1})=-4.0$. Actually, if we
repeat the above PEV and PIM with more iteration, the value function will
always oscillate between $-12.0$ and $-4.0$, unable to reach the optimal
policies in (29) and the optimal value in (30). That is, NPI will diverge
under this initial conditions and fail to find the optimal solutions.

###  IV-B Robust Path Tracking

Next, we show another classical robust path-tracking problem with continuous
state and action spaces to characterize the training stability of SaAC. In
this task, the vehicle aims to track a given path as accurately as possible in
the presence of lateral perturbation as shown in Fig. 4.

Figure 4: Robust path tracking task. There exists an unknown disturbance in
the lateral velocity.

The vehicle state is designed as $s=\left[p_{x},\Delta
y,\Delta\varphi,v_{x},v_{y},\omega\right]^{\top}$, where the elements are
longitudinal position, lateral tracking error, heading angle error,
longitudinal velocity, lateral velocity and raw rate respectively. Besides, we
choose the front wheel angle $\delta$ and acceleration $A$ as the protagonist
action to realize the lateral and longitudinal control, i.e.,
$a=[\delta,A]^{\top}$. At the same time, there exists a gaussian uncertainty
$\Delta v_{y}\sim\mathcal{N}(\kappa,\Lambda^{2})$ in the lateral velocity
$v_{y}$ due to crosswinds or road lateral slopes, wherein $\kappa$ and
$\Lambda$ are the learnable mean and standard deviation. Hence, the
adversarial policy is expected to learn the worst $\Delta v_{y}$ that
interferes with the tracking performance of the ego vehicle, i.e., $u=\Delta
v_{y}$. Considering the actuator saturation, we bound the protagonist action
and adversarial action with $\delta\in[-0.4,0.4]{\rm rad}$,
$A\in[-1.5,3.0]{\rm m/s^{2}}$ and $\Delta v_{y}\in[-0.5,0.5]{\rm m/s}$,
respectively. The dynamics of this task are modeled as follows based on [31]:

$p({s},{a},u)=\left[\begin{array}[]{c}p_{x}+\Delta
t\left(v_{x}\cos\Delta\varphi-v_{y}\sin\Delta\varphi\right)\\\ \Delta y+\Delta
t\left(v_{x}\sin\Delta\varphi+v_{y}\cos\Delta\varphi\right)\\\
\Delta\varphi+\Delta t\omega\\\ v_{x}+\Delta t\left(A+v_{y}\omega\right)\\\
\frac{mv_{x}v_{y}+\Delta t\left[\left(L_{f}k_{f}-L_{r}k_{r}\right)\omega-
k_{f}\delta v_{x}-mv_{x}^{2}\omega\right]}{mv_{x}-\Delta
t\left(k_{f}+k_{r}\right)}+u\\\ \frac{-I_{z}\omega v_{x}-\Delta
t\left[\left(L_{f}k_{f}-L_{r}k_{r}\right)v_{y}-L_{f}k_{f}\delta
v_{x}\right]}{\Delta
t\left(L_{f}^{2}k_{f}+L_{r}^{2}k_{r}\right)-I_{z}v_{x}}\end{array}\right],$
(31)

where the dynamical parameters are shown in Table III.

TABLE III: Dynamical parameters. Parameter | Symbol | Value
---|---|---
Front-wheel cornering stiffness | $k_{f}$ | -155495N/rad
Rear-wheel cornering stiffness | $k_{r}$ | -155495N/rad
Distance from CG to front axle | $L_{f}$ | 1.19m
Distance from CG to rear axle | $L_{r}$ | 1.46m
Mass | $m$ | 1520kg
Polar moment of inertia at CG | $I_{z}$ | 2640kg$\cdot\mathrm{m}^{2}$
Discrete time step | $\Delta t$ | 0.1s

Considering the tracking accuracy, energy efficiency and driving comfort, we
construct a classical quadratic-form reward function with carefully tuned
weights as

$\displaystyle r(s,a,u)=0.03(v_{x}-20)^{2}+0.8{\Delta
y}^{2}+30{\Delta\varphi}^{2}+0.05A^{2}$
$\displaystyle+0.02\omega^{2}+5\delta^{2},$

in which the objective is to maintain the vehicle speed close to 20m/s, while
keeping a small tracking error and ensuring that the vehicle stays within the
stability region. Then, $\pi_{\theta}$ is to minimize the accumulated rewards,
while $\mu_{\phi}$ aims to maximize them to exacerbate the driving performance
by outputting the lateral interference. Thus, the protagonist policy trained
in this setting takes into account possible disturbances during training and
should become more robust against the distractions from real environment.

The reference path is the composition of three sine curves with different
magnitudes and periods,

$y_{\rm
ref}=7.5\sin\frac{2\pi}{200}+2.5\sin\frac{2\pi}{300}-5\sin\frac{2\pi}{400}.$

To verify the effectiveness of SaAC, we select the model-based version of
robust adversarial reinforcement learning (RaRL) [18] as a comparison
benchmark, which is indeed a parameterized version of NPI. The only difference
of SaAC and RaRL is the target value in value network update, wherein the
former uses the bellman operator to construct the target and the latter adopts
the smooth bellman operator to calculate it. We also adopt another classic
model-based RL method called approximate dynamic programming (ADP) wherein
only the protagonist policy is constructed without the adversarial training,
to showcase the robust advantages of SaAC. Finally, we also construct the
SaAC-u algorithm, the extension of SPI-u with neural networks, where the
continuous uniform distribution is used as the weight function rather than the
adversarial policy. For fair comparison, all these algorithms adopt the same
algorithmic framework and training parameters. We utilize multi-layer
perceptron (MLP) as the function approximator of value function, protagonist
policy and adversarial policy. Each network contains five 256-unit hidden
layers and we apply the Gaussian error linear unit (GeLU) as their activation
functions. In addition, hyperbolic tangent (tanh) is utilized for the output
layers of policy networks to saturate their outputs. Meanwhile, the value
network uses a linear function as the activation of its output layer. With a
cosine-annealing learning rate, Adam [32] is used to update all networks. We
also deploy an asynchronous parallel training framework [31] to accelerate the
training process. Specifically, 2 samplers pick up data by interacting with
the environment, 2 buffers store samples, and 10 learners optimize the
networks by exploiting the collected data. The detailed hyperparameter
settings are listed in Table IV.

TABLE IV: Training hyperparameters.

[h]  Hyperparameter Value Optimizer Adam ($\beta_{1}=0.9,\beta_{2}=0.999$)
Function approximator MLP Number of hidden layers 5 Number of hidden units 256
Activation of hidden layer GeLU Activation of output layer Tanh (policy) /
Linear (Value) Batch size 256 Learning rate anneal Cosine anneal Policy
learning rate $5\times 10^{-5}$ $\rightarrow$ $1\times 10^{-6}$ Value learning
rate $8\times 10^{-5}$ $\rightarrow$ $1\times 10^{-6}$ Discount factor 0.99
Policy updating interval $M$ 1 Temperature of target network 0.001 Number of
samplers 2 Number of buffers 2 Number of learners 10

During training, we test the tracking performance of the learned protagonist
policy every 3,000 iterations. In each test, the ego vehicle will be
initialized randomly and attempts to track the given path for 150 steps. Then,
we will calculate the total average return of 5 episodes under the same policy
to show its current performance. The training results for 5 runs with
different seeds are shown in Fig. 5. In Table V, we also show the converged
return and characterize the convergence speed of different algorithms, which
is measured by the average number of iterations needed to firstly exceed a
certain goal performance, set -25 in our experiments. Clearly, SaAC obtains
the highest return when converged which is around -5 and SaAC-u almost has the
same return but it suffers a low convergence speed, needing 54000 iterations
to acquire a fair performance. This also demonstrates that the adversarial
policy will be a better weight function than a random distribution, which will
accelerates the policy evaluation and thus converges rapidly. Besides, ADP
finally attains a lower return than SaAC and SaAC-u, which means that it
cannot deal with the disturbance from environment perfectly with the normal
training process. Finally, we can see RaRL achieves the lowest average return
over the 5 runs, and Table V shows that it suffers a rather large variance in
the converged return under different seeds. We can conclude that RaRL is very
unstable in training under different initial conditions, indicating the
similar properties with SPI in tabular case.

Figure 5: Learning curves. The solid lines correspond to the mean over 10 runs. TABLE V: TAR of each run. Algorithm | Performance | Convergence speed
---|---|---
ADP | $-20.92\pm 12.40$ | 60000
RaRL | $-280.35\pm 379.64$ | -
SaAC | $-5.18\pm 0.69$ | 33000
SaAC-u | $-5.38\pm 0.61$ | 54000

Fig. 6 graphs the tracking errors of all baseline algorithms during training.
We can see RaRL hardly tracks the reference path accurately because there
exist high errors in position. Besides, SaAC-u shows a slow convergence speed
in heading error compared with SaAC. Finally, ADP obtains a higher position
error and heading angle error than SaAC, meaning the disturbance will work
obviously if the training process is conducted without considering the
environmental variation.

(a) Position error

(b) Heading angle error

Figure 6: Errors of robust path tracking task. (a) Position error. (b) Heading
error. The solid lines correspond to the mean and the shaded regions
correspond to 95% confidence interval over 5 runs.

We also conduct the robust test of the trained policy in Fig. 7, wherein the
protagonist policies of ADP and SaAC after 100000 iterations under the same
random seed are chosen to track the path for 5 episodes. Meanwhile, we
establish a varying disturbance to the lateral velocity of the model in (31)
from $-0.3m/s$ to $0.3m/s$ with the interval 0.06. Obviously, the total
average return respectively reaches their highest point near the disturbance
of 0 and the bigger disturbance will cause the performance degradation for
these two algorithms. However, SaAC always behaves better than ADP under all
these disturbances, which is befit from the robustness of adversarial
training.

To sum up, SPI can acquire a satisfactory solution of adversarial Bellman
equation with the large factor $\rho$ and the adversarial weight function. And
with neural network as function approximators, SaAC can maintain a fair
training stability as well as improve the robustness of protagonist policy in
a large margin.

Figure 7: Testing curves under lateral disturbance. The solid lines correspond
to the mean and the shaded regions correspond to 90% confidence interval over
5 episode.

##  V Conclusion

This paper aims to solve the zero-sum MGs approximately to handle the complex
tasks with large-scale action spaces. To this end, we propose the SPI
algorithm wherein WLSE function is developed to approximate the maximum
operator. Specially, we can control the approximation error by adjusting the
approximation factor and the weighted function enables an efficient sampling
in action spaces. We also prove the convergence of SPI and analyze its
approximation error in $\infty-$norm based on the contraction mapping theorem.
Based on this, we propose SaAC by extending SPI with the neural networks as
the function approximators, which is a typical model-based RL algorithm to
train the protagonist and adversarial policy simultaneously. We apply our
algorithm in a two-state MGs and the robust path tracking tasks respectively.
Results show that SPI can approximate the worst-case value function with a
high accuracy and SaAC can stabilize the training process and lead to the
adversarial robustness. About the future work, we will extend the SPI-based
algorithm to handle more complex industrial tasks such autonomous driving,
where the self-driving car needs to compete with its surrounding participants
to strive for a successful navigation. Moreover, we will consider the
constraints to the adversarial policy in current minimax formation to make the
less radical adversarial behaviors.

## References

  * [1] D. Silver, J. Schrittwieser _et al._ , “Mastering the game of go without human knowledge,” _Nature_ , vol. 550, no. 7676, pp. 354–359, 2017.
  * [2] X. Ma, K. Driggs-Campbell, and M. J. Kochenderfer, “Improved robustness and safety for autonomous vehicle control with adversarial reinforcement learning,” in _2018 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2018, pp. 1665–1671.
  * [3] Y. Ren, G. Zhan, S. E. Li _et al._ , “Improve generalization of driving policy at signalized intersections with adversarial learning,” _arXiv:2204.04403_ , 2022. [Online]. Available: https://arxiv.org/abs/2204.04403
  * [4] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [5] M. L. Littman, “Markov games as a framework for multi-agent reinforcement learning,” in _Machine learning proceedings 1994_. Elsevier, 1994, pp. 157–163.
  * [6] K. Zhang, S. Kakade _et al._ , “Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 1166–1178, 2020.
  * [7] J. Morimoto and K. Doya, “Robust reinforcement learning,” _Neural computation_ , vol. 17, no. 2, pp. 335–359, 2005.
  * [8] J. Li, S. E. Li _et al._ , “Reinforcement solver for h-infinity filter with bounded noise,” in _2020 15th IEEE International Conference on Signal Processing (ICSP)_ , vol. 1. IEEE, 2020, pp. 62–67.
  * [9] S. D. Patek, “Stochastic and shortest path games: theory and algorithms,” Ph.D. dissertation, Massachusetts Institute of Technology, 1997.
  * [10] Shapley, “Stochastic games,” _Proceedings of the National Academy of Sciences_ , vol. 39, no. 10, pp. 1095–1100, 1953.
  * [11] F. A. Dahl and O. M. Halck, “Minimax td-learning with neural nets in a markov game,” in _Proceedings of the 11th European Conference on Machine Learning_ , Berlin, Heidelberg, 2000, pp. 117–128.
  * [12] R. B. Diddigi, C. Kamanchi, and S. Bhatnagar, “A generalized minimax q-learning algorithm for two-player zero-sum stochastic games,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 9, pp. 4816–4823, sep 2022.
  * [13] V. Mnih, K. Kavukcuoglu, D. Silver _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [14] J. Fan, Z. Wang, Y. Xie _et al._ , “A theoretical analysis of deep q-learning,” in _Learning for Dynamics and Control_. PMLR, 2020, pp. 486–489.
  * [15] X. Pan, D. Seita, Y. Gao, and J. Canny, “Risk averse robust adversarial reinforcement learning,” in _2019 International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 8522–8528.
  * [16] M. A. Pollatschek and B. Avi-Itzhak, “Algorithms for stochastic games with geometrical interpretation,” _Management Science_ , vol. 15, no. 7, pp. 399–415, 1969.
  * [17] J. Van Der Wal, “Discounted markov games: Generalized policy iteration method,” _Journal of Optimization Theory and Applications_ , vol. 25, no. 1, pp. 125–138, 1978.
  * [18] L. Pinto, J. Davidson, R. Sukthankar, and A. Gupta, “Robust adversarial reinforcement learning,” in _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , 2017.
  * [19] E. Vinitsky, Y. Du, K. Parvate _et al._ , “Robust reinforcement learning using adversarial populations,” _arXiv:2008.01825_ , 2020. [Online]. Available: https://arxiv.org/abs/2008.01825
  * [20] A. J. Hoffman and R. M. Karp, “On nonterminating stochastic games,” _Management Science_ , vol. 12, no. 5, pp. 359–370, 1966.
  * [21] S. E. Li, _Reinforcement Learning for Sequential Decision and Optimal Control_. Springer Verlag, Singapore, 2023\.
  * [22] S. S. Rao, R. Chandrasekaran, and K. Nair, “Algorithms for discounted stochastic games,” _Journal of Optimization Theory and Applications_ , vol. 11, no. 6, pp. 627–637, 1973.
  * [23] J. Perolat, 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.
  * [24] B. Huang, J. D. Lee, Z. Wang, and Z. Yang, “Towards general function approximation in zero-sum markov games,” _arXiv:2107.14702_ , 2021. [Online]. Available: https://arxiv.org/abs/2107.14702
  * [25] Y. Wang and S. Zou, “Policy gradient method for robust reinforcement learning,” in _International Conference on Machine Learning, ICML 2022, July 2022, Baltimore, Maryland, USA_ , 2022.
  * [26] Y. Wang and S. Zou, “Online robust reinforcement learning with model uncertainty,” in _Advances in Neural Information Processing Systems_ , vol. 34, 2021, pp. 7193–7206.
  * [27] G. N. Iyengar, “Robust dynamic programming,” _Mathematics of Operations Research_ , vol. 30, no. 2, pp. 257–280, 2005.
  * [28] Y. Ren, J. Duan, S. E. Li, Y. Guan, and Q. Sun, “Improving generalization of reinforcement learning with minimax distributional soft actor-critic,” in _2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2020, pp. 1–6.
  * [29] P. E. Gill, W. Murray, and M. H. Wright, _Numerical linear algebra and optimization_. SIAM, 2021.
  * [30] J. Duan, Y. Guan, S. E. Li _et al._ , “Distributional soft actor-critic: Off-policy reinforcement learning for addressing value estimation errors,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 11, pp. 6584–6598, 2022.
  * [31] Y. Guan, J. Duan, S. E. Li _et al._ , “Mixed policy gradient,” _arXiv:2102.11513_ , 2021. [Online]. Available: https://arxiv.org/abs/2102.11513
  * [32] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014. [Online]. Available: https://arxiv.org/abs/1412.6980