Formal Methods and Tools, University of Twente, The Netherlands and
https://www.tvandijk.nl/<EMAIL_ADDRESS>Discrete Mathematics and
Mathematical Programming, University of Twente, The Netherlands and
<EMAIL_ADDRESS>Discrete Mathematics and
Mathematical Programming, University of Twente, The Netherlands and
<EMAIL_ADDRESS>Tom van Dijk, Georg Loho
and Matthew T. Maat Theory of computation Logic and verification Mathematics
of computing Discrete mathematics

###### Acknowledgements.

# The worst-case complexity of symmetric strategy improvement

Tom van Dijk  Georg Loho  Matthew T. Maat

###### Abstract

Symmetric strategy improvement is an algorithm introduced by Schewe et al.
(ICALP 2015) that can be used to solve two-player games on directed graphs
such as parity games and mean payoff games. In contrast to the usual well-
known strategy improvement algorithm, it iterates over strategies of both
players simultaneously. The symmetric version solves the known worst-case
examples for strategy improvement quickly, however its worst-case complexity
remained open.

We present a class of worst-case examples for symmetric strategy improvement
on which this symmetric version also takes exponentially many steps.
Remarkably, our examples exhibit this behaviour for any choice of improvement
rule, which is in contrast to classical strategy improvement where hard
instances are usually hand-crafted for a specific improvement rule. We present
a generalized version of symmetric strategy iteration depending less rigidly
on the interplay of the strategies of both players. However, it turns out it
has the same shortcomings.

###### keywords:

Parity game, Mean payoff game, Symmetric strategy improvement, Strategy
improvement, Worst-case complexity

###### category:

##  1 Introduction

We study certain classes of infinite turn-based games on directed graphs
between two players, also called infinitary payoff games, which includes
parity games and discounted/mean payoff games. These games are interesting
from an algorithmic perspective and from the viewpoint of complexity theory.

First, there are various problems that relate to solving these games. Solving
parity games is important for formal verification and synthesis of programs,
as many properties of programs are naturally specified by means of fixed
points; parity games capture the expressive power of nested least and greatest
fixed point operators. In particular, there are linear reductions between
parity games and the model checking problem of the modal $\mu$-calculus [11,
34]. Solving mean payoff games is equivalent to problems like solving energy
games [4], deciding feasibility in tropical linear programming [1], scheduling
with AND/OR precedence constraints [25], and the max-atoms problem [3].

Another notable aspect of these games is their complexity status. It is known
that there is a polynomial-time reduction from parity games to mean payoff
games, and from mean to discounted payoff games. Many classes of these games
are known to be contained in the intersection of NP and coNP [6, 36], and
parity games and mean payoff games have been shown to even lie in the
intersection of UP and coUP [23]. However, the question whether there exists a
polynomial-time algorithm for any of these games has been open for decades.

### Related work

Many algorithms have been proposed for solving parity games and mean payoff
games with the main algorithm classes being value iteration [19, 10, 14],
strategy improvement [22, 2] and attractor-based algorithms [31, 35], where we
list only a small part of the many papers. For most of these algorithms there
are instances which take exponentially many steps; these are usually simple
for value iteration, while work by Van Dijk [33] demonstrates an exponential
lower bound to many attractor-based algorithms. Recently, it has been shown
that parity games can actually be solved in quasi-polynomial time: after the
breakthrough in [5], several other quasi-polynomial algorithms have been
found, including [8, 13, 20, 27]. However, most of these approaches are likely
to be inherently superpolynomial as demonstrated in [7].

Strategy improvement [2, 12, 22, 26, 28, 29] (also called strategy iteration
or policy iteration) is considered to be a viable candidate for a polynomial-
time algorithm for many classes of infinitary payoff games due to its inherent
combinatorial nature. This method evaluates strategies by means of a function
on the nodes in the graph called the _valuation_. It then iteratively makes
changes to a strategy, improving the valuation, until an optimal strategy is
found. When there are multiple options for improvements, the choice is made by
a so-called _improvement rule_. There are a few valuations mainly used in the
literature [2, 12, 22, 28]. Based on these, many well-known improvement rules
have exponential worst-case running time as demonstrated by sophisticated
worst-case constructions, in particular by Friedmann et al. (see e.g. [9, 15,
16]). The main idea behind the worst-case constructions is that one player can
‘trap’ the other player repeatedly in different configurations so that the
encountered strategies simulate a binary counter.

While infinitary payoff games are symmetric in the two players by their
nature, only some algorithms explicitly exploit this symmetry. Most attractor-
based algorithms for parity games are inherently symmetric by simultaneously
considering the game from the perspective of both players, while value
iteration and strategy improvement algorithms are mostly inherently
asymmetric. Recently, a quasipolynomial symmetric algorithm for parity games
was proposed by Jurdzinski et al. [21].

Our work is mainly motivated by a symmetric version of strategy iteration for
infinitary payoff games established in [30]. This variant maintains two
strategies, one for each player. The players then iteratively improve their
strategy, using information from the best response to their opponent’s
strategy. This reduces the number of iterations needed in practice, and also
does not have superpolynomial running time on the type of examples that were
constructed for classic strategy improvement. The worst-case running time of
this variant was unknown so far.

### Our contribution

We develop a construction exhibiting exponential running time for symmetric
strategy improvement (SSI). Our main result is the following:

######  Theorem 1.1.

In the worst case, the number of iterations of symmetric strategy improvement
in parity games, mean payoff games and discounted payoff games is exponential
in the number of nodes and edges in the graph _independently_ of the
improvement rule. This holds for any of the currently used valuations in the
literature.

It is remarkable that the result holds for any improvement rule. This is
different from regular strategy improvement, where the existence of a
(theoretical) improvement rule for which the algorithm terminates in a linear
number of iterations is guaranteed, see [15, Lemma 4.2]. By our Theorem 1.1,
this does not exist for symmetric strategy iteration.

Moreover, we present a generalization of SSI which uses the valuation directly
and not only the strategy of the opponent, allowing for more freedom to
potentially overcome the exponential instances. However, we strengthen Theorem
1.1 with a subtle adapation of the worst-case instances to hold also for the
generalization. This suggests that one needs a different approach involving
more than only local information to benefit from insights in the interplay of
strategies for both players.

### Technical overview

To arrive at our main result, we derive a class of games for which SSI needs
exponential running time. It is a careful adaptation (depicted in Figure 3) of
the basic example from [2, 17] in such a way that the two players are both
distracted by the other player’s strategy. The key insight here is that the
optimal counterstrategy to a bad strategy can also be a bad strategy itself.
Hence restricting to moves from the optimal counterstrategy prevents them from
making the crucial switches for achieving actual progress.

Our family of games has a self-similar structure. It requires the algorithm to
solve a subgame first, and then after the important switches are made, solve
the same subgame again, leading eventually to the exponential blowup of the
number of iterations.

Recall that symmetric strategy iteration picks only edges of the optimal
counter strategy. While this implicitly also uses the valuation, as it is
defined via the subgraph arising from the optimal counterstrategy, the
generalization directly compares the valuations of the nodes. Only those edges
are considered, which provide a local improvement over the valuations of both
players.

To derive the lower bound construction for the generalization, we introduce a
new gadget (Figure 5). This replaces each of the iteratively arranged pairs of
nodes in the former family. The gadget then forces the generalization to
exhibit a similar behaviour as the original SSI.

### Paper organization

We provide the necessary background on parity games and (symmetric) strategy
improvement in Section 2. We introduce generalized symmetric strategy
improvement in Section 3. Then, Section 4 presents the structure and
iterations of the basic exponential instance for SSI. This is refined in
Sections 5 and 6 to the generalized version of SSI and arbitrary improvement
rules. We conclude with a discussion of potential extensions and limitations
of our construction.

##  2 Preliminaries

### Parity games

A parity game is a game played between two players, called player 0 and player
1. It is played on the nodes of a directed graph $G=(V,E)$, where the nodes
are partitioned into $V=V_{0}\cup V_{1}$, and $V_{i}$ is controlled by player
$i$. We assume every node has at least one outgoing edge. Associated with the
nodes of the graph is a priority function $p\colon V\to Q$, where
$Q\subset\mathbb{Z}$. At the start of the game, a pebble is placed on one of
the nodes. A move is made by the player controlling the node that the pebble
is currently on, and it consists of this player choosing an outgoing edge from
this node. The pebble moves along the edge to the next node. The players keep
making moves indefinitely. The winner of the game is decided by the largest
node priority that the pebble encounters infinitely often. If it is even,
player 0 wins, and if it is odd, player 1 wins.

It is well known that parity games are positionally determined, meaning that
there always is a player that has a positional winning strategy. Positional
means here that one only takes into account on which node the pebble currently
is. Therefore, we define a strategy for player 0 as a function $\sigma\colon
V_{0}\to V$ (with the condition that $(v,\sigma(v))\in E$ for all nodes $v\in
V_{0}$). Similarly, a player 1 strategy is a function $\tau:V_{1}\to V$ (with
$(v,\tau(v))\in E$ for all nodes $v\in V_{1}$).

Figure 1: Left: A parity game. Priorities are shown in the nodes. Nodes
controlled by player 0 are shown as circles, and nodes controlled by player 1
are squares. The sets of winning starting nodes for player 0 and 1 are $W_{0}$
and $W_{1}$, and the winning strategies are marked by dashed lines. Right: A
sink parity game with a strategy $\sigma$ (dashed) and its optimal
counterstrategy $\bar{\sigma}$ (dotted).

### Sink parity games

In this paper, we restrict ourselves to a class of parity games called _sink
parity games_ as it allows to simplify the arguments for valuations. This
class has often been used to show lower bounds for parity game algorithms (see
e.g. [15, 18]). Solving sink parity games is as hard as solving any parity
game, see Lemma 2.3.

######  Definition 2.1.

A _sink parity game_ is a parity game that fulfills the following conditions:

  1. 1.

There exists a so-called _sink node_ $\top$ for which $p(\top)<p(v)$ for all
nodes in $V\backslash\\{\top\\}$, and whose only outgoing edge is
$(\top,\top)$.

  2. 2.

There exists a player 0 strategy $\sigma$ such that, when it is played, the
highest priority (except $\top$) in any possible cycle is even.

  3. 3.

There exists a player 1 strategy $\tau$ such that, when it is played, the
highest priority (except $\top$) in any possible cycle is odd.

We call player 0 and player 1 strategies that satisfy the above conditions
admissible. If player 0 plays an admissible strategy $\sigma$ and player 1
plays an admissible strategy $\tau$, then the pebble must end up at $\top$.
Otherwise, it would enter the same node outside $\top$ twice, which would
create a cycle, and the highest priority of the cycle would have to be odd and
even at the same time. This also implies that $\top$ is reachable for the
other player when $\sigma$ or $\tau$ is played. One may say that the result of
best play in a sink parity game is a ‘tie’.

### Valuations of strategies

In the remainder of this section, we describe (symmetric) strategy improvement
in parity games. We use the valuation of [12] and [24], adapted to sink parity
games. The advantages of using this framework are that it is simpler to
explain, and it focuses on the crucial second component of the most commonly
used valuation by Jurdzinksi and Vöge [22]. In sink parity games and their
related mean/discounted payoff games, the valuation that we describe here is
equivalent to the other used versions of strategy improvement for parity games
and mean payoff games [2, 22, 28].

Now, suppose player 0 and player 1 both fix a strategy $\sigma$ and $\tau$,
respectively. Then, given a starting node $v$, the course of the game is
fixed. We want to evaluate how ‘good’ this outcome is for player 0. This is
expressed in the play value $\Theta_{\sigma,\tau}(v)$. If the pebble does not
reach $\top$, then it must eventually follow some cycle. If the highest
priority in the cycle is even, then this is very good for player 0, so we
assign $\infty$ to this play. If the priority is odd, we assign it value
$-\infty$. Otherwise, the pebble follows a path to $\top$. In this case we
establish the play value by counting how often each priority on this path is
encountered. The even player aims to encounter many high even priorities and
little high odd priorities on this path. The following definition formalizes
this.

######  Definition 2.2.

