Pierre Coucheney

Bruno Gaujal

Panayotis Mertikopoulos

Entropy-driven dynamics and robust learning procedures in games

Keywords: Reinforcement Learning, Stochastic Approximation, Quantal Response Equilibria, Entropy Apprentissage par renforcement, approximation stochastique, équilibres de réponse quantitative, entropie

In this paper, we introduce a new class of game dynamics made of a pay-off replicator-like term modulated by an entropy barrier which keeps players away from the boundary of the strategy space. We show that these entropy-driven dynamics are equivalent to players computing a score as their on-going exponentially discounted cumulative payoff and then using a quantal choice model on the scores to pick an action. This dual perspective on entropy-driven dynamics helps us to extend the folk theorem on convergence to quantal response equilibria to this case, for potential games. It also provides the main ingredients to design a discrete time effective learning algorithm that is fully distributed and only requires partial information to converge to QRE. This convergence is resilient to stochastic perturbations and observation errors and does not require any synchronization between the players.

Owing to the computational complexity of Nash equilibria and related game-theoretic solution concepts, algorithms and processes for learning in games have received considerable attention over the last two decades. Such procedures can be divided into two broad categories, depending on whether they evolve in continuous or discrete time: the former class includes the numerous dynamics for learning and evolution (see e.g. Sandholm [START_REF] Sandholm | Population Games and Evolutionary Dynamics. Economic learning and social evolution[END_REF] for a recent survey), whereas the latter focuses on learning in infinitely iterated games, such as fictitious play and its variants -for an overview, see Fudenberg and Levine [START_REF] Fudenberg | The Theory of Learning in Games, Economic learning and social evolution[END_REF] and references therein.

A key challenge in these endeavors is that it is often unreasonable to assume that players are capable of monitoring the strategies of their opponents -or even of calculating the payoffs of actions that they did not play. As a result, much of the literature of learning in games revolves around payoff-based adaptive schemes which only require players to observe the stream of their in-game payoffs: for instance, in the framework of cumulative reinforcement learning, players use their observed payoff information to score their actions based on their estimated performance over time, and they then use a fixed decision model (such as logit choice) to determine their actions at the next instance of play. The convergence of such algorithms in 2-player games has been studied from a Q-learning perspective by Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF] and Tuyls et al. [START_REF] Tuyls | An evolutionary dynamical analysis of multi-agent learning in iterated games[END_REF] whereas, more recently, Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] and Bravo [START_REF] Bravo | An adjusted payoff-based procedure for normal form games[END_REF] took a movingaverage approach for scoring actions in general N -player games and studied the long-term behavior of the resulting dynamics. Interestingly, in all these cases, when the learning process converges, it converges to a perturbed Nash equilibrium of the game -viz. a fixed point of a perturbed best-response correspondence (Fudenberg and Levine [START_REF] Fudenberg | The Theory of Learning in Games, Economic learning and social evolution[END_REF]).

Stochastic processes of this kind are usually analyzed with the ODE method of stochastic approximation which essentially compares the long-term behavior of the discrete-time process to the corresponding mean-field dynamics in continuous time -see e.g. the surveys by Benaïm [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF] and Borkar [START_REF] Borkar | Stochastic approximation[END_REF]. Indeed, there are several sufficient conditions which guarantee that a discrete-time process and its continuous counterpart both converge asymptotically to the same sets, so the continuous dynamics are usually derived as a limit of a discrete-time (and possibly random) process rooted in some adaptive learning scheme -cf. the aforementioned works by Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF], Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF], and Bravo [START_REF] Bravo | An adjusted payoff-based procedure for normal form games[END_REF].

Contrary to this approach, we proceed from the continuous to the discrete and develop two different learning processes from the same dynamical system (the actual algorithm depends crucially on whether we look at the evolution of the players' strategies or the performance scores of their actions). Accordingly, the first contribution of our paper is to derive a class of entropy-driven game dynamics which consist of a replicator-like term plus a barrier term that keeps players from approaching the boundary of the state space by imposing an entropic penalty to their payoffs -hence the dynamics' name. Interestingly, these dynamics are equivalent to players scoring their actions by taking an exponentially discounted (and continuously updated) aggregate of their payoffs and then using a quantal choice model to pick an action (McKelvey and Palfrey [START_REF] Mckelvey | Quantal response equilibria for normal form games[END_REF]); as such, entropy-driven dynamics constitute the strategy-space counterpart of the Q-learning dynamics of Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF] -see also Tuyls et al. [START_REF] Tuyls | An evolutionary dynamical analysis of multi-agent learning in iterated games[END_REF].

Another important feature of these dynamics is their temperature, a parameter which specifies the relative weight of the dynamics' entropic barrier term with respect to the game's payoffs -and also measures the weight that players attribute to past events, viz. the discount factor of their payoff aggregation scheme. These considerations allow us to derive a number of quite general results such as the dynamics' convergence to quantal response equilibria (QRE) in potential games and an extension of the well-known folk theorem of evolutionary game theory (Hofbauer and Sigmund [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF]). In particular, we show that stability and convergence depend crucially on the temperature of the dynamics: at zero temperature, strict Nash equilibria are the only stable and attracting states of the dynamics, just as in the case of the replicator equation; for negative temperatures, all pure action profiles are attracting (but with vastly different basins of attraction), whereas for low positive temperatures, only QRE that are close to strict equilibria remain asymptotically stable.

The second important contribution of our paper concerns the practical implementation of entropydriven game dynamics as learning algorithms with the following desirable properties:

1. The learning proceducre is payoff-based, fully distributed and stateless -players only need to observe their in-game payoffs and no knowledge of the game's structure or of the algorithm's state is required.

2. Payoffs may be subject to stochastic perturbations and observation errors; in fact, payoff observations need not even be up-to-date.

3. Updates need not be synchronized -there is no need for a global, centralized update clock used by all players.

These properties are key for the design of robust, decentralized optimization protocols in network and traffic engineering, but they also pose significant obstacles to convergence. Be that as it may, the convergence and boundary-avoidance properties of the continuous-time dynamics allow us to show that players converge to arbitrarily precise quantal approximations of strict Nash equilibria in potential games (Theorem 15 and Propositions 16,[START_REF] Lee | Introduction to Smooth Manifolds[END_REF]. Thus, thanks to the congestion characterization of such games (Monderer and Shapley [START_REF] Monderer | Potential games[END_REF]), we obtain a powerful distributed optimization method for a wide class of engineering problems, ranging from traffic routing (Altman et al. [START_REF] Altman | A survey on networking games in telecommunications[END_REF]) to wireless communications (Mertikopoulos et al. [START_REF] Mertikopoulos | Matrix exponential learning: Distributed optimization in MIMO systems[END_REF]).

1.1 Paper outline and structure.

After a few preliminaries in the rest of this section, our analysis proper begins in Section 2 where we introduce our cumulative reinforcement learning scheme and derive the associated entropy-driven game dynamics. Owing to the duality between the evolution of the players' mixed strategies and the performance scores of their actions (measured by an exponentially discounted aggregate of past payofs), we obtain two equivalent formulations of the dynamics: the score-based integral equation (ERL) and the strategy-based dynamics (ED).

In Section ??, we exploit this interplay to derive certain properties of the entropy-driven game dynamics, namely their convergence to perturbed equilibria in potential games (Proposition 7), and a variant of the folk theorem of evolutionary game theory (Theorem 10). Finally, Section 4 is devoted to the discretization of the dynamics (ERL) and (ED), yielding Algorithms 1 and 2 respectively. By using stochastic approximation techniques, we show that when the players' learning temperature is positive (corresponding to an exponential discount factor λ < 1), then the strategy-based algorithm converges almost surely to perturbed strict equilibria in potential games (Theorem 15), even in the presence of noise (Proposition 16) and/or update asynchronicities (Proposition 17).

Notational conventions.

If S = {s α } n α=0 is a finite set, the vector space spanned by S over R will be the set R S of all maps x : S → R, s ∈ S → x s ∈ R. The canonical basis {e s } s ∈S of this space consists of the indicator functions e s : S → R which take the value e s (s) = 1 on s and vanish otherwise, so thanks to the natural identification s → e s , we will make no distinction between s ∈ S and the corresponding basis vector e s of R S . Likewise, to avoid drowning in a morass of indices, we will frequently use the index α to refer interchangeably to either s α or e α (writing e.g. x α instead of the more unwieldy x s α ); in a similar vein, if {S k } k ∈K is a finite family of finite sets indexed by k ∈ K, we will use the shorthands (α; α -k ) for the tuple (α 0 , . . . , α k -1 , α, α k +1 , . . . ) ∈ k S k and k α in place of α ∈S k . We will also identify the set ∆(S) of probability measures on S with the unit n-dimensional simplex ∆(S) ≡ {x ∈ R S : α x α = 1 and x α ≥ 0} of R S . Since ∆(S) is a smooth submanifold-with-corners of R S , by a smooth function on ∆(S) we will mean a C ∞ function in the smooth structure that ∆(S) inherits from R S (Lee [START_REF] Lee | Introduction to Smooth Manifolds[END_REF]). Moreover, if S 0 ≡ S \ {s 0 }, we will write proj 0 (x) ≡ x -0 = (x 1 , . . . , x n ) for the induced surjection

x ∈ R S → x | S 0 ∈ R S 0 .
Regarding players and their actions, we will follow the original convention of Nash and employ Latin indices (k , , . . . ) for players, while keeping Greek ones (α, β, . . . ) for their actions (pure strategies); finally, unless otherwise mentioned, we will use α, β, . . . , for indices that start at 0, and µ, ν, . . . , for those which start at 1.

Definitions from game theory.

A finite game G ≡ G(N, A, u) will be a tuple consisting of a) a finite set of players N = {1, . . . , N }; b) a finite set A k of actions (or pure strategies) for each player k ∈ N; and c) the players' payoff functions u k : A → R, where A ≡ k A k denotes the game's action space, i.e. the set of all action profiles

(α 1 , . . . , α N ), α k ∈ A k . More succinctly, if A * ≡ k A k = {(α, k) : α ∈ A k }
is the disjoint union of the players' action sets, then the payoff map of G will be the map u :

A → R A * k R A k which sends the profile (α 1 , . . . , α N ) ∈ A to the payoff vector (u k (α; α -k )) α ∈A k ,k ∈N ∈ k R A k .
A restriction of G will then be a game G ≡ G (N, A , u ) with the same players as G, each with a subset A k ⊆ A k of their original actions, and with payoff functions u k ≡ u k | A suitably restricted to the reduced action space

A = k A k .
Of course, players can mix their actions by taking probability distributions x k = (x kα ) α ∈A k ∈ ∆(A k ) over their action sets A k . In that case, their expected payoffs will be

u k (x) = 1 α 1 • • • N α N u k (α 1 , . . . , α N ) x 1,α 1 • • • x N,α N , (1)
where x = (x 1 , . . . , x N ) denotes the players' (mixed) strategy profile and u k (α 1 , . . . , α N ) is the payoff to player k in the (pure) action profile (α 1 , . . . , α N ) ∈ A;1 more explicitly, if player k plays the pure strategy α ∈ A k , we will use the notation u kα (x) ≡ u k (α; x -k ) = u k (x 1 , . . . , α, . . . , x N ). In this mixed context, the strategy space of player k will be the simplex X k ≡ ∆(A k ) while the strategy space of the game will be the convex polytope X ≡ k X k . Together with the players' (expected) payoff functions u k : X → R, the tuple (N, X , u) will be called the mixed extension of G and it will also be denoted by G (relying on context to resolve any ambiguities).

The most prominent solution concept in game theory is that of Nash equilibrium (NE) which characterizes profiles that are resilient against unilateral deviations. We will thus say that q ∈ X is a Nash equilibrium of G when

u k (x k ; q -k ) ≤ u k (q) for all x k ∈ X k and for all k ∈ N. (NE)
In particular, if (NE) is strict for all x k ∈ X k \ {q k }, k ∈ N, then q will be called a strict Nash equilibrium. An especially relevant class of finite games is obtained when the players' payoff functions satisfy the potential property :

u kα (x) -u k β (x) = U(α; x -k ) -U(β; x -k ) (2)
for some (necessarily) multilinear function U : X → R. When this is the case, the game will be called a potential game with potential function U, and as is well known, the pure Nash equilibria of G will be precisely the vertices of X that are local maximizers of U (Monderer and Shapley [START_REF] Monderer | Potential games[END_REF]).

