Online Optimization in Games via Control Theory:
Connecting Regret, Passivity and Poincaré Recurrence

We provide affirmative answers to both questions raised above. We show that any finitely passive learning dynamic¹¹1 In control theory literature, a passive operator usually has a storage function with a finite lower bound. In this paper, storage functions can have a finite lower bound or not, depending on the types of the operators. We emphasize those operators which have a storage function with a finite lower bound as being finitely passive. For the definition of finitely passive learning dynamic, see Definition 5. guarantees constant regret (Theorem 8). By using the notion of convex conjugate from convex analysis, we show that any continuous-time FTRL dynamic is finitely passive and lossless (Theorem 7); the same holds for certain escort replicator dynamics [Har11] (Appendix D). These generalize [Mab18] which showed that Replicator Dynamic is finitely lossless. Combining the two theorems above immediately recovers the result in [MPP18] that any FTRL dynamic guarantees constant regret. We note that in the analysis of Mabrok [Mab18], the state space (i.e. the domain of the storage function) is the space of mixed strategies, while we turn to a new state space of cumulative payoffs for FTRL. This choice is crucial for the generalization to FTRL dynamics, and it permits a cleaner proof via the tools established in convex analysis.

A key observation that enables the above results is that FTRL dynamic admits a storage function with a simple gradient structure, which will be described formally in Section 5. This motivates us to study a new family of lossless learning dynamics, which is in one-one correspondence with the family of storage functions possessing that gradient structure. By observing that such storage functions are closed under convex combination, we discover that any convex combination of FTRL dynamics is finitely passive and lossless, and thus guarantees constant regret (Theorem 16). “Convex combination of FTRL dynamics” means: Suppose there are $k$ FTRL dynamics, indexed from $1$ to $k$. When we use the $j$-th one, it converts the cumulative payoffs at time $t$ to a mixed strategy $\mathbf{x}_{j}^{t}$. A convex combination of these FTRL dynamics converts the cumulative payoffs at time $t$ to the mixed strategy $\sum_{j=1}^{k}\alpha_{j}\cdot\mathbf{x}_{j}^{t}$, where $\alpha_{j}$’s are positive constants satisfying $\sum_{j=1}^{k}\alpha_{j}=1$.

Convex combinations of lossless dynamics are directly analogous to linear combinations of conservative vector fields in analyzing physical dynamics (see Figure 1). This technique is also of practical relevance, since we might want to mix-and-match different dynamics to elicit their advantages. For instance, different learning dynamics may lean toward either exploitation or exploration. By combining them via convex combination with our own choice of $\alpha_{j}$’s, we can control our desired balance between exploitation and exploration (see Example 14).

We also show that for every graphical constant-sum game (e.g. two-person zero-sum game) that admits a fully-mixed Nash equilibrium, it corresponds to a finitely lossless game operator (Proposition 17). Thus, the game dynamic of any convex combinations of FTRL dynamics in such a game corresponds to a finitely lossless operator. We use this observation to show that the game dynamic is almost perfectly recurrent, via the notion of Poincaré recurrence (Theorem 19). This distinguishes our work from [FS13] and its subsequent works about learning in games, as they mostly concern stability/convergence, while we study recurrence.

In Sections 2 and 3, we present the necessary background for this work, including the definitions of different operators, the notions of (lossless) passivity and storage function, and some basic results about passivity. In Section 4, we show the desirable properties (finitely losslessness, constant regret) of FTRL dynamics. In Section 5, we present a characterization of lossless learning dynamics via the above-mentioned gradient structure of storage functions, and we discuss some properties of convex combinations of such learning dynamics. The results about Poincaré recurrences of learning in graphical constant-sum games are presented in Section 6. All missing proofs can be found in the appendix.

We focus on the following type of continuous-time learning dynamics. An agent has an action set $A$; let $n:=|A|$. The process starts at time $0$. For any time $t\geq 0$ and for each action $j\in A$, the agent computes the cumulative payoff if she chooses action $j$ in the time interval $[0,t]$, denoted by $q_{j}(t)$. Formally, for each action $j$, let $p_{j}(\tau)$ denote the (instantaneous) payoff to action $j$ at time $\tau$. Then