Let $\sigma$ and $\tau$ be a player 0 and player 1 strategy, respectively.
Their _play value_ is a function $\Theta_{\sigma,\tau}:V\to\mathbb{Z}_{\geq
0}^{Q}\cup\\{-\infty,\infty\\}$, with $\mathbb{Z}_{\geq 0}^{Q}$ the set of
nonnegative integer vectors indexed by the priority set $Q$. It is defined as
follows:

  * •

Suppose the nodes encountered are
$v=v_{1},v_{2},\ldots,v_{k},\top,\top,\ldots$ (with $v_{k}\neq\top$). Then for
any $q\in Q$, the $q$-element of $\Theta_{\sigma,\tau}$ (the component of the
vector in $\mathbb{Z}_{\geq 0}^{Q}$ indexed by $q$) is given by
$\left(\Theta_{\sigma,\tau}(v)\right)_{q}=|\\{j\leq k:p(v_{j})=q\\}|$.

  * •

If $\top$ is not reached and player 0 wins, then
$\Theta_{\sigma,\tau}=\infty$.

  * •

If $\top$ is not reached and player 1 wins, then
$\Theta_{\sigma,\tau}=-\infty$.

We can compare play values by how ‘good’ they are for player 0. This is done
by a total order $\trianglelefteq$ on $\mathbb{Z}_{\geq
0}^{Q}\cup\\{-\infty,\infty\\}$. The smallest element for $\trianglelefteq$ is
$-\infty$ and the largest is $\infty$. The order $\trianglelefteq$ compares
the play values in $\mathbb{Z}_{\geq 0}^{Q}$ lexicographically, but different
for even and odd indices. To be precise, suppose we have $B$ and $C$ in
$\mathbb{Z}_{\geq 0}^{Q}$, and that $B\neq C$. Let $q^{\prime}$ be the highest
priority $q$ for which $B_{q^{\prime}}\neq C_{q^{\prime}}$. We then say that
$B\triangleleft C$ if either $B_{q^{\prime}}<C_{q^{\prime}}$ and $q^{\prime}$
is even, or $B_{q^{\prime}}>C_{q^{\prime}}$ and $q^{\prime}$ is odd. So if
$B\triangleleft C$, then $B$ has either less of some high even priority or
more of some high odd priority, so $B$ is ‘worse’ for player 0. Then we use
the concept of play value to evaluate strategies. We evaluate a player 0
admissible strategy $\sigma$ by an optimal player 1 response $\bar{\sigma}$.
To be precise, the valuation of an admissible strategy $\sigma$ is a function
$\Xi_{\sigma}:V\to\mathbb{Z}_{\geq 0}^{Q}$ given by:
$\Xi_{\sigma}(v)=\min_{\trianglelefteq}\\{\Theta_{\sigma,\tau}(v)\>|\>\tau\text{
player 1 strategy}\\}=\Theta_{\sigma,\bar{\sigma}}(v)$

A strategy $\tau$ attaining the minimum in the above equation is an _(optimal)
counterstrategy_. Note that there exists a player 1 strategy $\bar{\sigma}$
that simultaneously attains the minimum for all nodes in $V$ (equation (11) in
[22]). In general, this strategy might not be unique, but we pick one
arbitrarily to be $\bar{\sigma}$ if there are multiple options. Moreover, an
optimal response $\bar{\sigma}$ can be computed efficiently. Because we have a
sink parity game and an admissible $\sigma$, the minimum is never $\infty$ or
$-\infty$, so we can regard the range of $\Xi_{\sigma}$ as $\mathbb{Z}_{\geq
0}^{Q}$.

The valuation of an admissible player 1 strategy $\tau$ is defined similarly
using an optimal response $\bar{\tau}$ from player 0:
$\Xi_{\tau}(v)=\max_{\trianglelefteq}\\{\Theta_{\sigma,\tau}(v)\>|\>\sigma\text{
player 0 strategy}\\}=\Theta_{\bar{\tau},\tau}$.

Figure 1 shows an example of a sink parity game with a strategy and its
counterstrategy. For example, we have $\Xi_{\sigma}(v_{2})=(0,1,0,0,0,1)$, as
the play resulting from $\sigma$ and its optimal counterstrategy
$\bar{\sigma}$ goes through the nodes with priorities 2 and 6. Likewise,
$\Xi_{\sigma}(v_{4})=(0,0,0,1,0,0)$, hence
$\Xi_{\sigma}(v_{2})\triangleright\Xi_{\sigma}(v_{4})$.

### Strategy improvement

The core idea behind strategy improvement is to make so-called improving
moves. Improving moves for player 0 are given by the edges $(v,v^{\prime})$
with $v\in V_{0}$ for which
$\Xi_{\sigma}(v^{\prime})\triangleright\Xi_{\sigma}(\sigma(v))$. That means
that, with a new strategy picking $v^{\prime}$ after $v$, player 0 can send
the pebble to a node with higher valuation than it currently does in $\sigma$.
We denote the set of improving moves for $\sigma$ by $I_{\sigma}$. Player 0
creates a new strategy $\sigma^{\prime}$ from $\sigma$ by making improving
moves, which means $\sigma^{\prime}(v)=v^{\prime}$ for a number of improving
moves $(v,v^{\prime})\in I_{\sigma}$ and $\sigma^{\prime}(v)=\sigma(v)$
everywhere else. Of course, there may be multiple improving edges per node.
The choice which edges to use to improve is decided by an improvement rule,
which is a function $f:\mathcal{P}(E)\to\mathcal{P}(E)$ that takes as input a
set of improving edges, and outputs a set of improving edges subject to the
following conditions:

  * •

If $|S|>0$, then $|f(S)|>0$.

  * •

$f(S)\subseteq S$ for all $S\in\mathcal{P}(E)$.

  * •

Every node has at most one outgoing edge in $f(S)$.

By [22], for any choice of improving edges, we have
$\Xi_{\sigma^{\prime}}(v)\trianglerighteq\Xi_{\sigma}(v)$ for every $v\in V$,
and $\Xi_{\sigma^{\prime}}(v)\triangleright\Xi_{\sigma}(v)$ for at least one
node $v$. Hence we increase the valuation of the strategy. Clearly, the new
strategy is also admissible as its valuation is not $-\infty$. Additionally,
if $\sigma$ has no improving moves, then we know that $\Xi_{\sigma}$ is
pointwise maximal in the space of valuations ([22, Lemma 5.8]). This leads to
the strategy improvement algorithm (Algorithm 1).

Algorithm 1 Strategy improvement

1:Start with some admissible strategy $\sigma$

2:Find an optimal counterstrategy $\bar{\sigma}$ to $\sigma$, compute
$\Xi_{\sigma}$ and $I_{\sigma}$

3:if $I_{\sigma}=\emptyset$ then return $\sigma$

4:else

5: Let $\sigma^{\prime}$ be the strategy obtained from $\sigma$ by applying
all improving moves from $f(I_{\sigma})$

6: $\sigma\leftarrow\sigma^{\prime}$, go to 2

7:end if

We can also define improving moves for player 1, by saying $(v,v^{\prime})$
with $v\in V_{1}$ is an improving move if
$\Xi_{\tau}(v^{\prime})\triangleleft\Xi_{\tau}(\tau(v))$. We denote the set of
improving moves for player 1 by $I_{\tau}$. Similar to before, if
$\tau^{\prime}$ is obtained from $\tau$ by making improving moves,
$\Xi_{\tau^{\prime}}(v)\trianglelefteq\Xi_{\tau}(v)$ for every $v\in V$, and
$\Xi_{\tau^{\prime}}(v)\triangleleft\Xi_{\tau}(v)$ for at least one node $v$.
It is well-known that, if $\sigma$ is an optimal player 0 strategy (maximizing
$\Xi_{\sigma}$ pointwise) and $\tau$ and an optimal player 1 strategy
(minimizing $\Xi_{\tau}$ pointwise), then $\Xi_{\sigma}=\Xi_{\tau}$.

Now why are we interested in finding the strategy $\sigma$ that yields the
highest valuation $\Xi_{\sigma}$ in a sink parity game? The winner of a sink
parity game is already known, since the best both players can do is go to the
sink node $\top$. However, even in a sink parity game, finding the optimal
strategy (yielding the $\trianglelefteq$-best $\Xi_{\sigma}$) is as difficult
as solving parity games, as noted before in [16]. It is similar to the
reduction to the longest shortest path problem in [2] and escape games in
[29].

######  Lemma 2.3.

Deciding the winning starting sets and the winning strategies in a parity game
can be polynomial-time reduced to finding a player 0 strategy $\sigma$ in a
sink parity game that maximizes $\Xi_{\sigma}$.

Suppose we have a parity game $G=(V=V_{0}\cup V_{1},E)$ with priority function
$p:V\to\mathbb{Z}$. We may assume that there are no cycles within $V_{0}$ or
within $V_{1}$. This is because we can always add nodes with small priorities
controlled by player 0 in the middle of cycles in $V_{1}$ and vice versa
without affecting the outcome of the game. Now we construct a parity game
$G^{\prime}=(V^{\prime},E^{\prime})$ from $G$, by adding two extra nodes,
$\top$ and $w$. We extend $p$ by choosing $p(\top)$ smaller than all other
priorities, and taking for $p(w)$ an even number higher than all other
priorities. We add an edge from every node in $V_{0}$ to $\top$, from every
node in $V_{1}$ to $w$, from $w$ to $\top$ and from $\top$ to $\top$.

Figure 2: Reduction to a sink parity game

This is clearly a sink parity game, since player 0 has an admissible strategy
by always going to $\top$, and player 1 has an admissible strategy by going to
$w$. Now let $\sigma$ be an optimal player 0 strategy that maximizes
$\Xi_{\sigma}$ pointwise, and let $\bar{\sigma}$ be player 1’s optimal
response. Since $p(w)$ is even and very large, if player 1 can avoid entering
$\top$ through $w$, they will do so. Define the subgraph $G^{\prime}_{\sigma}$
by the graph with the same node set as $G^{\prime}$ and with edge set
$\\{(v,\sigma(v)):v\in V_{0}^{\prime}\\}\cup\\{(v,v^{\prime})\in
E^{\prime}:v\in V_{1}^{\prime}\\}$. Suppose for a node $v$ that
$\left(\Xi_{\sigma}(v)\right)_{p(w)}=1$. This implies that in
$G^{\prime}_{\sigma}$, the node $\top$ is only reachable from $v$ through $w$.
In particular, this means that player 1 would always have to end in a cycle in
$V$ if they would not have the option of going to $w$. Because $\sigma$ is
admissible, this cycle has an even highest priority. This implies that, in the
original game $G$, player 0 wins the game that starts at $v$ by playing
$\sigma$. If, on the other hand, $\left(\Xi_{\sigma}(v)\right)_{p(w)}=0$, this
implies that $\left(\Xi_{\tau}(v)\right)_{p(w)}=0$, and we can argue in the
same way that player 0 can only reach cycles of odd priority in $V$ if player
1 plays $\tau$. Hence $\tau$ wins for player 1 in the parity game $G$ that
starts from $v$. So we found the winning starting sets and winning strategies
for both players in $G$. (note that we could also have made the above
construction with $p(w)$ odd and connecting player 0 nodes to $w$ and player 1
nodes with $\top$). See also Example A.1.

### Symmetric strategy improvement

The symmetric strategy improvement (SSI) algorithm was introduced by Schewe et
al. in [30] as a symmetric version of strategy improvement. The algorithm
maintains and improves two strategies simultaneously: a player 0 strategy
$\sigma$ and a player 1 strategy $\tau$. It uses an optimal counterstrategy
$\bar{\tau}$ to $\tau$ to select improving moves for $\sigma$, and an optimal
counterstrategy $\bar{\sigma}$ to $\sigma$ to select improvements for $\tau$.
Note that this could be applied to a broader class of games than just (sink)
parity games, in particular mean and discounted payoff games. It is described
in Algorithm 2 where we expicitly include the choice of an improvement rule
$f\colon\mathcal{P}(E)\to\mathcal{P}(E)$.

Algorithm 2 Symmetric strategy improvement

1:Start with some pair of admissible strategies $\sigma$,$\tau$

2:Find counterstrategies $\bar{\sigma}$ and $\bar{\tau}$ and compute
$I_{\sigma}$ and $I_{\tau}$

