Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

AND Ya-Ping P Hsieh
email: yaping.hsieh@inf.ethz.ch

AND Volkan Cevher
email: volkan.cevher@epfl.ch.2020

Victor Boone

Pierre-Louis Cauvin

Angeliki Giannou

Kyriakos Lotidis

Sylvain Sorin

Manolis Vlatakis

A UNIFIED STOCHASTIC APPROXIMATION FRAMEWORK FOR LEARNING IN GAMES

Keywords: Mathematics Subject Classification. Primary 91A10, 91A26, secondary 68Q32, 68T02 Nash equilibrium, continuous games, finite games, stochastic approximation, variational stability, primal attractors, coherence

We develop a flexible stochastic approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite). The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, the exponential / multiplicative weights algorithm for learning in finite games, optimistic and bandit variants of the above, etc. In addition to providing an integrated view of these algorithms, our framework further allows us to obtain several new convergence results, both asymptotic and in finite time, in both continuous and finite games. Specifically, we provide a range of criteria for identifying classes of Nash equilibria and sets of action profiles that are attracting with high probability, and we also introduce the notion of coherence, a game-theoretic property that includes strict and sharp equilibria, and which leads to convergence in finite time. Importantly, our analysis applies to both oracle-based and bandit, payoff-based methods -that is, when players only observe their realized payoffs.

Introduction

The prototypical setting of online learning in games can be summarized as follows:

(1) At each stage of a repeated decision process, every player selects an action.

(2) The players receive a reward determined by their chosen actions and their individual payoff functions -assumed a priori unknown.

(3) Based on these payoffs and any other observed information, the players update their actions and the process repeats.

A key question that arises in this general setting is whether the players eventually settle down to a stable profile from which no player has an incentive to deviate. Put differently:

Does the players' learning process converge to a Nash equilibrium? This question has been at the forefront of game-theoretic research ever since the field's earliest steps, and it has recently received renewed attention owing to its connection to data science, multi-agent reinforcement learning, networks, and many other applications where agents are called to make decisions under uncertainty. The first positive answer here was 2. Characterization of attractors: We further show that sets that admit a local energy function (relative to the mean dynamics mentioned above) are attracting with high probability -or globally attracting with probability 1, depending on the energy function.

As a corollary of this result, we readily infer convergence to Nash equilibrium in all strictly monotone games, and we likewise derive a series of high probability convergence results to equilibria that satisfy a certain variational stability requirement.

3. Fast convergence to coherent sets: Finally, we introduce the notion of coherence -an algorithm-agnostic concept which covers strict Nash equilibria in finite games, sharp equilibria in continuous games, linear programs, etc. -and we show that RRM methods converge to such sets under significantly weaker conditions for their runtime parameters (step-size, sampling radius, etc.). In addition, we show that projection-based methods (as opposed to interior-valued ones) converge to coherent sets in a finite number of iterations.

An appealing feature of our analysis is that it applies to both first-order ("oracle-based") and zeroth-order ("payoff-based" or "bandit") methods. More to the point, our results can be easily adapted to many other learning algorithms in the literature, reducing in this way the number of ad hoc elements required to analyze a given method. Of course, given the breadth of the relevant literature, it is impossible to include here all methods covered by the proposed RRM template -or that could be covered modulo minor modifications. Our choice of examples is only meant to illustrate different trends in the literature, and to show how some algorithms that initially seem unrelated -like the dampened gradient approximation (DGA) method of [START_REF] Bervoets | Learning with minimal information in continuous games[END_REF] -can be included in our framework.

Paper outline. In Section 2, we introduce the game-theoretic background of our work, including the various solution concepts that we use throughout our paper (critical points, Nash equilibria, variationally stable states, etc.). Subsequently, in Section 3, we introduce a range of well-known algorithms for learning in games, and we show how they can be seen as special instances of the RRM blueprint. Our analysis proper begins in Section 4, where we introduce the notion of subcoercivity and present our ICT convergence results. Subsequently, in Sections 5 and 6, we state and prove our main convergence results for stochastically attracting and coherent sets respectively.

Preliminaries

Notation. In what follows, V will denote a d-dimensional real space with norm ∥•∥. We will also write Y := V * for the dual space of V, ⟨y, x⟩ for the canonical pairing between y ∈ Y and x ∈ V, and ∥y∥ * := max{⟨y, x⟩ : ∥x∥ ≤ 1} for the induced dual norm on Y. As is customary, if V is Euclidean, we will not distinguish between primal and dual vectors. Finally, if f : V → R ∪ {∞} is a convex function on V, we will write dom f := {x ∈ V : f (x) < ∞} for its effective domain, ∂f (x) := {y ∈ Y : f (x ′ ) ≥ f (x) + ⟨y, x ′ -x⟩ for all x ′ ∈ V} for the subdifferential of f at x, and dom ∂f := {x ∈ V : ∂f (x) ̸ = ∅} for the domain of subdifferentiability of f . 2.1. Games in normal form. Throughout the sequel, we will focus on games with a finite number of players i ∈ N = {1, . . . , N }, each selecting an action x i from some closed convex subset X i of a d i -dimensional normed space V i . Gathering all players together, we will write X = i X i for the space of all action profiles x = (x i ) i∈N and d = i d i for the dimension of the ambient space V = i V i . Finally, when we want to distinguish between the action of the i-th player and that of all other players, we will employ the shorthand (x i ; x -i ).

Given an action profile x ∈ X , each player i ∈ N is assumed to receive a reward u i (x) ≡ u i (x i ; x -i ) based on an associated payoff function u i : X → R. In terms of regularity, we will tacitly assume that u i is differentiable and we will write

v i (x) = ∇ xi u i (x i ; x -i ) and v(x) = (v i (x)) i∈N (1)
for the players' individual payoff gradients and the ensemble thereof. Finally, unless explicitly mentioned otherwise, we will treat each v i (x) as an element of the corresponding dual space Y i = V * i of V i , and we will make the following blanket assumption: Assumption 1. The players' payoff functions are Lipschitz continuous and smooth, i.e., there exist constants G i , L i ≥ 0, i ∈ N , such that

|u i (x ′ ) -u i (x)| ≤ G i ∥x ′ -x∥ and ∥∇u i (x ′ ) -∇u i (x)∥ * ≤ L i ∥x ′ -x∥.
(

) 2
for all x, x ′ ∈ X , i ∈ N . For concision, we will also write G := max i G i and L := max i L i .

A continuous game in normal form is then defined as a tuple G ≡ G(N , X , u) with players, actions and payoff functions as above. For concreteness, we provide some examples below:

Example 2.1 (Min-max games). Consider two players i ∈ {1, 2} with action spaces X 1 and X 2 , and payoff functions u 1 = -L = -u 2 for some smooth function L : X 1 × X 2 → R. Player 1 (the "min" player) seeks to minimize L = -u 1 whereas Player 2 (the "max" player) seeks to maximize L = u 2 . In many applications, L is (strictly) convex-concave, in which case von Neumann's theorem asserts that the game min x1∈X1 max x2∈X2 L(x 1 , x 2 ) always admits a solution if X 1 × X 2 is compact. ♢ Example 2.2 (Cournot oligopolies). Consider N firms supplying the market with a quantity x i ∈ [0, C i ] of some good up to each firm's capacity C i . The good is priced as a function P (x) = a -b N i=1 x i of the total quantity of the good in the market, so the net utility of the i-th firm is u i (x) = x i P (x) -c i x i where a, b and c i are market-related positive constants. The resulting game G(N , X , u) is known as a Cournot competition game and it plays a central role in economic theory. ♢ Example 2.3 (Finite games). In a finite game Γ ≡ Γ(N , A, u), each player i ∈ N chooses an action α i from some finite set A i ; the players' payoffs are then determined by the action profile α = (α 1 , . . . , α N ) ∈ A := i A i and an ensemble of payoff functions u i : A → R, i = 1, . . . , N . In the mixed extension of Γ, a player may pick an action according to a probability distribution x i ∈ ∆(A i ): this is known as a mixed strategy, and the corresponding mixed payoff to the i-th player is u i (x) = α∈A x α u i (α) where x α = i x iαi is the probability of the action profile α = (α 1 , . . . , α N ).

Letting X i = ∆(A i ), the mixed extension of Γ is defined as the continuous game ∆(Γ) = G(N , X , u). For posterity, we note here that the "payoff gradient" of each player i ∈ N is simply their mixed payoff vector, i.e., v i (x) = ∇ xi u i (x) = (u i (α i ; x -i )) αi∈Ai . ♢ 2.2. Solution concepts. The standard solution concept in game theory is that of a Nash equilibrium, i.e., an action profile that is resilient to unilateral deviations. Formally, x * ∈ X is a Nash equilibrium of a game G ≡ G(N , X , u) if

u i (x * ) ≥ u i (x i ; x * -i ) for all x i ∈ X i , i ∈ N . (NE)
Nash equilibria always exist if X is compact and each u i is individually concave in x i [START_REF] Debreu | A social equilibrium existence theorem[END_REF]. Otherwise, equilibria may not exist, in which case the following relaxations become relevant:

(1) Local Nash equilibria, i.e., profiles x * ∈ X for which (NE) holds locally:

u i (x * ) ≥ u i (x i ; x * -i ) for all x in a neighborhood U of x * in X . (LNE)
(2) Critical points, i.e., profiles x * ∈ X that satisfy the first-order stationarity condition:

d dt t=0 + u i (x * i + t(x i -x * i ); x * -i ) ≤ 0 for all x i ∈ X i , i ∈ N . (FOS)
Equivalently, (FOS) can be reformulated as a Stampacchia variational inequality of the form

⟨v(x * ), x -x * ⟩ ≤ 0 for all x ∈ X . (SVI)
The solutions of (SVI) are precisely the fixed points of the "linearized" best-response correspondence x → arg max x ′ ∈X ⟨v(x), x ′ ⟩ so, by standard fixed point arguments, the set of critical points of G is always nonempty if X is compact. Dually to the above, the Minty variational inequality associated to G is

⟨v(x), x -x * ⟩ ≤ 0 for all x ∈ X . (MVI)
It is straightforward to verify that the solutions of (MVI) comprise a convex set of Nash equilibria of G, so (MVI) can be seen as an equilibrium refinement criterion for G. Taking this a step further, a state x * ∈ X is said to be variationally stable if

⟨v(x), x -x * ⟩ < 0 for all x ̸ = x * in a neighborhood U of x * in X (VS)
and x * is called neutrally stable if the strict inequality "<" in (VS) is relaxed to "≤", i.e., if

⟨v(x), x -x * ⟩ ≤ 0 for all x in a neighborhood U of x * in X . (NS)
Finally, we say that x * is globally variationally stable [resp. globally neutrally stable] if (VS) [resp. (NS)] holds with U = X (i.e., for all x ∈ X ).

In general, the solution concepts discussed above are related as follows:

(GVS) (GNS) ≡ (MVI) (NE) (VS) (NS) (LNE) (FOS) ≡ (SVI) =⇒ =⇒ =⇒ =⇒ =⇒ =⇒ =⇒ =⇒ (3)
Without further assumptions, the implications in (3) are all one-way; in the next section, we discuss a number of cases where some (or all) of these implications become equivalences.

Remark 1. In the optimization literature, the direction of (SVI) / (MVI) is reversed because optimization problems are usually stated in terms of cost minimization. The maximization viewpoint is more common in games, so we will maintain the "≤" direction throughout. ♢ Remark 2. The notion of variational stability was introduced in [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] and echoes the seminal concept of evolutionary stability as introduced by Maynard Smith & Price [START_REF] Smith | The logic of animal conflict[END_REF] in the context of population games. Informally, "variational stability" is to games with a finite number of players and a continuum of actions what "evolutionary stability" is to games with a continuum of players and a finite number of actions; for an in-depth discussion, cf. [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF]. ♢ 2.3. Special cases of interest. We close this section with a discussion of some special cases and examples of the above definitions that will play a major role in the sequel.

▶ Monotone games. A game is monotone if it satisfies the monotonicity condition

