No-Regret Learning in Games is Turing Complete

A finite $n$-player normal form game consists of $n$ agents $[n]=\{1,\dots,n\}$, where each agent $i\in[n]$ can choose actions from a finite action set $S_{i}$. Actions are chosen by agent $i$ according to a mixed strategy, a distribution $\textbf{x}_{i}$ in the probability $|S_{i}|$-simplex $\Delta^{|S_{i}|}=\{\textbf{x}_{i}\in\mathbb{R}^{|S_{i}|}_{+}:\sum_{s\in S_{i}}x_{is}=1\}$. In normal form games, agents receive payoffs from pairwise interactions according to payoff matrices $A_{i,j}\in\mathbb{R}^{|S_{i}|\times|S_{j}|}$ where $i,j\in[n]$ and $i\neq j$. Given that mixed strategies $\textbf{x}_{i}\in\Delta^{|S_{i}|}$ and $\textbf{x}_{j}\in\Delta^{|S_{j}|}$ are chosen, agent $i$ receives payoff $\textbf{x}^{\intercal}_{i}A_{i,j}\textbf{x}_{j}$. These payoffs yield a natural optimization problem for each agent, where agents act strategically and independently to maximize their expected payoff over the other agents’ mixed strategies, i.e.

Throughout the paper we’ll restrict our attention to the case known as matrix games, when $n=2$.

In many game settings, the optimization in eq. (1) is a moving target since the opponent adaptively updates their strategy and the payoff matrix may be unknown. In such settings, arguably the most well known class of algorithms is Follow-the-Regularized-Leader (FTRL). The continuous-time version of an FTRL algorithm is as follows. Given initial payoff vector $\textbf{y}_{i}(0)$, an agent $i$ that plays against agent $j$ in a matrix game $A_{i,j}$ updates their strategy at time $t$ according to

where $h_{i}$ is strongly convex and continuously differentiable. FTRL effectively performs a balancing act between exploration and exploitation. The cumulative payoff vector $\textbf{y}_{i}(t)$ indicates the total payouts until time $t$, i.e. if agent $i$ had played strategy $s_{i}\in S_{i}$ continuously from $t=0$ until time $t$, agent $i$ would receive a total reward of $\textbf{y}_{is_{i}}(t)$. The two most well-known instantiations of FTRL dynamics are the online gradient descent algorithm when $h_{i}(\textbf{x}_{i})=||\textbf{x}_{i}||_{2}^{2}$, and the replicator dynamics (the continuous-time analogue of Multiplicative Weights Update (Arora et al., 2012)) when $h_{i}(\textbf{x}_{i})=\sum_{s_{i}\in{\cal S}_{i}}\textbf{x}_{is_{i}}\ln\textbf{x}_{is_{i}}$. FTRL dynamics in continuous time has bounded regret in arbitrary games (Mertikopoulos et al., 2018). For more information on FTRL dynamics and online optimization, see Shalev-Shwartz (2012).

In this paper, we will focus on replicator dynamics (RD) as the learning process generating game dynamics. In addition to its role in optimization, replicator dynamics is the prototypical dynamic studied in evolutionary game theory (Weibull, 1995; Sandholm, 2010) and is one of the key mathematical models of evolution and biological competition (Schuster and Sigmund, 1983; Taylor and Jonker, 1978). In this context, replicator dynamics can be thought of as a normalized form of ecological population models, and is studied given a single payoff matrix $A$ and a single probability distribution x that can be thought abstractly as capturing the proportions of different species/strategies in the current population. Species/strategies get randomly paired up and the resulting payoff determines which strategies will increase/decrease over time.

Formally, the dynamics are as follows. Let $A\in\mathbb{R}^{m\times m}$ be a matrix game and $\textbf{x}\in\Delta^{m}$ be the mixed strategy played. RD on $A$ are given by:

Under the symmetry of $A_{i,j}=A_{j,i}$, and of initial conditions (i.e. $\textbf{x}_{i}=\textbf{x}_{j}$), it is immediate to see that under the $\textbf{x}_{i},\textbf{x}_{j}$ solutions of eq. (2) are identical to each other and to the solution of eq. (3) with $A=A_{i,j}=A_{j,i}$. For our purposes, it will suffice to focus on exactly this setting of matrix games defined by a single payoff matrix $A$ and a single probability distribution x, which is actually the standard setting within evolutionary game theory.