3:$I\leftarrow f\left((I_{\sigma}\cap\\{(v,\bar{\tau}(v))|v\in
V_{0}\\})\cup(I_{\tau}\cap\\{(v,\bar{\sigma}(v))|v\in V_{1}\\}))\right)$

4:Let $\sigma^{\prime},\tau^{\prime}$ be result of applying all improving
moves from $I$ to $\sigma,\tau$

5:if $\sigma=\sigma^{\prime}$ and  $\tau=\tau^{\prime}$ then return
$\sigma,\tau$

6:else

7: $\sigma\leftarrow\sigma^{\prime}$, $\tau\leftarrow\tau^{\prime}$, go to 2

8:end if

It is clear that the algorithm terminates, since any improving move improves
the valuation for the respective player, and there is only a finite number of
strategies (having a fixed valuation) for both players. The following lemma
implies that the algorithm only terminates when the resulting pair of
strategies $(\sigma,\tau)$ is optimal for the players. It is implicitly proven
in [30, Lemma 3].

######  Lemma 2.4.

Suppose $\sigma$ is a non-optimal player 0 strategy or $\tau$ is a non-optimal
player 1 strategy. Let $\bar{\sigma}$ and $\bar{\tau}$ be optimal
counterstrategies to $\sigma$ and $\tau$, respectively. Then at least one of
the sets $I_{\sigma}\cap\\{(v,\bar{\tau}(v))|v\in V_{0}\\}$ and
$I_{\tau}\cap\\{(v,\bar{\sigma}(v))|v\in V_{1}\\}$ is nonempty.

##  3 Generalized symmetric strategy improvement

It was an intriguing insight by Schewe et al. how the interplay between
strategies of both players can be used to overcome the known hard instances of
strategy improvement. Since the evaluation of the goodness of a strategy
relies on the valuation, we go one step further and directly use the interplay
between the valuations arising from the strategies of the two players to make
the improvements. While this can overcome the first basic family of hard
instances presented in Section 4, we show in Section 5 that actually both
versions can still be forced to take exponentially many steps. In this way, we
extend the result of Theorem 1.1.

Our selection of improving edges contains the original set but is bigger in
general. Instead of basing the choices just on optimal counterstrategies, we
construct sets $J_{\sigma}(\tau)$ and $J_{\tau}(\sigma)$ by directly comparing
locally the valuations of adjacent nodes:

$\displaystyle J_{\sigma}(\tau)$ $\displaystyle=\\{(v,w):\;v\in
V_{0}\wedge\Xi_{\tau}(w)\trianglerighteq\Xi_{\tau}(\sigma(v))\\},$
$\displaystyle J_{\tau}(\sigma)$ $\displaystyle=\\{(v,w):\;v\in
V_{1}\wedge\Xi_{\sigma}(w)\trianglelefteq\Xi_{\sigma}(\tau(v))\\}.$

These notions allow us to state our generalized version in Algorithm 3. They
are in some sense the counterparts of $I_{\sigma}$ and $I_{\tau}$, recall that
$I_{\sigma}=\\{(v,w):\;v\in
V_{0}\wedge\Xi_{\sigma}(w)\triangleright\Xi_{\sigma}(\sigma(v))\\}$. One
obtains the original SSI back in this context by choosing only those
improvement rules that select only edges used by $\bar{\sigma}$ and
$\bar{\tau}$.

Algorithm 3 Generalized symmetric strategy improvement

1:Start with some admissible strategies $\sigma$ and $\tau$

2:Find $I_{\sigma}$, $I_{\tau}$, $J_{\sigma}(\tau)$ and $J_{\tau}(\sigma)$

3:$I\leftarrow f\left(\left(I_{\sigma}\cap
J_{\sigma}(\tau)\right)\cup\left(I_{\tau}\cap J_{\tau}(\sigma)\right)\right)$

4:Let $\sigma^{\prime},\tau^{\prime}$ be result of applying all improving
moves from $I$ to $\sigma,\tau$

5:if $\sigma=\sigma^{\prime}$ and  $\tau=\tau^{\prime}$ then return
$\sigma,\tau$

6:else

7: $\sigma\leftarrow\sigma^{\prime}$, $\tau\leftarrow\tau^{\prime}$, go to 2

8:end if

### Correctness of generalized symmetric strategy improvement

Like for normal SSI, it is clear that the algorithm terminates. We are left to
show that there is always an improving move possible if the pair of strategies
is not optimal. We do so by showing that all the improving moves that were
possible in SSI are also possible in the generalization. Correctness of
Algorithm 3 then follows from Lemma 2.4.

######  Lemma 3.1.

For any pair of strategies $\sigma,\tau$, we have that any edge
$(v,\bar{\sigma}(v))$ is in $J_{\tau}(\sigma)$, and any edge
$(v,\bar{\tau}(v))$ is in $J_{\sigma}(\tau)$.

We do so by contradiction. Suppose there is an edge $(v,\bar{\sigma}(v))$ that
is not in $J_{\tau}(\sigma)$. This means by definition of $J_{\tau}(\sigma)$
that $\Xi_{\sigma}(\bar{\sigma}(v))\triangleright\Xi_{\sigma}(\tau(v))$. Note
that the valuation of $\sigma$, which is $\Xi_{\sigma}$, is equal to
$\Theta_{\sigma\bar{\sigma}}$. Now consider the strategy subgraph
$G_{\sigma}:=(V,E_{\sigma})$ with $E_{\sigma}:=\\{(v,w):v\in
V_{1}\\}\cup\\{(v,\sigma(v)):v\in V_{0}\\})$. In $G_{\sigma}$, the valuation
of $\bar{\sigma}$ is equal to $\Theta_{\sigma\bar{\sigma}}=\Xi_{\sigma}$, as
there is only one player 0 strategy possible. But then
$\Xi_{\sigma}(\bar{\sigma}(v))\triangleright\Xi_{\sigma}(\tau(v))$ implies
that $(v,\tau(v))$ is an improving move for player 1 strategy $\bar{\sigma}$
in the game $G_{\sigma}$. However, this is not possible, since $\bar{\sigma}$
is defined to be an optimal counterstrategy to $\sigma$. We conclude that
$(v,\bar{\sigma}(v))\in J_{\tau}(\sigma)$. The proof of $(v,\bar{\tau}(v))\in
J_{\sigma}(\tau)$ is analogous.

##  4 Counterexample for worst-case complexity

We present a family of parity games for which the original SSI needs
exponentially many iterations, where we restrict to the SWITCH-ALL improvement
rule at first. This rule selects one improving edge for every node that has an
outgoing improving edge in $S$. We generalize this to arbitrary improvement
rules in Section 6. Some animations of the iterations of the examples
presented in Sections 4 and 5 can be found at
https://github.com/MatthewMaat/SI-animations/tree/master/Example%20animations

We use a sequence of sink parity games $(G_{n})_{n\in\mathbb{N}}$ whose nodes
and edges of $G_{n}$ are listed in Table 1 and Figure 3. The main structure is
similar to the mean payoff game from [2] and [17], with the main difference
being that we have backward edges to the ‘start’ of the game.

Node | Player | Priority | Successors
---|---|---|---
$a_{1}$ | Player 0 | 3 |  $a_{2}$, $d_{2}$
$a_{i}$, $i=2,\ldots,n$ | Player 0 | $2i+1$ |  $a_{1}$, $a_{i+1}$, $d_{i+1}$
$d_{1}$ | Player 1 | 4 |  $a_{2}$, $d_{2}$
$d_{i}$, $i=2,\ldots,n$ | Player 1 | $2i+2$ |  $d_{1}$, $a_{i+1}$, $d_{i+1}$
$a_{n+1}$ | Player 0 | $1$ | $a_{n+1}$
$d_{n+1}$ | Player 1 | $2n+4$ | $a_{n+1}$
Table 1: Nodes and edges of $G_{n}$ Figure 3: The graph $G_{n}$, with the
priorities written in the nodes. The initial strategies $\sigma_{0}$ and
$\tau_{0}$ are dashed.

Initial strategies We define $\sigma_{0}$ and $\tau_{0}$ by
$\sigma_{0}(a_{i})=a_{i+1}$ and $\tau_{0}(d_{i})=d_{i+1}$ for
$i=1,2,\ldots,n$, $\sigma_{0}(a_{n+1})=a_{n+1}$ and
$\tau_{0}(d_{n+1})=a_{n+1}$.

$G_{n}$ is a sink parity game. The node $a_{n+1}$ is the sink node with low
priority. Also, $\sigma_{0}$ is an admissible player 0 strategy. If the pebble
enters any node $a_{i}$ if $\sigma_{0}$ is played, it will end at the sink.
The only way player 1 could try to avoid this is by trying to keep the pebble
within $d_{1},d_{2},\ldots,d_{n}$, but then this will create a cycle with even
highest priority. Hence $\sigma_{0}$ is admissible. Likewise, $\tau_{0}$ is
admissible, so we have a sink parity game.

Optimal strategies of the players. Recall that a strategy having a high
valuation (for player 0) corresponds to being able to pass through node with
high even priorities and avoiding nodes with high odd priorities. Therefore,
to maximize their valuation, player 0 lets the pebble pass $d_{n+1}$, which
has the largest (and even) priority in the game. Playing a strategy $\sigma$
that achieves this when starting from a node $v$ yields
$\left(\Xi_{\sigma}(v)\right)_{2n+4}=1$. This means the valuation is larger
than any strategy that does not achieve this. There is only one strategy where
player 0 can do this from every starting node $a_{i}$, namely the strategy
with $\sigma(a_{i})=a_{i+1}$ for $i<n$ and $\sigma_{a_{n}}=d_{n+1}$.
Ironically, this differs from $\sigma_{0}$ in only one edge. However, as we
will see, we avoid making this switch for a long time. Likewise, player 1’s
goal is to avoid $d_{n+1}$. Their only strategy to avoid it from every node
$d_{i}$ is to pick $\tau(d_{i})=d_{i+1}$ for $i<n$, and $\tau(d_{n})=a_{n+1}$.
Again, player 1 is only one switch from optimal when starting with $\tau_{0}$.

The remainder of this section is dedicated to the proof of the following
proposition, where we consider iterations in $5$ phases. In Section 6, we
discuss how our main result follows from this.

######  Proposition 4.1.

Suppose SSI with the SWITCH-ALL rule on the game graph $G_{n}$ starts with the
strategy pair $\sigma_{0},\tau_{0}$. Then after $2^{n+1}-3$ iterations, the
optimal strategies $\sigma$ and $\tau$ are found. The optimal strategies for
both players do not appear in any earlier iteration.

######  Proof 4.2.

The reader can verify that one needs only one iteration to reach the optimum
in $G_{1}$. We assume the claim to be true for $G_{j-1}$ and show that it
holds for $G_{j}$ to conclude the proof by induction. We do this by showing
that the iterations of SSI are as follows:

  1. 1.

$2^{j}-3$ iterations with switches from $a_{1},a_{2},\ldots,a_{j-1}$ and
$d_{1},d_{2},\ldots,d_{j-1}$

  2. 2.

One iteration where the only switch made is $(a_{j},a_{1})$

  3. 3.

One iteration where the only switch made is $(d_{j},a_{j+1})$

  4. 4.

One iteration where the only switch made is $(a_{j},d_{j+1})$

  5. 5.

$2^{j}-3$ iterations with switches from $a_{1},a_{2},\ldots,a_{j-1}$ and
$d_{1},d_{2},\ldots,d_{j-1}$

Then clearly the total number of iterations is $2\cdot(2^{j}-3)+3=2^{j+1}-3$.
Now, we elaborate on these $5$ steps, where the first $2^{j}-3$ iterations
need extra insights captured in the following three observations.

