# A First Order Meta Stackelberg Method for Robust Federated Learning

Yunian Pan  Tao Li  Henger Li  Tianyi Xu  Zizhan Zheng  Quanyan Zhu

###### Abstract

Previous research has shown that federated learning (FL) systems are exposed
to an array of security risks. Despite the proposal of several defensive
strategies, they tend to be non-adaptive and specific to certain types of
attacks, rendering them ineffective against unpredictable or adaptive threats.
This work models adversarial federated learning as a Bayesian Stackelberg
Markov game (BSMG) to capture the defender’s incomplete information of various
attack types. We propose meta-Stackelberg learning (meta-SL), a provably
efficient meta-learning algorithm, to solve the equilibrium strategy in BSMG,
leading to an adaptable FL defense. We demonstrate that meta-SL converges to
the first-order $\varepsilon$-equilibrium point in $O(\varepsilon^{-2})$
gradient iterations, with $O(\varepsilon^{-4})$ samples needed per iteration,
matching the state of the art. Empirical evidence indicates that our meta-
Stackelberg framework performs exceptionally well against potent model
poisoning and backdoor attacks of an uncertain nature.

Adversarial Federated Learning, Meta Learning, Meta Equilibrium, Bayesian
Stackelberg Markov Game, ICML

##  1 Introduction

Federated learning (FL) provides a way for several devices possessing private
data to collaboratively train a learning model without the need to share their
local data (McMahan et al., 2017). Nonetheless, FL systems remain susceptible
to antagonistic attacks, including untargeted model poisoning and specific
backdoor attacks. To counter these vulnerabilities, a range of robust
aggregation techniques like Krum (Blanchard et al., 2017), coordinate-wise
median (Yin et al., 2018), trimmed mean (Yin et al., 2018), and FLTrust (Cao
et al., 2021) have been suggested for defense against non-specific attacks.
Furthermore, different post-training protective measures like Neuron Clipping
(Wang et al., 2022) and Pruning (Wu et al., 2020) have been recently
introduced to reduce the impact of backdoor attacks.

Existing defenses are typically built to resist specific attack types and
attacks that do not evolve in response to defensive measures. In this work, we
introduce a meta-Stackelberg game (meta-SG) framework that delivers robust
defensive performance, even against adaptive attacks such as the reinforcement
learning (RL)-based attack (Li et al., 2022a), which current state-of-the-art
defenses struggle to address, or an amalgamation of different attack types
like the simultaneous occurrence of model poisoning and backdoor attacks (see
Section 5).

Figure 1: A schematic illustration of the meta-Stagberg game framework. In the
pertaining stage, a simulated environment is constructed using generated data
and a set of attacks sampled from the attack domain consisting of various
attack strategies. The defender utilizes meta-Stackelberg learning (Algorithm
2) to obtain the meta policy $\theta$ and the adaptation $\Psi$ in
(LABEL:eq:meta-se). Then, in the online execution, the defender can adapt its
defense to $\Psi(\theta,\tau)$ using received feedback $\tau$ in the presence
of unknown attacks.

Our meta-SG defense framework is established on several key observations.
Firstly, the issue of robust FL in the face of a non-adaptive attack can be
perceived as a Markov decision process (MDP), where the state represents model
updates from selected devices, and the action refers to the gradient for
updating the global model. Moreover, when the attack is known beforehand, the
defender can employ the limited amount of local data at the server and
publicly accessible data to construct an (approximate) MDP model and determine
a robust defense policy by pre-training prior to the commencement of FL
training. Secondly, for situations where the attack is adaptive but with
specific parameters, we consider a Markov game between the attacker and the
defender and establish a robust defense by solving the Stackelberg equilibrium
of the game, wherein the defender is the leader and the attacker the follower.
This approach applies to both single and multiple concurrent attacks and may
yield an (almost) optimal defense. Thirdly, in more realistic scenarios where
attacks are unknown or uncertain, this situation can be treated as a Bayesian
Stackelberg Markov game (BSMG), offering a comprehensive model for adversarial
FL. Uncertain attacks refer to those involved in the pre-training stage but
undisclosed in the online FL process, leaving the defender unsure about their
existence. On the other hand, unknown attacks point to those excluded in the
pre-training, of which the defender is unaware. Nonetheless, the standard
solution concept for BSMG, the Bayesian Stackelberg equilibrium, aims at the
expected case and does not adapt to the actual attack.

In this study, we introduce a novel solution concept, the meta-Stackelberg
equilibrium (meta-SE), for BSMG as a systematic approach to creating resilient
and adaptive defenses for federated learning. By merging meta-learning with
Stackelberg reasoning, meta-SE provides a computationally efficient method to
handle information asymmetry in adversarial FL and facilitates strategic
adaptation during online execution amidst multiple (adaptive) attackers. Prior
to training an FL model, a meta-policy is trained by solving the BSMG using
experiences sampled from a set of potential attacks. During FL training, when
confronted with an actual attacker, the meta-policy rapidly adapts using a
relatively small batch of samples gathered in real-time. Importantly, our
proposed Meta-SG framework only requires a rough estimate of potential attacks
during meta-training due to the generalization capability offered by meta-
learning.

To solve the BSMG in the pre-training stage, we develop a meta-Stackelberg
learning (meta-SL) algorithm, based on the concept of debiased meta-
reinforcement learning (Fallah et al., 2021). Meta-SL is proven to converge to
the first-order $\varepsilon$-approximate meta-SE in $O(\varepsilon^{-2})$
iterations, and the corresponding sample complexity per iteration is
$O(\varepsilon^{-4})$. Such algorithmic complexity aligns with the latest
complexity results in nonconvex bi-level stochastic optimization (Ji et al.,
2021). Due to the conflicting interests between the defender and the attacker
in FL, the ensuing BSMG is strictly competitive, which can be seen as a
generalization of zero-sum. Therefore, meta-SL does not require second-order
derivatives of the attacker’s value function (the low-level problem), even
though the Hessian of the defender’s value function remains due to the meta
adaptation. Inspired by Reptile (Nichol et al., 2018), a first-order meta-
learning algorithm, we propose a fully first-order pre-training algorithm,
referred to as Reptile Meta-SL, as a substitute for meta SL in our
experiments. Reptile Meta-SL uses only the first-order stochastic gradients of
the attacker’s and defender’s objective functions to solve for the approximate
equilibrium. As evidenced by numerical results in Section 5 and Appendix, it
is effective in managing adaptive and/or uncertain (or unknown) attacks.

Our contributions can be summarized as follows, with the discussion of related
work relocated to the Appendix due to space constraints:

  * •

We tackle vital security issues in federated learning in the face of multiple
adaptive (non-adaptive) attackers of uncertain or unknown types.

  * •

We formulate a Bayesian Stackelberg game model (Section 2.2) to encapsulate
the information asymmetry in adversarial FL under uncertain or unknown
adaptive attacks.

  * •

To provide the defender with strategic adaptability, we introduce a new
equilibrium concept, the meta-Stackelberg equilibrium (Definition 3.1). Here,
the defender (the leader) commits to a meta policy and an adaptation strategy,
leading to a data-driven method to handle information asymmetry.

  * •

To learn the meta equilibrium defense during the pre-training phase, we
develop meta-Stackelberg learning (Algorithm 2), an efficient first-order meta
RL algorithm. This algorithm provably converges to $\varepsilon$-approximate
equilibrium in $O(\varepsilon^{-2})$ gradient steps with $O(\varepsilon^{-4})$
samples per iteration, matching the state-of-the-art efficiency in stochastic
bilevel optimization.

  * •

We carry out comprehensive experiments in real-world scenarios to demonstrate
the outstanding performance of our proposed method.

##  2 Model Formulation

###  2.1 Federated Learning and Threat Model

FL objective. Consider a learning system that includes one server and $n$
clients, each client possesses its own private dataset
$D_{i}={(x_{i}^{j},y_{i}^{j})_{j=1}^{|D_{i}|}}$ and $|D_{i}|$ signifies the
size of the dataset for the $i$-th client. Let
$U=\\{D_{1},D_{2},\dots,D_{n}\\}$ represent the compilation of all client
datasets. The objective of federated learning is defined as identifying a
model $w$ that minimizes the average loss across all the devices:
$\min_{w}F(w,U):=\frac{1}{n}\sum_{i=1}^{n}f(w,D_{i})$, where
$f(w,D_{i}):=\frac{1}{|D_{i}|}\sum_{j=1}^{|D_{i}|}\ell(w,(x_{i}^{j},y_{i}^{j}))$
is the local empirical loss with $\ell(\cdot,\cdot)$ being the loss function.

Attack objective. We consider two major categories of attacks, namely,
backdoor attacks and untargeted model poisoning attacks. Our framework can be
extended to other attack scenarios. For simplicity, assume that the first
$M_{1}$ malicious clients carry out the backdoor attack and the following
$M_{2}$ malicious clients undertake the poisoning attack. The model poisoning
attack aims to maximize the average model loss, i.e., $\max_{w}F(w)$; the
backdoor attack aims to preserve decent performance on clean test inputs
(“main task”) while causing misclassification of poisoned test inputs to one
or more target labels (“backdoor task”). Each malicious client in the backdoor
attack produces a poisoned data set $D^{\prime}_{i\leq M_{1}}$, obtained by
altering a subset of data samples $(x_{i}^{j},y_{i}^{j})\in D_{i}$ to
$(\hat{x}^{j}_{i},c^{*})$, where $\hat{x}^{j}_{i}$ is the tainted sample with
a backdoor trigger inserted, and $c^{*}\neq y^{j}_{i},c^{*}\in C$ is the
targeted label. Let
$U^{\prime}=\\{D^{\prime}_{1},D^{\prime}_{2},\dots,D^{\prime}_{M_{1}}\\}$
denote the compilation of poisoned datasets. The objective function in the
backdoor attack is defined as: $\min_{w}F^{\prime}(w)=\lambda
F(w,U)+(1-\lambda)F(w,U^{\prime})$, where $\lambda\in[0,1]$ serves to balance
between the main task and the backdoor task.

FL process. The federated learning process works in an adversarial setting as
follows. At each round $t$ out of $H$ FL rounds, the server randomly selects a
subset of clients $\mathcal{S}^{t}$ and sends them the most recent global
model $w_{g}^{t}$. Every benign client in $\mathcal{S}^{t}$ updates the model
using their local data via one or more iterations of stochastic gradient
descent and returns the model update $g^{t}$ to the server. Conversely, an
adversary in $\mathcal{S}^{t}$ creates a malicious model update
$\widetilde{g}^{t}$ clandestinely and sends it back. The server then collects
the set of model updates
$\\{{\widetilde{g}_{i}^{t}}\cup{\widetilde{g}_{j}^{t}}\cup{g_{k}^{t}}\\}_{i,j,k\in\mathcal{S}^{t},i\in[M_{1}],j\in[M_{2}],k\notin[M_{1}]\cup[M_{2}]}$,
utilizing an aggregation rule $Aggr$ to combine them and updates the global
model
$w_{g}^{t+1}=w_{g}^{t}-Aggr({\widetilde{g}_{i}^{t}}\cup{\widetilde{g}_{j}^{t}}\cup{g_{k}^{t}})$,
which is then sent to clients in round $t+1$. At the final round $T$, the
server applies a post-training defense $h(\cdot)$ on the global model to
generate the final global model $\widehat{w}_{g}^{T}=h(w_{g}^{T})$.

Attacker type and behavior. We anticipate multiple types of attacks occurring
simultaneously, emanating from various categories. For clarity, we consider a
single mastermind attacker present within the FL system who controls a group
of malicious clients employing diverse attack strategies, which may be either
non-adaptive or adaptive. Non-adaptive attacks involve a fixed attack strategy
that solves a short-sighted optimization problem, disregarding the defense
mechanism implemented by the server (i.e., the robust aggregation rule and the
post-training defense). Such attacks include explicit boosting (EB) (Bhagoji
et al., 2019), inner product manipulation (IPM) (Xie et al., 2020), and local
model poisoning attack (LMP) (Fang et al., 2020)), federated backdoor attack
(BFL) (Bagdasaryan et al., 2020), distributed backdoor attack (DBA) (Xie et
al., 2019), projected gradient decent (PGD) backdoor attack (Wang et al.,
2020). On the other hand, an adaptive attack, such as the RL-based model
poisoning attack (Li et al., 2022a) and RL-based backdoor attack (Li et al.,
2023a), designs model updates by simulating the server’s reactions to optimize
a long-term objective. These adaptive and non-adaptive untargeted/backdoor
attack methods mentioned above constitute the attack domain in our adversarial
FL setting. One significant hurdle in addressing adversarial attacks is the
information asymmetry (Li et al., 2022d). This is when the server (i.e., the
defender) lacks knowledge of the behavior and identities of malicious clients
in a realistic black-box scenario. We denote the collective attack
configuration of malicious clients as the type of the mastermind attacker,
detailing $M_{1},M_{2}$, attack behaviors (adaptive or not), and other
required parameters of the attack method.

###  2.2 Bayesian Stackelberg Markov Game Model

In this study, we propose a comprehensive framework for robust defense against
potent unknown or uncertain attacks. The central principle is to construct RL-
based defenses by simulating unknown attack behavior using RL-based attacks.
As demonstrated in prior research (Li et al., 2022a, 2023a), RL-based attacks
serve as a robust baseline for both model poisoning and backdoor attacks.
Therefore, a defense that is resilient to RL-based attacks could potentially
safeguard the system against other (less potent) attacks. To manage the high-
dimensional state and action spaces, we integrate a set of lightweight
defenses in the training stage and post-training stage. The groundbreaking
element of our approach is the use of RL to optimize these defenses, moving
away from the conventional fixed and manually-tuned hyperparameters. This
approach requires a Bayesian Stackelberg Markov game formulation, encapsulated
in the tuple $G=(\mathcal{P},Q,S,O,A,\mathcal{T},r,\gamma)$, where
$\gamma\in(0,1)$ is the reward discounting factor:

  * •

The player set $\mathcal{P}=\\{\mathcal{D},\mathcal{A}\\}$ contains
$\mathcal{D}$ as the leader (defender), and $\mathcal{A}$ as the follower
(attacker) who controls multiple malicious clients.

  * •

