Safe Multi-agent Learning via Trapping Regions

1 Introduction

In the recent years, enormous progress has been made for single agent planning and learning algorithms, with agents matching or exceeding human performance in various tasks and games [Mnih et al., 2013; Silver et al., 2016]. The vast success of single agent learning can be partially explained by robustness and strong convergence properties of the underlying algorithms in their basic form, such as Qlearning [Watkins and Dayan, 1992] or policy gradients [Sutton et al., 1999]. Despite wide interest, the same cannot be however said for multi-agent learning. Even most basic models, e.g. replicator learning for normal form games, exhibit nonconvergence, cyclic or even chaotic behavior [Sato et al., 2002]. Even worse, it has been shown that in decoupled learning systems, there can be no learning rule that guarantees convergence to a Nash equilibrium [Hart and Mas-Colell, 2003]. These nonconvergent examples have also been found in more practical learning problems, such as Generative Adversarial Networks [Mescheder et al., 2018]. Due to the above limitations, many successful multi-agent learning methods resorted to using a centralized component, such as centralized critic in actor-critic learning [Lowe et al., 2017] or meta-solvers in double-oracle type algorithms like Parallel Nash Memory [Oliehoek et al., 2006] and Policy Space Response Oracles [Lanctot et al., 2017]. Alternatives in form of decentralized algorithms usually rely on specific assumptions on the reward structure for convergence, for instance fictitious play or exploitability descent in zero-sum games [Brown, 1951; Lockhart et al., 2019].

Due to space restrictions, the proofs of our theorems and lemmas have been postponed to the Supplementary Material, and can be accessed in the extended version of the paper [Czechowski and Oliehoek, 2023]. There, we also provide an additional example, where we find trapping regions in a model of economic competition, which ensures that none of the competing companies will reduce their production to zero.

Despite this undisputed progress in designing convergent multi-agent algorithms, it can be argued that in practical, realworld multi-agent scenarios there will be plenty of situations, where convergence cannot be enforced. One can easily envisage a situation, e.g. in automated traffic control and driving scenarios, or in automated trading, where multiple entities (be it traffic lights, vehicles, or brokers) follow own learning protocols for individual reward maximization. Such learning rules, even though designed to be convergent in static, singleagent environments, would invariably interfere with one another in a multi-agent setting, sometimes resulting in cyclic, or divergent outcomes. The lack of convergence guarantees in such general settings forms a major obstacle for introduction of online learning systems in practical applications, as it introduces a lot of uncertainty over what will be the state of the system, if learning is left unsupervised. Can we nevertheless still establish a type of safety certificates, that would allow us to conclude that simultaneous learning will not spin out of control?

In this paper, we suggest a novel approach to address issue. We start from the realization, that convergence is often not absolutely necessary for reliability. From systems designers perspective, it is often enough to know that learning has rough stability guarantees - that is, that agents will not leave a predetermined region of the strategy space during learning.

For a conceptual application, let us consider a traffic light control network as in Figure 3, where individual traffic light controllers learn the best balance of green time between the phases to minimize the waiting time for approaching vehicles. It is not absolutely necessary that by learning each intersection reaches a final, static setting, but would be essential that at all times it gives minimal green time of at least few seconds to each phase, to make sure that no vehicle gets stuck indefinitely on a red traffic light, and also serve the lingering pedestrian flows.

We propose a method of a priori verifying these constraints, by establishing trapping regions; regions of strategy space, which learning trajectories will never escape. The idea behind this concept is simple: a candidate set for a trapping region is formed by the constraints imposed by practical, problem-dependent safety considerations. By verifying whether such set is forward-invariant for the joint learning operator, we obtain a yes-or-no answer on whether it is safe to allow multi-agent learning (possibly in a decentralized manner), without breaking these constraints. This method can be seen an alternative solution concept in systems, where Nash equilibria are difficult or impossible to reach by learning dynamics. Trapping regions are intended to be used as a safety prerequisite. For instance a road authority could pre-approve the algorithms of automated road users, by checking whether their joint policy forms suitable trapping regions - before they are deployed in real life.