As long as $\sigma(a_{j})=a_{j+1}$, we have $\bar{\sigma}(d_{j})=d_{1}$.
Likewise, as long as $\tau(d_{j})=d_{j+1}$, we have $\bar{\tau}(a_{j})=a_{1}$
Suppose $\sigma(a_{j})=a_{j+1}$, and we look at what $\bar{\sigma}$ could be.
Recall that player 1’s goal is to reach $a_{j+1}$ without passing $d_{j+1}$.
Starting from $d_{j}$, player 1 can do so in two ways: by picking
$\bar{\sigma}(d_{j})=a_{j+1}$, or by picking $\bar{\sigma}(d_{j})=d_{1}$ and
then choosing $\bar{\sigma}$ for $d_{1},d_{2},\ldots,d_{j-1}$ such that the
pebble ends up at $a_{j}$. The first option gives
$\left(\Xi_{\sigma}(d_{j})\right)_{2j+1}=0$ while the second one gives
$\left(\Xi_{\sigma}(d_{j})\right)_{2j+1}=1$. Hence, the latter gives a lower
valuation, and $\bar{\sigma}(d_{j})=d_{1}$. We can prove similarly that while
$\tau(d_{j})=d_{j+1}$, we have $\bar{\tau}(a_{j})=a_{1}$.

Suppose $\sigma(a_{j})=a_{j+1}$ and $\tau(d_{j})=d_{j+1}$. Then
$\Xi_{\sigma}(a_{j})\triangleleft\Xi_{\sigma}(d_{j})$ and
$\Xi_{\tau}(a_{j})\triangleleft\Xi_{\tau}(d_{j})$. In both cases, the
valuation vectors compared differ in their $q$-position where $q\geq 2j+1$.
From the proof of Observation 4.2 we know that when the pebble starts at
$d_{j}$ and players play $\sigma,\bar{\sigma}$, the pebble goes to $d_{1}$,
then to $a_{j}$ and directly to $a_{j+1}$. Hence $\Xi_{\sigma}(a_{j})$ and
$\Xi_{\sigma}(d_{j})$ differ in their $p(d_{j})=2j+2$-component, where the
latter valuation has a 1. Then it follows that
$\Xi_{\sigma}(a_{j})\triangleleft\Xi_{\sigma}(d_{j})$, as the values in the
vector corresponding to smaller priorities are insignificant when comparing
these two valuations. We can likewise see that
$\Xi_{\tau}(a_{j})\triangleleft\Xi_{\tau}(d_{j})$ because they differ in their
$p(a_{j})=2j+1$-component.

Suppose $\sigma(a_{j})=a_{j+1}$ and $\tau(d_{j})=d_{j+1}$. Then edge
$(a_{j},a_{1})$ is improving only if $\sigma(a_{i})=a_{i+1}$ for $i<j-1$ and
$\sigma(a_{j-1})=d_{j}$. Edge $(d_{j},d_{1})$ is never improving. Suppose
player 0 switches the improving edge $(a_{j},a_{1})$ while $\sigma$ is
different than specified above. The resulting strategy should also be
admissible. However, player 1 can play strategy $\bar{\sigma}(d_{i})=d_{i+1}$
for $i<j-1$ and $\bar{\sigma}(d_{j-1})=a_{j}$, creating a cycle with highest
priority $p(a_{j})=2j+1$. So the new strategy is not admissible, so
$(a_{j},a_{1})$ could not have been improving. Likewise, suppose
$(d_{j},d_{1})$ is improving for some strategy $\tau$ and we switch it. Then
player 0 can play $\bar{\tau}(a_{i})=a_{i+1}$ for $i<j-1$ and
$\bar{\tau}(a_{j-1})=d_{j}$. This either creates a cycle with highest priority
$p(d_{j})=2n+2$ or player 1 creates another cycle within
$d_{1},d_{2},\ldots,d_{j-1}$. In both cases, the resulting player 1 strategy
cannot be admissible, so the edge could not have been improving.

From Observations 4.2 and 4.2, we can conclude that the strategies at $a_{j}$
and $d_{j}$ will not change until $\sigma$ fulfills the conditon of
Observation 4.2 ($\sigma(a_{i})=a_{i+1}$ for $i<j-1$ and
$\sigma(a_{j-1})=d_{j}$). Moreover, from Observation 4.2, we notice that at
this first part of the algorithm we may as well remove $a_{j+1}$ and
$d_{j+1}$, and set $p(a_{j})=1$ and add edges $(d_{j},a_{j})$, $(a_{j},a_{j})$
without changing any choices of SSI. But now we are left with an exact copy of
$G_{j-1}$, so by induction hypothesis, we know that SSI needs $2^{j}-3$
iterations to reach the optimal pair of strategies there. The optimal player 0
strategy in $G_{j-1}$ is $\sigma(a_{i})=a_{i+1}$ for $i<j-1$ and
$\sigma(a_{j-1})=d_{j}$, which we only reach after $2^{j}-3$ iterations. So
only then do we need to consider the original graph $G_{j}$ again and are we
able to switch edge $(a_{j},a_{1})$ by Observation 4.2.

Figure 4: The strategies $\sigma,\tau$ (dashed) after $2^{j}-3$ iterations of
SSI. Edges that are switched in the next 3 iterations are marked with 1,2,3.

The $(2^{j}-2$)-th iteration There are no improving moves in
$a_{1},\ldots,a_{j-1}$ or in $d_{1},\ldots,d_{j-1}$, as the strategies are
’optimal’ strategies in $G_{j-1}$. However, we do not have optimal strategies
in $G_{j}$ yet, so by Lemma 2.4, there must be at least one edge switched by
SSI. The only choice left is edge $(a_{j},a_{1})$, so this edge is now
switched.

The $(2^{j}-1)$-th iteration We have $\sigma=\bar{\tau}$ (recall $\bar{\tau}$
from Observation 4.2). Since $\tau$ is the same as in the last iteration, the
nodes $d_{1},\ldots,d_{j-1}$ do not have improving moves. Only the edge
$(d_{j},a_{j+1})$ can be switched. Since the strategies are not optimal yet,
again Lemma 2.4 implies that we switch exactly this edge in the $(2^{j}-1)$-th
iteration.

The $2^{j}$-th iteration At the start of the $2^{j}$-th iteration, we observe
that player 1’s strategy $\tau$ is equal to the counterstrategy
$\bar{\sigma}$. This is since player 1 can only reach the sink (avoiding
$d_{j+1}$) by playing $\bar{\sigma}(d_{j})=a_{j+1}$, and only with this
current strategy can player 1 additionally pass node $a_{j}$ on the way there
if player 0 plays $\sigma$. Hence, SSI does not make any improving moves for
player 1. If player 0 makes any switch in the nodes
$a_{1},a_{2},\ldots,a_{j-1}$, then this always allows player 1 to create a
cycle with odd highest priority, so this cannot be an improving move.
Therefore, SSI can only make a switch in $a_{j}$. The only improving move in
$a_{j}$ is $(a_{j},d_{j+1})$, so exactly this edge is switched in iteration
$2^{j}$.

The final $2^{j}-3$ iterations Notice that we will never again make switches
in nodes $a_{j}$ and $d_{j}$. Moreover,
$\Xi_{\sigma}(a_{j})\triangleright\Xi_{\sigma}(d_{j})$ and
$\Xi_{\tau}(a_{j})\triangleright\Xi_{\tau}(d_{j})$. We might as well replace
$d_{j}$ by a sink node of priority 1, and $a_{j}$ by a node with priority
$2j+2$ with an edge to the sink (and remove $a_{j+1},d_{j+1}$). This is
without changing any future iterations of SSI. But then we have again a copy
of $G_{j-1}$ with its respective starting strategies. Using the induction
hypothesis again, SSI takes another $2^{j}-3$ iterations. It reaches the
optimal strategies only in the last iteration. These strategies are also
optimal in $G_{j}$, and this completes the proof of Proposition 4.1.

##  5 Adapted counterexample for generalization of symmetric strategy
improvement

We consider the worst-case performance of the generalized version of SSI, when
the SWITCH-ALL rule is used. The generalized version can solve the games from
the previous section quickly, as it considers more improving moves. However,
in this section we show that the generalized version still has exponential
running time on a suitably modified version of the counterexample.

The overall structure is the same as for the original counterexample, but the
nodes $a_{i}$ and $b_{i}$ are replaced by gadgets as shown in Figure 5. The
full construction is described in Table 2. The nodes $a_{i}$ and $d_{i}$
(except the sink) have priorities larger than $N$ and the other nodes have
priority smaller than $N$, so the priorities of $a_{i}$ and $d_{i}$ are still
the most important ones.

The function of these gadgets is to make it harder for the players to switch.
Now for example, instead of just making a switch at $a_{i}$, player 0 has to
switch their choice at both $c_{i}$ and $m_{i}$ to significantly change the
course of the game. Additionally, the nodes $e_{i},f_{i},k_{i},l_{i}$ make
improving moves seem very insignificant with respect to differences in
valuation. Similar to Proposition 4.1, the following proposition holds:

######  Proposition 5.1.

Suppose generalized SSI on the game graph $G_{n}$ starts with
$\sigma_{0},\tau_{0}$. Then after $7\cdot 2^{n-1}-5$ iterations, the optimal
strategies $\sigma$ and $\tau$ are found. The optimal strategies for both
players do not appear in any earlier iteration.

######  Proof 5.2.

Figure 5: Subgraph for generalized SSI that replaces $a_{i}$ and $b_{i}$ when
$i>1$. Initial strategies $\sigma_{0}$ and $\tau_{0}$ are dashed. Nodes that
do not have all their incident edges shown are small and grey.

Node | Player | Priority | Successors |  | Node | Player | Priority | Successors
---|---|---|---|---|---|---|---|---
$a_{i}$ | Player 0 | $N+2i-1$ | $c_{i}$ |  | $a_{n+1}$ | Player 0 | $1$ | $a_{n+1}$
$d_{i}$ | Player 1 | $N+2i$ | $h_{i}$ |  | $d_{n+1}$ | Player 1 | $N+2n+2$ | $a_{n+1}$
$c_{i}$ | Player 0 | $14i+1$ |  $e_{i},m_{i}$, $(a_{1})$ |  | $e_{i}$ | Player 1 | $14i+4$ | $m_{i},a_{i+1}$
$m_{i}$ | Player 0 | $14i+3$ |  $f_{i},c_{i}$, $(a_{1})$ |  | $f_{i}$ | Player 1 | $14i+6$ | $c_{i},d_{i+1}$
$g_{i}$ | Player 1 | $14i+8$ |  $k_{i},h_{i}$, $(d_{1})$ |  | $k_{i}$ | Player 0 | $14i+11$ | $h_{i},a_{i+1}$
$h_{i}$ | Player 1 | $14i+10$ |  $l_{i},g_{i}$, $(d_{1})$ |  | $l_{i}$ | Player 0 | $14i+13$ | $g_{i},d_{i+1}$

$\sigma_{0}(a_{i})=c_{i}$ | $\tau_{0}(d_{i})=h_{i}$ | $\sigma_{0}(a_{n+1})=a_{n+1}$ | $\tau_{0}(d_{n+1})=a_{n+1}$
---|---|---|---
$\sigma_{0}(c_{i})=e_{i}$ | $\sigma_{0}(m_{i})=c_{i}$ | $\tau_{0}(g_{i})=h_{i}$ | $\tau_{0}(h_{i})=l_{i}$
$\tau_{0}(e_{i})=a_{i+1}$ | $\tau_{0}(f_{i})=d_{i+1}$ | $\sigma_{0}(k_{i})=a_{i+1}$ | $\sigma_{0}(l_{i})=d_{i+1}$

Table 2: Nodes, edges and initial strategies of the adapted counterexample. We
have $N=16n+16$, and $i$ ranges from 1 to $n$. Nodes between brackets mean
that they are only a successor if $i>1$.

We show this by induction similar to before. For $n=1$, the reader can verify
that in the first iteration we switch $(m_{1},f_{1})$ and $(g_{1},k_{1})$, and
in the second iteration we switch $(h_{1},g_{1})$ and $(c_{1},m_{1})$ to reach
the optimum. For the induction step, we assume the lemma holds for $G_{j-1}$,
and show that the iterations of generalized SSI on $G_{j}$ are as follows:

  1. 1.

$7\cdot 2^{j-1}-5$ iterations with switches in nodes $x_{i}$ with index $i<j$

  2. 2.

One iteration where only $(c_{j},a_{1})$ and $(m_{j},a_{1})$ are switched

  3. 3.

One iteration where only $(g_{j},k_{j})$ is switched

  4. 4.

One iteration where only $(h_{j},g_{j})$ is switched

  5. 5.

One iteration where only $(m_{j},f_{j})$ is switched

  6. 6.

