1 Introduction↩︎

Solving for equilibria has long been one of the core problems in algorithmic game theory. However, an equilibrium may not correspond to a solution that yields a high utility³ for all the players in the game. For example, in the well-known game of Prisoner’s Dilemma (PD), the only Nash equilibrium (NE) is defect-defect, which yields a relatively low utility for both players. Interestingly, however, when it comes to Iterated Prisoner’s Dilemma (IPD) [1], a repeated version of PD, there exists an NE with a much higher utility for both players (cf. Example 1). Therefore, solving for equilibria in repeated games may have advantages over that in one-shot matrix games, in terms of possibly achieving higher utilities.

More importantly, repeated games can also be employed to compute equilibria for one-shot games. In particular, one of the most efficient and scalable approaches for equilibrium computation is through no-regret learning/regret-minimization, which has been both theoretically [2], [3] and empirically [4], [5] supported. It is known that when all players in the game run a no-regret algorithm, their average strategy over time will converge to certain equilibria determined by the regret they minimize. At the heart of these approaches is a proper definition of regret, which by default usually means external regret [6], [7], and measures the difference between the loss incurred by an online decision-maker (or a player in repeated games) and certain comparator decisions that they would have made, knowing the time-varying environments in hindsight.

However, in this classical regret definition, the loss sequences are implicitly assumed to be only functions of timestep [8]. This is general enough and perfectly sensible in the online learning setting, but not in a game-theoretic one, where, by definition, the opponent players should be responsive to the player’s behavior during learning [9]. Hence, the classical regret cannot capture the adaptivity of the opponents, who can make decisions based on the history of the play, and the fact that a player’s action may affect the opponents’ decisions later. Such an inability may lead to sub-optimal equilibrium solutions (e.g., always “defect” for IPD, as in Example 1). In fact, it has been shown that when players are responsive, achieving no-(external-)regret is impossible [9].

To account for the responsiveness and adaptivity of the opponents/adversaries, several new notions of regret have been developed for both online learning and repeated game settings. However, they are either not directly applicable to the repeated-game setting, or computationally intractable. For example, in the online learning setting, [10], [11] introduced the notion of Policy Regret to model environments with memory, in which the loss at round \(t\) may depend on a history of past actions rather than only the current action. Their guarantees typically rely on an \(m\)-bounded-memory assumption, meaning that the loss at time \(t\) depends only on the most recent \(m\) actions. This assumption can be too restrictive in repeated games: a deviation in an early round (e.g., at \(t=1\)) may alter the opponents’ observations later, and thereby change their subsequent play well beyond \(m\) rounds, even when each player uses a finite-memory strategy. In the repeated-game setting, [12] proposed the notion of Response Regret, which considered the mixed strategy space that depends on the whole history of the play, making the minimization of Response Regret convex. However, this is at the cost of exponentially large space in the history length to store the strategies, and thus computationally intractable. Subsequently, [13] extended the Policy Regret notion in [11] to the game setting. However, the comparator in the regret considered there is restricted to constant actions and thus neither adaptive nor dynamic. Moreover, to achieve sublinear policy regret, [13] assumed that the opponents’ strategies are insensitive to recent histories, which further restricted the adaptability and thus the power of opponents. For a more detailed related work discussion, we refer to Appendix 8.

Motivated by these prior studies, our paper focuses on the repeated-game setting, and aims at developing a regret notion that is natural and native to such a setting, while retaining as much generality as possible, e.g., allowing time-varying/dynamic comparator strategies and few constraints on all players’ strategy spaces, while maintaining computational tractability and the possibility of finding better equilibrium solutions by minimizing such a notion. We summarize our contributions as follows.

1.0.0.1 Our Contributions.

Our main contributions are four-fold: (i) For repeated games, we advocate a new and natural notion of Repeated Policy Regret (RP-Regret), as a performance metric that measures the difference between the realized and the best-in-hindsight accumulated utility when all players can respond to the history of play. It allows the opponents to be adaptive, and the comparator strategies to be time-varying, i.e., dynamic; (ii) We prove a series of necessary conditions for obtaining a sublinear RP-Regret, on the variation of the player’s comparator strategies in the regret definition, as well as the memories of both the comparator and the opponents’ strategies (cf. Table 1); (iii) In light of the non-convexity in minimizing RP-Regret, we propose three algorithms: (1) one that is based on a certain optimization oracle, as assumed in some prior work in online non-convex learning; (2) one that minimizes a linearized surrogate of RP-Regret at each timestep, Local Repeated Policy Regret (LRP-Regret), that is convex; (3) one that directly minimizes RP-Regret when the opponents change strategies slowly; (iv) We establish the relationship between the minimization of our regret notions and the computation of certain equilibria of the repeated game. Additionally, we also provide experimental results to demonstrate the advantage of our new regret notions in finding better cooperative solutions with higher utility for the players in games like the Stag-Hunt.

1.0.0.2 Challenges & Our Techniques.

Our notion of RP-Regret is general and particularly devised for the repeated-game setting, but at the cost of having a non-convex objective to minimize due to the memory of players’ strategies. To address the non-convexity issue, we develop several approaches for RP-Regret minimization: (i) we resort to certain non-convex optimization oracles as in [14]; (ii) we linearize the expected loss at each timestep to convexify it; (iii) we lift the variable dimension by reformulating the repeated game as a Markov game, yielding a convex objective in the occupancy measure space for the regret-minimizer. In particular, for (iii) we have developed new techniques to address the following challenges: Firstly, the occupancy measure by nature incorporates the strategies of both the regret-minimizer and the opponents in the game, which does not align with our setting where the opponents are not controlled by the regret-minimizer. Therefore, we need to optimize the occupancy measure while keeping the opponents’ strategies extracted from the occupancy measure close to the actual ones. Due to the online nature of game-playing, we cannot know the opponents’ strategies at timestep \(t\) before we propose the occupancy measure at timestep \(t\). Naively projecting to the occupancy measure space corresponding to the opponents’ strategies at the previous timestep \(t-1\) will cause the error to accumulate and eventually blow up. As a result, we carefully design constraints for the occupancy measure, which can provably keep the first-order difference between the extracted opponents’ strategies and the actual ones bounded, and then resort to the framework of online learning with time-varying constraints to solve it; Secondly, we convert the violation of constraints during online learning to the RP-Regret upper bound; Thirdly, the original constraint on the “forgetfulness” of the behavioral-form strategies is non-convex with respect to the occupancy measure, addressing which requires us to redesign the constraint for the behavioral-form strategies.

1.0.0.3 Motivating Examples.

Now we present two examples to illustrate the advantages of our RP-Regret and LRP-Regret over the classical notion of external regret in playing repeated games. Due to space constraints, Example 2 can be found in §7.

2 Preliminaries↩︎

2.0.0.1 Notation.

We use \(\RR^n\), \(\RR^n_{\geq 0}\), and \(\RR^n_{>0}\) to denote the space of \(n\)-dimensional real vectors, real vectors with non-negative elements, and those with positive elements, respectively. For any integer \(n\), let \([n]\mathrel{\vcenter{:}}=\cbr{1,2,\dots, n}\). For any vector \(\bx\in\RR^n\), we use \(x_i\) to denote the i-th element in \(\bx=(x_1,\cdots,x_n)^\top\) and \(\nbr{\bx}_p\) to denote the p-norm. By default, we use \(\nbr{\bx}\) to denote the \(\ell_2\)-norm of \(\bx\). We define \(\Delta_m \mathrel{\vcenter{:}}= \{\bx\in[0,1]^m:\sum_{i=1}^m x_i=1\}\) as the \((m-1)\)-dimensional probability simplex. For a set \(S\), we will use \(S^n\) to denote the Cartesian product of \(S\) for \(n\) times. For any convex and differentiable function \(\psi^S\colon S\to \RR\), we can define the associated Bregman divergence as \(D_{\psi^S}(\bx,\by)=\psi^S(\bx)-\psi^S(\by)-\inner{\nabla \psi^S(\by)}{\bx-\by}\). When \(D_{\psi^S}(\bx,\by)\geq \frac{k}{2}\nbr{\bx-\by}^2\), we will call \(\psi^S\) \(k\)-strongly convex. For any vector \(\bx\) and positive integers \(i<j\), we will use \(\bx_{i:j}\) to denote the slicing \((x_i,x_{i+1},...,x_{j-1},x_j)\) of \(\bx\). For any finite set \(S\), we will use \(|S|\) to denote its cardinality. We use \(\emptyset\) to denote an empty set, and use \(\NN\) and \(\NN_{>0}\) to denote the set of non-negative and positive integers, respectively. For any argument, \(\ind(\text{argument})=1\) when the argument holds, and equals \(\ind(\text{argument})=0\) otherwise. For any two integers \(a\in\NN,b\in\NN_{>0}\), we use \(a\% b\) to denote the remainder of \(a\) divided by \(b\).

2.0.0.2 Repeated (Matrix) Games.

Let \(\cN=\{1,2,...,N\}\) denote the set of all players with \(N\geq 2\). Then, we use \(\cA_i\) to denote the action set of player \(i\in \cN\), and \(\cA\) to denote the joint action set of all players, i.e., \(\cA=\prod_{i=1}^N \cA_i\). For any joint action \(\ba\in\cA\), we also call it an action profile. We use \(\cA_{-i}\) to denote the joint action set of all the players except player \(i\). The game is repeated across timesteps \(t\geq 1\). At every timestep \(t\), each player \(i\) chooses an action \(a_{t,i}\in\cA_i\) individually, and incurs a loss⁴ \(\cL_i(\ba_t)\in[0,1]\), where \(\ba_t=(a_{t,1},a_{t,2},...,a_{t,N})\). Note that \(\{\cL_i\}_{i\in\cN}\) is referred to as the set of loss matrices (which explains the name of repeated matrix games) when \(N=2\), and as the set of loss tensors in general when \(N>2\).

2.0.0.3 History and Strategy.