2 Reinforcement learning and entropy-driven dynamics.

In this section, our aim will be to derive a class of continuous-time learning dynamics based on the following cumulative reinforcement premise: agents accumulate a long-term "performance score" for each of their actions and they then use a smooth choice function to map these scores to strategies and continue playing. More precisely:

1. The assessment phase (Section 2.2) will comprise the scheme with which players aggregate past payoff information in order to update their actions' performance scores.

2. The choice phase (Section 2.3) will then describe how these scores are used to select a mixed strategy.

For simplicity, we will first derive the dynamics that correspond to this learning process in the case of a single player whose payoffs are determined at each instance of play by Nature-the case of several players involved in a finite game will be entirely similar. Furthermore, the passage from discrete to continuous time will be done here at a heuristic level and we will assume that players have perfect payoff information, that is: a) they are assumed able to observe or otherwise calculate the payoffs of all their actions; and b) unless mentioned otherwise, this payoff information will be assumed accurate and not subject to measurement errors or other exogenous perturbations. The precise interplay between discrete and continuous time and the effect of imperfect information and stochastic fluctuations will be explored in detail in Section 4.

The model.

In view of the above, our single-player learning model will be as follows: at time t, an agent makes a discrete choice from the elements of a finite set A = {α 0 , α 1 , . . . , α n } (representing e.g. the routes of a traffic network, different stock options, etc.). We will denote the payoff to α ∈ A at time t by u α (t), and the agent's assessment of his actions' performance up to instance t will be represented by the score variables y α (t) ∈ R, α ∈ A. In this context, the assessment phase will describe how y α (t) is updated using the payoffs u α (s), s ≤ t, of all past instances of play, whereas the choice stage will specify the choice map Q : R A → X ≡ ∆(A) which prescribes the agent's mixed strategy x ∈ X given his assessment of each action α ∈ A so far.

2.2

The assessment stage: memory and aggregation of past information.

Assuming for the moment that the agent plays at discrete time intervals s = 0, 1, . . . , t, the class of assessment schemes that we will consider is the familiar and widely used exponential model of long-term performance evaluation

y α (t) = t s=0 λ t -s u α (s), (3)
where λ ∈ (0, +∞) is the model's discounting parameter, u α (t) is the sequence of payoffs corresponding to α ∈ A, and we are assuming for the moment that the model is initially unbiased, i.e. y α (0) = 0. Clearly:

1. For λ ∈ (0, 1) we get the standard exponential discounting model which assigns exponentially more weight to recent observations.

2. If λ = 1 we get the unweighted aggregation scheme y α (t) = t s=1 u α (t) which has been examined in the context of learning by Rustichini [START_REF] Rustichini | Optimal properties of stimulus-response learning models[END_REF], Hofbauer et al. [START_REF] Hofbauer | Time average replicator and best reply dynamics[END_REF], Sorin [START_REF] Sorin | Exponential weight algorithm in continuous time[END_REF], Mertikopoulos and Moustakas [START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF] and many others.

3. For λ > 1, the scheme (3) assigns exponentially more weight to past instances; as such, this case has attracted very little interest in the literature (after all, it seems rather counter-intuitive to discount current events in favor of a possibly irrelevant past). Nevertheless, we will see that the choice λ > 1 leads to some very surprising advantages, so we will not exclude this parameter range from our analysis. Now, if the agent plays at discrete time intervals 0, h, . . . , nh ≡ t with time step h > 0, the exponential model (3) should be replaced by the scale-invariant version:

y α (t) = s ∈[0:t:h] λ t -s u α (s)h, (3 )
where the factor h has been included to make the sum (3 ) intensive in h,2 the notation [0 : t : h] represents the index set {0, h, 2h, . . . , nh = t }, and we plead guilty to a slight abuse of notation for not differentiating between s and s/h in the argument of u α (and between n and t = nh in the case of y α ). Accordingly, the assessment scheme (3 ) yields the recursive updating rule:

y α (t) = u α (t)h + λ h y α (t -h), (4)
which in turn shows that the updating of (3 ) does not require the agent to have infinite memory: scores are simply updated by adding the payoffs obtained over a period h to the scores of the previous period scaled by the discount (or reinforcement) factor λ h .

In this way, letting h → 0 + (and assuming Lipschitz-continuous payoff processes u α (t) for simplicity), we readily obtain the continuous-time model

ẏα (t) = u α (t) -T y α (t), (5)
or, in integral form:

y α (t) = y α (0)e -Tt + t 0 e -T (t -s) u α (s) ds, (5 )
where

T ≡ log(1/λ) (6)
represents the temperature of our performance assessment scheme (see the following sections for a justification of this terminology) and the term y α (0)e -Tt reflects the initial bias y α (0) of the agent (initially taken equal to 0). 3 In tune with our previous discussion, the standard exponential discounting regime λ ∈ (0, 1) will thus correspond to positive temperatures T > 0, unweighted aggregation will be obtained for T → 0, and exponential reinforcing of past observations will be recovered for negative learning temperatures T < 0.

Remark 1. In our context, the scheme (5) emerges quite simply as the differential form of an exponetially discounted model for aggregating past payoffs. It is thus interesting to note that Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF] and Tuyls et al. [START_REF] Tuyls | An evolutionary dynamical analysis of multi-agent learning in iterated games[END_REF] obtained the dynamics (5) for T = 1 from a quite different viewpoint, namely as the continuous-time limit of the Q-learning estimator

y α (t + 1) = y α (t) + γ(t + 1) (u α (t) -y α (t)) × 1(α(t) = α) P(α(t) = α) , (7)
where 1 and P denote respectively the indicator and probability of having chosen α at time t, and γ(t) is an ( 2 -1 )-summable series of time steps (see also Fudenberg and Levine [START_REF] Fudenberg | The Theory of Learning in Games, Economic learning and social evolution[END_REF]). The exact interplay between ( 5) and (7) will be explored in detail in Section 4; for now we simply note that (5) can be interpreted both a model of discounting past information and also as a moving Q-average. While on this point, we should also highlight the relation between [START_REF] Borkar | The ode method for convergence of stochastic approximation and reinforcement learning[END_REF] and the moving average estimator of Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] which omits the factor P(α(t) = α) (or the similar estimator of Bravo [START_REF] Bravo | An adjusted payoff-based procedure for normal form games[END_REF] which has a state-dependent step size). As a result of this difference, the mean-field dynamics of [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] are scaled by the player's mixed strategy x α (t) = P(α(t) = α), leading to the adjusted dynamics ẏα = x α (t) (u α (t)y α (t)). Given this difference in form, there will basically be no overlap between our results and those of Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF], but we will endeavor to draw analogies with their results wherever possible.

The choice stage: smoothed best responses and entropy functions.

Having established the way that an agent updates his assessment vector y ∈ R A over time, we now turn to mapping these scores to mixed strategies x ∈ X ≡ ∆(A) in a smooth fashion. In the theory of discrete choice, this boils down to a smooth best response problem so our aim will be to give a brief overview of the related constructions suitably adapted to our purposes; for a more comprehensive account, see McFadden [START_REF] Mcfadden | Econometric models of probabilistic choice. Structural Analysis of Discrete Data with Econometric Applications[END_REF], Anderson et al. [START_REF] Anderson | Discrete Choice Theory of Product Differentiation[END_REF], or Chapter 5 in Sandholm [START_REF] Sandholm | Population Games and Evolutionary Dynamics. Economic learning and social evolution[END_REF].

To motivate our approach, observe that a natural choice for the agent would be to always pick the action α ∈ A with the highest score; however, this "best response" approach carries several problems: First, if two scores y α and y β happen to be equal (e.g. if there are payoff ties), then this mapping becomes a set-valued correspondence which requires a tie-breaking rule to be resolved (and is theoretically quite cumbersome to boot). Additionally, such a practice could lead to completely discontinuous trajectories of play in continuous time-for instance, when the payoffs u α (t) are driven by an additive white Gaussian noise process, as is commonly the case in information-theoretic applications of game theory; see e.g. Altman et al. [START_REF] Altman | A survey on networking games in telecommunications[END_REF]. Finally, since best responding generically results in picking pure strategies, such a process precludes convergence of strategies to non-pure equilibria in finite games.

In view of the above, a common alternative to the "best response" choice x = arg max α ∈A {y α } is to smooth things out using the Gibbs map G : R A → X defined as 4G α (y) = exp(y α )

β exp(y β ) , α ∈ A (8)
(see e.g. Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF], Fudenberg and Levine [START_REF] Fudenberg | The Theory of Learning in Games, Economic learning and social evolution[END_REF], Hofbauer et al. [START_REF] Hofbauer | Time average replicator and best reply dynamics[END_REF], Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF], Marsili et al. [START_REF] Marsili | Exact solution of a modified El Farol's bar problem: Efficiency and the role of market impact[END_REF], Mertikopoulos and Moustakas [START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF], Rustichini [START_REF] Rustichini | Optimal properties of stimulus-response learning models[END_REF], Sorin [START_REF] Sorin | Exponential weight algorithm in continuous time[END_REF] and many others for uses of this choice map in game-theoretic learning). Indeed, it is well-known that G(y) is the unique solution of the (strictly concave) maximization problem maximize β x β y βg(x),

subject to x α ≥ 0, β x β = 1, (9)
where the Boltzmann-Gibbs entropy g(x) = β x β log x β acts as a control cost adjustment to the agent's average score y = β x β y β (Fudenberg and Levine [START_REF] Fudenberg | The Theory of Learning in Games, Economic learning and social evolution[END_REF], van Damme [START_REF] Van Damme | Stability and perfection of Nash equilibria[END_REF]). In this way, G(y) can be viewed as a smoothed best response : if the control cost is scaled down by some small ε > 0 (i.e. g(x) is replaced by εg(x) in ( 9)), then the resulting solution x ε = G(ε -1 y) of ( 9) represents a smooth approximation to the best response correspondence y → arg max α ∈A {y α } as ε → 0. Interestingly, the Gibbs map can also be seen as a special case of a quantal response function in the sense of McKelvey and Palfrey [START_REF] Mckelvey | Quantal response equilibria for normal form games[END_REF]-or a perturbed best response in the language of Hofbauer and Sandholm [START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF]. To wit, assume that the agents' scores are subject to additive stochastic fluctuations of the form ỹα = y α + ξ α ,

where the ξ α are independently Gumbel-distributed random variables with zero mean and scale parameter ε > 0 (amounting to a variance of ε 2 π 2 /6). Then, the choice probability P α (y) of α ∈ A (defined as the probability that α ∈ A maximizes the perturbed score variable ỹα ) will simply be

P α (y) ≡ P ỹα = max β ỹβ = G α (ε -1 y). (11)
As a result, ordinary best responses are again recovered in the limit where the magnitude of the perturbations (measured by the scale parameter ε > 0 of the Gumbel distribution) approaches 0. More generally, assume that the perturbations ξ α are not Gumbel-distributed but instead follow an arbitrary probability law with a strictly positive and smooth density function. In this context, Hofbauer and Sandholm [START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF] showed that the resulting choice probability vector Q(y) ∈ ∆(A) solves the associated entropy maximization problem

maximize β x β y β -h(x), subject to x α ≥ 0, β x β = 1, (EP)
where the deterministic representation h of ξ h is a smooth, strictly convex function on X ≡ ∆(A). Specifically, the choice probabilities Q α (y) ≡ P( ỹα = max β ỹβ ) determine a strictly convex potential function h * : R A → R such that Q α (y) = ∂h * ∂y α , so h * will be related to the deterministic representation h of ξ via the Legendre-Fenchel transformation (Rockafellar [START_REF] Rockafellar | Convex Analysis[END_REF]):

h * (y) = max x ∈ X β x β y β -h(x) , y ∈ R A . (L-F)
On account of the above, the choice map Q can be viewed either as a quantal response function to some perturbation process ξ, or as a smooth approximation to arg max α y α with respect to an admissible control cost adjustment h (if we take the strictly concave problem (EP) as our starting point). 5 Formally, we have: Definition 1. A function h : X → R ∪ {+∞} will be called a generalized entropy function when:

1. h is convex and finite almost everywhere, except possibly on the relative boundary bd(X) of X.

2. h is smooth on rel int(X) and |dh(x)| → ∞ when x converges to bd(X).

The Hessian tensor Hess(h) of h is positive-definite on rel int(X).