One iteration where only $(c_{j},m_{j})$ is switched

  7. 7.

$7\cdot 2^{j-1}-5$ iterations with switches in nodes $x_{i}$ with index $i<j$

Similar to the proof of Proposition 4.1, we can argue about the phase of the
algorithm where no switches are yet made in the nodes $c_{j},m_{j},g_{j}$ and
$l_{j}$. We can observe that edges $(c_{j},a_{1})$ and $(m_{j},a_{1})$ are
part of $\bar{\tau}$ but not yet improving until player 0 plays a specific
strategy, and $(g_{j},d_{1})$ and $(h_{j},d_{1})$ are part of $\bar{\sigma}$
and never improving. So in the first phase, the only improving moves with
index $j$ are $(m_{j},f_{j})$ and $(g_{j},k_{j})$. But we do not make these
moves for a reason that is similar to Observation 4.2. If we consider the path
of the pebble when $\tau$ and $\bar{\tau}$ are played, then starting from
$f_{j}$, we go immediately to $d_{j+1}$, while from $c_{j}$ we go back to
$a_{1}$ and through $d_{j}$ to $d_{j+1}$. So $\Xi_{\tau}(c_{j})$ is much
bigger (because of the $p(d_{j})=N+2i$) than $\Xi_{\tau}(f_{j})$. Hence
generalized SSI never makes the switch $(m_{j},f_{j})$ in the beginning.
Likewise, the move $(g_{j},k_{j})$ is postponed by the algorithm. Therefore,
we can again pretend that $a_{j}$ is the sink and $d_{j}$ only has an edge
towards the sink and use the induction hypothesis to show that this first
phase takes $7\cdot 2^{j-1}-5$ iterations.

Now going back to the induction proof, the next five iterations of the
algorithm are similar to the three iterations in the middle of the
counterexample for SSI, except that we need two switches per module instead of
one.

For the last part, we can again pretend that $d_{j}$ is the sink and $a_{j}$ a
node with even priority with an edge to the sink. This yields a copy of
$G_{j-1}$, but with nodes like $c_{j-1}$ and $e_{j-1}$ and $(f_{j-1})$
switched. This, however, does not affect any choices of the algorithm (as the
valuations of $c_{i}$ and $e_{i}$ are always very close). Then using the
induction hypothesis, it follows that this last phase takes $7\cdot 2^{j-1}-5$
iterations. This completes the induction proof.

##  6 Concluding the proof

We look at the last details to prove Theorem 1.1. So far, we assumed that the
improvement rule SWITCH-ALL is used. It turns out that in many iterations of
(generalized) SSI, there is only one improving move. This implies the
following result.

######  Lemma 6.1.

The results of Propositions 4.1 and 5.1 hold for any improvement rule $f$.

We prove this by arguing that if we use SWITCH-ALL on the graphs $G_{n}$ for
both constructions, then either there is only one switch possible, or every
switch but one switch is irrelevant. Here irrelevant means that whether or not
we make the switch, the further course of the algorithm does not change, hence
the number of iterations can only increase if we decide not to make some
improving switches.

First, we consider the class of games $G_{n}$ that proved Proposition 4.1
(Figure 3). If we use the SWITCH-ALL rule, then by following the induction
proof we find that we make two switches per iteration whenever we make
switches at $a_{1}$ and $d_{1}$ (following from the induction basis), and we
make one switch in every other case (from the induction step). Note however,
that not making a switch in $d_{1}$ never has any effect on the course of the
algorithm. Observations 4.2, 4.2, 4.2 still hold if no switch is made in
$d_{1}$, and so does the rest of the induction step. It also follows that if
only $d_{1}$ is switched and $a_{1}$ not, then in the next iteration $a_{1}$
has the only possible switch. In all cases, symmetric strategy improvement
takes at least as many iterations as for SWITCH-ALL.

Next we consider the games $G_{n}$ from the proof of Proposition 5.1 (Figure
5). There are two cases where there are multiple switches when SWITCH-ALL is
used. First, the modules attached to $a_{1}$ and $d_{1}$ are switched at the
same time. However, for the same reason as above, we can ignore the second
module. Secondly, $(c_{i},a_{1})$ and $(m_{i},a_{1})$ are switched at the same
time. Note that if $(c_{i},a_{1})$ is switched, then any switch in $m_{i}$
becomes irrelevant as $m_{i}$ is not reachable at that moment for player 0,
and we make the switch $(m_{i},f_{i})$ three iterations later. If, on the
other hand, only $(m_{i},a_{1})$ is switched while $\sigma(c_{i})=e_{i}$, then
nothing significant changes in the game and in the next iteration we will
still have to switch $(c_{i},a_{1})$. Finally, if $(m_{i},a_{1})$ is switched
while $\sigma(c_{i})=m_{i}$ and $\sigma(m_{i})=f_{i}$, then the switch
$(c_{i},a_{1})$ becomes irrelevant after the switch as it only removes one
$14i+3$-priority from the valuation. So in all cases, there is only one
relevant switch. We conclude that using an improvement rule for this $G_{n}$
takes at least as many iterations as for SWITCH-ALL.

Note that the number of nodes and edges of $G_{n}$ for regular SSI is $2n+2$
and $6n$, respectively. Also, the running time of SSI cannot be more than the
total number of strategies for both players, which is exponential in the
number of nodes and edges. Hence the worst-case running time of symmetric
strategy improvement for parity games is exponential in the number of nodes
and edges. Moreover, we already noted that in sink parity games, the
valuations from the literature are equivalent. Furthermore, the result for
mean and discounted payoff games can be shown analogously to [15, Theorem
4.19]. This concludes the proof of Theorem 1.1.

Finally, the number of nodes and edges of our game $G_{n}$ for generalized SSI
is also linear in $n$. This yields the following result.

######  Theorem 6.2.

The results from Theorem 1.1 also hold for generalized SSI.

##  7 Discussion

We showed that both symmetric strategy improvement (SSI) and a generalization
have exponential worst-case time complexity. The reason is that they can make
too few crucial switches, as they are distracted by their opponent’s (bad)
strategy. In our example, the opponent’s valuation always steers the players
to make ‘bad’ improving moves. Hence, even using the local information of the
other player’s valuation is not always useful (an implementation of SSI and
its worst-case example can be found in Oink [32]). Remarkably, no improvement
rule can fix this issue. Furthermore, we presented a generalization of SSI and
its worst-case example which allows for more flexibility.

The parity game example presented in Figure 3 occurs to be trivial to solve
for various natural implementations. One could think of preprocessing
techniques like SCC decomposition, removing self-loops or choosing an initial
strategy with some heuristic (in fact, the construction in the proof of Lemma
2.3 gives such a heuristic that would solve the parity game quickly). There
are further tweaks like propagating information about which nodes are won
through the graph by attracting towards them. However, we argue that the main
principles of our counterexamples are robust against such tricks. Imagine the
parity game of Figure 3 to be part of a larger parity game, where $a_{n+1}$
looks much higher valued than $d_{n+1}$ at the beginning. Suppose that in
reality $d_{n+1}$ is winning for player 0 (or player 0 has a strategy such
that it has a large valuation in the version of SSI used here), and $a_{n+1}$
is winning for player 1 (or player 1 can let it have a low valuation). Then,
until SSI discovers the true value of $a_{n+1}$ and $d_{n+1}$, the best
possible strategies to play from $a_{1},a_{2},\ldots$ and $d_{1},d_{2},\ldots$
are in fact the strategies we use as initial strategies in Section 4. So most
likely, the preprocessing would pick these strategies or we quickly end up
with them after some iterations. Secondly, SCC decomposition can be tricked by
adding edges back from the rest of the game to $a_{1},d_{1}$ that are bad
choices for the player that can choose them, and the propagation trick is
stopped by the modules from Figure 5. It is likely that other optimizations,
assuming that they have a weakness, will be stopped by adding modules that
exploit this weakness in a similar way. Note, however, that structures like
those in our hard instances are unlikely to show up in practice. As observed
by the authors of SSI [30], the number of iterations of SSI is low on randomly
generated instances.

Our work leaves open if there is actually any way to use the interplay of
strategies of the two players which does not end up with exponential worst-
case running time. Our constructions suggest that the restriction imposed by
using local information of the opponent’s strategy might always be exploited
to lure the iterations into an exponential trap.