$Q(\cdot):\Xi\to[0,1]$ denotes the probability distribution over the
attacker’s private types. $\Xi:=\\{\xi_{i}\\}_{i=1}^{|\Xi|}$ where $\xi_{i}$
denotes $i$-th type attacks.

  * •

$O$ is the observation space; the observation for the server (i.e., defender)
at round $t$ is $w^{t}_{g}$ (the server does not have access to the client’s
identities); the observation for the attacker at round $t$ is
$s^{t}:=(w^{t}_{g},\mathbf{I}^{t})$ since the attacker controls these
malicious clients. $\mathbf{I}^{t}\in\\{0,1\\}^{|\mathcal{S}^{t}|}$ is the
identity vector for the random client subset
$\mathcal{S}^{t}\subseteq\\{1,\ldots,n\\}$, where the identities of malicious
and benign devices are $1$ and $0$ respectively. Notice that the clients’
identities are independent of players’ actions.

  * •

$A=\\{A_{\mathcal{D}},A_{\xi}\\}$ is the joint action set, where
$A_{\mathcal{D}}$ and $A_{\xi}$ denote the set of defense actions and
type-$\xi$ attack actions, respectively; in the FL setting,
$a_{\mathcal{D}}^{t}=\widehat{w}_{g}^{t+1}:=h({w}_{g}^{t+1})$. The attacker’s
action is characterized by the joint actions of malicious clients
$a^{t}_{A_{\xi}}:=\\{\widetilde{g}_{i}^{t}\\}_{i=1}^{M_{1}}\cup\\{\widetilde{g}_{i}^{t}\\}_{i=M_{1}+1}^{M_{2}}$.
Note that a malicious device not sampled at round $t$ does not send any
information to the server; hence its action has no effect on the model update.
The subscript $\xi$ is suppressed if it is clear from the context.

  * •

$\mathcal{T}:S\times A\rightarrow\Delta(S)$ is the state transition function,
which represents the probability of reaching a state $s^{\prime}\in S$ from
current state $s\in S$, where the defender and the attacker chose actions
$a^{t}_{\mathcal{D}}$ and $a^{t}_{A_{\xi}}$ respectively.

  * •

$r=\\{r_{\mathcal{D}},r_{\mathcal{A}_{\xi}}\\}$, where
$r_{\mathcal{D}}:S\times A\rightarrow\mathbb{R}_{\leq 0}$ and
$r_{\mathcal{A}_{\xi}}:S\times A\rightarrow\mathbb{R}$ are the reward
functions for the defender and the attacker, respectively. Define the expected
reward at round $t$ as
$r_{\mathcal{D}}^{t}:=-\mathbb{E}[F(\widehat{w}^{t+1}_{g})]$ and
$r_{\mathcal{A}_{\xi}}^{t}:=\rho\mathbb{E}[F^{\prime}(\widehat{w}^{t+1}_{g})]-(1-\rho)\mathbb{E}[F(\widehat{w}^{t+1}_{g})]$,
$\rho=M_{1}/(M_{1}+M_{2})$, if $\mathbf{1}\cdot\mathbf{I}^{t}>0$, and
$r^{t}_{\mathcal{A}_{\xi}}:=0$ otherwise.

##  3 Meta-Stackelberg Equilibrium

Let the defender’s and the attacker’s policies be parameterized by neural
networks $\pi_{\mathcal{D}}(a_{\mathcal{D}}^{t}|s^{t};\theta)$,
$\pi_{\mathcal{A}}(a_{\mathcal{A}}^{t}|s^{t};\phi)$ with model weights
$\theta\in\Theta$ and $\phi\in\Phi$, respectively. Given the two players’
policies $\theta$, $\phi$ and the private attack type $\xi$, the defender’s
expected utility is defined as
$J_{\mathcal{D}}(\theta,\phi,\xi):=\mathbb{E}_{a_{\mathcal{A}}^{t}\sim\pi_{\mathcal{A}}(\cdot;\phi,\xi),a_{\mathcal{D}}^{t}\sim\pi_{\mathcal{D}}(\cdot;\theta)}[\sum_{t=1}^{H}\gamma^{t}r_{\mathcal{D}}(s^{t},a_{\mathcal{D}}^{t},a_{\mathcal{A}}^{t})]$.
Similarly, the attacker’s expected utility is
$J_{\mathcal{A}}(\theta,\phi,\xi):=\mathbb{E}_{a_{\mathcal{A}}^{t}\sim\pi_{\mathcal{A}}(\cdot;\phi,\xi),a_{\mathcal{D}}^{t}\sim\pi_{\mathcal{D}}(\cdot;\theta)}[\sum_{t=1}^{H}\gamma^{t}r_{\mathcal{A}}(s^{t},a_{\mathcal{D}}^{t},a_{\mathcal{A}}^{t})]$.
Denote by
$\tau_{\xi}:=(s^{k},a^{k}_{\mathcal{D}},a^{k}_{\mathcal{A}})_{k=1}^{H}$ the
trajectory of the BSMG under type-$\xi$ attacker, which is subject to the
distribution
$q(\theta,\phi,\xi):=\prod_{t=1}^{H}\pi_{\mathcal{D}}(a_{\mathcal{D}}^{t}|s^{t};\theta)\pi_{\mathcal{A}}(a^{t}_{\mathcal{A}}|s^{t};\phi,\xi)\mathcal{T}(s^{t+1}|s^{t},a_{\mathcal{D}}^{t},a_{\mathcal{A}}^{t})$.
In the later development of meta-SG, we consider the gradient
$\nabla_{\theta}J_{\mathcal{D}}(\theta,\phi,\xi)$ and its sample estimate
$\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau_{\xi})$ based on the trajectory
$\tau_{\xi}$. The estimation is due to the policy gradient theorem (Sutton et
al., 2000) reviewed in Appendix D, and we note that such an estimate takes a
batch of $\tau_{\xi}$ (the batch size is $N_{b}$) for variance reduction. For
simplicity, we use the one-trajectory estimate denoted by
$\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau_{\xi})$.

A natural defense strategy to tackle the information asymmetry is to find a
Bayesian Stackelberg equilibrium (BSE):

$\displaystyle\quad\max_{\theta\in\Theta}\mathbb{E}_{\xi\sim
Q(\cdot)}[J_{\mathcal{D}}(\theta,\phi^{*}_{\xi},\xi)]\quad$ (1)
$\displaystyle\text{s.t. }\phi_{\xi}^{*}\in\arg\max
J_{\mathcal{A}}(\theta,\phi,\xi),\forall\xi\in\Xi.$

(1) admits a simple characterization for optimal defense, yet its limitation
is evident. The attacker’s actions (equivalently, the aggregated models)
reveal partial information about its hidden type (its attack objective), which
the defender does not properly handle, as the strategy is fixed throughout the
BSMG. Consequently, the defender does not adapt to the specific attacker in
the online execution.

To equip the defender with responsive intelligence in the face of unknown
multi-type attacks, we propose a new equilibrium concept, meta-Stackelberg
equilibrium in Definition 3.1. The intuition of this meta-equilibrium is that
$\Psi(\theta,\tau_{\xi})$ is tailored to each realized $\xi$ when the defender
observes the attacker’s moves included in $\tau_{\xi}$.

######  Definition 3.1 (Meta Stackelberg Equilibrium).

A triple of the defender’s meta policy $\theta$, the adaptation mapping
$\Psi$, and the attacker’s type-dependent policy $\phi$ is a meta Stackelberg
equilibrium if it satisfies

$\displaystyle\quad\max_{\theta\in\Theta,\Psi}V(\theta):=\mathbb{E}_{\xi\sim
Q}\mathbb{E}_{\tau\sim
q}[J_{\mathcal{D}}(\Psi(\theta,\tau),\phi^{*}_{\xi},\xi)],$ (2)
$\displaystyle\text{s.t. }\phi^{*}_{\xi}\in\arg\max\mathbb{E}_{\tau\sim
q}J_{\mathcal{A}}(\Psi(\theta,\tau),\phi,\xi),\forall\xi\in\Xi,$

where $q=q(\theta,\phi,\xi)$ is the trajectory distribution.

In practice, $\Psi(\theta,\tau)$ is simply fixed as a one-step (or multi-step,
see Appendix C) SGD operation, i.e.,
$\Psi(\theta,\tau)=\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau)$ to
leave $\theta$ as the only variable to be optimized. In comparison with meta-
defense and BSE-defense, the proposed meta-SE defense highlights strategic
adaptation in adversarial FL modeled by the BSMG. A detailed discussion on
this meta-equilibrium is deferred to Appendix B.

##  4 Meta-Stackelberg Learning

Based on the aforementioned meta-Stackelberg equilibrium, we introduce the
meta-learning-based defense approach (Li & Zheng, 2023) (referred to as the
meta-defense in the sequel) by considering non-adaptive attack methods. The
goal of meta-defense is to find a meta-policy and an adaptation rule such that
the adapted policy gives satisfying defense performance. The mathematical
characterization is presented in Appendix C.

The meta-defense framework includes three stages: pre-training, online
adaptation, and post-training. The pre-training stage is implemented in a
simulated environment (as discussed in our technical report), which allows
sufficient alternative training with trajectories generated from random
potential attacks, which includes both adaptive (e.g., RL-based attacks as
discussed in our technical report) and non-adaptive (e.g., IPM and LMP)
attacks. After obtaining a meta-policy, the defender will interact with the
real FL environment in the online adaptation stage to tune its defense policy
using feedback (i.e., rewards) received in the face of real attacks. In real-
world FL training, the server typically waits for $1\sim 10$ minutes before
receiving responses from the clients, allowing the defender to update the
defense policy using SGD in the interim. In the post-training stage, the
defender finally performs a post-training defense on the global model.

###  4.1 Robust FL via Meta-Stackelberg Learning

Even though meta-learning enables an adaptable defense, it fails to address
adaptative attacks in the online adaptation phase, e.g., the RL attacker
learns to evade the adapted defense. To create strategic online adaptation,
the defender needs to learn the Stackelberg equilibrium of the BSMG using
meta-learning, preparing itself for the worst possible case: adaptive attacks
in the online phase.

Inspired by a first-order meta-learning algorithm called Reptile (Nichol et
al., 2018), we propose Reptile meta-Stackelberg learning (meta-SL) defense
(Algorithm 2 solving for the BSMG) in adversarial FL. The algorithms start
from an initial meta-defense policy model $\theta^{0}$ and a set of initial
attack policies $\\{\phi_{i}\\}_{i\leq m}$ from the attack domain. Meta-SL
alternatively updates the defender’s and attacker’s policies, and each
iteration comprises three major steps. Step 1 attack sampling: in each
iteration, the algorithm first sample a batch of $K$ attacks from $Q(\xi)$.
Step 2 policy adaptation: for each attack, meta-SL adapts the defender’s
policy $\theta^{t}_{k}$ to the $k$-th attack by performing $l$-step gradient
descent to the defender’s value function (see Appendix C) with step size
$\eta$. Step 3 meta policy update: meta-SL first derives the attacker’s best
response policy for each sampled type by applying gradient descent to the
attacker’s value function until convergence. After this alternative learning,
the algorithm then performs $l$-step gradient descent to the defender’s value
function under the convergent attack policy (of each type) for adaptation.
Finally, the average of all adapted policies of the sampled attacks becomes
the new meta policy.

###  4.2 First-order Approximate Meta Equilibrium

Now we unfold the theoretical analysis for the pre-training stage, which we
refer to as meta-Stackelberg learning (meta-SL). The main task of meta-SL is
solving (LABEL:eq:meta-se), a bi-level optimization problem. We employ a bi-
level approach, applying gradient ascent to the upper-level problem (the
defender’s) where the gradient estimation involves the optimizer of the lower-
level problem (the attacker’s). The details are deferred to Appendix C.

In general, the meta-SE (Definition 3.1) may not be feasible (Nouiehed et al.,
2019), we hereby propose a weaker characterization that only involves the
first-order necessary conditions. To simplify our exposition, we let
$\mathcal{L}_{\mathcal{D}}(\theta,\phi,\xi):=\mathbb{E}_{\tau\sim
q}J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)$
and $\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi):=\mathbb{E}_{\tau\sim
q}J_{\mathcal{A}}(\theta+\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)$,
for a fixed type $\xi\in\Xi$.. In the sequel, we will assume
$\mathcal{L}_{\mathcal{D}}$ and $\mathcal{L}_{\mathcal{A}}$ to be continuously
twice differentiable and Lipschitz-smooth with respect to both $\theta$ and
$\phi$ as in (Li et al., 2022b), and the Lipschitz assumptions are deferred to
Appendix D.

######  Definition 4.1 ($\varepsilon$-meta First-Order Stackelberg
Equilibrium).

For a small $\varepsilon\in(0,1)$, a set of parameters
$(\theta^{*},\\{\phi^{*}_{\xi}\\}_{\xi\in\Xi})\in\Theta\times\Phi^{|\Xi|}$ is
a $\varepsilon$-meta First-Order Stackelbeg Equilibrium ($\varepsilon$-meta-
FOSE) of the meta-SG if it satisfies the following conditions for $\xi\in\Xi$,

$\displaystyle\max_{\theta\in\Theta\bigcap
B(\theta^{*})}\langle\nabla_{\theta}\mathcal{L}_{\mathcal{D}}(\theta^{*},\phi^{*}_{\xi},\xi),\theta-\theta^{*}\rangle$
$\displaystyle\leq\varepsilon,$ (3) $\displaystyle\max_{\phi\in\Phi\bigcap
B(\phi^{*}_{\xi})}\langle\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{*},\phi^{*}_{\xi},\xi),\phi-\phi^{*}_{\xi}\rangle$
$\displaystyle\leq\varepsilon,$

where $B(\theta^{*}):=\\{\theta\in\Theta:\|\theta-\theta^{*}\|\leq 1\\}$, and
$B(\phi^{*}_{\xi}):=\\{\theta\in\Theta:\|\phi-\phi^{*}_{\xi}\|\leq 1\\}$. When
$\varepsilon=0$, the parameter set
$(\theta^{*},\\{\phi^{*}_{\xi}\\}_{\xi\in\Xi})$ is said to be the meta-FOSE.