A dynamical system is a mathematical model of a time-evolving process. The objects undergoing change in a dynamical system is called its state and is often denoted by $\textbf{x}\in\mathbb{X}$, where $\mathbb{X}$ is a topological space called a state space. For most of this paper we will be focusing on continuous time systems, but in §5 we will consider discrete time systems derived from numerical approximations of their continuous counterpart. To distinguish between continuous and discrete time, we will use $\textbf{x}(t)$ to describe the state as a function of continuous time $t\in\mathbb{R}$ and $\textbf{x}^{t}$ to describe the state as a function of discrete time $t\in\mathbb{Z}$.

Change between states in a continuous time dynamical system is described by a flow $\Phi:\mathbb{X}\times\mathbb{R}\to\mathbb{X}$ satisfying two properties:

1. (i)

   For each $t\in\mathbb{R}$, $\Phi(\cdot,t):\mathbb{X}\to\mathbb{X}$ is bijective, continuous, and has a continuous inverse.

2. (ii)

   For every $s,t\in\mathbb{R}$ and $\textbf{x}\in\mathbb{X}$, $\Phi(\textbf{x},s+t)=\Phi(\Phi(\textbf{x},t),s)$.

Intuitively, flows describe the evolution of states in the dynamical system. Given a time $t\in\mathbb{R}$, the flow gives us the relative movement of every point $\textbf{x}\in\mathbb{X}$; we will denote this by the map $\Phi^{t}:\mathbb{X}\to\mathbb{X}$. Similarly, given a point $\textbf{x}\in\mathbb{X}$, the flow captures the trajectory of x as a function of time; in an abuse of notation, we will denote this by $\textbf{x}(t)$ where $t$ is changing.

Continuous time dynamical systems are often given as systems of ordinary differential equations (ODEs). Systems of ODEs describe a vector field $V:\mathbb{X}\to T\mathbb{X}$ which assigns to each $\textbf{x}\in\mathbb{X}$ a vector in the tangent space of $\mathbb{X}$ at x. The unit sphere $\mathbb{S}^{n}=\{\textbf{x}\in\mathbb{R}^{n+1}:\|x\|_{2}^{2}=1\}$ will play a special role in proving Theorem 1, in which case the tangent space $T\mathbb{S}^{n}$ at each $\textbf{x}\in\mathbb{S}^{n}$ is $\{\textbf{y}\in\mathbb{R}^{n}:\textbf{x}\cdot\textbf{y}=0\}$. Intuitively, the tangent space defines bundles of vectors that ensure the system’s states remain well defined on the state space as time progresses. A system of ODEs is said to generate (or give) a flow $\Phi$ if $\Phi$ describes a solution of the ODEs at each point $\textbf{x}\in\mathbb{X}$. Throughout this paper we assume that all dynamical systems discussed can be given by a system of ODEs. For this reason, we will use the term dynamical system to refer to the system of ODEs, the associated vector field, and a generated flow interchangeably. A well known result in dynamical systems theory states that, for Lipschitz-continuous systems of ODEs, the generated flow is unique (see Perko (1991); Meiss (2007)) and using these terms interchangeably is well defined.

An important notion for proving Theorem 1, and dynamical systems in general, is that of a global attracting set of the dynamical system. Let $\Phi$ be a flow generated by some dynamical system on $\mathbb{X}$. We say $\mathbb{Y}\subset\mathbb{X}$ is forward invariant for the flow $\Phi$ if $\Phi^{t}(\textbf{y})\in\mathbb{Y}$ for every $t\geq 0$, $\textbf{y}\in\mathbb{Y}$. We say $\mathbb{Y}\subset\mathbb{X}$ is globally attracting for the flow $\Phi$ if $\mathbb{Y}$ is nonempty, forward invariant, and

Stated informally, if $\mathbb{Y}$ is globally attracting it will eventually capture the dynamics of $\Phi$ starting from any point in $\mathbb{X}$ after some transitionary period of time.