The Legendre-Fenchel conjugate h * of h as defined by (L-F) will be called the free entropy of h, and the map Q : R A → X, y → Q(y) ≡ arg max x ∈ X { β x β y βh(x)}, will be the choice map associated to h. Finally, a generalized entropy function h : X → R will be called regular when a) its restriction to any subface X of X is itself an entropy function, and b) the ratio h (q + vt)/h (q + vt) vanishes as q + vt approaches bd(X ) for all interior points q ∈ rel int(X ) and for all tangent vectors v ∈ T q X . The fact that the choice map Q of an entropy functional is well-defined and single-valued is an easy consequence of the convexity and boundary behavior of h; the smoothness of Q then follows from the implicit function theorem. Thus, given that (EP) allows us to view Q(ε -1 y) as a smooth approximation to arg max α y α for ε → 0 + , the class of choice maps that we will consider will be precisely the maps that are derived from entropy functionals in the sense of Definition 1. A few remarks are thus in order: Remark 1. In statistical mechanics and information theory, entropy functions are concave, so Definition 1 actually describes negative entropies. Besides notational convenience, one of the main reasons for this change of sign is that entropy functions as defined above are essentially smooth functions of Legendre type, with the added non-degeneracy condition of having a strictly definite Hessian (Rockafellar [26]). In fact, Definition 1 with our chosen sign convention bears very close ties to the class of Bregman functions, a key tool in interior point and proximal methods in optimization; for a more detailed account, see e.g. Rockafellar [START_REF] Rockafellar | Convex Analysis[END_REF], Auslender et al. [START_REF] Auslender | Asymptotic analysis for penalty and barrier methods in convex and linear programming[END_REF], Alvarez et al. [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF] and references therein.

Remark 2. Examples of entropy functionals abound; some of the most prominent ones are:

1. The Boltzmann-Gibbs entropy:

h(x) = β x β log x β . (12a)
2. The log-entropy:

h(x) = -β log x β . (12b)
3. The Tsallis entropy:

6 h(x) = (1 -q) -1 β (x β -x q β ), 0 < q ≤ 1. (12c) 4. The Rényi entropy: 6 h(x) = (q -1) -1 log β x q β , 0 < q ≤ 1. ( 12d
)
Except for the Rényi entropy, all of the above examples can be written in the convenient form h(x) = β θ(x β ) for some function θ : [0, +∞) → R ∪ {+∞} with the properties:

1. θ is finite and smooth everywhere except possibly at 0.

2. θ (x) → -∞ as x → 0 + and θ (x) > 0 for all x > 0.

When h can be decomposed in this way, we will follow Alvarez et al. [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF] and say that h is decomposable with Legendre kernel θ.

Remark 3. The regularity requirement of Definition 1 is just a safety net to ensure that h behaves well with respect to restrictions and does not exhibit any pathologies near bd(X). Of the examples ( 12) only the log-entropy (12b) is not regular because it is identically equal to +∞ on every proper subface of X.

Remark 4. Another technical point that underlies Definition 1 is that we are implicitly assuming that h is defined on an open neighborhood of X in R A + so that the derivatives of h are well-defined. The reason that we are not making this assumption explicit is that it may be done away with as follows: Let A 0 ≡ A \ {α 0 } and consider the canonical projection proj 0 : R A → R A 0 defined in components as proj 0 (x 0 , x 1 , . . . , x n ) ≡ x -0 = (x 1 , . . . , x n ). Then, the image X 0 ≡ {w ∈ R A 0 : w µ ≥ 0 and µ w µ ≤ 1} of X under proj 0 will be homeomorphic to X and the inverse to proj 0 on X 0 will be the injective immersion

ι 0 : R A 0 → R A with ι 0 (w 1 , . . . , w n ) = (1 -µ w µ , w 1 , . . . , w n ).
In view of the above, the directional derivatives of h on X may be defined by means of the pullback h 0 ≡ ι * 0 h = h • ι 0 as ∂h ∂w µ ≡ ∂h 0 ∂w µ (and similarly for the Hessian of h).

As one would expect, if h is defined on an open neighborhood of X, we will have ∂h ∂w µ = ∂h ∂x µ -∂h ∂x 0 , so the above discussion reduces to treating x 0 = 1µ w µ as a dependent variable.Conversely, any smooth function h : X → R can be extended smoothly to all of R A + (e.g. via mollification), in which case it is easy to see that the directional derivatives ∂h ∂x µ -∂h ∂x 0 are independent of the extension and the equality ∂h ∂w µ = ∂h ∂x µ -∂h ∂x 0 still holds on X. Consequently, we lose no generality in assuming that h is in fact defined on an open neighborhood of X in R A + , and we will do so throughout the rest of the paper unless explicitly stated otherwise. However, the "reduced" coordinates w = proj 0 (x) and the associated derivations ∂ ∂w µ will be very important in our calculations, so their introduction above is not just a technical triviality.

Entropy-driven learning dynamics.

Combining the results of the previous two sections on how to assess the long-term performance of an action and how to translate these assessments into strategies, we obtain the general class of entropydriven learning processes :

y α (t) = y α (0) e -Tt + t 0 e -T (t -s) u α (s) ds, x(t) = Q(y(t)), (ERL)
where Q is the choice map of the driving entropy h : X → R and T is the model's learning temperature.

From an implementation perspective, the difficulty with (ERL) is twofold: First, for a given entropy function h, it is not always practical to write the choice function Q in a closed-form expression that the agent can use to update his strategies. 7 Furthermore, even when this is possible, (ERL) is a two-step computationally intensive process which does not allow the agent to update his strategies directly. The rest of this section will thus be devoted to writing (ERL) as a continuous-time dynamical system on X that can be updated with minimal computation overhead.

To that end, it will be convenient to work with a modified set of variables which measure the longterm difference in performance between an action µ ∈ A and a "flagged" benchmark action α 0 ∈ A.

Formally, letting A 0 = A \ {α 0 } as in Remark 4 above, the relative score of an action µ ∈ A 0 will be the difference

z µ = y µ -y 0 , (13)
or, more concisely, z = π 0 (y) where π 0 : R A → R A 0 is the submersion

π 0 (y 0 , y 1 , . . . , y n ) = (y 1 -y 0 , . . . , y n -y 0 ) = (z 1 , . . . , z n ). (14)
Thereby, the evolution of z over time will be

żµ = ẏµ -ẏ0 = ∆u µ -T z µ , (ZD)
where now ∆u µ denotes the associated payoff difference

∆u µ ≡ u µ -u 0 , µ ∈ A 0 .
The main advantage of introducing the variables z is that even though the choice map Q : R A → X is not injective (and thus does not admit an inverse), 8 there exists a smooth embedding

Q 0 : R A 0 → X 0 = proj 0 (X) = {x ∈ R A 0 : x µ ≥ 0, µ x µ ≤ 1} such that the following diagram commutes: R A X R A 0 X 0 Q π 0 proj 0 Q 0 ι 0 (15)
With such an embedding at our disposal, we will then be able to translate the dynamics of z ∈ R A 0 to X 0 , and thence to X via the inverse ι 0 of proj 0 on X:

ι 0 (w 1 , . . . , w n ) = (1 -µ w µ , w 1 , . . . , w n ).
To construct Q 0 itself, note that (EP) may be rewritten in terms of z µ = y µy 0 as:

maximize µ w µ z µ -h 0 (w 1 , . . . , w n ), subject to w µ ≥ 0, µ w µ ≤ 1, ( EP 0 )
where

h 0 ≡ ι * 0 h = h • ι 0 , i.e. h 0 (w 1 , . . . , w n ) = h(1 -µ w µ , w 1 , . . . , w n ).
Similarly to (EP), the (unique) solution of (EP 0 ) will lie in the interior int(X 0 ) of X 0 , so we will have x = Q(y) iff

z µ = ∂h 0 ∂w µ = ∂h ∂x µ - ∂h ∂x 0 , (16)
i.e. iff z = F 0 (w) where F 0 : int(X 0 ) → R A 0 denotes the gradient F 0 (w) = ∇ h 0 (w), w ∈ int(X 0 ). As it turns out, the required embedding Q 0 is simply the inverse of F 0 :

Lemma 2. Let h : X → R be a generalized entropy function. Then, the map

F 0 ≡ ∇ h 0 : int(X 0 ) → R A 0 defined above is a diffeomorphism whose inverse Q 0 ≡ F -1 0 makes the diagram (15) commute. Proof.
Proof. The fact that F 0 is a continuous bijection with continuous inverse follows from the general theory of Legendre-type functions-see e.g. Theorem 26.5 in Rockafellar [START_REF] Rockafellar | Convex Analysis[END_REF]; the diagram (15) then commutes on account of the equivalence x = Q(y) ⇔ π 0 (y) = F 0 (proj 0 (x)). Finally, to show that F 0 is indeed a diffeomorphism, note that the Jacobian of F 0 is just the Hessian of h 0 , and with Hess(h) strictly positive-definite by assumption, our claim follows from the inverse function theorem (see e.g. Lee [START_REF] Lee | Introduction to Smooth Manifolds[END_REF]).

Having established a diffeomorphism between the variables z µ and w µ , let h µν denote the elements of the corresponding Jacobian matrix J F 0 = Hess(h 0 ), i.e.

h µν = ∂z µ ∂w ν = ∂ 2 h 0 ∂w µ ∂w ν = ∂ 2 h ∂x µ ∂x ν + ∂ 2 h ∂x 2 0 - ∂ 2 h ∂x 0 ∂x µ - ∂ 2 h ∂x 0 ∂x ν . (17)
Then, letting h µν = ∂w µ ∂z ν denote the inverse of h µν , and combining the learning scheme (ERL) with the evolution equation (ZD), we obtain the (unilateral) entropy-driven learning dynamics:

ẋµ = ẇµ = ν ∂w µ ∂z ν żν = ν h µν (∆u ν -T z ν ) , (18)
where, as before, ∆u ν = u νu 0 and z ν = ∂h ∂x ν -∂h ∂x 0 .9 Therefore, if the agent's payoffs are coming from a finite game G ≡ G(N, A, u), our previous discussion yields the class of entropy-driven game dynamics

ẋkµ = k ν h µν k (x) u kν (x) -u k,0 (x) -T k ν h µν k (x) ∂h k ∂x kν - ∂h k ∂x k ,0 , (ED)
where now h k : X k → R is the entropy function of player k (generating the corresponding player-specific choice map Q k : R A k → X k ) and h µν k is the inverse Hessian matrix of h k defined as in [START_REF] Lee | Introduction to Smooth Manifolds[END_REF]. These dynamics will be the main focus of the rest of our paper, so some remarks are in order: Remark 1. To get some trivial book-keeping out of the way (and to keep our notation as light as possible), note that the player-specific entropy functions h k may be encoded in the aggregate entropy h :

X → R with h(x 1 , . . . , x N ) = k h k (x k ), x k ∈ X k . Likewise, if we set X = k X k and replace A with A * ≡ Remark 2.
It is also important to note that the dynamics (ED) admit global solutions, i.e. solutions that remain in int(X 0 ) for all t ≥ 0. This can be proven directly using the differential system (ED), but the score representation (5) probably yields a more transparent view: since the payoff streams u α (t) are Lipschitz and bounded, 10 the scores y α (t) will remain finite for all t ≥ 0, so interior solutions x(t) = Q(y(t)) of (ED) will be defined for all t ≥ 0 themselves. 11Remark 3. The previous remark brings up an important distinction between interior and non-interior orbits: strictly speaking, (ED) is only defined on int(X 0 ), so boundary initial conditions must be handled with more care. To address initial conditions x(0) ∈ X with arbitrary support A ≡ supp(x(0)) ⊆ A, it will be convenient to assume that the entropy h is regular; in that case, by restricting (EP) to the subface X ≡ ∆(A ) of X, we obtain a similarly restricted choice map Q : R A → X and the agent may proceed by updating the scores of the supported actions α ∈ A in (ERL). In this way, every subface X of X becomes an invariant manifold of (ERL)/(ED), so entropy-driven dynamics are seen to belong to the general class of imitative dynamics introduced by Björnerstedt and Weibull [START_REF] Björnerstedt | Nash equilibrium and evolution by imitation. The Rational Foundations of Economic Behavior[END_REF] (see also Weibull [34]).

Remark 4. In addition to tuning their learning temperature T > 0, players can also try to sharpen their response model by replacing the choice stage of (ERL) with