where $q_{j}^{0}$ is a constant chosen at the beginning of the process. Let $\mathbf{q}(t):=(q_{1}(t),\cdots,q_{n}(t))$. For any $t\geq 0$, the agent uses a conversion function $f$ which takes $\mathbf{q}(t)$ as input, and outputs a mixed strategy $\mathbf{x}(t)\in\Delta^{n}$ over the $n$ actions. The process can be expressed compactly as an ordinary differential equations (ODE) system:

When $\mathbf{q}^{0}=(q_{1}^{0},\ldots,q_{n}^{0})$ is already given, the conversion function $f$ specifies the learning dynamic. The learning dynamic can be viewed as an operator, which takes the function-of-time $\mathbf{p}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{n}$ as input, and the output is another function-of-time $\mathbf{x}:\mathbb{R}^{+}\rightarrow\Delta^{n}$.

For any $\mathbf{p}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{n}$, the regret of a learning dynamic at time $T>0$ is

We say a learning dynamic guarantees constant regret if for any $\mathbf{p}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{n}$ and any $T>0$, the regret at time $T$ is bounded from above by a constant that depends on $\mathbf{q}^{0}$ only.

When the conversion function $f$ is the logit choice map

where $\mathcal{N}=\sum_{j=1}^{n}\exp(q_{j})$, the learning dynamic (1) is equivalent to the well-known Replicator Dynamic [HS98, San10], which is the continuous-time analogue of Multiplicative Weights Update.

A FTRL learning dynamic is specified by a strictly convex regularizer function $h:\Delta^{n}\rightarrow\mathbb{R}$, which determines the conversion function $f$ as below:

It is known that Replicator Dynamic is a special case of FTRL, by setting $h(\mathbf{x})=\sum_{j=1}^{n}x_{j}\log x_{j}$. Online Gradient Descent (OGD) is another commonly studied learning dynamic that is also a special case of FTRL with $L^{2}$ regularization, i.e. $h(\mathbf{x})=\frac{1}{2}\sum_{j=1}^{n}(x_{j})^{2}$. [H⁺16] When $n=2$, the conversion function of OGD is

When a system has $m\geq 2$ agents, and each agent uses a learning dynamic, we concatenate the corresponding learning operators together to form a merged learning operator (MLO). Precisely, the input to the MLO is $\hat{\mathbf{p}}=(\mathbf{p}^{1},\cdots,\mathbf{p}^{m})$, and its output is $\hat{\mathbf{x}}=(\mathbf{x}^{1},\cdots,\mathbf{x}^{m})$, where $\mathbf{x}^{i}$ is the output of the learning operator of agent $i$ when its input is $\mathbf{p}^{i}$. In this paper, we use hat notations (e.g. $\hat{\mathbf{p}},\hat{\mathbf{x}}$) to denote variables formed by such concatenations of variables of individual agents.

Here, we provide a general definition of game operators (as in Figure 2), and leave the discussion about graphical constant-sum games, which appear in our Poincaré recurrence results, to Section 6.

A game has $m$ agents. Each agent $i$ has $n_{i}$ actions. After each agent chooses a mixed strategy over her own actions, the game determines a payoff vector $\hat{\mathbf{p}}\in\mathbb{R}^{n_{1}}\times\cdots\times\mathbb{R}^{n_{m}}$, where $\hat{p}_{k\ell}$ is the payoff to action $\ell$ of agent $k$. Let $\Delta:=\Delta^{n_{1}}\times\cdots\times\Delta^{n_{m}}$, and $\mathcal{P}:=\mathbb{R}^{n_{1}}\times\cdots\times\mathbb{R}^{n_{m}}$. We can think of the game as a function $G:\Delta\rightarrow\mathcal{P}$. Its game operator takes a function-of-time $\hat{\mathbf{x}}:\mathbb{R}^{+}\rightarrow\Delta$ as input, and it outputs a function-of-time $\hat{\mathbf{p}}:\mathbb{R}^{+}\rightarrow\mathcal{P}$, where $\hat{\mathbf{p}}(t)=G(\hat{\mathbf{x}}(t))$ for all $t\geq 0$.