⟨v(x ′ ) -v(x), x ′ -x⟩ ≤ 0 for all x, x ′ ∈ X . (Mon)
The strict version of this requirement (i.e., that equality holds if and only if x = x ′ ) is sometimes referred to as diagonal strict concavity (DSC), a terminology due to Rosen [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N -person games[END_REF].

In monotone games, the solutions of (MVI) and (SVI) coincide, leading to the string of equivalences (MVI)

⇐⇒ (NE) ⇐⇒ (LNE) ⇐⇒ (FOS) ≡ (SVI) (4)
By comparison, if a game is strictly monotone, every implication in (3) becomes an equivalence, so the game admits a unique, globally variationally stable Nash equilibrium. Examples 2.1 and 2.2 are both strictly monotone (assuming L is strictly convex-concave in Example 2.1); other examples include socially concave games [START_REF] Even-Dar | On the convergence of regret minimization dynamics in concave games[END_REF], Cournot oligopolies [START_REF] Monderer | Potential games[END_REF], Kelly auctions [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF][START_REF] Tullock | Efficient rent seeking[END_REF], congestion control [START_REF] Even-Dar | On the convergence of regret minimization dynamics in concave games[END_REF], and many other classes of problems.

▶ Potential games. First formalized by Monderer & Shapley [START_REF] Monderer | Potential games[END_REF], potential games admit a potential function Φ : X → R such that [START_REF] Rosenthal | A class of games possessing pure-strategy Nash equilibria[END_REF], power allocation in wireless networks [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory in multiuser communication systems[END_REF], etc.

u i (x i ; x -i ) -u i (x ′ i ; x -i ) = Φ(x i ; x -i ) -Φ(x ′ i ; x -i ) for all x, x ′ ∈ X and all i ∈ N . (Pot) If G is a potential game, we have v(x) = ∇Φ(x) so a)
▶ Second-order stationarity. Our next example concerns critical points that satisfy a condition similar to second-order sufficient conditions in optimization, namely

z ⊤ Jac v (x * )z < 0 for all nonzero tangent vectors z to X at x * (SOS)
where Jac v (x * ) denotes the Jacobian of v at x * . In the context of saddle-point problems and continuous games, this condition has been studied extensively in the machine learning and control literatures, cf. [START_REF] Giannou | On the convergence of policy gradient methods to Nash equilibria in general stochastic games[END_REF][START_REF] Hsieh | On the convergence of single-call stochastic extra-gradient methods[END_REF][START_REF] Mertikopoulos | On the almost sure convergence of stochastic gradient descent in non-convex problems[END_REF][START_REF] Ratliff | On the characterization of local Nash equilibria in continuous games[END_REF][START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N -person games[END_REF]] and references therein. Importantly, as we note below, (SOS) is a special case of (VS).

Proposition 1 (Hsieh et al., 2019, Lemma A.4). Let x * be a critical point of G satisfying (SOS). Then x * is variationally stable.

▶ Finite games. As a last example, let G = ∆(Γ) be the mixed extension of a finite game Γ ≡ Γ(N , A, u). Since each player's payoff function u i (x i ; x -i ) is linear in x i , we readily get

(NE) ⇐⇒ (LNE) ⇐⇒ (FOS) ≡ (SVI) (5)
In addition, we have the following characterization of stable states in finite games: We will use all this freely in the sequel.

The learning framework

We now proceed to detail our online learning framework, beginning with the general model in Section 3.1 and continuing with a range of learning algorithms that can be seen as special cases thereof in Section 3.2. The reader interested only in the general theory can skip Section 3.2.

3.1. Regularized Robbins-Monro processes. Our basic learning framework will hinge on the regularized Robbins-Monro template

Y n+1 = Y n + γ n vn X n+1 = Q(Y n+1 ), (RRM)
where:

(1) X n = (X i,n ) i∈N ∈ X denotes the players' action profile at each stage n = 1, 2, . . .

(2) vn = (v i,n ) i∈N ∈ Y is a sequence of individual "gradient-like" signals. (3) Y n = (Y i,n
) i∈N ∈ Y is an auxiliary state variable aggregating individual gradient steps.

(4) γ n > 0 is a step-size sequence, for which we will assume throughout that n γ n = ∞ (typically the method is run with γ n ∝ 1/n ℓγ for some ℓ γ ≥ 0).

(5) Q : Y → X is a "generalized projection" map that mirrors gradient steps in Y to action updates in X ; we will refer to Q throughout as the players' mirror map.

As far as terminology is concerned, the term "Robbins-Monro" refers to the seminal stochastic approximation method of Robbins & Monro [START_REF] Robbins | A stochastic approximation method[END_REF], while the adjective "regularized" alludes to the "follow-the-regularized-leader" (FTRL) family of algorithms of Shalev-Shwartz & Singer [START_REF] Shalev-Shwartz | Convex repeated games and Fenchel duality[END_REF] -which, in turn, is intimately related to the mirror descent (MD) framework of Nemirovski & Yudin [START_REF] Nemirovski | Problem Complexity and Method Efficiency in Optimization[END_REF]. To streamline our presentation, we detail each of these elements below and defer a list of examples to Section 3.2.

▶ The sequence of gradient signals. To keep track of the sequence of events in (RRM), we will view X n as a stochastic process on some complete probability space (Ω, F, P), and we will write F n := F(X 1 , . . . , X n ) ⊆ F for the history of play up to stage n (inclusive). Since we tacitly assume that vn is generated after each player has selected an action at round n but before the (n + 1)-th update has been triggered, we also posit that vn is F n+1 -measurable but not necessarily F n -measurable. In this way, we may decompose vn as

vn = v(X n ) + U n + b n (6)
where

U n = vn -E[v n | F n ] and b n = E[v n | F n ] -v(X n ). (7)
Since E[U n | F n ] = 0 by construction, U n can be intepreted as a random, zero-mean error relative to v(X n ); by contrast, b n is F n -measurable, so it captures any systematic -and possibly non-random -offset of vn relative to v(X n ). We will quantify all this by assuming that b n , U n and vn are bounded for some q ≥ 2 as

E[∥b n ∥ * | F n ] ≤ B n E[∥U n ∥ q * | F n ] ≤ σ q n and E[∥v n ∥ q * | F n ] ≤ M q n ( 8
)
where the sequences B n , σ n and M n , n = 1, 2, . . . , are to be construed as deterministic upper bounds on the bias, fluctuations, and magnitude of vn respectively (with the case q = ∞ taken to mean that the various quantites are bounded w.p.1). Accordingly, depending on these bounds, a gradient signal with B n = 0 will be called unbiased, and an unbiased signal with σ n = 0 will be called perfect.

Remark 1. We should stress here that vn should not be interpreted narrowly as the output of a black-box oracle for v(X n ), but as a "model-agnostic" surrogate thereof. In particular, the noise term U n can model raw observational noise, but also inner randomizations of the algorithm; analogously, the bias term b n is intended to capture situations where vn results from actions other than X n , the inclusion of corrective terms in a learning algorithm, etc. These modeling aspects are crucial to include in our analysis optimistic and extra-gradient methods; we explain this issue in detail in Section 3.2.

♢

Remark 2. By Assumption 1 and the inequality ( m i=1 a i ) q ≤ m q-1 m i=1 a q i , the decomposition [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF] of vn shows that we can always pick M q n = 3 q-1 (G q + B q n + σ q n ) in [START_REF] Bervoets | Learning with minimal information in continuous games[END_REF]. This makes the last part of (8) redundant, but we will maintain the explicit bound M n for vn to simplify the presentation. ♢ ▶ The players' mirror map. The second defining element of (RRM) is the "mirror map" Q i : Y i → X i of each player -or, in aggregate form, the product map Q = (Q i ) i∈N : Y → X . This is defined by means of a "regularizer " on X as follows: 1 Definition 1. We say that h i : V i → R ∪ {∞} is a regularizer on X i if:

(1) h i is supported on X i , i.e., dom

h i = {x i ∈ V i : h i (x i ) < ∞} = X i .
(2) h i is continuous and strongly convex on X i , i.e., there exists a constant K i > 0 such that

h i (λx i + (1 -λ)x ′ i ) ≤ λh i (x i ) + (1 -λ)h i (x ′ i ) -1 2 K i λ(1 -λ)∥x ′ i -x i ∥ 2 (9)
for all x i , x ′ i ∈ X i and all λ ∈ [0, 1]. The mirror map associated to h i is defined for all y i ∈ Y i as

Q i (y i ) = arg max xi∈Xi {⟨y i , x i ⟩ -h i (x i )} (10)
and the image

X hi = im Q i of Q i is called the prox-domain of h i .
Finally, we will also say that h i is steep when dom ∂h i = ri X i .

For concision, we will write h(x) = i h i (x i ) for the players' aggregate regularizer and Q = (Q i ) i∈N for the induced mirror map. We provide three examples of this construction below:

Example 3.1 (Euclidean projection). Consider the quadratic regularizer h(x) = ∥x∥ 2 2 /2, x ∈ X . Then the induced mirror map is the standard Euclidean projector

Q(y) = Π X (y) ≡ arg min x∈X ∥y -x∥ 2 . (11)
As a special case, in unconstrained settings (i.e., when X = V), we have Q(y) = y.

Example 3.2 (Entropic regularization on the simplex). Let A i , i = 1, . . . , N , be an ensemble of pure strategies, set X i = ∆(A i ), and let h i (x i ) = αi∈Ai x iαi log x iαi be the (negative) Gibbs-Shannon entropy on X i . By standard arguments, the resulting mirror map of each player i ∈ N is the logit choice map

Q i (y i ) = Λ i (y i ) ≡ (exp(y iαi )) αi∈Ai αi∈Ai exp(y iαi ) (12)
This choice map plays a central role in finite games; we will revisit it several times in Section 3.2.

Example 3.3 (Regularization on the orthant). Let

X i = [0, ∞) and set h i (x i ) = x i log x i -x i for all x i ∈ X i , i ∈ N
. By a straightforward calculation, the induced mirror map is Q i (y i ) = exp(y i ). As we discuss in Section 3.2, this provides the relevant setup for games with half-space constraints. 2 3.2. Specific algorithms. We now proceed to describe a representative range of learning algorithms that can be incorporated as specific instances of the general framework (RRM).

Depending on the information available to the players, we classify the algorithms under study as oracle-based or payoff-based. 1 The authors thank S. Sorin for proposing this definition. 2 Strictly speaking, the regularizer x log x -x is not strongly convex over R + but it is strongly convex over any bounded subset of R + -and it can be made strongly convex over all of R + by adding a small quadratic penalty of the form εx 2 /2. This issue does not change the essence of our results, so we sidestep the details.

▶ Oracle-based methods. In the first batch of methods under consideration, the players are assumed to have access to a stochastic first-order oracle (SFO), that is, a "black-box" feedback mechanism that returns an estimate of their individual payoff gradients at the chosen action profile. Formally, when queried at x ∈ X , an SFO outputs a random vector of the form

V (x; θ) = v(x) + err(x; θ), (SFO)
where θ is a random variable taking values in some measurable space Θ and err(x; θ) is an umbrella error term capturing all sources of uncertainty in the model. In practice, (SFO) is queried repeatedly at a sequence of action profiles X n ∈ X , n = 1, 2, . . . , possibly with a different random seed θ n each time. 3 For concreteness, we will assume that the noise in (SFO) is zero-mean and bounded in L q for some q ≥ 2, i.e.,

E[err(x; θ n ) | F n ] = 0 and E[∥err(x; θ n )∥ q * | F n ] ≤ σ q (13)
for some σ ≥ 0 and all x ∈ X (with q = ∞ taken to mean that err(x; θ) is bounded w.p.1).

We are now in a position to introduce the array of oracle-based methods under study; to lighten notation, we present some of these policies in an unconstrained setting.

Algorithm 1 (Stochastic gradient ascent). Perhaps the most basic iterative policy for multiagent online learning is the standard (individual) gradient ascent method

X n+1 = X n + γ n V (X n ; θ n ) (SGA)
with θ n drawn i.i.d. from Θ. From a loss minimization viewpoint, (SGA) is a multi-agent analogue of the standard stochastic gradient descent algorithm; in min-max games, (SGA) is sometimes referred to as the Arrow-Hurwicz method [START_REF] Arrow | Studies in linear and non-linear programming[END_REF]. Clearly, (SGA) is immediately recovered from (RRM) if the latter is run with the sequence of gradient signals vn ← V (X n ; θ n ) and the trivial mirror map Q(y) = y.

♢ Algorithm 2 (Extra-gradient). Going a step further from (SGA), the (stochastic) extragradient (EG) algorithm of Korpelevich [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF] is based on the following principle: starting at some "base" state X n , the players first take a gradient step to an interim, "leading" state X n+1/2 ; subsequently, to anticipate their payoff landscape, they update the base state X n with gradient information from X n+1/2 instead of X n , and the process repeats. Formally, this leads to the policy

X n+1/2 = X n + γ n V (X n ; θ n ) X n+1 = X n + γ n V (X n+1/2 ; θ n+1/2 ) (EG)
with θ n , θ n+1/2 drawn i.i.d. from Θ. Accordingly, (EG) is readily recovered from (RRM) by taking vn ← V (X n+1/2 ; θ n+1/2 ).

♢ Algorithm 3 (Optimistic gradient). A computational drawback of (EG) is that it requires two oracle queries per update -and hence, more overhead per iteration. One way to overcome this hurdle is to reuse past gradient information in the hope that it provides a good enough approximation of the present; this leads to the optimistic gradient policy X n+1/2 = X n + γ n V (X n-1/2 ; θ n-1 )

X n+1 = X n + γ n V (X n+1/2 ; θ n ) (OG)
Similarly to (EG), (OG) is recovered from (RRM) by setting vn ← V (X n+1/2 ; θ n ). This "gradient reuse" idea goes back at least to Popov [START_REF] Popov | A modification of the Arrow-Hurwicz method for search of saddle points[END_REF], and it has resurfaced several times in the literature since then, cf. [START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Hsieh | On the convergence of single-call stochastic extra-gradient methods[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF] and references therein. To simplify our presentation, we will assume in the sequel that (OG) is run with an SFO satisfying [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF] with q = ∞.

♢

The next method concerns learning in mixed extensions of finite games.

Algorithm 4 (Exponential / multiplicative weights). Let G = ∆(Γ) be the mixed extension of a finite game Γ(N , A, u) as per Example 2.3. In this setting, the players' learning process typically unfolds as follows: at each stage n = 1, 2, . . . , every player selects a mixed strategy X i,n ∈ ∆(A i ) and draws a pure strategy α i,n ∈ A i according to X i,n . Then, depending on the amount of information available to the players, we have the following oracle models:

(1) Full information feedback: in this case, players observe their mixed payoff vectors, i.e.,

V i (X n ; α n ) = v i (X i,n ; X -i,n ). (14a)
(2) Realization-based feedback: here, players instead observe their pure payoff vectors, i.e.,

V i (X n ; α n ) = v i (α i,n ; α -i,n ). (14b)
Both models can be seen as SFOs with seed α n , i.e., the (pure) action profile chosen by the players at stage n; the oracle (14a) is deterministic, while the oracle (14b) is stochastic and satisfies [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF] with q = ∞.

In this context, one of the most widely used learning methods is the so-called exponential / multiplicative weights algorithm -or Hedge -which unfolds iteratively as

Y i,n+1 = Y i,n + γ n V i (X n ; α n ) X i,n+1 = Λ i (Y i,n+1 ) (Hedge)
with Λ i denoting the logit choice map of ( 12) and V i given by (14a) or (14b) depending on the information available to the players. In both cases, (Hedge) is recovered immediately from (RRM) by letting vn ← V (X n ; α n ) and Q i = Λ i . For an overview of the method's history and its applications, see [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF] and references therein.

♢ ▶ Payoff-based methods. Moving forward, it is important to recall that Algorithms 1-4 all assume that players have access to a black-box oracle mechanism, but do not specify how this could be achieved in practice. Albeit commonplace, this assumption is not realistic in many applications where players may only be able to observe their realized payoffs and have no information about the strategies of other players or actions they did not play. To bridge this disconnect, we describe below a range of payoff-based policies where players estimate their individual payoff gradients indirectly, from their realized, "in-game" payoffs.

Algorithm 5 (Single-point stochastic approximation). A straightforward way of reconstructing gradients from zeroth-order feedback is via the single-point stochastic approximation framework of Spall [START_REF] Spall | Multivariate stochastic approximation using a simultaneous perturbation gradient approximation[END_REF]. In the unconstrained case (X = V), the relevant update step is:

Xi,n = X i,n + δ n W i,n , X i,n+1 = X i,n + γ n (u i ( Xn )/δ n ) W i,n .
(SPSA)

In (SPSA), each player's "query state" Xi,n , i = 1, . . . , N , is a perturbation of the "base state" X i,n by a step of magnitude δ n > 0 along a random direction W i,n drawn from the ensemble of signed basis vectors E i := {(±e 1 , . . . , ±e di )}. In this manner, (SPSA) can be seen as a special case of (RRM) with vi,n

← (u i ( Xn )/δ n ) W i,n for all i ∈ N . 4 ♢ 4
This formulation of (SPSA) is tailored to unconstrained problems. In this case, to ensure that the resulting gradient estimator remains bounded, it is customary to include an indicator of the form 1(∥ Xn∥ ≤ Rn) for some suitably chosen sequence Rn → ∞ [START_REF] Spall | Multivariate stochastic approximation using a simultaneous perturbation gradient approximation[END_REF]. This would lead to the same analysis but at the cost of heavier Algorithm 6 (Dampened gradient approximation). An alternative approach to (SPSA) is the two-point, "explore-then-update" approach of Bervoets et al. [START_REF] Bervoets | Learning with minimal information in continuous games[END_REF] who focused on games with X i = [0, ∞) for all i ∈ N and introduced the dampened gradient approximation policy

X i,n+1/2 = X i,n + (1/n)W i,n X i,n+1 = X i,n [1 + (u i (X n+1/2 ) -u i (X n ))W i,n ] (DGA)
In the above, the "exploration direction" W i,n is sampled uniformly at random from {±1} at each n. In other words, (DGA) is a two-stage process where players first "explore" their individual payoff functions at a nearby state, and then use this information to estimate their individual payoff gradients and update their base state.

To include (DGA) in the framework of (RRM), take

Q i (y i ) = exp(y i ) as per Example 3.3. Then, letting Y n = log X n , we get Y n+1 = Y n + log(1 + (u i (X n+1/2 ) -u i (X n ))W i,n ). ( 15
)
We may therefore view (DGA) as an instance of (RRM) with γ n = 1/n and gradient signals given by vi,n

← n • log(1 + (u i (X n+1/2 ) -u i (X n ))W i,n ).
♢ Algorithm 7 (The EXP3 algorithm). In our final example, we return to finite games, and we focus on the "bandit" case where players only observe the payoffs of the pure strategies that they played. In this setting, it is common to employ the importance-weighted estimator

V iαi ( Xn ; αn ) = 1(α i,n = α i ) Xiαi,n u i (α i,n ; α-i,n ) for all α i ∈ A i , i ∈ N , (IWE)
where each player i ∈ N draws an action αi,n from A i according to a mixed strategy Xi,n ∈ ∆(A i ). Then, plugging (IWE) into (Hedge), we obtain the method known as exponential weights for exploration and exploitation (EXP3), viz.

Y i,n+1 = Y i,n + γ n V i ( Xn ; αn ), X i,n+1 = Λ i (Y i,n+1 ), (EXP3)
where the sampling strategy of the i-th player at stage n is given by Xi

,n = (1 -δ n )X i,n + δ n unif(A i ). (16)
In the above, δ n ≥ 0 is an "explicit exploration" parameter that determines the mixing between X i,n and the uniform distribution unif(A i ) on A i . Accordingly, (EXP3) can be seen as an instance of (RRM) with Q i = Λ i and vn given by (IWE) with pure strategies αn drawn according to Xn .

♢ ▶ Runtime parameters. The above justifies the characterization of (RRM) as a "parent scheme" for Algorithms 1-7. In particular, thanks to the explicit expressions for vn derived in each case, we can likewise estimate the error bounds B n , σ n and M n of each method.

Proposition 3. Suppose that Algorithms 1-7 are run with step-size

γ n ∝ 1/n ℓγ , ℓ γ ∈ [0, 1],
and, where applicable, a sampling parameter δ n ∝ 1/n ℓ δ , ℓ δ ∈ (0, 1/2). Then the corresponding sequence of gradient signals vn in (RRM) enjoys the bounds:

• For Algorithms 1 and 4:

B n = 0, σ n = O(1)
, and M n = O(1).

• For Algorithms 2 and 3:

B n = O(1/n ℓγ ), σ n = O(1)
, and M n = O(1).

• For Algorithms 5 and 7:

B n = O(1/n ℓ δ ), σ n = O(n ℓ δ ), and M n = O(n ℓ δ ).
notation so, instead, we will assume that the players' payoff functions are bounded when discussing (SPSA). For a detailed discussion of how to adapt (SPSA) in the presence of constraints, we refer the reader to Bravo et al. [START_REF] Bravo | Bandit learning in concave N -person games[END_REF] who show that the relevant entries of Table 1 apply verbatim when X is compact.

Algorithm Actions (X i ) Mirror Map (Q) Feedback Bias (Bn) Magnitude (Mn) (SGA) R d i y oracle 0 O(1) (EG) / (OG) R d i y oracle O(1/n ℓγ ) O(1) (Hedge) ∆(A i ) Λ(y) oracle 0 O(1) (SPSA) R d i y payoff O(1/n ℓ δ ) O(n ℓ δ ) (DGA) [0, ∞) exp(y) payoff O(1/n) O(1) (EXP3) ∆(A i ) Λ(y) payoff O(1/n ℓ δ ) O(n ℓ δ )
Table 1: The algorithms of Section 3.2 as instances of (RRM). Where applicable, the methods' step-size and sampling parameters are taken to be of the form γn ∝ 1/n ℓγ and δn ∝ 1/n ℓ δ for some ℓγ ∈ [0, 1] and ℓ δ ∈ (0, 1/2) respectively.

• For Algorithm 6:

B n = O(1/n), σ n = O(1)
, and

M n = O(1).
For ease of reference, we summarize the above in Table 1 (for the proof of Proposition 3, see Appendix B). Of course, we can also "mix'n'match" different methods to include other algorithms considered in the literature: for instance, coupling (SPSA) with a general mirror map leads to the bandit mirror descent algorithm of Bravo et al. [START_REF] Bravo | Bandit learning in concave N -person games[END_REF]; incorporating the gradient reuse step of (OG) in the setup of (Hedge) yields the optimistic multiplicative weights (OMW) method of Daskalakis & Panageas [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF]; etc. In the sections to come, we will exploit the expressive power of (RRM) to provide a synthetic analysis for all these policies.

Stochastic approximation and first results

4.1. Mean dynamics and stochastic approximation. In this section, we derive a series of convergence results for (RRM) by treating it as a "noisy" discretization of the mean dynamics

ẏ = v(x) x = Q(y). (MD)
In this continuous-time interpretation, ẏ represents the limit of the finite difference quotient

(Y n+1 -Y n )/γ n .
As such, if γ n is "sufficiently small" and the gradient signal vn is a "good enough" approximation of v(X n ), it is plausible to expect that the iterates of (RRM) and the solutions of (MD) will eventually come together. Following [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF][START_REF] Benaïm | Asymptotic pseudotrajectories and chain recurrent flows, with applications[END_REF], this heuristic can be made precise as follows: First, let ψ : R × Y → Y denote the flow associated to (MD), i.e., the map which sends an initial condition y ∈ Y to the point ψ t (y) ∈ Y obtained by following the orbit of (MD) starting at y for time t ∈ R. Then, to compare the sequence of iterates Y n generated by (RRM) with the solution orbits of (MD), define the effective time

τ n = n k=1 γ k and the associated affine interpolation Y(t) of Y n as Y(t) = Y n + t -τ n τ n+1 -τ n (Y n+1 -Y n ) for all t ∈ [τ n , τ n+1 ], n = 1, 2, . . . (17)
We then have the following notion of "asymptotic closeness" between (RRM) and (MD):

Definition 2 [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF]. The sequence Y n is an asymptotic pseudotrajectory (APT) of (MD) if

lim t→∞ sup 0≤s≤T ∥Y(t + s) -ψ s (Y(t))∥ * = 0 for all T > 0. (APT)
In words, Definition 2 posits that Y n asymptotically tracks the orbits y(t) of (MD) with arbitrary precision over windows of arbitrary length. In our setting, the following proposition can be used as an explicit criterion guaranteeing this property: Proposition 4. Suppose that (RRM) is run with step-size and gradient signal sequences such that a)

γ n → 0; b) B n → 0; and c) n γ 1+q/2 n M q n < ∞. Then, with probability 1, the sequence X n = Q(Y n ) is an APT of (MD).
Proposition 4 shadows a basic result of Benaïm [6, Prop. 4.1, cf. Eq. ( 13) and onwards] so we omit its proof. For our purposes, it is more important to note that a tandem application of Propositions 3 and 4 immediately yields the following concrete conditions for Algorithms 1-7:

Corollary 1. Suppose that Algorithms 1-7 are run with parameters as in Proposition 3. Then the sequence Y n comprises an APT of (MD) provided that:

• For Algorithms 1-3:

ℓ γ > 2/(2 + q)
• For Algorithm 4: ℓ γ > 0

• For Algorithms 5 and 7:

ℓ γ > 2ℓ δ > 0
Corollary 1 provides a minimal set of hypotheses under which (MD) is a faithful representation of Algorithms 1-7. For some of these algorithms, this property is already known in the literature, see e.g., [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF] for (SGA) and [START_REF] Bervoets | Learning with minimal information in continuous games[END_REF] for (DGA). For others, the link with (MD) appears to be new: especially in the case of (EG) / (OG), Corollary 1 settles a standing question in the literature concerning the mean dynamics of optimistic gradient methods.

The primal-dual dichotomy.

To proceed, we will need some basic definitions from the theory of dynamical systems. Specifically, given a flow ϕ : R × M → M on some metric space M and a nonempty compact subset S of M, we say that:

(1) S is invariant under ϕ if ϕ t (S) = S for all t ∈ R.

(2) S is an attractor of ϕ if it admits a neighborhood W ⊆ Y such that dist(ϕ t (y), S) → 0 uniformly in y ∈ W as t → ∞.

(3) S is internally chain transitive (ICT) if it is invariant and ϕ| S has no attractors except S.

With all this in hand, the general theory of Benaïm & Hirsch [START_REF] Benaïm | Asymptotic pseudotrajectories and chain recurrent flows, with applications[END_REF] yields the following convergence result when applied to (MD):

Theorem 1 [START_REF] Benaïm | Asymptotic pseudotrajectories and chain recurrent flows, with applications[END_REF]. Let Y n , n = 1, 2, . . . , be an APT of (MD) with sup n ∥Y n ∥ * < ∞. Then Y n converges to an ICT set of (MD). ■ Taken together, Theorem 1 and Corollary 1 suggest that the behavior of the various algorithms presented in Section 3.2 (and many more) can be understood by looking at the ICT sets of the same mean dynamics. However, from a practical viewpoint, this conclusion carries two important limitations: First, the boundedness caveat for Y n cannot be readily checked against the game's primitives, so it is not clear when Theorem 1 applies -and, in much of the literature, this assumption has persisted as a condition that needs to be enforced "by hand" [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF][START_REF] Kushner | Stochastic approximation algorithms and applications[END_REF]. Second -and perhaps more importantly -this reasoning ignores the fact that X n evolves in X , the game's action space, whereas the orbits of (MD) live in Y, the game's dual space. In turn, this leads to a fundamental mismatch: a dual orbit y(t) may diverge in Y, even though the induced primal orbit x(t) = Q(y(t)) converges in X .

Example. Consider the single-player game with u(x) = -x, x ≥ 0. Then the dynamics (MD) give ẏ = -1, so y(t) → -∞ as t → ∞, i.e., y(t) diverges; however, under the exponential mirror map of Example 3.3, the player's trajectory of actions evolves as x(t) = exp(y(t)), i.e., x(t) converges (to 0). In this case, even if we were to ignore the boundedness issue, Theorem 1 becomes vacuous (and, in a sense, misleading): the dynamics (MD) do not have any ICT sets and are divergent, even though the induced trajectory of actions converges in X .

♢

The above creates a relatively awkward situation in which dynamical notions of stationarity and stability are defined on Y, whereas the corresponding game-theoretic notions reside in X . To reconcile this incompatibility, it is instead natural to focus directly on X and ask whether the notion of an ICT set can be transposed there. However, this is only meaningful if the ensemble of trajectories x(t) = Q(y(t)) constitute a flow on X ; that is, formally, we must posit the existence of a flow χ on X (or a subset thereof) that is conjugate to ψ in the sense that

Q • ψ t = χ t • Q for all t ∈ R.
In general, this may fail to hold: for example, consider the single-player game u(x) = x, x ∈ [0, 1], and consider the Euclidean projector Q(y) = [y] 1 0 ≡ min{max{y, 0}, 1} induced by the quadratic regularizer h(x) = x 2 /2 on X = [0, 1]. Clearly, (MD) gives ψ t (y) = y + t for all t ∈ R and all y ∈ R. Nevertheless, even though the orbits ψ t (0) and ψ t (-1) both have the same starting point Q(0) = Q(-1) = 0 in X , the induced primal trajectories evolve differently: for all t ∈ [0, 1], we have Q(ψ t (0)) = t and Q(ψ t (-1)) = 0, implying in turn that there can be no flow χ on X whose orbits are the images of the orbits of (MD).

Because this discrepancy arises at the boundary of X , Theorem 1 is more relevant for cases where all orbits are contained in ri X . In this case, we have the following result. Proposition 5. Let D ⊆ Y be a forward-invariant set of ψ such that B = Q(D) is contained in ri X . Then there exists a flow χ on B such that χ t (Q(y)) = Q(ψ t (y)) for all y ∈ D and all t ≥ 0; in particular, χ can be defined on all of ri X if im Q = ri X .

Proof. Clearly, the only candidate for χ is to set χ t (x) = Q(ψ t (y)) whenever x = Q(y) for y ∈ D. To see that this construction is well-defined, suppose that Q(y ′ ) = Q(y) = x for some y, y ′ ∈ D, and let w = y ′ -y; then, it suffices to show that Q(ψ t (y)) = Q(ψ t (y + w)) for all t ≥ 0.

As a first step, we claim that Q(ψ t (y) + w) = Q(ψ t (y)) for all t ≥ 0. Indeed, since Q(y) ∈ ri X , Lemma A.1 in Appendix A shows that w annihilates all tangent directions to X at x, i.e., ⟨w, x ′ -x⟩ = 0 for all x ′ ∈ X . However, since ψ t (D) ⊆ D and Q(D) ⊆ ri X , the point x t = Q(ψ t (y)) will also be interior; hence, with ψ t (y) ∈ ∂h(x t ) and ⟨w,

x ′ -x t ⟩ = ⟨w, x ′ -x⟩ + ⟨w, x -x t ⟩ = 0 for all x ′ ∈ X , invoking Lemma A.1 in the converse direction gives ψ t (y) + w ∈ ∂h(x t ), i.e., Q(ψ t (y) + w) = Q(ψ t (y)).
In view of the above, a simple differentiation yields

d dt [ψ t (y) + w] = d dt ψ t (y) = v(Q(ψ t (y))) = v(Q(ψ t (y) + w)) (18)
which, by the Picard-Lindelöf theorem, shows that ψ t (y) + w is the (necessarily unique) solution orbit of (MD) starting at y + w at time t = 0. We thus conclude that Q(ψ t (y + w)) = Q(ψ t (y) + w) = Q(ψ t (y)), i.e., χ is well-defined. Our second assertion follows from the fact that im Q = dom ∂h = ri X , so we can apply our first claim to D = Y.

■ Proposition 5 indicates that, if Q is interior-valued, we can map the flow on Y to an induced primal flow on X . For concreteness, before discussing the precise connection between (RRM) and the induced dynamics on X , we illustrate the latter in the case of Examples 3.1-3.3:

ẋiαi = x iαi [u i (α i ; x -i ) -u i (x i ; x -i )]. (RD) Example 4.3. Let X i = [0, ∞) and take Q i (y i ) = exp(y i )
as in Example 3.3. Then, by differentiating x i = e yi we obtain the dampened gradient dynamics of Bervoets et al. [START_REF] Bervoets | Learning with minimal information in continuous games[END_REF], viz.