Throughout the paper, we use \(\bh\) to denote a vector of history actions, of which every element is a joint action of the \(N\) players. We may also refer to \(\bh\) as history for short. We use \(L(\bh)\) to denote the length of \(\bh\), and \(\bh_k=(a_{k,1},a_{k,2},...,a_{k,N})\in\cA\) to denote the \(k^{\rm th}\) element of \(\bh\). Note that \(k\in\cbr{1,2,...,L(\bh)}\). Moreover, we use \(\bh_{s:k}=(\bh_s,\bh_{s+1},...,\bh_k)\) to denote the slice of \(\bh\) for \(s\leq k\), which is \(\emptyset\) if \(s>k\). For notational convenience, we use \((\bh,\ba)\) or \((\bh,\bh')\) to denote the concatenation of a vector and an action profile/a vector. We use \(\cH_m\mathrel{\vcenter{:}}= \cbr{\bh=(\bh_1,\bh_2,...,\bh_m)\mid \forall k=1,2,...,m, \bh_k\in\cA}\) to denote the set of all histories of length \(m\). For convenience, we define \(\cH \mathrel{\vcenter{:}}= \bigcup_{i=0}^\infty \cH_i\), where \(\cH_0=\cbr{\emptyset}\) contains the unique history \(\bh=\emptyset\) with length \(L(\bh)=0\).

We use \(\bpi\ui\colon \cH\to \Delta_{|\cA_i|}\) to denote the (history-dependent) strategy of player \(i\). \(\pi\ui(a_i\given \bh)\) is the probability of choosing action \(a_i\in\cA_i\) conditioned on observing the history \(\bh\). Let \(\cX\ui \mathrel{\vcenter{:}}= \cbr{\bpi\ui\given \bpi\ui\colon \cH\to \Delta_{|\cA_i|}}\) be the space \(\bpi\ui\) lies in and \(\cX\mathrel{\vcenter{:}}= \cbr{\bpi\given \bpi\colon \cH\to \Delta_{|\cA|}}\) be the space of the joint strategy profile \(\bpi\) lies in. Unless we specify \(\bpi\) to be a correlated strategy explicitly, we use the notation of \(\pi(\ba\given\bh)\) to denote \(\pi(\ba\given\bh)=\prod_{i=1}^N \pi\ui(a_i\given\bh)\), i.e., as a product strategy. For convenience, we also use \(\bpi^{(-i)}\) to denote the strategy profile of all players except player \(i\), i.e., \(\pi\uni(\ba_{-i}\given\bh)=\prod_{j\not=i}\pi^{(j)}(a_j\given\bh)\). In repeated games, at each timestep \(t\), based on some history \(\bh\), each player \(i\) will draw their action \(a_{t,i}\) from their strategy at timestep \(t\), denoted as \(\bpi\ui_t\), i.e., sampling from \(\pi_t\ui(\cdot\given\bh)\). Note that \(\bh\) here could be either the full history from time \(1\) to \(t-1\), or some truncated portion of it. Lastly, we define \(\nbr{\bpi\ui}_p \mathrel{\vcenter{:}}= \rbr{\sum_{a_i\in\cA_i,\bh\in\cH} \abr{\pi\ui(a_i\given \bh)}^p}^{1/p}\).

2.0.0.4 Expected Loss in Repeated Games.

Firstly, for any history \(\bh\in\cH\) and a vector of strategies \(\bpi_{1:L(\bh)}\) of length \(L(\bh)\), we define \(\Pr(\bh\given \bh';\bpi_{1:L(\bh)}) \mathrel{\vcenter{:}}= \prod_{s=1}^{L(\bh)}\prod_{i=1}^N \pi_s\ui(h_{s,i}\given (\bh',\bh_{1:s-1}))\) as the probability that \(\bh\) occurs when all players observe \(\bh'\in\cH\) initially, and sample action profile \(\bh_k\in\cA\) according to \(\bpi_k\) for \(k\in\cbr{1,2,...,L(\bh)}\). For simplicity, we define \(\Pr(\bh;\bpi_{1:L}) \mathrel{\vcenter{:}}= \Pr(\bh\given \emptyset;\bpi_{1:L})\) for \(\bpi_{1:L}\) of any length \(L>0\). Then, we can define the expected loss of player \(i\) when all the players follow a sequence of strategies in \(\bpi_{1:m+1}\) for \(m+1\) steps, and when observing some \(\bh'\in\cH\) initially, as \(f_i^m(\bpi_{1:m+1}\given \bh')\mathrel{\vcenter{:}}= \sum_{\ba\in \cA} \cL_i(\ba)\sum_{\bh\in\cH_m} \Pr((\bh,\ba)\given \bh';\bpi_{1:m+1})\). Note that the input sequence of the strategy profiles \(\bpi_{1:m+1}\) in \(f_i^m(\bpi_{1:m+1}\given \bh')\) always has the length of \(m+1\), the same as the length of \((\bh, \ba)\), where \(m=L(\bh)\). When \(\bh=\emptyset\), we define \(m=L(\bh)=0\). Additionally, we define \(f_i^m(\bpi_{1:m+1}) \mathrel{\vcenter{:}}= f_i^m(\bpi_{1:m+1}\given \emptyset)\) for simplicity. Finally, we may denote \(\bpi_{1:m+1}\) simply as \(\bpi\) when the subscript is clear from the context. Unlike one-shot normal-form games, the expected loss in repeated games is non-convex with respect to the strategies \(\bpi_{1:m+1}\). Therefore, to optimize the expected loss, we need to either assume a non-convex optimization oracle (13), or linearize and thus convexify the function (4.1), or lift the dimension of the variables (4.2).

3 A New Metric: Repeated Policy Regret (RP-Regret)↩︎

3.1 RP-Regret Definition↩︎

We consider the case in repeated games where the opponents are adaptive, i.e., they can make decisions by responding to histories of play. The player is also aware that their deviations in action could trigger responses from the opponents. To handle this setting, we advocate a new metric of Repeated Policy Regret (RP-Regret) in repeated games. Without loss of generality, we will consider the player of interest as player 1, and we refer to all other players as the opponents, as the definition of RP-Regret applies to all players. Specifically, for player 1, we first define the accumulated expected loss \(J_T(\bpi_{1:T})\) of the joint strategy \(\bpi_{1:T}\) when playing \(T\) rounds of the game: \[\begin{align} \label{equ:def95J95f} &J_T(\bpi_{1:T}) := \sum_{t=1}^T f^{t-1}(\bpi_{1:t}), \end{align}\tag{1}\]

where, for notational simplicity, we omit the subscript \(1\) of \(f_1^m(\bpi_{1:m+1})\). Therefore, an intuitive measure of performance would be comparing \(J_T(\bpi_{1:T})\) with the best-response expected loss of \(\min_{\hat{\bpi}\uo_{1:T}\in(\cX\uo)^T} J_T((\hat{\bpi}\uo_{1:T}, \bpi^{(-1)}_{1:T}))\), where we recall that \(\cX\ui\) is the space in which the strategy of player \(i\) lies. In the following, we refer to \(\hat{\bpi}\uo_{1:T}\) as the comparator. Then, we can define the RP-Regret as \[\begin{align} &R_T:= J_T(\bpi_{1:T})-\min_{\hat{\bpi}\uo_{1:T}\in \cC_T\uo} J_T((\hat{\bpi}\uo_{1:T}, \bpi^{(-1)}_{1:T}))\label{eq:RP-Regret-def} \end{align}\tag{2}\]

where \(T\in\NN_{>0}\) and \(\cC_T\ui\subseteq (\cX\ui)^T\) is the space that the comparator \(\hat{\bpi}_{1:T}\ui\) of player \(i\) lies in, subject to some constraints (to be specified later) that make \(\cC_T\ui\) potentially smaller than \((\cX\ui)^T\), and thus lead to a weaker comparator for potentially better tractability, as we shall see later.

RP-Regret captures how much better we could have done if we had chosen \(\hat{\bpi}_{1:T}\uo\) when all players are adaptive (i.e., they are aware of the history). In contrast to external regret, the deviation to the comparator strategy \(\hat{\bpi}_t\uo\) at timestep \(t\) will not only affect the expected loss at timestep \(t\) but also all expected losses afterward. This is because the distribution over histories has changed, and the adaptive opponents may change their strategies correspondingly. RP-Regret coincides with the adaptive regret⁵ defined in [18], when the strategies \(\bpi_t\uo\) for all \(t\) have no restrictions on the memory used, i.e., can react arbitrarily differently when observing different histories. However, the regret is linear in the worst case, as shown in Lemma 3 and Lemma 4 (related but different hardness results also appeared in [9], [18]). Therefore, we will set additional restrictions on the memory, so that players should behave similarly when observing similar histories (to be discussed in detail in §3.2). In this case, RP-Regret differs from the adaptive regret defined in [18], where the strategies of all players may now change over time.

More relatedly, the policy regret in [13] restricts the comparator \(\hat{\bpi}_{1:T}\uo\) to be a fixed action across all timesteps as in external regret. Moreover, for some \(m>0\) and any history \(\bh\in\cH,\tilde{\bh},\bar{\bh}\in\cH_m\), they assume \(\sum_{t=m}^T \nbr{\pi_t\uno(\cdot| (\bh, \tilde{\bh})) - \pi_t\uno(\cdot| (\bh, \bar{\bh}))}\) is sublinear in \(T\). In other words, the opponents’ strategies do not depend on recent history. This assumption further restricts the adaptability and thus the power of the opponents, limiting its applicability in repeated game playing, the focus of our paper.

3.2 When is Minimizing RP-Regret Possible?↩︎

Being fairly natural and native to repeated game playing, the notion of RP-Regret can be hard to minimize. To understand its fundamental limits, we first identify two basic conditions that can be proved necessary for achieving a RP-Regret sublinear in \(T\). The first one is a variation condition, which restricts the comparator’s strategy from changing too fast across different timesteps. The second one concerns the imperfect memories of all the players and the comparator.

Condition [assumption:1-variation] on the comparator is a common assumption in the literature of dynamic regret minimization [19]–[22], which restricts the power of the comparator in order to achieve sublinear dynamic regret. Note that the well-known external regret also implicitly adopts such a condition with the variation of the comparator being zero.

As a surrogate to quantitatively characterize Condition [assumption:imperfect-memory], we propose Condition [assumption:2-forgetful] below, which instantiates the “imperfect” recall as having finite-memory with an exponential decay property.

Condition [assumption:2-forgetful] quantitatively bounds how sensitive the strategy is to the distant past: once the most recent suffix \(\bh\) is fixed, changing the earlier prefix from \(\tilde{\bh}\) to \(\bar\bh\) can only change each conditional action probability by a multiplicative factor that approaches \(1\) at an exponential rate in the length of \(\bh\), as denoted by \(L\rbr{\bh}\). Thus, for any target accuracy \(\epsilon>0\), it suffices to retain a suffix of length \(L=O\rbr{\log\rbr{1/\epsilon}}\) to make the effect of earlier history negligible. We adopt exponential (rather than polynomial) decay precisely to ensure that this effective memory length grows only logarithmically with \(1/\epsilon\), which ensures efficient computation. This assumption is satisfied by several regularized mirror-descent-type updates, see, e.g., [23]–[25].

An alternative to quantify imperfect recall is via bounded memory [26], where strategies depend only on the last \(m\) rounds for a fixed constant \(m\). However, bounded dependence on the last \(m\) observations does not prevent a player from using its actions as an information carrier: by choosing actions according to a protocol, the player can encode information about earlier events into the recent suffix that future decisions can still access. As shown in the proof of Lemma 2, this phenomenon can preclude sublinear regret even when \(m=1\). Condition [assumption:2-forgetful] rules out such near-perfect “state passing” by forcing policies that share the same recent suffix to be nearly indistinguishable regardless of the earlier prefix, with the indistinguishability improving exponentially in the suffix length.

We summarize the hardness results in Table 1 and postpone the full statements to Appendix 10. Although in Table 1 we only state the necessity of Condition [assumption:imperfect-memory], Condition [assumption:2-forgetful] is “almost necessary”, as the difference between these two conditions only originates from those imperfect recall strategies with the choice of \(\gamma=1\) in Condition [assumption:2-forgetful] (following the convention that \({1}/{0}=+\infty\)). Given the results above, we now focus on minimizing the RP-Regret by assuming the necessary conditions summarized in Table 1 throughout, unless otherwise noted.

4 RP-Regret Minimization↩︎

As mentioned before, unlike the traditional framework of online convex optimization with memory [10], [27], which exclusively focuses on handling convex loss functions, our loss is non-convex with respect to the input argument due to the product of strategies in consecutive timesteps. Hence, it is hard to minimize RP-Regret directly due to the non-convexity. We now propose three different ways to minimize RP-Regret as follows:

• Minimizing RP-Regret directly with an oracle that can optimize a non-convex function, where we only need the necessary conditions in Table 1, except that we use [assumption:2-forgetful] instead of [assumption:imperfect-memory]. This setting with a non-convex optimization oracle, though it may be computationally intractable, can still provide some insights into the players’ learning process, and has also been adopted in the literature [14]. This part is presented in detail in Appendix 13.

• Minimizing a surrogate notion of RP-Regret, i.e., Local RP-Regret (LRP-Regret), by convexifying the RP-Regret locally around the implemented strategies during regret minimization, which will be discussed in §4.1.

• Reformulating the problem as a Markov game [28], [29] under certain reparameterization, with an additional requirement that Condition [assumption:1-variation] holds also for the opponent (not only for the comparator, as a necessary condition by Lemma 2). This part will be introduced in §4.2.

The first bullet justifies that Condition [assumption:1-variation] on the comparator and Condition [assumption:2-forgetful] on both the comparator and the opponents are sufficient to achieve sublinear RP-Regret, when one leverages a non-convex optimization oracle, as in online non-convex learning [14]. This sufficiency result mirrors the necessity of these conditions (and their variants) in §3.2. Hereafter, we will focus on introducing the other two approaches above that account for computational efficiency.

4.1 Minimizing a Surrogate: Local Repeated Policy Regret↩︎

Motivated by the one-step deviation principle [30], which means that the strategy profile of a repeated game is a subgame perfect Nash equilibrium (SPNE) if and only if no player can decrease their expected loss by deviating from their original strategy via only a single action at one round of the game, we propose the notion of Local Repeated Policy Regret (LRP-Regret). Specifically, instead of computing the regret by globally deviating from the strategy \(\bpi\uo_{1:T}\) to \(\hat{\bpi}\uo_{1:T}\), we compute the regret when the player only locally deviates from \(\bpi\uo_{1:T}\) at one timestep, which is formally given by \[\begin{align} \label{eq:local-RP-Regret-def} R_T^{\rm local} \mathrel{\vcenter{:}}= \max_{\hat{\bpi}\uo_{1:T}\in\cC_T\uo} \sum_{s=1}^T \big(J_T(\bpi_{1:T})-J_T(\tilde{\bpi}^{(1),s}_{1:T}, \bpi^{(-1)}_{1:T})\big),\quad \text{where~~}\tilde{\bpi}^{(1),s}_t=\begin{cases} \hat{\bpi}\uo_t&t=s\\ \bpi\uo_t&t\not=s, \end{cases} \end{align}\tag{4}\] and \(\cC_T\uo\subseteq\rbr{\cX\uo_\gamma}^T\) is the space of the comparator \(\hat{\bpi}_{1:T}\uo\), which satisfies Condition [assumption:1-variation] and Condition [assumption:2-forgetful] with \(\gamma\leq \frac{1}{2(N+2)}\). \(\lim_{T\to\infty} \frac{R_T^{\rm local}}{T}=0\) implies that when player 1 deviates to \(\hat{\bpi}_{1:T}\uo\) at only one timestep \(t\in\cbr{1,2,...,T}\), the accumulated loss \(J_T\) upon averaging over all timesteps will not decrease.

Interestingly, one can verify that Lemmas 2, 3, and 4 still hold for this weaker regret notion, which implies that the necessary conditions in Table 1 are still necessary for LRP-Regret minimization. We defer the formal results and proofs to Appendix 14.1.

For the LRP-Regret given in 4 , it is easy to verify that the expected loss at timestep \(t\), \(f_t^{m,{\rm local}}\colon \Delta_{|\cH_m|\times |\cA_1|}\to \RR\), can be written as \[\begin{align} f_t^{m,{\rm local}}(\bar \bpi\uo_{1:t}) \mathrel{\vcenter{:}}= (T-m-1) f^m(\bpi\uo_{t-m:t},\bpi\uno_{t-m:t})+\sum_{s=t-m}^t f^m((\bpi\uo_{t-m:s-1}, \bar\bpi\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t}).\label{eq:local-loss-def} \end{align}\tag{5}\] Moreover, for an arbitrary strategy vector \(\bar\bpi\uo_{1:T}\) of length \(T\), the corresponding expected loss at timestep \(t\), \(f_t^{t-1,{\rm local}}(\bar \bpi\uo_{1:t})\), is linear with respect to \(\bar\bpi_t\uo\). Therefore, one may update the strategy using the simple projected gradient descent (PGD) algorithm as: \[\begin{align} \pi_{t+1}\uo=\Proj{\cX\uo_{\gamma}}{\pi_t\uo - \eta\nabla f_t^{m,{\rm local}}(\bpi\uo_{1:t})},\label{eq:PGD-def} \end{align}\tag{6}\] where \(\eta>0\) is the learning rate.

The proof is postponed to Appendix 14.2. In 1, the \(\tilde{O}\) notation hides factors polynomial in \(m\) (and logarithmic in \(T\)). The exponential dependence on \(|\cA|^{m+1}\) stems from maintaining an \(\rbr{m+1}\)-step history. Consequently, if the comparator variation \(P_T\) is sublinear in \(T\), for any \(\epsilon>0\), \(\frac{R_T^{\rm local}}{T} \leq\epsilon\) when \(m=\Theta(\log\frac{1}{\epsilon})\).

4.2 Minimizing RP-Regret with Slowly-Changing Opponents↩︎

We also propose another approach that can directly minimize the original RP-Regret 2 , under the additional condition that the opponent changes their strategies slowly, i.e., Condition [assumption:1-variation] also holds for the opponents’ strategies.

4.2.1 Reformulating Repeated Games with Bounded Memory as Markov Games↩︎

We will show that the expected loss at each timestep can be approximated by the expected loss of an infinite-horizon average-loss Markov/stochastic game [28], [29], [31], and develop a regret minimization algorithm based on this reformulation.

Naively, one can use the whole history as the state of the Markov game. However, the state space will increase exponentially as the timestep increases. Hence, we will consider the case where all the players have an \(M\)-bounded memory with some fixed \(M\), such that they only make decisions conditioned on the history of length \(M\). In Lemma 27, we will show that under Condition [assumption:2-forgetful], we can convert the unbounded memory of all players to \(M\)-bounded memory, with a small approximation error. Particularly, for all players \(i\in\cN\), we can convert a strategy \(\pi\ui\) with unbounded memory to a strategy \(\overbar\pi\ui\) with \(M\)-bounded memory by letting \[\begin{align} &\forall a_i\in\cA_i,\bh\in\cH,~~~~~\overbar\pi\ui(a_i\given\bh)=\begin{cases} \pi\ui(a_i\given\bh_{L(\bh)-M+1:L(\bh)})&L(\bh)\geq M\\ \frac{1}{|\cH_{M-L(\bh)}|} \sum_{\bh'\in\cH_{M-L(\bh)}}\pi\ui(a_i\given (\bh',\bh))&L(\bh)<M. \end{cases} \end{align}\] In the remainder of this section, we will only focus on strategies with \(M\)-bounded memory.

By definition, the expected time-average loss of the Markov Game in Definition 1⁶ is equivalent to the expected average loss of the infinitely repeated matrix game when the joint (Markov) strategy \(\bpi\) is the same at each timestep: in particular, for player \(1\) \[\begin{align} \lim_{T\to\infty}\EE_{\bh_{t+1}\sim \Pr(\cdot\given\bh_{t},\ba_t),\ba_t\sim\bpi(\cdot\given \bh_{t})}\sbr{\frac{1}{T}\sum_{t=0}^{T-1} \cL_1(\bh_{t},\ba_t)} = \lim_{T\to\infty} \frac{1}{T}\sum_{t=0}^{T-1} f^t(\underbrace{(\bpi,...,\bpi)}_{t+1})\eqqcolon f^\infty(\bpi),\label{eq:f-infty-def} \end{align}\tag{7}\] where \(\bh_{t}\in\cH_M\) denotes the state at timestep \(t\).

4.2.2 Occupancy-Measure-based Regret Minimization in the Markov Game↩︎

The key challenge in learning in the induced Markov game is the non-convexity of the expected time-average loss with respect to the (stationary) strategy \(\bpi\). To convexify the problem, we propose to change the variable from the strategy to the occupancy measure of the MG. Thus, instead of updating the strategy \(\pi_t^{\uo}\), we will update the occupancy measure \(\bq_t\) at each timestep \(t\).

For an infinite-horizon MG, its expected loss can be represented as a linear function with respect to the occupancy measure [32]. Formally, for any history \(\bh\in\cH_M\) and joint action \(\ba\in\cA\), the occupancy measure \(\bq^{\pi}\) that corresponds to joint strategy \(\pi\) can be written as \[\begin{align} q^{\bpi}(\bh,\ba) \mathrel{\vcenter{:}}= \EE_{\bh_0\sim\mu_0,\bpi}\left[\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\ind(\bh_t=\bh)\right]\cdot \pi(\ba\given \bh)\label{eq:def-occupancy-measure} \end{align}\tag{8}\] where \(\mu_0\) is the initial distribution over \(\cS=\cH_M\)⁷. Moreover, it is known that the joint strategy can be recovered as \(\pi(\ba\given\bh)=\frac{q^{\bpi}(\bh,\ba)}{\sum_{\ba'\in\cA} q^{\bpi}(\bh,\ba')}\), and there is a correspondence between \(\bpi\) and \(\bq^{\pi}\) [32]. We highlight that in the regret-minimization procedure concerned in this subsection, only the strategy \(\bpi_t\uo\) of player \(1\) is controlled by the (regret minimization) algorithm, which is determined by the occupancy measure, \(\bq_t\), at timestep \(t\) proposed by the algorithm. All other players are adaptive opponents. Hence, we define the strategy of player 1 at timestep \(t\) as \(\pi_t\uo(a_1\given \bh)\mathrel{\vcenter{:}}= \frac{\sum_{\ba_{-1}'\in\cA_{-1}} q_t(\bh,(a_1,\ba_{-1}'))}{\sum_{\ba'\in\cA} q_t(\bh,\ba')}\) for any \(\bh\in \cH_M\) and \(a_1\in\cA_1\), where \(\bq_t\) is controlled by the regret minimizer.

To ensure that \(\frac{q_t(\bh,\ba)}{\sum_{\ba'\in\cA} q_t(\bh,\ba')}\) can always be represented as \(\pi_t\uo(a_1\given\bh)\prod_{i=2}^N \pi_t\ui(a_i\given\bh)\) for all \(\bh\in\cH_M,\ba\in\cA\), we additionally need the following constraints on \(\bq_t\) at timestep \(t\), as characterized by a constraint function \(g_t\colon \RR^{|\cH_M|\times |\cA|}\to \RR\) defined below: for any \(\bq\in \RR^{|\cH_M|\times |\cA|}\), \[\begin{align} &g_t(\bq) \mathrel{\vcenter{:}}= \sum_{\bh\in\cH_M,\ba\in\cA} (-1)^{\ind(D_t(\bh,\ba,\bq_t)\leq 0)}D_t(\bh,\ba,\bq)\leq 0,\label{eq:def-constraint-no-timestep}\\ &\text{where~~~~}D_t(\bh,\ba,\bq)\mathrel{\vcenter{:}}= q(\bh,\ba)-\pi_t^{(-1)}(\ba_{-1}\given \bh)\sum_{\ba_{-1}'\in\cA_{-1}} q(\bh,(a_1,\ba_{-1}')).\notag \end{align}\tag{9}\]