x k = Q k (λ k y k ) ( 19
)
for some λ k ≥ 0. As can be seen from (EP), these choice parameters may then be viewed as (playerspecific) inverse choice temperatures: as λ k → ∞, the choices of player k freeze down to a "bestresponding" to the stimulus y, whereas for λ k → 0, player k mixes actions uniformly, without regards to their performance scores. On the other hand, the same reasoning that led to (ED) also yields the choice-adjusted dynamics

ẋkµ = λ k k ν h µν k (x) u kν (x) -u k ,0 (x) -λ k T k ν h µν k (x) ∂h k ∂x kν - ∂h k ∂x k ,0 . (ED λ )
We thus see that the inverse temperature λ k of the player's choice model and the temperature T of their learning model ( 5) play very different roles on the resulting learning dynamics (ED λ ). The learning temperature T affects only the entropic correction term of (ED λ ) whereas λ k affects all terms of (ED λ ) commensurately; in fact, λ k can also be seen as a player-specific change of time, an observation which will be crucial in considering players with different update schedules in Section 4.

We will close this section by noting that even though the dynamics (ED) are fully updateable on X (as opposed to the otherwise equivalent process (ERL) which interweaves X and R A ), the RHS of (ED) still contains a non-explicit step in the calculation of the inverse matrix h µν . Given that the computational complexity of inverting a matrix is polynomial in the size of the matrix, this does not pose much of a problem in practical applications (after all, it is the number of players that usually explodes, not the number of actions per player).

That said, (ED) can be simplified considerably if the entropy function which is driving the process is itself decomposable. Indeed, assume that h(x) = β θ(x β ) for some non-degenerate Legendre kernel θ : [0, +∞) → R ∪ {+∞} as in Remark 2 following Definition 1. In that case, (17) readily yields

h µν = ∂ 2 h ∂x µ ∂x ν + ∂ 2 h ∂x 2 0 - ∂ 2 h ∂x 0 ∂x µ - ∂ 2 h ∂x 0 ∂x ν = θ (x µ ) δ µν + θ (x 0 ), (20)
so h µν can be calculated from the following lemma: Lemma 3. Let A µν = q µ δ µν + q 0 with q 0 , q 1 , . . . , q n > 0. Then, the inverse A µν of A µν will be:

A µν = δ µν q µ - q h q µ q ν , ( 21
)
where q h is the harmonic aggregate: q -1 h ≡ n α=0 q -1 α .

Proof. Proof. By simple inspection, we have:

In view of the above inversion formula applied to [START_REF] Mcfadden | Econometric models of probabilistic choice. Structural Analysis of Discrete Data with Econometric Applications[END_REF], and setting

z k µ = ∂h ∂w k µ = θ (x k µ ) -θ (x k ,0
) in (ED), some algebra finally yields the entropic dynamics with kernel θ:

ẋkα = 1 θ (x kα ) u kα (x) -θ h (x k ) k β u k β (x) θ (x k β ) - T θ (x kα ) θ (x kα ) -θ h (x k ) k β θ (x k β ) θ (x k β ) , (ED θ )
where θ h denotes the harmonic aggregate

θ h (x k ) = k β 1/θ (x k β ) -1
. 12 Hence, in the important case of the Boltzmann-Gibbs kernel θ(x) = x log x, we readily obtain the temperature-adjusted replicator dynamics

ẋkα = x kα u kα (x) - k β x k β u k β (x) -T x kα log x kα - k β x k β log x k β (T-RD)
which, for T = 0, freeze to the ordinary (asymmetric) replicator dynamics of Taylor and Jonker [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF]:

ẋkα = x kα u kα (x) - k β x k β u k β (x) . (RD)
3 Entropy-driven game dynamics and rationality.

In this section, our aim will be to analyze the entropy-driven dynamics (ED) from the point of view of rational agents, mostly looking to determine their asymptotic convergence properties with respect to standard game-theoretic solution concepts. Thus, in conjunction with the notion of Nash equilibrium, we will also focus on the widely studied concept of a quantal response equilibrium :

Definition 4 (McKelvey and Palfrey, 1995). Let G ≡ G(N, A, u) be a finite game in normal form and let Q : R A → X be a regular choice function. We will say that q ∈ X is a quantal response equilibrium (QRE) of G with respect to Q (or a Q-equilibrium for short) when, for some ≥ 0,

q = Q ( u(q)) , (QRE)
where u(q) ∈ k R A k denotes the payoff vector of the profile q ∈ X. More generally, if

G ≡ G (N, A , u| A ) is a restriction of G, we will say that q ∈ X is a restricted QRE of G if it is a QRE of G .
The scale parameter ≥ 0 will be called the rationality level of the QRE in question. Obviously, when = 0, players choose actions uniformly, without any regard to their payoffs; at the other end of the spectrum, when → ∞, players become fully rational and the notion of a QRE approximates smoothly that of a Nash equilibrium. Finally, one could also consider negative rationality levels, in which case players become anti-rational: for < 0, the condition x = Q( u(x)) characterizes the QRE of the opposite game -G = (N, A, -u), and as → -∞, these equilibria approximate the Nash equilibria of -G.

To make this approximation idea more precise, let q * ∈ X be a Nash equilibrium of a finite game G and let γ : U → X be a smooth curve on X defined on a half-infinite interval of the form U = [a, +∞), a ∈ R. We will then say that γ is a Q-path to q * when γ( ) is a Q-equilibrium of G with rationality level and lim →∞ γ( ) = q * ; in a similar vein, we will say that q ∈ X is a Q-approximation of q * when q is itself a Q-equilibrium and there is a Q-path joining q to q * (van Damme [START_REF] Van Damme | Stability and perfection of Nash equilibria[END_REF] uses the terminology approachable).

Example 1. By far the most widely used specification of a QRE is the logit equilibrium which corresponds to the Gibbs choice map (8): in particular, q ∈ X will be a logit equilibrium of G when q kα = exp( u kα (q))/ β exp( u k β (q)) for all α ∈ A k , k ∈ N.

Our first result links the rest points of (ED) at temperature T with the game's restricted QRE:

Proposition 5. Let G ≡ G(N, A, u) be a finite game and let h : X → R be a regular entropy function with choice map Q : R A → X. Then:

1. For T > 0, the rest points of the entropy-driven dynamics (ED) coincide with the restricted QRE of G with rationality level = 1/T .

2. For T = 0, the rest points of (ED) are the restricted Nash equilibria of G.

3. For T < 0, the rest points of (ED) are the restricted QRE of the opposite game -G. depicted in dark red and interior rest points in light/dark blue; see labels for the game's payoffs). For high learning temperatures T 0, the dynamics cannot keep track of payoffs and their only rest point is a global attractor which approaches the barycenter of X as T → +∞ (corresponding to a QRE under stochastic perturbations of very high magnitude). As the temperature drops to around T ≈ 0.935, this attractor becomes unstable and undergoes a supercritical pitchfork bifurcation (a phase transition) resulting in the appearance of two asymptotically stable QRE that converge to the strict Nash equilibria of the game as T → 0 + . For negative temperatures, the non-equilibrium vertices of X become asymptotically stable (but with a very small basin of attraction), and each of them gives birth to an unstable equilibrium in a subcritical pitchfork bifurcation. Of these two equilibria, the one closer to the game's interior Nash equilibrium is annihilated with the pre-existing QRE at T ≈ -0.278, and as T → -∞, we obtain a time-inverted image of the T → +∞ portrait with the only remaining QRE repelling all trajectories towards the vertices of X .

RR n°8210

RR n°8210

Proof. Proof. Since our focus is on restricted equilibria, it clearly suffices to prove the above correspondences for interior rest points; since the faces of X are forward-invariant under the dynamics (ED), the general claim then follows from passing to an appropriate restriction G of G.

To that end, let T > 0 and note that Eq. ( 13) on the evolution of the relative scores z k µ allows us to characterize the rest points of (ED) by means of the equation ∆u k µ (x) -T z k µ = 0; equivalently, in terms of the absolute scores y kα , we will have u kα (x) -T y kα = u k β (x) -T y k β for all α, β ∈ A k , k ∈ N. However, with x = Q(y), we will also have y kα -∂h ∂x kα = y k β -∂h ∂x k β , so we readily obtain

u kα (x) -T ∂h ∂x kα = u k β (x) -T ∂h ∂x k β ; in turn, this shows that x = Q(T -1 u(x)), so x is a Q-equilibrium of G with rationality level = 1/T .
For T = 0 the result is immediate because [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF] shows that x ∈ X is an interior rest point of (ED) if and only if u kα (x) = u k β (x) for all α, β ∈ A k , k ∈ N, i.e. if and only if x is an interior Nash equilibrium of G (recall that the Hessian of h is non-singular). Finally, the time inversion t → -t in (ED) is equivalent to the inversion u → -u, T → -T , so our claim for negative T follows from the case T > 0.

Remark 1. Proposition 5 shows that the temperature T of the dynamics (ED) plays a double role: on the one hand, it determines the discount (or reinforcement) factor in the players' assessment phase [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF], so it reflects the importance that they give to past events; on the other hand, T also determines the rationality level of the rest points of (ED), measuring how far the stationary points of the players' learning process are from being Nash. Perhaps unsurprisingly, this dual role of the temperature is brought to the forefront by the probabilistic/perturbed interpretation of quantal responses as choice probabilities in the case of stochastically perturbed payoffs. Indeed, recalling the relevant discussion of Section 2.3, we see that a QRE with rationality level = T -1 corresponds to best responding in the presence of a noise process with standard deviation ε ∝ -1 = T . On that account, the players' learning temperature simply measures the inherent variance (inverse rationality) of a QRE, just as the physical notion of temperature measures the variance of the random motions of the particles that make up a thermodynamic system (e.g. an ideal gas following Maxwell-Boltzmann statistics).

Of course, stationarity does not capture the long-term behavior of a dynamical system, so the rest of our analysis will be focused on the convergence properties of (ED). To that end, we begin with the special case of potential games where the players' payoff functions are aligned along a common potential function as in Eq. [START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF]. In this setting, our first result is that for small temperatures, the game's potential function is "almost" increasing along the solution orbits of (ED): Lemma 6. Let G ≡ G(N, A, u) be a finite potential game with potential U, and let h : X → R be a generalized entropy function. Then, the function F(x) ≡ T h(x) -U(x) is Lyapunov for the entropy-driven dynamics (ED): for any interior orbit x(t) of (ED), we will have d dt F(x(t)) ≤ 0 with equality if and only if x(0) is a QRE of G (or -G for T < 0). Proof. Proof. By expressing F in the reduced coordinates w k µ = x k µ that we used in the derivation of (ED) (see also Remark 4 following Definition 1), we readily obtain:

dF dt = k k µ ∂F ∂w k µ ẇkµ = k k µ ,ν T ∂h ∂w k µ -∆u k µ h µν k ∆u k µ -T ∂h ∂w k µ , (22)
with the second equality following from the fact that G is a potential game, so ∂u k ∂x kα = ∂U ∂x kα by (2). Thus, with Hess(h) 0, [START_REF] Mertikopoulos | Matrix exponential learning: Distributed optimization in MIMO systems[END_REF] implies that Ḟ(x) ≤ 0 with equality if and only if ∆u k µ (x) = T ∂h ∂w k µ = T ∂h ∂x k µ -∂h ∂x k ,0 , i.e. if and only if x is a QRE of G (or -G for T < 0; cf. the proof of Proposition 5).

When the players' entropy function is regular, Lemma 6 can be easily extended to orbits lying on any subface X of X simply by considering the restricted QRE of the game that are supported in X . Even in that case however, Lemma 6 makes no distinction between positive and negative temperatures and simply RR n°8210

shows that the dynamics (ED) will tend to move towards the minimizers of F on X . What changes with the sign of T is the relation that these minimizers have with regards to restricted QRE: for T < 0, the only local minimizers of F are the vertices of X (which are themselves pure restricted QRE), 13 whereas for T > 0, the restricted QRE of G that are supported in a subface X of X coincide with the local minimizers of F | X . Formally, Lemma 6 and the above reasoning give: Proposition 7. Let h : X → R be a regular entropy function and let x(t) be a solution orbit of the associated entropic dynamics (ED) for a potential game G. Then:

1. For T > 0, x(t) converges to a restricted QRE of G with the same support as x(0).

2. For T = 0, x(t) converges to a restricted Nash equilibrium whose support is contained in that of x(0).