ẋi = x i v i (x).
(DGD) 4.3. Subcoercivity and convergence. Other than the primal-dual dichotomy described above, the other important caveat in Theorem 1 is the boundedness of the generated sequence Y n . In the optimization literature, a standard way to establish this type of control on an algorithm designed to find a zero of a vector field v on R d is to assume that it is coercive, i.e., lim ∥x∥→∞ ⟨v(x), x⟩/∥x∥ = -∞. Intuitively, coercivity means that v(x) is strongly "inward pointing" for large values of x, so it acts as a natural barrier against escape phenomena; at the same time, it also imposes that ∥v(x)∥ * grows superlinearly in x, and is only relevant for unconstrained problems, so it is not particularly well-suited for our purposes. Instead, we will consider the following, weaker requirement:

Definition 3.
We say that G is subcoercive if there exists a compact set K ∈ ri X and a reference point p ∈ K such that

⟨v(x), x -p⟩ ≤ 0 for all x ∈ X \ K. (SC)
Geometrically, subcoercivity simply posits that the Nash field v(x) of the game points weakly towards p outside K, so any "attracting" behavior in G must be contained in K: for example, it is straightforward to verify that any variationally stable state of G must lie within K if (SC) holds. Beyond this, it is important to note that v may vanish at infinity, and K can be arbitrarily large (relative to X ). We provide some examples below: Example 4.4 (Potential games). Suppose that G admits a quasiconcave potential Φ with arg max Φ ⊆ ri X . If we fix a maximizer p of Φ, we have ⟨v(x), x -p⟩ = ⟨∇Φ(x), x -p⟩ ≤ 0 for all x ∈ X , so G is subcoercive. More generally, G is subcoercive whenever Φ is "eventually quasiconcave", i.e., the upper level sets L + c (Φ) = {x ∈ X : Φ(x) ≥ c} of Φ are convex for sufficiently small c > inf Φ and at least one such set is contained in ri X . 5

♢

Example 4.5 (Min-max games). Consider the toy game min

x1∈[-1,1] max x2∈[-1,1] x 1 x 2 . Since ⟨v(x), x⟩ = -x 2 x 1 + x 1 x 2 = 0 for all x ∈ [-1, 1] × [-1, 1]
, the game is trivially subcoercive. More generally, it is easy to check that any two-player, quasi-convex / quasi-concave game with an interior equilibrium is subcoercive.

♢ By itself, subcoercivity ensures that there is no consistent drift pointing away from K, so it is reasonable to expect that Y n does not escape to infinity either. To control the inherent stochasticity in Y n and make this intuition precise, we will require the following summability conditions on the bias, variance, and magnitude of the gradient signal process vn :

n γ n B n < ∞ n γ 2 n σ 2 n < ∞ and n γ 2 n M 2 n < ∞.
(Sum) 5 To see this, let K = L + c 0 (Φ) be a convex upper level set of Φ in ri X . Then, for all c ≤ c 0 and all x with Φ(x) = c, the segment

x + τ (p -x), τ ∈ [0, 1], is contained in L + c (Φ) ⊇ L + c 0 (Φ), so the function ϕ(τ ) = Φ(x + τ (p -x)) cannot have ϕ ′ (0) < 0. This implies that 0 ≤ ⟨∇Φ(x), p -x⟩ = ⟨v(x), p -x⟩ for all x ∈ X \ K, i.e., G is subcoercive.
Under these conditions, we have the following stability result. Proposition 6. Suppose that (RRM) is run with step-size and gradient signal sequences satisfying (Sum). If G is subcoercive, the sequence of iterates Y n generated by (RRM) is bounded w.p.1.

Before proving Proposition 6, it is important to note that subcoercivity only concerns the primitives of the game under study, and it is otherwise "algorithm-agnostic". In this regard, given the primal-dual nature of the underlying dynamics (MD), Proposition 6 plays a major role in enabling the use of stochastic approximation tools and techniques (otherwise, the boundedness of X by itself does not suffice).

Moreover, from an operational viewpoint, Proposition 3 makes the verification of (Sum) a trivial affair for the algorithms under study. In particular, a joint application of Corollary 1, Propositions 3 and 6, and Theorem 1 readily yields the general convergence result below: Theorem 2. Suppose that Algorithms 1-7 are run with step-size γ n ∝ 1/n ℓγ , ℓ γ ∈ (1/2, 1], and, where applicable, a sampling parameter δ n ∝ 1/n ℓ δ with 1 -ℓ γ < ℓ δ < ℓ γ -1/2. If G is subcoercive, then: a) Y n converges to an ICT set of (MD) with probability 1; and, in addition, b) if the players' mirror map Q is interior-valued, the induced sequence of play X n = Q(Y n ) converges with probability 1 to an ICT set of the primal flow χ on X .

We then have the following consequences for potential and zero-sum games (both stated for simplicity under the assumption that Q is interior-valued):

Corollary 2.
If G admits a subcoercive potential, X n converges to a component of critical points of G w.p.1. In particular, if the potential is concave, X n converges to the set of Nash equilibria of G.

Corollary 3. Suppose that G is a strictly convex-concave min-max game with an interior equilibrium x * ∈ ri X . Then X n converges to x * w.p.1.

Corollaries 2 and 3 follow respectively from the fact that the only ICT sets of potential games and strictly convex-concave games are their sets of critical points, see e.g., [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] and references therein. As for Theorem 2 (which we prove below), it should not be viewed as an equilibrium convergence guarantee, but as a characterization of what types of behaviors may arise in the limit of a game-theoretic learning process -equilibrium and non-equilibrium alike. However, because of the subcoercivity requirement, this characterization only extends to limit sets that are contained in the relative interior of the players' action spaces; games with boundary solutions require a different treatment, which we undertake in the next two sections.

4.4. Technical proofs. We conclude this section with the proof of Proposition 6 and Theorem 2; we begin with the latter, which is more conceptual and less technical.

Proof of Theorem 2. By Propositions 3 and 6, Y n is a bounded APT of (MD), so the first part of the theorem follows directly from Theorem 1. As for the second, since Q is Lipschitz continuous (cf. Lemma A.1 in Appendix A), the sequence X n = Q(Y n ) is also bounded and, in addition, we have:

∥X(t + s) -χ s (X(t))∥ = ∥Q(Y(t + s)) -χ s (Q(Y(t)))∥ = ∥Q(Y(t + s)) -Q(ψ s (Y(t)))∥ ≤ (1/K)∥Y(t + s) -ψ s (Y(t))∥ * ( 19
)
where K is the strong convexity modulus of h and we used the fact that χ t • Q = Q • ψ t for all t (by Proposition 5). This implies that X n is an APT of χ, 6 so our claim follows from the limit set theorem of Benaïm & Hirsch [7, Theorem 0.1].

■

We are thus left to prove the boundedness guarantee of Proposition 6.

Proof of Proposition 6. Our proof hinges on the construction of a suitable "energy function" E : Y → R + for (RRM). To define it, we will assume for simplicity -and without loss of generality -that X has nonempty topological interior in V (which can be achieved by redefining V to be the affine hull of X ), that the reference point p in Definition 3 is the origin 0 ∈ V, and that h(p) = 0 (which can be achieved by a simple translation). With this in mind, let h * (y) = max x∈X {⟨y, x⟩ -h(x)} denote the convex conjugate of h. Then, by Lemma A.2 in Appendix A, we have

(K/2)∥Q(y)∥ 2 ≤ h * (y) ≤ -min h + ⟨y, Q(y)⟩ + (2/K)∥y∥ 2 * for all y ∈ Y (20)
where we note that min h ≤ h(p) = 0 by assumption. Since h is lower-semicontinuous, we have h = h * * by the Fenchel-Moreau theorem. In addition, the Moreau-Rockafellar theorem [4, Theorem 4.17] implies that h * is coercive because it can be written as h * (y) = h * (y)-⟨y, p⟩ and 0 = p ∈ ri X = ri dom h * * by subcoercivity. Finally, since X has nonempty interior, it follows that the polar cone PC(x) is trivially 0 for all x ∈ ri X , so the subdifferential ∂h of h is compact-valued on K ⊆ ri X . Thus, by the upper hemicontinuity of the subdifferential and the compactness of K, we deduce that the image D = ∂h(K) of K under ∂h is compact, cf. [28, p. 201]. Hence, by the coercivity of h * and the fact that

Q(y) = x if and only if ∂h(x) ∋ y (cf. Lemma A.1 in Appendix A), there exists some c > 0 such that h * (y) ≤ c whenever Q(y) ∈ K, i.e., Q -1 (K) is contained in the c-sublevel set L - c (h * ) of h * .
With all this said and done, fix some c ′ > c and let

E(y) = φ(h * (y)) for all y ∈ Y (21)
where φ : R + → R + is a C 2 -smooth "gauge function" with the following properties: i) φ(u) = 0 for u ≤ c; ii) φ(u) = √ u for u ≥ c ′ ; iii) φ ′ (u) ≥ 0 and φ ′′ (u) ≤ 1 for all u ∈ R + . 7 Then, setting x = Q(y) and differentiating, we readily obtain

∇E(y) = φ ′ (h * (y)) • ∇h * (y) = φ ′ (h * (y)) • x for all y ∈ Y (22)
and hence, by the smoothness properties of φ and h * , there exists some constant C 2 ≥ 0 such that

E(y + w) = E(y) + φ ′ (h * (y)) • ⟨w, x⟩ + C 2 ∥w∥ 2 * for all y, w ∈ Y. (23)
Therefore, combining Eqs. ( 22) and [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF] and letting

E n = E(Y n ),
we obtain

E n+1 ≤ E n + φ ′ (h * (Y n )) • ⟨v n , X n ⟩ + C 2 ∥v n ∥ 2 * ≤ E n + φ n ⟨b n + U n , X n ⟩ + C 2 ∥v n ∥ 2 * ( 24
)
where we set

φ n = φ ′ (h * (Y n ))
and we used the fact that φ(h * (y)) • ⟨v(x), x⟩ ≤ 0 for all y ∈ Y (the latter being a consequence of subcoercivity and the defining properties of φ).

Accordingly, conditioning on F n and taking expectations, we finally get

E[E n+1 | F n ] ≤ E n + γ n φ n B n ∥X n ∥ + γ 2 n M 2 n , (25)
where we used the Cauchy-Schwarz inequality to bound ⟨b n , X n ⟩ from above by

B n ∥X n ∥ (recall also that E[U n | F n ] = 0 by definition). Now, let ε n = γ n φ n B n ∥X n ∥ + M 2
n denote the "residual" term in [START_REF] Hart | Stochastic uncoupled dynamics and Nash equilibrium[END_REF], and consider the auxiliary process 6 We are grateful to V. Boone for pointing out this simple argument. 7 That such a function exists is an exercise in the construction of aproximate identities, which we omit. E n-1 , i.e., E n is a supermartingale relative to F n . Moreover, by [START_REF] Giannou | The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond[END_REF] and the definition of φ, we further have

E n = E n+1 + ∞ k=n+1 ε k . By (25), we have E[E n | F n ] ≤ E n + ∞ k=n ε n =
φ n = 1 2 h * (Y n ) ≤ 1 √ 2K∥X n ∥ whenever h * (Y n ) ≥ c ′ (26)
so there exists some (deterministic) positive constant C 1 such that sup n φ n ∥X n ∥ ≤ C 1 . We thus get

∞ n=1 ε n ≤ C 1 ∞ n=1 γ n B n + C 2 ∞ n=1 γ 2 n M 2 n < ∞ (27)
by the summability condition (Sum). This shows that E[ n ε n ] < ∞ and, in turn, that

E[E n ] ≤ E[E 1 ] < ∞, i.e
., E n is uniformly bounded in L 1 . Accordingly, by Doob's submartingale convergence theorem [23, Theorem 2.5], it follows that E n converges with probability 1 to some finite random limit

E ∞ . Since n ε n < ∞, this implies that E n = E n-1 -
∞ k=n ε n also converges to some (random) finite limit (a.s.). Therefore, by the coercivity of E, we deduce that lim sup n ∥Y n ∥ * < ∞ w.p.1, as claimed.

Robust convergence and stable limit sets

Even though Theorem 2 provides a universal characterization of the long-run behavior of any algorithm of the general form (RRM), there are several issues that remain open, namely:

(1) How is the long-run behavior of an algorithm affected by a small perturbation in its initialization?

(2) Does the update structure of the gradient-like signals vn affect the algorithm's endstate?

(3) Are some limit sets independent of the amount of information available to the players? In view of all this, the rest of this section will focus on whether we can identify a class of "robust" limit sets that satisfy the above desiderata. We present and discuss our main results in Section 5.2 after some necessary definitions and prerequisites in Section 5.1.

5.1.

Stochastically attracting sets and energy functions. In the theory of dynamical systems, the established way of analyzing such questions is via the notion of an attractor (cf. the relevant discussion in Section 4). Following Nevel'son & Khasminskii [START_REF] Nevel'son | Stochastic Approximation and Recursive Estimation[END_REF], this notion can be adapted to our stochastic setting as follows: Definition 4. Let S be a nonempty closed subset of X . We say that S is stochastically attracting under (RRM) for a given tolerance level η > 0 if there exists a neighborhood U of S in X such that

P(X n converges to S | X 1 ∈ U) ≥ 1 -η. (28)
In the context of stochastic approximation algorithms, the requirement ( 28) is reminiscent of results guaranteeing convergence with positive probability toward an attractor. Such guarantees are usually conditioned on the notion of attainability, as pioneered by Benaïm [START_REF] Benaïm | Vertex reinforced random walks and a conjecture of Pemantle[END_REF] and Duflo [START_REF] Duflo | Cibles atteignables avec une probabilité positive d'après M. Benaïm[END_REF];8 however, in the present setting, there are two salient difficulties with this approach, both having to do with the primal-dual nature of the mean dynamics (MD). On the one hand, if the players' mirror map Q : Y → X is surjective on the boundary of X (e.g., as in the case of Euclidean projections), it is in general impossible to define a conjugate primal flow on X -and hence, it is not possible to treat S as an attractor. On the other hand, if Q is interior-valued (that is, im Q = ri X ), the defining Robbins-Monro process Y n . The left plot shows two different initializations of (SGA), while the right plot displays the trajectories of (SGA) and (EG) from the same initialization. In both cases, the existence of an attractor allows for robust predictions that are largely independent of the initialization or exact update structure of (RRM).

may escape to infinity if Q -1 (S) = ∅, and establishing attainability in this case can be as difficult as the original problem of proving (28) directly.

On account of all this, we will instead seek to establish (28) via a primal-dual variant of Lyapunov's direct method. In particular, since we are interested in the attracting properties of subsets of the primal space X ⊆ V, but the dynamics evolve in the dual space Y = V * of V, our analysis will hinge on the following construction: Definition 5. Let S be a nonempty closed subset of X . We will say that E : Y → [0, ∞) is a local energy function for S under (MD) if a) E is Lipschitz continuous and smooth; b) Q(y) → S if and only if E(y) → 0; and c) sup{ Ė(y) : E -< E(y) < E + } < 0 for all sufficiently small E + > E -> 0. In particular, if the last requirement holds for all E + ≤ sup E, we will refer to E as a global energy function for S.