The necessary equilibrium condition for Definition 3.1 can be reduced to
$\|\nabla_{\theta}\mathcal{L}_{\mathcal{D}}(\theta^{*},\phi_{\xi},\xi)\|\leq\varepsilon$
and
$\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{*},\phi_{\xi},\xi)\|\leq\varepsilon$
in the unconstraint settings. Since we utilize stochastic gradient in
practice, all inequalities mentioned above shall be considered in expectation.
These conditions, along with the positive-semi-definiteness of the Hessians,
construct the optimality conditions for a local solution for the meta-SE,
which may not exist even in the zero-sum cases (Jin et al., 2019). The
advantage of considering meta-FOSE is that its existence is guaranteed.

######  Theorem 4.2.

Under the condition that $\Theta$ and $\Phi$ are compact and convex, the meta-
SG admits at least one meta-FOSE.

For the rest of this section, we assume the attacker is unconstrained, i.e.,
$\Phi$ is a finite-dimensional Euclidean space.

###  4.3 Sufficiency for First-Order Estimation in Strictly Competitive Games

Finding a meta-FOSE for (LABEL:eq:meta-se) is challenging due to the non-
convex equilibrium constraint at the lower level. To see this more clearly,
consider differentiating the defender’s value function:
$\nabla_{\theta}V=\mathbb{E}_{\xi\sim
Q}[\nabla_{\theta}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)+(\nabla_{\theta}\phi_{\xi}(\theta))^{\top}\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)]$,
where $\nabla_{\theta}\phi_{\xi}(\cdot)$ is locally characterized by the
implicit function theorem, i.e.,
$\nabla_{\theta}\phi_{\xi}(\theta)=(-\nabla^{2}_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi))^{-1}\nabla^{2}_{\phi\theta}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)$.
Therefore, the gradient estimation requires iteratively estimating the second-
order information for the attacker (lower level) objective, which can be
costly and prohibitive in many scenarios (Song et al., 2019). Hence, we
introduce the following assumption to bypass the technicality involved in
calculating $\nabla_{\theta}\phi_{\xi}$.

######  Assumption 4.3 (Strict-Competitiveness).

The BSMG is strictly competitive, i.e., there exist constants $c<0$, $d$ such
that $\forall\xi\in\Xi$, $s\in S$, $a_{\mathcal{D}},a_{\mathcal{A}}\in
A_{\mathcal{D}}\times A_{\xi}$,
$r_{\mathcal{D}}(s,a_{\mathcal{D}},a_{\mathcal{A}})=cr_{\mathcal{A}}(s,a_{\mathcal{D}},a_{\mathcal{A}})+d$.

The above assumption is a direct extension of the strict-competitiveness (SC)
notion in matrix games (Adler et al., 2009). One can treat the SC notion as a
generalization of zero-sum games: if one joint action
$(a_{\mathcal{D}},a_{\mathcal{A}})$ leads to payoff increases for one player,
it must decrease the other’s payoff. In adversarial FL, the untargeted attack
naturally makes the game zero-sum (hence, SC), and the backdoor attack also
leads to the SC (see Appendix D). The purpose of introducing 4.3 is to
establish the Danskin-type result (Bernhard & Rapaport, 1995) for the
Stackelberg game with nonconvex value functions (see Lemma 4.5), which spares
us from the Hessian inversion.

Another key regularity assumption we impose on the nonconvex value functions
is adapted from the Polyak-Łojasiewicz (PL) condition (Karimi et al., 2016),
which is customary in nonconvex analysis.

######  Assumption 4.4 (Stackelberg Polyak-Łojasiewicz condition).

There exists a positive constant $\mu$ such that for any
$(\theta,\phi)\in\Theta\times\Phi$ and $\xi\in\Xi$, the following inequalities
hold:
$\frac{1}{2\mu}\|\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi,\xi)\|^{2}\geq\max_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi,\xi)-\mathcal{L}_{\mathcal{D}}(\theta,\phi,\xi)$,
$\
\frac{1}{2\mu}\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)\|^{2}\geq\max_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)-\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)$.

Under 4.4, the first-order estimation is sufficient by Lemma 4.5.

######  Lemma 4.5.

Under Assumptions 4.4 and regularity conditions, there exists
$\\{\phi_{\xi}:\phi_{\xi}\in\arg\max_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)\\}_{\xi\in\Xi}$,
such that $\nabla_{\theta}V(\theta)=\nabla_{\theta}\mathbb{E}_{\xi\sim
Q,\tau\sim
q}J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi_{\xi},\xi)$.
Moreover, there exists a constant $L>0$ such that the defender value function
$V(\theta)$ is $L$-Lipschitz-smooth.

###  4.4 Non-Asymptotic Iteration Complexity

We now present the main iteration complexity results. Lemma 4.6 states that
one can stabilize the lower-level simulated RL attacks under mild conditions,
with proper choices of the batch size $(\mathcal{O}(\varepsilon^{-4}))$ and
the attacker learning iteration $(\mathcal{O}(\log\varepsilon^{-1}))$.
Moreover, the defender’s gradient feedback can be approximated using the last
iterate of the inner loop.

######  Lemma 4.6.

Under Assumption 4.4 and regularity assumptions. For any given
$\varepsilon\in(0,1)$, at any iteration $t\in 1,\ldots,N_{\mathcal{D}}$, if
the attacker learning iteration $N_{\mathcal{A}}$ and the batch size $N_{b}$
are large enough such that
$N_{\mathcal{A}}\sim\mathcal{O}(\log\varepsilon^{-1})$ and
$N_{b}\sim\mathcal{O}(\varepsilon^{-4})$, then, for any $\xi\in\Xi$, the
attack policy is stabilized, i.e.,

$\mathbb{E}\left[\max_{\phi}\langle\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi),\phi-\phi^{t}_{\xi}(N_{\mathcal{A}})\rangle\right]\leq\varepsilon.$

Further, the defender’s gradient feedback can be $\varepsilon$-approximated,
i.e.,

$\mathbb{E}\left[\|\nabla_{\theta}V(\theta^{t})-\nabla_{\theta}\mathbb{E}_{\xi\sim
Q}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)\|\right]\leq\varepsilon,$

where the expectation $\mathbb{E}[\cdot]$ is taken over all the randomness
from the algorithm.

Equipped with Lemma 4.6, we apply the standard analysis for first-order
methods in a non-convex setting to the outer loop, leading to the main
complexity result in Theorem 4.7.

######  Theorem 4.7.

Under assumption 4.4 and regularity assumptions, for any given
$\varepsilon\in(0,1)$, let the learning rates $\kappa_{\mathcal{A}}$ and
$\kappa_{\mathcal{D}}$ be properly chosen (see Appendix D); let
$N_{\mathcal{A}}$ and $N_{b}$ be chosen as required by Lemma 4.6, then, meta-
SL finds a $\varepsilon$-meta-FOSE within
$N_{\mathcal{D}}\sim\mathcal{O}(\varepsilon^{-2})$ iterations.

Theorem 4.7 implies that meta-SL requires
$\mathcal{O}(\varepsilon^{-2}\log\varepsilon^{-1})$ iterations of first-order
evaluation, which matches the $\Omega(\varepsilon^{-2})$ lower bound for the
general non-convex smooth setting (Carmon et al., 2020), (up to a logarithmic
factor) indicating the efficiency of meta-SL.

##  5 Experiments

For the detailed setup of the experiment and corresponding results, please
refer to our technical report (Li et al., 2023b). In our experiments, we
evaluate our meta-SG defense using the MNIST (LeCun et al., 1998) and CIFAR-10
(Krizhevsky et al., 2009) datasets. The evaluation is performed under a range
of advanced attacks, including non-adaptive and adaptive untargeted model
poisoning attacks (specifically, IPM (Xie et al., 2020), LMP (Fang et al.,
2020), RL (Li et al., 2022a)), backdoor attacks (BFL (Bagdasaryan et al.,
2020), BRL (Li et al., 2023a)), and a combination thereof. Various robust
defenses are taken into account as baselines, including training-stage
defenses such as Krum (Blanchard et al., 2017), Clipping Median (Yin et al.,
2018; Sun et al., 2019; Li et al., 2022a), FLTrust (Cao et al., 2021), and
post-training defenses like Neuron Clipping (Wang et al., 2022), Pruning (Wu
et al., 2020).

(a)

(b)

Figure 2: Advantages of the Meta-SG framework against (a) the RL-based model
poisoning attack (Li et al., 2022a) on MNIST with $20\%$ malicious devices and
(b) a mix of the backdoor attack against FL (BFL) (Bagdasaryan et al., 2020)
($5\%$ malicious devices) and the inner product manipulation (IPM) based model
poisoning attack (Xie et al., 2020) ($10\%$ malicious devices) on CIFAR-10.
The baseline defense combines the training-stage FLTrust and the post-training
Neuron Clipping.

As shown in Figure 2(a), meta-SG demonstrates excellent accuracy in federated
learning models when facing the RL-based model poisoning attack. Furthermore,
as seen in Figure 2(b), meta-SG maintains high model accuracy for unpoisoned
data and significantly lowers backdoor accuracy in scenarios involving both
backdoor and model poisoning attacks. In contrast, the baseline defense that
merely combines a training-stage defense with a post-training defense leads to
low model accuracy and fails to shield the FL system from a backdoor attack.
Due to the page limit, more experiment results are deferred to our technical
report (Li et al., 2023b).

##  6 Conclusion and Future Work

In this work, we have proposed a data-driven approach to tackle information
asymmetry in adversarial federated learning, which can also be applied to a
variety of scenarios in adversarial machine learning, where information
asymmetry is prevalent. We have offered a meta-equilibrium solution concept
that is computationally tractable and strategically adaptable. In addition,
theoretical guarantees on sample complexity and convergence rate have been
established under mild assumptions, indicating the computational efficiency of
training the meta-equilibrium-based FL defense.