3. For T < 0, x(t) converges to a vertex of X or is stationary (if x(0) is a restricted QRE of -G).

The above proposition will be our main result for potential games, so some remarks are in order:

Remark 1. By continuity, the phase portrait of the entropy-driven dynamics for small temperatures (positive or negative) will be broadly similar to the base case T = 0 (at least, in the generic case where there are no payoff ties in G). Accordingly, the main difference between positive and negative temperatures is that for small T < 0 the dynamics converge to a bona fide (pure) Nash equilibrium for most initial conditions (except for a small basin of attraction around each vertex of X which pulls the dynamics to non-equilibrium vertices), whereas for small T > 0, interior solutions of (ED) always converge to a Qapproximation of a Nash equilibrium (see also Fig. 1). As we shall see in Section 4, the fact that the entropy-driven dynamics always converge to the vicinity of a Nash equilibrium for small T > 0 will be crucial in the presence of imperfect payoff information and/or stochastic fluctuations.

Remark 2. Interpreting the game's potential U as the internal energy of a thermodynamic system, then, modulo a change of sign,the Lyapunov function F(x) = T h(x) -U(x) is known in statistical physics as the (Helmholtz) free energy and measures the useful work that can be obtained from a thermodynamic system at constant temperature (Landau and Lifshitz [START_REF] Landau | Statistical physics[END_REF]). 14 In this context, the principle of energy minimization states that the free energy of an isolated system never increases, so Lemma 6 may be viewed as a corollary of the Second Law of Thermodynamics: under constant temperature, the free energy of the system decreases until it reaches a thermal equilibrium.

The previous discussion establishes a fundamental qualitative difference between positive and negative learning temperatures in potential games: for T < 0, every vertex of X is attracting in (ED), while for T > 0, the dynamics can only converge to interior points. As we show below, this behavior actually applies to any finite game: Proposition 8. Let h : X → R be a regular entropy function. Then: 1. For negative temperatures T < 0, every vertex q ∈ X is attracting in the entropic dynamics (ED).

2. For positive temperatures T > 0, any ω-limit point of an interior solution orbit x(t) is itself interior; in fact, the ω-limit set of int(X) and the boundary bd(X) of X are separated by neighborhoods. 13 Perhaps the easiest way to see is this is to note that F is subharmonic:

∂ 2 U ∂x 2 kα = 0 for all α ∈ A k , k ∈ N, on account of U
being multilinear, and ∂ 2 h ∂x 2 kα > 0 on account of h having a positive-definite Hessian. 14 Recall that our sign convention for the entropy is the opposite of physics and probability; furthermore, potentials are minimized in physics, so h and U should be replaced by -h and -U respectively, yielding the familiar expression F = U -Th (Landau and Lifshitz [START_REF] Landau | Statistical physics[END_REF]).

RR n°8210

Proof. Proof. Our proof will be based on the dynamics (13) for the relative scores z k µ , µ ∈ A k ,0 ≡ A k \ α k ,0 . In integral form, we have:

z k µ (t) = z k µ (0)e -Tt + t 0 e -T (t -s) ∆u k µ (x(s)) ds, (23)
so, with ∆u k µ bounded on X, the last integral will be bounded in absolute value by M k T (1e -Tt ) for some M k > 0. We will thus have

z k µ (0) + M k /T e -Tt -M k /T ≤ z k µ (t) ≤ M k /T + z k µ (0) -M k /T e -Tt , (24)
and for T > 0, any ω-limit point of (13) will lie in the rectangle

C T = {z ∈ k R A k ,0 : |z k µ | ≤ M k /T }.
However, the image of C T under the reduced choice map Q 0 : R A k ,0 → X 0 will be a compact set that is wholly contained in the interior of X 0 , thus proving our assertion for T > 0.

On the other hand, for T < 0, [START_REF] Monderer | Potential games[END_REF] shows that if we pick z k µ (0) < -M k /|T |, then we will have

lim t →∞ z k µ (t) = -∞ for all µ ∈ A k ,0 , k ∈ N. Since the set U T = {z ∈ k R A k ,0 : z k µ < -M k |T | -1 } is a neighborhood of (-∞, . . . , -∞) in k R A k ,0
which is mapped diffeomorphically by Q 0 to the relative interior of a neighborhood of (0, . . . , 0) in X 0 , it follows that the pure vertex q = (α 1,0 , . . . , α N,0 ) of X attracts all nearby interior solutions of (ED). By restriction, this property will hold on any subface of X which contains q, and with the choice of flagged actions α k,0 ∈ A k being arbitrary, our proof is complete. This dichotomy in the behavior of the entropic dynamics (ED) for positive and negative temperature ties in with the following result which is of independent interest: Proposition 9. Let h : X → R be a generalized entropy function. Then, there exists a volume form Vol h on int(X) such that if U 0 ⊆ X is relatively open in X and cl(U 0 ) ∩ bd(X) = ∅, then:

Vol h (U t ) = Vol h (U 0 ) exp(-A 0 T t), (25)
where

A 0 = card( k A k ) -card(N) = k (card(A k ) -1)
, and U t ≡ {x(t) : x(0) ∈ U 0 }. Hence, the entropy-driven game dynamics (ED) are contracting for T > 0, expanding for T < 0 and incompressible iff T = 0.

Proof. Proof. Again, our proof will be based on the dynamics (13) for the relative score variables z k µ , µ ∈ A k ,0 ≡ A k \ α k,0 , which are related to the mixed strategy variables x ∈ X via the commutative diagram [START_REF] Lamberton | When can the two-armed bandit algorithm be trusted?[END_REF]:

Q 0 (z) = proj 0 (x). Indeed, if V 0 is an open set of k R A k and W k µ = ∆u k µ (x) -T z k µ
denotes the RHS of ( 13), then, by Liouville's theorem, we will have

d dt Vol(V t ) = V t div W dV , (26)
where dV = k , µ dz k µ is the ordinary Euclidean volume form of k R A k ,0 , Vol denotes the associated (Lebesgue) measure, and V t is the image of V 0 at time t under (13), viz. V t = {z(t) : z(0) ∈ V 0 }. However, since ∆u k µ does not depend on z k (because u k µ and u k ,0 themselves do not depend on x k ), we will have

∂W k µ ∂z k µ = -T . Hence, summing over all µ ∈ A k ,0 , k ∈ N, we obtain div W = -k (card(A k ) -1)T = -A 0 T
, and by integrating, we obtain the volume evolution equation Vol(V t ) = Vol(V 0 ) exp(-A 0 T t).

In view of the above, let Vol h = proj * 0 (Q -1 0 ) * Vol be the push-forward of the Euclidean volume Vol(•) to int(X) via the diffeomorphism

Q -1 0 • proj 0 : int(X) → k R A k , i.e. Vol h (U) = Vol(Q -1 0 (proj 0 (U)))
for any relatively open set U ∈ int(X). Then, taking V 0 such that proj 0 (U 0 ) = Q 0 (V 0 ), our assertion follows from the volume evolution equation above by recalling that proj 0 (x(t)) = Q 0 (z(t)).

RR n°8210

Interestingly, in the special case of the Boltzmann-Gibbs entropy at zero temperature, Proposition 9 yields the classical result that the asymmetric replicator dynamics (RD) are incompressible and hence do not admit interior attractors (Hofbauer and Sigmund [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF], Ritzberger and Weibull [START_REF] Ritzberger | Evolutionary selection in normal-form games[END_REF]). 15 We thus see that incompressibility characterizes a much more general class of dynamics and, in our learning context, it is simply a consequence of the players assigning a uniform weight to their past observations (neither discounting, nor reinforcing them).

That said, in the case of the replicator dynamics, we have a significantly clearer picture for the stability and attraction properties of a game's equilibria thanks to the folk theorem of evolutionary game theory (Hofbauer and Sigmund [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF]). In particular, it is well known that:

1. If an interior trajectory converges, its limit is Nash.

2. If a state is Lyapunov stable, then it is also Nash.

3. A state is asymptotically stable if and only if it is a strict Nash equilibrium. 16By comparison, in the context of our more general class of entropy-driven game dynamics we obtain: Theorem 10. Let G ≡ G(N, A, u) be a finite game and let h : X → R be a regular entropy function with choice map Q : k R A k → X. Then, the entropy-driven dynamics (ED) have the following properties:

1. For positive temperatures T > 0, if q ∈ X is Lyapunov stable then it is also a QRE of G; moreover, if q is a Q-approximate strict Nash equilibrium and T is small enough, then q is also asymptotically stable.

2. For T = 0, if q ∈ X is Lyapunov stable, then it is also a Nash equilibrium of G; furthermore, q is asymptotically stable if and only if it is a strict Nash equilibrium of G.

3. Finally, for T < 0, a profile q ∈ X will be asymptotically stable if and only if it is pure (i.e. a vertex of X); any other rest point of (ED) is unstable.

Proof. Proof. Our proof will be broken up in three parts based on the temperature of the dynamics (ED):

Positive temperatures. Let T > 0 and assume that q ∈ X is Lyapunov stable (and, hence, stationary).

Clearly, if q is interior, it will be a QRE of G by Proposition 5 so there is nothing to show. Suppose therefore that q ∈ bd(X); then, by Proposition 8, we may pick a neighborhood U of q in X such that cl(U) does not contain any ω-limit points of the interior of X under (ED). However, since q is Lyapunov stable, any interior solution that is wholly contained in U will have an ω-limit in cl(U), a contradiction. Regarding asymptotic stability, we will make the simplifying technical assumption that the entropy function h is decomposable with the same Legendre kernel θ for all players (the proof is entirely similar in the general case, but significantly more painful to write down). Assuming further that q * = (α 1,0 , . . . , α N,0 ) is a strict Nash equilibrium of G and let q ≡ q(T ) ∈ X be a Q-approximation of q * with rationality level = 1/T . Then, letting W k µ = ∆u k µ -T z k µ denote the RHS of the dynamics (13), a simple differentiation yields:

∂W k µ ∂z ν q =            -T if = k, ν = µ, 0 if = k, ν µ, ρ h ν ρ (q) ∂ ∂w ρ ∆u k µ otherwise, ( 27
)
where h ν ρ (q) is the inverse Hessian matrix of h evaluated at q and ∂ ∂w ρ = ∂ ∂x ρ -∂ ∂x ,0 as before. In particular, using the inversion formula of Lemma 3, we will have

h ν ρ (q) = δ ν ρ θ (q ν ) - θ h (q ) θ (q ν )θ (q ρ ) , (28)
where θ h (q ) denotes the harmonic aggregate: θ h (q ) = β 1/θ (q β ) -1 . Since q is a Q-approximation of the strict equilibrium q * = (α 1,0 , . . . , α N,0 ), we will also have q k µ ≡ q k µ (T ) → q * k µ = 0 and q k ,0 → q * k ,0 = 1 as T → 0 + . Moreover, recalling that q is a QRE of G with rationality level = 1/T , we will also have ∆u k µ (q) = Tθ (q k µ ) -Tθ (q k ,0 ), implying in turn that Tθ (q k µ (T )) → ∆u k µ (q * ) < 0 as T → 0 + . However, with h regular, the Legendre kernel θ of h will satisfy θ (x)/θ (x) → 0 as x → 0 + , whence we obtain

1 Tθ (q k µ (T )) = θ (q k µ (T )) θ (q k µ (T )) 1 Tθ (q µ (T )) → 0 ∆u k µ (q * ) = 0. ( 29
)
Thus, on account of ( 28) and ( 29), the off-diagonal elements of ( 27) will be o(T ) as T → 0 + , so, by continuity, the eigenvalues of the Jacobian of the vector field W evaluated at q ≡ q(T ) will all be negative if T > 0 is small enough. As a result, q will be a hyperbolic rest point of ( 13), so it will also be structurally stable by the Hartman-Grobman theorem, and hence asymptotically stable as well.