A dynamical game system (DGS) comprises of $m$ agents. The game operator has input $\hat{\mathbf{x}}$ and output $\hat{\mathbf{p}}$. Each agent uses a learning dynamic of the form (1). The agents’ learning operators are concatenated to form a MLO, which has input $\hat{\mathbf{p}}=(\mathbf{p}^{1},\cdots,\mathbf{p}^{m})$ and output $\hat{\mathbf{x}}=(\mathbf{x}^{1},\cdots,\mathbf{x}^{m})$ when $\hat{\mathbf{r}}\equiv\mathbf{0}$. The MLO is interconnected with the game operator in the manner of Figure 2.

To generalize the above idea to passivity of an ODE system, we need several mathematical notations. Let $\mathbb{L}_{2}$ denote the Hilbert space of square integrable functions mapping $\mathbb{R}^{+}$ to $\mathbb{R}^{n}$ with inner product: $\left\langle f,g\right\rangle_{T}:=\int_{0}^{T}\left\langle f(t),g(t)\right\rangle\,\mathsf{d}t$. Let $\mathbb{L}_{2,e}:=\{f:\mathbb{R}^{+}\rightarrow\mathbb{R}^{n}~{}\big{|}~{}\left\langle f,f\right\rangle_{T}<\infty~{}\text{for all }T\in\mathbb{R}^{+}\}$. An (input-output) operator is simply a mapping $S:\mathbb{U}\rightarrow\mathbb{Y}$, where $\mathbb{U},\mathbb{Y}\subset\mathbb{L}_{2,e}$.

We consider the following type of operators, which can be represented by an ODE system called state space system (SSS) of the following general form:

where $\mathbf{z}^{0}\in\mathcal{Z}\subset\mathbb{R}^{d_{1}}$, $\mathbf{z}:\mathbb{R}^{+}\rightarrow\mathcal{Z}$, and $\mathbf{u},\mathbf{y}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{d_{2}}$. The set $\mathcal{Z}$ is called the set of states. As the notations suggest, $\mathbf{u},\mathbf{y}$ are the input and output of this operator respectively. When $\mathbf{u}$ is fed into the operator, the first two equalities define a well-posed ODE system, so a unique solution of $\mathbf{z}$ exists under mild conditions. Then $\mathbf{y}$ is the output determined by a function $g_{2}$ of the unique solution $\mathbf{z}$ and the input $\mathbf{u}$. The learning dynamic (1) is such an operator, by viewing $\mathbf{q},\mathbf{p},\mathbf{x},f(\mathbf{q}(t))$ in (1) as $\mathbf{z},\mathbf{u},\mathbf{y},g_{2}(\mathbf{z}(t),\mathbf{u}(t))$ in (5) respectively. We are ready to present the definition of passivity for such operators.

We note the reminiscence of inequality (6) with the inequality in the motivating example of electrical network.

When a SSS is finitely passive/lossless, we may assume, without loss of generality, that the finite lower bound of its storage function is zero. We make this assumption on all finitely passive/lossless SSS in the rest of this paper.

In Figure 2, we presented a feedback interconnection (FIC) system. While it is intuitive for readers to have a first understanding of the concept in control theory, for our analysis it is more convenient to use Figure 3. The FIC system in Figure 3 consists of two SSS $S_{1}:\mathbb{U}\rightarrow\mathbb{Y}$ and $S_{2}:\mathbb{Y}\rightarrow\mathbb{U}$, with an external input source $\mathbf{r}\in\mathbb{U}$, while its output is $\mathbf{y}_{1}\in\mathbb{Y}$; note that the FIC system is an operator by definition. The variables are related via: $\mathbf{u}_{1}=\mathbf{r}-\mathbf{y}_{2}$, $\mathbf{y}_{1}=S_{1}(\mathbf{u}_{1})$, $\mathbf{u}_{2}=\mathbf{y}_{1}$, and $\mathbf{y}_{2}=S_{2}(\mathbf{u}_{2})$.

An important property of passive operators is that passivity is composable, i.e. the composition of two passive operators results in a passive system. Intuitively, if no operator in the total system is able to produce energy, then the system as a whole cannot produce energy either. The following theorem formally captures this intuition for FIC systems.