Informally, Definition 5 posits that E is smooth, positive-definite, and strictly decreasing along all nearby primal orbits x(t) = Q(y(t)) that do not lie in S. For concreteness, we provide below a series of representative examples that will play an essential part in the sequel.

Example 5.1 (Variational stability). Suppose that x * satisfies (VS), i.e., ⟨v(x), x -x * ⟩ < 0 for all x ̸ = x * in some neighborhood U of x * in X . Then a suitable primal-dual measure of distance from x * is provided by the so-called "Fenchel coupling" [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF]

F (y) = h(x * ) + h * (y) -⟨y, x * ⟩. ( 29
)
The key property of this coupling is that, under (MD), we have

Ḟ (y) = ⟨ ẏ, ∇h * (y)⟩ -⟨ ẏ, x * ⟩ = ⟨v(x), x -x * ⟩ < 0 whenever x ∈ U\{x * } (30)
where, in the penultimate step, we set x = Q(y) and we invoked Lemma A.1 in Appendix A to write Q(y) = ∇h * (y). By the Fenchel-Young inequality, we also have F (y) ≥ 0 with equality if and only if Q(y) = x * (cf. Lemma A.2), so F (y) is a prime candidate for a local energy function.

To meet the entire range of requirements of Definition 5, we will need two further technical ingredients. The first is a regularity assumption on h, namely that

h(x n ) + ⟨y n , x -x n ⟩ → h(x) (R)
for all x ∈ X and all sequences of primal points x n → x and subgradients y n ∈ ∂h(x n ). This condition simply posits that the first-order approximation of h(x) from h(x n ) is always accurate when x n → x, a property which is satisfied by all examples of regularizers that we have considered so far; for an in-depth discussion, cf. Azizian et al. [START_REF] Azizian | On the rate of convergence of Bregman proximal methods in constrained variational inequalities[END_REF] and references therein.

The second technicality is that F must grow at most linearly in ∥y∥ * in order to ensure the global Lipschitz continuity requirement of Definition 5. To achieve this, it suffices to rescale F for large values of x by means of the gauge function

φ(z) = z if 0 ≤ z ≤ 1 2 √ z -1 if z ≥ 1 (31)
which ensures that φ • F behaves like F for small values of F , and like √ F for large values of F . We then have the following result: Lemma 1. Suppose that x * satisfies (VS) and the players' regularizers satisfy (R). Then, with notation as above, the function E(y) = φ(F (y)) is a local energy function for x * under (MD); moreover, if x * is globally stable, E is a global energy function for x * under (MD).

To streamline our presentation, we defer the proof of Lemma 1 to Appendix A. We only note here that, by the relevant discussion in Section 2, the above yields an energy function for a wide class of games, including a) strictly monotone games (a global one in this case); b) games with second-order stationary equilibria as per (SOS); and c) all finite games admitting a strict Nash equilibrium.

♢ Example 5.2 (Convex optimization). Consider the convex minimization problem min x∈X f (x)

where f : X → R is a smooth convex function with a nonempty, compact set of minimizers S = arg min f . To get a primal-dual measure of distance from S, we may extend the definition of the coupling (29) to the current setting as

F (y) = h * (y) -h * S (y) (32)
where h * S (y) = max x∈S {⟨y, x⟩ -h(y)} denotes the convex conjugate of h relative to S. As we show below, rescaling F by the gauge function [START_REF] Hsieh | On the convergence of single-call stochastic extra-gradient methods[END_REF] yields a global energy function for S under (MD): Lemma 2. Suppose that (R) holds. Then, with notation as above, the function E(y) = φ(F (y)) is a global energy function for S = arg min f . As before, to keep the discussion going, we defer the proof of Lemma 2 to Appendix A. ♢ Example 5.3 (Discoordination games). As a last example, consider a two-player discoordination game with payoff functions u

1 (x 1 , x 2 ) = (x 1 -x 2 ) 2 /2 and u 2 (x 1 , x 2 ) = (x 1 + x 2 ) 2 /2 for x 1 , x 2 ∈ [-1, 1]
. This game admits five critical points, the origin (0, 0) and the four vertices {±1, ±1} of X = [-1, 1] 2 . None of these critical points is an equilibrium: the origin is unstable to deviations by both players, whereas the vertices are unstable to deviations by one of the players (but not the other). Given the lack of an equilibrium in pure strategies (a standard feature of discoordination games), the players' limiting behavior is quite difficult to predict; however, since the critical point at (0, 0) is unstable for both players, it is reasonable to expect that it should be selected against. The critical point at (0, 0) is unstable to deviations by both players, and no trajectories converge there, even though it is the only interior ICT of (MD).

To examine this issue in the context of (MD), consider for concreteness the mirror map 9 In this case, it is straightforward to check that E(y 1 , y 2 ) = 2 sech(y 1 /2) sech(y 2 /2) is an (almost global) local energy function for the four-corner set S = {-1, 1} × {-1, 1}. As a result, the sequence of play generated by (RRM) is expected to spend most time near one of these points, cf. Fig. 2.

Q i (y i ) = tanh(y i /2) that is induced by the entropic regularizer h i (x i ) = (1 -x i ) log(1 - x i ) + (1 + x i ) log(1 + x i ).

♢

In Section 6, we present an additional range of examples that cover such cases as (stochastic) linear programming, the set of undominated strategies of a game, etc. 5.2. Main results, implications, and applications. We are now in a position to state our main results on the stable limit sets of (RRM). To do so, we will assume for concreteness that (RRM) is run with step-size and gradient signal sequences such that