Zero temperature. For T = 0, let q be Lyapunov stable so every neighborhood U of q in X admits an interior orbit x(t) that stays in U for all t ≥ 0; we then claim that q is Nash. Indeed, assume ad abusrdum that α k ,0 ∈ supp(q) has u k ,0 (q) < u k µ (q) for some µ ∈ A k and let U be a neighborhood of q such that x k ,0 > q k ,0 /2 and ∆u k µ (x) ≥ m > 0 for all x ∈ U. Then, picking an orbit x(t) that is wholly contained in U, the integral equation [START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF] gives z k µ (t) ≥ z k ,0 (0) + mt, implying in turn that z k µ (t) → +∞ as t → ∞. However, with z k µ = ∂h ∂x k µ -∂h x k ,0 and h regular this is only possible if x k µ (t) → 0, a contradiction. Assume now that q = (α k,1 , . . . , α k, N ) is a strict Nash equilibrium of G and let A k,0 ≡ A k \ α k ,0 as usual. To show first that q is Lyapunov stable, it will be again convenient to work with the relative scores z k µ and show that if m ∈ R is sufficiently negative, then every trajectory z(t) that starts in the open set

U m = {z ∈ k R A k ,0 : z k µ < m} always stays in U m ; since U m is a neighborhood of (-∞, . . . , -∞) in k R A k ,0
, this is easily seen to imply Lyapunov stability for q in X.

In view of the above, pick m ∈ R so that ∆u k µ (x(z)) ≤ -ε < 0 for all z ∈ U m and let τ m = inf{t : z(t) U m } be the time it takes z(t) to escape U m . Then, if τ m is finite and t ≤ τ m , the integral form [START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF] of the relative score dynamics (13) readily yields

z k µ (t) = z k µ (0) + t 0 ∆u k µ (Q 0 (z(s))) ds ≤ z k µ (0) -εt < m for all µ ∈ A k ,0 , k ∈ N. (30)
Thus, substituting τ m for t in [START_REF] Sorin | Exponential weight algorithm in continuous time[END_REF], we obtain a contradiction to the definition of τ m and we may conclude that z(t) always stays within U m if m is chosen negative enough -i.e. q is Lyapunov stable.

To show that q is in addition attracting, it suffices to let t → ∞ in [START_REF] Sorin | Exponential weight algorithm in continuous time[END_REF] and recall that Q 0 (z) → q when z → (-∞, . . . , -∞). Finally, for the converse implication, assume that q is not pure; in particular, assume that q lies in the relative interior of a non-singleton subface X -spanned by supp(q). Then, with h regular, Proposition 9 shows that q cannot attract a relatively open neighborhood U of initial conditions in X because (ED) remains volume-preserving when restricted to any subface X of X. In turn, this implies that q cannot be attracting in X and precludes asymptotic stability, as claimed.

Negative temperatures. For T < 0, the fact that every vertex of X is attracting follows from Proposition 8; Lyapunov stability then follows from ( 24) by noting that if z k µ (0) < -M k |T | -1 , then we will have z k µ (t) < z k µ (0) for all t ≥ 0 (cf. the proof of Proposition 8). Conversely, assume that q ∈ X is a non-pure Lyapunov stable state. Then, by passing to a subface of X if necessary, we may assume that q is actually interior. In that case however, if we take an interior neighborhood U of q in X, Proposition 9 shows that any neighborhood V of q that is contained in U will eventually grow to a volume larger than that of U under (ED), so there is no open set of trajectories contained in U. This shows that non-pure rest points of (ED) cannot be stable and our proof is complete.

In conjunction with our previous results, Theorem 10 provides an interesting insight into the role of the dynamics' temperature parameter T : for small T > 0, the dynamics (ED) are attracted to the interior of X and they only converge to points that are approximately Nash; for small T < 0, the bona fide strict Nash equilibria of the game are indeed asymptotically stable, but so are all the vertices of X (albeit with very small basins of attractions); finally, for T = 0, the dynamics (ED) are attracted to strict Nash equilibria and only there (see also Fig. 1). We thus obtain the following rule of thumb: for T > 0, the dynamics (ED) converge to states that are almost Nash, whereas for T < 0, the dynamics converge to Nash states except for a very small fraction of initial conditions.

As such, from the point of view of control and optimization, if one seeks to reach the strict Nash equilibria of the game (e.g. as is usually the case when the game is a potential one), it would appear that the zero temperature case provides the best convergence properties. Nonetheless, there are two important caveats to keep in mind: First, if the dynamics (ED) are to be properly implemented as a discrete-time algorithm, then the results of the next section show that the positive temperature regime is much more stable -all the while allowing players to converge arbitrarily close to a strict equilibrium. On the other hand, if one is only interested in the convergence speed of the dynamics (ED), then even arbitrarily small negative temperatures yield convergence rates that are exponentially faster than the T = 0 case: Proposition 11. Let G ≡ G(N, A, u) be a finite game and let h : X → R be a regular entropy function with choice map Q : k R A k → X. If q * = (α 1,0 , . . . , α N,0 ) is a strict equilibrium of G and x(t) is an interior solution of (ED) which starts sufficiently close to q * , then, for all T ≤ 0, we will have

z k µ (t) ∼ z k µ (0)e |T |t + ∆u k µ (q * ) e |T |t -1 |T | , (31)
where, as before, z k µ = ∂h ∂x k µ -∂h ∂x k ,0 are the relative scores of the players' equilibrium actions, ∆u k µ = u k µu k ,0 are the corresponding payoff differences, and we are using the notational convention (e 0t -1)/0 = t.

Put differently, we will have z k µ (t) = O(exp(|T |t)) for T < 0 and z k µ (t) = O(t) for T = 0: the relative scores z k µ escape to negative infinity exponentially faster for T < 0 than for T = 0.

Corollary 12. If q * = (α 1,0 , . . . , α N,0 ) is a strict Nash equilibrium of G and x(t) is an interior solution of the temperature-adjusted replicator dynamics (T-RD) that starts close enough to q * , then

x k ,0 (t) ∼        1 -e -O(exp(|T |t)) for T < 0, 1 -e -O(t) for T = 0. ( 32
)
By contrast, lim sup t →∞ x k,0 (t) < 1 whenever T > 0.

Remark 1. It is not too hard to obtain expressions similar to [START_REF] Tuyls | An evolutionary dynamical analysis of multi-agent learning in iterated games[END_REF] for more general choice functions Q, but the end result is not as concise, so we omit it.

Proof. (Proposition 11.) Pick some ε > 0 and let x(t) start close enough to q * so that (1 + ε)∆u k µ (q * ) ≤ ∆u k µ (x(t)) ≤ (1-ε)∆u k µ (q * ); that this is possible follows from the Lyapunov property of strict equilibria established in Theorem 10 (recall also that ∆u k µ (q * ) < 0 for all µ ∈ A k ,0 ≡ A k \ α k ,0 , k ∈ N, because q * is a strict equilibrium of G). We will thus have:

(1 + ε)∆u k µ (q * ) ≤ żkµ + T z k µ ≤ (1 -ε)∆u k µ (q * ), (33)
so if we multiply by e Tt and integrate, we readily obtain:

(1 + ε)∆u k µ (q * ) e Tt -1 T ≤ e Tt z k µ (t) -z k µ (0) ≤ (1 -ε)∆u k µ (q * ) e Tt -1 T , (34)
with the convention that (e 0t -1)/0 = t. Our assertion then follows by rearranging terms in [START_REF] Weibull | Evolutionary Game Theory[END_REF] above and noting that ε can be taken arbitrarily small since

z k µ (t) → -∞ for all µ ∈ A k,0 , k ∈ N.
Proof. (Corollary 12.) For Boltzmann action selection as in ( 8), we will have

x k ,0 = 1 + k µ exp(z k µ ) -1
so the estimate (32) follows from [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF] and the Taylor expansion 1/(1

+ s) ∼ 1 -s + O(s 2 ).
4 Discrete-time learning algorithms and stochastic approximations.

In this section, we examine how the entropy-driven dynamics (ERL) and (ED) may be used to design and implement learning algorithms in the context of finite games that are played repeatedly over time. The main challenge in this endeavor is that in practical implementations, players can only observe the payoffs that they actually received when playing the game (or even only a noisy version thereof), whereas the dynamics (ERL)/(ED) involve the expected payoff functions u kα (x). Therefore, in the absence of perfect monitoring (or any other device permitting the calculation of expected payoffs), any discretization of the dynamics (ERL)/(ED) should involve only the players in-game payoff streams and no other information. A natural way of addressing this issue is to take an Euler-like discretization of the dynamics, use the players' evolving mixed strategies to select an action at each stage, and update only those components for which payoffs were actually observed. In what follows, we will give a brief account of this approach (known as stochastic approximation) and then apply it directly to the dynamics (ERL) and (ED).

Stochastic approximation of continuous dynamics.

For completeness, we recall here a few general elements from the theory of stochastic approximation following Benaïm [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF] and Borkar [START_REF] Borkar | Stochastic approximation[END_REF]. To begin with, let S be a finite set, and let Z(n), n ∈ N be a R S -valued stochastic process that satisfies the recursion

Z(n + 1) = Z(n) + γ n+1 U(n + 1), (35)
where γ n is a sequence of step sizes (usually assumed to vanish with n) and U(n) is another R S -valued process which is adapted to the filtration F of Z. Then, if there exists a Lipschitz-continuous vector field

f : R S → R S such that E[U(n + 1)|F n ] = f (Z(n))
, we will say that (35) is a stochastic approximation of the continuous-time dynamical system ż = f (z).

(MD)

More explicitly, if we split the so-called innovation term U(n) of (35) into its average value 35) may be rewritten as

f (Z(n)) = E[U(n)|F n ] and a zero-mean noise term V (n + 1) = U(n + 1) -f (Z(n)), (
Z(n + 1) = Z(n) + γ n+1 (f (Z(n)) + V (n + 1)) , (SA)
which is easily seen to be a noisy Euler-like discretization of (MD); conversely, the equation (MD) will be referred to as the mean dynamics of the stochastic recursion (SA).

The main goal of the theory of stochastic approximation is to relate the process (SA) with the solution trajectories of the mean dynamics (MD). To that end, the standard assumptions that ensure that this comparison is possible are:

(A 1 ) The step sequence γ n is ( 2 -1 )-summable (typically,

γ n = 1/n). (A 2 ) V (n) is a difference of martingales with sup n E V (n) 2 < ∞. (A 3 ) The stochastic process Z(n) is bounded: sup n Z(n) < ∞ (a.s.
). Under these assumptions, the following lemma ensures that Z(n) can only converge to a connected set of rest points of the corresponding mean dynamics: Lemma 13. Assume that the dynamics (MD) admit a strict Lyapunov function (i.e. a real-valued function which decreases along every non-stationary solution orbit of (MD)), and assume further that the set of values of this function at the rest points of (MD) has measure zero in R. Then, under the assumptions (A 1 )-(A 3 ), every accumulation point of the process Z(n) generated by the recursion (SA) belongs to a connected set of rest points of the mean dynamics (MD).

Proof. Proof. Our claim is a direct consequence of the following string of results in Benaïm [START_REF] Benaïm | Dynamics of stochastic approximation algorithms[END_REF] (listed in order of successive implications): Proposition 4.2, Proposition 4.1, Theorem 5.7, and Proposition 6.4.

As an application of the previous lemma, let us consider a game G and a stochastic approximation of the entropy-driven dynamics (ED) that satisfies conditions (A 1 )-(A 3 ). If G admits a potential function U, Lemma 6 shows that the free entropy F = T h -U is Lyapunov for the entropy-driven dynamics (ERL)/(ED), and Sard's theorem (Lee [START_REF] Lee | Introduction to Smooth Manifolds[END_REF]) ensures that the set of values taken by F at its critical points has measure zero. Thus, in view of Proposition 5, we see that stochastic approximations of (ERL)/(ED) may only converge to connected sets of restricted QRE of G. In what follows, we will exploit this property in order to derive two entropy-driven learning algorithms based respectively on the score dynamics (ERL) and the strategy-based dynamics (ED).

Remark 1. We should note here that (SA) implicitly assumes that each component of the vector Z is updated simultaneously. In a game theoretic setting, this corresponds to complete player synchronization, an assumption which does not always hold; we will address such issues in Section 4.4.

Score-based implementation of entropy-driven learning.

We begin by constructing a discrete-time stochastic approximation of the score-based entropic dynamics (ERL) as follows: at each step, players play a smoothed best response to the performance scores of their actions (using the choice map Q defined in Section 2.3), and then update these scores depending on the payoffs they receive from the chosen action. We illustrate this process in Algorithm 1 below (presented in a synchronous version, with players selecting actions and receiving payoffs simultaneously): Algorithm 1 Score-based learning with entropy-driven action selection. n ← 0 foreach player k ∈ N and action α ∈ A k do initialize Y kα and set

X k ← Q k (Y k ) Repeat n ← n + 1 foreach player k ∈ N simultaneously do select a new action αk according to the mixed strategy X k # current action ûk ← u k ( α) # current payoff Y k αk ← Y k αk + γ n ( ûk -TY k αk )/X k αk # update current action score foreach action α ∈ A k do X kα ← Q kα (Y k )
# update mixed strategy

To study the convergence properties of Algorithm 1, let Y (n) denote the players' score profile at the n-th iteration of the algorithm -and similarly for X(n) (strategies), α(n) (actions) and û(n) (payoffs). Then, Y (n) is a stochastic process adapted to the filtration F n generated by X and satisfies the relation:

E (Y kα (n + 1) -Y kα (n))/γ n+1 | F n = E[ ûk (n + 1)|F n ] -TY kα (n) = u kα (X(n)) -TY kα (n), ( 36
)
for all α ∈ A k , k ∈ N. Together with the selection rule X k (n) = Q k (Y k (n))
, the RHS of the above expression yields the entropy-driven score dynamics (ERL), so the strategy process X(n) generated by Algorithm 1 will be a stochastic approximation of (ERL).

In the special case where T = 1, Algorithm 1 boils down to the Q-learning scheme of Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF] which, under the assumption that Y (n) remains bounded (a.s.), was proven to converge to Nash distributions (the analogue of a QRE with rationality level = 1) in various classes of 2-player games. Unfortunately, the unconditional convergence of this algorithm still eludes us because assumptions (A 2 ) and (A 3 ) are hard to verify: in fact, one can check that the order of the noise term V (n) is