It is straightforward to see that \(g_t(\bq_t)\leq 0\), with equality if and only if \(\frac{q_t(\bh,\ba)}{\sum_{\ba'\in\cA} q_t(\bh,\ba')}=\pi_t\uo(a_1\given\bh)\prod_{i=2}^N \pi_t\ui(a_i\given\bh)\). Note that the constraint at timestep \(t\), \(D_t(\bh,\ba,\bq^{\pi})\), is a linear constraint on \(\bq^{\pi}\) determined after \(\bq_t\) is proposed, which falls into the realm of online convex optimization with time-varying constraints [33]–[35], and it will be the core of our algorithm. Compared to simply letting \(g_t(\bq) = \sum_{\bh\in\cH_M,\ba\in\cA} \abr{D_t(\bh,\ba,\bq)}{\leq 0}\), our novel constraints in 9 can avoid the non-differentiable issue of the absolute value function at zero.

4.2.3 Convexifying Condition [assumption:2-forgetful] and the Overall Algorithm↩︎

The Markov game reformulation in §4.2.1 provides an alternative way to approximate the expected loss under Conditions [assumption:1-variation] and [assumption:2-forgetful]. However, the forgetful constraint in Condition [assumption:2-forgetful] becomes non-convex with respect to the occupancy measure. Therefore, instead of enforcing Condition [assumption:2-forgetful], we propose to enforce the following weaker constraint, which is convex with respect to the occupancy measure and can be guaranteed when Condition [assumption:2-forgetful] is satisfied.

It is straightforward to see that when Condition [assumption:2-forgetful] is satisfied, for every action \(a_i\in\cA_i\), we must have either \(\pi\ui(a_i\given \bh)>0\) for all \(\bh\in\cH\) or equal to \(0\) for all \(\bh\in\cH\). Then, Condition [assumption:2-forgetful-prime] is satisfied since the \(\bnu\ui\) in the condition always exists (note that the \(\gamma\) in Condition [assumption:2-forgetful] and Condition [assumption:2-forgetful-prime] are different). In the following lemma, whose proof is deferred to Appendix 19.3, we show that the unary expected loss \(f^K(\underbrace{(\bpi,...,\bpi)}_{K+1})\) can be further approximated by the average loss of the induced Markov game given by Definition 1. Therefore, we will solve the Markov game instead.

For any initial distribution, the expected loss after \(K+1\) rounds equals that after infinite rounds, up to an exponentially decreasing error. Moreover, the expected loss after infinite rounds is irrelevant to the initial distribution, which implies that the dependence on history is exponentially decaying.

We are now ready to introduce our algorithm, which is essentially online convex optimization over time-varying constraints (as depicted by 9 ), as tabulated in 3.

4.2.4 Theoretical Guarantees↩︎

We show next that 3 achieves a sublinear RP-Regret and a sublinear accumulated constraint violation \(\sum_{t=1}^T g_t(\bq_t)\). A detailed version of the theorem and its proof are in Appendix 15.2.

Note that to find a \(T\) as a polynomial in \(\frac{1}{\epsilon}\) and satisfy \(T\geq \Omega(\frac{\Delta_T}{\epsilon^4})\) simultaneously, \(\Delta_T\) needs to be sublinear in \(T\). [assumption:2-forgetful-prime] is a linear constraint on the occupancy measure, which can be implemented efficiently in our algorithm by projection.

5 Equilibrium Computation via RP-Regret Minimization↩︎

In this section, we investigate one important implication of our new regret notion – equilibrium computation, in repeated games. We will focus on the infinitely repeated game setting, instead of the finitely repeated one. This is because, for a one-shot matrix game, when its NE is unique, the only subgame perfect Nash equilibrium of its finitely repeated version is playing the NE of the one-shot game at every timestep [36]. Therefore, solving the NE of the finitely repeated game degenerates to solving the NE of the one-shot matrix game. On the other hand, the uniqueness of NE for a one-shot matrix game is not uncommon — for two-player zero-sum matrix games, the set of games with non-unique NEs has Lebesgue measure zero [37], [38]. Hence, we will hereafter direct our attention to the infinitely repeated general-sum game setting.

5.1 Equilibria in Repeated Games↩︎

In light of our RP-Regret definition, we first introduce the following notions of (subgame perfect) equilibria in infinitely repeated games. We start with the coarse correlated equilibrium.

Compared to standard subgame-perfect Nash equilibrium (SPNE), SPCCE admits correlated strategies. Moreover, SPNE (SPCCE) can be viewed as SPNE (SPCCE) with \(\Theta(T)\)-bounded deviation, since there is no restriction on the comparator.

Similarly, we can define the corresponding Nash equilibrium when the joint strategy \(\bpi_{1:\infty}\) is a product strategy conditioned on each history.

5.2 Relationship between RP-Regret and Equilibria↩︎

We now discuss the relationship between RP-Regret and the aforementioned equilibrium notions.

The proof of 3 is postponed to Appendix 16.2. This theorem builds up the relationship between approximate robust SPNE (and thus SPCCE) and RP-Regret minimization. When all the players can obtain a sublinear RP-Regret against their comparators whose accumulated variations are bounded by \(P_{T_0}\), then we can build an approximate SPNE with \(P_T\)-bounded deviation.

We defer the proof of the theorem to Appendix 16.1. This theorem establishes the connection between equilibrium in repeated games and LRP-Regret. When all the players are running no-LRP-regret learning and achieve sublinear LRP-Regret, we can obtain an approximate SPNE. Compared to 3, 4 only holds when sublinear regret is obtained with respect to the comparator without variation budget (\(P_T=\Theta(T)\)).

We note that 4 only states the relationship between approximate \(O(T)\)-robust SPNE and LRP-Regret minimization, but does not provide an algorithm to achieve so. Indeed, directly running our regret minimization algorithm for LRP-Regret (§4.1) may not achieve the equilibrium, since it requires the variation of the comparator \(P_{T_0}\) to be sublinear in \(T_0\). We defer the development of such no-LRP-Regret algorithms as an immediate future work.

5.3 Computing the Equilibria↩︎

We now propose an algorithm to find an approximate SPCCE with \(O(T)\)-bounded deviation of infinitely repeated matrix games. The algorithm is proposed in 4. Guarantee of the algorithm is provided below.

The proof is deferred to 17.1. The proof relies on modeling the repeated game as a Markov game as in §4.2.1, and then resorting to the existing result about solving CCE in Markov games [39]–[42].

6 Conclusion↩︎

In this paper, we studied regret-minimization in repeated games with adaptive opponents who can respond based on the histories of play. To this end, we advocated a new metric, RP-Regret, which is native to this setting, and identified a series of necessary conditions for obtaining RP-Regret sublinear in time. We then developed additional conditions and provable algorithms to minimize RP-Regret, followed by the connection of RP-Regret minimization to certain known sub-game perfect equilibria computation. Our work opens new directions for future research, including the development of weaker equilibrium notions induced by RP-Regret minimization in §4, for which weaker assumptions may be required to compute. It also raises the possibility of obtaining provable equilibrium-selection results via RP-Regret minimization in games with particular payoff structures.

Acknowledgement↩︎

M.L. was supported by the MathWorks Fellowship. A.O. was supported in part by the ONR grant N000142512296. K.Z. acknowledges the support from the Army Research Office (ARO) grant W911NF-24-1-0085, the NSF CAREER Award 2443704, the AFOSR YIP Award FA9550-25-1-0258, a Cisco Faculty Research Award, and a JP Morgan Faculty Research Award.

 

Supplementary Materials for

“Regret Minimization with Adaptive Opponents in Repeated Games”

7 Motivating Example Details↩︎

8 Detailed Related Work↩︎

8.0.0.1 Equilibrium Computation in Repeated Games.

Learning and equilibrium computation in repeated normal-form games is a well-studied area. One well-known folklore result is that when all the players run no-(external-)regret learning algorithms, the average iterates will converge to the coarse correlated equilibrium of the one-shot matrix game [2]. In playing repeated games, since the players could change their strategies based on past observations, the equilibrium for the repeated game can be different from that of the one-shot game. In this regard, using the well-known folk theorem⁹ [43], [44], one can find the NE in infinitely repeated matrix games. [45] gave a polynomial-time algorithm based on the folk theorem to compute the NE of an infinitely repeated two-player general-sum game, which is known to be PPAD-hard for the one-shot case [46], [47]. However, [48] showed that finding the minimax value is NP-hard in general-sum games with 3 or more players, which prevented the technique in [45] from being extended to the multi-player cases.

8.0.0.2 Impossibility Results.

[48] proved that computing an NE for an \(N\)-player infinitely repeated game with discount factors is as hard as computing an NE of an \((N-1)\)-player one-shot game. By [46], [47], [49], computing an NE of a 2-player general-sum one-shot game is PPAD-hard and thus computing an NE of a 3-player infinitely repeated game with discount factor is also PPAD-hard. The result does not conflict with this paper since in §5.3, we are computing a coarse correlated equilibrium (CCE) instead of an NE of the repeated game. Also, our result implies that directly minimizing RP-Regret without further assumptions may not be computationally tractable. Otherwise, if each player achieves a sublinear RP-Regret, by 3, the trajectory converges to a subgame perfect NE of an infinitely repeated game without discount factor. [9], [18] gave impossibility results on minimizing regret in repeated games when the regret minimizer cannot observe the full strategy of the opponent. Therefore, to the best of our knowledge, it is still unclear under which conditions we can minimize regret, when the other players deviate themselves as a reaction to the deviation of one player, the setting our work focuses on.

8.0.0.3 Rationalizing Cooperation.

Our study is also motivated by those of rationalizing cooperation in Iterated Prisoner’s Dilemma with bounded rationality and strategy complexity [1], [50]–[52]. These papers investigated the Nash equilibrium of the (finitely) repeated game when the strategies are modeled as an automaton with finite states, and showed the existence of equilibrium with payoff close to the cooperative outcome. In this paper, we show, in contrast, that when players have unlimited memory power (automata with infinite states), our regret notion of RP-Regret cannot be minimized.

8.0.0.4 Opponent Shaping and Modeling.

Our work also takes significant inspiration from the recent empirical literature of opponent shaping in multi-agent (reinforcement) learning [53]–[56], which developed algorithms to shape the opponents’ future strategies, knowing that they will adapt to the actions of the learning agent/player. However, most of the algorithms do not enjoy theoretical guarantees, e.g., on the convergence, and/or on the quality of the strategies they converge to. [57] proved that their algorithm called Stable Opponent Shaping will converge. However, the guarantee only applies when assuming the opponents are naive learners¹⁰, and there is no guarantee on the performance against general unknown opponents. By contrast, our method, through the lens of regret-minimization, is more general and robust against any possible players/opponents satisfying some provably necessary conditions (see §3.2).

8.0.0.5 Online Learning.

Our work is closely related to the problem of online convex optimization with memory, which was first studied in [10] and later generalized to developing the concept of Policy Regret and studied in [11], [27]. Recently, [22] showed how to achieve sublinear policy regret when the comparator is allowed to choose a time-varying strategy with a sublinear variation budget. One of the applications of OCO with memory is [58], which discussed how to fit the online control problem into the framework of OCO with memory. However, existing analyses along these lines typically either assume that the loss function is convex or impose an \(m\)-bounded-memory condition on the loss, namely that the loss at timestep \(t\) depends only on the recent action window \(\sbr{\ba_{t-m},\dots,\ba_t}\). In contrast, in repeated games the expected per-round loss induced by strategic interaction need not be convex in the player’s decision variables, and it can depend on the entire history. [59] considered regret minimization in bounded-memory games. However, the \(k\)-adaptive regret considered in [59] will restart the game every \(k+1\) rounds (i.e., the adversary will forget the history every \(k+1\) rounds), which is a different setting from classical repeated games, where the adversary plays repeated games and will remember the history from the beginning to the end.

Another line of related work in online learning is dynamic regret minimization [19]. In this setup, the accumulated loss is compared with a comparator that can change over time, but usually with a sublinear variation budget. Therefore, dynamic regret is more suitable when the environment is non-stationary. To encourage the player’s strategy to adapt to the changes in the opponents’ strategies, we also consider dynamic comparators, but in game-theoretic settings, and with different regret notions.

9 Proof for Example 1↩︎

In Iterated Prisoner’s Dilemma, since the players are symmetric, we will focus on analyzing player 1 without loss of generality. Note that tit-for-tat (where both players start with \(C\)) promotes cooperation, since the players will stick to \(C\) and the time-average utility will be \(0.6\), higher than that of the one-shot Nash equilibrium \((D,D)\).

However, tit-for-tat may not be a good strategy in terms of external regret: mutually playing it will cause a linear external regret, because the regret of player 1 when compared to always playing \(D\) is \((1.0-0.6)T\). In fact, for any player that achieves sublinear external regret in IPD for any \(T\), the time-average strategy must converge to \(D\) as \(T\to\infty\), since otherwise the player will suffer a linear regret compared to the fixed action \(D\), the strictly dominant strategy.

On the other hand, for the RP-Regret defined in 2 , consider the first timestep \(t\) that player 1 is going to deviate from deterministically choosing \(C\) (since the beginning of playing tit-for-tat mutually) to some comparator strategy. In this case, since the expected utility is a multi-linear function of the comparator strategy, and the comparator is in the Cartesian product of each timestep’s strategy space, there exists an optimal deviation strategy of RP-Regret in the comparator space that is deterministic – choosing either \(C\) or \(D\) at every timestep. Furthermore, at this timestep \(t\) when the comparator is different from deterministically choosing \(C\) for the first time, we can restrict the comparator strategy to be an oblivious (in addition to deterministic) one, since the history \(\bh_{1:t-1}\) has always been \((C,C)\) before, deterministically. With a tit-for-tat opponent, their strategy is deterministic at timestep \(t+1\) as well. By induction, with such a deterministic history, it does not lose optimality to restrict the comparator at \(t+1\) to be oblivious as well. Next, we will show that at timestep \(t\), the best deviation for the comparator is actually \(C\). Then, by induction, the comparator should choose \(C\) deterministically at all timesteps except possibly at the last timestep \(t=T\).