γ n = γ/n ℓγ B n = O(1/n ℓ b ) and M n = O(n ℓσ ) (33)
for some ℓ γ ∈ [0, 1], ℓ b > 0 and ℓ σ < 1/2. Since the schedule (33) involves B n and M n (which, depending on the algorithm, may be beyond the players' control), this requirement may seem unverifiable at first glance. However, in view of Proposition 3, the exponents ℓ b and ℓ σ can be directly expressed in terms of the parameters of the specific algorithm under study, so this is not an issue. Without further ado, we have the following general result:

Theorem 3. Fix a tolerance level η > 0, and let X n = Q(Y n ) be the sequence of play generated by (RRM) with step-size and gradient signal sequences such that ℓ γ +ℓ b > 1 and ℓ γ -ℓ σ > 1/2 in [START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF]. If S admits a local energy function and γ is sufficiently small, S is stochastically attracting; specifically, there exists a neighborhood U of S, independent of the tolerance level η, such that P(X n converges to S | X 1 ∈ U) ≥ 1 -η. In addition, if the energy function on S is global, then, with probability 1, X n converges to S from any initialization.

Corollary 4. Suppose that Algorithms 1-7 are run with step-size

γ n ∝ 1/n ℓγ , ℓ γ ∈ (1/2, 1],
and, where applicable, a sampling parameter

δ n = δ/n ℓ δ such that 1 -ℓ γ < ℓ δ < ℓ γ -1/2.
Then the conclusions of Theorem 3 hold.

Remark 3. In the baseline case B n = 0, sup n σ n =: σ < ∞, the proof of Theorem 3 shows that it suffices to take γ = O(min{E + /(σH), M E + /β}) • √ η.

Theorem 3 and Corollary 4 are our main results concerning the stable limit sets of (RRM) so, before discussing their proof, we present a series of corollaries and applications thereof.

Corollary 5. Suppose that Algorithms 1-7 are run with parameters as in Corollary 4. If x * is globally variationally stable, then X n converges to x * w.p.1. Corollary 6. Suppose that Algorithms 1-7 are run with parameters as in Corollary 4. If G is strictly monotone, then X n converges to the game's unique Nash equilibrium w.p.1.

The guarantees of Corollary 4 are particularly important from an equilibrium convergence standpoint, because, as we mentioned in Section 2, strictly monotone games account for a very wide range of applications -socially concave games [START_REF] Even-Dar | On the convergence of regret minimization dynamics in concave games[END_REF], Cournot oligopolies [START_REF] Monderer | Potential games[END_REF], Kelly auctions [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], etc.

We should also stress here that neither of the above results can be inferred by the ICT convergence analysis of Section 4. In particular, if x * lies at the boundary of X , it may fail to be accessible unless the dual process Y n escapes to infinity, in which case Theorem 2 no longer applies. This illustrates the flexibility of Definition 5, as it allows us to tackle at the same time both boundary and interior solutions, in both bounded and unbounded domains.

To the best of our knowledge, the only comparable global convergence results in the literature for oracle-based methods concern the convergence of the standard mirror descent algorithm (B n = 0, sup n σ 2 n < ∞) in strictly monotone games with compact domains [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF]. For payoff-based algorithms, the closest results we are aware of are by Bravo et al. [START_REF] Bravo | Bandit learning in concave N -person games[END_REF] and Tatarenko & Kamgarpour [START_REF] Tatarenko | Learning generalized Nash equilibria in a class of convex games[END_REF][START_REF] Tatarenko | Learning Nash equilibria in monotone games[END_REF] for a constrained variant of (SPSA) in strictly monotone games with compact domains (the latter actually showing convergence in probability, but without requiring strict monotonicity).

Finally, in terms of local results, Theorem 3 further yields the following corollaries: Corollary 7. Suppose that Algorithms 1-7 are initialized and run as per Corollary 4. If x * is variationally stable -or, more narrowly, if it satisfies (SOS) -then X n converges locally to x * with arbitrarily high probability.

Corollary 8. Let x * be a strict Nash equilibrium of a finite game. If Algorithms 4 and 7 are initialized and run as per Corollary 4, X n converges locally to x * with arbitrarily high probability.

Of the above results, a special case of Corollary 7 was proven in [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] for unbiased signal sequences with finite unconditional variance (i.e., B n = 0 and sup n E[∥U n ∥ 2 * ] < ∞); at the time of writing, this seems to be the closest antecedent of our results in the literature. In particular, the convergence of Algorithms 2, 3 and 6 to variationally stable states and LNE satisfying (SOS) seems to be new.

Importantly, points satisfying (SOS) are the game-theoretic analogue of minimizers with a positive-definite Hessian in non-convex minimization problems [START_REF] Ratliff | On the characterization of local Nash equilibria in continuous games[END_REF]. In this regard, Corollary 7 is particularly important as it shows that such equilibria are attracting under the entire class of algorithms under study. Likewise, Corollary 8 is a key result because, generically -i.e., except on a set of games which is meager in the sense of Baire -pure Nash equilibria in finite games are always strict. Thus, coupled with the inherent instability of mixed equilibria in finite games [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF], Corollary 8 goes a long way toward establishing a learning analogue of the "folk theorem" of evolutionary game theory which states that a Nash equilibrium is stable and attracting if and only if it is strict [START_REF] Hofbauer | Evolutionary game dynamics[END_REF]. 5.3. Technical proofs. We conclude this section with the proof of Theorem 3. The main ingredient of our analysis is a "template inequality" for (RRM) when the set under study admits an energy function (local or global).

To state it, note first that if E is an energy function for S under (MD), there exists some E + > 0 (possibly equal to sup E) such that the sublevel set

D = {y ∈ Y : E(y) ≤ E + } ( 34
)
is forward invariant under (MD) and sup{ Ė(y) :

E + ≥ E(y) > E -} < 0 for all E -∈ (0, E + ).
Moreover, by assumption, there exist positive constants β, H > 0 such that ∥∇E(y)∥ ≤ H and E(y ′ ) ≤ E(y) + ⟨∇E(y), y ′ -y⟩ + 1 2 β∥y ′ -y∥ 2 * (35) for all y, y ′ ∈ Y. With all this in hand, we have the following template inequality:

Lemma 3. Let E n := E(Y n ).
Then, for all n = 1, 2, . . . , we have

E n+1 ≤ E n + γ n ⟨v(X n ), ∇E(Y n )⟩ + γ n ξ n + γ n χ n + γ 2 n ψ 2 n , (36)
where the error terms ξ n , χ n , and ψ n are given by

ξ n = ⟨U n , ∇E(Y n )⟩, χ n = H∥b n ∥ * and ψ 2 n = 1 2 β∥v n ∥ 2 * . (37)
Proof. Simply unroll [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF] after substituting y ← Y n and y ′ ← Y n+1 = Y n + γ n vn with vn as in [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF].

■ Now, by the definition of E, we have

Ė(y) = ⟨v(Q(y)), ∇E(y)⟩ < 0 whenever y ∈ D \ Q -1 (S). Hence, for X n ∈ Q(D), (36) becomes
E n+1 ≤ E n + γ n ξ n + γ n χ n + γ 2 n ψ 2 n . (38)
Of course, each of these error terms can be positive, so E n may fail to be decreasing, even when X n ∈ Q(D). On that account, it will be convenient to introduce the error processes

I n = n k=1 γ k ξ k II n = n k=1 γ k χ k and III n = n k=1 γ 2 k ψ 2 k ( 39
)
which measure directly the aggregate effect of each error term in [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF]. As it turns out, under (Sum), these errors can be compensated by the negative drift of (36), leading to the following global result: Proposition 7. Suppose that S admits a global energy function, and let X n = Q(Y n ) be the sequence of play generated by (RRM). If (Sum) holds, then, with probability 1, X n converges to S.

To streamline our discussion, before proving Proposition 7, we present a similar convergence result for sets that only admit local energy functions. In this case, even if the algorithm begins play close to S, a single "bad" realization of the noise could force the process to exit the basin of attraction of S, possibly never to return. With a fair degree of hindsight, we will control the probability with which this "bad event" occurs via the stability requirement

P(Z n > E + /4 for some n) < η/3 (Stab)
where η > 0 is the target tolerance level, and Z n ← I n , II n or III n , depending on the error term that we wish to control. Modulo this requirement, we obtain the following local analogue of Proposition 7:

Proposition 8. Suppose that S admits a local energy function, and let X n = Q(Y n ) be the sequence of play generated by (RRM). Assume further that the algorithm begins play at a neighborhood U of S such that E(Y 1 ) ≤ E + /4. If (Sum) and (Stab) hold, then

P(E(Y n ) < E + for all n and lim n→∞ dist(X n , S) = 0) ≥ 1 -η. (40)
Of course, Propositions 7 and 8 can be difficult to employ in practice because of their reliance on the conditions (Sum) and (Stab). Because of this, we defer the proof of Propositions 7 and 8 to the end of this section, and we proceed below to complete the proof of Theorem 3 by showing that (Sum) and (Stab) both hold under the stated step-size and gradient signal requirements.

Proof of Theorem 3. We begin by noting that (Sum) holds trivially under the stated conditions for γ n ∝ 1/n ℓγ , B n = O(1/n ℓ b ) and M n = O(n ℓσ ). As a result, the first part of the theorem follows immediately from Proposition 7.

Likewise, for the second part, it will suffice to establish the stability condition (Stab). To that end, proceeding term-by-term, we have:

(1) Since I n is a martingale, Kolmogorov's inequality [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF]Corollary 2.1] gives

P max 1≤k≤n I k ≥ E + /4 ≤ P max 1≤k≤n |I k | ≥ E + /4 ≤ 16 E[I 2 n ] E 2 + = 16 E n k=1 γ k ξ k 2 E 2 + ≤ 16H 2 n k=1 γ 2 k σ 2 k E 2 + =: C I (41)
where we used the variance bound

E[ξ 2 k ] = E[E[|⟨U k , ∇E(Y k )⟩| 2 | F k ]] ≤ H 2 σ 2 k (42)
and the fact that

E[ξ k ξ m ] = E[ξ k ξ m | F k∨m ] = 0 whenever k ̸ = m.
Thus, given that {X n ≥ E + /4 for some n} = n {I * n ≥ E + /4} is a union of nested events, we conclude that (Stab) holds for Z n ← I n whenever C I ≤ η/3.

(2) For the second term, we have II n ≤ H ∞ k=1 γ k B k for all n with probability 1, so (Stab) holds for Z n ← II n as long as C II := (4H/E + ) n γ n B n ≤ 1.

(3) Finally, for the last term, Markov's inequality yields

P(III n ≥ E + /4) ≤ 4 E[III n ] E + = 2β n k=1 γ 2 k M 2 k E + =: C III . (43)
We thus see that the event {III n ≥ E + /4 for some n} = n {III n ≥ E + /4} occurs with probability no more than C III , which implies in turn that the requirement (Stab) for Z n ← III n holds whenever C III ≤ η/3.

Since C I , C II and C III are all O(γ 2 ), we can choose γ sufficiently small so that C I ≤ η/3, C II ≤ 1 and C III ≤ η/3. In this case, (Stab) holds by construction, and our claim follows from Proposition 8.

■

We are thus left to prove Propositions 7 and 8. To that end, we begin with a technical lemma showing that the aggregate error processes I n , II n and III n of (39) are subleading relative to the long-run drift of [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF]. Lemma 4. Under (Sum), the aggregate error processes of (39) are sublinear in τ n , i.e., we have

Z n /τ n → 0 with probability 1, (Sub)
where Z n ← I n , II n or III n , depending on the error term under study.

Proof. We treat each case Z n ← I n , II n or III n separately.

(1) For I n , (Sum) readily gives

∞ n=1 E[γ 2 n ξ 2 n | F n ] ≤ ∞ n=1 γ 2 n E[∥∇E(Y n )∥ 2 ∥U n ∥ 2 * | F n ] ≤ H 2 ∞ n=1 γ 2 n σ 2 n < ∞. (44)
Thus, by the strong law of large numbers for martingale difference sequences [23, Theorem 2.18], we conclude that I n /τ n converges to 0 with probability 1.

(2) For II n , the conclusion is immediate by the fact that n γ n B n < ∞ under (Sum).

(3) Finally, for the submartingale term III n , we have

E[III n ] = n k=1 γ 2 k E[ψ 2 k ] ≤ β 2 n k=1 γ 2 k E[∥v k ∥ 2 * ], ≤ β 2 n k=1 γ 2 k M 2 k , (45)
so, by (Sum), it follows that III n is bounded in L 1 . Therefore, by Doob's submartingale convergence theorem [23, Theorem 2.5], we further deduce that III n converges (a.s.) to some (finite) random variable III ∞ , implying in turn that III n /τ n → 0 with probability 1.

■

Moving forward, we present two lemmas that will allow us to deduce the convergence of the energy iterates E n := E(Y n ) modulo the occurrence of the favorable event

E = {Y n ∈ D for all n} (46)
where D = {y ∈ Y : E(y) ≤ E + } is defined as in [START_REF] Juditsky | Solving variational inequalities with stochastic mirrorprox algorithm[END_REF]. In particular, we have the following results:

Lemma 5. Suppose that P(E) > 0. If (Sub) holds, then P(lim inf n→∞ E n = 0 | E) = 1.
Lemma 6. Suppose that P(E) > 0. If (Sum) holds, there exists some finite random variable

E ∞ such that P(lim n→∞ E n = E ∞ | E) = 1.
Proposition 9. Suppose that E is a local energy function for S. If P(E) > 0 and (Sum) holds, then P(X n converges to S | E) = 1.

Proof of Lemma 5. Since P(E) > 0, it suffices to show that the hitting time N a = inf{n ∈ N : E n ≤ a} is finite with probability 1 on E for all sufficiently small a > 0. More precisely, building on an argument of Duvocelle et al. [START_REF] Duvocelle | Multi-agent online learning in time-varying games[END_REF], we will show that the event N a = E ∩ {N a = ∞} has P(N a ) = 0 whenever 0 < a ≤ E + : indeed, if this is the case and a k ∈ (0, E + ), k = 1, 2, . . . , is a sequence converging monotonically to 0, we will have P(N a k ) = 0 for all k ∈ N. Thus, with only a countable number of N a k in play, we will have

P(lim inf n→∞ E n = 0 | E) = P(N a k < ∞ for all k | E) = P( ∞ k=1 {N a k < ∞} | E) = 1 -P( ∞ k=1 {N a k < ∞} | E) = 1 - P(E ∩ ( ∞ k=1 {N a k < ∞})) P(E) = 1 - P( ∞ k=1 N a k ) P(E) = 1, (47)
as per our original assertion. Now, to establish our claim for N a , assume to the contrary that P(N a ) > 0 for some sufficiently small a > 0, and let c a = -sup{ Ė(y) : a ≤ E(y) ≤ E + }, so c a > 0 by Definition 5. Then, by telescoping (36), we get

E n+1 ≤ E 1 + n k=1 γ k Ė(Y k ) + n k=1 γ k ξ k + n k=1 γ k χ k + n k=1 γ k ψ 2 k ≤ E 1 -c a - I n + II n + III n τ n • τ n for all n = 1, 2, . . . (48)
with probability 1 on N a . Since P(N a ) > 0 by assumption and (I n + II n + III n ) τ n → 0 with probability 1 by (Sub), the above gives P(lim n→∞ E n = -∞ | N a ) = 1. However, with inf n E n ≥ a > 0 on N a by construction, we get a contradiction, and our proof is complete. ■ Proof of Lemma 6. Consider the nested sequence of events

E n = { Ė(Y k ) ≤ 0 for all k = 1, 2, . . . , n} (49)
so E = ∞ n=1 E n . Then, letting Ẽn = 1 En E n , Eq. ( 36) readily gives

Ẽn+1 = 1 En+1 E n+1 ≤ 1 En E n+1 ≤ 1 En E n + γ n Ė(Y n ) + γ n ξ n + γ n χ n + γ 2 n ψ 2 n 1 En ≤ Ẽn + γ n 1 En ξ n + γ n χ n + γ 2 n ψ 2 n 1 En , (50)
where we used the fact that

Ė(Y k ) = ⟨v(X k ), ∇E(Y k )⟩ ≤ 0 for all k = 1, 2, . . . , n if E n occurs.
Since E n is F n -measurable, conditioning on F n and taking expectations then yields

E[ Ẽn+1 | F n ] ≤ Ẽn + γ n 1 En E[ξ n | F n ] + 1 En E[γ n χ n + γ 2 n ψ 2 n | F n ] ≤ Ẽn + E[γ n χ n + γ 2 n ψ 2 n | F n ] ≤ Ẽn + γ n HB n + 1 2 βγ 2 n M 2 n . (51)
Now, given that n γ n B n and n γ 2 n M 2 n are both finite by (Sum), Ẽn is an almost supermartingale with summable increments, i.e., n E[ Ẽn+1 | F n ] -Ẽn < ∞ w.p.1. Therefore, by Gladyshev's lemma [53, p. 49], we conclude that Ẽn converges almost surely to some (finite) random variable. Since P(E) > 0 and 1 En = 1 for all n if and only if E occurs, we further deduce that P(E n converges | E) = P( Ẽn converges | E) = 1, and our claim follows. ■ Proof of Proposition 9. By Lemma 4, (Sub) is satisfied whenever (Sum) is. Thus, by a tandem application of Lemmas 5 and 6, we conclude that lim n→∞ E n = 0 with probability 1 on E. Finally, since Q(y) → S whenever E(y) → 0, our claim follows.

■

We are now in a position to prove Propositions 7 and 8.

Proof of Proposition 7. By the definition of a global attractor, we have E + = sup E, so P(E) = 1. Our claim is then an immediate consequence of Proposition 9.

■

Proof of Proposition 8. Suppose that E(Y 1 ) ≤ E + /4. We then claim that the event E always occurs on the intersection of the events E I , E II , and E III , where E Z = {Z n ≤ E + /4 for all n}. Indeed, this being trivially the case for n = 1, assume that Y k ∈ D for all k = 1, 2, . . . , n for some n ≥ 1. Then, telescoping [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF] yields

E n+1 ≤ E 1 + n k=1 γ k Ė(Y k ) + I n + II n + III n ≤ E + /4 + 0 + E + /4 + E + /4 + E + /4 = E + (52)
by the inductive hypothesis and our other assumptions. This shows that E n+1 ∈ D, so the induction argument is complete, and we conclude that E ⊇ E I ∩ E II ∩ E III . Now, by (Stab), we have P(E I ) ≤ η/3 and likewise for the rest, so we get

P(E) ≥ P(E I ∩ E II ∩ E III ) = 1 -P(E I ∪ E II ∪ E III ) ≥ 1 -P(E I ) -P(E II ) -P(E III ) ≥ 1 -η. (53)
Our claim then follows directly from Proposition 9. ■ 6. Fast convergence to coherent sets 6.1. The notion of coherence: definition and examples. In this section, we will show that the analysis of the previous section can be strengthened considerably under a "structural alignment" notion, which we dub coherence. We begin with the definition and a series of motivating examples. Definition 6. A nonempty compact subset S of X will be called coherent if it admits a (finite) set of deviation directions Z = {z 1 , . . . , z m } ⊆ V such that a) ⟨v(x), z⟩ < 0 for all x ∈ S and all z ∈ Z.

(54a) b) Q(y) → S whenever max z∈Z ⟨y, z⟩ → -∞.

In particular, if (54a) holds for all x ∈ X , we will say that S is globally coherent; and if we want to stress that S is coherent but not globally so, we will say that S is locally coherent.

The motivation behind Definition 6 is as follows. First, the geometric condition (54a) posits that any deviation from S along a vector z ∈ Z is actively disincentivized by the players' individual gradient field v so, in a certain sense, v points locally "toward" S. The second condition is game-independent and asks that the elements of Z are sufficient to identify S by acting as primal-dual "support vectors" for S under Q. The terminology "coherence" has been chosen precisely to indicate that these two properties dovetail to create a favorable convergence landscape under (RRM).

To illustrate this notion, we proceed below with a series of examples. The first two concern finite games; the last two concern continuous ones. Example 6.1 (Strict equilibria in finite games). Recall that a strict Nash equilibrium of a finite game Γ = Γ(N , A, u) is a strategy profile x * such that (NE) holds as a strict inequality for all x ̸ = x * . An immediate consequence of this definition is that a) x * is pure, i.e., it is supported on a single pure strategy profile α * ∈ A; and that b) unilateral deviations from α * lead to strictly inferior payoffs, i.e., u α (α * i ; α * -i ) > u i (α i ; α * -i ) for all α i ∈ A i \{α * i }, i ∈ N . With this in mind, consider the set of unilateral deviations

Z = {e iαi -e iα * i : α i ∈ A i \{α * i }, i ∈ N }. (55)
Since ⟨v(x * ), e iαi -e iα

* i ⟩ = u i (α i ; α * -i ) -u i (α * i ; α * -i ) < 0 for all α i ∈ A i \{α * i }, i ∈ N , condition (
54a) is satisfied. Lemma A.4 further shows that Q iαi (y) → 0 whenever y iαiy iα * i → -∞, so the requirement Q(y) → x * of (54b) is also satisfied. In other words, strict equilibria are coherent. ♢ Example 6.2 (Undominated strategies). Recall that a pure strategy α i ∈ A i is dominated by β i ∈ A i if u i (α i ; x -i ) < u i (β i ; x -i ) for all x ∈ X . We then say that α i is eliminated in a mixed strategy profile x ∈ X if α i is not supported in x i , i.e., if x iαi = 0. A fundamental requirement for game-theoretic learning is that dominated strategies become extinct over time, i.e., that the trajectory of play converges to the set X * of action profiles that eliminate all dominated strategies. 10This set is globally coherent. To see this, consider the set of dominating deviations

Z = {e iαi -e iβi : α i is dominated by β i }. (56)
By definition, ⟨v(x), e iαi -e iβi ⟩ = u i (α i ; x -i ) -u i (β i ; x -i ) < 0 for all x ∈ X , so (54a) holds globally. Moreover, for any finite game, X * is a face of X [START_REF] Samuelson | Evolutionary stability in asymmetric games[END_REF] and hence compact. Finally, Lemma A.4 shows that Q iαi (y) → 0 if y iαi -y iβi → -∞, so the requirement Q(y) → X * of (54b) is also satisfied, and we conclude that the set of undominated strategies is globally coherent.

♢ Example 6.3 (Sharp equilibria in concave games). Following Polyak [START_REF] Polyak | Introduction to Optimization[END_REF], a Nash equilibrium of a concave game is sharp if the stationarity condition (FOS) holds as a strict inequality for all x ̸ = x * , i.e., ⟨v(x * ), x -x * ⟩ < 0 for all x ̸ = x * .

(Sharp)

Examples of sharp equilibria include deterministic Nash policies in generic stochastic games [START_REF] Zhang | Gradient play in multi-agent Markov stochastic games: Stationary points and convergence[END_REF], power control and resource allocation games [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory in multiuser communication systems[END_REF], etc. Geometrically, sharp equilibria can be characterized by the condition that v(x * ) lies in the (topological) interior of the polar cone PC(x * ) to X at x * . This means in particular that there exists a polyhedral cone C that is spanned by a finite set of vectors Z = {z 1 , . . . , z m } ⊆ V such that a) the tangent cone TC(x * ) to X at x * is contained in the interior of C; and b) ⟨v(x * ), z⟩ < 0 for all z ∈ Z. Lemma A.5 in Appendix A shows that Q(y) → S if max z∈Z ⟨y, z⟩ → -∞, so we conclude that sharp equilibria are coherent. ♢ Example 6.4 (Stochastic linear programming). To borrow an example from optimization (viewed here as a single-player game), let X be a convex polytope and consider the stochastic linear program maximize u

(x) = E θ [⟨V (θ), x⟩] subject to x ∈ X (SLP)
where V (θ) is a random payoff vector drawn from some complete probability space (Θ, P θ ). By linearity, the set of solutions X * = arg max u of (SLP) is a face of X ; moreover, if we let v = E θ [V (θ)] = ∇u(x), we have ⟨v, x -x * ⟩ < 0 whenever x * ∈ X * and x ∈ X \ X * . Finally, since X is a convex polytope, there exists a finite set of vectors Z = {z 1 , . . . , z m } such that a) x * + z ∈ X \ X * for all x * ∈ X * , z ∈ Z; and b) every point x ∈ X \ X * can be decomposed as x = x * + λz for some x * ∈ X * , z ∈ Z and λ > 0. Lemma A.5 in Appendix A shows that Q(y) → X * whenever ⟨y, z⟩ → -∞ for all z ∈ Z, so (54b) is satisfied and we conclude that the solution set X * of (SLP) is globally coherent.