E[ V (n + 1) 2 |F n ] = O((1 + Y (n) 2 )e Y (n) ), (37)
so (A 2 ) rests on first establishing the boundedness requirement (A 3 ). 17 However, establishing (A 3 ) is not trivial in itself because of the "almost surely" requirement; it seems to be possible to do so thanks to an argument by M. Faure (personal communication), but since Algorithm 1 is not the main focus of our paper, we will not venture further along this direction. There exists other conditions (replacing Assumptions A 1 , A 2 and A 3 ) under which convergence can be proved. A possible track to prove convergence without requiring a priori boundedness of V (n) is to truncate the stochastic approximation with expanding bounds. This approach is used in ? [? ], but again, the required summability conditions on E[||V (n + 1)|| 2 |F n ] are not satisfied in our case unless (Y (n)) is bounded. In any case, our focus is more on the following strategy-based algorithm, where boundedness is guaranteed.

Strategy-based implementation of entropy-driven learning.

In this section, we will focus on the strategy-based variant of the entropic game dynamics (ED), and we will implement it as a payoff-based learning procedure in discrete time. One of the advantages of this approach is that it does not rely on having a closed form expression for the choice map Q (which is hard to obtain for non-Boltzmann action selection); another is that since the algorithm is strategy-based (and hence its update variables are bounded by default), we will not need to worry too much about satisfying conditions (A 2 ) and (A 3 ) as in the case of Algorithm 1. As a result, the strategy-based implementation of the entropic game dynamics (ED) will be significantly easier to handle than its score-based variant.

Without further ado, we have:

X kα ← X kα + γ n Θ (X kα ) ûk X k αk 1( αk = α) - θ h (X k ) θ (X k αk ) -T g kα (X) (38)
where

g kα (X) ≡ θ (X kα )-θ h (X k ) k β θ (X k β ) θ (X k β )
is the entropy adjustment term of (ED).

As stated above, the update step of Algorithm 2 has been designed so as to track the entropic dynamics (ED). Indeed, letting X(n) (resp. α(n), û(n)) denote the players' strategy (resp. action, payoff) profile at the n-th iteration of the algorithm, we will have for all α ∈ A k , k ∈ N:

E (X kα (n + 1) -X kα (n))/γ n+1 | F n = u kα (X(n)) X kα (n)θ (X kα (n)) - θ (X k β (n)) θ (X kα (n)) k β u k β (X(n)) θ (X k β (n)) -T g kα (X(n)) θ (X kα (n)) , (39)
which is simply the RHS of the entropy-driven dynamics (ED) evaluated at X(n).

Remark 1. In the case of the Boltzmann-Gibbs kernel θ(x) = x log x, the update step (38) becomes

X kα ← X kα + γ n+1 (1( αk = α) -X kα ) • ûk -T X kα log X kα -k β X k β log X k β . (40)
For zero temperatures, we thus obtain the reinforcement learning scheme of Sastry et al. [START_REF] Sastry | Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information[END_REF] that was based on the classical replicator equation (RD).

On the other hand, unlike Algorithm 1 (which was evolving in R A ), Algorithm 2 is well-defined only if the iterates X are admissible mixed strategies at each update step. To check that this indeed the case, note first that the second term of the RHS of (38) vanishes when summed over α ∈ A k , so k α X kα (n) remains constant and equal to 1 (recall that X k (0) is initialized as a valid probability distribution). It thus suffices to check that X kα (n) ≥ 0 for all α ∈ A k ; restricting ourselves to positive learning temperatures T > 0 and normalizing the game's payoffs to [0, 1] for simplicity, we have: Lemma 14. Let θ be a regular entropy kernel such that xθ (x) ≥ m for some m > 0 and for all x ∈ (0, 1). Then, for T > 0 and normalized payoffs u k : A → [0, 1], there exists a positive constant K > 0 (which only depends on T and θ) such that if the step sequence γ n is bounded from above by K, then X kα (n) ≥ 0 for all α ∈ A k , k ∈ N, and for all n ≥ 0.

Proof. Proof. For notational simplicity, we will only consider here the single-player case, the general case being similar. To that end, we first claim that the entropic term g k of (38) is bounded by a constant C θ ; indeed:

• θ is increasing, hence θ (ξ) ≤ θ (1) for all ξ ∈ (0, 1).

• For all x ∈ X ≡ ∆(A), β 1/θ (x β ) ≥ max β 1/θ (x β ), so θ h (x) ≤ min β θ (x β ) ≤ max{θ (ξ) : card(A) -1 ≤ ξ ≤ 1}. Thus there exists θ h,max such that θ h,max ≥ θ h (x) > 0 for all x ∈ X.

• By the regularity assumption for θ, we will have θ (ξ)/θ (ξ) → 0 as ξ → 0 + , so there exists M > 0 such that |θ (ξ)/θ (x)| < M for all ξ ∈ (0, 1).

As a result, our claim follows by taking C θ = θ (1) + θ h,max card(A)M. Now, letting α be the chosen action at step n and û the corresponding payoff, we will have:

1 x α θ (x α ) T g α (x) -û/x α 1( α = α) -θ h (x)/θ (x α ) ≤ 1 x α θ (x α ) TC θ + û/x αθ (x α ) θ h (x) -1( α = α)θ (x α ) ≤ 1 x α θ (x α ) TC θ + θ h,max • û x αθ (x α ) -1 ≤ m -1 TC θ + m -1 θ h,max , (41)
where we used the assumption T ≥ 0 for the first inequality and the normalization û ∈ [0, 1] for the second and third one. Hence, if

γ n ≤ m -1 TC θ + m -1 θ h,max ≡ K, we will have X α (n + 1) ≥ X α (n)(1 - γ n+1 K) ≥ 0 whenever X α (n) ≥ 0,
and the induction is complete.

Under the assumptions of Lemma 14 above, Algorithm 2 is well-defined and is no risk of crashing; we now show that if G is a potential game, then Algorithm 2 converges to a QRE of G almost surely: Theorem 15. Let G be a potential game, and let θ be a regular entropy kernel such that xθ (x) ≥ m for some m > 0 and for all x ∈ (0, 1). Then, for T > 0 and sufficiently small step sizes γ n satisfying (A 1 ), Algorithm 2 converges almost surely to a connected set of QRE of G with rationality level 1/T . Proof. Proof. By the proof of Lemma 14, assumptions (A 2 ) and (A 3 ) for the iterates X(n) of Algorithm 2 are verified immediately -simply note that the innovation term of (38) is bounded by the constant K of Lemma 14. Thus, by Lemma 13 and the subsequent discussion, it follows that X(n) converges to a connected set of restricted QRE of G.

We will now show that the accumulation points of X(n) can only lie in the relative interior rel int(X) of X. To that end, let z k µ = θ (x k µ ) -θ (x k ,0 ) be the reduced score variables of (13) and let W k µ = ∆u k µ -T z k µ denote the RHS of the reduced score dynamics (ZD), viz. ż = W (z). Then, following Borkar and Meyn [START_REF] Borkar | The ode method for convergence of stochastic approximation and reinforcement learning[END_REF], the limiting ODE of the dynamics (ZD) will be:

ż = W ∞ (z) ≡ lim r →∞ W (r z)/r = lim t →∞ ∆u k µ (Q 0 (r z)) -T r z r = -T z, (ZD ∞ )
where Q 0 : z → x is the reduced choice map of Eq. ( 15). For T > 0, the origin is a global attractor of (ZD ∞ ), so Theorem 2.1 in Borkar and Meyn [START_REF] Borkar | The ode method for convergence of stochastic approximation and reinforcement learning[END_REF] implies that the discrete stochastic approximation

Z k µ (n) = θ (X k µ (n)) -θ (X k ,0 (
n)) of (ZD) will be bounded almost surely. Moreover, given that Q 0 is a homeomorphism onto rel int(X), the image of any compact subset of k R A k ,0 will be a compact subset of rel int(X), so any accumulation point of the process X = Q 0 (Z) will lie in rel int(X), as claimed. Since X(n) was shown to converge to a connected set of restricted QRE of G, our assertion follows.

Remark 1. It is important to note here that Theorem 15 holds for any T > 0, so Algorithm 2 may be tuned to converge to QRE with arbitrarily high rationality level = 1/T -and hence, arbitrarily close to the game's strict Nash equilibria; cf. the discussion following Theorem 10 in Section 3. In this way, Theorem 15 is different in scope than the convergence results of Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF] and Bravo [START_REF] Bravo | An adjusted payoff-based procedure for normal form games[END_REF]: instead of taking high learning temperatures to guarantee a unique QRE, players who employ low learning temperatures may converge arbitrarily close to the game's strict equilibria.

Remark 2. In view of the above, one might hope that Algorithm 2 would still converge to the game's (strict) Nash equilibria even for T = 0. In that case however, the limiting ODE (ZD ∞ ) no longer admits a global attractor at the origin, so the relative scores Z k µ no longer remain bounded and we cannot discount the convergence of Algorithm 2 to non-Nash vertices of X. In fact, even in the simplest possible case of a single player game with two actions, Lamberton et al. [START_REF] Lamberton | When can the two-armed bandit algorithm be trusted?[END_REF] showed that the T = 0 version of Algorithm 2 with Boltzmann action selection fails to converge a.s. to a Nash equilibrium for step sequences of the form γ n = 1/n h , 0 < h < 1.

Robustness of the strategy-based learning algorithm.

Even though Algorithm 2 only requires players to observe and record their in-game payoffs, it still relies on the following assumptions: a) that players have perfect measurements of their payoffs (or that the same action profile always yields the exact same payoffs); b) that players all play at the same time; and c) that there is no delay between playing and receiving payoffs. Since these assumptions are often violated in practical scenarios, we devote the rest of this section to examining the robustness of Algorithm 2 in this more general setting.

Noisy measurements and stochastic perturbations. In many real-world applications of game theory (and especially in traffic congestion games), the payoffs received by the players at each stage of the game may be subject to random shocks (Hofbauer and Sandholm [START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF], Mertikopoulos and Moustakas [START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF]) or players may only be able to get a rough measurement of their true payoffs (see e.g. ? [? ] for an example drawn from revenue sharing and mechanism design).