## References

  * [1] Marianne Akian, Stéphane Gaubert, and Alexander E. Guterman.  Tropical polyhedra are equivalent to mean payoff games.  Int. J. Algebra Comput., 22(1), 2012.  doi:10.1142/S0218196711006674.
  * [2] Henrik Björklund and Sergei G. Vorobyov.  A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games.  Discret. Appl. Math., 155(2):210–229, 2007.  doi:10.1016/j.dam.2006.04.029.
  * [3] Manuel Bodirsky and Marcello Mamino.  Tropically convex constraint satisfaction.  Theory Comput. Syst., 62(3):481–509, 2018.  doi:10.1007/s00224-017-9762-0.
  * [4] L. Brim, J. Chaloupka, L. Doyen, R. Gentilini, and J. F. Raskin.  Faster algorithms for mean-payoff games.  Form. Methods Syst. Des., 38(2):97–118, apr 2011.  doi:10.1007/s10703-010-0105-x.
  * [5] Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.  Deciding parity games in quasipolynomial time.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 252–263. ACM, 2017.  doi:10.1145/3055399.3055409.
  * [6] Anne Condon.  The complexity of stochastic games.  Information and Computation, 96(2):203–224, 1992.  URL: https://www.sciencedirect.com/science/article/pii/089054019290048K, doi:10.1016/0890-5401(92)90048-K.
  * [7] Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic, and Pawel Parys.  Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2333–2349. SIAM, 2019.  doi:10.1137/1.9781611975482.142.
  * [8] Daniele Dell’Erba and Sven Schewe.  Smaller progress measures and separating automata for parity games.  Frontiers Comput. Sci., 4, 2022.  doi:10.3389/fcomp.2022.936903.
  * [9] Yann Disser, Oliver Friedmann, and Alexander V. Hopp.  An exponential lower bound for zadeh’s pivot rule.  Math. Program., 199(1):865–936, 2023.  doi:10.1007/s10107-022-01848-x.
  * [10] Dani Dorfman, Haim Kaplan, and Uri Zwick.  A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games.  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 114:1–114:14, Dagstuhl, Germany, 2019\. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2019/10690, doi:10.4230/LIPIcs.ICALP.2019.114.
  * [11] E. Allen Emerson, Charanjit S. Jutla, and A. Prasad Sistla.  On model checking for the $\mathrm{\mu}$-calculus and its fragments.  Theor. Comput. Sci., 258(1-2):491–522, 2001.  doi:10.1016/S0304-3975(00)00034-7.
  * [12] John Fearnley.  Efficient parallel strategy improvement for parity games.  In Computer Aided Verification - 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part II, volume 10427 of Lecture Notes in Computer Science, pages 137–154. Springer, 2017.  doi:10.1007/978-3-319-63390-9\\_8.
  * [13] John Fearnley, Sanjay Jain, Bart de Keijzer, Sven Schewe, Frank Stephan, and Dominik Wojtczak.  An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space.  Int. J. Softw. Tools Technol. Transf., 21(3):325–349, 2019.  doi:10.1007/s10009-019-00509-3.
  * [14] Nathanaël Fijalkow, Paweł Gawrychowski, and Pierre Ohlmann.  Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games.  In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:15, Dagstuhl, Germany, 2020\. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2020/12701, doi:10.4230/LIPIcs.MFCS.2020.34.
  * [15] Oliver Friedmann.  Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs.  PhD thesis, Ludwig Maximilians University Munich, 2011.  URL: http://edoc.ub.uni-muenchen.de/13294/.
  * [16] Oliver Friedmann.  A superpolynomial lower bound for strategy iteration based on snare memorization.  Discret. Appl. Math., 161(10-11):1317–1337, 2013.  doi:10.1016/j.dam.2013.02.007.
  * [17] V. A. Gurvich, A. V. Karzanov, and L. G. Kachivan.  Cyclic games and an algorithm to find minimax cycle means in directed graphs.  USSR Computational Mathematics and Mathematical Physics, 28(5):85–91, 1988.  URL: http://www.maths.lse.ac.uk/Personal/stengel/ussrGKK.pdf.
  * [18] Thomas Dueholm Hansen.  Worst-case analysis of strategy iteration and the simplex method.  PhD thesis, Aarhus University, Denmark, 2012.  URL: https://pure.au.dk/portal/files/52807524/PhD_dissertation_Thomas_Dueholm_Hansen.pdf.
  * [19] Marcin Jurdzinski.  Small progress measures for solving parity games.  In STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings, volume 1770 of Lecture Notes in Computer Science, pages 290–301. Springer, 2000.  doi:10.1007/3-540-46541-3\\_24.
  * [20] Marcin Jurdzinski and Ranko Lazic.  Succinct progress measures for solving parity games.  In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–9. IEEE Computer Society, 2017.  doi:10.1109/LICS.2017.8005092.
  * [21] Marcin Jurdziński, Rémi Morvan, Pierre Ohlmann, and K. S. Thejaswini.  A symmetric attractor-decomposition lifting algorithm for parity games.  arXiv e-prints, page arXiv:2010.08288, October 2020.  arXiv:2010.08288, doi:10.48550/arXiv.2010.08288.
  * [22] Marcin Jurdzinski and Jens Vöge.  A discrete stratety improvement algorithm for solving parity games.  BRICS Report Series, 7(48), Jun. 2000.  URL: https://tidsskrift.dk/brics/article/view/20215, doi:10.7146/brics.v7i48.20215.
  * [23] Marcin Jurdziński.  Deciding the winner in parity games is in up $\cap$ co-up.  Information Processing Letters, 68(3):119–124, 1998.  URL: https://www.sciencedirect.com/science/article/pii/S0020019098001501, doi:10.1016/S0020-0190(98)00150-1.
  * [24] Michael Luttenberger.  Strategy iteration using non-deterministic strategies for solving parity games.  CoRR, abs/0806.2923, 2008.  URL: http://arxiv.org/abs/0806.2923, arXiv:0806.2923.
  * [25] Rolf H. Möhring, Martin Skutella, and Frederik Stork.  Scheduling with AND/OR precedence constraints.  SIAM J. Comput., 33(2):393–415, 2004.  URL: http://dx.doi.org/10.1137/S009753970037727X, doi:10.1137/S009753970037727X.
  * [26] Pierre Ohlmann.  Monotonic Graphs for Parity and Mean-Payoff Games.  PhD thesis, University of Paris, 2021.  URL: https://www.irif.fr/~ohlmann/contents/these.pdf.
  * [27] Pawel Parys.  Parity games: Zielonka’s algorithm in quasi-polynomial time.  In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 10:1–10:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.MFCS.2019.10.
  * [28] Anuj Puri.  Theory of hybrid systems and discrete event systems., 1995.  URL: https://www.elibrary.ru/item.asp?id=5408583.
  * [29] Sven Schewe.  An optimal strategy improvement algorithm for solving parity and payoff games.  In Computer Science Logic, 22nd International Workshop, CSL 2008, 17th Annual Conference of the EACSL, Bertinoro, Italy, September 16-19, 2008\. Proceedings, volume 5213 of Lecture Notes in Computer Science, pages 369–384. Springer, 2008.  doi:10.1007/978-3-540-87531-4\\_27.
  * [30] Sven Schewe, Ashutosh Trivedi, and Thomas Varghese.  Symmetric strategy improvement.  In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 388–400. Springer, 2015.  doi:10.1007/978-3-662-47666-6\\_31.
  * [31] Tom van Dijk.  Attracting tangles to solve parity games.  In Computer Aided Verification - 30th International Conference, CAV 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings, Part II, volume 10982 of Lecture Notes in Computer Science, pages 198–215. Springer, 2018.  doi:10.1007/978-3-319-96142-2\\_14.
  * [32] Tom van Dijk.  Oink: An implementation and evaluation of modern parity game solvers.  In Tools and Algorithms for the Construction and Analysis of Systems - 24th International Conference, TACAS 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14-20, 2018, Proceedings, Part I, volume 10805 of Lecture Notes in Computer Science, pages 291–308. Springer, 2018.  doi:10.1007/978-3-319-89960-2\\_16.
  * [33] Tom van Dijk.  A parity game tale of two counters.  In Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2019, Bordeaux, France, 2-3rd September 2019, volume 305 of EPTCS, pages 107–122, 2019.  doi:10.4204/EPTCS.305.8.
  * [34] Igor Walukiewicz.  Monadic second order logic on tree-like structures.  In STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in Computer Science, pages 401–413. Springer, 1996.  doi:10.1007/3-540-60922-9\\_33.
  * [35] Wieslaw Zielonka.  Infinite games on finitely coloured graphs with applications to automata on infinite trees.  Theor. Comput. Sci., 200(1-2):135–183, 1998.  doi:10.1016/S0304-3975(98)00009-7.
  * [36] Uri Zwick and Mike Paterson.  The complexity of mean payoff games on graphs.  Theor. Comput. Sci., 158(1&2):343–359, 1996.  doi:10.1016/0304-3975(95)00188-3.

##  Appendix A Example

######  Example A.1.

Now we illustrate the reduction to a sink parity game and the symmetric
strategy improvement algorithm with an example. Suppose we have a parity game
as on the left in Figure 6. This can be transformed into a sink parity game as
in Lemma 2.3. Two copies of the resulting sink parity game are shown on the
right in Figure 6. One copy shows a trivial admissible player 0 strategy
$\sigma$, with its optimal response $\bar{\sigma}$. The other one shows an
admissible $\tau$ with its optimal response $\bar{\tau}$.

Figure 6: Left: a parity game. Middle: strategy $\sigma$ (dashed) and
counterstrategy $\bar{\sigma}$ (dotted) in the resulting sink parity game.
Right: Strategy $\tau$ (dashed) and counterstrategy $\bar{\tau}$ (dotted).

Now we look at what symmetric strategy improvement does if we start with the
pair of strategies shown in Figure 6. We denote the valuations $\Xi_{\sigma}$
and $\Xi_{\tau}$ in this game by $(a_{1},a_{2},a_{4},a_{5},a_{6})$, where
$a_{i}$ stands for $\left(\Xi_{\sigma}\right)_{i}$ or
$\left(\Xi_{\tau}\right)_{i}$. Now we find the improving moves. Player 0 has
two improving moves, the first is $(v_{1},v_{2})$, as
$\Xi_{\sigma}(v_{2})=(1,1,0,0,0)\triangleright\Xi_{\sigma}(\sigma(v_{1}))=\Xi_{\sigma}(\top)=(0,0,0,0,0)$,
and the other improving move is $(v_{1},v_{4})$. Since
$\bar{\tau}(v_{1})=v_{2}$, the symmetric strategy improvement algorithm will
switch player 0’s choice in $v_{1}$ to $v_{2}$. Player 1 has one improving
move, namely $(v_{5},v_{4})$, as
$\Xi_{\tau}(v_{4})=(0,0,1,1,1)\triangleleft(0,0,0,0,1)=\Xi_{\tau}(v_{6})$.
However, $\bar{\sigma}(v_{5})=v_{2}$, so
$I_{\tau}\cap\\{(v,\bar{\sigma}(v))|v\in V_{0}\\}$ is empty, and we do not
change $\tau$ in this iteration. So in the first iteration, the only switch
that is made is changing $\sigma(v_{1})$ to $v_{2}$. The reader can verify
that in the second iteration of the symmetric strategy improvement algorithm,
only the switch $(v_{5},v_{4})$ is made for player 1, and that after that, the
algorithm terminates. Then, we have a pair of optimal strategies $\sigma$ and
$\tau$ as shown on the left in Figure 7. We can now infer the winning sets
$W_{0}$ and $W_{1}$ of the original game from the $6$-element of the
valuations of the nodes. Also, the optimal strategies in the sink game form
winning strategies in the original game.

Figure 7: Left: optimal strategies $\sigma$ (dashed) and $\tau$ (dotted),
found after performing symmetric strategy improvement. Right: the resulting
winning sets and winning strategies (dashed) in the original game.

##  Appendix B Note on further increasing the number of switches

On the number of switches, note that with the adapted counterexample,
generalized symmetric strategy improvement still makes ‘too few’ switches,
because it puts off making some good switches. It considers the large
difference in $\Xi_{\tau}$ for player 0 switches and the large difference in
$\Xi_{\sigma}$ for player 1 switches. That opens the question if one could
further increase the number of switches that generalized symmetric strategy
improvement makes. A next logical increase would be to always make an
improving move in a node if one can, and then possibly be guided by the
opponent’s strategy for deciding which improving move to make. However, in a
run of regular strategy improvement on the switch-best counterexample from
[15], there is always exactly one improving move per node, and therefore this
generalization would behave the same on this game for player 0 as strategy
improvement where every possible switch is made. 111There is one exception in
the iteration after their so-called deceleration lane resets, here we can
choose to which node in the deceleration lane we go. However, for this
generalization, it is both from the perspective of $\Xi_{\sigma}$ and
$\Xi_{\tau}$ always better to switch to the highest even node in the lane like
in regular strategy improvement. Hence it would make sense to assume that this
always happens. Hence there is still an exponential-time worst-case example.
This time, one could say that it is because the algorithm is switching too
many edges, as the main idea behind this example is that the parts
representing significant bits are distracted by unnecessary switches so that
the insignificant bits are being switched very often like a binary counter.


# Network Anomaly Detection Using Federated Learning

William Marfo  Department of Computer Science
University of Texas at El Paso
El Paso, USA
<EMAIL_ADDRESS>Deepak K. Tosh  Department of Computer Science
University of Texas at El Paso
El Paso, USA
<EMAIL_ADDRESS>Shirley V. Moore  Department of Computer Science
University of Texas at El Paso
El Paso, USA
<EMAIL_ADDRESS>
###### Abstract

Due to the veracity and heterogeneity in network traffic, detecting anomalous
events is challenging. The computational load on global servers is a
significant challenge in terms of efficiency, accuracy, and scalability. Our
primary motivation is to introduce a robust and scalable framework that
enables efficient network anomaly detection. We address the issue of
scalability and efficiency for network anomaly detection by leveraging
federated learning, in which multiple participants train a global model
jointly. Unlike centralized training architectures, federated learning does
not require participants to upload their training data to the server,
preventing attackers from exploiting the training data. Moreover, most prior
works have focused on traditional centralized machine learning, making
federated machine learning under-explored in network anomaly detection.
Therefore, we propose a deep neural network framework that could work on low
to mid-end devices detecting network anomalies while checking if a request
from a specific IP address is malicious or not. Compared to multiple
traditional centralized machine learning models, the deep neural federated
model reduces training time overhead. The proposed method performs better than
baseline machine learning techniques on the UNSW-NB15 data set as measured by
experiments conducted with an accuracy of 97.21% and a faster computation
time.

###### Index Terms:

Federated Learning, Artificial Intelligence, Machine Learning, Deep Learning,
Networks, Anomaly Detection, Security Attacks

##  I Introduction

The internet is turning out to be an integral part of everyone’s lives as more
and more devices are being connected to serve societal needs. Our work is
motivated by two major observations. Firstly, one drawback of connecting to
the network is the threat of network attacks that can compromise users’
private information, leading to data loss and adversely affecting
productivity. There are several traditional security mechanisms to defend
against these attacks, such as firewalls, virtual private networks (VPNs),
demilitarized zones (DMZs), and vulnerability scanners. One way to prevent
these attacks is early detection and prevention. However, these kinds of
architecture do not scale very well because of their centralized nature.
Secondly, we observe from heuristics and data set distributions that the
majority of the requests made to a server are innocuous. Therefore, almost all
server request data sets are highly imbalanced, weighted highly towards the
harmless requests [1, 2].

To solve these issues, we propose a federated deep learning model that keeps
track of session requests from different devices by using their IP addresses
and port numbers to determine whether the request seems anomalous. Network
anomaly detection using machine learning (ML) helps by analyzing different
features of the request to verify if a request coming from a device is
anomalous or not [3]. Further, as we use a federated approach, we have no
single point of failure, making our approach scalable and more robust.