## References

  * Adler et al. (2009) Adler, I., Daskalakis, C., and Papadimitriou, C. H.  A Note on Strictly Competitive Games.  In _Internet and Network Economics_ , pp. 471–474, 2009.  ISBN 9783642108402.  doi: 10.1007/978-3-642-10841-9\\_44.
  * Bagdasaryan et al. (2020) Bagdasaryan, E., Veit, A., Hua, Y., Estrin, D., and Shmatikov, V.  How to backdoor federated learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2938–2948. PMLR, 2020.
  * Baruch et al. (2019) Baruch, G., Baruch, M., and Goldberg, Y.  A little is enough: Circumventing defenses for distributed learning.  In _Advances in Neural Information Processing Systems(NeurIPS)_ , 2019\.
  * Bernhard & Rapaport (1995) Bernhard, P. and Rapaport, A.  On a theorem of Danskin with an application to a theorem of Von Neumann-Sion.  _Nonlinear Analysis: Theory, Methods & Applications_, 24(8):1163–1181, 1995.  ISSN 0362-546X.  doi: 10.1016/0362-546x(94)00186-l.
  * Bernstein et al. (2018) Bernstein, J., Zhao, J., Azizzadenesheli, K., and Anandkumar, A.  signsgd with majority vote is communication efficient and fault tolerant.  In _International Conference on Learning Representations(ICLR)_ , 2018\.
  * Bhagoji et al. (2019) Bhagoji, A. N., Chakraborty, S., Mittal, P., and Calo, S.  Analyzing federated learning through an adversarial lens.  In _International Conference on Machine Learning(ICML)_ , 2019.
  * Bhaskar et al. (2016) Bhaskar, U., Cheng, Y., Ko, Y. K., and Swamy, C.  Hardness results for signaling in bayesian zero-sum and network routing games.  In _Proceedings of the 2016 ACM Conference on Economics and Computation_ , pp. 479–496, 2016.
  * Blanchard et al. (2017) Blanchard, P., Guerraoui, R., Stainer, J., et al.  Machine learning with adversaries: Byzantine tolerant gradient descent.  In _Advances in Neural Information Processing Systems(NeurIPS)_ , 2017\.
  * Cao et al. (2021) Cao, X., Fang, M., Liu, J., and Gong, N. Z.  Fltrust: Byzantine-robust federated learning via trust bootstrapping.  In _NDSS_ , 2021.
  * Carmon et al. (2020) Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A.  Lower bounds for finding stationary points i.  _Mathematical Programming_ , 184(1-2):71–120, 2020.
  * Chen et al. (2023) Chen, Z., Kailkhura, B., and Zhou, Y.  An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization.  _Machine Learning_ , 112(5):1433–1463, 2023.  ISSN 0885-6125.  doi: 10.1007/s10994-023-06329-6.
  * Duan et al. (2016) Duan, Y., Schulman, J., Chen, X., Bartlett, P. L., Sutskever, I., and Abbeel, P.  Rl 2: Fast reinforcement learning via slow reinforcement learning.  _arXiv preprint arXiv:1611.02779_ , 2016.
  * Fallah et al. (2021) Fallah, A., Georgiev, K., Mokhtari, A., and Ozdaglar, A.  On the convergence theory of debiased model-agnostic meta-reinforcement learning, 2021.
  * Fang et al. (2020) Fang, M., Cao, X., Jia, J., and Gong, N.  Local model poisoning attacks to byzantine-robust federated learning.  In _29th USENIX Security Symposium_ , 2020.
  * Finn et al. (2017) Finn, C., Abbeel, P., and Levine, S.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International conference on machine learning_ , pp. 1126–1135. PMLR, 2017.
  * Fudenberg & Tirole (1991) Fudenberg, D. and Tirole, J.  _Game Theory_.  MIT Press, Cambridge, MA, 1991.
  * Ge et al. (2023) Ge, Y., Li, T., and Zhu, Q.  Scenario-Agnostic Zero-Trust Defense with Explainable Threshold Policy: A Meta-Learning Approach.  _arXiv preprint arXiv:2303.03349_ , 2023.
  * Geyer et al. (2017) Geyer, R. C., Klein, T., and Nabi, M.  Differentially private federated learning: A client level perspective.  _arXiv preprint arXiv:1712.07557_ , 2017.
  * Gupta et al. (2021) Gupta, A., Lanctot, M., and Lazaridou, A.  Dynamic population-based meta-learning for multi-agent communication with natural language.  _Advances in Neural Information Processing Systems_ , 34:16899–16912, 2021.
  * Harris et al. (2022) Harris, K., Anagnostides, I., Farina, G., Khodak, M., Wu, Z. S., and Sandholm, T.  Meta-learning in games.  _arXiv preprint arXiv:2209.14110_ , 2022.
  * Ji et al. (2021) Ji, K., Yang, J., and Liang, Y.  Bilevel optimization: Convergence analysis and enhanced design.  In _International conference on machine learning_ , pp. 4882–4892. PMLR, 2021.
  * Jin et al. (2019) Jin, C., Netrapalli, P., and Jordan, M. I.  Minmax optimization: Stable limit points of gradient descent ascent are locally optimal.  _ArXiv_ , abs/1902.00618, 2019.
  * Karimi et al. (2016) Karimi, H., Nutini, J., and Schmidt, M.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16_ , pp. 795–811. Springer, 2016.
  * Kayaalp et al. (2022) Kayaalp, M., Vlaski, S., and Sayed, A. H.  Dif-maml: Decentralized multi-agent meta-learning.  _IEEE Open Journal of Signal Processing_ , 3:71–93, 2022\.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kwon et al. (2023) Kwon, J., Kwon, D., Wright, S., and Nowak, R.  A Fully First-Order Method for Stochastic Bilevel Optimization.  _arXiv_ , 2023.  doi: 10.48550/arxiv.2301.10945.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Li & Zheng (2023) Li, H. and Zheng, Z.  Robust moving target defense against unknown attacks: A meta-reinforcement learning approach.  In _Decision and Game Theory for Security: 13th International Conference, GameSec 2022, Pittsburgh, PA, USA, October 26–28, 2022, Proceedings_ , pp. 107–126. Springer, 2023.
  * Li et al. (2022a) Li, H., Sun, X., and Zheng, Z.  Learning to attack federated learning: A model-based reinforcement learning attack framework.  In _Advances in Neural Information Processing Systems_ , 2022a.
  * Li et al. (2023a) Li, H., Wu, C., Zhu, S., and Zheng, Z.  Learning to backdoor federated learning.  _arXiv preprint arXiv:2303.03320_ , 2023a.
  * Li et al. (2023b) Li, H., Xu, T., Li, T., Pan, Y., Zhu, Q., and Zheng, Z.  A first order meta stackelberg method for robust federated learning (technical report).  _arXiv preprint arXiv:2306.13273_ , 2023b.
  * Li & Zhu (2023) Li, T. and Zhu, Q.  On the Price of Transparency: A Comparison between Overt Persuasion and Covert Signaling.  _arXiv preprint arXiv:2304.00096_ , 2023.
  * Li et al. (2022b) Li, T., Lei, H., and Zhu, Q.  Sampling attacks on meta reinforcement learning: A minimax formulation and complexity analysis.  _arXiv preprint arXiv:2208.00081_ , 2022b.
  * Li et al. (2022c) Li, T., Peng, G., Zhu, Q., and Baar, T.  The Confluence of Networks, Games, and Learning a Game-Theoretic Framework for Multiagent Decision Making Over Networks.  _IEEE Control Systems_ , 42(4):35–67, 2022c.  ISSN 1066-033X.  doi: 10.1109/mcs.2022.3171478.
  * Li et al. (2022d) Li, T., Zhao, Y., and Zhu, Q.  The role of information structures in game-theoretic multi-agent learning.  _Annual Reviews in Control_ , 53:296–314, 2022d.  ISSN 1367-5788.  doi: 10.1016/j.arcontrol.2022.03.003.
  * Manshaei et al. (2013) Manshaei, M. H., Zhu, Q., Alpcan, T., Bacşar, T., and Hubaux, J.-P.  Game theory meets network security and privacy.  _ACM Comput. Surv._ , 45(3), jul 2013.  ISSN 0360-0300.  doi: 10.1145/2480741.2480742.  URL https://doi.org/10.1145/2480741.2480742.
  * McMahan et al. (2017) McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics (AISTATS)_ , pp. 1273–1282. PMLR, 2017.
  * Nguyen et al. (2021) Nguyen, T. D., Rieger, P., Chen, H., Yalame, H., Möllering, H., Fereidooni, H., Marchal, S., Miettinen, M., Mirhoseini, A., Zeitouni, S., et al.  Flame: Taming backdoors in federated learning.  _Cryptology ePrint Archive_ , 2021.
  * Nichol et al. (2018) Nichol, A., Achiam, J., and Schulman, J.  On first-order meta-learning algorithms.  _arXiv preprint arXiv:1803.02999_ , 2018.
  * Nouiehed et al. (2019) Nouiehed, M., Sanjabi, M., Huang, T., Lee, J. D., and Razaviyayn, M.  Solving a class of non-convex min-max games using iterative first order methods, 2019.
  * Pillutla et al. (2022) Pillutla, K., Kakade, S. M., and Harchaoui, Z.  Robust aggregation for federated learning.  _IEEE Transactions on Signal Processing_ , 70:1142–1154, 2022.
  * Rieger et al. (2022) Rieger, P., Nguyen, T. D., Miettinen, M., and Sadeghi, A.-R.  Deepsight: Mitigating backdoor attacks in federated learning through deep model inspection.  _arXiv preprint arXiv:2201.00763_ , 2022.
  * Shejwalkar & Houmansadr (2021) Shejwalkar, V. and Houmansadr, A.  Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning.  In _NDSS_ , 2021.
  * Shen et al. (2021) Shen, W., Li, H., and Zheng, Z.  Coordinated attacks against federated learning: A multi-agent reinforcement learning approach.  In _ICLR 2021 Workshop on Security and Safety in Machine Learning Systems (SecML)_ , 2021.
  * Song et al. (2019) Song, X., Gao, W., Yang, Y., Choromanski, K., Pacchiano, A., and Tang, Y.  Es-maml: Simple hessian-free meta learning.  _arXiv preprint arXiv:1910.01215_ , 2019.
  * Sun et al. (2019) Sun, Z., Kairouz, P., Suresh, A. T., and McMahan, H. B.  Can you really backdoor federated learning?  _arXiv preprint arXiv:1911.07963_ , 2019.
  * Sutton et al. (2000) Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y.  Policy gradient methods for reinforcement learning with function approximation.  In _Advances in Neural Information Processing Systems 12_ , pp. 1057—1063. MIT press, 2000.
  * Wang et al. (2020) Wang, H., Sreenivasan, K., Rajput, S., Vishwakarma, H., Agarwal, S., Sohn, J.-y., Lee, K., and Papailiopoulos, D.  Attack of the tails: Yes, you really can backdoor federated learning.  _Advances in Neural Information Processing Systems_ , 33:16070–16084, 2020.
  * Wang et al. (2022) Wang, H., Xiang, Z., Miller, D. J., and Kesidis, G.  Universal post-training backdoor detection.  _arXiv preprint arXiv:2205.06900_ , 2022.
  * Wu et al. (2020) Wu, C., Yang, X., Zhu, S., and Mitra, P.  Mitigating backdoor attacks in federated learning.  _arXiv preprint arXiv:2011.01767_ , 2020.
  * Xie et al. (2019) Xie, C., Huang, K., Chen, P.-Y., and Li, B.  Dba: Distributed backdoor attacks against federated learning.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Xie et al. (2020) Xie, C., Koyejo, O., and Gupta, I.  Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation.  In _Uncertainty in Artificial Intelligence (UAI)_ , pp. 261–270. PMLR, 2020.
  * Yin et al. (2018) Yin, D., Chen, Y., Kannan, R., and Bartlett, P.  Byzantine-robust distributed learning: Towards optimal statistical rates.  In _International Conference on Machine Learning_ , pp. 5650–5659. PMLR, 2018.
  * Zhang et al. (2022) Zhang, X., Hu, C., He, B., and Han, Z.  Distributed reptile algorithm for meta-learning over multi-agent systems.  _IEEE Transactions on Signal Processing_ , 70:5443–5456, 2022.
  * Zhao & Zhu (2022) Zhao, Y. and Zhu, Q.  Stackelberg meta-learning for strategic guidance in multi-robot trajectory planning.  _arXiv preprint arXiv:2211.13336_ , 2022.

##  Appendix A Broader Impacts and Limitations

Meta Equilibrium and Information Asymmetry. Information asymmetry is a
prevailing phenomenon arising in a variety of contexts, including adversarial
machine learning (e.g. FL discussed in this work), cyber security (Manshaei et
al., 2013), and large-scale network systems (Li et al., 2022c). Our proposed
meta-equilibrium (Definition 3.1) offers a data-driven approach tackling
asymmetric information structure in dynamic games without Bayesian-posterior
beliefs (see Appendix B). Achieving the strategic adaptation through
stochastic gradient descent, the meta-equilibrium is computationally superior
to perfect Bayesian equilibrium and better suited for real-world engineering
systems involving high-dimensional continuous parameter spaces. It is expected
that the meta-equilibrium can also be relevant to other adversarial learning
contexts, cyber defense, and decentralized network systems.

First-order Method with Strict Competitiveness. Due to the hardness of the
stochastic bilevel optimization problem, we have expanded our search scope
with an alternative solution concept that merely involves the first-order
necessary conditions for meta-SE. Our analytical result relies on the special
game structure induced by the strict competitiveness assumption, which
essentially “aligns” the defender/attacker objectives leveraging the nature of
policy gradient, despite them being general-sum. Relaxing this assumption
allows our framework to deal with a more general class of problems, yet may
potentially disrupt the Danskin-type structure of gradient estimation. For
simplicity of exposition, we neglected the stochastic analysis for the
defender policy gradient estimation in the outer loop of the algorithm, the
concentration of which depends on the trajectory batch size and attacker-type
sample size. We leave the outer loop sample-complexity analysis to future
work.

Incomplete Universal Defense. Our aim is to establish a comprehensive
framework for universal federated learning defense. This framework ensures
that the server remains oblivious to any details pertaining to the environment
or potential attackers. Still, it possesses the ability to swiftly adapt and
respond to uncertain or unknown attackers during the actual federated learning
process. Nevertheless, achieving this universal defense necessitates an
extensive attack set through pre-training, which often results in a protracted
convergence time toward a meta-policy. Moreover, the effectiveness and
efficiency of generalizing from a wide range of diverse attack distributions
pose additional challenges. Considering these, we confine our experiments in
this paper to specifically address a subset of uncertainties and unknowns.
This includes parameters that determine attack types, the number of malicious
devices, the heterogeneity of local data distributions, backdoor triggers,
backdoor targets, and other relevant aspects. However, we acknowledge that our
focus is not all-encompassing, and there may be other factors that remain
unexplored in our research.

##  Appendix B Further Justification on Meta Equilibrium

This section offers further justification for the meta-equilibrium, and we
argue that meta-equilibrium provides a data-driven approach to address
incomplete information in dynamic games. Note that information asymmetry is
prevalent in the adversarial machine learning context, where the attacker
enjoys an information advantage (e.g., the attacker’s type). The proposed
meta-equilibrium notion can shed light on these related problems beyond the
adversarial FL context.

We begin with the insufficiency of Bayesian Stackelberg equilibrium (1) in
handling information asymmetry, a customary solution concept in security
studies (Li et al., 2022d). One can see from (1) that such an equilibrium is
of ex-ante type: the defender’s strategy is determined before the game starts.
It targets an “representative” attacker (an average of all types). As the game
unfolds, new information regarding the attacker’s private type is revealed
(e.g., through the global model updates). However, this ex-ante strategy does
not enable the defender to handle this emerging information as the game
proceeds. Using game theory language, the defender fails to adapt its strategy
in the interim stage.

To create interim adaptability in this dynamic game of incomplete information,
one can consider introducing the belief system to capture the defender’s
learning process on the hidden type. Let $I^{t}$ be the defender’s
observations up to time $t$, i.e.,
$I^{t}:=(s^{k},a_{\mathcal{D}}^{k})_{k=1}^{t}s^{t+1}$. Denote by $\mathcal{B}$
the belief generation operator $b^{t+1}(\xi)=\mathcal{B}[I^{t}]$. With the
Bayesian equilibrium framework, the belief generation can be defined
recursively as below

$\displaystyle
b^{t+1}(\xi)=\mathcal{B}[s^{t},a^{t}_{\mathcal{D}},b^{t}]:=\frac{b^{t}(\xi)\pi_{\mathcal{A}}(a^{t}_{\mathcal{A}}|s^{t};\xi)\mathcal{T}(s^{t+1}|s^{t},a^{t}_{\mathcal{A}},a^{t}_{\mathcal{D}})}{\sum_{\xi^{\prime}}b^{t}(\xi^{\prime})\pi_{\mathcal{A}}(a^{t}_{\mathcal{A}}|s^{t};\xi^{\prime})\mathcal{T}(s^{t+1}|s^{t},a^{t}_{\mathcal{A}},a^{t}_{\mathcal{D}})}.$
(B1)

Since $b^{t}$ is the defender’s belief on the hidden type at time $t$, its
belief-dependent Markovian strategy is defined as
$\pi_{\mathcal{D}}(s^{t},b^{t})$. Therefore, the interim equilibrium, also
called Perfect Bayesian Equilibrium (PBE) (Fudenberg & Tirole, 1991) is given
by a tuple
$(\pi^{*}_{\mathcal{D}},\pi^{*}_{\mathcal{A}},\\{b^{t}\\}_{t=1}^{H})$
satisfying

$\displaystyle\pi_{\mathcal{D}}^{*}=\arg\max\mathbb{E}_{\xi\sim
Q}\mathbb{E}_{\pi_{\mathcal{D}},\pi^{*}_{\mathcal{A}}}[\sum_{t=1}^{H}r_{\mathcal{D}}(s^{t},a_{\mathcal{D}}^{t},a_{\mathcal{A}}^{t})b^{t}(\xi)]$
(PBE)
$\displaystyle\pi_{\mathcal{A}}^{*}=\arg\max\mathbb{E}_{\pi_{\mathcal{D}},\pi_{\mathcal{A}}}[\sum_{t=1}^{H}r_{\mathcal{A}}(s^{t},a_{\mathcal{D}}^{t},a_{\mathcal{A}}^{t})],\forall\xi,$
$\displaystyle\\{b^{k}\\}_{k=1}^{H}\text{ satisfies }\eqref{eq:belief}\text{
for realized actions and states}.$

In contrast with (1), this perfect Bayesian equilibrium notion (PBE) enables
the defender to make good use of the information revealed by the attacker, and
subsequently adjust its actions according to the revealed information through
the belief generation. From a game-theoretic viewpoint, both (PBE) and
(LABEL:eq:meta-se) create strategic online adaptation: the defender can infer
and adapt to the attacker’s private type through the revealed information
since different types aim at different objectives, hence, leading to different
actions. Compared with PBE, the proposed meta-equilibrium notion is better
suited for large-scale complex systems where players’ decision variables can
be high-dimensional and continuous, as argued in the ensuing paragraph.