Note that in the above theorem, if the FIC system is lossless and $\mathbf{r}$ is the zero function, then we have $L_{1}(\mathbf{z}_{1}(t))+L_{2}(\mathbf{z}_{2}(t))=L_{1}(\mathbf{z}_{1}^{0})+L_{2}(\mathbf{z}_{2}^{0})$ for all $t\geq 0$, i.e. the value of $L_{1}+L_{2}$ does not change over time. The underlying dynamic is said to admit a constant-of-motion.

In the context of DGS, Figure 3 is obtained after several modifications from Figure 2:

• •

  In Figure 2, the game operator’s output is $\hat{\mathbf{p}}$, which is added to $\hat{\mathbf{r}}$ to form the MLO’s input. In Figure 3, the game operator’s output is $-\hat{\mathbf{p}}$ instead, and it is subtracted from $\mathbf{r}$ to form the MLO’s input.

• •

  The MLO’s output is $\hat{\mathbf{x}}$ in Figure 2, but the MLO’s output in Figure 3 has a constant shift $\hat{\mathbf{x}}^{*}=(\mathbf{x}^{*,1},\ldots,\mathbf{x}^{*,m})\in\Delta$. Precisely, the output is $\hat{\mathbf{x}}-\hat{\mathbf{x}}^{*}$. We call this operator the “MLO with shift $\hat{\mathbf{x}}^{*}$”.

• •

  In Figure 3, the game operator’s input is $\hat{\mathbf{x}}-\hat{\mathbf{x}}^{*}$ instead of $\hat{\mathbf{x}}$, while its output is $-\hat{\mathbf{p}}$ instead of $\hat{\mathbf{p}}$.

By viewing a DGS as a FIC system, we are interested in MLO and game operators which possess good properties like passivity. The key advantage of this approach is it permits a DGS to be decoupled into two distinct operators, which can be analysed separately.

$S_{1}$ is a MLO. First, we show that it is passive if all learning operators possessed by the agents are passive. This allows us to turn our focus to analyzing whether each individual learning operator is passive/lossless or not.

By the next proposition, the choice of shift does not affect passivity of the learning operator. Thus, we say a learning dynamic is passive when its learning operator with any shift is passive.

The above proposition works even when the shifts are not mixed strategies, e.g. when $\mathbf{x}^{*,a}$ is the zero vector. We use $E$ to denote a storage function of a learning operator with zero shift, and $L$ to denote a storage function of a learning operator with a shift of a mixed strategy.

While a shift does not affect passivity, it does affect whether the learning operator is finitely passive or not. In order to prove that certain learning dynamics guarantee constant regret, we need their learning operators with some specific shifts to be finitely passive. This motivates the following definition of finitely passive learning dynamics. Let $\mathbf{e}_{j}$ denote the vector with the $j$-th entry be one, and all other entries be zero.

There are $m$ agents. Each agent $i$ has $n_{i}$ actions. In a graphical game [KLS01], there is a normal-form (matrix) game between every pair of agents, which we call an edge-game. The edge game between agents $i,k$ is specified by two matrices, $\mathbf{A}^{ik}\in\mathbb{R}^{n_{i}\times n_{k}}$ and $\mathbf{A}^{ki}\in\mathbb{R}^{n_{k}\times n_{i}}$. When each agent $k\neq i$ chooses a mixed strategy $\mathbf{x}_{k}\in\Delta^{n_{k}}$, the payoff vector of agent $i$, which contains the payoff to each action of agent $i$, is the sum of the payoff vectors in all her edge-games. Precisely, the payoff vector of agent $i$ is

A graphical constant-sum game [DP09] is a graphical game such that for every pair of agents $\{i,k\}$, there exists a constant $c^{\{i,k\}}$ satisfying $\mathbf{A}^{ik}_{j\ell}+\mathbf{A}^{ki}_{\ell j}=c^{\{i,k\}}$ for any action $j$ of agent $i$ and action $\ell$ of agent $k$.

Recall that a game operator has an input of mixed strategies of different agents with shift $\hat{\mathbf{x}}^{*}$, while the output is the negative of the cumulative payoff vector to different actions. We point out one useful fact, which follows quite readily from [PS14].

When the game is lossless, by the composability of passive operators (Theorem 2), if it is coupled with passive (resp. lossless) learning dynamics, then the DGS is passive (resp. lossless).