This paper is organized as follows. Section 2 introduces the setting and necessary preliminaries. In Section 3 we present the definition of a trapping region, prove several useful theorems and lemmas that are useful for their verification for Lipschitz-continuous learning, and present two algorithms, for verifying whether given hyperrectangular sets forms a trapping region, only from the knowledge of learning operator on the set boundary. The first algorithm, is based on binary partitioning, and is applicable when learning dynamics are known analytically and Lipschitz, and we would like to have a mathematically rigorous guarantee. The second one is a heuristic algorithm, applicable in scenarios where learning dynamics can only be sampled, its dependability is directly correlated to the number of boundary samples taken.

Finally, in Section 4 we introduce two examples, that illustrate the applications of trapping regions. The first of our first of our examples is a toy problem, a simple GAN-like learning scenario, where gradient learning starting from almost all points never converges, whereas trapping regions are abundant and easy to find. In our second example we deal with a practical traffic control problem, where four intersection in a traffic network adjust their strategies to dispatch traffic in an optimal manner. For this problem, we construct and verify a trapping region, which ensures all traffic directions will be given enough time, when traffic controllers are left to learn unsupervised.

1.1 RelatedWork

Trapping regions are well known and standard tool in qualitative theory of dynamical systems, e.g. [Meiss, 2007; Bonatti, 2006], but to the best of our knowledge have not been directly applied in learning and control scenarios. The majority of work on safety guarantees in control theory focuses on so-called constrained optimization [Altman, 1999]. In the context of safe reinforcement learning, the focus has been on designing algorithms that satisfy particular safety constraints, c.f. [Garcıa and Fern´andez, 2015] and references therein. In the multi-agent case, research has been directed towards methods where an orchestrator [ElSayed-Aly et al., 2021] or agents individually [Lu et al., 2021] are adapting their behavior to respect the constraints; this has also been the underlying philosophy in the method of barrier functions [Wills and Heath, 2004; Yang et al., 2020]. There are also strong connections to methods of formal verification methods, in particular ones based on reachability analysis [Ruan et al., 2018; Wang et al., 2021].

Relation to Lyapunov Control. Our method shares most similarities with the ones based on Lyapunov functions, such as Neural Lyapunov Control [Chang et al., 2019], see also [Berkenkamp et al., 2017]. There are however several key differences that we would like to highlight here. Most importantly, Lyapunov-based methods are only applicable to (locally) convergent scenarios, as the existence of a Lyapunov function implies the existence of a locally attracting equilibrium of the system. On the other hand, trapping regions are very well suited to deal with problems, where learning never converges to a stationary solution. Even if the learning trajectory does not converge, the bounds provided by the trapping region will ensure that they never diverge into unsafe regions of the joint strategy space. This has strong practical consequences: a non-convergent learning process without safety guarantees would have to be indefinitely supervised, whereas trapping regions ensure that it only explores safe parts of the strategy space, and does not require supervision. Dealing with non-stationarity is particularly important for multi-agent systems, as it was shown e.g. in [Kleinberg et al., 2011] outcomes of a non-convergent cyclic learning process can lead to higher social welfare than these of a stationary Nash; and even worse, often stationarity cannot be ensured, as some learners can be outside of our control (e.g. in adversarial scenarios). In Section 4.1, we provide a lowdimensional example where none of the learning trajectories converge to the equilibrium point, but trapping regions are easy to find, c.f. Figure 2.

The second difference comes in computational complexity. Neural Lyapunov Control requires evaluation of learning directions over a whole domain, while we only require it on a boundary of a domain, effectively reducing the dimension of the verification problem by one (c.f. Lemma 1).

2 Preliminaries

We consider decentralized learning schemes for groups of n agents that can be represented compactly by discrete adaptive dynamics of the form:

where xi ∈ Xi ⊂ Rki represents a point in the strategy space of a given agent i (e.g. weights in a neural network or ratios of playing a mixed strategy), and the parameter γ ∈ R+ denotes the adaptation rate. Throughout this paper, we assume that the learning operators are continuous, and we denote by N = ∑i ki the dimensionality of the joint learning space. The maps Fi : Xi → Rki represent the learning operators, i.e. the outputs of the algorithms of each agent based on the inputs. For instance, for individual gradient-ascent type of algorithms we have

with Ri : RN → R being the individual reward/payoff for agent i. To simplify the exposition, we will sometimes represent the learning system (1) in a vectorized notation

with F = [F1, . . . , Fn]T and x = [x1 , . . . , xn ]T . Joint strategy sequences {xt}t which satisfy (3) will be referred to as the learning trajectories.

An equilibrium for the system (3) is a point in the joint strategy space x∗ ∈ RN such that F(x∗) = 0. In gradient learning, it is also a necessary condition for a strategy profile to be a local optimum, with the sufficient condition being that the Hessian of the learning operator F is negative definite. We remark that an equilibrium for the learning system (3) does not necessarily need to be a Nash equilibrium; however, a local optimum is a local Nash point, i.e. no agent is able to increase their reward unilaterally from a such point by performing a small deviation in its strategy.

For single agent learning, gradient descent in (2) does converge to a local optimum under mild assumptions of regularity of Ri, and suitable choices of γ (i.e. γ can be constant, but needs to be suitably small). In general multi-agent setting, learning schemes given by systems of form (1) can have complicated, even chaotic dynamics, and might not converge to equilibria at all, as for instance in relatively simple twoplayer games [Sato et al., 2002].

3 Trapping Regions

Convergence in multi-agent learning cannot be always guaranteed; however the key aspect for security / reliability is often enough to ensure, that learning agents do not diverge into regions of policy space, which can yield dangerous combinations of strategies. To this end, one needs to contain the learning trajectories within a prescribed safety region. Motivated by this rationale, in this section we formally define the trapping region - a subset of the joint strategy space, characterized by the property that learning trajectories that begin within such region can never leave it.

We remark that the definitions and theorems below could have been framed in a continuous learning setting by working with the ordinary differential equation ˙x = F(x). but we opted for a discrete point of view, as more commonly encountered in literature on learning systems. The discrete system (3) does in fact emerge as the Euler numerical solution of the ODE, with step size γ.

3.1 Formal Definition and Forward Invariance

In what follows, we will denote by intX and ∂X respectively the topological interior and boundary of a set X, by dist(x,X) the Euclidean distance between a point x and a set X, and by diam(X) the diameter (in Euclidean distance) of a set X. By Xl we will denote the Cartesian product of l copies of X. We also recall that a compact set is a set which is bounded, and which contains limit points for all convergent sequences of its elements. We first recall the classical definition of a trapping region in context of learning dynamics (1).

Definition 1. c.f. [Bonatti, 2006]. Let T ⊂ RN be a compact subset of the joint strategy space, and let γ > 0. If

then we call T a trapping region (for the system (3), with learning rate γ).

The following theorem, a folklore in dynamical systems community, highlights the advantage of establishing trapping regions; a trapping region not only guarantees that the learning curves starting inside can never escape it, but also that there is a learning equilibrium (possibly a Nash equilibrium) inside of it.

Theorem 1. Let T be a trapping region. Then

1. Any learning trajectory (3) that starts in T never leaves T,
2. If T is convex, then there exists a learning equilibrium x∗ ∈ intT.

3.2 Algorithmic Verification: Explicit Learning Dynamics

In practice, verification of condition (4) can be troublesome, as the volume of the trapping region usually requires a prohibitively high amount of samples. For small learning rates and continuous learning dynamics, it is however enough to verify this assumption on the boundary, as any trajectory that could leave the region would have to pass through the boundary area. This is a standard argument, more commonly known in the continous case (e.g. [Meiss, 2007]), and is formalized for our discrete setting in Lemma 1.