To achieve the strategic adaptation, PBE relies on the Bayesian-posterior
belief updates, which soon become intractable as the denominator in (B1)
involves integration over high-dimensional space and discretization inevitably
leads to the curse of dimensionality. Despite the limited practicality, PBE is
inherently difficult to solve even in finite-dimensional cases. It is shown in
(Bhaskar et al., 2016) that the equilibrium computation in games with
incomplete information is NP-hard, and how to solve for PBE in dynamic games
remains an open problem. Even though there have been encouraging attempts at
solving PBE in two-stage games (Li & Zhu, 2023), it is still challenging to
address PBE computation in generic Markov games.

##  Appendix C Algorithms

This section elaborates on meta-learning defense and meta-Stackelberg
learning. To begin with, we first review the policy gradient method (Sutton et
al., 2000) in RL and its Monte-Carlo estimation. To simplify our exposition,
we fix the attacker’s policy $\phi$, and then BSMG reduces to a single-agent
MDP, where the optimal policy to be learned is the defender’s $\theta$.

#### Policy Gradient

The idea of the policy gradient method is to apply gradient ascent to the
value function $J_{\mathcal{D}}$. Following (Sutton et al., 2000), we obtain
$\nabla_{\theta}J_{\mathcal{D}}:=\mathbb{E}_{\tau\sim
q(\theta)}[g(\tau;\theta)]$, where
$g(\tau;\theta)=\sum_{t=1}^{H}\nabla_{\theta}\log\pi(a_{\mathcal{D}}^{t}|s^{t};\theta)R(\tau)$
and $R(\tau)=\sum_{t=1}^{H}\gamma^{t}r(s^{t},a_{\mathcal{D}}^{t})$. Note that
for simplicity, we suppress the parameter $\phi,\xi$ in the trajectory
distribution $q$, and instead view it as a function of $\theta$. In numerical
implementations, the policy gradient $\nabla_{\theta}J_{\mathcal{D}}$ is
replaced by its Monte-Carlo (MC) estimation using sample trajectory. Suppose a
batch of trajectories $\\{\tau_{i}\\}_{i=1}^{N_{b}}$, and $N_{b}$ denotes the
batch size, then the MC estimation is

$\hat{\nabla}_{\theta}J_{\mathcal{D}}(\theta,\tau):=1/{N_{b}}\sum_{\tau_{i}}g(\tau_{i};\theta)$
(C1)

The same deduction also holds for the attacker’s problem when fixing the
defense $\theta$.

#### Meta-Learning FL Defense

Meta-learning-based defense (meta defense) mainly targets non-adaptive attack
methods, where $\pi_{\mathcal{A}}(\cdot;\phi,\xi)$ is a pre-fixed attack
strategy following some rulebook, such as IPM (Xie et al., 2020) and LMP (Fang
et al., 2020). In this case, the BSMG reduces to single-agent MDP for the
defender, where the transition kernel is determined by the attack method.
Mathematically, the meta-defense problem is given by

$\max_{\theta,\Psi}\mathbb{E}_{\xi\sim
Q(\cdot)}[J_{\mathcal{D}}(\Psi(\theta,\tau),\phi,\xi)]$ (C2)

Since the attack type is hidden from the defender, the adaptation mapping
$\Psi$ is usually defined in a data-driven manner. For example,
$\Psi(\theta,\tau)$ can be defined as a one-step stochastic gradient update
with learning rate $\eta$:
$\Psi(\theta,\tau)=\theta+\eta\hat{\nabla}J_{\mathcal{D}}(\tau_{\xi})$ (Finn
et al., 2017) or a recurrent neural network in (Duan et al., 2016). This work
mainly focuses on gradient adaptation for the purpose of deriving theoretical
guarantees in Appendix D.

With the one-step gradient adaptation, the meta-defense problem in (C2) can be
simplified as

$\max_{\theta}\mathbb{E}_{\xi\sim Q(\cdot)}\mathbb{E}_{\tau\sim
q(\theta)}[J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)]$
(C3)

Recall that the attacker’s strategy is pre-determined, $\phi,\xi$ can be
viewed as fixed parameters, and hence, the distribution $q$ is a function of
$\theta$. To apply the policy gradient method to (C3), one needs an unbiased
estimation of the gradient of the objective function in (C3). Consider the
gradient computation using the chain rule:

$\displaystyle\nabla_{\theta}\mathbb{E}_{\tau\sim
q(\theta)}[J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)]$
(C4) $\displaystyle=\mathbb{E}_{\tau\sim
q(\theta)}\\{\underbrace{\nabla_{\theta}J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)(I+\eta\hat{\nabla}^{2}_{\theta}J_{D}(\tau))}_{\text{\char
172}}$
$\displaystyle\quad+\underbrace{J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau))\nabla_{\theta}\sum_{t=1}^{H}\pi(a^{t}|s^{t};\theta)}_{\text{\char
173}}\\}.$

The first term results from differentiating the integrand
$J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)$
(the expectation is taken as integration), while the second term is due to the
differentiation of $q(\theta)$. One can see from the first term that the above
gradient involves a Hessian $\hat{\nabla}^{2}J_{\mathcal{D}}$, and its sample
estimate is given by the following. For more details on this Hessian
estimation, we refer the reader to (Fallah et al., 2021).

$\displaystyle\hat{\nabla}^{2}J_{\mathcal{D}}(\tau)=\frac{1}{N_{b}}\sum_{i=1}^{N_{b}}[g(\tau_{i};\theta)\nabla_{\theta}\log
q(\tau_{i};\theta)^{\mathsf{T}}+\nabla_{\theta}g(\tau_{i};\theta)]$ (C5)

Finally, to complete the sample estimate of
$\nabla_{\theta}\mathbb{E}_{\tau\sim
q(\theta)}[J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)]$,
one still needs to estimate
$\nabla_{\theta}J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)$
in the first term. To this end, we need to first collect a batch of sample
trajectories ${\tau^{\prime}}$ using the adapted policy
$\theta^{\prime}=\theta+\eta\hat{\nabla}_{\theta}J_{D}(\tau)$. Then, the
policy gradient estimate of
$\hat{\nabla}_{\theta}J_{\mathcal{D}}(\theta^{\prime})$ proceeds as in (C1).
To sum up, constructing an unbiased estimate of (C4) takes two rounds of
sampling. The first round is under the meta policy $\theta$, which is used to
estimate the Hessian (C5) and to adapt the policy to $\theta^{\prime}$. The
second round aims to estimate the policy gradient
$\nabla_{\theta}J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi,\xi)$
in the first term in (C4).

In the experiment, we employ a first-order meta-learning algorithm called
Reptile (Nichol et al., 2018) to avoid the Hessian computation. The gist is to
simply ignore the chain rule and update the policy using the gradient
$\nabla_{\theta}J_{\mathcal{D}}(\theta^{\prime},\phi,\xi)|_{\theta^{\prime}=\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau)}$.
Naturally, without the Hessian term, the gradient in this update is biased,
yet it still points to the ascent direction as argued in (Nichol et al.,
2018), leading to effective meta policy. The advantage of Reptile is more
evident in multi-step gradient adaptation. Consider a $l$-step gradient
adaptation, the chain rule computation inevitably involves multiple Hessian
terms (each gradient step brings a Hessian term) as shown in (Fallah et al.,
2021). In contrast, Reptile only requires first-order information, and the
meta-learning algorithm ($l$-step adaptation) is given by Algorithm 1.

1: Input:  the type distribution $Q(\xi)$, step size parameters $\kappa,\eta$

2: Output: $\theta^{T}$

3: randomly initialize $\theta^{0}$

4: for iteration $t=1$ to $T$ do

5: Sample a batch $\hat{\Xi}$ of $K$ attack types from $Q(\xi)$;

6: for each $\xi\in\hat{\Xi}$ do

7: $\theta_{\xi}^{t}(0)\leftarrow\theta^{t}$

8: for $k=0$ to $l-1$ do

9: Sample a batch trajectories ${\tau}$ of the horizon length $H$ under
$\theta^{t}_{\xi}(k)$;

10: Evaluate $\hat{\nabla}_{\theta}J_{\mathcal{D}}(\theta^{t}_{\xi}(k),\tau)$
using MC in (C1);

11:
$\theta_{\xi}^{t}(k+1)\leftarrow\theta_{\xi}^{t}(k)+\kappa\hat{\nabla}_{\theta}J_{\mathcal{D}}(\theta^{t},\tau)$

12: end for

13: end for

14: Update
$\theta^{t+1}\leftarrow\theta^{t}+1/K\sum_{\xi\in\hat{\Xi}}(\theta^{t}_{\xi}(l)-\theta^{t})$;

15: end for

Algorithm 1 Reptile Meta-Reinforcement Learning with $l$-step adaptation

#### Meta-Stackelberg Learning

Recall that in meta-SE, the attacker’s policy $\phi_{\xi}^{*}$ is not pre-
fixed, instead, it is the best response to the defender’s adapted policy. To
obtain this best response, one needs alternative training: fixing the defense
policy, and applying gradient ascent to the attacker’s problem until
convergence. It should be noted that the proposed meta-SL utilizes the
unbiased gradient estimation in (C5), which paves the way for theoretical
analysis in Appendix D. Yet, we turn to the Reptile to speed up pre-straining
in the experiments. We present both algorithms in Algorithm 2, and only
consider one-step adaptation for simplicity. The multi-step version is a
straightforward extension of Algorithm 2.

1: Input:  the type distribution $Q(\xi)$, initial defense meta policy
$\theta^{0}$, pre-trained attack policies $\\{\phi_{\xi}^{0}\\}_{\xi\in\Xi}$,
step size parameters $\kappa_{\mathcal{D}}$, $\kappa_{\mathcal{A}}$, $\eta$,
and iterations numbers $N_{\mathcal{A}},N_{\mathcal{D}}$;

2: Output: $\theta^{N_{\mathcal{D}}}$

3: for iteration $t=0$ to $N_{\mathcal{D}}-1$ do

4: Sample a batch $\hat{\Xi}$ of $K$ attack types from $Q(\xi)$;

5: for each $\xi\in\hat{\Xi}$ do

6: Sample a batch of trajectories using $\phi^{t}$ and $\phi_{\xi}^{t}$;

7: Evaluate $\hat{\nabla}_{\theta}J_{D}(\theta^{t},\phi^{t}_{\xi},\xi)$ using
(C1);

8: Perform one-step adaptation
$\theta_{\xi}^{t}\leftarrow\theta^{t}+\eta\hat{\nabla}_{\theta}J_{D}(\theta^{t}_{\xi}(k),\phi^{t}_{\xi},\xi)$;

9: $\phi^{t}_{\xi}(0)\leftarrow\phi^{t}_{\xi}$;

10: for $k=0,\ldots,N_{\mathcal{A}}-1$ do

11: Sample a batch of trajectories using $\theta_{\xi}^{t}$ and
$\phi^{t}_{\xi}(k)$;

12:
$\phi^{t}_{\xi}(k+1)\leftarrow\phi^{t}_{\xi}(k)+\kappa_{\mathcal{A}}\hat{\nabla}_{\phi}J_{\mathcal{A}}(\theta_{\xi}^{t},\phi_{\xi}^{t}(k),\xi)$;

13: end for

14: if Reptile then

15: Sample a batch of trajectories using $\theta_{\xi}^{t}$ and
$\phi_{\xi}^{t}(N_{\mathcal{A}})$;

16: Evaluate
$\hat{\nabla}J_{D}(\xi):=\hat{\nabla}_{\theta}J_{\mathcal{D}}(\theta,\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)|_{\theta=\theta_{\xi}^{t}}$
using (C1);

17: else

18: Sample a batch of trajectories using $\theta^{t}$ and
$\phi^{t}_{\xi}(N_{\mathcal{A}})$;

19: Evaluate the Hessian using (C5);

20: Sample a batch of trajectories using $\theta^{t}_{\xi}$ and
$\phi^{t}_{\xi}(N_{\mathcal{A}})$;

21: Evaluate
$\hat{\nabla}J_{D}(\xi):=\hat{\nabla}_{\theta}J_{\mathcal{D}}(\theta_{\xi}^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)$
using (C4);

22: end if

23:
$\bar{\theta}^{t}_{\xi}\leftarrow\theta^{t}+\kappa_{\mathcal{D}}\hat{\nabla}J_{D}(\xi)$;

24: end for

25:
$\theta^{t+1}\leftarrow\theta^{t}+1/{K}\sum_{\xi\sim\hat{\Xi}}(\bar{\theta}^{t}_{\xi}-\theta_{t})$,
$\phi^{t+1}_{\xi}\leftarrow\phi^{t}_{\xi}(N_{\mathcal{A}})$;

26: end for

Algorithm 2 (Reptile) Meta-Stackelberg Learning with one-step adaptation

##  Appendix D Theoretical Results

###  D.1 Existence of Meta-SG

######  Theorem D.1 (Theorem 4.2).

Under the conditions that $\Theta$ and $\Phi$ are compact and convex, the
meta-SG admits at least one meta-FOSE.

###### Proof.

Clearly, $\Theta\times\Phi^{|\Xi|}$ is compact and convex, let
$\phi\in\Phi^{|\Xi|},\phi_{\xi}\in\Phi$ be the (type-aggregated) attacker’s
strategy, since the consider twice continuously differentiable utility
functions $\ell_{\mathcal{D}}(\theta,\phi):=\mathbb{E}_{\xi\sim
Q}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)$ and
$\ell_{\xi}(\theta,\phi):=\mathcal{L}_{\mathcal{A}}(\theta,\phi_{\xi},\xi)$
for all $\xi\in\Xi$. Then, there exists a constant $\gamma_{c}>0$, such that
the auxiliary utility functions:

$\displaystyle\tilde{\ell}_{\mathcal{D}}(\theta;(\theta^{\prime},\phi^{\prime}))$
$\displaystyle\equiv\ell_{\mathcal{D}}(\theta,\phi)-\frac{\gamma_{c}}{2}\|\theta-\theta^{\prime}\|^{2}$
(D6)
$\displaystyle\tilde{\ell}_{\xi}(\phi_{\xi};(\theta^{\prime},\phi^{\prime})$
$\displaystyle\equiv\ell_{\xi}(\theta^{\prime},(\phi_{\xi},\phi^{\prime}_{-\xi}))-\frac{\gamma_{c}}{2}\|\phi_{\xi}-\phi^{\prime}_{\xi}\|^{2}\quad\forall\xi\in\Xi$

are $\gamma_{c}$-strongly concave in spaces $\theta\in\Theta$,
$\phi_{\xi}\in\Phi$ for all $\xi\in\Xi$, respectively for any fixed
$(\theta^{\prime},\phi^{\prime})\in\Theta\times\Phi^{|\Xi|}$.

Define the self-map $h:\Theta\times\Phi^{|\Xi|}\to\Theta\times\Phi^{|\Xi|}$
with
$h(\theta^{\prime},\phi^{\prime})\equiv(\bar{\theta}(\theta^{\prime},\phi^{\prime}),\bar{\phi}(\theta^{\prime},\phi^{\prime}))$,
where

$\displaystyle\bar{\theta}(\theta^{\prime},\phi^{\prime})=\arg\max_{\theta\in\Theta}\tilde{\ell}_{\mathcal{D}}(\theta,\phi^{\prime}),\quad\quad\bar{\phi}_{\xi}(\theta^{\prime},\phi^{\prime})=\arg\max_{\phi_{\xi}\in\Phi}\tilde{\ell}_{\xi}(\theta^{\prime},(\phi_{\xi},\phi^{\prime}_{-\xi})).$

Due to compactness, $h$ is well-defined. By strong concavity of
$\tilde{\ell}_{\mathcal{D}}(\cdot;(\theta^{\prime},\phi^{\prime}))$ and
$\tilde{\ell}_{\xi}(\cdot;(\theta^{\prime},\phi^{\prime}))$, it follows that
$\bar{\theta},\bar{\phi}$ are continuous self-mapping from
$\Theta\times\Phi^{|\Xi|}$ to itself. By Brouwer’s fixed point theorem, there
exists at least one $(\theta^{*},\phi^{*})\in\Theta\times\Phi^{|\Xi|}$ such
that $h(\theta^{*},\phi^{*})=(\theta^{*},\phi^{*})$. Then, one can verify that
$(\theta^{*},\phi^{*})$ is a meta-FOSE of the meta-SG with utility function
$\ell_{\mathcal{D}}$ and $\ell_{\xi}$, $\xi\in\Xi$, in view of the following
inequality

$\displaystyle\langle\nabla_{\theta}\tilde{\ell}_{\mathcal{D}}(\theta^{*};(\theta^{*},\phi^{*})),\theta-\theta^{*}\rangle$
$\displaystyle=\langle\nabla_{\theta}\ell_{\mathcal{D}}(\theta^{*},\phi^{*}),\theta-\theta^{*}\rangle$
$\displaystyle\langle\nabla_{\phi_{\xi}}\tilde{\ell}_{\xi}(\theta^{*};(\theta^{*},\phi^{*})),\phi_{\xi}-\phi^{*}_{\xi}\rangle$
$\displaystyle=\langle\nabla_{\phi_{\xi}}\ell_{\xi}(\theta^{*},\phi^{*}),\phi_{\xi}-\phi^{*}_{\xi}\rangle,$

therefore, the equilibrium conditions for meta-SG with utility functions
$\tilde{\ell}_{\mathcal{D}}$ and $\\{\tilde{\ell}_{\xi}\\}_{\xi\in\Xi}$ are
the same as with utility functions $\ell_{\mathcal{D}}$ and
$\\{\ell_{\xi}\\}_{\xi\in\Xi}$, hence the claim follows. ∎

###  D.2 Proofs: Non-Asymptotic Analysis

In the sequel, we make the following smoothness assumptions for every attack
type $\xi\in\Xi$. In addition, we assume, for analytical simplicity, that all
types of attackers are unconstrained, i.e., $\Phi$ is the Euclidean space with
proper finite dimension.

######  Assumption D.2 (($\xi$-wise) Lipschitz smoothness).

The functions $\mathcal{L}_{\mathcal{D}}$ and $\mathcal{L}_{\mathcal{A}}$ are
continuously diffrentiable in both $\theta$ and $\phi$. Furthermore, there
exists constants $L_{11}$, $L_{12},L_{21}$, and $L_{22}$ such that for all
$\theta,\theta_{1},\theta_{2}\in\Theta$ and $\phi,\phi_{1},\phi_{2}\in\Phi$,
we have, for any $\xi\in\Xi$,

$\displaystyle\left\|\nabla_{\theta}\mathcal{L}_{\mathcal{D}}\left(\theta_{1},\phi,\xi\right)-\nabla_{\theta}\mathcal{L}_{\mathcal{D}}\left(\theta_{2},\phi,\xi\right)\right\|$
$\displaystyle\leq L_{11}\left\|\theta_{1}-\theta_{2}\right\|$ (D7)
$\displaystyle\left\|\nabla_{\phi}\mathcal{L}_{\mathcal{D}}\left(\theta,\phi_{1},\xi\right)-\nabla_{\phi}\mathcal{L}_{\mathcal{D}}\left(\theta,\phi_{2},\xi\right)\right\|$
$\displaystyle\leq L_{22}\left\|\phi_{1}-\phi_{2}\right\|$ (D8)
$\displaystyle\left\|\nabla_{\theta}\mathcal{L}_{\mathcal{D}}\left(\theta,\phi_{1},\xi\right)-\nabla_{\theta}\mathcal{L}_{\mathcal{D}}\left(\theta,\phi_{2},\xi\right)\right\|$
$\displaystyle\leq L_{12}\left\|\phi_{1}-\phi_{2}\right\|$ (D9)
$\displaystyle\left\|\nabla_{\phi}\mathcal{L}_{\mathcal{D}}\left(\theta_{1},\phi,\xi\right)-\nabla_{\phi}\mathcal{L}_{\mathcal{D}}\left(\theta_{2},\phi,\xi\right)\right\|$
$\displaystyle\leq L_{12}\left\|\theta_{1}-\theta_{2}\right\|$ (D10)
$\displaystyle\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi_{1},\xi)-\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi_{2},\xi)\|$
$\displaystyle\leq L_{21}\|\phi_{1}-\phi_{2}\|.$ (D11)

######  Lemma D.3 (Implicit Function Theorem (IFT) for Meta-SG).

Suppose for $(\bar{\theta},\bar{\phi})\in\Theta\times\Phi^{|\Xi|}$,
$\xi\in\Xi$ we have
$\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\bar{\theta},\bar{\phi},\xi)=0$ the
Hessian
$\nabla^{2}_{\phi}\mathcal{L}_{\mathcal{A}}(\bar{\theta},\bar{\phi},\xi)$ is
non-singular. Then, there exists a neighborhood
$B_{\varepsilon}(\bar{\theta}),\varepsilon>0$ centered around $\bar{\theta}$
and a $C^{1}$-function
$\phi(\cdot):B_{\varepsilon}(\bar{\theta})\to\Phi^{|\Xi|}$ such that near
$(\bar{\theta},\bar{\phi})$ the solution set
$\\{(\theta,\phi)\in\Theta\times\Phi^{|\Xi|}:\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)=0\\}$
is a $C^{1}$-manifold locally near $(\bar{\theta},\bar{\phi})$. The gradient
$\nabla_{\theta}\phi(\theta)$ is given by
$-(\nabla^{2}_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi))^{-1}\nabla^{2}_{\phi\theta}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)$.

######  Lemma D.4.

Under assumptions D.2, 4.4, there exists
$\\{\phi_{\xi}:\phi_{\xi}\in\arg\max_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)\\}_{\xi\in\Xi}$,
such that

$\nabla_{\theta}V(\theta)=\nabla_{\theta}\mathbb{E}_{\xi\sim Q,\tau\sim
q}J_{\mathcal{D}}(\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau),\phi_{\xi},\xi).$

Moreover, the function $V(\theta)$ is $L$-Lipschitz-smooth, where
$L=L_{11}+\frac{L_{12}L_{21}}{\mu}$

$\|\nabla_{\theta}V(\theta_{1})-\nabla_{\theta}V(\theta_{2})\|\leq
L\|\theta_{1}-\theta_{2}\|.$

###### Proof of Lemma D.4.

First, we show that for any $\theta_{1},\theta_{2}\in\Theta,\xi\in\Xi$, and
$\phi_{1}\in\arg\max_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi,\xi)$,
there exists
$\phi_{2}\in\arg\max_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{2},\phi,\xi)$
such that
$\|\phi_{1}-\phi_{2}\|\leq\frac{L_{12}}{\mu}\|\theta_{1}-\theta_{2}\|$.
Indeed, based on smoothness assumption (D11) and (D10),

$\displaystyle\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi_{1},\xi)-\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{2},\phi_{1},\xi)\|\leq
L_{21}\|\theta_{1}-\theta_{2}\|,$
$\displaystyle\|\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta_{1},\phi_{1},\xi)-\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta_{2},\phi_{1},\xi)\|\leq
L_{12}\|\theta_{1}-\theta_{2}\|.$

Since
$\phi_{2}\in\arg\max_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{2},\phi,\xi)$,
$\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{2},\phi_{2},\xi)=0$. Apply PL
condition to $\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi_{2},\xi)$,

$\displaystyle\max_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi,\xi)-\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi_{2},\xi)$
$\displaystyle\leq\frac{1}{2\mu}\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi_{2},\xi)\|^{2}$
$\displaystyle=\frac{1}{2\mu}\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi_{2},\xi)-\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta_{2},\phi_{2},\xi)\|^{2}$
$\displaystyle\leq\frac{L^{2}_{21}}{2\mu}\|\theta_{1}-\theta_{2}\|^{2}\quad\quad\text{
by \eqref{lip5}.}$

Since PL condition implies quadratic growth, we also have

$\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi_{1},\xi)-\mathcal{L}_{\mathcal{A}}(\theta_{1},\phi_{2},\xi)\geq\frac{\mu}{2}\|\phi_{1}-\phi_{2}\|^{2}.$

Combining the two inequalities above we obtain the Lipschitz stability for
$\phi^{*}_{\xi}(\cdot)$, i.e.,

$\|\phi_{1}-\phi_{2}\|\leq\frac{L_{21}}{\mu}\|\theta_{1}-\theta_{2}\|.$

Second, show that $\nabla_{\theta}V(\theta)$ can be directly evaluated at
$\\{\phi^{*}_{\xi}\\}_{\xi\in\Xi}$. Inspired by Danskin’s theorem, we first
made the following argument, consider the definition of directional
derivative. Let
$\ell(\theta,\phi):=\nabla_{\theta}\mathbb{E}_{\xi,\tau}J_{\mathcal{D}}(\theta+\eta\hat{\nabla}J_{\mathcal{D}}(\tau),\xi)$.
For a constant $\tau$ and an arbitrary direction $d$,

$\displaystyle\quad\ell(\theta+\tau d,\phi^{*}(\theta+\tau
d))-\ell(\theta,\phi^{*}(\theta)))$ $\displaystyle=\ell(\theta+\tau
d,\phi^{*}(\theta+\tau d))-\ell(\theta+\tau
d,\phi^{*}(\theta))+\ell(\theta+\tau
d,\phi^{*}(\theta))-\ell(\theta,\phi^{*}(\theta))$
$\displaystyle=\nabla_{\phi}\ell(\theta+\tau
d,\phi^{*}(\theta))^{\top}\underbrace{[\phi^{*}(\theta+\tau
d)-\phi^{*}(\theta))]}_{\Delta\phi}+o(\Delta\phi^{2})$
$\displaystyle+\tau\nabla_{\theta}\ell(\theta,\phi^{*}(\theta))^{T}d+o(d^{2}).$

Hence, a sufficient condition for the first equation is
$\nabla_{\phi}\ell(\theta+\tau d,\phi^{*}(\theta))=0$, meaning that
$\ell_{D}(\theta,\phi)$ and $\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)$ share
the first-order stationarity at every $\phi$ when fixing $\theta$. Indeed, by
Lemma D.3, we have, the gradient is locally determined by

$\displaystyle\nabla_{\theta}V$ $\displaystyle=\mathbb{E}_{\xi\sim
Q}[\nabla_{\theta}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)+(\nabla_{\theta}\phi_{\xi}(\theta))^{\top}\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)]$
$\displaystyle=\mathbb{E}_{\xi\sim
Q}\left[\nabla_{\theta}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)-[(\nabla^{2}_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi))^{-1}\nabla^{2}_{\phi\theta}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)]^{\top}\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)\right].$

Given a trajectory
$\tau:=(s^{1},a_{\mathcal{D}}^{t},a_{\mathcal{A}}^{t},\ldots,a_{\mathcal{D}}^{H},a_{\mathcal{A}}^{H},s^{H+1})$,
let
$R_{\mathcal{D}}(\tau,\xi):=\sum_{t=1}^{H}\gamma^{t-1}r_{\mathcal{D}}(s_{t},a_{t},\xi)$
and
$R_{\mathcal{D}}(\tau,\xi):=\sum_{t=1}^{H}\gamma^{t-1}r_{\mathcal{D}}(s_{t},a_{t},\xi)$.
Denote by $\mu(\tau;\theta,\phi)$ the trajectory distribution, that the log
probability of $\mu$ is given by

$\displaystyle\log\mu(\tau;\theta,\phi)$
$\displaystyle=\sum_{t=1}^{H}(\log\pi_{\mathcal{D}}(a^{t}_{\mathcal{D}}|s^{t};\theta+\eta\hat{\nabla}_{\theta}J_{\mathcal{D}}(\tau))+\log\pi_{\mathcal{A}}(a^{t}_{\mathcal{A}}|s^{t};\phi)+\log
P(s^{t+1}|a^{t}_{\mathcal{D}},a^{t}_{\mathcal{A}},s^{t})$

According to the policy gradient theorem, we have

$\displaystyle\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi,\xi)=\mathbb{E}_{\mu}[R_{\mathcal{D}}(\tau,\xi)\sum_{t=1}^{H}\nabla_{\phi}\log(\pi_{\mathcal{A}}(a_{\mathcal{A}}^{t}|s^{t};\phi))],$
$\displaystyle\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)=\mathbb{E}_{\mu}[R_{\mathcal{A}}(\tau,\xi)\sum_{t=1}^{H}\nabla_{\phi}\log(\pi_{\mathcal{A}}(a_{\mathcal{A}}^{t}|s^{t};\phi))].$