With its scalability, federated learning (FL) helps tackle this problem. Since
FL is not centralized, it removes dependence on a central server that plagues
the scalability of large networks’ cores. The workload is distributed by
delegating the learning to edge servers from the singleton global server.
Besides having the benefit of higher efficiency in the system, the ensemble of
the independent edge servers also contributes to higher accuracy. We
demonstrate both benefits in our results in Sec. IV.

Our FL architecture uses a hierarchical approach in which edge servers are
added between clients and global servers to reduce the workload on the global
server and the failure rates. In FL, only models with trainable weights
parameters can be aggregated without a drop in their performance. For our
network anomaly detection experiments, we propose using artificial neural
networks (ANN) as it not only performs well in comparison to other models but
is also an excellent candidate to be used in the federated learning
environment due to their flexible nature [4].

The contributions of this paper can be summarized as follows.

  * •

We present a hierarchical federated learning architecture (HFL) to increase
the scalability of FL for network anomaly detection.

  * •

We propose an HFL framework for network anomaly detection on the UNSW-NB15
dataset, which is the first on this dataset in literature to the best of our
knowledge.[1].

  * •

We conduct and report comprehensive experiments to show the performance
improvements of our federated learning model over the traditional centralized
models that were trained individually on local data of clients.

The rest of this paper is organized as follows: Section 2 introduces
background knowledge about federated learning and network anomaly detection.
Section 3 details our proposed architecture for network anomaly detection
using HFL. Experimental data and results are given in Section 4. In Section 5,
we provide a summary and discuss future works.

##  II Background

Network anomaly detection using FL is an application of ML in cybersecurity.
This section discusses the concepts of federated learning, network anomaly
detection, and some current work in these domains.

###  II-A Federated Learning

Presently, the trend of using applications based on client-server
architecture, such as cloud computing and web or mobile applications, is
increasing [4]. Also, with technological advancement, the use and trust of
artificial intelligence (AI)-based applications are increasing. FL is a
valuable technique for performing AI-based tasks using ML or deep learning
(DL) applications based on client-server architecture [5]. In FL, ML/DL models
are trained in a distributed and collaborative environment by ensuring the
privacy of sensitive data of clients and the performance of the ML/DL models.
In order to preserve the privacy of sensitive data and the model’s
performance, two types of models are used in federated learning, including
local and global models. The client’s data is not moved directly from one
client’s device to the server in federated learning. Instead, local models are
trained on each client’s local devices, and only the parameters of models
trained on the client’s devices are sent to a server, where the parameters of
global models are updated using these parameters from the local models. In
this way, not only is the user’s privacy preserved, but it also causes less
overhead on a server, reducing the computational resources and cost. Due to
additional computational overhead on the global server, we can only add new
devices to a limited scale. Also, vertical scaling is an expensive thing to
do. Most of these issues are resolved using a hierarchical architecture in a
federated learning environment.

In [6], the researchers used the same data set as ours and used ANN-based
learning in a centralized fashion. The primary novelty of that work was
feature selection. They achieved accuracy between 88.13 and 90.85%. We show
that our FL model outperforms this accuracy more efficiently and quickly.

Moreover, FL methods have been proposed for intrusion detection in various
applications, including large-scale cyber-physical systems, Wi-Fi networks,
and others. Researchers in [11] adopted a deep neural network to learn the
hierarchical representations of private network data and achieved an accuracy
of 99.27% for intrusion detection with a focus on edge nodes and a cloud
server. With a suitable dataset, one can get the best precision for the ML
techniques used in FL learning. The authors in [12] introduced a study on
several past methods applied for intrusion detection using FL learning. The
datasets used had 5,874,010 trainable parameters where they utilized the
framework to achieve better communication-computation trade-offs in a client-
edge-cloud HFL system.

Authors in [13, 14] used an FL framework to train a deep learning model in IoT
heterogeneous systems and reduced communication overhead by 75-85%. In [15],
researchers proposed an FL framework to optimize user assignment and allocate
resources to provide a scalable production system based on Tensorflow.

In our HFL, edge servers are added as intermediate servers between clients and
global servers. Edge servers are parameter servers that add more distribution
to the FL architecture. Multiple clients are connected to a single-edge server
based on availability. The edge server receives the parameters of local models
from clients, performs aggregations, and passes these parameters to global
servers. Due to this computational distribution, overhead on the global server
is reduced. As edge servers are connected to a relatively smaller number of
clients, edge servers are also more efficient. In case of failure of an edge
server, a client can connect to other edge servers, which also increases the
reliability of our FL architecture.

As discussed in the introduction, this problem is biased in one class.
Therefore, studies have been done in this context to tackle the class
imbalance problem. In [7], the authors used the same data set as ours and
applied oversampling method (SMOTE) to handle the class imbalance problem, and
used Random Forest (RF) classifier for the classification task and achieved
95.1% accuracy. Our method not only aims to outperform this in accuracy but
also makes a more robust model as FL is distributed while addressing the issue
of class imbalance.

###  II-B Network Anomaly Detection

Devices connected to networks are vulnerable to attacks from other malicious
devices. Network anomaly detection is used to identify requests from such
malicious devices as anomalies considering that the requests from normal
devices will have different characteristics than those from malicious devices.
The idea is to have an early detection and prevention system that can identify
if a request from a device deviates from the usual trend and deny the request
if the algorithm identifies it as such. In ML, many techniques exist for
anomaly detection based on available data, and classification algorithms can
be used if data is labeled [8, 9, 10]; however, unsupervised algorithms such
as clustering or autoencoders are used in the case of unlabeled data [10]. In
our experiments, we use the labeled UNSW-NB15 dataset [1] to verify if a
request is anomalous or not, and we tackle the problem as a classification
task in an HFL environment.

##  III Proposed Approach

Our DL-based ANN model is trained in an HFL environment to detect anomalous
requests from different devices on the connected network. In this section, we
discuss our approach in two parts. In the first part, we discuss the structure
of our HFL environment as well as the architecture of the ANN model we used
for anomaly detection in the second part.

Figure 1: Hierarchical Federated Learning Architecture (in the flow, the ”raw
data” is network traffic, whereas the ”weights” are learned parameters).

###  III-A Hierarchical Federated Learning Architecture

Our HFL environment has three main components: clients, edge servers, and a
global server. In the following, we discuss each component briefly. Fig.1
shows the overall architecture of HFL architecture.

1\. Client: The client is a device/machine that owns the data. Each client’s
data does not move directly from one client to another or even to the edge or
global server to preserve privacy. Each client also has local models
(independent copies of the same DL models at the client level). Every client
can connect to one or multiple edge servers based on availability. The local
model on each client gets trained for one or a few epochs, and all clients’
updated parameters (trainable weights) of local models are passed to the
connected edge servers. The edge servers aggregate the parameters received
from the clients and pass them to the global server, where it aggregates all
the parameters from edge servers and updates the global model. We then
evaluate the global model, which is passed back to the client, where the
parameters of the local model are updated. We can have any number of clients
in our architecture. Let us assume we have $i$ number of clients symbolized as
$c_{i}$ and each client has its data $X_{c_{i}}$ and a local model
$f_{c_{i}}$, where $X_{c_{i}}\in\mathbf{R}^{n\times d}$, where $n$ is the
number of samples, and $d$ shows the number of features in each sample. After
training $f_{c_{i}}$ on $m_{e}$ epochs on $X_{c_{i}}$ data we pass updated
parameters $w_{f_{c_{i}}}$ of local $f_{c_{i}}$ model to the connected edge
server $e_{i}$.

2\. Edge server: The edge server is an intermediate between the client and the
global server. The edge server is used to add another level of distribution in
FL to reduce the load of the global server. The updated weights are passed to
the edge server after a few training epochs on local models on client devices.
On edge servers, those parameters are aggregated using the selected
aggregation function. The aggregation helps reduce the global server load as
it has to aggregate thousands or millions of clients, but now the load is
distributed among edge servers. We can have any number of edge servers in our
architecture. Assume an edge server $e_{i}$ receives parameters from $m_{i}$
connected clients; it will aggregate all those parameters by taking the
average as given in equation (1) and pass those aggregated parameters $w_{ei}$
to global server $g$.

$w_{ei}=\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}w_{cj}$ (1)

3\. Global server: The global server resides where the global model resides,
and all edge servers are connected to the global server. The parameters of the
global model are relayed to all clients after the performance evaluation of
the global model. Aggregated parameters on each edge server are passed to the
global server, where they are again aggregated based on the same aggregation
function. Let us assume global server $g$ is connected to $k$ edge servers;
the global server will aggregate all aggregated parameters that it received
from edge servers as $w_{g}$ as shown in equation (2) and will update the
parameters of its global model $h$.

$w_{g}=\frac{1}{K}\sum_{i=1}^{k}w_{mi}$ (2)

Algorithm 1 HFL Training

0: training data $X_{c}$ on each client Procedure:

1: Initiate local and global models

2: Load and preprocess data on local devices

3: for $i=0$ to $itrs$ do

4: get parameters of global models and update local models on clients

5: Train local models on clients for $e$ epochs

6: Find and connect available edge server and pass parameters to edge server

7: Aggregate parameters from all clients on edge server

8: Pass aggregated parameters to global server

9: Aggregate parameters from all edge servers and update parameters of global
model

10: Evaluate performance of global model

11: end for

12: return parameters

Termination condition/epochs in Alg. 1: The number of epochs will determine
how frequently the weights in the neural network will be updated. In order to
increase the generalization capabilities of the neural network, the training
should occur on an optimal number of epochs.

In general, there is no fixed number of epochs for improving a model’s
performance. The number of epochs is not specifically relevant as long as a
desired accuracy or performance can be achieved. Moreover, the training and
validation loss (i.e., errors) better determine the termination and progress
of training. As long as these losses decrease, learning happens successfully.

We use ‘early stopping’ to determine when to stop the training. The early
stopping method is used to overcome overfitting, where the model performs well
on the training data but not on test data. We pass the validation data into
the fit() method while fitting our model to the training data. The early
stopping technique helps by defining a large number of epochs to train the
model and halts the training once the performance stops improving on the
validation data.

###  III-B Model Architecture

Figure 2: Artificial Neural Networks

Our system uses fully-connected ANN as local and global models. ANN is a
powerful model inspired by the human brain’s architecture. ANNs are widely
used for supervised learning tasks involving network anomaly detection. We
train an ANN on our tabular data. A perceptron is a basic unit in an ANN that
takes the dot product of data/input with a weight matrix. The weight matrix
contains trainable parameters of the perceptron that learns the basic patterns
in data. There can be multiple hidden layers in an ANN, and each layer may
have multiple perceptrons. After each layer, a non-linear activation function
is used for different non-linearly separable classes. In our model, we use two
hidden layers; in each hidden layer, we use 256 hidden units (perceptrons).
After each hidden layer, we use ReLU as an activation function ($\sigma$). In
contrast, at the output layer of an ANN, we use a sigmoid activation function
that predicts the probabilities of different classes for the given sample.
Fig.2 shows the architecture of the ANN model used in our experiments. Let us
assume a data sample $X_{i}$ is passed to the $l^{th}$ layer of the model here
$X_{i}\in\mathbf{R}^{1\times d}$, where $d$ shows the number of features in
the given sample the model will work as follows:

$o_{l}=\sigma(w_{l}^{T}.X_{i}+b_{l}).$ (3)

##  IV Experimentation and evaluation

###  IV-A Data background

In this research, we used the UNSW-NB15 dataset [1], and all experiments were
conducted with TensorFlow Federated (TFF) in Google Colab with NVIDIA Tesla
P100 and 16 GB RAM. UNSW-NB15 is a network intrusion dataset containing
records from raw network packets. The raw network packets of the UNSW-NB 15
dataset were created by the IXIA PerfectStorm tool in the Cyber Range Lab of
UNSW Canberra, Australia, for generating a hybrid of real modern normal
activities and synthetic recent attack behaviors. The tcpdump tool captured
100 GB of the raw traffic (e.g., Pcap files). This dataset has nine types of
attacks: Fuzzers, Analysis, Backdoors, DoS, Exploits, Generic, Reconnaissance,
Shellcode, and Worms. The Argus and Bro-IDS tools are used, and twelve
algorithms are developed to generate 49 features [1] with the class label. We
used this tabular dataset to detect anomalous network traffic. The dataset
contains 2,540,043 samples, and the label column is binary, showing an
attack/anomaly if a label is one; otherwise, 0.