We will model such stochastic perturbations by considering a random noise term ξ k (n), k ∈ N, which is added to the payoff ûk (n) received by player k at the n-th iteration of Algorithm 2 (and which, in principle, might depend on the players' strategy or action profiles). Then, with notation as before, we have: Proposition 16. Let ξ(n) be an F n -adapted difference of martingale with values in R N (i.e. E[ξ(n + 1)|F n ] = 0); assume further that ξ k is bounded for all k ∈ N (a.s.) and that ξ k is stochastically independent of the chosen action αk of player k. Then, the conclusion of Theorem 15 still holds when the payoff stream ûk in Algorithm 2 is replaced by the perturbed process ũk = ûk + ξ k .

Proof. Proof. Since the noise process ξ is bounded (a.s.), we can still assume that the perturbed payoff functions are normalized in [0, 1]; hence, by taking a sufficiently small step sequence, Algorithm 2 remains well-defined (i.e. X(n) ∈ X for all n). It thus suffices to check that the conditional expectation of the innovation term of (38) with ûk replaced by ũk = ûk + ξ k still yields the entropy-driven dynamics (ED θ ). That this is so, is an immediate consequence of the independence between ξ k and αk ; indeed: 6 ). In each figure, the shades of gray represent the normalized density of states at each point of the game's strategy space and we also drew the phase portraits of the underlying mean dynamics (ED) for convenience. We see that Algorithm 2 converges to the game's QRE (which, for T = 1/ = 0.2 are very close to the game's strict equilibria) quite rapidly: after only n = 10 iterations, more than 99% of the initial strategies have converged within ε = 0.01 of the game's equilibria.

E[ ũk (n + 1) 1( αk (n + 1) = α)|F n ] = E ( ûk (n + 1) + ξ k (n + 1)) 1( αk (n + 1) = α)|F n = u kα (X(n)) + E ξ k (n + 1)|F n X kα (n) = u kα (X(n)), (42)

RR n°8210

where the second equality follows from the independence of ξ and α, and the last one stems from the fact that ξ(n) is an F n -adapted difference of martingale. The entropic dynamics (ED) are then obtained as in (39).

Remark 1. We should note here that the assumptions on the noise term ξ(n) of Proposition 16 are rather mild: they encompass not only the case where the perturbations are independent of the players' choices (a case which has attracted significant interest in the literature by itself), but also scenarios where ξ(n + 1) might depend on the entire history of the game up to stage n, or even when the noise stems from imperfect observations of the other players' current actions (i.e. at the (n + 1)-th stage of the game).

Asynchronous updates and delays. In Algorithm 2, it is assumed that players update their strategies at every iteration simultaneously, i.e. they adhere to a synchronous strategy revision process. On the other hand, in congestion games and applications (e.g. in wireless networks), it is often the case that revisions are asynchronous: for instance, if we consider a set of wireless users communicating with a slotted ALOHA base station [START_REF] Altman | A survey on networking games in telecommunications[END_REF], then each user's decision to transmit or remain silent at a given timeslot is not coordinated with other users, so updates and strategy revisions occur at different periods for each user. Furthermore, in the same scenario, variable message propagation delays often mean that the outcome of a user's choice does not depend on the choices of other users at the current timeslot, but on their choices in previous timeslots.

In view of the above, the first extension to Algorithm 2 that we will consider here is the case where only a random subset of players (possibly of cardinality 1) revises their strategies at a given iteration of the algorithm. To that end, let R n ⊆ 2 N be the random set of players who update their strategies at the n-th iteration of the algorithm. In practice, players are not aware of the global iteration counter n but can only know the number of updates that they have carried out up to time n, as measured by the random variables φ k (n) ≡ card{m ≤ n : k ∈ R m }, k ∈ N. Accordingly, the asynchronous variant of Algorithm 2 that we will consider consists of replacing the instruction "for each player k ∈ N" by "for each player k ∈ R n " and replacing "n" by "φ k (n)" in the step-size computation.

Furthermore, as noted above, another natural extension of Algorithm 2 consists of allowing the (possibly perturbed) payoffs perceived by the players to be subject to delays. Formally, let τ kα (n) be the (integer-valued) delay that player k experiences when playing his α-th action at step n. Then, the payoff ûk of player k in (38) at step n should be replaced by u k (α k (n); α -k (n -τ kα (n))), with expected value conditioned on the history F n given by u k ,α k (n) (X(n -τ kα (n))).

Following Chapter 7 of Borkar [START_REF] Borkar | Stochastic approximation[END_REF], we will make the following assumptions regarding these two extensions of Algorithm 2:

1. The step sequence is of the form γ n = K/n, where K is a positive constant small enough to guarantee that Algorithm 2 remains well-defined for all n.

2. The strategy revision process R n is a homogeneous ergodic Markov chain over 2 N . We denote by λ k the asymptotic rate at which player k updates its strategy (if µ is the stationary distribution, then

λ k = A⊆2 N :k ∈ A µ(A))
3. The delays τ kα (n) are bounded, i.e. there exists M such that for every n, 0 ≤ τ kα (n) ≤ M (a.s.). This condition ensures that the bias induced by the delay becomes negligeable in face of the stepsize sequence as times goes by.

These hypotheses are rather mild in themselves, but they can be weakened even further at the expense of presentational simplicity and clarity (see e.g. Chapter 7 of Borkar [START_REF] Borkar | Stochastic approximation[END_REF]). Still and all, in this context, we have:

Proposition 17. Under the previous assumptions, the conclusion of Theorem 15 still holds for the variant of Algorithm 2 with asynchronous updates and payoff delays.

Proof. Proof. By Theorems 2 and 3 in Chapter 7 of Borkar [START_REF] Borkar | Stochastic approximation[END_REF], the algorithm modified to account for asynchronous strategy revisions and payoff delays as above, will be a stochastic approximation of the rate-adjusted dynamics ẋk = λ k ED θ (x k ),

where λ k is the mean rate at which player k updates its strategy, and ED θ denotes the RHS of the entropydriven dynamics (ED θ ). In general, the revision rate λ will depend on time (leading to a non-autonoumous dynamical system), but given that the revision process R n is a homogeneous ergodic Markov chain, λ k will be equal to the (constant) probability of including player k at the revision set R n at the n-th iteration of the algorithm. These dynamics have the same rest points as (ED) and an easy calculation shows that the free entropy F(x) = T h(x) -U(x) of 6 remains a strict Lyapunov function for (43), so the proof of Theorem 15 goes through unchanged.

Remark 1. It is important to note here that the entropic dynamics (43) adjusted for different strategy revision rates are equivalent to the choice-adjusted dynamics (ED λ ) which correspond to players using a different inverse choice temperature (hence the identical notation). Therefore, if the players' revision process is a homogeneous ergodic Markov chain, their mean revision rates λ k ∈ (0, 1) may also be viewed as inverse choice temperatures of players who never miss a revision opportunity, but who tone down their actions' performance scores by playing the mixed strategy x k = Q(λ k y k ) instead of Q(y k ). 184.5 Algorithm 2 in practice.

Let us give a close look at Algorithm 2 to assess its interest from an engineering perspective.

• First, it should be clear that the algorithm is highly distributed. The information needed to update one player's strategy is the payoff of its chosen action, which does not depend on any assessment of alternative choices. In particular, it does not rely on the observation of other players action, or even on the knowledge of the set of other players. Another feature is the fact that no synchronization between players is required: As shown in Section ??, each player can choose its updates instants in a complete independent fashion.

• The algorithm is robust to imperfection in the measurement (if any) of the payoff. This measurement can be based on old actions of remote players and it can suffer from random fluctuations (for example coming from a bad instrument and/or perturbations from the environment).

• The temperature parameter T should be rather easy to tune: In potential games, it should be taken strictly positive to ensure convergence to quantal response equilibria. Of course, small temperature values give better approximation of NE because QRE gets closer and closer to Nash equilibria when the temperature goes to 0. But, small temperatures may alter the speed of convergence because the step-sizes have to be chosen very small.The optimal choice of the temperature giving a good compromise between accuracy and speed of convergence is problem dependent.

All this leads to a distributed, player centric version of Algorithm 2, given in Algorithm 3, where each player k is equipped with a clock and plays each time its clock rings. The clock rings (τ k n ) n ∈N form an infinite increasing sequence of integers with positive rate (i.e. for any n, n # compute (or measure) current payoff foreach action α ∈ A k do # update mixed strategy

X kα ← X kα + γ n Θ (X kα ) ûk X k αk 1( αk = α) - θ h (X k ) θ (X k αk ) -T g kα (X)

4 Figure 1 :

 41 Figure 1: Phase portraits of the temperature-adjusted replicator dynamics (T-RD) in a 2 × 2 potential game (Nash equilibria are

  Distribution after n = iterations.

Figure 2 :

 2 Figure2: Snapshots of the evolution of of Algorithm 2. In our simulations, we drew 10 4 random initial strategies in the potential game of Fig.1and, for each strategy allocation, we ran the Boltzmann variant of Algorithm 2 with learning temperature T = 0.2 and step sequence γ n = 1/(5 + n 0.6 ). In each figure, the shades of gray represent the normalized density of states at each point of the game's strategy space and we also drew the phase portraits of the underlying mean dynamics (ED) for convenience. We see that Algorithm 2 converges to the game's QRE (which, for T = 1/ = 0.2 are very close to the game's strict equilibria) quite rapidly: after only n = 10 iterations, more than 99% of the initial strategies have converged within ε = 0.01 of the game's equilibria.

>Algorithm 3

 3 c ≥ 0). The corresponding revision set at time n, R n , is defined by: R n = {k |n ∈ (τ k n ) n∈N }. Algorithm used by one player (say player k) n ← 0 Repeat At time τ k n+1 n ← n + 1 select a new action αk according to the mixed strategy X k # current action ûk ← u k ( α1 , . . . , αN )

RR n°8210

Recall that we will be using α for both elements α ∈ A k and basis vectors e α ∈ ∆(A k ), so there is no clash of notation between payoffs to pure and mixed strategies.RR n°8210

Note that the sum (3 ) consists of O(1/h) terms that are O(1) in h so it would scale extensively with h -1 if not scaled by h.RR n°8210

Note that the difference/differential equations (4)/(5) imply that initial scores decay (or grow) exponentially with time in the absence of external forcing, commensurately to the first payoff observation u α (0).RR n°8210

Due to the entrenched terminology for the logit choice model, many authors call (8) the "logit" map. However, (8) actually describes the inverse logit (or logistic) distribution, so, to avoid inconsistencies, we will refer to[START_REF] Borkar | Stochastic approximation[END_REF] by the name of its originator.RR n°8210

These two viewpoints are not equivalent because there exist cost functions h that do not arise as deterministic representations of perturbation processes ξ -see Hofbauer and Sandholm[START_REF] Hofbauer | On the global convergence of stochastic fictitious play[END_REF] for a counterexample based on the log-entropy h(x) =β log x β .

The Tsallis and Rényi entropies are not well-defined for q = 1, but they both approach the standard Gibbs entropy as q → 1, so we will use the definition (12a) for q = 1 in (12c-12d).RR n°8210

The case of the Boltzmann-Gibbs entropy is a shining (but, ultimately, misleading) exception to the norm.RR n°8210

In fact, Q is constant along (1, . . . , 1): adding c ∈ R to every component of y ∈ R A will not change the solution x = Q(y) of (EP).RR n°8210

k A k in Definition 1, then the player-specific choice maps Q k : R A k → X k may themselves be encoded in the composite choice map Q : R A * k R A k → X associated to h. Therefore, whenever we mention entropy functions and choice maps in the context of a game (and not simply in a discrete choice problem), it should be understood that we are referring to the above construction.

Note that ẋ0 =µ ẋ µ , so the action α 0 ∈ A is not being discriminated against).

Importantly, this property remains true in the case of several agents involved in a finite game.

Interestingly, for T = 0, this can be seen as an alternative proof of Theorem 4.1 of Alvarez et al.[START_REF] Alvarez | Hessian Riemannian gradient flows in convex programming[END_REF] on the existence of global solutions in Hessian-Riemannian gradient descent dynamics.RR n°8210

Needless to say, θ h is not a second derivative; we just use this notation for visual consistency.RR n°8210

This does not hold in the symmetric case: there the proof breaks down because the symmetrized payoff u α (x) depends on x α .

Recall that q ∈ X is said to be Lyapunov stable (or stable) when for every neighborhood U of q in X , there exists a neighborhood V of q in X such that if x(0) ∈ V then x(t) ∈ U for all t ≥ 0. Moreover, q is called attracting when there exists a neighborhood U of q in X such that lim t →∞ x(t ) = q if x(0) ∈ U , and q is called asymptotically stable when it is both stable and attracting.RR n°8210

Note that this is also true for the weaker requirement supplied by Borkar[START_REF] Borkar | Stochastic approximation[END_REF], namely that there existK such that E[| |V (n + 1)| | 2 |F n ] ≤ K (1 + | |Y n | | 2 ) for all n.RR n°8210

Note also that λ k < 1 so players who do not update all the time tend to choose actions in a more uniform manner.RR n°8210