Suppose the comparator at timestep \(t\) is going to play action \(C\) with some probability \(w\) and \(D\) with probability \(1-w\), then they will receive an expected utility of \(w\cdot u_1({C,C})+(1-w)\cdot u_1({D,C})=0.6w+(1-w)=1-0.4w\), where \(u_1(a_1,a_2)\) denotes the utility of player 1 when the actions of both players are \(a_1,a_2\), respectively. When \(t<T\), for timestep \(t+1\), suppose the comparator will play action \(C\) with probability \(w'\) and \(D\) with probability \(1-w'\). Now, player 2, still following tit-for-tat, changes from playing \(C\) deterministically at timestep \(t\), to playing \(C\) with probability \(w\), due to the deviation of player 1 at timestep \(t\). Therefore, the expected utility of player 1 at timestep \(t+1\) now is \(ww'\cdot u_1({C,C})+w(1-w')\cdot u_1({D,C})+(1-w) w'\cdot u_1({C,D})+(1-w)(1-w')\cdot u_1({D,D})=0.8w-0.2ww'-0.2w'+0.2\).

The summation of the expected utility of player 1 at timestep \(t\) and \(t+1\) is thus \(0.4w-0.2ww'-0.2w'+1.2=1.2-0.2w'+w(0.4-0.2w')\). Note that we analyze the deviation at timestep \(t\) by only looking at the expected utility at these two timesteps, since \(w\) will not affect the utility after \(t+1\) (if exists), given player \(2\) following tit-for-tat. Noting that \(w'\leq 1\), we know \(0.4-0.2w'>0\), and further have that \(w\) should be \(1.0\) in order to maximize the summed expected utility (regardless of the choice of \(w'\)). Hence, the comparator should not deviate from \(C\) at this timestep \(t\). Continuing the induction, we further know that the comparator has no incentive to deviate from \(C\) for \(t<T\), until \(t=T\). However, this will at most increase the utility by \(1.0-0.6=0.4\), leading to a constant (and thus sublinear) RP-Regret in terms of \(T\). 0◻

The key ingredient that differentiates these two regret notions is that RP-Regret considers the influence of a deviation at the current timestep on future timesteps, by accounting for the adaptivity of the opponents, while external regret assumes that the opponents are non-adaptive.

10 Full Statements of Hardness Results↩︎

10.1 Hardness Results in Table 1↩︎

We now present the full statements and proofs of the hardness results in Table 1.

We note that since Condition [assumption:2-forgetful] is stronger than Condition [assumption:imperfect-memory], the results in Lemmas 2-4 above with “even if Condition [assumption:2-forgetful] holds” remain true when replacing it with “even if Condition [assumption:imperfect-memory] holds”. This completes the statements in Table 1. We also note that Lemma 4 holds even when the opponent is further subject to a bounded memory length constraint as [26] (i.e., only make decisions based on the past \(M\)-length histories where \(M\) is a constant), as our proof later will show.

10.1.1 Proofs of Results in Table 1↩︎

11 Approximation of RP-Regret↩︎

Unfortunately, even under the necessary conditions given in Table 1, minimizing RP-Regret as defined in Eq. 2 can still be computationally challenging, since each \(f^{t-1}\) depends on every strategy from timestep \(1\) to \(t\), and the number of optimization variables blows up as \(T\) becomes large. Hence, we further approximate the notion of RP-Regret by truncating the strategies far from the current timestep \(t\). Specifically, instead of calculating the expected loss over all possible full histories from \(1\) to \(t\), we only take the latest histories of length no more than \(m\) into account, where \(m\) is a constant. With Condition [assumption:2-forgetful] satisfied for all the players, in 5, we prove that such an approximation will only cause an error of \(2C_m^\gamma\) that decays exponentially with respect to \(m\). Formally, we define \[\begin{align} &J_T^m(\bpi_{1:T}) \mathrel{\vcenter{:}}= \sum_{t=1}^T f^{\min\{t-1,m\}}(\bpi_{t-\min\{t-1,m\}:t}),\quad R_T^m \mathrel{\vcenter{:}}= J_T^m(\bpi_{1:T})-\min_{\hat{\bpi}\uo_{1:T}\in\cC_T\uo} J_T^m((\hat{\bpi}\uo_{1:T}, \bpi^{(-1)}_{1:T}))\label{eq:m-regret-def} \end{align}\tag{10}\] where \(m\in\NN\), and \(\cC_T\ui\subseteq \rbr{\cX\ui}^T\) is the set of all the strategies of player \(i\) with a bounded variation satisfying Conditions [assumption:1-variation] and [assumption:2-forgetful]. Note that the expected loss \(f^{\min\{t-1,m\}}(\bpi_{t-\min\{t-1,m\}:t})\) is only related to the strategies from timestep \(t-m\) to \(t\), which is more efficient to optimize compared to \(f^{t-1}(\bpi_{1:t})\).

Next, we will verify that \(f^{\min\{t-1,m\}}(\bpi_{t-\min\{t-1,m\}:t})\) can be a good approximation of \(f^{t-1}(\bpi_{1:t})\). In this case, \(J_T^m\) and \(R_T^m\) will also approximate \(J_T\) and \(R_T\) well, respectively.

Therefore, when \(\gamma\leq \frac{1}{2(N+2)}\), the approximation error \(|R_T^m-R_T|\) decays exponentially with respect to \(m\). The proof is postponed to Appendix 18.

12 Bounding \(R_T^m\) by \(\bar R_T^m\) and Switching Cost↩︎

12.1 Mitigating the Dependence on Past Strategies↩︎

The expected loss at timestep \(t\) in the online learning literature typically only depends on the strategy at that single timestep [60]. Therefore, to facilitate the analysis, we define the following vanilla RP-Regret over the unary loss, i.e., the expected loss \(f_t^m\) defined in the following only depends on \(\bpi\uo_t\), instead of \(\bpi\uo_{t-m:t}\). Such a technique has also been exploited in the literature when memory is involved in online learning [10], [11], [13], [22], [27]. Specifically, for any strategy profile \(\bpi\uo\in\cX^{(1)}\) (of length \(1\)), any integer \(m\geq 0\), and any timestep \(t>m\), we can define the unary expected loss: \[\begin{align} &f_t^m(\bpi\uo) \mathrel{\vcenter{:}}= f^m(((\bpi\uo,\bpi_{t-m}\uno),(\bpi\uo,\bpi_{t-m+1}\uno),...,(\bpi\uo,\bpi_t\uno))).\label{eq:unary-loss-def} \end{align}\tag{11}\] Then, we can define the corresponding cumulative loss and regret as follows: \[\begin{align} \bar J_T^m(\bpi_{1:T}) \mathrel{\vcenter{:}}= \sum_{t=1}^T f_t^{\min\{t-1,m\}}(\bpi\uo_t),\qquad~~~ \bar R_T^m \mathrel{\vcenter{:}}= \bar J_T^m(\bpi_{1:T})-\min_{\hat{\bpi}\uo_{1:T}\in \cC_T\uo} \bar J_T^m((\hat{\bpi}\uo_{1:T},\bpi\uno_{1:T})).\label{eq:m-regret-no-memory-def} \end{align}\tag{12}\]

Note that \(f_t^m(\bpi\uo_t)=f^m(((\underbrace{\bpi_t\uo,\bpi_t\uo,...,\bpi_t\uo}_{m+1}), \bpi\uno_{t-m:t}))\). Then, by the Lipschitz continuity (with some constant \(C_{\rm Lips}>0\)) of \(f^m\) with respect to \(\bpi_{t-m:t}\uo\) (cf. Lemma 6), we have\[\begin{align} \abr{R_T^m-\bar R_T^m}\leq C_{\rm Lips}m^2 \max_{\hat{\bpi}\uo_{1:T}\in \cC_T\uo} \sum_{t=2}^T\rbr{\nbr{\bpi\uo_{t-1}-\bpi\uo_t}_\infty+\nbr{\hat{\bpi}\uo_{t-1}-\hat{\bpi}\uo_t}_\infty}. \end{align}\] The right-hand side (RHS) is sublinear in \(T\) when we have Condition [assumption:1-variation] on the comparator \(\hat{\bpi}_{1:T}\uo\), and the strategy of player 1, the regret minimizer, also satisfies Condition [assumption:1-variation]¹¹. Hence, instead of minimizing \(R_T^m\), we can minimize \(\bar R_T^m\) using any online learning algorithm that can also guarantee \(\sum_{t=2}^T \nbr{\bpi\uo_{t-1}-\bpi\uo_t}_\infty\) to be sublinear in \(T\).

12.2 Bounding the difference between \(J_T^m\) and \(\bar J_T^m\)↩︎

Following the framework of online convex optimization with memory [22], [27], we will use the Lipschitz continuity of \(f^{\min\{t-1,m\}}\) to remove the dependence on past strategies with an additional cost corresponding to the variation defined in Condition [assumption:1-variation]. We first show \(f^m(\bpi_{1:m+1})\) is Lipschitz with respect to \(\bpi_{1:m+1}\) for any \(m\in\NN\) and joint strategy \(\bpi_{1:m+1}\).

The proof is postponed to Appendix 18.1. Then, we can bound \(R_T^m\) by \(\bar R_T^m\) with an additional switching cost (accumulated variation of \(\bpi_t\uo\) over time) by using Lemma 6 and Lemma 7 in the following.

The proof is postponed to Appendix 18.3.

By Lipschitz continuity of \(f^m\), for any strategy vector \(\tilde{\bpi}\in\rbr{\cX}^T\) of length \(T\), we have \[\begin{align} |J_T^m(\tilde{\bpi})-\bar J_T^m(\tilde{\bpi})|\leq& C_{\rm Lips} \sum_{t=2}^T \sum_{s=\max\cbr{t-m,1}}^{t-1} \nbr{\tilde{\bpi}_t\uo-\tilde{\bpi}_s\uo}_\infty \overset{(i)}{\leq} C_{\rm Lips} m^2\underbrace{\sum_{t=2}^T \nbr{\tilde{\bpi}_{t-1}\uo-\tilde{\bpi}_t\uo}_\infty}_{\text{Switching Cost}} \end{align}\] where \((i)\) is obtained directly from Lemma 7.

13 Minimization of Repeated Policy Regret with an Oracle↩︎

In this section, we will extend the result in [14] to our setting where the comparator can change over time with a sublinear accumulated variation instead of a fixed comparator. We need the oracle \(\cO\) to achieve that.

We can then design Algorithm 2 by using the oracle above. Note that all the strategies of player \(1\) are in the subspace of \(\cX\uo\) that satisfies [assumption:2-forgetful], which is denoted as \(\cX\uo_\gamma\).

Intuitively, we will divide all \(T\) timesteps into \(T/K\) episodes, with \(K\) timesteps in each episode (\(K\) is the hyper-parameter that we will specify later). Then, for each episode, we will run [14] from scratch. This is similar to the restart techniques in the non-stationary MG literature [61], to overcome the non-stationarity.

Throughout this proof, when \(t\leq m\) we interpret expressions such as \(f^m(\bpi_{t-m:t})\) and \(f^m(\bpi\uo,\bpi_{t-m:t}\uno)\) as their available-history versions \(f^{t-1}(\bpi_{1:t})\) and \(f^{t-1}(\bpi\uo,\bpi_{1:t}\uno)\), respectively. Equivalently, one may start the displayed \(m\)-memory bounds after the first \(m\) rounds and absorb the first \(m\) losses into an additive \(O(m)\) term.

Firstly, we have \[\begin{align} \EE[R_T]=&\EE\sbr{\sup_{\hat{\bpi}_{1:T}\uo\in \cC_T}\sum_{t=1}^T f^{t-1}(\bpi_{1:t})-f^{t-1}(\hat{\bpi}_{1:t}\uo,\bpi_{1:t}\uno)}\\ \overset{(i)}{\leq}& \EE\sbr{\sup_{\hat{\bpi}_{1:T}\uo\in \cC_T}\sum_{t=1}^T f^m(\bpi_{t-m:t})-f^m(\hat{\bpi}_{t-m:t}\uo,\bpi_{t-m:t}\uno)}+4C_m^\gamma T\\ \overset{(ii)}{\leq}& \EE\sbr{\sup_{\hat{\bpi}_{1:T}\uo\in \cC_T}\sum_{t=1}^T f^m(\bpi_t\uo,\bpi_{t-m:t}\uno)-f^m(\hat{\bpi}_t\uo,\bpi_{t-m:t}\uno)}+4C_m^\gamma T\\ &+C_{\rm Lips} m^2\sum_{t=2}^T \EE\sbr{\nbr{\bpi_t\uo-\bpi_{t-1}\uo}_\infty}+C_{\rm Lips} m^2\sup_{\hat{\bpi}_{1:T}\uo\in \cC_T}\sum_{t=2}^T \nbr{\hat{\bpi}_t\uo-\hat{\bpi}_{t-1}\uo}_\infty\\ \overset{(iii)}{\leq}& \EE\sbr{\sup_{\hat{\bpi}_{1:T}\uo\in \cC_T}\sum_{t=1}^{T/K}\sum_{s=t\cdot K-K+1}^{t\cdot K} f^m(\bpi_{s}\uo,\bpi_{s-m:s}\uno)- f^m(\hat{\bpi}_{t\cdot K}\uo,\bpi_{s-m:s}\uno)}+4C_m^\gamma T\\ &+C_{\rm Lips} m^2\sum_{t=2}^T \EE\sbr{\nbr{\bpi_t\uo-\bpi_{t-1}\uo}_\infty}+C_{\rm Lips} (m^2+(m+1)K^2)\sup_{\hat{\bpi}_{1:T}\uo\in \cC_T}\sum_{t=2}^T \nbr{\hat{\bpi}_t\uo-\hat{\bpi}_{t-1}\uo}_\infty \end{align}\] where we define \(f^m(\bpi\uo,\bpi_{t-m:t}\uno) \mathrel{\vcenter{:}}= f^m(((\bpi\uo,\bpi_{t-m}\uno),(\bpi\uo,\bpi_{t-m+1}\uno),...,(\bpi\uo,\bpi_t\uno)))\). \((i)\) is by Lemma 5, and \((ii),(iii)\) are by Lemma 6 and Lemma 7. Then,

\[\begin{align} \EE[R_T]\leq& \EE\sbr{\sum_{t=1}^{T/K} \underbrace{\sup_{\hat{\bpi}\uo\in\cX\uo_\gamma}\sum_{s=t\cdot K-K+1}^{t\cdot K} f^m(\bpi_s\uo,\bpi_{s-m:s}\uno)- f^m(\hat{\bpi}\uo,\bpi_{s-m:s}\uno)}_{\circled{1}}}+4C_m^\gamma T\\ &+C_{\rm Lips} m^2\sum_{t=2}^T \EE\sbr{\nbr{\bpi_t\uo-\bpi_{t-1}\uo}_\infty}+C_{\rm Lips} (m^2+(m+1)K^2)\sup_{\hat{\bpi}_{1:T}\uo\in \cC_T}\sum_{t=2}^T \nbr{\hat{\bpi}_t\uo-\hat{\bpi}_{t-1}\uo}_\infty. \end{align}\] Since \(\circled{1}\) is exactly the external regret of a non-convex function as in [14], we can directly use [14], then \[\begin{align} \EE[R_T]\leq& \eta C_{\rm Lips}^2 |\cA|^{2m+2}(1+m)^2 T+2\frac{|\cA|^{m+1}}{\eta}\frac{T}{K}+4C_m^\gamma T+C_{\rm Lips} (m^2+(m+1)K^2)P_T\\ &+\alpha T + \beta |\cA|^{m+1}\rbr{\frac{1}{\eta} + C_{\rm Lips}(1+m)} T. \end{align}\]

By choosing \(\eta=\frac{1}{\sqrt K}\) and \(K=\rbr{\frac{T}{P_T}}^{0.4}\), we have \[\begin{align} &\EE\sbr{R_T}\\ \leq& 4C_m^\gamma T+C_{\rm Lips}^2|\cA|^{2m+2}(m+1)^2P_T^{0.2}T^{0.8}+C_{\rm Lips}m^2 P_T\\ &+C_{\rm Lips}(m+1)T^{0.8} P_T^{0.2}+T^{0.6}P_T^{0.4}+|\cA|^{m+1}T^{0.8} P_T^{0.2}\\ &+\alpha T + \beta |\cA|^{m+1}\rbr{\rbr{\frac{T}{P_T}}^{0.2} + C_{\rm Lips}(1+m)} T\\ =&4C_m^\gamma T+\rbr{C_{\rm Lips}^2|\cA|^{2m+2}(1+m)^2+C_{\rm Lips}(m+1)+|\cA|^{m+1}}T^{0.8} P_T^{0.2}+C_{\rm Lips}m^2 P_T+T^{0.6}P_T^{0.4}\\ &+\alpha T + \beta |\cA|^{m+1}\rbr{\rbr{\frac{T}{P_T}}^{0.2} + C_{\rm Lips}(1+m)} T. \end{align}\] Therefore, we have \[\begin{align} \EE\sbr{R_T}\leq O \rbr{ T^{0.8}P_T^{0.2} + \alpha T + \beta \frac{T^{1.2}}{P_T^{0.2}} + C_m^\gamma T}. \end{align}\] For any desired accuracy \(\epsilon>0\), when the optimization oracle is accurate enough (\(\alpha,\beta\) small enough) and by picking \(m=O\rbr{\log \frac{1}{\epsilon}}\), we can achieve \(\EE\sbr{\frac{R_T}{T}}\leq \epsilon\). 0◻

14 Minimization of Local RP-Regret↩︎

14.1 Hardness Results↩︎

14.2 Proof of Theorem 1↩︎

In this section, we will use \(\bpi\uo_{1:T}\) as the strategy of player 1 generated by the regret minimizer and \(\bpi\uno_{1:T}\) to denote the strategy generated by the adversary. Also, we will use \(\bpi_{1:T}\) to denote the joint strategy.

Therefore, according to 5 , \[\begin{align} f_t^{t-1,{\rm local}}(\bar \bpi\uo_{1:t})=(T-t) f^{t-1}(\bpi\uo_{1:t},\bpi\uno_{1:t})+\sum_{s=1}^t f^{t-1}((\bpi\uo_{1:s-1}, \bar\bpi\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{1:t}). \end{align}\] and \(f_t^{t-1,{\rm local}}(\bpi_{1:t}\uo)=Tf^{t-1}(\bpi_{1:t})\). Then we have \[\begin{align} R_T^{\rm local}=\sum_{t=1}^T f^{t-1,\rm local}_t (\bpi_{1:t}\uo)-\min_{\hat{\bpi}\uo_{1:T}\in\cC_T\uo}\sum_{t=1}^T f^{t-1,\rm local}_t (\hat{\bpi}_{1:t}\uo). \end{align}\]

For any \(\hat{\bpi}\uo_{1:t}\), we can still get \[\begin{align} &f_t^{t-1,{\rm local}}(\bpi\uo_{1:t})-f_t^{t-1,{\rm local}}(\hat{\bpi}\uo_{1:t})\notag\\ =& \sum_{s=1}^{t-m-1} f^{t-1}(\bpi\uo_{1:t},\bpi\uno_{1:t})-f^{t-1}((\bpi\uo_{1:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{1:t})\tag{13}\\ &+\sum_{s=t-m}^t f^{t-1}(\bpi\uo_{1:t},\bpi\uno_{1:t})-f^{t-1}((\bpi\uo_{1:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{1:t}).\tag{14} \end{align}\] For 13 , we have \[\begin{align} &\sum_{s=1}^{t-m-1}\abr{f^{t-1}((\bpi\uo_{1:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{1:t})-f^{t-1}(\bpi\uo_{1:t},\bpi\uno_{1:t})}\\ \leq& \sum_{s=1}^{t-m-1}\Big(\abr{f^{t-1}((\bpi\uo_{1:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{1:t})-f^{t-s}(\bpi\uo_{s+1:t}, \bpi\uno_{s+1:t})}\\ &+\abr{f^{t-s}(\bpi\uo_{s+1:t}, \bpi\uno_{s+1:t})-f^{t-1}(\bpi\uo_{1:t},\bpi\uno_{1:t})}\Big)\\ \overset{(i)}{\leq}& 4\sum_{s=1}^{t-m-1} C_{t-s}^\gamma \overset{(ii)}{\leq} 4N C_m^\gamma, \end{align}\] where \((i)\) is by Lemma 5 and \((ii)\) is by the definition of \(C_m^\gamma\), and by the condition \(\gamma\leq \frac{1}{2(N+2)}\), which ensures Lemma 5 holds. For 14 , we have \[\begin{align} &\sum_{s=t-m}^t f^{t-1}(\bpi\uo_{1:t},\bpi\uno_{1:t})-f^{t-1}((\bpi\uo_{1:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{1:t})\\ \leq& \sum_{s=t-m}^t f^m(\bpi\uo_{t-m:t},\bpi\uno_{t-m:t}) - f^m((\bpi\uo_{t-m:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t})\\ &+ \sum_{s=t-m}^t \abr{f^{t-1}((\bpi\uo_{1:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{1:t})-f^m((\bpi\uo_{t-m:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t})}\\ &+\sum_{s=t-m}^t\abr{f^{t-1}(\bpi\uo_{1:t},\bpi\uno_{1:t})-f^m(\bpi\uo_{t-m:t},\bpi\uno_{t-m:t})}\\ \leq& \sum_{s=t-m}^t f^m(\bpi\uo_{t-m:t},\bpi\uno_{t-m:t}) - f^m((\bpi\uo_{t-m:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t})+4(m+1)C_m^\gamma. \end{align}\]

For notational simplicity, let \(\hat{\bpi}_{1:T}\uo=\argmin_{\bar\bpi\uo_{1:T}\in\cC_T\uo} \sum_{t=1}^T f^{t-1,\rm local}_t (\bar\bpi_{1:t}\uo)\). Then, \[\begin{align} R_T^{\rm local}=&\sum_{t=1}^T f^{t-1,\rm local}_t (\bpi_{1:t}\uo)-\sum_{t=1}^T f^{t-1,\rm local}_t (\hat{\bpi}_{1:t}\uo)\\ \leq& \sum_{t=m+1}^T\sum_{s=t-m}^t\rbr{f^m(\bpi\uo_{t-m:t},\bpi\uno_{t-m:t}) - f^m((\bpi\uo_{t-m:s-1}, \hat{\bpi}\uo_s, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t})}+4(N+m+1)C_m^\gamma T\\ &+\sum_{t=1}^m \abr{f^{t-1,\rm local}_t (\bpi_{1:t}\uo)-f^{t-1,\rm local}_t (\hat{\bpi}_{1:t}\uo)}\\ \overset{(i)}{\leq}& \sum_{t=m+1}^T\sum_{s=t-m}^t\rbr{f^m((\bpi\uo_{t-m:s-1}, \bpi\uo_t, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t}) - f^m((\bpi\uo_{t-m:s-1}, \hat{\bpi}\uo_t, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t}) }\\ &+4(N+m+1)C_m^\gamma T+m^2+C_{\rm Lips}\sum_{t=m+1}^T \sum_{s=t-m}^{t-1}\rbr{\nbr{\bpi\uo_s-\bpi\uo_t}_\infty+\nbr{\hat{\bpi}\uo_s-\hat{\bpi}\uo_t}_\infty}\\ \overset{(ii)}{\leq}& \sum_{t=m+1}^T\sum_{s=t-m}^t\rbr{f^m((\bpi\uo_{t-m:s-1}, \bpi\uo_t, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t}) - f^m((\bpi\uo_{t-m:s-1}, \hat{\bpi}\uo_t, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t}) }\\ &+4(N+m+1)C_m^\gamma T+m^2+C_{\rm Lips}m^2\sum_{t=m+2}^T \rbr{\nbr{\bpi\uo_{t-1}-\bpi\uo_t}_\infty+\nbr{\hat{\bpi}\uo_{t-1}-\hat{\bpi}\uo_t}_\infty} \end{align}\] where \((i)\) uses Lemma 6 and \((ii)\) uses Lemma 7.

Notice that \(\sum_{s=t-m}^t f^m((\bpi\uo_{t-m:s-1}, \bar\bpi\uo_t, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t})\) is a linear function with respect to \(\bar\bpi_t\uo\). So, \[\begin{align} &\sum_{t=m+1}^T\sum_{s=t-m}^t\rbr{f^m((\bpi\uo_{t-m:s-1}, \bpi\uo_t, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t}) - f^m((\bpi\uo_{t-m:s-1}, \hat{\bpi}\uo_t, \bpi\uo_{s+1:t}),\bpi\uno_{t-m:t}) }\\ =& \sum_{t=m+1}^T\inner{\bg_t}{\bpi\uo_t-\hat{\bpi}\uo_t} \end{align}\] where, for \(t\geq m+1\), \[\begin{align} \bg_t\mathrel{\vcenter{:}}= \nabla_{\bar\bpi\uo}\left.\sum_{s=t-m}^t f^m((\bpi\uo_{t-m:s-1},\bar\bpi\uo,\bpi\uo_{s+1:t}),\bpi\uno_{t-m:t})\right|_{\bar\bpi\uo=\bpi_t\uo}. \end{align}\] We set \(\bg_t=0\) for \(t\leq m\).

Therefore, by Lemma 28, we have \[\begin{align} R_T^{\rm local}\leq& \frac{\eta}{2}\sum_{t=m+1}^T\nbr{\bg_t}^2+\frac{1}{2\eta}\nbr{\bpi_{m+1}\uo-\hat{\bpi}_{m+1}\uo}^2+\frac{2|\cH_{m+1}|}{\eta} \sum_{t=m+2}^T \nbr{\hat{\bpi}_{t-1}-\hat{\bpi}_t}_\infty\\ &+4(N+m+1)C_m^\gamma T+m^2+C_{\rm Lips}m^2\sum_{t=m+2}^T \rbr{\nbr{\bpi\uo_{t-1}-\bpi\uo_t}_\infty+\nbr{\hat{\bpi}\uo_{t-1}-\hat{\bpi}\uo_t}_\infty} \end{align}\] since \(D_1= 2|\bigcup_{k=0}^m\cH_k|\leq 2|\cH_{m+1}|\). By \[\begin{align} \nbr{\bg_t}\leq& \nbr{\bg_t}_1\\ =& \sum_{\bh_1\in\bigcup_{k=0}^m \cH_k,a_1\in\cA_1}\abr{ \sum_{\bh_2\in\cH_{m+1},\bh_{2,1:L(\bh_1)}=\bh_1,h_{2,L(\bh_1)+1,1}=a_1}\cL_1(\bh_{2,m+1})\Pr(\bh_2|h_{2,L(\bh_1)+1,1}=a_1;\bpi_{t-m:t})}\\ \leq& \sum_{\bh_2\in\cH_{m+1}}\sum_{s=0}^m \Pr(\bh_2|h_{2,s+1,1};\bpi_{t-m:t})=(m+1) |\cA_1|. \end{align}\] Note that we use \(h_{2,s,1}\in\cA_1\) to denote the action player 1 played at timestep \(s\) and \(\Pr(\bh_2|h_{2,s+1,1};\bpi_{t-m:t})\) means the probability that \(\bh_2\) occurs when playing \(\bpi_{t-m:t}\) conditioned on observing \(h_{2,s+1,1}\in\cA_1\) at timestep \(s+1\).

Then, for any \(\hat{\bpi}_{1:T}\), we have \[\begin{align} R_T^{\rm local} \overset{(i)}{\leq}& \frac{\eta}{2} (m+1)^2 |\cA_1|^2 T+\frac{2|\cH_{m+1}|^2}{\eta}+\frac{2|\cH_{m+1}|}{\eta} \sum_{t=m+2}^T \nbr{\hat{\bpi}_{t-1}-\hat{\bpi}_t}_\infty\\ &+4(N+m+1)C_m^\gamma T+m^2+C_{\rm Lips}m^2\sum_{t=m+2}^T \nbr{\hat{\bpi}\uo_{t-1}-\hat{\bpi}\uo_t}_\infty+C_{\rm Lips}m^2(m+1) |\cA_1| \eta T \end{align}\] where \((i)\) is because \(\bpi_t\uo=\Proj{\cX\uo_\gamma}{\bpi_{t-1}\uo-\eta \bg_t}\) and \(\nbr{\bg_t}\leq (m+1) |\cA_1|\). Note that by definition of \(\cC_T\uo\) and \(\hat{\bpi}\uo_{1:T}\in\cC_T\uo\), \(\sum_{t=m+2}^T \nbr{\hat{\bpi}\uo_{t-1}-\hat{\bpi}\uo_t}_\infty\leq P_T\). By choosing \(\eta=\sqrt{\frac{2|\cH_{m+1}|\rbr{|\cH_{m+1}|+P_T}}{\rbr{C_{\rm Lips}m^2(m+1) |\cA_1|+(m+1)^2|\cA_1|^2/2}T}}\), we have \[\begin{align} R_T^{\rm local}\leq& 2\sqrt{\rbr{2|\cH_{m+1}|\rbr{|\cH_{m+1}|+P_T}}\rbr{\rbr{C_{\rm Lips}m^2(m+1) |\cA_1|+(m+1)^2|\cA_1|^2/2}T}}\\ &\qquad+4(N+m+1)C_m^\gamma T+m^2+C_{\rm Lips}m^2 P_T.\qedhere \end{align}\]

15 Proof of Theorem 2↩︎

15.1 Important Lemmas↩︎

Here’s the performance difference lemma for average-reward MDPs. For convenience, we will use the shorthand \(\EE_{\bpi}\) to denote \(\EE_{\ba_t\sim\bpi(\cdot\given \bh_t), s_{t+1}\sim \Pr(\cdot\given \bh_t,\ba_t)}\). Also, we define \[\begin{align} \rho^{\bpi} \mathrel{\vcenter{:}}= \lim_{T\to+\infty}\frac{1}{T}\EE_{\bpi}\left[\sum_{t=0}^{T-1} \cL_1(\bh_t,\ba_t)\right] \end{align}\] where \(\Pr\) is the transition probability and \(\cL_1\) is the loss for player \(1\). It is easy to see from the proof of Lemma 35, the initial state \(\bh_0\) does not affect the value of \(\rho^{\bpi}\) so we omit the initial state here. Also, in this section, we assume that we are controlling player \(1\) so we will omit the subscript \(1\) in the following.

From Lemma 33, the MG induced by \(M\)-bounded length memory defined in Definition 1 is aperiodic unichain. Under such a condition, \(d^{\bpi}\) is fixed regardless of the initial state \(\bh_0\).

The proof is postponed to Appendix 19.3. By Lemma 11, we can prove that \(\rho^{\bpi}\) is Lipschitz continuous.

15.2 Formal Version and Proof of Theorem 2↩︎

For any \(t\geq K+1\), by the Lipschitz continuity proved in Lemma 6, we have \[\begin{align} \abr{f^{t-1}(\bpi_{1:t})-f^{t-1}(\bpi_{1:t-K-1},\underbrace{\bpi_t,\bpi_t,...,\bpi_t}_{K+1})}\leq C_{\rm Lips}\sum_{s=t-K}^{t-1} \nbr{\bpi_t-\bpi_s}_\infty\leq& C_{\rm Lips}\sum_{i=1}^N\sum_{s=t-K}^{t-1} \nbr{\bpi\ui_t-\bpi\ui_s}_\infty. \end{align}\] Then, by Corollary 35, we have \[\begin{align} &\abr{f^{t-1}(\bpi_{1:t-K-1},\underbrace{\bpi_t,\bpi_t,...,\bpi_t}_{K+1})-\rho^{\bpi_t}}\\ =&\abr{\sum_{\bh\in\cH_M} \cL_1(\bh_M) (\mu(\cP^{\bpi_t})^{K+1})_{\bh}-\sum_{\bh\in\cH_M} \cL_1(\bh_M) (\lim_{T\to+\infty} \frac{1}{T}\sum_{s=0}^{T-1} \mu(\cP^{\bpi_t})^s)_{\bh}}\\ \leq& 2\rbr{1-\delta}^{\floor{\frac{K}{M\useconstant{constant:go-back-root-length}}}}. \end{align}\]

where \(\mu\in\Delta_{|\cH_M|}\) is the state distribution induced by \(\bpi_{1:t-K-1}\) (which is common for the two terms above).

Therefore, we have \[\begin{align} R_T=&\sum_{t=1}^T f^{t-1}(\bpi_{1:t})-\sum_{t=1}^T f^{t-1}(\hat{\bpi}\uo_{1:t},\bpi\uno_{1:t})\notag\\ \leq& \sum_{t=1}^T \rho^{\bpi_t}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+\sum_{t=1}^{T} \abr{\rho^{\bpi_t}-f^{t-1}(\bpi_{1:t})}+\sum_{t=1}^{T} \abr{\rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}-f^{t-1}(\hat{\bpi}\uo_{1:t},\bpi\uno_{1:t})}\notag\\ \leq&\sum_{t=1}^T \rho^{\bpi_t}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+\sum_{t=1}^{K} \abr{\rho^{\bpi_t}-f^{t-1}(\bpi_{1:t})}+\sum_{t=1}^{K} \abr{\rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}-f^{t-1}(\hat{\bpi}\uo_{1:t},\bpi\uno_{1:t})}\tag{15}\\ &+C_{\rm Lips}\sum_{t=K+1}^T\sum_{s=t-K}^{t-1} \nbr{\bpi_t-\bpi_s}_\infty+C_{\rm Lips}\sum_{t=K+1}^T\sum_{i=2}^N\sum_{s=t-K}^{t-1} \nbr{\bpi\ui_t-\bpi\ui_s}_\infty+C_{\rm Lips}\sum_{t=K+1}^T\sum_{s=t-K}^{t-1} \nbr{\hat{\bpi}\uo_t-\hat{\bpi}\uo_s}_\infty\tag{16}\\ &+4\rbr{1-\delta}^{\floor{\frac{K}{M\useconstant{constant:go-back-root-length}}}}T.\tag{17} \end{align}\]

Since \(\max\left\{\abr{\rho^{\bpi_t}-f^{t-1}(\bpi_{1:t})},\abr{\rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}-f^{t-1}(\hat{\bpi}\uo_{1:t},\bpi\uno_{1:t})}\right\}\leq 1\), 15 can be upper-bounded by \[\begin{align} &\sum_{t=1}^T \rho^{\bpi_t}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+\sum_{t=1}^{K} \abr{\rho^{\bpi_t}-f^{t-1}(\bpi_{1:t})}+\sum_{t=1}^{K} \abr{\rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}-f^{t-1}(\hat{\bpi}\uo_{1:t},\bpi\uno_{1:t})}\\ \leq& \sum_{t=1}^T \rho^{\bpi_t}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+2K. \end{align}\] Also, by Lemma 7, 16 can be bounded by \[\begin{align} &C_{\rm Lips}\sum_{t=K+1}^T\sum_{s=t-K}^{t-1} \nbr{\bpi_t-\bpi_s}_\infty+C_{\rm Lips}\sum_{t=K+1}^T\sum_{i=2}^N\sum_{s=t-K}^{t-1} \nbr{\bpi\ui_t-\bpi\ui_s}_\infty+C_{\rm Lips}\sum_{t=K+1}^T\sum_{s=t-K}^{t-1} \nbr{\hat{\bpi}\uo_t-\hat{\bpi}\uo_s}_\infty\\ \leq& C_{\rm Lips} K^2\sum_{t=2}^T \nbr{\bpi_t-\bpi_{t-1}}_\infty+C_{\rm Lips} K^2\sum_{t=2}^T\sum_{i=2}^N \nbr{\bpi\ui_t-\bpi\ui_{t-1}}_\infty+C_{\rm Lips} K^2\sum_{t=2}^T \nbr{\hat{\bpi}\uo_t-\hat{\bpi}\uo_{t-1}}_\infty\\ \leq& C_{\rm Lips} K^2\sum_{t=2}^T \nbr{\bpi_t-\bpi_{t-1}}_\infty+C_{\rm Lips} K^2\Delta_T \end{align}\] where the last line is by the definition of \(\Delta_T\). Hence, we have \[\begin{align} R_T\leq& \sum_{t=1}^T \rho^{\bpi_t}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+2K+C_{\rm Lips} K^2\sum_{t=2}^T \nbr{\bpi_t-\bpi_{t-1}}_\infty+C_{\rm Lips} K^2 \Delta_T+4\rbr{1-\delta}^{\floor{\frac{K}{M\useconstant{constant:go-back-root-length}}}}T. \end{align}\]

Recall that we defined the marginals \(\bpi_t^{[i]}\) in [eq:def-self-play-strategy-i]. Let \(\bpi_t^{[\cdot]}\) denote the joint strategy induced by \(\bq_t\), i.e., \[\begin{align} \pi_t^{[\cdot]}(\ba\given\bh)\mathrel{\vcenter{:}}= \frac{q_t(\bh,\ba)}{\sum_{\ba'\in\cA}q_t(\bh,\ba')}. \end{align}\] Its player-\(i\) marginal is \(\bpi_t^{[i]}\), and in particular \(\bpi_t^{[1]}=\bpi_t\uo\). Then, by Lemma 13, we have \[\begin{align} &\sum_{t=1}^T \rho^{\bpi_t}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}\\ \leq& \sum_{t=1}^T \rho^{\bpi_t^{[\cdot]}}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+C_Q\sum_{t=1}^T\max_{\bh\in\cH_M} \nbr{\bpi_t(\cdot\given \bh)-\bpi_t^{[\cdot]}(\cdot\given \bh)}_1\\ =& \sum_{t=1}^T \rho^{\bpi_t^{[\cdot]}}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+C_Q\sum_{t=1}^T\max_{\bh\in\cH_M} \sum_{\ba\in\cA}\abr{\bpi_t\uo(a_1\given \bh)\bpi_t\uno(\ba_{-1}\given \bh)-\bpi_t\uo(a_1\given \bh)\frac{\bpi_t^{[\cdot]}(\ba\given \bh)}{\bpi_t\uo(a_1\given \bh)}}\\ =& \sum_{t=1}^T \rho^{\bpi_t^{[\cdot]}}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+C_Q\sum_{t=1}^T\max_{\bh\in\cH_M} \sum_{\ba\in\cA}\bpi_t\uo(a_1\given \bh)\abr{\bpi_t\uno(\ba_{-1}\given \bh)-\frac{\bpi_t^{[\cdot]}(\ba\given \bh)}{\bpi_t\uo(a_1\given \bh)}} \end{align}\] The difference between \(\bpi_t^{[i]}\) and \(\bpi_t\ui\) is that \(\bpi_t^{[i]}\) is the marginal of the occupancy measure \(\bq_t\), while \(\bpi_t\ui\) is the true strategy of player \(i\).

The proof is postponed to Appendix 18.2. Since \(\bq_t\in\cX\), the lower-bound constraint in [eq:def-convex-set-self-play] gives \(\sum_{\ba\in\cA} q_t(\bh,\ba)\geq \frac{\gamma^{NM}}{|\cA|^M}\) for any \(\bh\in\cH_M\). Therefore, for any \(t=2,3,...,T\), \[\begin{align} &C_{\rm Lips}K^2\sum_{t=2}^T \nbr{\bpi_t-\bpi_{t-1}}_\infty\\ \leq& C_{\rm Lips} K^2\sum_{t=2}^T \nbr{\bpi_t^{[\cdot]}-\bpi_{t-1}^{[\cdot]}}_\infty+2C_{\rm Lips} K^2\sum_{t=1}^T \nbr{\bpi_t^{[\cdot]}-\bpi_t}_\infty\\ \leq& \frac{2 C_{\rm Lips} K^2|\cA|^{M+1}}{\gamma^{NM}}\sum_{t=2}^T\nbr{\bq_t-\bq_{t-1}}_\infty+ 2C_{\rm Lips} K^2\sum_{t=1}^T \max_{\bh\in\cH_M} \sum_{\ba\in\cA}\bpi_t\uo(a_1\given \bh)\abr{\bpi_t\uno(\ba_{-1}\given \bh)-\frac{\bpi_t^{[\cdot]}(\ba\given \bh)}{\bpi_t\uo(a_1\given \bh)}}. \end{align}\]

For each timestep \(t\), define \[\begin{align} \sigma_t(\bh,\ba)\mathrel{\vcenter{:}}= \begin{cases} 1, & D_t(\bh,\ba,\bq_t)\geq 0,\\ -1, & D_t(\bh,\ba,\bq_t)<0. \end{cases} \end{align}\] The constraint in Algorithm 3 is equivalently \[\begin{align} g_t(\bq)=\sum_{\bh\in\cH_M,\ba\in\cA}\sigma_t(\bh,\ba)D_t(\bh,\ba,\bq), \end{align}\] where \[\begin{align} D_t(\bh,\ba,\bq) =q(\bh,\ba)-\pi_t^{(-1)}(\ba_{-1}\given \bh)\sum_{\ba_{-1}'\in\cA_{-1}}q(\bh,(a_1,\ba_{-1}')). \end{align}\] In particular, \[\begin{align} g_t(\bq_t)=\sum_{\bh\in\cH_M,\ba\in\cA}|D_t(\bh,\ba,\bq_t)|. \end{align}\] Notice that \[\begin{align} \frac{q_t(\bh,\ba)}{\sum_{\ba_{-1}'\in\cA_{-1}} q_t(\bh,(a_1,\ba_{-1}'))} =\frac{q_t(\bh,\ba)}{\sum_{\ba'\in\cA} q_t(\bh,\ba')} \frac{\sum_{\ba'\in\cA}q_t(\bh,\ba')}{\sum_{\ba_{-1}'\in\cA_{-1}} q_t(\bh,(a_1,\ba_{-1}'))} =\pi_t^{[\cdot]}(\ba\given \bh)\cdot \frac{1}{\pi_t\uo(a_1\given \bh)}. \end{align}\] Here \(\pi_t^{[\cdot]}\) denotes the joint distribution induced by \(\bq_t\), and \(\bpi_t^{[1]}=\bpi_t\uo\) is its player-\(1\) marginal. Therefore, \[\begin{align} \abr{\bpi_t\uno(\ba_{-1}\given \bh)-\frac{\bpi_t^{[\cdot]}(\ba\given \bh)}{\bpi_t\uo(a_1\given \bh)}} &=\frac{|D_t(\bh,\ba,\bq_t)|}{\sum_{\ba_{-1}'\in\cA_{-1}}q_t(\bh,(a_1,\ba_{-1}'))}\\ &\leq \frac{|\cA|^{M+1}}{\gamma^{N(M+1)}|\cA_{-1}|}|D_t(\bh,\ba,\bq_t)|, \end{align}\] where the last inequality is by Lemma 14. Then, we have \[\begin{align} R_T\leq&\sum_{t=1}^T \rho^{\bpi_t^{[\cdot]}}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+2K\\ &+\frac{2 C_{\rm Lips} K^2|\cA|^{M+1}}{\gamma^{NM}}\sum_{t=2}^T\nbr{\bq_t-\bq_{t-1}}_\infty+C_{\rm Lips} K^2 \Delta_T+4\rbr{1-\delta}^{\floor{\frac{K}{M\useconstant{constant:go-back-root-length}}}}T\\ &+(C_Q+2C_{\rm Lips} K^2)\frac{|\cA|^{M+1}}{\gamma^{N(M+1)}|\cA_{-1}|} \sum_{t=1}^T\max_{\bh\in\cH_M} \sum_{\ba\in\cA}\bpi_t\uo(a_1\given \bh) D_t(\bh,\ba,\bq_t)\\ \leq&\sum_{t=1}^T \rho^{\bpi_t^{[\cdot]}}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+2K\\ &+\frac{2 C_{\rm Lips} K^2|\cA|^{M+1}}{\gamma^{NM}}\sum_{t=2}^T\nbr{\bq_t-\bq_{t-1}}_\infty+C_{\rm Lips} K^2 \Delta_T+4\rbr{1-\delta}^{\floor{\frac{K}{M\useconstant{constant:go-back-root-length}}}}T\\ &+(C_Q+2C_{\rm Lips}K^2)\frac{|\cA|^{M+1}}{\gamma^{N(M+1)}}\sum_{t=1}^T\max_{\bh\in\cH_M,\ba\in\cA} \cbr{D_t(\bh,\ba)}. \end{align}\]

For the comparator sequence, define the joint strategy \(\hat{\pi}_t^{[\cdot]}(\ba\given\bh)\mathrel{\vcenter{:}}= \hat{\pi}_t\uo(a_1\given\bh)\pi_t\uno(\ba_{-1}\given\bh)\). By Lemma 16, we have \[\begin{align} \sum_{t=2}^T \nbr{\hat{\bq}_t-\hat{\bq}_{t-1}}\leq& (C_Q|\cH_M|+1) |\cA|\sum_{t=2}^T \nbr{\hat{\bpi}^{[\cdot]}_{t}-\hat{\bpi}^{[\cdot]}_{t-1}}_\infty\\ =& (C_Q|\cH_M|+1) |\cA|\sum_{t=2}^T \max_{\bh\in\cH_M,\ba\in\cA} \abr{\hat{\pi}_t\uo(a_1\given \bh)\prod_{i=2}^N \pi_t\ui(a_i\given \bh)-\hat{\pi}_{t-1}\uo(a_1\given \bh)\prod_{i=2}^N \pi_{t-1}\ui(a_i\given \bh)}\\ \leq&(C_Q|\cH_M|+1) |\cA|\sum_{t=2}^T \max_{\bh\in\cH_M,\ba\in\cA} \cbr{\abr{\hat{\pi}_t\uo(a_1\given \bh)-\hat{\pi}_{t-1}\uo(a_1\given \bh)}+\sum_{i=2}^N \abr{ \pi_t\ui(a_i\given \bh)-\pi_{t-1}\ui(a_i\given \bh)}}\\ \leq& (C_Q|\cH_M|+1)|\cA|\rbr{\sum_{t=2}^T\nbr{\hat{\bpi}_t\uo-\hat{\bpi}_{t-1}\uo}_\infty+\sum_{i=2}^N\sum_{t=2}^T\nbr{\bpi_t\ui-\bpi_{t-1}\ui}_\infty}\\ \leq& (C_Q|\cH_M|+1)|\cA|\Delta_T. \end{align}\] Then, by the convergence of Algorithm 6 in Lemma 30 and the variation of \(\bq\) bounded by variation of \(\bpi\) in Lemma 16, we have \[\begin{align} &\sum_{t=1}^T \rho^{\bpi_t^{[\cdot]}}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+\frac{2 C_{\rm Lips} K^2|\cA|^{M+1}}{\gamma^{NM}}\sum_{t=2}^T \nbr{\bq_t-\bq_{t-1}}_\infty\notag\\ \leq& \frac{5}{2}\sqrt{\frac{T}{(C_Q|\cH_M|+1) |\cA| \Delta_T}}+\rbr{5+4|\cA|^{M+1}+8C_{\rm Lips}K^2\frac{|\cA|^{\frac{3}{2}(M+1)}}{\gamma^{NM}}}\sqrt{(C_Q|\cH_M|+1) |\cA|}\sqrt{T\Delta_T}\tag{18}\\ &\sum_{t=1}^T g_t(\bq_t)\leq \sqrt{2\rbr{(8C_{\rm Lips}K^2\frac{|\cA|^{\frac{3}{2}(M+1)}}{\gamma^{NM}}+8|\cA|^{M+1}+1)\sqrt{(C_Q|\cH_M|+1)|\cA|T\Delta_T}+\sqrt{\frac{T}{(C_Q|\cH_M|+1)|\cA|\Delta_T}}}}\notag\\ &\times \sqrt{T+\frac{5}{2}\sqrt{\frac{T}{(C_Q|\cH_M|+1)|\cA|\Delta_T}}+\rbr{5+4|\cA|^{M+1}+8C_{\rm Lips}K^2\frac{|\cA|^{\frac{3}{2}(M+1)}}{\gamma^{NM}}}\sqrt{(C_Q|\cH_M|+1)|\cA|T\Delta_T}}\tag{19} \end{align}\] since \[\begin{align} &R=\max_{\bq} \nbr{\bq}_2=1,\\ &k=1,\\ &D=\max_{t,\bq} g_t(\bq)\leq 2,\\ &G=\max\{\nbr{\cL_1}, \nbr{\nabla g_t}\}\leq 2\sqrt{|\cH_M|\cdot |\cA|}=2|\cA|^{\frac{M+1}{2}},\\ &F=1,\\ &C=2C_{\rm Lips}K^2\frac{|\cA|^{M+1}}{\gamma^{NM}}. \end{align}\] For ease of illustration, let \(\cU_1\) be the R.H.S. of Eq. 18 and \(\cU_2\) be the R.H.S. of Eq. 19 . This leads to the fact that \[\begin{align} &\sum_{t=1}^T \rho^{\bpi_t^{[\cdot]}}-\sum_{t=1}^T \rho^{(\hat{\bpi}\uo_t,\bpi\uno_t)}+\frac{2 C_{\rm Lips} K^2|\cA|^{M+1}}{\gamma^{NM}}\sum_{t=2}^T \nbr{\bq_t-\bq_{t-1}}_\infty\leq \cU_1,\\ &\sum_{t=1}^T g_t(\bq_t)\leq \cU_2. \end{align}\]

Let \(\hat{\bq}_t\) be the occupancy measure induced by \((\hat{\bpi}_t\uo,\bpi_t\uno)\). When \(\hat{\bq}_t\) lies in \(\cX\), it corresponds to a product-form strategy profile and, for any \(\bh\in\cH_M,\ba\in\cA\), \[\begin{align} \frac{\hat{q}_t(\bh,\ba)}{\sum_{\ba'\in\cA} \hat{q}_t(\bh,\ba')} =\hat{\pi}_t\uo(a_1\given \bh)\pi_t\uno(\ba_{-1}\given \bh). \end{align}\] Equivalently, \(D_t(\bh,\ba,\hat{\bq}_t)=0\) for all \(\bh,\ba\), and hence \(g_t(\hat{\bq}_t)=0\leq 0\). Therefore, \(\hat{\bq}_{1:T}\) satisfies the feasibility requirement of Lemma 30.

Therefore, \[\begin{align} R_T\leq& \cU_1+2K+C_{\rm Lips} K^2 \Delta_T+4\rbr{1-\delta}^{\floor{\frac{K}{M\useconstant{constant:go-back-root-length}}}}T+(C_Q+2C_{\rm Lips}K^2)\frac{|\cA|^{M+1}}{\gamma^{N(M+1)}|\cA_{-1}|}\sum_{t=1}^T g_t(\bq_t)\\ \leq& \cU_1+(C_Q+2C_{\rm Lips}K^2)\frac{|\cA|^{M+1}}{\gamma^{N(M+1)}|\cA_{-1}|}\cU_2+2K+C_{\rm Lips} K^2 \Delta_T+4\rbr{1-\delta}^{\floor{\frac{K}{M\useconstant{constant:go-back-root-length}}}}T.\qedhere \end{align}\]

16 Regret and Subgame Perfect Equilibrium↩︎

16.1 LRP-Regret and Subgame Perfect Equilibrium↩︎

In this section, we will prove that when all players get a sublinear \(R_T^{\rm local}\) even when the comparator can vary arbitrarily with \(P_T \mathrel{\vcenter{:}}= \sum_{t=2}^T \nbr{\hat{\bpi}\uo_t-\hat{\bpi}\uo_{t-1}}=O(T)\) and \(\bpi\ui\succeq \frac{\gamma}{|\cA_i|}\one\) for \(\gamma\in(0,1]\)¹², the equilibrium is actually an approximate SPNE.

In the following, we will only prove that player 1 cannot decrease their loss much by deviating, by the symmetry of players. For any \(\bh\in\cH_M\) and \(a_1\in\cA_1\), define \[\begin{align} &Q_t(\bh,a_1) \mathrel{\vcenter{:}}= \sum_{\ba_{-1}\in\cA_{-1}} \bpi_t^{(-1)}(\ba_{-1}\given \bh) \rbr{V_{t+1}((\bh_{2:M},(a_1,\ba_{-1})))+\cL_1((a_1,\ba_{-1}))},\\ &V_t(\bh) \mathrel{\vcenter{:}}= \sum_{\ba\in\cA} \bpi_t(\ba\given \bh) \rbr{V_{t+1}((\bh_{2:M},\ba))+\cL_1(\ba)}. \end{align}\] and \(V_{T_0+1}(\bh)=0\) for all \(\bh\in\cH_M\).

Then we have

The proof is postponed to the end of this section.

Note that \(R_{T}^{\rm local}\leq o(T)\) is the regret for player 1. The relation above can be extended to any player with their corresponding local regret on the right-hand side. With the lemma above, we can conclude subgame perfection.

For notational simplicity, we define \(f_i^m(\bpi|\mu) \mathrel{\vcenter{:}}= \sum_{\bh\in\cH}\mu(\bh)f_i^m(\bpi_{1:m+1}\given \bh)\) as a generalization of \(f_i^m(\bpi_{1:m+1}\given \bh)\). For an infinitely repeated matrix game as in Lemma 4, we can divide the \(T\) (\(T\to\infty\)) timesteps into \(K\) epochs, with \(T_0\) timesteps in each epoch.

The proof is deferred to Appendix 19.2.

Since when \(\bpi\ui\succeq\frac{\gamma}{|\cA_i|}\) we have \(\useconstant{constant:go-back-root-length}=1\), by Lemma 18, \[\begin{align} &\frac{1}{T-t_0+1}\sum_{t=t_0}^T \rbr{f_1^{t-t_0}(\bpi_{t_0:t}\given \bh_0)-f_1^{t-t_0}(\hat{\bpi}\uo_{t_0:t},\bpi\uno_{t_0:t}\given \bh_0)}\\ =& \frac{1}{T-t_0+1}\sum_{t=t_0}^{\ceil{t_0/T_0}T_0}\rbr{f_1^{t-t_0}(\bpi_{t_0:t}\given \bh_0)-f_1^{t-t_0}(\hat{\bpi}\uo_{t_0:t},\bpi\uno_{t_0:t}\given \bh_0)}\\ &+\frac{1}{T-t_0+1}\sum_{t=\ceil{t_0/T_0}T_0+1}^T \rbr{f_1^{t-t_0}(\bpi_{t_0:t}|\mu_0)-f_1^{t-t_0}(\hat{\bpi}\uo_{t_0:t},\bpi\uno_{t_0:t}|\mu_0)}\\ \overset{(i)}{=}&\frac{1}{T-t_0+1}\sum_{t=\ceil{t_0/T_0}T_0+1}^T \rbr{f_1^{t-t_0}(\bpi_{t_0:t}|\mu_0)-f_1^{t-t_0}(\hat{\bpi}\uo_{t_0:t},\bpi\uno_{t_0:t}|\mu_0)}\\ \overset{(ii)}{\leq}&\frac{\sum_{B=\ceil{t_0/T_0}+1}^{T/T_0} \epsilon_B}{T/T_0}+\frac{4M|\cA|^M}{T_0\gamma^{NM}}\overset{(iii)}{\leq}\frac{|\cA|^M}{\gamma^{NM}}\frac{R_{T_0}^{\rm local}}{T_0}+\frac{4M|\cA|^M}{T_0\gamma^{NM}}. \end{align}\] where \((i)\) is by \(T\to\infty\) and \((ii)\) is by Lemma 18 and \(T\to\infty\). \(\mu_0\) is the history distribution at timestep \(\ceil{t_0/T_0}T_0+1\) given \(\bh_0\) at timestep \(t_0\). \((iii)\) is because for any \(B=0,1,2,...,T/T_0\), by Lemma 11, we have \[\begin{align} \epsilon_B=&\frac{1}{T_0}\sum_{t=1}^{T_0} \rbr{f_1^{t-1}(\bpi_{1:t}|\mu_0)-f_1^{t-1}(\hat{\bpi}\uo_{1:t},\bpi\uno_{1:t}|\mu_0)}\\ =&\frac{1}{T_0}\sum_{t=1}^{T_0} \sum_{\bh_0\in\cH_M}\mu_0(\bh_0) \sum_{\bh\in\cH_{t-1}}\Pr(\bh\given \bh_0;\hat{\bpi}\uo_{1:t-1},\bpi\uno_{1:t-1})\\ &\cdot\inner{\bpi_t\uo(\cdot\given \bh_{t-M:t-1})-\hat{\bpi}_t\uo(\cdot\given \bh_{t-M:t-1})}{Q_t(\bh_{t-M:t-1},\cdot)}\\ \leq& \frac{1}{T_0}\sum_{t=1}^{T_0}\sum_{\bh_0\in\cH_M}\mu_0(\bh_0)\sum_{\bh\in\cH_{t-1}} \Pr(\bh\given \bh_0;\hat{\bpi}\uo_{1:t-1},\bpi\uno_{1:t-1})\max\cbr{\max_{\bh'\in\cH_M} \inner{\bpi_t\uo(\cdot\given \bh')-\hat{\bpi}_t\uo(\cdot\given \bh')}{Q_t(\bh',\cdot)},0}\\ \leq&\frac{|\cA|^M}{\gamma^{NM}}\frac{R_{T_0}^{\rm local}}{T_0}. \end{align}\] In the last line, we use Lemma 17.0◻

16.2 RP-Regret and SPNE↩︎

From the discussion above, since \(\bpi\ui\succeq\frac{\gamma}{|\cA_i|}\)¹⁵, by Lemma 18, we have \[\begin{align} &\frac{1}{T-t_0+1}\sum_{t=t_0}^T \rbr{f_1^{t-t_0}(\bpi_{t_0:t}\given \bh_0)-f_1^{t-t_0}(\hat{\bpi}\uo_{t_0:t},\bpi\uno_{t_0:t}\given \bh_0)}\\ \leq&\frac{\sum_{B=\ceil{t_0/T_0}+1}^{T/T_0} \epsilon_B}{T/T_0}+\frac{4M|\cA|^M}{T_0\gamma^{NM}} \end{align}\] by the discussion in Appendix 16.1. Then, \[\begin{align} \epsilon_B \mathrel{\vcenter{:}}= &\frac{1}{T_0}\sum_{t=1}^{T_0} \rbr{f_1^{t-1}(\bpi_{1:t}|\mu_0)-f_1^{t-1}(\hat{\bpi}\uo_{1:t},\bpi\uno_{1:t}|\mu_0)}\\ \overset{(i)}{\leq}&\frac{R_{T_0}}{T_0}\overset{(ii)}{\leq}\frac{O(T_0^p (P^B_{T_0})^q)}{T_0}~~~~~~~~~~(p+q=1,p<1). \end{align}\] where \((i)\) is by definition of RP-Regret and \((ii)\) is the condition of Lemma 3 (since RP-Regret is sublinear such \(p,q\) must exist). Note that we define \(P_{T_0}^B=\sum_{t=BT_0+2}^{(B+1)T_0} \nbr{\hat{\bpi}\uo_t-\hat{\bpi}\uo_{t-1}}_\infty\). So, \[\begin{align} &\frac{1}{T-t_0+1}\sum_{t=t_0}^T \rbr{f_1^{t-t_0}(\bpi_{t_0:t}\given \bh_0)-f_1^{t-t_0}(\hat{\bpi}\uo_{t_0:t},\bpi\uno_{t_0:t}\given \bh_0)}\\ \leq&\frac{\sum_{B=\ceil{t_0/T_0}+1}^{T/T_0} O(T_0^p (P_{T_0}^B)^q)}{T}+\frac{4M|\cA|^M}{T_0\gamma^{NM}}\\ \leq& O\rbr{\rbr{\frac{P_T}{T}}^q}+\frac{4M|\cA|^M}{T_0\gamma^{NM}}. \end{align}\] The last line is due to the concavity of function \(x^q(q<1)\). So, \(\frac{1}{N}\sum_{i=1}^N x_i^q\leq \rbr{\frac{\sum_{i=1}^N x_i}{N}}^q\).0◻

17 Finding Subgame Perfect Coarse Correlated Equilibrium in Repeated Games↩︎

17.1 Computation of SPCCE↩︎

We defer the proof to the latter part of this section. By Lemma 19, \(\max_{i=1,2,...,N}\frac{1}{T_0}\sum_{t=1}^{T_0} \rbr{V^{\bar\bpi_t}(\bh^1)-V^{\hat{\bpi}\ui,\bar\bpi\uni_t}(\bh^1)} \leq 8eK^2 \sqrt{\frac{\max_{i=1,2,...,N}|\cA_i|K}{T_0}}\) (\(e\) is the Euler’s number) in \(T_0\) iterations when all players apply Algorithm 4. Then, we will first sample a strategy \(\bpi_{t_0}\) uniformly from \(1,2,...,T_0\), for any horizon \(k\) (possibly larger than \(K\)), we choose \(\bpi_{t_0}(\given \bh^{(k-1)\% K+1})\) as the strategy for any \(\bh\in\cH_M\). Therefore, by Lemma 18 and following a similar proof as Theorem 3, we will get an \(O\rbr{\frac{1}{T_0^{2/7}}}\)-approximate \(O(T)\)-robust SPCCE. 0◻

Firstly, define \(\alpha_t^s=\alpha_s\prod_{j=s+1}^t (1-\alpha_j)\). Notice that \(\sum_{s=1}^t \alpha_t^s=1\). Then, we can define \(\bar\bpi_t\ui\) as the strategy sampled from \(\bpi_1\ui,\bpi_2\ui,...,\bpi_t\ui\) with probability \(\alpha_t^1,\alpha_t^2,...,\alpha_t^t\). We will first prove that \(\underline{V}_t(\bh^k)\leq V^{\hat{\bpi}\uo,\bar\bpi_t\uno}(\bh^k)\) for any \(\hat{\bpi}\uo\) in Lemma 21. Then, the regret is upper-bounded by \(\sum_{t=1}^T \rbr{V^{\bar\bpi_t}(\bh^k)-\underline{V}_t(\bh^k)}\), which can be proved to be upper-bounded by \(\sqrt T\).

18 Auxiliary Lemmas↩︎

In the following, we will prove Lemma 25. We prove that with the forgetful condition (Condition [assumption:2-forgetful]) on all agents, the past history will not affect much of the current action distribution, because all of the agents “forget" what the past history is.

18.1 Proof of Lemma 6↩︎

Firstly, \[\begin{align} &|f^m(\bpi)-f^m(\tilde{\bpi})|\notag\\ =&\Big|\sum_{\ba\in \cA} \cL_1(\ba)\sum_{\bh\in\cH_m} \Big(\Pr((\bh,\ba);\bpi)-\Pr((\bh,\ba);\tilde{\bpi})\Big) \Big|\notag\\ \leq& \sum_{\ba\in \cA}\Big|\sum_{\bh\in\cH_m} (\pi_{m+1}(\ba\given \bh)\Pr(\bh;\bpi)-\tilde{\pi}_{m+1}(\ba\given \bh)\Pr(\bh;\tilde{\bpi})) \Big|\notag\\ \leq&\sum_{\ba\in \cA}\Big|\sum_{\bh\in\cH_m} (\pi_{m+1}(\ba\given \bh)-\tilde{\pi}_{m+1}(\ba\given \bh))\Pr(\bh;\bpi) \Big|\tag{20}\\ &+\sum_{\ba\in \cA}\Big|\sum_{\bh\in\cH_m} (\Pr(\bh;\bpi)-\Pr(\bh;\tilde{\bpi}))\tilde{\pi}_{m+1}(\ba\given \bh) \Big|.\tag{21} \end{align}\] Term 20 is bounded by \[\begin{align} &\sum_{\ba\in \cA}\Big|\sum_{\bh\in\cH_m} (\pi_{m+1}(\ba\given \bh)-\tilde{\pi}_{m+1}(\ba\given \bh))\Pr(\bh;\bpi)\Big|\\ =&\sum_{\ba\in \cA}\Big|\inner{\pi_{m+1}(\ba\given \bh)-\tilde{\pi}_{m+1}(\ba\given \bh)}{\Pr(\bh;\bpi)}_{\bh\in\cH_m}\Big|\\ \leq& \sum_{\ba\in \cA}\nbr{(\pi_{m+1}(\ba\given \bh)-\tilde{\pi}_{m+1}(\ba\given \bh))_{\bh\in\cH_m}}_\infty\cdot \nbr{(\Pr(\bh;\bpi))_{\bh\in\cH_m}}_1\\ \leq& \sum_{\ba\in \cA}\nbr{(\pi_{m+1}(\ba\given \bh)-\tilde{\pi}_{m+1}(\ba\given \bh))_{\bh\in\cH_m}}_\infty\\ \leq& |\cA|\cdot \nbr{(\pi_{m+1}(\ba\given \bh)-\tilde{\pi}_{m+1}(\ba\given \bh))_{\ba\in\cA,\bh\in\cH_m}}_\infty. \end{align}\]

For the term 21 , for a fixed \(\ba\in\cA\), we have \[\begin{align} &\Big|\sum_{\bh\in\cH_m}\tilde{\pi}_{m+1}(\ba\given \bh) \Big(\Pr(\bh;\bpi)-\Pr(\bh;\tilde{\bpi})\Big)\Big|\\ =&\Big|\sum_{\bh\in\cH_m}\tilde{\pi}_{m+1}(\ba\given \bh) \Big(\prod_{s=1}^{m} \pi_s(\bh_s\given \bh_{1:s-1})-\prod_{s=1}^{m} \tilde{\pi}_s(\bh_s\given \bh_{1:s-1})\Big)\Big|\\ =& \Big|\sum_{\bh\in\cH_m}\tilde{\pi}_{m+1}(\ba\given \bh) \sum_{k=1}^{m}\Big(\prod_{s=1}^{m} \bar \pi_s^{k-1}(\bh_s\given \bh_{1:s-1})-\prod_{s=1}^{m} \bar \pi_s^{k}(\bh_s\given \bh_{1:s-1})\Big)\Big|\\ \leq& \sum_{k=1}^{m}\Big|\sum_{\bh\in\cH_m}\tilde{\pi}_{m+1}(\ba\given \bh) \Big(\prod_{s=1}^{m} \bar \pi_s^{k-1}(\bh_s\given \bh_{1:s-1})-\prod_{s=1}^{m} \bar \pi_s^{k}(\bh_s\given \bh_{1:s-1})\Big)\Big| \end{align}\] where \[\begin{align} \bar \bpi^{k}_s= \begin{cases} \bpi_s&s>k\\ \tilde{\bpi}_s&s\leq k. \end{cases} \end{align}\]

For any \(k\in\{1,2,...,m\}\), we have \[\begin{align} &\Big|\sum_{\bh\in\cH_m}\tilde{\pi}_{m+1}(\ba\given \bh) \Big(\prod_{s=1}^{m} \bar \pi_s^{k-1}(\bh_s\given \bh_{1:s-1})-\prod_{s=1}^{m} \bar \pi_s^{k}(\bh_s\given \bh_{1:s-1})\Big)\Big|\\ =& \Big|\sum_{\bh\in\cH_m}\tilde{\pi}_{m+1}(\ba\given \bh) \prod_{s=1,s\not=k}^m \bar \pi_s^{k}(\bh_s\given \bh_{1:s-1})\Big(\pi_k(\bh_k\given \bh_{1:k-1})- \tilde{\pi}_k(\bh_k\given \bh_{1:k-1})\Big)\Big|\\ =&\Big|\inner{\prod_{s=1,s\not=k}^m \bar \pi_s^{k}(\bh_s\given \bh_{1:s-1})}{\tilde{\pi}_{m+1}(\ba\given \bh)(\pi_k(\bh_k\given \bh_{1:k-1})- \tilde{\pi}_k(\bh_k\given \bh_{1:k-1}))}_{\bh\in\cH_m}\Big|\\ \leq&\nbr{\rbr{\prod_{s=1,s\not=k}^m \bar \pi_s^{k}(\bh_s\given \bh_{1:s-1})}_{\bh\in\cH_m}}_1 \cdot \nbr{\rbr{\tilde{\pi}_{m+1}(\ba\given \bh)(\pi_k(\bh_k\given \bh_{1:k-1})- \tilde{\pi}_k(\bh_k\given \bh_{1:k-1}))}_{\bh\in\cH_m}}_\infty\\ =& |\cA|\cdot \nbr{\rbr{\pi_k(\bh_k\given \bh_{1:k-1})- \tilde{\pi}_k(\bh_k\given \bh_{1:k-1})}_{\bh\in\cH_m}}_\infty. \end{align}\] Therefore, term 21 is bounded by \[\begin{align} \sum_{\ba\in \cA}\Big|\sum_{\bh\in\cH_m} (\Pr(\bh;\bpi)-\Pr(\bh;\tilde{\bpi}))\tilde{\pi}_{m+1}(\ba\given \bh) \Big|\leq& |\cA|^2\cdot\sum_{k=1}^m \nbr{\rbr{\pi_k(\bh_k\given \bh_{1:k-1})- \tilde{\pi}_k(\bh_k\given \bh_{1:k-1})}_{\bh\in\cH_m}}_\infty. \end{align}\]

Finally, \[\begin{align} &|f^m(\bpi)-f^m(\tilde{\bpi})|\\ \leq& |\cA|\cdot \nbr{(\pi_{m+1}(\ba\given \bh)-\tilde{\pi}_{m+1}(\ba\given \bh))_{\ba\in\cA,\bh\in\cH_m}}_\infty+|\cA|^2\cdot\sum_{k=1}^m \nbr{\rbr{\pi_k(\bh_k\given \bh_{1:k-1})- \tilde{\pi}_k(\bh_k\given \bh_{1:k-1})}_{\bh\in\cH_m}}_\infty\\ \leq&|\cA|^2\cdot\sum_{k=1}^{m+1} \nbr{\bpi_k-\tilde{\bpi}_k}_\infty. \end{align}\] For the second part, since for any \(\bh\in\cH,\ba\in\cA,k=1,2,...,m+1\), we have \[\begin{align} |\pi_k(\ba\given \bh)-\tilde{\pi}_k(\ba\given \bh)|=&\abr{\prod_{i=1}^N \pi_k\ui(a_i\given \bh)-\prod_{i=1}^N \tilde{\pi}_k\ui(a_i\given \bh)}\\ =&\abr{\sum_{i=1}^N \prod_{j=1}^{i-1} \tilde{\pi}_k^{(j)}(a_j\given \bh) \prod_{j=i+1}^N \pi_k^{(j)}(a_j\given \bh) \rbr{\pi_k\ui(a_i\given \bh)-\tilde{\pi}_k\ui(a_i\given \bh)}}\\ \leq& \sum_{i=1}^N \prod_{j=1}^{i-1} \tilde{\pi}_k^{(j)}(a_j\given \bh) \prod_{j=i+1}^N \pi_k^{(j)}(a_j\given \bh) \abr{\pi_k\ui(a_i\given \bh)-\tilde{\pi}_k\ui(a_i\given \bh)}\\ \leq& \sum_{i=1}^N \abr{\pi_k\ui(a_i\given \bh)-\tilde{\pi}_k\ui(a_i\given \bh)}. \end{align}\] As a consequence, \[|f^m(\bpi)-f^m(\tilde{\bpi})|\leq C_{\rm Lips}\sum_{t=1}^{m+1}\nbr{\bpi_t-\tilde{\bpi}_t}_\infty\leq C_{\rm Lips}\sum_{i=1}^N\sum_{t=1}^{m+1}\nbr{\bpi_t\ui-\tilde{\bpi}_t\ui}_\infty.\] where \(C_{\rm Lips} \mathrel{\vcenter{:}}= |\cA|^2\). 0◻

18.2 Lemma for Markov Game↩︎

18.3 Other Lemmas↩︎

18.4 Projected Gradient Descent (PGD)↩︎

Here we provide the upper bound on the regret \(\sum_{t=1}^T \inner{\cL_t}{\bx_t}-\min_{\hat{\bx}_{1:T},\hat{\bx}_t\in\cX}\sum_{t=1}^T \inner{\cL_t}{\hat{\bx}_t}\). We adapted [22] here.

18.5 Projected Gradient Descent with Time-varying Constraints↩︎

19 Auxiliary Lemmas for the Induced Markov Game↩︎

In this section, we assume all agents have a bounded memory \(M\) and we are considering the Induced Markov Game defined in Definition 1.

19.1 Milder Constraint↩︎

It is easy to see that Condition [assumption:2-forgetful-prime] implies the following condition, Condition [assumption:L1-forgetful]. Therefore, in this section, we will show that when all players satisfy Condition [assumption:L1-forgetful], we can use the expected average loss of an infinite-horizon Markov game to approximate the expected loss of the repeated game at each timestep.

A direct corollary of Condition [assumption:L1-forgetful] is that

For the Markov chain¹⁶ induced by \(\bpi\), let \(\cP^{\bpi}\) be the transition matrix. Then we have the following lemma.

19.2 Fast Mixing↩︎

Firstly, we will prove a set of results in the Markov chain with transition matrix \((\cP^{\bpi})^M\). For simplicity, we model it as a directed graph, with vertices as \(\cH_M\). There exists a directed edge \(\bh_1\to\bh_2\) if and only if \((\cP^{\bpi})^M_{\bh_1,\bh_2}\geq (\frac{\gamma^N}{|\cA|})^M\).

Note that by Lemma 31, for every two vertices \(\bh_1,\bh_2\) in the graph, there exists a vertex \(\bh_3\) (might be equal to \(\bh_1\) or \(\bh_2\)), which is a common successor of \(\bh_1\) and \(\bh_2\). That is, there exist edges \(\bh_1\to\bh_3\) and \(\bh_2\to\bh_3\).

Firstly, we would like to prove that there exists a vertex \(\bh_0\in\cH_M\), which satisfies that every other vertex could reach it within \(O(\log_2 |\cH_M|)\) steps.

By Lemma 32, we can obtain a rooted tree, say rooted at \(\bh_0\), with a bounded depth \(O(\log_2 |\cH_M|)\).

Back to the Markov chain, by Lemma 33, for any \(\bh_1\in\cH_M\), we have \((\cP^{\bpi})^{MK}_{\bh_1,\bh_0}\geq (\frac{\gamma^N}{|\cA|})^{MK}\) for any \(K\geq \useconstant{constant:go-back-root-length}\).

19.3 Contraction property with bounded memory of length \(M\)↩︎

In this section, we will directly adopt all conditions and notations in Appendix 19.2 without specifying them.

By Lemma 33, there exists some constant \(\useconstant{constant:go-back-root-length}\) so that \((\cP^{\bpi})^{M\useconstant{constant:go-back-root-length}}_{\bh_1,\bh_0}\geq (\frac{\gamma^N}{|\cA|})^{M\useconstant{constant:go-back-root-length}}\). For any \(\bpi\uo\), the transition matrix of the induced Markov chain can be written as \[\begin{align} &(\cP^{\bpi})^{M\useconstant{constant:go-back-root-length}}=\delta\underbrace{\begin{bmatrix} 1 & 0&...&0\\ 1 & 0&...&0\\ ...&...&...&...\\ 1 & 0&...&0\\ \end{bmatrix}}_{\cU}+(1-\delta)\hat{\cP}^{\bpi}\tag{22}\\ &\delta \mathrel{\vcenter{:}}= (\frac{\gamma^N}{|\cA|})^{M\useconstant{constant:go-back-root-length}}\tag{23} \end{align}\] where \(\hat{\cP}^{\bpi}\) is also a Markov matrix and we assume the index of \(\bh_0\) is 1 without loss of generality (\(\bh_0\) is defined in Lemma 33 and we will use \(\bh_0\) to denote it in this section by default). So, the distribution \((1,0,...,0)\) places probability one on \(\bh_0\).

Notice that for any initial distribution \(\mu\in\Delta_{|\cH_M|}\), we have \(\mu\cU=(1,0,...,0)=:\bo\). Therefore, we have the following lemma.

A direct consequence of Lemma 34 is that the average probability distribution of the state will also converge.

References↩︎

---

1. Accepted for presentation at the Conference on Learning Theory (COLT) 2026.↩︎

2. Alphabetical Order↩︎

3. For the classical examples of (Iterated) Prisoner’s Dilemma and Stag-Hunt, we follow the convention of using the term utility; later when defining regret notions, we will follow the convention from online learning and use the term loss throughout.↩︎

4. To follow the convention of online learning, we use loss instead of utility/payoff in the rest of the paper.↩︎

5. We are aware that there is another definition of adaptive regret [15]–[17], which refers to the maximum external regret over all intervals \([r,s]\subseteq [T]\). However, given the context of this paper, we will only discuss the adaptive regret for repeated games.↩︎

6. The expected time-average loss always exists and does not depend on the initial distribution when strategies of all players satisfy Condition [assumption:2-forgetful] (see Lemma 26 for a formal proof).↩︎

7. \(\mu_0\) is omitted here since \(\bq^{\pi}\) is invariant to the initial distribution under Condition [assumption:2-forgetful]. Please refer to Appendix 19.1 for a detailed discussion.↩︎

8. In fact, this lemma also holds when all players satisfy a weaker condition (cf. Condition [assumption:L1-forgetful] in the Appendix).↩︎

9. Folk theorem gives a way to construct “trigger" strategies. Specifically, if one of the players deviates, say player 1, then other players will also change their strategy to the minimax one, to guarantee player 1 will suffer at least \(\min_{\bpi\uno}\max_{\bpi\uo} \cL_1(\bpi\uo,\bpi\uno)\) loss in every later timestep. Therefore, no player can benefit from deviation if all of them can obtain a lower loss than their minimax loss.↩︎

10. At each timestep, the learner takes one step of gradient descent according to the loss at the last timestep.↩︎

11. Condition [assumption:1-variation] on the strategy generated by the regret minimizer is neither an assumption nor a pre-defined condition, but a property that our regret minimization algorithm should have, as to be detailed later in §4.↩︎

12. Our regret minimization algorithm guarantees sublinear regret when \(P_T=o(T)\) in the adversarial online setting. It is unknown whether we can still achieve sublinear regret when \(P_T=O(T)\) in the game setting, where we can control all players.↩︎

13. The joint-strategy version of Condition [assumption:L1-forgetful] is \(\forall \bar\bh,\tilde{\bh}\in\cH,~~~~~\frac{1}{2}\nbr{\bpi_k(\cdot\given\bar\bh)-\bpi_k(\cdot|\tilde{\bh})}_1\leq 1-\gamma\).↩︎

14. The reason that Lemma 4 only holds when \(P_T=O(T)\) is that the variation of \(\underline\bpi_{1:T}\) may be linear in \(T\) by the construction described above.↩︎

15. In fact, here we do not necessarily require this. Satisfying Condition [assumption:L1-forgetful] is enough.↩︎

16. By taking \(\bpi\) as constant and merging it into the transition probability, we get a Markov chain from the induced Markov game defined in Definition 1.↩︎