In a DGS, $\hat{\mathbf{p}}$ is a function of $\hat{\mathbf{x}}$ via the game operator, while $\hat{\mathbf{x}}$ is a function of $\hat{\mathbf{q}}$ via the conversion function. Thus, $\hat{\mathbf{p}}$ is a function of $\hat{\mathbf{q}}$. We say the ODE system (1) is divergence-free if $\sum_{i=1}^{m}\sum_{j}\frac{\partial p_{ij}}{\partial q_{ij}}$ is zero everywhere. When $\hat{\mathbf{p}}$ is derived using a graphical game via (9), $p_{ij}$ does not depend on $q_{ij}$ since for every $k\neq i$, $\mathbf{x}_{k}$ is a function of $\mathbf{q}_{k}$ only. Thus, the game dynamic is divergence-free.

Intuitively, an ODE system with domain $\mathbb{R}^{N}$ is Poincaré recurrent if almost all trajectories return arbitrarily close to their initial position infinitely often. In order to work formally with the notion of Poincaré recurrence we need to define a measure on $\mathbb{R}^{N}$. We use the standard Lebesgue measure on $\mathbb{R}^{N}$. Liouville’s formula states that divergence-free ODE systems preserve volume [Wei95]; see Appendix A for more discussion of volume and Liouville’s formula. Thus, the following Poincaré Recurrence Theorem is applicable if its bounded-orbit requirement is satisfied.

Given any $\epsilon>0$, we can cover $\mathbb{R}^{n}$ by countably many balls of radius $\epsilon$, and apply the theorem to each ball. We conclude that almost every point returns to within an $\epsilon$ neighbourhood of itself. Since $\epsilon>0$ is arbitrary, we conclude that almost every initial point is almost recurrent.

Recall that in each learning operator of a DGS, the state is represented by a vector $\mathbf{q}\in\mathbb{R}^{n}$, which represents the cumulative payoffs. Clearly, it can be unbounded as time goes even in a graphical constant sum game³³3For instance, this happens for a two-person zero-sum game with every payoff entry to agent 1 is strictly positive., thus prohibiting us to use Theorem 18. Instead, as in [MPP18], we consider a transformation that maps $\mathbf{q}=(q_{1},\ldots,q_{n})$ to

It is well-known that for any FTRL dynamic with starting point $\mathbf{q}^{0}=(q^{0}_{1},\ldots,q^{0}_{n})$ and conversion function $f:\mathbb{R}^{n}\rightarrow\Delta^{n}$, it is equivalent to the following dynamic with state variables $\mathbf{q}^{\prime}=(q_{1}^{\prime},\ldots,q_{n-1}^{\prime})\in\mathbb{R}^{n-1}$, whereas $1\leq j\leq n-1$:

Given a mixed strategy $\mathbf{x}^{*}$, if we cast the output of the above dynamic to be $(x_{1}(t)-x_{1}^{*},\cdots,x_{n-1}(t)-x_{n-1}^{*})$, then it is easy to verify that the learning operator is finitely lossless via the storage function $\overline{L}(q^{\prime}_{1},\ldots,q^{\prime}_{n-1})=L(q^{\prime}_{1},\cdots,q^{\prime}_{n-1},0)$, where $L$ is the storage function of the original learning operator with shift $\mathbf{x}^{*}$.

See Figure 5 for an illumination of Poincaré recurrence under conditions (1) and (2). To prove the theorem, we first show that Poincaré recurrence occurs in the space that contains $\hat{bbq}^{\prime}$ ($\hat{\mathbf{q}}^{\prime}$ is the concatenation of the $\mathbf{q}^{\prime}$ of all agents). This comprises of two major steps:

• •

  The dynamic preserves volume, since the dynamic is divergence-free.

• •

  For any starting point $\hat{\mathbf{q}}^{\prime}(0)$, the dynamic remains bounded. To show this, we use the fact that $\overline{L}$ is a constant-of-motion of the game dynamic, so for any $t\geq 0$, $\hat{\mathbf{q}}^{\prime}(t)$ must stay within a level set of $\overline{L}$, which is bounded (see Appendix C).

Poincaré recurrence in the space that contains $\hat{\mathbf{q}}^{\prime}$ implies Poincaré recurrence in the strategy space $\Delta$, since the conversion function in (10) is continuous.