Now let $\mathbb{X}$ and $\mathbb{Y}$ be two topological spaces. We say that a function $f:\mathbb{X}\to\mathbb{Y}$ is a homeomorphism if (i) $f$ is bijective, (ii) $f$ is continuous, and (iii) $f$ has a continuous inverse. Furthermore, two flows $\Phi:\mathbb{X}\times\mathbb{R}\to\mathbb{X}$ and $\Psi:\mathbb{Y}\times\mathbb{R}\to\mathbb{Y}$ are homeomorphic if there exists a homeomorphism $g:\mathbb{X}\to\mathbb{Y}$ such that for each $\textbf{x}\in\mathbb{X}$ and $t\in\mathbb{R}$ we have $g(\Phi(\textbf{x},t))=\Psi(g(\textbf{x}),t)$. If $g$ is also $C^{1}$ and has a $C^{1}$ inverse, then we say $g$ is a diffeomorphism and that the flows $\Phi$ and $\Psi$ are diffeomorphic. Observe that every diffeomorphism is also a homeomorphism, and thus every pair of diffeomorphic flows are also homeomorphic. Homeomorphic (resp. diffeomorphic) flows satisfy a strong, and typical, notion of equivalence between dynamical systems. Intuitively, two dynamical systems are homeomorphic if their trajectories can be mapped to one another by stretching and bending space.

Throughout this paper we rely crucially on the notion of a Turing complete dynamical systems, i.e. a dynamical system able to simulate any Turing machine. We will briefly recall the Turing machine model and formalize its relationship with dynamical systems.

A Turing machine is given by a tuple $T=\left(Q,\Sigma,\delta,q_{0},q_{\text{halt}}\right)$ where

• •

  $Q$ is a finite set of states, including an initial state $q_{0}$ and a halting state $q_{\text{halt}}$;

• •

  $\Sigma$ is an alphabet with cardinality at least two;

• •

  $\delta:Q\times\Sigma\to Q\times\Sigma\times\{-1,0,1\}$ is a transition function.

For a given Turing machine $T$ and an input tape $s=(s_{i})_{i\in\mathbb{Z}}\in\Sigma^{\mathbb{Z}}$, the Turing machine’s computation is carried out according to the following process:

• [0]

  Initialize the current state $q$ to $q_{0}$, and the current tape $w=(w_{i})_{i\in\mathbb{Z}}$ to be $s$.

• [1]

  If $q=q_{\text{halt}}$ then halt the algorithm and return $w$ as output. Otherwise compute $\delta(q,w_{0})=(q^{\prime},w^{\prime}_{0},\sigma)$, where $\sigma\in\{-1,0,1\}$.

• [2]

  Update the current state and tape by setting $q=q^{\prime}$ and the $0^{\text{th}}$ position of $w$ to $w_{0}=w^{\prime}_{0}$.

• [3]

  Update $w$ with the $\sigma$ shifted tape $(w_{i+\sigma})$, then return to [1].

Without loss of generality, we will assume that Turing machines adhere to standard simplifying conventions (cf. Sipser (1996)). Specifically, we assume that the alphabet $\Sigma=\{0,\dots,9\}$ and any given tape of the Turing machine only has a finite number of symbols different from $0$, where $0$ represents the special “blank symbol”. Under these assumptions it follows that there exists a finite (possibly large) integer $k_{0}>0$ such that any tape $w$ satisfies

with each $w_{i}\in\Sigma$. Equivalently, at any given step in the Turing machine’s evolution, these assumptions ensure there can be at most $2k_{0}+1$ non-blank symbols on the tape. In particular, we get that the space of configurations of a Turing machine $T$ is $Q\times A\subset Q\times\Sigma^{\mathbb{Z}}$, where $A$ is the subset of strings taking the form (5).

The construction of dynamical systems that simulate Turing machines is at the heart of our results, and has been studied for various problems in physics (Reif et al., 1994; Freedman, 1998; Cardona et al., 2021b). Although equivalent definitions exist, our analyses will adopt the formalisms used by recent work on fluid dynamics (Cardona et al., 2021a; Tao, 2017). An analogous definition can be given for flows on a manifold.

Intuitively, a dynamical system simulates a Turing machine if there is a correspondence between trajectories reaching certain sets and computations halting with certain configurations. In particular, constructing the point $p_{s}$ depends only on the Turing machine $T$ and input tape $s$, while constructing the set $U_{w_{-k},\dots,w_{k}}$ depends only on the specified halting configuration of $T$. Both here and throughout the paper, we say a mathematical object (e.g. points, sets, or matrices) is constructible if it can be computed in finite time; constructability is not explicitly used in our arguments, but is important for nuanced technical reasons since it disallows pathological scenarios such as having all information about a machine’s computations being encoded in an initial condition.