Lemma 1. Given a compact set T, if γ > 0 is sufficiently small, and for all x ∈ ∂T we have

then T is a trapping region.

Lemma 1 can be used to derive exact inequalities needed to be satisfied by the learning operators, which are sufficient to establish a trapping region. In what follows, we denote by xi = [xi1 , . . . , xiki ]T and Fi = [Fi1, . . . , Fiki ]T the components of strategies and learning operators for each agent i ∈ 1, . . . , n. In the examples we will sometimes omit the second subscript, when the strategy space of each agent is one-dimensional.

Definition 2. Let T be a set of the form of a product of intervals

For i ∈ 1, . . . , n, j ∈ 1, . . . ki, we denote by Tij l the set of all points x ∈ T, such that πij - the projection onto i-th agents j-th component satisfies πijx = xij- . We call this set the (ijth) left face of T. Similarly, we denote by Tij r the set of all points x ∈ T, such that πijx = xij+ , and call it the (ijth) right face of T.

Our next Lemma follows follows directly from Lemma 1 applied to a trapping region of form of a product of intervals.

Lemma 2. Given a set T ∈ RN which is a product of intervals, assume that the following isolation inequalities are satisfied:

Then, the set T is a trapping region for γ > 0 sufficiently small.

For Lipschitz-continuous learning dynamics, and trapping regions of form of a product of intervals, explicit bound on the range of γ can be given.

Theorem 2. Let T be as in Lemma 2 and F be Lipschitzcontinuous with Lipschitz constant over T bounded from above by L. The upper bound on step size γ for which T forms a trapping region in the learning system (1) can be given explicitly by

Remark 1. For sufficiently regular boundaries ∂T, conditions (7) can be generalized to situations, where T is not a product of intervals. Namely, for T to be a trapping region it is enough that

where n∂T(x) is the normal vector to ∂T, pointing in direction outwards of T, c.f. [Meiss, 2007].

The visualization of assumption (7) from Lemma 2 is presented in Figure 1; the intuition behind it is that the learning operators Fij have to point inwards, into the trapping region, so their values have to be positive on left faces and negative on right faces. When the adaptive dynamics are not given explicitly (e.g. they depend on a reward from environment simulator), one may need to resort to verifying condition (7) approximately, by evaluating the learning dynamics Fij on a finite subset of points, which provide good enough coverage of faces of T. If some analytical knowledge on learning dynamics is available, we can verify (7) rigorously (with sufficient numerical precision). For instance, assume that we know the upper bound for the Lipschitz constant of F over T, given by L. Our verification is based on the following observation. We will check whether

where S denotes either of the faces Tij l , Tij r , respectively, or their hyperrectangular subsets. Then it is enough to verify that either

where C(S) is the baricenter (i.e. the centroid / intersection of diagonals) of S. Alternatively, we can show that

which will prove that the candidate T is not a trapping region.

If S is the whole face of T (i.e. Tij l or Tij r for some i, j), then the verification of inequality (11) can fail, even despite that T is a trapping region. Therefore, we propose to adopt binary space partitioning mechanism [Fuchs et al., 1980] to iteratively subdivide faces of T into smaller hyperrectangles, until inequalities fail, or all hyperrectangles have been verified. For details, we refer to the pseudocode in Algorithm 1. The function SPLIT in Algorithm 1 splits a hyperrectangle S into two disjoint non-empty hyperrectangles S1, S2, such that S = S1 ∪ S2 in half, along the longest dimension of the hyperrectangle.

Theorem 3. If T is a trapping region, Algorithm 1 is guaranteed to terminate in finite steps. Without loss of generality, assume that T is a unit hypercube. Then, the computational complexity of the algorithm is O (log(L/2m∗ )∑ni=1 ki-1∑ni=1 ki ), where

Conversely, if Algorithm 1 terminates and returns true, T is a trapping region for learning rates as in Theorem 2.

3.3 Algorithmic Verification: Sampled Learning Dynamics