By SC 4.3, when $\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)=0$,
there exists $c<0$, $d$, such that
$\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi,\xi)=\mathbb{E}_{\mu}[cR_{\mathcal{A}}(\tau,\xi)\sum_{t=1}^{H}\nabla_{\phi}\log(\pi_{\mathcal{A}}(a_{\mathcal{A}}^{t}|s^{t};\phi))]+\mathbb{E}_{\mu}[\sum_{t=1}^{H}\gamma^{t-1}d\sum_{t=1}^{H}\nabla_{\phi}\log(\pi_{\mathcal{A}}(a_{\mathcal{A}}^{t}|s^{t};\phi))]=0$.
Hence $\nabla_{\theta}V=\mathbb{E}_{\xi\sim
Q}[\nabla_{\theta}\mathcal{L}_{\mathcal{D}}(\theta,\phi_{\xi},\xi)]$.

Third, $V(\theta)$ is also Lipschitz smooth. As we notice that,
$\ell_{\mathcal{D}}$ is Lipschitz smooth since $\mathbb{E}_{\xi\sim Q}$ is a
linear operator, we have,

$\displaystyle\quad\
\|\nabla_{\theta}V(\theta_{1})-\nabla_{\theta}V(\theta_{2})\|$
$\displaystyle\leq\|\nabla_{\theta}\mathbb{E}_{\xi\sim
Q}\mathcal{L}_{\mathcal{D}}(\theta_{1},\phi_{1},\xi)-\nabla_{\theta}\mathbb{E}_{\xi\sim
Q}\mathcal{L}_{\mathcal{D}}(\theta_{2},\phi_{2},\xi)\|$
$\displaystyle=\|\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{1},\phi_{1})-\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{2},\phi_{1})+\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{2},\phi_{1})-\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{2},\phi_{2})\|$
$\displaystyle\leq\|\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{1},\phi_{1})-\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{2},\phi_{1})\|+\|\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{2},\phi_{1})-\nabla_{\theta}\ell_{\mathcal{D}}(\theta_{2},\phi_{2})\|$
$\displaystyle\leq
L_{11}\|\theta_{1}-\theta_{2}\|+L_{12}\|\phi_{1}-\phi_{2}\|$
$\displaystyle\leq(L_{11}+\frac{L_{12}L_{21}}{\mu})\|\theta_{1}-\theta_{2}\|,$

which implies the Lipschitz constant $L=L_{11}+\frac{L_{12}L_{21}}{\mu}$. ∎

It is impossible to present the convergence theory without the assistance of
some standard assumptions in batch reinforcement learning, of which the
justification can be found in (Fallah et al., 2021). We also require some
additional information about the parameter space and function structure. These
assumptions are all stated in D.5.

######  Assumption D.5.

  1. (a)

The following policy gradients are bounded,
$\|\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta,\phi,\xi)\|\leq G^{2}$,
$\|\mathcal{L}_{\mathcal{A}}(\theta,\phi,\xi)\|\leq G^{2}$ for all
$\theta,\phi\in\Theta\times\Phi$ and $\xi\in\Xi$.

  2. (b)

The policy gradient estimations are unbiased.

  3. (c)

The variances for the stochastic gradients are bounded, i.e., for all
$theta_{\xi}^{t},\phi^{t}_{\xi},\xi$,

$\mathbb{E}[\|\hat{\nabla}_{\phi}J(\theta_{\xi}^{t},\phi^{t}_{\xi},\xi)-\nabla_{\phi}J(\theta_{\xi}^{t},\phi^{t}_{\xi},\xi)\|^{2}]\leq\frac{\sigma^{2}}{N_{b}}.$

  4. (d)

The parameter space $\Theta$ has diameter
$D_{\Theta}:=\sup_{\theta_{1},\theta_{2}\in\Theta}\|\theta_{1}-\theta_{2}\|$;
the initialization $\theta^{0}$ admits at most $D_{V}$ function gap, i.e.,
$D_{V}:=\max_{\theta\in\Theta}V(\theta)-V(\theta^{0})$.

  5. (e)

It holds that the parameters satisfy $0<\mu<-cL_{22}$.

Equipped with D.5 we are able to unfold our main result Theorem 4.7, before
which we show in Lemma D.6 that $\phi^{*}_{\xi}$ can be efficiently
approximated by the inner loop in the sense that
$\nabla_{\theta}\mathbb{E}_{\xi\sim
Q}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)\approx\nabla_{\theta}V(\theta^{t})$,
where $\phi^{t}_{\xi}(N_{\mathcal{A}})$ is the last iterate output of the
attacker policy.

######  Lemma D.6.

Under D.5, 4.4, 4.3, and D.2, let $\rho:=1+\frac{\mu}{cL_{22}}\in(0,1)$,
$\bar{L}=\max\\{L_{11},L_{12},L_{22},L_{21},V_{\infty}\\}$ where
$V_{\infty}:=\max\\{\max\|\nabla V(\theta)\|,1\\}$. For all $\varepsilon>0$,
if the attacker learning iteration $N_{\mathcal{A}}$ and batch size $N_{b}$
are large enough such that

$\displaystyle N_{\mathcal{A}}$
$\displaystyle\geq\frac{1}{\log\rho^{-1}}\log\frac{32D_{V}^{2}(2V_{\infty}+LD_{\Theta})^{4}\bar{L}|c|G^{2}}{L^{2}\mu^{2}\varepsilon^{4}}$
$\displaystyle N_{b}$ $\displaystyle\geq\frac{32\mu
L_{21}^{2}D_{V}^{2}(2V_{\infty}+LD_{\Theta})^{4}}{|c|L_{22}^{2}\sigma^{2}\bar{L}L\varepsilon^{4}},$

then, for $z_{t}:=\nabla_{\theta}\mathbb{E}_{\xi\sim
Q}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)-\nabla_{\theta}V(\theta^{t})$,

$\mathbb{E}[\|z_{t}\|]\leq\frac{L\varepsilon^{2}}{4D_{V}(2V_{\infty}+LD_{\Theta})^{2}},$

and

$\mathbb{E}[\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{t}_{\xi}(N),\xi)\|]\leq\varepsilon.$

###### Proof of Lemma D.6.

Fixing a $\xi\in\Xi$, due to Lipschitz smoothness,

$\displaystyle\quad\
\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N),\xi)-\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N-1),\xi)$
$\displaystyle\leq\langle\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N-1),\xi),\phi^{t}_{\xi}(N)-\phi^{t}_{\xi}(N-1)\rangle+\frac{L_{22}}{2}\|\phi^{t}_{\xi}(N)-\phi^{t}_{\xi}(N-1)\|^{2}.$

The inner loop updating rule ensures that when
$\kappa_{\mathcal{A}}=\frac{1}{L_{21}}$,
$\phi^{t}_{\xi}(N)-\phi^{t}_{\xi}(N-1)=\frac{1}{L_{21}}\hat{\nabla}_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)$.
Plugging it into the inequality, we arrive at

$\displaystyle\
\quad\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N),\xi)-\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N-1),\xi)$
$\displaystyle\leq\frac{1}{L_{21}}\langle\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N-1),\xi),\hat{\nabla}_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\rangle+\frac{L_{22}}{2L^{2}_{21}}\|\hat{\nabla}_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\|^{2}.$

Therefore, we let $(\mathcal{F}^{t}_{n})_{0\leq n\leq N}$ be the filtration
generated by $\sigma(\\{\phi^{t}_{\xi}(\tau)\\}_{\xi\in\Xi}|\tau\leq n)$ and
take conditional expectations on $\mathcal{F}^{t}_{n}$:

$\displaystyle\quad\mathbb{E}[V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N))|\mathcal{F}^{t}_{N-1}]\leq
V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N-1))$
$\displaystyle\mathbb{E}_{\xi}\left[\frac{1}{L_{21}}\langle\nabla_{\phi}\mathcal{L}_{\mathcal{D}},\nabla_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\rangle+\frac{L_{22}}{2L^{2}_{21}}\|\hat{\nabla}_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\|^{2}\right].$

By variance-bias decomposition, and D.5 (b) and (c),

$\displaystyle\quad\
\mathbb{E}[\|\hat{\nabla}_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\|^{2}|\mathcal{F}^{t}_{N-1}]$
$\displaystyle=\mathbb{E}[\|\hat{\nabla}_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)-\nabla_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)+\nabla_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\|^{2}|\mathcal{F}^{t}_{N-1}]$
$\displaystyle=\mathbb{E}[\|(\hat{\nabla}_{\phi}-\nabla_{\phi})J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\|^{2}|\mathcal{F}^{t}_{N-1}]+\mathbb{E}[\|\nabla_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\|^{2}|\mathcal{F}^{t}_{N-1}]$
$\displaystyle\quad+\mathbb{E}[2\langle(\hat{\nabla}_{\phi}-\nabla_{\phi})J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi),\nabla_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\rangle|\mathcal{F}^{t}_{N-1}]$
$\displaystyle\leq\frac{\sigma^{2}}{N_{b}}+\|\nabla_{\phi}J_{\mathcal{A}}(\theta^{t}_{\xi},\phi^{t}_{\xi}(N-1),\xi)\|^{2}.$

Applying the PL condition (4.4), and D.5 (a) we obtain

$\displaystyle\quad\mathbb{E}[V(\theta^{t})-\ell_{\mathcal{D}}(\theta,\phi^{t}(N))|\phi^{N-1}]-V(\theta^{t})-\ell_{\mathcal{D}}(\theta,\phi^{t}(N-1))$
$\displaystyle\leq\mathbb{E}_{\xi}\left[\frac{1}{L_{21}}\langle\nabla_{\phi}\mathcal{L}_{\mathcal{D}},\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{t}_{\xi}(N-1),\xi)\rangle+\frac{L_{22}}{2L_{21}^{2}}(\frac{\sigma^{2}}{N_{b}}+\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{t}_{\xi}(N-1),\xi)\|^{2})\right]$
$\displaystyle=\mathbb{E}_{\xi}\left[-\frac{1}{2L_{22}}\|\nabla_{\phi}\mathcal{L}_{\mathcal{D}}\|^{2}+\frac{1}{2L_{22}}\|\nabla_{\phi}(\mathcal{L}_{\mathcal{D}}+\frac{L_{22}}{L_{21}}\mathcal{L}_{\mathcal{A}})(\theta^{t},\phi^{t}_{\xi}(N-1),\xi)\|^{2}+\frac{L_{22}\sigma^{2}}{2L_{21}^{2}N_{b}}\right]$
$\displaystyle\leq\frac{\mu}{cL_{21}}(\max_{\phi}\ell_{\mathcal{D}}(\theta^{t},\phi)-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N-1)))+\frac{L_{22}\sigma^{2}}{2L_{21}^{2}N_{b}},$

rearranging the terms yields

$\displaystyle\mathbb{E}[V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N))|\mathcal{F}^{t}_{n}]\leq\rho(V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N-1)))+\frac{L_{22}\sigma^{2}}{2L_{21}^{2}N_{b}},$

where we use the fact that
$-\max_{\phi}\ell_{\mathcal{D}}(\theta^{t},\phi)\leq-V(\theta^{t})$.
Telescoping the inequalities from $\tau=0$ to $\tau=N$, we arrive at

$\displaystyle\mathbb{E}[V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N))]\leq\rho^{N}(V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(0)))+\frac{1-\rho^{N}}{1-\rho}\left(\frac{L_{22}\sigma^{2}}{2L_{21}^{2}N_{b}}\right).$

PL-condition implies quadratic growth, we also know that
$V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N))\leq\mathbb{E}_{\xi}\frac{1}{2\mu}\|\nabla_{\phi}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N),\xi)\|^{2}\leq\frac{1}{2\mu}G^{2}$,
by 4.3,

$\displaystyle\|\phi^{*}_{\xi}(\theta^{t})-\phi^{t}_{\xi}(N)\|^{2}$
$\displaystyle\leq\frac{2}{\mu}(\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{*}_{\xi},\xi)-\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{t}_{\xi}(N),\xi))$
$\displaystyle\leq\frac{2|c|}{\mu}\big{|}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{*}_{\xi},\xi)-\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N),\xi)\big{|}$

Hence, with Jensen inequality and choice of $N_{\mathcal{A}}$ and $N_{b}$,

$\displaystyle\mathbb{E}[\|z_{t}\|]$
$\displaystyle=\mathbb{E}[\|\nabla_{\theta}V(\theta^{t})-\mathbb{E}_{\xi}\nabla_{\theta}\mathcal{L}_{\mathcal{D}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)\|]$
$\displaystyle\leq
L_{12}\mathbb{E}[\|\phi^{t}_{\xi}(N_{\mathcal{A}})-\phi^{*}_{\xi}\|]$
$\displaystyle\leq
L_{12}\sqrt{\frac{2|c|}{\mu}\mathbb{E}[V(\theta^{t})-\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N_{\mathcal{A}}))]}$
$\displaystyle\leq
L_{12}\sqrt{\frac{|c|}{\mu^{2}}\rho^{N_{\mathcal{A}}}G^{2}+(1-\rho^{N_{\mathcal{A}}})\frac{|c|L_{22}^{2}\sigma^{2}}{\mu
L_{21}^{2}N_{b}}}.$

Now we adjust the size of $N_{\mathcal{A}}$ and $N_{b}$ to make
$\mathbb{E}[\|z_{t}\|]$ small enough, to this end, we set

$\displaystyle\rho^{N_{\mathcal{A}}}\frac{|c|G^{2}}{\mu^{2}}$
$\displaystyle\leq\frac{\varepsilon^{4}L^{2}}{32D_{V}^{2}(2V_{\infty}+LD_{\Theta})^{4}\bar{L}}$
$\displaystyle\frac{|c|L_{22}^{2}\sigma^{2}}{L_{21}^{2}N_{b}}$
$\displaystyle\leq\frac{\varepsilon^{4}L^{2}\mu^{2}}{32D_{V}^{2}(2V_{\infty}+LD_{\Theta})^{4}\bar{L}},$

which further indicates that