♢

The above examples illustrate that the notion of coherence underlies a diverse range of game-theoretic settings and problems. In light of this, we devote the rest of this section to analyzing the convergence properties of coherent sets under (RRM). 6.2. Convergence analysis and results. The first thing to note is that, if S is coherent, it admits the local energy function

E(y) = log 1 + z∈Z exp ⟨y, z⟩ (57)
Indeed, if E(y) → inf E = 0, we must have ⟨y, z⟩ → -∞ for all z ∈ Z, and hence Q(y) → S by Definition 6. Moreover, for all y such that x = Q(y) is sufficiently close to S, we have ∇E(y) = z∈Z ⟨v(x), z⟩e ⟨y,z⟩ (1 + z∈Z e ⟨y,z⟩ ) < 0 by the continuity of v. This shows that the requirements of Definition 5 are all satisfied, leading to the following corollary of Theorem 3:

Corollary 9. Suppose that S is coherent, and let X n be the sequence of play of (RRM) with step-size and gradient signal assumptions as in Theorem 3. Then the conclusions of Theorem 3 hold, namely (i) if S is globally coherent, X n converges to S with probability 1; and (ii) if S is locally coherent, X n converges locally to S with probability at least 1 -η if γ is small enough.

Corollary 9 is a strong convergence guarantee in itself, but it does not exploit the sharper structural properties of coherent sets. As we show below, the assumptions of Theorem 3 on the method's step-size and gradient signals can be relaxed considerably, allowing in many cases the use of even constant step-sizes. To simplify the presentation, we will assume throughout that (RRM) adheres to the general parameter schedule [START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF]. In this general setting, we have: Theorem 4. Let X n = Q(Y n ) be the sequence of play generated by (RRM) with step-size and gradient signal sequences as per [START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF]. Then: Case 1: If S is globally coherent, then, from any initialization, X n converges to S w.p.1.

Case 2: If S is locally coherent and, in addition, (i) ℓ γ -ℓ σ > 1/2; or (ii) 0 ≤ ℓ γ < q/(2 + q) and ℓ σ < 1/2 -1/q, there exists an open initialization domain W ⊆ Y such that, for any η > 0

P(X n converges to S | Y 1 ∈ W) ≥ 1 -η (58)
provided that γ > 0 is small enough.

Before discussing the proof of Theorem 4, we present a series of explicit convergence guarantees for specific algorithms: Corollary 10. Suppose that Algorithms 1-7 are run with step-size γ n ∝ 1/n ℓγ , ℓ γ ∈ [0, 1], and, where applicable, a sampling parameter δ n ∝ 1/n ℓ δ , ℓ δ ∈ (0, 1/2). If S is globally coherent, X n converges to S with probability 1 provided the following conditions are met:

• For Algorithms 1 and 4-7: no other requirements needed.

• For Algorithms 2 and 3: ℓ γ > 0.

Corollary 11. Suppose that Algorithms 1-7 are run with step-size γ n ∝ 1/n ℓγ , ℓ γ ∈ [0, 1], and, where applicable, a sampling parameter δ n ∝ 1/n ℓ δ , ℓ δ ∈ (0, 1/2). Then the conclusions of Theorem 4 for locally coherent sets continue to hold provided the following conditions are met:

• For Algorithm 1: ℓ γ > 1/2 if q = 2; no such requirement needed if q > 2.

• For Algorithms 2 and 3: ℓ γ > 1/2 if q = 2; ℓ γ > 0 otherwise.

• For Algorithms 4-7: no other requirements needed.

We should stress here that, depending on the statistical properties of the players' feedback mechanism, the above results imply convergence even with a constant step-size, a feature which is quite unique in the context of stochastic approximation. To the best of our knowledge, the only comparable result in the literature in terms of step-size assumptions is the recent work of Giannou et al. [START_REF] Giannou | The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond[END_REF] for local convergence to strict Nash equilibria: since strict equilibria are locally coherent, the analysis of Giannou et al. [START_REF] Giannou | The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond[END_REF] corresponds to the last item of Corollary 11.

Perhaps surprisingly, the principal reason for this relaxation in terms of step-size requirements is not the boundedness of the q-th moments of the players' oracle: the step-size requirements of Section 5 cannot be relaxed for non-coherent attractors even if q = ∞; at the same time, the convergence guarantees of Theorem 4 for globally coherent sets yield convergence with a constant step-size even when q = 2. Instead, as we hinted at before, these sharper convergence properties are due to the fact that the quadratic error term

III n = n k=1 γ 2 k ψ 2
k is not present in the case of coherent sets: it is precisely this simplification that leads to convergence with significantly faster step-size schedules.

Our last result builds on this observation to show that convergence occurs at a finite number of iterations if the mirror map of the process is surjective (e.g., if it is a Euclidean projection): 11 Theorem 5. Suppose that the mirror map Q : Y → X of (RRM) is surjective. If S is coherent, then, with probability 1, every trajectory X n = Q(Y n ) that converges to S does so in a finite number of iterations, i.e., there exists some n 0 such that X n ∈ S for all n ≥ n 0 .

Corollary 12. Suppose that (RRM) is run with Euclidean projections and step-size and gradient signal sequences as per [START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF]. If S is globally coherent and X is compact, the induced sequence of play X n = Q(Y n ) converges to S in a finite number of iterations (a.s.).

In view of the above, coherent sets comprise perhaps the most well-behaved class of rational outcomes under (RRM): the agents' sequence of play converges to such sets in a finite number of iterations, even with bandit, payoff-based feedback. In turn, this means that the algorithms' long-run behavior remains robust in the face of uncertainty, a property with important implications for the general theory of learning in games. 6.3. Technical proofs. We conclude this section with the proof of Theorem 4. The key step to achieve this is the following refinement of Lemma 3 for coherent sets. Lemma 7. Suppose that S ⊆ X is coherent, and let E z (y) = ⟨y, z⟩ for y ∈ Y, z ∈ Z. Then the iterates

E n = E z (Y n ) of E z satisfy the template inequality E n+1 ≤ E n + γ n ⟨v(X n ), z⟩ + γ n ξ n + γ n χ n . (59)
where the error terms ξ n and χ n are now given by

ξ n = ⟨U n , z⟩ and χ n = max z∈Z ∥z∥ • B n . (60)
Proof. Simply set y ← Y n+1 in E z (y) and invoke the definition of (RRM).

■

Compared to Lemma 3, the template inequality (59) does not have a second-order term, so the second moment of vn plays a much more minor role when dealing with coherent sets. This can be seen very clearly in the following coherent analogue of Proposition 7: Proposition 10. Suppose that S is globally coherent, and let X n = Q(Y n ) be the sequence of play generated by (RRM). If (Sub) holds, then X n converges to S with probability 1.

The crucial difference between Propositions 7 and 10 is that the former requires the summability condition (Sum), while the latter requires only the subleading growth requirement (Sub). The latter assumption grants much more flexibility to the players because they can employ practically any step-size of the form γ n ∝ 1/n ℓγ for some ℓ γ ∈ [0, 1]. A similar situation arises for locally coherent sets, in which case the stability requirement (Stab) can be replaced by the "dominance" condition

P(I n ≤ Cτ µ n /2 for all n) ≥ 1 -η (Dom.I) P(II n ≤ Cτ µ n /2 for all n) ≥ 1 -η (Dom.II)
for some C > 0 and µ ∈ [0, 1). Under this milder condition, we have:

Proposition 11. Suppose that S is locally coherent, fix some confidence level η > 0, and let X n = Q(Y n ) be the sequence of play generated by (RRM). If (Sub) and (Dom) hold, there exists an unbounded open initialization domain W ⊆ Y such that

P(X n converges to S | Y 1 ∈ W) ≥ 1 -(m + 1)η. ( 62
)
11 As we explain in Appendix A, the image im Q of Q coincides with the prox-domain X h = dom ∂h of h.

As such, a sufficient condition for Q to be surjective is for h to be Lipschitz continuous on X .

holds. We are thus left to establish (Dom.I). To that end, let I * n = sup 1≤k≤n |I n | and set P n := P(I * n > Cτ µ n /2) so

P n ≤ E[|I n | q ] (C/2) q τ µq n ≤ c q E[ n k=1 γ 2 k ∥U k ∥ 2 * q/2 ] τ µq n ( 68
)
where c q is a positive constant depending only on C and q, and we used Kolmogorov's inequality [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF]Corollary 2.1] in the first step and the Burkholder-Davis-Gundy inequality [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF]Theorem 2.10] in the second. To proceed, we will require the following variant of Hölder's inequality [6, p. 15]:

n k=1 a k b k ρ ≤ n k=1 a λρ ρ-1 k ρ-1 n k=1 a (1-λ)ρ k b ρ k (69)
valid for all a k , b k ≥ 0 and all ρ > 1, λ ∈ [0, 1). Then, substituting

a k ← γ 2 k , b k ← ∥U k ∥ 2 * , ρ ← q/2 and λ ← 1/2 -1/q, (68) gives P n ≤ c q ( n k=1 γ k ) q/2-1 n k=1 γ 1+q/2 k E[∥U k ∥ q * ] τ µq n ≤ c q n k=1 γ 1+q/2 k σ q k τ 1+(µ-1/2)q n (70)
We now consider two cases, depending on whether the numerator of ( 70) is summable or not. Case 1: ℓ γ (1 + q/2) ≥ 1 + qℓ σ . In this case, the numerator of ( 70) is summable under [START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF], so the fraction in (70) behaves as O(1/n (1-ℓγ )(1+(µ-1/2)q) ).

Case 2: ℓ γ (1 + q/2) < 1 + qℓ σ . In this case, the numerator of ( 70) is not summable under [START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF], so the fraction in (70) behaves as O n 1-ℓγ (1+q/2)+qℓσ n (1-ℓγ )(1+(µ-1/2)q) . Thus, working out the various exponents, a straightforward -if tedious -calculation shows that there exists some µ ∈ (0, 1) such that P n is summable as long as ℓ σ < 1/2 -1/q and 0 ≤ ℓ γ < q/(2 + q). Hence, if γ is sufficiently small relative to η, we conclude that P(I n ≤ Cτ µ n /2 for all n) ≥ 1n P n ≥ 1 -η/2.

Finally, if ℓ γ > 1/2 + ℓ σ , (Dom.I) is a straightforward consequence of (Stab) with Z n ← I n . Our assertion then follows by putting everything together and invoking Proposition 11. ■

We conclude this section with the proof of our finite-time convergence result.

Proof of Theorem 5. Since Q is surjective, Lemma A.1 shows that Q -1 (S) contains a shifted copy of x∈S PC(x). Thus, given that max z∈Z ⟨Y n , z⟩ → -∞ by the proof of Theorem 4, it follows that, for every a ∈ R, there exists some (possibly random) n 0 ≡ n 0 (a) such that max z∈Z ⟨Y n , z⟩ < -a for all n ≥ n 0 . This shows that Y n converges to Q -1 (S) within a finite number of iterations, as claimed.

■

Concluding remarks

The proposed regularized Robbins-Monro (RRM) stochastic approximation framework captures a wide range of existing algorithms, both first-and zeroth-order, and it allows us to derive a series of convergence results in a unified way. Conceptually speaking, an appealing feature of this framework lies in the fact that it provides an analysis bluepring that can be used in several other settings and algorithms of interest. The associated workflow for this is as follows: it suffices to simply estimate the bounds B n and M n for the method under study (in the sense of Table 1); the long-run behavior of the method may then be harvested from Theorems 2-4. We leave the inclusion of even more general frameworks -such as algorithms with adaptive step-sizes, asyncrhonous and/or delayed feedback [START_REF] Héliou | Gradient-free online learning in continuous games with delayed rewards[END_REF][START_REF] Oliveira | Nash equilibrium seeking with arbitrarily delayed player actions[END_REF], etc. -to future work.

Another fruitful direction for future research concerns the wandering behavior of RRM methods. By Conley's decomposition theorem (the "fundamental theorem of dynamical systems"), a flow decomposes into a chain recurrent part and an attracting part; of these, the former is fragile because of the Kupka-Smale theorem, and is actually absent in all but a meager set of flows (in the Baire category sense of the term). This means that, generically, one would expect a learning process to wander about different basins of attraction, until, by the attainability theory of Benaïm [START_REF] Benaïm | Vertex reinforced random walks and a conjecture of Pemantle[END_REF] and Duflo [START_REF] Duflo | Cibles atteignables avec une probabilité positive d'après M. Benaïm[END_REF], it is captured by one of them. Making this statement precise would complement our results in an essential way, and would give us a better understanding of the complex phenomena that arise in game-theoretic learning.

(1) F S (y) ≥ 0 with equality if and only if Q(y) ∈ S. Moreover, under the reciprocity condition (R), we have F S (y) → 0 if and only if Q(y) → S.

(2) F S is differentiable and ∇F S (y) = Q(y) -Q S (y), where Q S (y) = arg max x∈S {⟨y, x⟩h(x)}.

(3) For all y, y ′ ∈ Y we have ∥∇F S (y ′ ) -∇F S (y)∥ ≤ (2/K)∥y ′ -y∥ * .

Proof. Since S ⊆ X , we have h * S ≤ h * by definition, and hence F S ≥ 0. Moreover, since the minimum in (A.4) must be attained in S, we get F S (y) = 0 if and only if h(p) -h * (y) -⟨y, p⟩ = 0 for some p ∈ S; by Lemma A.2, this occurs if and only if Q(y) = p ∈ S, so our first claim follows.

Moving forward, to show that F S (y) → 0 if and only if Q(y) → S, let y n be a sequence in Y, and let x n = Q(y n ). For the "if" part, since S is compact, we may assume without loss of generality (and by descending to a subsequence if necessary) that x n converges to some x ∈ S. Observe now that a) 0 ≤ F S (y n ) ≤ F (x, y n ) by the minimum (A.4); and b) F (x, y n ) → 0 by (R). Thus, by sandwiching, we conclude that F S (y n ) → 0. Conversely, if F S (y n ) → 0, we may again assume by compactness (and by descending to a subsequence if necessary) that x n = Q(y n ) converges to some x ∈ X . If x ̸ ∈ S, then, by (R), we have lim n→∞ F (x, y n ) > 0 for all x ∈ S. Since S is compact and F (x, y) is continuous in x, we conclude that lim inf n→∞ F S (y n ) > 0, a contradiction which establishes our claim.

Our last two claims follow by applying Lemma A.1 to h and h + δ S where δ S denotes the convex indicator of S.

■

The next properties we discuss concern the way that different regions of Y are mapped to X under Q. Lemma A.5. Let h be a regularizer on X , let y n , n = 1, 2, . . . be a sequence in Y, and fix some x ∈ X . If ⟨y n , z⟩ → -∞ for every nonzero z ∈ TC(x), we have Q(y n ) → x.