In some situations, the exact learning dynamics are not available - e.g. they depend on a reward, which can only be obtained from a real world or an experiment. Then, one has to resort to heuristic verification of trapping regions, by sampling points from the faces of the interval set. We provide the pseudocode for this situation in Algorithm 2, and apply it in practice in traffic management example in Section 4.2.

Algorithm 1 Rigorous trapping region verification via binary space partitioning.

Inputs: Learning dynamics F , T = [x11 - , x11 + ] × · · · × [xnkn - , xnkn + ] - a candidate for the trapping region, L - upper bound for Lipschitz constant of F over T. Returns: Is T a trapping region? Start: 1: for agent i in 1:n in parallel do 2: for coordinate j in 1:kn in parallel do 3: for direction in {left,right} in parallel do 4: if direction is left then 5: SETS TO CHECK = {Tij l }, δ = -1 6: else 7: SETS TO CHECK = {Tij r }, δ = 1 8: while SETS TO CHECK ̸= ∅ do 9: S = SETS TO CHECK.POP() 10: C(S) = baricenter(S) 11: if δFij(C(S)) ≥ 0 then 12: return false // no isolation 13: else if δFij (C(S)) + L diam(S) /2 ≥ 0 then 14: // need subdivision to check isolation 15: S1, S2=SPLIT(S) // binary partitioning 16: SETS TO CHECK.PUSH(S1, S2) 17: return true

Proposition 1. Algorithm 2 always terminates in finite steps, regardless of whether T is a trapping region or not. The computational complexity of the algorithm is O(2M ∑ni=1 ki).

We remark that Algorithm 2 contains a naive, uniform sampling strategy, and one can envision a more sophisticated treelike partitioning, like in Algorithm 1, where we resample the regions in which we are closest to failing the isolation inequalities. However, due to computational demands of our illustrative example, the traffic experiment in Section 4.2, we have opted for uniform sampling, as it offers highest parallel execution potential, and was most suited for execution in a computational cluster environment - every sample evaluation can be executed as a separate process.

Theorem 4. Let S∗ be the set of all sampled points, D be the size of mesh generated by the sample, i.e.

Also let

quantify how close we were to fail verifying isolation over S∗ . If Algorithm 2 returns true and F is Lipschitz-continuous with Lipschitz constant L < m∗ /D, then T is a trapping region for learning rates as in Theorem 2.

4 Examples

In this Section we will provide examples of application of Algorithm 1 to two systems with known dynamics - a Generative Adversarial Network in Subsection 4.1 and of application Algorithm 2 Non-rigorous trapping region verification via sampling.

Inputs: Learning dynamics F , F - learning dynamics, can be only sampled (e.g. from simulator), T = [x11 - , x11 + ] × · · · × [xnkn - , xnkn + ] - a candidate for the trapping region, M - sample size per face Returns: Is T a trapping region? Start: 1: for agent i in 1:n in parallel do 2: for coordinate j in 1:kn in parallel do 3: for direction in {left,right} in parallel do 4: if direction is left then 5: SET = Tij l , δ = -1 6: else 7: SET= Tij r , δ = 1 // a uniformly spaced sample of M points 8: S = SAMPLE POINTS(SET, M) 9: for x ∈ S in parallel do 10: // F evaluated on sample points 11: if δFij(x) ≥ 0 then 12: return false // no isolation 13: return true

of Algorithm 2 to a traffic learning system with dynamics provided by the system simulator in Subsection 4.2. Additional example in a model of economic competition is provided in the Supplementary Material.

4.1 Generative Adversarial Learning

Our first example is a system, which exemplifies the issue of non-convergence of multi-agent learning, but where trapping regions can be readily constructed. Since the learning is non-convergent, methods based on Lyapunov functions, and regions of attractions of equilibria would not be applicable to this scenario. We consider a parameterized family of learning systems, where the parameter controls the coupling between learner rewards - from completely decoupled, to strongly coupled. More concretely, agent one is in control of a continuous variable ψ ∈ R, and agent two controls θ ∈ R. The rewards of each agent are the negative of the loss functions for each, and these are given by