Definition 1 leads to a natural notion of Turing completeness for dynamical systems.

Our construction of Turing complete game dynamics relies crucially on the notion of generalized Lotka-Volterra (GLV) vector fields. In particular, two properties of GLV vector fields will play a key role in the proof: (i) polynomial vector fields on $\mathbb{R}^{n}_{++}$ are a special case of GLV vector fields, and (ii) GLV vector fields can be embedded into RD on a matrix games without approximation.

Formally, a GLV vector field is a vector field on $\mathbb{R}^{n}_{++}$ given by the system of ODEs

where $m$ is some positive integer, $\lambda\in\mathbb{R}^{n}$, $A\in\mathbb{R}^{n\times m}$, and $B\in\mathbb{R}^{m\times n}$. Since exponents given by $B$ can be any real number, the terms in the parentheses are multivariate generalized polynomials. In special cases where the ODEs are standard multivariate polynomials, GLV vector fields equate to polynomial vector fields—a fact straightforwardly shown by noting that any polynomial vector field $P=\{P_{i}\}_{i\in[n]}$ on $\mathbb{R}^{n}_{++}$ is equivalent to the GLV vector field $\tilde{P}=\{x_{i}(\tfrac{1}{x_{i}}P_{i})\}_{i\in[n]}$.

Polynomial and GLV vector fields play an integral role by allowing us to invoke recent results by Cardona et al. (2021a) and Andrade et al. (2021). The starting point of our construction can stated as follows:

In Appendix A we provide a proof sketch of this result; we refer the reader to Cardona et al. (2021a) for the full proof. In §3.2 we will extend the Turing completeness from Proposition 1 to replicator dynamics in matrix games by leveraging recent work by Andrade et al. (2021). In essence, Andrade et al. (2021) showed that GLV vector fields can approximate essentially any dynamical system, and that any GLV vector field can be embedded into the dynamics of RD on some matrix game. In this paper we only rely on the latter result, since polynomial vector fields are already a special case of GLV vector fields and thus do not need to be approximated.

At a high level, proving Proposition 2 boils down to composing an embedding trick introduced by Brenig and Goriely (1989) with Theorem $7.5.1$ by Hofbauer and Sigmund (1998). The relationship highlighted here between $m-1$ and the number of monomials was not included in the original statement by Andrade et al. (2021), however it is shown as part of an important step in their proof and is required for Corollary 1.

To prove the main result of this section, Theorem 1, we will apply Proposition 2 on a diffeomorphism of the Turing complete vector field constructed in Proposition 1.

An interesting corollary of Theorem 1 is that we arrive at a bound on the number of actions needed for defining games where learning dynamics can be Turing complete. The bound is likely loose for several reasons. Firstly, the polynomial vector field from Proposition 1 is not known to have minimal degree nor dimension. Secondly, the combinatorial argument in Appendix B makes no attempt at a nuanced count on the number of unique monomials in the polynomials given by these vector fields. Deriving a tight bound is not only an interesting open question for game dynamics, but also for recent work in fluid dynamics (Cardona et al., 2021a; de Lizaur, 2021) and analog computing (Hainry, 2009).

The halting problem is a prototypical decision problem for Turing machines and is arguably the most famous undecidable problem in computer science. Given a Turing machine $T$ and an input tape, the halting problem for $T$ asks whether or not $T$ will halt. By contrast, the reachability problem is canonical for dynamical systems and has been studied in various control settings; given a dynamical system $X$ and a set of initial conditions, the reachability problem for $X$ asks whether or not $X$’s trajectory will intersect a predetermined set. Although the computability of the halting problem is generally well understood in Turing machines, the computability of the reachability problem has not traditionally been studied in the context of game dynamics. However, from the strong equivalence between halting and reachability required by Definition 1, we immediately get a reduction between these classic decision problems.

The proof of this proposition follows directly from Definition 1, since checking whether the dynamical system reaches a set becomes equivalent to checking whether the Turing machine halts by definition. From Theorem 1 we know that replicator dynamics on a matrix game can simulate a universal Turing machine. Therefore, due to the undecidability of the halting problem in general, we deduce that the reachability problem can be undecidable for replicator dynamics on matrix games.