$\displaystyle N_{\mathcal{A}}$
$\displaystyle\geq\frac{1}{\log\rho^{-1}}\log\frac{32D_{V}^{2}(2V_{\infty}+LD_{\Theta})^{4}\bar{L}|c|G^{2}}{L^{2}\mu^{2}\varepsilon^{4}}$
$\displaystyle N_{b}$ $\displaystyle\geq\frac{32\mu
L_{21}^{2}D_{V}^{2}(2V_{\infty}+LD_{\Theta})^{4}}{|c|L_{22}^{2}\sigma^{2}\bar{L}L\varepsilon^{4}}.$

In the setting above, it is not hard to verify that

$\displaystyle\mathbb{E}[\|z_{t}\|]\leq\frac{L\varepsilon^{2}}{4D_{V}(2V_{\infty}+LD_{\Theta})^{2}}\leq\varepsilon.$

Also note that
$\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)\|=\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)-\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{*}_{\xi},\xi)\|$,
given the proper choice of $N_{\mathcal{A}}$ and $N_{b}$, one has

$\displaystyle\quad\mathbb{E}\|\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{t}_{\xi}(N_{\mathcal{A}}),\xi)-\nabla_{\phi}\mathcal{L}_{\mathcal{A}}(\theta^{t},\phi^{*}_{\xi},\xi)\|$
$\displaystyle\leq
L_{21}\mathbb{E}[\|\phi^{t}_{\xi}(N_{\mathcal{A}})-\phi^{*}_{\xi}\|]\leq\frac{L\varepsilon^{2}}{4D_{V}(2V_{\infty}+LD_{\Theta})^{2}}\leq\varepsilon,$

which indicates the $\xi$-wise inner loop stability. ∎

Now we are ready to provide the convergence guarantee of the first-order outer
loop.

######  Theorem D.7.

Under D.5, 4.3, and D.2, let the stepsizes be,
$\kappa_{\mathcal{A}}=\frac{1}{L_{22}}$, $\kappa_{\mathcal{D}}=\frac{1}{L}$,
if $N_{\mathcal{D}},N_{\mathcal{A}},$ and $N_{b}$ are large enough,

$\displaystyle N_{\mathcal{D}}\geq
N_{\mathcal{D}}(\varepsilon)\sim\mathcal{O}(\varepsilon^{-2})\quad
N_{\mathcal{A}}\geq
N_{\mathcal{A}}(\varepsilon)\sim\mathcal{O}(\log\varepsilon^{-1}),\quad
N_{b}\geq N_{b}(\varepsilon)\sim\mathcal{O}(\varepsilon^{-4})$

then there exists $t\in\mathbb{N}$ such that
$(\theta^{t},\\{\phi^{t}_{\xi}(N_{\mathcal{A}})\\}_{\xi\in\Xi})$ is
$\varepsilon$-meta-FOSE.

###### Proof.

According to the update rule of the outer loop, (here we omit the projection
analysis for simplicity)

$\displaystyle\theta^{t+1}-\theta^{t}=\frac{1}{L}\hat{\nabla}_{\theta}\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N_{\mathcal{A}})),$

one has, due to unbiasedness assumption, let $(\mathcal{F}_{t})_{0\leq t\leq
N_{\mathcal{D}}}$ be the filtration generated by $\sigma(\theta^{t}|k\leq t)$

$\displaystyle\mathbb{E}[\langle\nabla_{\theta}\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N_{\mathcal{A}})),\theta^{t+1}-\theta^{t}\rangle|\mathcal{F}_{t}]$
$\displaystyle=\frac{1}{L}\mathbb{E}[\|\nabla_{\theta}\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N_{\mathcal{A}}))\|^{2}|\mathcal{F}_{t}]$
$\displaystyle=L\mathbb{E}\|\theta^{t+1}-\theta^{t}\|^{2}|\mathcal{F}_{t}],$

which leads to

$\displaystyle\mathbb{E}[\langle\nabla_{\theta}\ell_{\mathcal{D}}(\theta^{t},\phi^{*}),\theta^{t+1}-\theta^{t}\rangle|\mathcal{F}_{t}]$
$\displaystyle=\mathbb{E}[\langle
z_{t},\theta^{t}-\theta^{t+1}\rangle|\mathcal{F}_{t}]+L\mathbb{E}[\|\theta^{t+1}-\theta^{t}\|^{2}\|].$

Since $V(\cdot)$ is $L$-Lipschitz smooth,

$\displaystyle\mathbb{E}[V(\theta^{t})-V(\theta^{t+1})]$
$\displaystyle\leq\mathbb{E}[\langle\nabla_{\theta}V(\theta^{t}),\theta^{t}-\theta^{t+1}\rangle]+\frac{L}{2}\mathbb{E}[\|\theta^{t+1}-\theta^{t}\|^{2}]$
(D12) $\displaystyle\leq\mathbb{E}[\langle z_{t},\theta^{t+1}$
$\displaystyle-\theta^{t}\rangle]-\mathbb{E}[\langle\nabla_{\theta}\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N_{\mathcal{A}})),\theta^{t+1}-\theta^{t}\rangle]+\frac{L}{2}\mathbb{E}[\|\theta^{t+1}-\theta^{t}\|^{2}]$
$\displaystyle\leq\mathbb{E}[\langle z_{t},\theta^{t+1}$
$\displaystyle-\theta^{t}\rangle]-\frac{L}{2}\mathbb{E}[\|\theta^{t+1}-\theta^{t}\|^{2}].$

Fixing a $\theta\in\Theta$, let
$e_{t}:=\langle\nabla_{\theta}\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N_{\mathcal{A}})),\theta-\theta^{t}\rangle$,
we have

$\displaystyle\mathbb{E}[e_{t}|\mathcal{F}_{t}]$
$\displaystyle=L\mathbb{E}[\langle\theta^{t+1}-\theta^{t},\theta-\theta^{t}\rangle|\mathcal{F}_{t}]$
(D13)
$\displaystyle=\mathbb{E}[\langle\nabla_{\theta}\ell_{\mathcal{D}}(\theta^{t},\phi^{t}(N_{\mathcal{A}}))-\nabla_{\theta}V(\theta^{t}),\theta^{t+1}-\theta^{t}\rangle+\langle\nabla_{\theta}V(\theta^{t}),\theta^{t+1}-\theta^{t}\rangle]$
$\displaystyle\quad+L\mathbb{E}[\langle\theta^{t+1}-\theta^{t},\theta-\theta^{t+1}\rangle]$
$\displaystyle\leq\mathbb{E}[(\|z_{t}\|+V_{\infty}+LD_{\Theta})\|\theta^{t+1}-\theta^{t}\|]$

By the choice of $N_{b}$, we have, since
$V_{\infty}=\max\\{\max_{\theta}\|\nabla V(\theta)\|,1\\}$,

$\displaystyle\mathbb{E}[\|z_{t}\|]\leq
L_{12}\mathbb{E}[\|\phi^{N}-\phi^{*}\|]\leq\frac{L\varepsilon^{2}}{4D_{V}(2V_{\infty}+LD_{\Theta})}\leq
V_{\infty}.$

Thus, the relation (D13) can be reduced to

$\mathbb{E}[e_{t}]\leq(2V_{\infty}+LD_{\Theta})\mathbb{E}[\|\theta^{t+1}-\theta^{t}\|].$

Telescoping (D12) yields

$-D_{V}\leq\mathbb{E}[V(\theta^{0})-V(\theta^{N_{\mathcal{D}}})]\leq
D_{\Theta}\sum_{t=0}^{T-1}\mathbb{E}[\|z_{t}\|]-\frac{L}{2(2V_{\infty}+LD_{\Theta})^{2}}\mathbb{E}[\sum_{t=0}^{T-1}\mathbb{E}[e^{2}_{t}|\mathcal{F}_{t}].$

Thus, setting
$N_{\mathcal{D}}\geq\frac{4D_{V}(2V_{\infty}+LD_{\Theta})^{2}}{L\varepsilon^{2}}$,
and then by Lemma 4.6, we obtain that,

$\frac{1}{N_{\mathcal{D}}}\sum_{t=0}^{N_{\mathcal{D}}-1}\mathbb{E}[e^{2}_{t}]\leq\frac{\varepsilon^{2}}{2}+\frac{2D_{V}(2V_{\infty}+LD_{\Theta})^{2}}{LN_{\mathcal{D}}}\leq\varepsilon^{2}$

which implies there exists $t\in\\{0,\ldots,N_{\mathcal{D}}-1\\}$ such that
$\mathbb{E}[e^{2}_{t}]\leq\varepsilon^{2}$.

∎

##  Appendix E Related Works

#### Poisoning/backdoor attacks and defenses in FL.

Various methods for compromising the integrity of a federated learning target
model have been introduced, including targeted poisoning attacks which strive
to misclassify a particular group of inputs, as explored in the studies by
(Bhagoji et al., 2019; Baruch et al., 2019). Other techniques, such as those
studied by (Fang et al., 2020; Xie et al., 2020; Shejwalkar & Houmansadr,
2021), focus on untargeted attacks with the aim of diminishing the overall
model accuracy. The majority of existing strategies often utilize heuristics-
based methods (e.g., (Xie et al., 2020)), or they focus on achieving a short-
sighted goal ( (Fang et al., 2020; Shejwalkar & Houmansadr, 2021)). On the
other hand, malicious participants can easily embed backdoors into the
aggregated model while maintaining the model’s performance on the main task
with model replacement (Bagdasaryan et al., 2020). To enhance the
surreptitious nature of these poisoned updates, triggers can be distributed
across multiple cooperative malicious devices, as discussed by Xie et al.
(2019)(Xie et al., 2019), and edge-case backdoors can be employed, as
demonstrated by Wang et al. (2020) (Wang et al., 2020). However, these methods
can be sub-optimal, especially when there’s a need to adopt a robust
aggregation rule. Additionally, these traditional methods typically demand
access to the local updates of benign agents or precise parameters of the
global model for the upcoming round (Xie et al., 2020; Fang et al., 2020) in
order to enact a significant attack. In contrast to these methods, RL-based
approach (Li et al., 2022a; Shen et al., 2021; Li et al., 2023a) employs
reinforcement learning for the attack, reducing the need for extensive global
knowledge while focusing on a long-term attack goal.

Several defensive strategies have been suggested to counter model poisoning
attacks, which broadly fall into two categories: those based on robust
aggregation and those centered around detection. Robust-aggregation-based
defenses encompass techniques such as dimension-wise filtering. These methods
treat each dimension of local updates individually, as explored in studies by
(Bernstein et al., 2018; Yin et al., 2018). Another strategy is client-wise
filtering, the goal of which is to limit or entirely eliminate the influence
of clients who might harbor malicious intent. This approach has been examined
in the works of (Blanchard et al., 2017; Pillutla et al., 2022; Sun et al.,
2019). Some defensive methods necessitate the server having access to a
minimal amount of root data, as detailed in the study by (Cao et al., 2021).
Naive backdoor attacks are limited by even simple defenses like norm-bounding
(Sun et al., 2019) and weak differential private (Geyer et al., 2017)
defenses. Despite to the sophisticated design of state-of-the-art non-
addaptive backdoor attacks against federated learning, post-training stage
defenses (Wu et al., 2020; Nguyen et al., 2021; Rieger et al., 2022) can still
effectively erase suspicious neurons/parameters in the backdoored model.

#### Multi-agent meta learning.

Meta-learning, and in particular meta-reinforcement-learning aim to create a
generalizable policy that can fast adapt to new tasks by exploiting knowledge
obtained from past tasks (Duan et al., 2016; Finn et al., 2017). The early use
cases of meta-learning have been primarily single-agent tasks, such as few-
shot classification and single-agent RL (Finn et al., 2017). A recent research
thrust is to extend the meta-learning idea to multi-agent systems (MAS), which
can be further categorized into two main directions: 1) distributed meta-
learning in MAS (Kayaalp et al., 2022; Zhang et al., 2022); 2) meta-learning
for generalizable equilibrium-seeking (Gupta et al., 2021; Harris et al.,
2022; Zhao & Zhu, 2022; Ge et al., 2023). The former focuses on a
decentralized operation of meta-learning over networked computation units to
reduce computation/storage expenses. The latter is better aligned with the
original motivation of meta-learning, which considers how to solve a new game
(or multi-agent decision-making) efficiently by reusing past experiences from
similar occasions.

In stark contrast to the existing research efforts, our work leverages the
adaptability of meta-learning to address information asymmetry in dynamic
games of incomplete information, leading to a new equilibrium concept: meta-
equilibrium (see Definition 3.1). What distinguishes our work from the
aforementioned ones is that 1) every entity in our meta-SG is a self-interest
player acting rationally without any coordination protocol; 2) meta-learning
in our work is beyond a mere solver for computing long-established equilibria
(e.g., Stackelberg equilibrium); it brings up a non-Bayesian approach to
processing information in dynamic games (see Appendix B), which is
computationally more tractable. This meta-equilibrium notion has been proven
effective in combating information asymmetry in adversarial FL. Since
asymmetric information is prevalent in security studies, our work can shed
light on other related problems.

#### First-order methods in bilevel optimization.

The meta-SG problem in (LABEL:eq:meta-se) amounts to a stochastic bilevel
optimization. The meta-SL in Algorithm 2 admits a much simpler gradient
estimation than what one would often observe in the bilevel optimization
literature (Chen et al., 2023; Kwon et al., 2023), where the gradient estimate
for the upper-level problem involves a Hessian inverse (Chen et al., 2023) or
some first-order correction terms (Kwon et al., 2023). The key intuition
behind this simplicity lies in the strict competitiveness (see 4.3).
Informally speaking, (LABEL:eq:meta-se) is more akin to minimax programming
(Nouiehed et al., 2019; Li et al., 2022b), even though it is a general-sum
game. However, the data-driven meta-adaptation within the value function in
LABEL:eq:meta-se leads to a more involved gradient estimation. since the data
induces extra randomness in addition to policy gradient estimates (Fallah et
al., 2021). Perhaps, the closest to our work is (Li et al., 2022b) where the
authors investigate adversarial meta-RL and arrive at a similar Stackelberg
formulation. However, (Li et al., 2022b) considers a minimax relaxation to the
original Stackelberg formulation, leading to simpler nonconvex programming.
Our work is among the first endeavors to investigate fully first-order
algorithms for solving general-sum Stackelberg games.