Proof. Assume that lim sup n ∥x n -x∥ > 0. Then, given that y n ∈ ∂h(x n ), we get h(x) ≥ h(x n ) + ⟨y n , x -x n ⟩ ≥ h(x n ) -⟨y n , z n ⟩∥x n -x∥, where we set z n = (x n -x)/∥x n -x∥. If we further assume (by descending to a subsequence if needed) that z n converges in the unit sphere of ∥•∥, there exists some z ∈ TC(x) with ∥z∥ = 1 and such that ⟨y n , z n ⟩ ≤ (1 + ε)⟨y n , z⟩ for some ε > 0. Thus, taking the lim sup of the above estimate gives h(x) ≥ ∞, a contradiction which proves our claim. ■ Lemma A.6. Let h be a regularizer on a convex polytope P of V, let S be a face of P, and let Z = {z 1 , . . . , z m } be a set of unit vectors of V such that every point x ∈ P \ S can be written as x = p + λz for some p ∈ S, z ∈ Z and λ > 0. If max z∈Z ⟨y, z⟩ → -∞, then Q(y) → S.

Proof. By the compactness of P (and descending to a subsequence if necessary), we may assume that x n = Q(y n ) converges to some x ∈ P. If x / ∈ S, there exist p ∈ S, z ∈ Z and λ > 0 such that x = p + λz. In turn, this gives h(p) ≥ h(x n ) + ⟨y n , p -x n ⟩ = h(x n ) -⟨y n , z n ⟩∥x n -p∥ where we set z n = (x n -p)/∥x n -p∥. Since z n → z, taking n → ∞ yields h(p) ≥ ∞, a contradiction which shows that x = lim x n ∈ S, as claimed.

■

We conclude this appendix with the dynamical properties of the Fenchel coupling under (MD). The heavy lifting will be provided by the following simple lemma: Lemma A.7. Let x(t) = Q(y(t)) be an orbit of (MD). Then, for every nonempty closed convex subset S of X , we have ḞS (y) = ⟨v(x), x -x S ⟩ (A.5)

(1) For the first (Lipschitz continuity and smoothness), note that ∇E(y) = φ ′ (F S (y))∇F S (y), so, lettting x = Q(y) and x S = Q S (y), Lemma A.3 yields By the reciprocity condition (R), it follows that the set {x = Q(y) : F S (y) ≥ 1} is well-separated from S, so ∥x -pr S (x)∥ is bounded away from zero if F S (y) ≥ 1. Thus, by combining Eqs. (B.11) and (B.12), we conclude that ∥∇E(y)∥ is bounded. Finally, again by Lemma A.2, F (y) is (1/K)-Lipschitz smooth, so Eq. ( 35) -which is equivalent to the Lipschitz smoothness of E -follows immediately from the concavity of φ.

∇E(y) = (x -x S ) • 1 if F S (y) ≤ 1,
(2) For the positive-definiteness requirement of Definition 5, note that Lemma A.3 and the reciprocity condition (R) yield Q(y) → S if and only if F S (y) → 0. Thus, given that φ(z) = z for small z, the same will hold for E = φ • F S , and our claim follows.

(3) Finally, for the Lyapunov properties of E under (MD), recall that Lemma A.7 gives ḞS (y) = ⟨v(x), x -x S ⟩, so Ė(y) = ⟨ ẏ, ∇E(y)⟩ = φ ′ (F (y))⟨v(x), x -x S ⟩ < 0 whenever x ∈ U \ S (B. [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF] where we used the defining property (B.7) of S (recall that x S ∈ S by construction). Moving forward, by Lemma A.3, there exists some E + > 0 such that the sublevel set D = {y ∈ Y : F S (y) ≤ E + } is mapped to U under Q, i.e., Q(y) ∈ U whenever F S (y) ≤ E + . Thus, putting everything together, we conclude that Ė(y) → 0 if and only if F S (y) → 0, which implies that sup{ Ė(y) : E -< E(y) < E + } < 0 for all E -∈ (0, E + ), and our proof is complete.

■

  Proof. Lemma A.1 in Appendix A shows that Q is Lipschitz continuous. Since v is also Lipschitz continuous by Assumption 1, our assertion follows from Benaïm & Hirsch [7, Theorem 0.1].

Example 4 . 1 .

 41 Take X = V and Q(y) = y as in Example 3.1. Then (MD) trivially gives the (individual) gradient dynamicsẋ = v(x) (GD) Example 4.2. Let X i = ∆(A i ) and take Q i = Λ i as in Example 3.2.Then, by a standard calculation, (MD) boils down to the replicator dynamics of Taylor & Jonker[START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF]

■

Figure 1 :

 1 Figure 1: The long-run behavior of different online learning algorithms in the two-player min-max game defined by the loss function L(x1, x2) = x1x2 +ε[ϕ(x2)ϕ(x1)] with ϕ(z) = 2z 2 -4z 4 , ε ≥ 0, and x1, x2 ∈ [-1, 1].The left plot shows two different initializations of (SGA), while the right plot displays the trajectories of (SGA) and (EG) from the same initialization. In both cases, the existence of an attractor allows for robust predictions that are largely independent of the initialization or exact update structure of (RRM).

Figure 2 :

 2 Figure2: Learning in a 2-player discoordination game. All algorithms under study converge to a corner critical point which resists deviations by one of the players (but not the other). The critical point at (0, 0) is unstable to deviations by both players, and no trajectories converge there, even though it is the only interior ICT of (MD).

Lemma A. 4 (

 4 Mertikopoulos & Sandholm, 2016, Prop. A.1). Let h be a regularizer on the simplex ∆(A) ⊆ R A . If y α -y β → -∞, then Q α (y) → 0.

2 K 1 +

 21 Lemma A.2, we also have F (p, y) ≥ (K/2)∥x -p∥ 2 for all p ∈ S, so, by minimizing over p ∈ S, we getF S (y) ≥ (K/2) dist(x, S) 2 = (K/2)∥x -pr S (x)∥ 2 (B.10)where pr S (x) := arg min p∈S ∥x -p∥. In turn, this gives ∥x -pr S (x)∥ ≤ 2/K whenever F S (y) ≤ 1, so we get∥∇E(y)∥ = ∥x -x S ∥ ≤ ∥x -pr S (x)∥ + ∥pr S (x) -x S ∥ ≤ 2/K + diam(S) (B.11)whenever F S (y) ≤ 1. On the other hand, if F S (y) ≥ 1, we have∥∇E(y)∥ = ∥∇F S (y)∥ F S (y) ≤ 2 K ∥x -x S ∥ ∥x -pr S (x)∥# by (B.9) and (B.10)≤ ∥pr S (x) -x S ∥ ∥x -pr S (x)∥ # by the triangle inequality ∥x -pr S (x)∥ (B.12)

  any local maximum of Φ is a local Nash equilibrium of G; and b) any strict local maximum of Φ is variationally stable. The Cournot oligopoly of Example 2.2 is a textbook example of a potential game; other examples include finite congestion games

In some cases, the index set may be enlarged to include all positive half-integers (n = 1/2, 1, 3/2, . . . ).

A point y ∈ Y is said to be attainable by Yn if, for every neighborhood W of y in Y and for all n ≥ 1, we have P(Y k ∈ W for some k ≥ n) > 0.

For the general case, takeE(y) = [h * (y) -inf h * ] -1 .

The case of mixed strategies dominated by mixed strategies requires heavier notation, so we do not treat it.

Acknowledgments P. Mertikopoulos is grateful for financial support by the French National Research Agency (ANR) in the framework of the "Investissements d'avenir" program (ANR-15-IDEX-02), the LabEx PER-SYVAL (ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003), and the bilateral ANR-NRF grant ALIAS (ANR-19-CE48-0018-01). This project has also received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and

To prove Propositions 10 and 11 -and, through them Theorems 4 and 5 -it will be convenient to introduce the family of sets W(a) = {y ∈ Y : max z∈Z ⟨y, z⟩ < -a}.

(

By Definition 6, these sets are mapped to neighborhoods of S under Q, so they are particularly well-suited to serve as initialization domains for (RRM). In particular, by the requirements of Definition 6 and the continuity of v, there exists some a such that c := -sup{⟨v(Q(y)), z⟩ : y ∈ W(a), z ∈ Z} < 0. With all this in hand, the proofs of Propositions 10 and 11 are fairly straightforward.

Proof of Proposition 10. Since S is globally coherent, we can take a = -∞ in the definition of W(a) above. Then, telescoping [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N -person games[END_REF] readily yields

Thus, if (Sub) holds, we get E z (Y n ) → -∞ for all z ∈ Z, i.e., X n = Q(Y n ) → S.

■

Proof of Proposition 11. Let µ ∈ [0, 1) be such that (Dom) holds for every z ∈ Z (recall that ξ n depends on z), and let ∆a = max n {Cτ µ n -cτ n }. Then, if Y 1 is initialized in W := W(a + ∆a), we claim that Y n ∈ W(a) for all n. Indeed, this being trivially true for n = 1, assume it to be the case for all k = 1, 2, . . . , n. Then, by [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N -person games[END_REF] and our inductive hypothesis, we get

i.e., Y n+1 ∈ W(a), as claimed. Since Y n ∈ W(a) for all n, we conclude that (64) holds with probability 1 on the event that (Dom.I) and (Dom.II) both hold for all z ∈ Z. Since (Dom.I) involves |Z| = m separate events (one for each z ∈ Z) and II n does not depend on z, it follows that E z (Y n ) → -∞ for all z ∈ Z with probability at least 1 -(m + 1)η. Our claim then follows from Definition 6.

■

We are now in a position to prove Theorem 4.

Proof of Theorem 4. As in the case of Theorem 3, our proof will hinge on showing that (Sub) and (Dom) hold under the stated step-size and sampling parameter schedules. Our claim will then follow by a direct application of Propositions 10 and 11. First, regarding (Sub), the law of large numbers for martingale difference sequences [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF]Theorem 2.18] shows that I n /τ n → 0 w.p.1 on the event

so, in turn, given that ℓ σ < 1/2, we get

This establishes (Sub) for Z n ← I n ; as for the case of II n , our claim follows by noting that [START_REF] Hsieh | The limits of min-max optimization algorithms: Convergence to spurious non-critical sets[END_REF]. This shows that (Sub) holds, so the first case of the theorem follows from Proposition 10. Now, for the second case of the theorem, since B n is deterministic and B n = O(1/n ℓ b ) for some ℓ b > 0, it is always possible to find C > 0 and µ ∈ (0, 1) so that (Dom.II)

Appendix A. Regularizers and mirror maps

In this appendix we present some basic properties of the mirror map Q. To state them, recall first that the subdifferential of a h at x ∈ X is defined as ∂h(x) := {y ∈ Y : h(x ′ ) ≥ h(x) + ⟨y, x ′ -x⟩ for all x ′ ∈ V}, the domain of subdifferentiability of h is dom ∂h := {x ∈ dom h : ∂h ̸ = ∅}, and the convex conjugate of h is defined as h * (y) = max x∈X {⟨y, x⟩ -h(x)} for all y ∈ Y. We then have the following basic results.

Lemma A.1. Let h be a regularizer on X , and let Q : Y → X be its induced mirror map. Then:

(1) Q is single-valued on Y: in particular, for all x ∈ X , y ∈ Y, we have x = Q(y) ⇐⇒ y ∈ ∂h(x).

(2) The prox-domain

(4) For all x ∈ ri X , we have y, y ′ ∈ ∂h(x) if and only if ⟨y ′ -y, x ′ -x⟩ = 0 for all x ′ ∈ X .

Our second basic result concerns the Fenchel coupling

For our purposes, the most relevant properties of F are as follows:

Lemma A.2. For all p ∈ X and all y, y ′ ∈ Y, we have:

In particular, if h(0) = 0, we have

Variants of Lemmas A.1 and A.2 already exist in the literature (see e.g., [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] and references therein), so we do not provide a proof. Instead, we proceed below to show how the above extends to the setwise Fenchel coupling Error bounds for specific algorithms. Our aim in this appendix is to prove the bounds on the bias and magnitude of vn reported in Proposition 3 and Table 1.

Proof of Proposition 3. We proceed in a method-by-method basis starting with the oraclebased methods of Section 3.2, that is, Algorithms 1-4. For this, we will make free use of the fact that we can take M q n = 3 q-1 (G q + B q n + σ q n ) in ( 8), cf. the discussion after (6).

▶ Algorithm 1: Stochastic gradient ascent. For (SGA), we have U n = err(X n ; θ n ) and b n = 0, so our claim follows immediately from the stated assumptions for (SFO).

▶ Algorithm 2: Extra-gradient. For (EG), we have vn = V (X n+1/2 ;

We thus get

and, analogously 1) under ( 13), as claimed.

▶ Algorithm 3: Optimistic gradient. For (OG), we have again

so the same series of arguments as above gives

under [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF] with q = ∞. The noise term U n can be bounded in exactly the same way, so we omit the calculations.

▶ Algorithm 4: Exponential / multiplicative weights. We consider two cases, based on the information available to the players. For the full information oracle (14a), we have vn = v(X n ) so b n = U n = 0 by definition (i.e., the oracle is perfect). Otherwise, under the realization-based oracle (14b), we have

We thus get b n = 0 and U n = O(1), which proves our assertion.

We now proceed with the payoff-based methods of Section 3.2, namely Algorithms 5-7.

▶ Algorithm 5: Single-point stochastic approximation. Since u i is assumed bounded in the context of (SPSA), the bound for M n follows trivially. As for the bias of (SPSA), it will be convenient to set V δ i (x; w) = (d i /δ) u i (x+δw) w i so, in obvious notation, vi,n = V δn i (X n ; W n ). Thus, if we fix a pivot point x ∈ X and a query point x = x + δw for some w ∈ E = i E i , a first-order Taylor expansion of u i with integral remainder gives

where we set z = x -x = δw. Hence, if w is drawn uniformly at random from E, taking expectations yields

where we used the fact that E[w i ] = 0 for all i ∈ N and that w i and w j are independent for all i, j ∈ N , i ̸ = j. As for the second term, Assumption 1 readily yields

Thus, by combining (B.5) and (B.6), we conclude that b

) by the definition of X n+1/2 , expanding the logairthm readily yiels B n = O(1/n) and M n = O(1). Our claim then follows as above.

▶ Algorithm 7: Exponential weights for exploration and exploitation. Since αn is sampled according to Xn , we readily get

, and our proof is complete. ■ B.2. Energy function derivations. Our aim in this last appendix is to prove the energy properties of the Fenchel coupling as stated in Lemmas 1 and 2. For concision, we will prove both as a special case of the following general result: Proposition B.1. Let S be a nonempty compact convex subset of X , and assume that there exists a neighborhood U of S such that Proof. We will verify the requirements of Definition 5 in order.

innovation programme (grant agreement № 725594-TIME-DATA) and from the Swiss National Science Foundation (SNSF) under grant number 200021-205011.