and

for some positive, small ϵ.

Both agents use gradient descent on their respective loss functions, with a fixed step γ, which leads to following update rules

which, for short, we shall denote by (ψt+1, θt+1) =: G(ψt, θt).

Although a system with such prescribed loss functions is nothing more than a toy example, it serves to accentuate the problems of non-convergence. Similar learning systems have been thoroughly analyzed in literature; this system in fact has the same update rules as the famously non-convergent DiracGAN example in [Mescheder et al., 2018] with the Wasserstein loss function, where both the generator and the discriminator apply an L4 regularization term weighted by factor inversely proportional to ϵ.

The dynamics of (18) are surprisingly complicated for such low dimensional system. The system possesses a single Nash equilibrium (ψ, θ) = (0, 0) (also the only learning equilibrium), regardless of the value of ϵ. For joint optimization, the equilibrium is always locally unstable (regardless of how small the system coupling parameter ϵ is), and the learning trajectories starting from its near proximity diverge from it until they enter a cyclic regime. For initial conditions of larger norm, they converge towards the cyclic attractor, and never reach the equilibrium; in fact none of the other trajectories does. The divergence from the Nash equilibrium is formalized via the following proposition below (with ∥·∥ denoting L2 norm):

Proposition 2. For any γ > 0 and any ϵ > 0 there exist a value R0 > 0, such that for any (ψ0, θ0) with 0 < ∥(ψ0, θ0)∥ < R0 we have ∥G(ψ0, θ0)∥ > ∥(ψ0, θ0)∥. As a consequence, (0, 0) is a repelling equilibrium.

On the other hand, it is easy to find trapping regions. We report that by executing Algorithm 1 we have successfully established existence of various trapping regions for different values of ϵ, and computed γ bounds via formula (8) (by making use of quantities obtained in the algorithm):

• T = [-0.1, 0.1]2 and ϵ ∈ {0.01, 0.02, 0.03, 0.04} (we report failure, i.e. it is not a trapping region for ϵ = 0.05) and the upper bounds on γ are given by {4.6 × 10-3 , 7.9 × 10-3 , 1.7 × 10-3 , 10-17 }, respectively;
• T = [-0.2, 0.2]2 and ϵ ∈ {0.05, 0.1, 0.15} (failure for

ϵ = 0.2), and the upper bounds on γ are given by {1.9× 10-2 , 4.6 × 10-4 , 2.0 × 10-4 }, respectively.

The Lipschitz constants in both examples were found analytically, by maximizing the L1 norm of the total derivative ||D(ψ,θ)G|| over (ψ, θ) ∈ T. We remark that the closer we got to the point of failure, the more subdivisions were needed in the partitioning algorithm, however the execution time was near immediate - a few seconds at most on a modern laptop, without leveraging parallelization. To contrast, a brute force optimization without verifying the trapping region would yield endless execution without convergence, and without any guarantees that learning will not diverge.

For this particular system, we can also prove the existence of an ϵ-parameterized family of trapping regions theoretically, by the following proposition:

Proposition 3. The square given by [-√ϵ, √ϵ]2 is a trapping region for step size γ > 0 small enough. As a consequence, trajectories never leave [-√ϵ, √ϵ]2 , and there is an equilibrium inside [-√ϵ, √ϵ]2 (it is in fact the global Nash equilibrium (0, 0)).

4.2 Multi-Agent Traffic Management