The corollary follows immediately from Proposition 3 and Theorem 1, since the undecidability of the halting problem for universal Turing machines uncovers the undecidability of the reachability problem for replicator dynamics on matrix games.

Games are primarily understood and studied via equilibrium concepts, e.g. Nash equilibria, evolutionary stable strategies, and coarse correlated equilibria. It is therefore unsurprising that the goal of learning in games is often to converge on some set of equilibria. Yet, beyond certain special cases (e.g. potential games), learning behaviours remain largely enigmatic and there has been limited progress towards resolving non-convergence in general settings. The results in this paper may explain why: determining convergence to a set of equilibria is a special case of reachability, and identifying learning algorithms that provably converge on such a set can be an undecidable problem even in very simple classes of games. The goal of this section is to formalize this intuition.

In Corollary 2 we found that reachability can be undecidable for replicator dynamics on matrix games. Therefore, taken as a negative result, Corollary 2 implies that undecidable trajectories can exist in larger classes of game dynamics where replicator dynamics on matrix games is a special case. Unfortunately, replicator dynamics is special case of FTRL dynamics and no-regret learning dynamics more generally (Mertikopoulos et al., 2018), which suggests these popular learning dynamics can inherit the negative result on any class of games containing matrix games. Similarly, matrix games are very restricted and a special case of many popular classes of games, e.g. normal form and smooth games. As an example of how broadly these results generalize, matrix games in the FTRL framework describe quadratic objective functions and thus undecidable trajectories exist for optimization-driven learning over quadratic objectives. Thus, as Corollary 2 holds for replicator dynamics on matrix games, we arrive at the reachability problem being generally undecidable for rich classes of game dynamics studied in the literature and used in practice.

In light of Corollary 2, the claim follows from our discussion above. As determining convergence to sets of game theoretic solution concepts is a special case of the reachability problem, Corollary 3 reveals that determining whether game dynamics converge to fundamental solution concepts is undecidable in general. It is important to note that the undecidability may not hold for specific games or learning dynamics; the primary take-away is that undecidability is possible and has strong implications about how we should approach these important questions.

The fact that MWU is a discretization of replicator dynamics is well known in the field of game dynamics, but a precise derivation of this relationship is often omitted. For clarity in our analysis of discretization errors, we will highlight one possible discretization that reveals MWU as a discrete-analogue of replicator dynamics in Appendix C. The discretization we arrive at is used to find a bound on the cumulative error of MWU relative to replicator dynamics, which is crucial for the analyses and discussion to follow.

The proof of Lemma 1 consists of relatively straightforward calculations, but requires carefully handling nonlinearities introduced by MWU; a full proof is included in Appendix D.

Using Lemma 1 as a basis, we can bound the error accrued over multiple iterations of MWU.¹¹1In the language of numerical analysis, Lemma 1 gives the local error used to find the global error in Lemma 2.

A full derivation of Lemma 2 is found in Appendix E, and follows from using Lemma 1 alongside standard techniques for bounding error in iterated numerical methods.

The result in Lemma 2 shows that, relative to replicator dynamics, the error accrued by MWU will grow with the number of iterations. Error growing as a function of time is problematic when simulating a Turing machine by using MWU as discretization of replicator dynamics.

Recall that in Theorem 1 we showed that replicator dynamics can simulate a universal Turing machine because it can embed a dynamical system that simulates a universal Turing machine, which is done to ensure the Turing machine’s halting remains equivalent to the dynamics’ trajectories reaching a certain set. However, in general, determining whether such a Turing machine will halt or how many steps are required to halt is undecidable. Therefore, without an a priori bound on the maximum amount of time needed to determine whether the machine halts or not, we cannot choose step sizes for MWU that guarantee the discretization remains sufficiently close to replicator dynamics when intersecting the relevant set.

The result follows from the construction of the open sets used in Proposition 1 and the fact that we can ensure MWU’s discretization error stays sufficiently small over any finite window of time due to Lemma 2. Resolving the limitations of Theorem 2, and uncovering the true computational power of discrete algorithms such as MWU, will likely require new technical approaches for bounding errors or simulating Turing machines.