####  IV-A1 Preprocessing of our data set

In our experiments, we dropped the null value columns during the preprocessing
stage for columns containing null values in more than 50% samples. After that,
we ended up with 45 features, excluding the last four features in [1]. Then we
converted the categorical data into numerical data. We split our data into
training and testing data based on a 90-10 ratio and ended with 2,286,038
training and 254,005 testing samples. We used all testing data for the global
model evaluation, but we split training data into 4 splits (as we had four
clients, so one split for each client), resulting in an equal number of
samples. In each training split for each client, we had 571,509 samples, with
an 87.5: 12.5 ratio of positive and negative samples in each split.

###  IV-B Performance and evaluation metrics

Performance and evaluation metrics are used to evaluate the performance of ML
models. Mostly in supervised learning techniques involving network anomaly
detection, the model’s performance is evaluated by comparing the model’s
prediction with the actual ground truth. The evaluation metrics for our
experiments include accuracy, precision, recall, and F1-Score.

Precision represents how precise/accurate each model is out of those data
points that are predicted as anomalous and how many of them are actually
anomalous. A high precision (seen in our deep neural network model) is a good
measure considering an unbalanced data set and is robust against false
positives. (False positives occur when a model mispredicts the positive
outcome. An incorrectly predicted negative class is referred to as a false
negative). The recall represents how many of the actual network anomalies the
models captured through predicting it as anomalous. F1-score is a balance of
both precision and recall, given as $F1\>score=2\times\frac{precision\times
recall}{precision+recall}$. Thus, it ensures that high precision or recall
alone cannot bias the metric. Finally, accuracy is the simple mean of
correctness derived from the difference in predictions from the labeled ground
truth data.

Figure 3: Accuracy of ML techniques (network anomaly detection)

###  IV-C Performance evaluation

This sub-section discusses the performance evaluation results on different
models and experimental settings. Here we can see that the performance of
local models improves when they are trained in an HFL environment. In Fig.3,
we have shown that the ANN model trained in HFL has the best performance with
an accuracy of 97.21% and a training time of 1,500 seconds (please see Fig.5).
Even though the performance of ANN trained in a traditional centralized ML
environment came close, it took longer to train under the same conditions.
Support vector machine (SVM) and random forests models had accuracies of
90.01% and 89.01%, respectively, in the centralized ML approaches.
Furthermore, Table I shows different experiments’ evaluation scores for
accuracy, precision, recall, and F1-scores. An illustrative comparison is
shown in Fig. 4.

Figure 4: ML algorithms performance measures for UNSW-NB15 dataset.

Figure 5: Training time cost of ML algorithms

###  IV-D Experimental results

This section discusses other experiments we performed to develop an efficient
and accurate network anomaly detection algorithm. In this work, we performed
the following types of experiments:

1\. Experiments of model selection:

We used all the data, including training and testing splits of the data set,
to select the suitable ML model. For this purpose, we compared the performance
of SVM, Random Forest, and ANN on the test data. Table I shows that the ANNs
performed well compared to SVM and Random Forest in these experiments; that is
why we used ANNs in further experiments. It further reinforces the higher
accuracy gains in HFL over individual clients.

2\. Network anomaly detection on individual clients:

In these experiments, we divided our data set into 4 parts with the same
positive and negative sample ratio. These splits of the data set have
different distributions of different types of attacks. We then trained ANN
models for each data split separately and evaluated the performance using
selected evaluation metrics. In Table I, we can see that the performance of
different individual models trained with different splits of data varies (for
example, on client/split 1, accuracy is about 90% whereas, on client 3, it is
about 91%). We can also see that the overall performance of individually
trained models is inferior to those of the same data splits when models were
trained in the FL environment. From the learning curves in Fig.6, we can see
that initially, the learning of all models was slow (e.g., iterations 1
through 5), but after several iterations (please see Fig.6), it speeds up as
global models start to learn patterns learned by the local models from local
data.

TABLE I: Performance evaluation Experiment | Accuracy | Precision | Recall | F1 Score
---|---|---|---|---
Client 1 (Individual) | 90.12 | 91.89 | 91.42 | 91.65
Client 1 (HFL) | 96.41 | 98.46 | 97.65 | 98.05
Client 2 (Individual) | 90.98 | 91.63 | 92.03 | 91.82
Client 2 (HFL) | 96.39 | 98.5 | 97.82 | 98.15
Client 3 (Individual) | 91.01 | 91.58 | 92.07 | 91.82
Client 3 (HFL) | 96.58 | 98.58 | 97.79 | 98.18
Client 4 (Individual) | 90.92 | 92.03 | 91.51 | 91.76
Client 4 (HFL) | 96.42 | 98.57 | 97.8 | 98.18
Centralized SVM | 90.01 | 89.10 | 88.19 | 90.28
Centralized RF | 89.01 | 87.21 | 88.32 | 89.11
Centralized ANN | 92.01 | 90.10 | 90.40 | 92.15
Global HFL (ANN) (ours) | 97.21 | 98.09 | 97.18 | 97.63
TABLE II: Performance evaluation Experiment | Accuracy | Precision | Recall | F1 Score
---|---|---|---|---
4 Clients / 4 Edge Servers | 96.02 | 98.12 | 97.32 | 97.71
6 Clients / 3 Edge Servers | 96.19 | 98.25 | 97.52 | 97.88
10 Clients / 3 Edge Servers | 96.39 | 98.53 | 97.81 | 98.15
10 Clients / 4 Edge Servers | 96.37 | 98.49 | 97.82 | 98.14
10 Clients / 5 Edge Servers | 97.38 | 98.51 | 97.81 | 98.15

Figure 6: Learning curve of the local and global models in 50 iterations.

3\. Network anomaly detection in FL environment:

In these experiments, we explored the effect on the performance of the network
anomaly detection models if we increase or decrease the number of clients. We
experimented using 4, 6, and 10 clients, keeping the count of edge servers
constant (3), and then we changed the number of edge servers to 4 and 5,
keeping the number of clients constant (10). In these experiments, we first
created 10 splits of the dataset, and when we used only $s$ number of splits
for experiments having the same number of clients. The results show that the
edge servers increase the federated learning architectures’ scalability while
retaining the model’s performance in the system.

Notably, aggregations are done first on edge servers before passing them to
the global server; this reduces the load on the global server and makes
communication faster. In literature, trade-offs have been reported between the
communication cost and training time depending on the communication frequency
with the servers, e.g., in the investigation presented in [12]. We delegate a
further investigation on bandwidth vs. accuracy/efficiency as future work.

In our experiments, the highest accuracy we achieved with 10 clients was
97.38%; meanwhile, the training time more than doubled from that of 4 clients.
Table II shows the performance of global models trained on a different number
of clients and edge servers. We can see that increasing the number of clients
enhances the performance of the models; however, there is no significant
impact on performance if we change the number of edge servers, but the
training time increases, on the other hand.

Another salient point is that centralized ANN and HFL had similar performances
in terms of accuracy. However, the only difference was the training time, as
the HFL trained much faster due to the inclusion of the edge servers that
reduced the load on the global model. Therefore, with time kept constant, the
HFL method could train itself much more than centralized ANN. This explains
the accuracy gains of the HFL method besides only efficiency.

##  V Conclusion

In contemporary times, not only computers or mobile devices but also many IoT-
based home appliances are connected to private or public networks. Besides
many advantages, there is always a threat of network attacks on the devices
connected to networks, especially the internet. In this work, we proposed to
use ANN in an HFL environment to detect if the requests from a device are
anomalous or not.

HFL helps with scalability issues, makes global models more efficient, and
reduces the training load on global servers. Results of our experiments on the
UNSW-NB15 dataset have shown the improvement in the performance of ANNs on
client devices to detect anomalous requests when trained in the federated
learning environment in comparison to when they were trained on the data of
individual devices as it only contains the information about attacks they were
being targeted. In future work, we will hone in on optimizing the data
imbalance problem inherent to biased datasets to further improve the accuracy,
and propose to use pre-selection for faster training.

## References

  * [1] N. Moustafa and J. Slay, ”UNSW-NB15: a comprehensive data set for network intrusion detection systems (UNSW-NB15 network data set),” 2015 Military Communications and Information Systems Conference (MilCIS), 2015, pp. 1-6, doi: 10.1109/MilCIS.2015.7348942.
  * [2] W. Marfo, D. K. Tosh and S. V. Moore, ”Condition monitoring and anomaly detection in cyber-physical systems,” 2022 17th Annual System of Systems Engineering Conference (SOSE), 2022, pp. 106-111, doi: 10.1109/SOSE55472.2022.9812638.
  * [3] Hastie T., Tibshirani R., Friedman, J.(2009), The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edition, Springer,2008.
  * [4] Q. Li et al., ”A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection,” in IEEE Transactions on Knowledge and Data Engineering, doi: 10.1109/TKDE.2021.3124599.
  * [5] Y. Jee Cho, S. Gupta, G. Joshi and O. Yağan, ”Bandit-based Communication-Efficient Client Selection Strategies for Federated Learning,” 2020 54th Asilomar Conference on Signals, Systems, and Computers, 2020, pp. 1066-1069, doi: 10.1109/IEEECONF51394.2020.9443523.
  * [6] Kasongo, S.M., Sun, Y. Performance Analysis of Intrusion Detection Systems Using a Feature Selection Method on the UNSW-NB15 Dataset. J Big Data 7, 105 (2020). https://doi.org/10.1186/s40537-020-00379-6
  * [7] Jindaluang, Wattana. ”Oversampling by genetic algorithm and k-nearest neighbors for network intrusion problem.” Journal of Intelligent Fuzzy Systems (2022)
  * [8] S. Wang, J. F. Balarezo, S. Kandeepan, A. Al-Hourani, K. G. Chavez and B. Rubinstein, ”Machine Learning in Network Anomaly Detection - A Survey,” in IEEE Access, vol. 9, pp. 152379-152396, 2021, doi: 10.1109/ACCESS.2021.3126834.
  * [9] Kurniabudi, Kurniabudi & Purnama, Benni & Sharipuddin, & Dr, Darmawijoyo & Stiawan, Deris & Samsuryadi, Samsuryadi & Heryanto, Ahmad & Budiarto, Rahmat. (2019). Network anomaly detection research: A survey. Indonesian Journal of Electrical Engineering and Informatics. 7. 36-49. 10.11591/ijeei.v7i1.773.
  * [10] Casas, P., Mazel, J., Owezarski, P. (2011). UNADA: Unsupervised Network Anomaly Detection Using Sub-space Outliers Ranking. In: Domingo-Pascual, J., Manzoni, P., Palazzo, S., Pont, A., Scoglio, C. (eds) NETWORKING 2011. NETWORKING 2011. Lecture Notes in Computer Science, vol 6640. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20757-0_4
  * [11] S. I. Popoola, G. Gui, B. Adebisi, M. Hammoudeh and H. Gacanin, ”Federated Deep Learning for Collaborative Intrusion Detection in Heterogeneous Networks,” 2021 IEEE 94th Vehicular Technology Conference (VTC2021-Fall), 2021, pp. 1-6, doi: 10.1109/VTC2021-Fall52928.2021.9625505.
  * [12] L. Liu, J. Zhang, S. H. Song and K. B. Letaief, ”Client-Edge-Cloud Hierarchical Federated Learning,” ICC 2020 - 2020 IEEE International Conference on Communications (ICC), 2020, pp. 1-6, doi: 10.1109/ICC40277.2020.9148862.
  * [13] Alaa Awad Abdellatif, Naram Mhaisen, Amr Mohamed, Aiman Erbad, Mohsen Guizani, Zaher Dawy, and Wassim Nasreddine. 2022. Communication-efficient hierarchical federated learning for IoT heterogeneous systems with imbalanced data. Future Gener. Comput. Syst. 128, C (Mar 2022), 406–419. https://doi.org/10.1016/j.future.2021.10.016
  * [14] H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-efficient learning of deep networks from decentralized data. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1273-1282. http://proceedings.mlr.press/v54/ Also arXiv preprint arXiv:1602.05629, 2016.
  * [15] Keith Bonawitz et. al. Towards federated learning at scale: system design. Proc. Machine Learning and Systems (MLSys 2019), 2019.