Our second example is of a more practical nature. We analyze a rectangular network of four signalized intersections, each situated 200 meters from its two nearest neighbors, as depicted in Figure 3. Each of the intersections controls traffic by alternating between one of two phases - giving green to either the vertical or the horizontal stream of vehicles. The cycle time, i.e. the total time for serving the horizontal and, subsequently, the vertical movement is set to 60 seconds. For each episode of simulation, of length of two hours, each intersection can select a strategy from the continuous set A = [0, 60], which determines the amount of green seconds to be assigned to the first phase (the offset). The remainder of the cycle is assigned to the second phase. The vehicle streams are generated on all roads in all directions (i.e. east ↔west, and north ↔ south), and, for simplicity, we excluded left and right turning movements on intersections. The simulation is controlled by an open-source microscopic traffic simulator SUMO [Lopez et al., 2018], version 1.8.0. The episodical payoff for each intersection is the negative of the aggregate number of vehicleseconds on all road lanes incoming to the intersection, therefore the goal of each intersection is to dispatch the incoming traffic as efficiently as possible. To ensure that the learning dynamics do not exhibit trivial symmetries, the simulations were performed for a simple instance of asymmetrical demand. One vehicle would be spawned each ten seconds on the beginning of each of the outmost lanes of the network, with the exception of the northeast ↔ northwest stream, where vehicles are spawned every five seconds. Analogous computations could have been performed for other traffic patterns.

For our experiment, the selection of the strategy by the learners is performed via decoupled gradient descent, as in Equations (1) and (2). Each intersection controller estimates the gradient of own reward by difference quotients:

for some small δ (in our experiments δ = 0.1). The adaptation rate γ is set to 10-6 . Such settings were chosen as they would give satisfactory results for learning on one intersection, while keeping other intersections fixed.

As discussed previously, non-convergence is an undesirable learning effect in such traffic management scenario, as one would like to ensure that learning always stays within some predetermined bounds, so minimal green time can be given to vehicle flows and pedestrians within each cycle. As a reasonable prerequisite we assume that each phase should be given at least 20 seconds of green time, which translates to the candidate for a trapping region given by T = [20, 40]4 . From the nature of the problem, we expect the reward function to be continuous, but we do not have an analytical formula for it. Therefore, we apply Algorithm 2 and sample faces of T with a uniform rectangular grid of five points in each direction (M = 125). This part of computation is parallelized over multiple threads, and so it does not significantly increase verification time.

The numerical evaluation of isolation inequalities (7) is successful; and, according to Theorem 1 we conclude that each learning trajectory that starts in T stays in T, regardless of whether it converges, and that there is a learning equilibrium in intT. We illustrate this by plotting projections of the trapping region and four learning trajectories in Figure 4. We remark that due to parallelization, verifying the region was much more efficient computationally, than computing learning trajectories. It took about half an hour on 32 CPUs, whereas computation of depicted 500 steps of each learning trajectory took about eight hours, and could utilize only one CPU per trajectory. The experiment used AMD 7452 and AMD 7502P CPUs, 2.35 and 2.5 Ghz respectively. It would have been technically possible to execute the algorithm on a GPU, however in this example it would bring no advantage, as the most time consuming part was obtaining reward difference quotients from the system simulator, which can only run on CPUs.

5 Applicability, Limitations and FutureWork

In this paper we have introduced the method of trapping regions, which can be used to circumvent safety problems caused by non-convergence in multi-agent learning. We have presented algorithms for verification of trapping regions, and theoretical results on the implications for safety and provided examples in GAN learning, in an applied traffic management scenario, and (in the Supplementary Material) in a standard mathematical model of economic competition.

Our examples are relatively low-dimensional. We however remark, that even low-dimensional learning can be non-convergent and highly unpredictable, and therefore pose safety concerns (e.g. the chaotic example of chaos in a simple two player game [Sato et al., 2002]). Moreover, lowdimensionality of strategy spaces does not mean that the learning systems need to be trivial; for instance agents can be controlled by high-dimensional pre-trained neural networks with the last layer being retrained online. Our algorithms are well suited to deal with such scenarios. The extension of the method to high-dimensional settings is a challenge for future research, due to exponential complexity of verification algorithms w.r.to the joint action space. We see possibilities for exploiting symmetries of the action space as a method for dimensionality reduction: e.g., in mean field games where an infinite amount of identical agents share same learning dynamics [Yang et al., 2018], or by employing coordination graphs [Kuyer et al., 2008].

Acknowledgements

This project was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 758824 -INFLUENCE).