Angeliki Giannou
email: giannouangeliki@gmail.

Emmanouil-Vasileios Vlatakis-Gkaragkounis

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.

Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information

In this paper, we examine the Nash equilibrium convergence properties of no-regret learning in general N -player games. For concreteness, we focus on the archetypal "follow the regularized leader" (FTRL) family of algorithms, and we consider the full spectrum of uncertainty that the players may encounter -from noisy, oracle-based feedback, to bandit, payoff-based information. In this general context, we establish a comprehensive equivalence between the stability of a Nash equilibrium and its support: a Nash equilibrium is stable and attracting with arbitrarily high probability if and only if it is strict (i.e., each equilibrium strategy has a unique best response). This equivalence extends existing continuous-time versions of the "folk theorem" of evolutionary game theory to a bona fide algorithmic learning setting, and it provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games.

Introduction

The prototypical framework for online learning in games can be summarized as follows:

1. At each stage of the process, every participating agent chooses an action from some finite set.

2. All agents receive a reward based on the actions of all other players and their individual payoff functions (assumed a priori unknown).

3. The players record their rewards and any other feedback generated during the payoff phase, and the process repeats.

This multi-agent framework has both important similarities and major differences with single-agent online learning. Indeed, if we isolate a single, focal player and abstract away all others, we essentially recover a multi-armed bandit (MAB) problem -stochastic or adversarial, depending on the assumptions for the non-focal players [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Cesa | Prediction, Learning, and Games[END_REF]. In this case, the most widely used figure of merit is the agent's regret, i.e., the difference between the agent's cumulative payoff and that of the best fixed action in hindsight. Accordingly, much of the literature on online learning has focused on deriving regret bounds that are min-max optimal, both in terms of the horizon T of the process, as well as the number of actions A available to the focal player.

On the other hand, from a game-theoretic standpoint, the main question that arises is whether players eventually settle on an equilibrium profile from which no player has an incentive to deviate. In this regard, a "folk" result states that the empirical frequency of play under no-regret play converges to the game's set of coarse correlated equilibria (CCE) [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF][START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF]. However, there are two key caveats with this result. First, CCE are considerably weaker than Nash equilibria, to the extent that they fail even the most basic postulates of rationalizability [START_REF] Dekel | Rational behavior with payoff uncertainty[END_REF]: as was shown by Viossat and Zapechelnyuk [START_REF] Viossat | No-regret dynamics and fictitious play[END_REF], CCE may be supported exclusively on strictly dominated strategies, even in simple, symmetric two-player games. Second, the convergence of the empirical mean does not carry any tangible guarantees for the players' day-to-day behavior: under this type of convergence, the player's best payoff over time could be close to that of a Nash equilibrium, but the players might otherwise be spending arbitrarily long periods of time on dominated strategies.

The above is just a well-known example of the convergence failures of no-regret learning in games with a possibly exotic equilibrium structure. More to the point, even when the underlying game admits a unique Nash equilibrium, recent works have shown that no-regret algorithms -such as the popular multiplicative weights update (MWU) method -could still lead to chaotic [START_REF] Kuen | Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games[END_REF][START_REF] Monnot | Limits and limitations of no-regret learning in games[END_REF][START_REF] Palaiopanos | Multiplicative weights update with constant stepsize in congestion games: Convergence, limit cycles and chaos[END_REF] or Poincaré recurrent / cycling behavior [START_REF] Hofbauer | Time average replicator and best reply dynamics[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Mertikopoulos | Cycles in adversarial regularized learning[END_REF]. From a convergence viewpoint, all these results can be seen as instances of a much more general impossibility result at play: there are no uncoupled dynamics leading to Nash equilibrium in all games [START_REF] Hart | Uncoupled dynamics do not lead to Nash equilibrium[END_REF]]. 1 Since no-regret dynamics are by definition unilateral, they are a fortiori uncoupled, so this result shatters any hope of obtaining a universal Nash equilibrium convergence result for the players' day-to-day behavior.

Our contributions. In view of the above, a critical question that arises is the following: Is there a class of Nash equilibria that consistently attract no-regret processes? Conversely, are all Nash equilibria equally likely to emerge as outcomes of a no-regret learning process?

To address these questions in as general a setting as possible, we focus on the "follow the regularized leader" (FTRL) family of algorithms: this is arguably the most widely used class of dynamics for no-regret learning in games, and it includes as special cases the seminal multiplicative weights / EXP3 algorithms [START_REF] Arora | The multiplicative weights update method: A meta-algorithm and applications[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev | Convex repeated games and Fenchel duality[END_REF]. In terms of feedback, we also consider a flexible, contextagnostic template in which players are only assumed to have access to an inexact model of their payoff vectors at a given stage. This model for the players' feedback covers a broad range of modeling assumptions, such as (a) the case where players can retroactively compute -or otherwise observe -their full payoff vectors (e.g., as in routing games); and (b) the bandit case, where players only observe their in-game payoffs and have no other information on the game being played.

The range of modeling assumptions covered by our framework is quite extensive, so one would likewise expect different, context-specific answers to these questions -presumably with equilibria becoming "less stable" as information becomes "more scarce". This expectation is justified by the behavior of no-regret learning in single-agent environments: there, the type of information available to the learner has a dramatic effect on the achieved regret minimization rate. Nevertheless, we show that this conjecture is false: as far as the algorithms' equilibrium convergence properties are concerned, the learning dynamics described above are all equivalent.

In more detail, we show that all FTRL algorithms under study enjoy the following properties: a) Strict Nash equilibria are stochastically asymptotically stable -i.e., they are stable and attracting with arbitrarily high probability.

b) Only strict Nash equilibria have this property: mixed Nash equilibria supported on more than one strategies are inherently unstable from a learning viewpoint.

We are not aware of a similar result in the literature at this level of generality (i.e., including models with bandit feedback), and we believe that this equivalence represents an important refinement criterion for the prediction of the day-to-day behavior of no-regret learners in the face of uncertainty and lack of perfect information.

Related work. To put our contributions in the proper context, we provide below an account of relevant works in the literature, classified along the two directions of our main result: "strictness =⇒ stability" and "stability =⇒ strictness".

I. Strictness =⇒ Stability. Analyzing the convergence of game-theoretic learning dynamics has generated a vast corpus of literature that is impossible to survey here. Nonetheless, an emerging theme in this literature is the focus on specific classes of games (such as potential games or 2 N games). As a purely indicative -and highly incomplete -list, we cite here the works of Leslie and Collins [START_REF] Leslie | Individual Q-learning in normal form games[END_REF] and Leslie [START_REF] Leslie | Generalised weakened fictitious play[END_REF], Cominetti et al. [START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF], Kleinberg et al. [START_REF] David Kleinberg | Load balancing without regret in the bulletin board model[END_REF], Coucheney et al.

[8], Syrgkanis et al. [START_REF] Syrgkanis | Fast convergence of regularized learning in games[END_REF], and Cohen et al. [START_REF] Cohen | Learning with bandit feedback in potential games[END_REF], who provide a range of equilibrium convergence results in potential, 2 N , and (λ, µ)-smooth games, under different feedback assumptions -from payoff vector observations [START_REF] David Kleinberg | Load balancing without regret in the bulletin board model[END_REF][START_REF] Syrgkanis | Fast convergence of regularized learning in games[END_REF] to bandit [START_REF] Cohen | Learning with bandit feedback in potential games[END_REF][START_REF] Cominetti | A payoff-based learning procedure and its application to traffic games[END_REF][START_REF] Leslie | Generalised weakened fictitious play[END_REF][START_REF] Leslie | Individual Q-learning in normal form games[END_REF]. By contrast, our focus is determining the stochastic stability of a class of equilibria -not games.

As far as we are aware, the only comparable results in this literature concern an idealized continuous-time, deterministic, full-information version of our setting, which is common in applications to population biology and evolutionary game theory. In this context, building on earlier results on the replicator dynamics [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF][START_REF] Weibull | Evolutionary Game Theory[END_REF], the authors of [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] showed that strict Nash equilibria are asymptotically stable under the continuous-time dynamics of FTRL. However, we stress here again that these results only concern continuous-time, deterministic dynamical systems with an inherent full-information assumption; we are not aware of a result providing convergence to strict Nash equilibria with bandit feedback.

II. Stability =⇒ Strictness. In the converse direction, a related result in the literature on evolutionary games is that only strict Nash equilibria are asymptotically stable under the (multipopulation) replicator dynamics [START_REF] Hofbauer | Evolutionary game dynamics[END_REF][START_REF] William | Population Games and Evolutionary Dynamics[END_REF][START_REF] Weibull | Evolutionary Game Theory[END_REF], a continuous-time, deterministic dynamical system which can be seen as the "mean-field" limit of the exponential weights algorithm [START_REF] Hofbauer | Time average replicator and best reply dynamics[END_REF][START_REF] Rustichini | Optimal properties of stimulus-response learning models[END_REF][START_REF] Sylvain Sorin | Exponential weight algorithm in continuous time[END_REF].

In a much more recent paper [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF], this implication was extended to the dynamics of FTRL, but always in a deterministic, full-information, continuous-time setting. In this regard, our results are aligned with [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF]; however, other than this high-level conceptual link, there is no precise connection, either at the level of implications or at the level of proofs. Specifically, the analysis of [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF] relies crucially on volume-conservation arguments that are neither applicable nor relevant in a discrete-time stochastic setting -where the various processes involved could jump around stochastically without any regard for volume contraction or expansion.

Proof techniques. Learning with partial information is an inherently stochastic process, so our results are also stochastic in nature -hence the requirement for asymptotic stability with arbitrarily high probability. This constitutes a major point of departure from continuous-time models of learning [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF], so our proof techniques are also radically different as a result. The principal challenge in our proof of stability of strict Nash equilibria comes in controlling the aggregation of error terms with possibly unbounded variance (coming from inverse propensity scoring of bandittype observations). Because of this, stochastic approximation techniques that have been used to show convergence with L 2 -bounded feedback [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] cannot be applied in this setting; we achieve this control by applying a sharp version of the Doob-Kolmogorov maximal inequality to control equilibrium deviations with high probability. In the converse direction, the crucial argument in the proof of the instability of mixed equilibria is a direct probabilistic estimate which leverages a nondegeneracy argument for the noise entering the process; we are not aware of other works using a similar technique.

Preliminaries

The stage game. Throughout this work we will focus on normal form games with a finite number of players and a finite number of actions per player. Formally, such a game is defined as a tuple Γ = Γ(N , A, u) with the following primitives:

• A finite set of players -or agents -indexed by i ∈ N = {1, . . . , N }.

• A finite set of actions -or pure strategies -indexed by α i ∈ A i = {1, . . . , A i }, i ∈ N . Players can also play mixed strategies, which represent probability distributions x i ∈ X i := ∆(A i ); in this case, we will write x iα i for the probability that player i ∈ N selects α i ∈ A i . Aggregating over all players, we will also write x = (x 1 , . . . , x N ) for the players' mixed strategy profile and X := i X i for the set thereof. Finally, when we want to focus on the strategy (or action) of a particular player i ∈ N , we will use the shorthand (x i ; x -i ) := (x 1 , . . . , x i , . . . , x N ) -and, similarly, (α i ; α -i ) for pure strategies.

• An ensemble of payoff functions u i : A → R where A := i A i is the space of all pure strategy profiles. The expected payoff of player i in a mixed strategy profile x ∈ X is then given by

u i (x) ≡ u i (x i ; x -i ) = α 1 ∈A 1 • • • α N ∈A N u i (α 1 , . . . , α N ) • x 1,α 1 • • • x N,α N (1)
where u i (α 1 , . . . , α N ) is the payoff of player i in the action profile α = (α 1 , . . . , α N ) ∈ A.

For posterity, we will also write v iα i (x) = u i (α i ; x -i ) for the payoff that player i would have gotten by playing α i ∈ A i against the mixed strategy profile x -i of all other players. In this way, the mixed payoff vector of the i-th player will be

v i (x) = (v iα i (x)) α i ∈A i (2)
and we will write v(x) = (v 1 (x), . . . , v N (x)) for the ensemble thereof. For notational convenience, we will also set Y i = R A i and Y = i Y i for the space of payoff vectors and profiles respectively. Finally, in a slight abuse of notation, we will identify α i with the mixed strategy that assigns all probability to α i , and we will denote the corresponding pure payoff vector as

v i (α) = (u i (α i ; α -i )) α i ∈A i .
The distinction between pure and mixed payoff vectors will become important later on, when we discuss the information at each player's disposal.

Nash equilibrium. In this general context, the most widely used solution concept is that of a Nash equilibrium, i.e., a mixed strategy profile that discourages unilateral deviations. Formally, x * is a Nash equilibrium of Γ if

u i (x * ) ≥ u i (x i ; x * -i ) for all x i ∈ X i and all i ∈ N . (NE)
The set of pure strategies supported at the equilibrium component x * i ∈ X i of each player will be denoted by supp(x * i ) = {α i ∈ A i : x * iα i > 0}. Accordingly, Nash equilibria can be equivalently characterized by means of the variational inequality

v iα * i (x * ) ≥ v iα i (x * ) for all α * i ∈ supp(x * i ) and all α i ∈ A i , i ∈ N . (3)
The above characterization gives rise to the following classification of Nash equilibria:

• x * is a pure equilibrium if supp(x * i ) only contains a single strategy for all i ∈ N . • x * is a mixed equilibrium in any other case; in particular, if supp(x * i ) = A i for all i ∈ N , we say that x * is fully mixed.

By definition, pure equilibria correspond to vertices of X , fully mixed equilibria lie in the relative interior ri(X ) of X , and, more generally, mixed equilibria lie in the relative interior of the face of the simplex spanned by the support of each player's equilibrium component. A further distinction between Nash equilibria that is inherited by the inequality (3) is as follows: if (3) holds as a strict inequality for all α i ∈ A i \ supp(x * i ), i ∈ N , the equilibrium in question is said to be quasi-strict [START_REF] Fudenberg | Game Theory[END_REF]. Quasi-strict equilibria have the defining property that all pure best responses are played with positive probability; it is also well known that all Nash equilibria in all but a measure-zero set of games are quasi-strict. For this reason, the property of having a quasi-strict equilibrium is generic, and games that enjoy this property are called themselves generic [ Specifically, the set of games with Nash equilibria that are not quasi-strict is meager in the Baire category sense.]

We stress here that quasi-strict equilibria could be either mixed or pure: for example, the equilibrium of Matching Pennies is fully mixed and quasi-strict, whereas the equilibrium of the Prisoner's dilemma is quasi-strict and pure. In this last case, when a quasi-strict equilibrium is pure, it will be called strict: any deviation from an equilibrium strategy results in a strictly worse payoff.

Regret minimization and regularized learning

A key requirement in the context of online learning is the minimization of the players' regret, i.e., the cumulative payoff difference between each player's chosen action and the best possible action in hindsight over a given horizon of play T . Formally, given a sequence of play X n ∈ X , n = 0, 1, . . . , the (external) regret of player i ∈ N is defined as

Reg i (T ) = max x i ∈X i T n=0 [u i (x i ; X -i,n ) -u i (X i,n ; X -i,n )] (4)
and we will say that player i has no regret if Reg i (T ) = o(T ).

One of the most widely used online learning schemes to achieve this requirement is the so-called "follow the regularized leader" (FTRL) family of algorithms [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev | Convex repeated games and Fenchel duality[END_REF]. Heuristically, at each stage of the learning process, FTRL prescribes a mixed strategy that maximizes the player's (perceived) cumulative payoff modulo a regularization penalty whose role is to "smooth out" the transition between strategies during play. Formally, this leads to the round-by-round recursive rule

X i,n = Q i (Y i,n ) Y i,n+1 = Y i,n + γ n vi,n (FTRL)
where Q i : Y i → X i denotes the "choice map" of player i ∈ N , γ n > 0 is a "learning rate" parameter such that n γ n = ∞, and vi,n is a "payoff signal" that provides an estimate for the mixed payoffs of player i at stage n. We discuss each of these components in detail below.

The feedback model

Depending on the specific framework at play, the modeling details concerning the feedback received by the players may vary wildly. For example, when modeling congestion in a city, it is reasonable to assume that commuters can estimate the time it would have taken them to get to their destination via a different route -e.g., by means of a GPS service or an app like GoogleMaps or Waze. By contrast, in applications of online learning to auctions and online advertising, it is not clear how a player could estimate the payoff of actions they did not play.

To account for as broad a range of feedback models as possible, we will take a context-agnostic approach and assume that each player receives a "black-box" model of their payoff vector of the form

vn = v(X n ) + ξ n (5)
for some abstract error process ξ n = (ξ i,n ) i∈N . To differentiate between random (zero-mean) and systematic (non-zero-mean) errors, we will further decompose ξ n as

ξ n = Z n + b n , where b n = E[ξ n | F n ] and E[Z n | F n ] = 0 (6)
with F n denoting the history of X n up to stage n (inclusive) 2 . We may then characterize the input signal vn by means of the following statistics:

a) Bias: E[ b n * | F n ] ≤ B n (7a) b) Mean square: E[ vn 2 * | F n ] ≤ M 2 n (7b)
In the above, B n and M n represent deterministic bounds on the bias and variance of the feedback signal vn . For concreteness, we will also make the following blanket assumptions: (A1) Bias control:

lim n→∞ B n = 0 and n γ n B n < ∞. (A2) Variance control: n γ 2 n M 2 n < ∞. (A3)
Generic observation errors at equilibrium: For every mixed Nash equilibrium x * of Γ and for all n = 0, 1, . . . , there exists a player i ∈ N and strategies a, b ∈ supp(x * i ) such that

P(|v ia,n -vib,n | ≥ β | F n ) > 0 for all sufficiently small β > 0. (8)
The formulation of these hypotheses has been kept intentionally abstract because we have not made any modeling assumptions for how the players' payoff signals are generated. In this regard, they are to be construed as an "inexact model" that allows for a wide variety of settings; as an application, we illustrate below how these assumptions are verified in two widely used learning frameworks.

Model 1 (Oracle-based feedback). Assume that each player chooses an action based on a given mixed strategy. Then, once this procedure has been completed, an oracle reveals to each player the payoffs corresponding to their pure strategies given the other players' chosen strategies (in the congestion example, this oracle could be Waze or a GPS device). Formally, at each round n, every player i ∈ N picks an action α i,n ∈ A i based on X i,n ∈ X i and observes the pure payoff vector

v i (α n ) ≡ (u i (α i ; α -i,n )) α i ∈A i . Then the player's feedback signal is vi,n = v i (α n ), which is a special case of the model (5) with Z n = v(X n ) -v(α n ) and b n = 0.
In more detail, we have:

• (A1) is trivial because b n = 0. • (A2) is satisfied as long as n γ 2 n < ∞ (because sup n E[ vn 2 * ] ≤ max x v(x) 2 * < ∞). • (A3) is proved in Appendix B.
Model 2 (Payoff-based feedback). Assume that each player picks an action based on some mixed strategy as above; however, players now only observe their realized payoffs u i (α i,n ; α -i,n ). This is the standard model for multi-armed bandits [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Cesa | Prediction, Learning, and Games[END_REF], and it is also known as the "bandit feedback" setting. In this case, players can estimate their payoff vectors by means of the importance-weighted estimator:

viα i ,n = 1{α i,n = α i } Xiα i,n u i (α n ) (IWE)
where

Xi,n = (1 -ε n )X i,n + ε n /|A i |
is the mixed strategy of the i-th player at stage n. Compared to X i,n , the player's actual sampling strategy is recalibrated by an explicit exploration parameter ε n → 0 whose role is to stabilize the learning process by controlling the variance of (IWE). The idea is that even if a strategy has zero probability to be chosen under X n , it will still be sampled with positive probability thanks to the mixing factor ε n .

A standard calculation (that we defer to Appendix B) shows that (IWE) can be recast in the general form [START_REF] Kuen | Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games[END_REF]

with B n = O(ε n ) and M 2 n = O(1/ε n ).
We then have:

• (A1) is satisfied as long as ε n → 0 and n γ n ε n < ∞. • (A2) is satisfied as long as n γ 2 n /ε n < ∞. • (A3) is proved in Appendix B.
Remark. The above conditions for the method's learning rate and exploration parameters can be achieved by using schedules of the form γ n ∝ 1/n p and ε n ∝ 1/n q with p + q > 1 and 2pq > 1.

A popular choice is p = 2/3 + δ and q = 1/3 + δ for some arbitrarily small δ > 0 -or δ = 0 and including an extra logarithmic factor, cf. [START_REF] Slivkins | Introduction to multi-armed bandits[END_REF] and references therein.

Regularization

The second component of the FTRL method is the players' "choice map" Q i : Y i → X i . Because the players' score variables Y i,n essentially represent an estimate of each strategy's cumulative payoff over time, Q i is defined as a "regularized" version of the best-response correspondence y i → arg max x i ∈X i { y i , x i } (the regularization being necessary to avoid prematurely committing to a strategy). On that account, we will consider regularized best responses of the general form

Q i (y i ) = arg max x i ∈X i { y i , x i -h i (x i )}. (9)
In the above, each player's regularizer h i :

X i → R is defined as h i (x i ) = α i ∈A i θ i (x i ) for some "kernel function" θ i : [0, 1] → R with the following properties: (i) θ i is continuous on [0, 1]; (ii) C 2 -smooth on (0, 1]; and (iii) inf [0,1] θ ′′ i > 0.
Of course, different regularizers give rise to different instances of (FTRL); for concreteness, we present below two prototypical examples thereof.

Example 1 (Multiplicative/Exponential weights update). A popular choice of regularizer is the (negative) entropy h i (x) = i x i log x i , which leads to the logit choice map Λ i (y) = exp(y i )/ j exp(y j ) and the algorithm known as multiplicative weights update (MWU), cf. [START_REF] Arora | The multiplicative weights update method: A meta-algorithm and applications[END_REF][START_REF] Auer | Gambling in a rigged casino: The adversarial multi-armed bandit problem[END_REF][START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Vladimir | Aggregating strategies[END_REF].

Example 2 (Euclidean projection). Another popular regularizer is the quadratic penalty

h i (x) = i x i 2 /2
, which yields the payoff projection choice map Π i (y) = arg min x∈∆ y-x 2 , cf. [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF][START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF].

Analysis and Results

To understand the long-run behavior of (FTRL), we will focus on the following overarching question: Which Nash equilibria hold convergence and stability properties and how are these properties affected by the uncertainty in the players' feedback model?

We provide the technical groundwork for our answers in Section 4.1 below; subsequently, we state our results in Section 4.2, and present the technical analysis in Section 5.

Asymptotic Stability

The first thing to note in this general context is that a game may admit several Nash equilibria, both mixed and pure. As a result, global convergence to an equilibrium from all initializations is not possible; for this reason, we will focus on the notion of (stochastic) asymptotic stability [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF][START_REF] Rafail | Stochastic Stability of Differential Equations[END_REF][START_REF] William | Population Games and Evolutionary Dynamics[END_REF]. Heuristically, an equilibrium is stochastically stable if any sequence of play that begins close enough to the equilibrium in question, remains close enough with high probability; in addition, if the sequence of play eventually converges to said equilibrium, then we say that it is stochastically asymptotically stable. Formally, we have the following definition. Definition 1. Fix some arbitrary confidence level δ > 0. Then x * ∈ X is said to be 1. Stochastically stable if, for every neighborhood U of x * in X , there exists a neighborhood U 0 of x * such that whenever

X 0 = Q(Y 0 ) ∈ U 0 , we have P(X n ∈ U for all n = 0, 1, . . . ) ≥ 1 -δ ( 10
)
whenever X 0 = Q(Y 0 ) ∈ U 0 .
2. Attracting if there exists a neighborhood U 0 of x * such that

P(lim n→∞ X n = x * ) ≥ 1 -δ (11) whenever X 0 = Q(Y 0 ) ∈ U 0 .

Stochastically asymptotically stable if it is stochastically stable and attracting.

Definition 1 will be the mainstay of our analysis and results, so some remarks are in order.

Remark 1. A first intricate detail in the above definition is the high probability requirement: indeed, under uncertainty, a single unlucky estimation of the players' payoff vector could drive X n away from any neighborhood of x * , possibly never to return. In this regard, local stability results cannot be expected to hold with probability 1, hence the requirement to hold with some arbitrary confidence level in the definition above.

Remark 2. Another remark worth making is the requirement X 0 = Q(Y 0 ) ∈ U 0 that indicates that some strategies in X are not admissible as initial states. Going back to the two archetypal examples of (FTRL), Examples 1 and 2, there is a dichotomy in the properties of the corresponding mirror maps. On the one hand, the kernel of the Euclidean/quadratic regularizer is differentiable on all of [0, 1]. On the other hand, the derivative of the kernel of the negative Shannon-entropy goes to -∞ as x goes to 0. This means that in the latter the boundaries are off the limits and inevitably some initial conditions do not belong in im Q. We discuss this dichotomy extensively in Appendix A.2.

Main Results

We are now in a position to state our main results. The informal version is as follows.

Main Theorem. Suppose that Assumptions (A1)-(A3) hold. Then: x * is a strict Nash equilibrium ⇐⇒ x * is stochastically asymptotically stable under (FTRL)

Formally, we get the following precise statements and corollaries for the specific feedback models described in Section 3.1.

Theorem 1. Let x * ∈ X be
γ 2 n /ε n < ∞, n γ n ε n < ∞.

Then, a Nash equilibrium is stochastically asymprotically stable if and only if it is strict.

These results -and, in particular, the implications for the bandit case -provide a learning justification to the abundance of arguments that have been made in the refinement literature against selecting mixed Nash equilibria [START_REF] Dekel | Rational behavior with payoff uncertainty[END_REF][START_REF] Fudenberg | Game Theory[END_REF][START_REF] Van Damme | Stability and perfection of Nash equilibria[END_REF]. In the rest of our paper, we present an outline of the main proof ideas and defer the details to the appendix.

Our Techniques

The Stochastic Asymptotic Stability of Strict Nash Equilibria

At a high level, the standard tool in FTRL dynamics for questions pertaining to asymptotic stability of strict Nash equilibria is the construction of a potential -or Lyapunov -function. However, the analysis and the underlying structural results are considerably more involved when we shift from the continuous dynamics to discrete algorithms and more importantly in a stochastic framework with incomplete feedback information. Still, to build intuition we first recall the continuous and deterministic analogue.

The continuous-time case. In prior work [START_REF] Harper | Escort evolutionary game theory[END_REF][START_REF] Hewitt | Real and abstract analysis[END_REF][START_REF] Weinberg | Quantum Field Theory[END_REF], multiple instantiations of Bregman functions, like the KL-divergence have been employed as a potent tool for understanding replicator & population dynamics, which are the continuous analogues of MWU/EW (Example 1). Unfortunately, Bregman functions are insufficient to cover the full spectrum of regularizers studied in this work. This limitation has been sidesteped in [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] by exploiting the information of the dual space Y of the payoff scores, via the Fenchel coupling:

F h (x, y) = h(x) + h * (y) -y, x for all x ∈ X , y ∈ Y ( 12
)
where h * : Y → R is the convex conjugate of h: h * (y) = sup x∈X { y, xh(x)}. Indeed, F h (x * , y) ≥ 0 where equality holds if and only if x * = Q(y) (Proposition A.4). Therefore, for the continuous FTRL dynamics ẏ(t) = v(x(t)), x(t) = Q(y(t)), it remains to show that the time derivative of the Lyapunov-candidate-function L x * (y(t)) = F h (x * , y(t)) is negative. This last key ingredient for the strict Nash equilibria is derived by their variational stability property. Formally, a point x * is variationally stable if there exists a neighborhood U of x * such that

v(x), x -x * ≤ 0 for all x ∈ U (VS)
with equality if and only if x = x * . Roughly speaking, this property states that the payoff vectors are pointing "towards" the equilibrium in question since in a neighborhood of x * , it strictly dominates over all other strategies. Thus by applying the chain rule, (VS) implies that dL x * (y(t))/dt ≤ 0 3 . Given their usefulness also in the discrete time stochastic case, we present all the aformentioned properties in detail in the paper's supplement (Appendix A.1-A.5).

The discrete time. The core elements of the continuous time proof do not trivially extend to the discrete time case. Even though we are not able to show that (F h (x * , Y k )) ∞ k=1 is a decreasing sequence, due to the discretization and the uncertainty involved, we prove that F h (x * , Y k ) → 0. This immediately implies that FTRL algorithm converges to x * , since from Proposition A.4

F h (x * , Y k ) ≥ 1 2K h x * -X k .
To exploit again the Fenchel coupling as a Lyapunov function, successive differences have to be taken among F h (x * , Y n+1 ), . . . , F h (x * , Y 0 ). In contrast to the continuous time analysis, since the chain rule no longer applies, we can only do a second order Taylor expansion of the Fenchel coupling. Additionally, let us recall that in our stochastic feedback model, the payoff vector vn = v(X n ) + Z n + b n including possibly either random zero-mean noise or systematic biased noise. Combining Proposition A.4, definition of vn and (FTRL), we can create the following upper-bound of Fenchel coupling at each round:

F h (x * , Y n+1 ) ≤ F h (x * , Y 0 ) + n k=0 γ k (drift k + noise k + bias k ) + 1 2K h n k=0 γ 2 k vk 2 * (⋆)
where

drift k = v(X k ), X k -x * , noise k = Z k , X k -x * , bias k = b k , X k -x *
are the related terms with the drift of the actual payoff, the zero-mean noise and the bias correspondingly. When X n lies in a variationally stable region U V S of x * , the first-order term of drift k , which also appears in the continuous time, corresponds actually to the negative "drift" of the variational stability which attracts Fenchel coupling to zero.

Having settled the basic framework, we split the proof sketch of Theorem 1 into two parts: stochastic stability & convergence. Our analysis relies heavily on tools from the convex analysis and martingale limit theory to control the influence of the stochastic terms in the aforementioned bound.

Step 1: Stability. Let U ε = {x : D h (x * , x) < ε} and U * ε = {y ∈ Y : F h (x * , y) < ε} be the ε-sublevel sets of Bregman function and Fenchel coupling respectively. Our first observation is that for all "natural" decomposable regularizers, it holds the so-called "reciprocity condition" (Propositions A.1 and A.5): essentially, this posits that U ε and Q(U * ε ) are neighborhoods of x * in X . Additionally, since F h (x * , y) = D h (x * , x) whenever Q(y) = x and supp(x) contains supp(x * ), from

3. Analytically, dLx * (y(t)) dt = dh * (y(t)) dt -ẏ(t), x * = ẏ(t), ∇h * (y) -ẏ(t), x * = v(x(t)), x(t) -x * ≤ 0. Proposition A.4, it holds that Q(U * ε ) ⊆ U ε and Q -1 (U ε ) = U * ε .
Thus, we conclude that whenever y ∈ U * ε , x = Q(y) ∈ U ε . To proceed, fix a confidence level δ and ε sufficiently small such that (VS) holds for all x ∈ U ε . Using Doob's maximal inequalities for (sub)martingales (Theorems 5 and 6) we can prove that with probability at least 1δ, (a)

{ n k=0 γ k noise k }, (b) { n k=0 γ k bias k } and (c) { 1 2K h n k=0 γ 2 k vk
2 * } are less than ε/4 for all n ≥ 0. For concision, we defer the full proof to the supplement of the paper in Appendix A.7. For the rest of this part, we condition on this event and rewrite (⋆) as

F h (x * , Y n+1 ) < n k=0 γ k drift k + ε.
Following the definition of stability (Definition 1), we prove inductively that if X 0 belongs a smaller neighborhood, namely if

X 0 ∈ U ε/4 ∩ im Q, then X n never escapes U ε , X n ∈ U ε for all n ≥ 0. • Induction Basis/Hypothesis: Since X 0 ∈ U ε/4 ∩ im Q, apparently F h (x * , Y 0 ) < ε/4 and X 0 ∈ U ε . Assume that X k ∈ U ε for all 0 ≤ k ≤ n. • Induction Step: We will prove that Y n+1 ∈ U * ε and consequently X n+1 ∈ U ε . Since U ε is a neighborhood of x * in which (VS) holds we have that drift k ≤ 0 for all 0 ≤ k ≤ n. Consequently F h (x * , Y n+1 ) < ε which implies that Y n+1 ∈ U * ε or equivalently X n+1 ∈ U ε .
Step 2: Convergence. A tandem combination of stochastic Lyapunov and variational stability is the following lemma:

Lemma 1 (Informal statement of Lemma A.1). Let x * ∈ A be a strict Nash equilibrium. If X n does not exit a neighborhood R of x * , in which variational stability holds, then there exists a subsequence X n k of X n that converges to x * almost surely.

Indeed, if X n is entrapped in a variationally stable region U ε of x * without converging to x * , we can show that ∞ k=0 γ k drift k → -∞, while comparatively by the law of the large numbers for martingales (Theorem 3), the contribution of (a),(b),(c) is negligible. Thus, in limit (⋆) implies that 0 ≤ lim inf F h (x * , Y n ) ≤ -∞, which is a contradiction.

Our final ingredient to complete the proof is that (F h (x * , Y k )) ∞ k=1 behaves like an almost supermartingale when it is entrapped in a variationally stable region U ε of x * . So, by convergence theorem for (sub)-martingales (Theorem 4), (F h (x * , Y k )) ∞ k=1 actually converges to a random finite variable. Inevitably though,

lim inf n→∞ F h (x * , Y n ) = lim n→∞ F h (x * , Y n ) = 0 and by Proposi- tion A.4, Q(Y n ) = X n → x * .

The Stochastic Instability of Mixed Nash Equilibria

For the proof of Theorem 2, it is worth mentioning that in this case stability fails for any choice of step-size. We start by focusing on the assumption of non-degeneracy (A3) of theorem's statement.

• From a game-theoretic perspective, (A3) actually demands that with non-zero probability, when players receive the payoffs corresponding to pure strategy profiles, there exists at least one player for whom at least two strategies of the equilibrium have distinct payoff signal. Note that if for each player, the payoffs corresponding to two different strategies of supp(x * ) were all equal 4immediately implies a non-generic game with pure Nash equilibria. • To illustrate this assumption in our generic feedback model, suppose that this error term ξ n is standard normal random noise ξ n . Indeed, the requirement of (A3) is satisfied since

P(|v i,a (X n )+ ξ ia,n -v i,b (X n ) -ξ ib,n | ≥ 1/|N |) > 1 -O exp(-1/|N | 2 )
. Such kind of property can be derived actually for any per-coordinate independent noise since actually the event of two independent coordinates to be exactly equal has zero measure. For the bandit models Model 1, Model 2 of the previous section, we show that (A3) is satisfied in Corollaries 3 and 4 of Appendix B.

Moving on to the proof of Theorem 2, we start our analysis by connecting the difference of the payoff signal between two pure strategies, with the difference of the changes in the output of the regularizers' kernels, θ i : Lemma 2 (Informal Statement of Lemma B.2). Let X i,n be the sequence of play in (FTRL) i.e., X i,n = Q(Y i,n ) ∈ X i of player i ∈ N ; and for some round n ≥ 0 let a, b ∈ supp(X i,n ) be two pure strategies of player i ∈ N . Then it holds:

θ ′ i (X ia,n+1 ) -θ ′ i (X ia,n ) -θ ′ i (X ib,n+1 ) -θ ′ i (X ib,n ) = γ n (v ia,n -vib,n )
To proceed with the proof of Theorem 2 assume ad absurdum that a mixed Nash equilibrium x * is stochastically asymptotically stable. Since x * is mixed, there exist a, b ∈ supp(x * ). Second, the stochastic stability implies that for all ε, δ > 0 if X 0 belongs to an initial neighborhood U ε , then X nx * < ε for all n ≥ 0, with probability at least 1δ. Third, by the triangle inequality for two consecutive instances of the sequence of play X i,n , X i,n+1 for any player i ∈ N it holds:

|X ia,n+1 -X ia,n | + |X ib,n+1 -X ib,n | < O(ε) with probability 1 -δ (13)
Consider ε sufficiently small, such that the probabilities of the strategies that belong to the support of the equilibrium are bounded away from 0, for all the points of the neighborhood. Since θ i is continuously differentiable in (0, 1], the differences described in Lemma 2 are bounded from O(ε) due to Eq. ( 13). Thus, if the sequence of play X n is contained to an ε-neighborhood of x * , then the difference of the feedback, for any player i ∈ N , to two strategies of the equilibrium is O(ε/γ n ) with probability at least 1δ:

P(|v ia,n -vib,n | = O(ε/γ n ) | F n ) ≥ 1 -δ
However, from assumption (A3) for a fixed round n and some player i ∈ N , there exist β, π > 0 such that:

P(|v ia,n -vib,n | ≥ β | F n ) = π > 0.
Thus by choosing ε = O(βγ n ) and δ = π/2, we obtain a contradiction and our proof is complete.

Discussion

The equivalence between strict Nash equilibria and stable attracting states of feedback-limited (FTRL) implies that any equilibrium that exhibits payoff-indiffirence between different strategies is inherently unstable. This fragility has already been remarked from an epistemic viewpoint [START_REF] Van Damme | Stability and perfection of Nash equilibria[END_REF], and our results provide a complementary justification based on realistic models of learning.

In the converse direction, the generality of the feedback models considered also provides a template for proving stochastic asymptotic stability results in more demanding learning environments. A particular case of interest arises in online ad auctions where payoffs are observed with delay (or are dropped completely): depending on the delay, the estimation of the player's payoff could exhibit a bias relative to the sampling strategy, and our generic conditions provide an estimate of how large the delays can be before convergence breaks down. This opens the door to an array of fruitful research directions that we intend to pursue in the future.

Appendix A. Proof of stability of strict Nash equilibria

Looking at the continuous analogues of FTRL algorithms, the standard methodology leverages potential-Lyapunov arguments. However, in the discrete case multiple intrinsic challenges arise especially in the presence of uncertainty. In the prototypical example of MWU/EW (Example 1) the standard potential function is the Kullback-Leibler divergence. Thus, a natural candidate for the generalization from MWU/EW to any FTRL algorithm would be the Bregman divergence. Unfortunatelly, Bregman divergence does not always capture the actual behavior of FTRL algorithms in the boundary of the simplex. Hence, in order to trace the information entailed in the dual space, where FTRL algorithms truly evolve, we leverage the Fenchel coupling. In the first three subsections we present the main properties of Bregman divergence (Appendix A.1), the dichotomy among different regularizers (Appendix A.2) and then Fenchel coupling and its properties (Appendix A.4). Then we explore a structural property of strict Nash equilibria, namely variational stability (Appendix A.5). In the last section before we present our proofs we introduce some notions from martingales limit theory. With these last two sections we have established all the necessary machinery to bound the influence of the uncertainty in the behavior of the algorithm and finally prove the stability result.

A.1. Bregman divergence

Bregman divergence provides a way to measure the distance of two points that belong to the simplex. Its properties render it a useful tool to prove convergence results. Below we state its definition and prove these properties that would be crucial in the establishment of our proof. Given a fixed point p ∈ X then the Bregman divergence of a function h is defined for all points x ∈ X as

D h (p, x) = h(p) -h(x) -h ′ (x; p -x) for all p, x ∈ X (A.1)
where h ′ (x; px) is the one-sided derivative

h ′ (x; p -x) ≡ lim t→0 + t -1 [h(x + t(p -x)) -h(x)] (A.2)
Notice that this definition of the Bregman divergence permits to work also with points on the boundary. It is possible that the limit of D h attains the value of

+∞ if h ′ (x; p -x) = -∞, as x → p,
where p is a point of the boundary. However, the condition below ensures that this is not the case.

D h (p; x) → 0 whenever x → p (Reciprocity)
This is known as the reciprocity condition. What this property actually means is that the sublevel sets of D(p, •) are neighborhoods of p. This is illustrated in Fig. 1, when the function employed is the negative Shannon-entropy and the induced Bregman divergnce the Kullback-Leibler divergence.

Notice that for most decomposable functions h, this property holds. Below we present a proof of this statement.

Proposition A.1. If h(x) = i θ(x i ), with θ having the properties described in (reguralizer's properties) and furthermore it holds that θ ′ (x) = o(1/x) for x close to 0, then D h (p; x) → 0 whenever x → p for all x, p ∈ X .

Proof. It is sufficient to prove that lim x→0 (θ(0)θ(x)θ ′ (x)(0x)) = 0. The difference of the first two terms is obviously gives zero. Now, for the last term notice that if θ ′ (x) = o(1/x) for x close to 0, then lim x→0 xθ ′ (x) = 0 and the proof is completed.

Additionally, Bregman divergence satisfies the properties described below.

Proposition A.2. Let h be a K-strongly convex function defined on the simplex X = ∆(A), that has the properties described in reguralizer's properties and let ∆ p be the union of the relative interiors of the faces of X that contain p i.e.,

∆ p = {x ∈ X : supp(p) ⊆ supp(x)} = {x ∈ X : x a > 0 whenever p a > 0} (A.3) Then 1. D h (p, x) < ∞ whenever x ∈ ∆ p .
2. D h (p, x) ≥ 0 for all x ∈ X , with equality if and only if p = x, more particularly

D h (p, x) ≥ 1 2 K x -p 2 for all x ∈ X (A.4)
Proof. For the first part, if x ∈ ∆ p then h(x + t(xp)) is finite and smooth in a neighborhood of 0 and thus D(p, x) is also finite. The second part of the proposition, let z = xp then strong convexity yields

h(x + tz) ≤ th(p) + (1 -t)h(x) - 1 2 Kt(1 -t) x -p 2 t -1 (h(x + tz) -h(x)) ≤ h(p) -h(x) - 1 2 (1 -t)K x -p 2 h(p) -h(x) -t -1 (h(x + tz) -h(x)) ≥ 1 2 (1 -t)K x -p 2
And by taking t → 0, we obtain the result.

We mention at this point that from (reguralizer's properties), since for each i ∈ N : inf ∈[0,1] θ ′′ i > 0, there exists K i > 0 such that for all x, y ∈ [0, 1] and t ∈ [0, 1]

θ i (tx + (1 -t)y) ≤ tθ i (x) + (1 -t)θ i (y) - K i 2 t(1 -t)|x -y| 2 (A.5)
In all the proofs h symbolizes the aggregate function of all the regularizers i.e., h(x) = i h i (x i ), with strong convexity parameter K ≡ min i K i .

A.2. Steep vs non-steep

In this section we elaborate in detail the dichotomy of the properties of different regularizers mentioned in Remark 2. As we mentioned players may have different regularizers h i employed in their choice maps Q i (y) = arg max x∈X i { x, yh i (x)}. Depending on the regularizer chosen, FTRL dynamics may differ significantly. To formally express this difference, it is convenient to consider that h is an extended-real valued function h : V → R ∪ {∞} with value ∞ outside of the simplex X . Then the subdifferential of h at x ∈ V is defined as:

∂h(x) = {y ∈ V * : h(x ′ ) ≥ h(x) + y, x ′ -x ∀x ′ ∈ V} (A.6)
If ∂h(x) is nonempty, then h is called subdifferentiable at x ∈ X . When x ∈ ri(X ) then ∂h(x) is always non-empty or ri(X ) ⊆ dom ∂h ≡ {x ∈ X : ∂h(x) = ∅}. Notice that when the gradient of h exists, then its subgradient always contains it. With these in mind, we present a typical separation between the different regularizers. On the one hand, steep regularizers like the negative Shannonentropy become infinitely steep as x approaches the boundary or ∇h(x) → ∞. On the other hand, non-steep are everywhere differentiable, like the Euclidean, allowing the sequence of play to transfer between the different faces of the simplex. In the dual space of payoffs, steepness implies that the choice map is not surjective (since it cannot map all payoff vectors to points of the boundary), it is however injective (it maps a payoff vector plus a multiple of (1, 1, . . . , 1) to the same strategy). Non-steep regularizers give rise to surjective maps, which are not injective, not even up to a multiple of (1, 1, . . . , 1), to the boundary. Focusing on the more simple case of decomposable regularizers, the kernel of a steep one is differentiable on (0, 1] while for non-steep the kernel is differentiable in all of [0, 1]. As a result, when a steep regularizer is employed the mirror map Q : Y → X cannot return any point of the boundary. In other words, the points of the boundary are infeasible not only as initial conditions but also as part of the sequence of play.

Remark 3. This dichotomy is important for our analysis since we study the stochastic asymptotic stability of Nash equilibria, which may lie on the boundary, and we seek a neighborhood of initial conditions such that the equilibrium to be stable and attracting. Thus, instead of demanding the existence of a neighborhood U of an equilibrium x * , such that whenever X 0 ∈ U , x * is stable and attracting; we demand the existence of a neighborhood U of x * such that whenever X 0 ∈ U ∩ im Q then x * is stable and attracting.

A.3. Polar cone

The notion of the polar cone is tightly connected with the notion of duality. Given a finite dimensional vector space V, a convex set C ⊆ V and a point x ∈ C the tangent cone TC C (x) is the closure of the set of all rays emanating from x and intersecting C in at least one other point. The dual of the tangent cone is the polar cone PC C (x) = {y ∈ V * : y, z ≤ 0 for all z ∈ TC C (x)}.

When the under consideration convex set is the simplex of the players' strategies, the polar cone corresponding to the boundary differs significantly from the one corresponding to the interior. Formally, the polar cone at a point x of the simplex is

PC(x) = {y ∈ Y : y a ≥ y b for all a, b ∈ A} 5 (A.7)
An illustration of this is depicted in Fig. 3. When (FTRL) is run, the notion of the polar cone emerges from the choice map Q : Y → X , connecting the primal space of the strategies with the dual space of the payoffs. The proposition below presents this exact connection.

Proposition A.3. Let h be a strong convex regularizer that satisfies the properties described in reguralizer's properties and let Q : Y → X be the induced choice map then

1. x = Q(y) ⇔ y ∈ ∂h(x)
2. ∂h(x) = ∇h(x) + PC(x) for all x ∈ X .

A.4. Fenchel coupling

Even though Bregman divergence is a useful tool, (FTRL) evolves in the dual space of payoffs. Thus dually to the above the Fenchel coupling 6 is defined,

F h : X × Y → R F h (p, y) = h(p) + h * (y) -y, p for all p ∈ X , y ∈ Y (A.8)
where h * : Y → R is the convex conjugate of h: h * (y) = sup x∈X { y, xh(x)}. The fenchel conjugate is differentiable on Y and it holds that ∇h * (y) = Q(y) for all y ∈ Y (A.9)

Fenchel coupling is also a measure that connects the primal with the dual space. As we mentioned above, (FTRL) evolves in the dual space and thus we use Fenchel coupling to trace its convergence properties. As the next proposition states, whenever Fenchel coupling F (p, y) is bounded from above so does Q(y)p . This proposition in its entity, is critical for our proof, since we first need to find a neighborhood U of attractness (See Definition 1). For this step, Bregman divergence is necessary in order to define the aforementioned neighborhood since Q(y)p < c for some constant c is not necessarily a neighborhood of p (See Appendix A.2).

Proposition A.4. Let h be a K-strongly convex function on X and has the propertied described in reguralizer's properties. Let p ∈ X , then 1. F h (p, y) ≥ 1 2 K Q(y)p 2 for all y ∈ Y and whenever F h (p, y) → 0, Q(y) → p.

F

h (p, y) = D h (p, x) whenever Q(y) = x and x ∈ ∆ p . 3. F h (p, y ′ ) ≤ F h (p, y) + y ′ -y, Q(y) -p + 1 2K y ′ -y 2 * .
Remark 4. Notice that the first part of the proposition is not implied by the second one, since it is possible that im Q = dom ∂h is not always contained in ∆ p (see Appendix A.2).

Proof. For the first part, let x = Q(y) then h * (y) = y, xh(x)

F h (p, y) = h(p) -h(x) -y, p -x (A.10) Since y ∈ ∂h(x) (Proposition A.3), it is h(x + t(p -x)) ≥ h(x) + t y, p -x (A.11)
6. The term is due to [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF].

and by strong convexity of h, we have

h(x + t(p -x)) ≤ th(p) + (1 -t)h(x) - 1 2 Kt(1 -t) p -x 2 (A.12)
Thus by combining (A.11),(A.12) and taking t → 0 we get

F h (p, y) ≥ h(p) -h(x) -h(p) + h(x) + K 2 p -x 2 ≥ K 2 p -x 2 (A.13)
For the second part of the proposition, notice that x + t(px) lies in the relative interior of some face of X for t in a neighborhood of 0 and thus h(x + t(px)) is smooth and finite. So, h admits a two-sided derivative along xp and since y ∈ ∂h(x), y, px = h ′ (x; px) and our claim naturally follows.

Finally for the last part of the proposition, we have

F h (p, y ′ ) = h(p) + h * (y ′ ) -y ′ , p ≤ h(p) + h * (y) + y ′ -y, ∇h * (y) + 1 2K y ′ -y 2 * -y ′ , p = F h (p, y) + y ′ -y, Q(y) -p + 1 2K y ′ -y 2 *
where the second inequality follows from the fact that h * is 1/K strongly smooth [START_REF] Tyrrell Rockafellar | of A Series of Comprehensive Studies in Mathematics[END_REF].

In terms of Fenchel coupling our reciprocity assumption can be written as

F h (p, y) → 0 whenever Q(y) → p (Reciprocity)
Again for most of h decomposable, the assumption is turned into a property as we prove below.

Proposition A.5. If h(x) = i θ(x i ), with θ having the properties described in (reguralizer's properties) and furthermore it holds that θ ′ (x) = o(1/x) for x close to 0, then F h (p, y) → 0 whenever Q(y) → p for all p ∈ X .

Proof. Again it is sufficient to prove that whenever Q(y) = x → 0 then F h (p, y) → 0. Notice that from Proposition A.4 F h (p, y) = D h (p, x) whenever x = Q(y) and x ∈ ∆ p . Thus by Proposition A.1 Q(y) = x → 0 implies that F h (p, y) → 0.

A. What this property actually states is that in a neighborhood of x * , it strictly dominates over all other strategies. Interestingly, strict Nash equilibria hold this property:

Proposition A.6. For finite games in normal form, the following are equivalent:

x * x v(x)
Figure 2: (VS) states that the payoff vectors are pointing "towards" the equilibrium i) x * is a strict Nash equilibrium.

ii) v(x * ), z ≤ 0 for all z ∈ TC(x * ) with equality if and only if z=0.

iii) x * is variationally stable.

Proof. We will first prove that i) ⇒ ii) ⇒ iii) ⇒ i). i) ⇒ ii) Since x * is a Nash equilibrium by definition it holds for each player i that

v(x * ), x -x * ≤ 0 for all x ∈ X (A.14)
For the strict part of the inequality, by definition of strict Nash equilibria it holds that v i (x * ), x ix * i < 0 whenever x i = x * i and thus

v(x * ), z = N i=1 v i (x * ), x i -x * i < 0 if x i = x * i for some i or z = 0 (A.15)
ii) ⇒ iii) By definition of the polar cone, we have that v(x * ) belongs to the interior of PC(x * ) 7 .

Thus by continuity there exists some neighborhood of x * such that v(x) also belongs to the polar cone of PC(x * ) or x * is variationally stable.

iii) ⇒ i) Assume now that x * is variationally stable but not strict, then there exist for some player i a,b ∈ A i such that u i (a; x * -i ) = u i (b; x * -i ). Then for x i = x * i + λ(e ae b ) and

x -i = x * -i we have v(x * ), x -x * = v i (x * ), λ(e a -e b ) = 0 (A.16)
which is a contradiction.

A.6. Martingale limit theory

Our analysis leverages tools from martingale limit theory. Below we first present a simple fact for the reader to keep in mind, followed by the main theorems that we utilize in the main body of our proofs Fact 1. Let R n = n k=1 r k , where r k is a positive random variable for all k = 0, 1, . . . attached to the filtration F k-1 . Then R n is a submartingale.

We begin with the strong law of large numbers for martingale difference sequences:

7. Indeed if it belonged to the boundary then the equality in ii) would not hold only for z = 0. Theorem 3. Let R n = n k=1 r k be a martingale with respect to an underlying stochastic basis (Ω, F, (F n ) ∞ n=1 , P) and let (τ n ) ∞ n=1 be a nondecreasing sequence of positive numbers with

lim n→∞ τ n = ∞. If ∞ n=1 τ -p n E[|r n | p | F n-1 ] < ∞ for some p ∈ [1, 2] almost surely, then lim n→∞ τ -1 n R n = 0 almost surely (A.17)
The second important result for our analysis is Doob's martingale convergence theorem:

Theorem 4. If R n is a submartingale that is bounded in L 1 (i.e., sup n E[|R n |] < ∞), R n converges almost surely to a random variable R with E[R] < ∞.
Finally, we use the known as Doob's maximal inequality and one of its variants, presented below:

Theorem 5. Let R n be a non-negative submartingale and fix some ε > 0. Then:

P(sup n R n ≥ ε) ≤ E[R n ] ε (A.18)
Theorem 6. Let R n be a martingale and fix some ε > 0. Then:

P(sup n |R n | ≥ ε) ≤ E[R 2 n ] ε 2 (A.19)
Proofs of all these results can be found in [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF].

A.7. Deferred Proof of Theorem 1

In the following preliminary result, we focus on the case of (FTRL) with payoff feedback as described in Section 3.1 and we show that if x * is a strict Nash equilibrium, there exists a subsequence of (X n ) ∞ n=0 that converges to it. In order to achieve this convergence result, it is necessary to assume that the sequence (X n ) ∞ n=0 is contained in a neighborhood of x * , in which (VS) holds. Here, we outline the basic steps below:

Step 0: By contradiction, assume that there exists a neighborhood, in which X n is not contained for all sufficiently large n and assume without loss of generality that holds for all n = 0, 1, . . ..

Step 1: We start by showing that the terms of the RHS of the third property described in Proposition A.4 are converging almost surely to finite values, except for one. This term, which is a consequence of x * being variational stable, goes to -∞ as n → ∞ .

Step 2: The next crucial observation is that the Fenchel coupling is bounded from below by 0, thanks to the first property in Proposition A.4, which gives us the contradiction.

Remark. For the interested reader, the assumption (A2), n γ 2 n M 2 n < ∞, that we use in the preliminary lemma and in Theorem 1 could be relaxed by using the Hölder inequality to n γ 1+q/2 n M q n < ∞ for any q ∈ [2, ∞).

Lemma A.1. Let x * ∈ A be a strict Nash equilibrium. If (FTRL) is run with payoff feedback of the type [START_REF] Kuen | Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games[END_REF], that satisfies (A1)-(A2) and the sequence of play (X n ) ∞ n=0 does not exit a neighborhood R of x * , in which variational stability holds, then there exists a subsequence X n k of X n that converges to x * almost surely.

Proof. Suppose that there exists a neighborhood U ⊆ R of x * , such that X n / ∈ U for all large enough n. Assume without loss of generality that this is true for all n ≥ 0. Since variational stability holds in R, we have v(x), xx * < 0 for all x ∈ R, x = x * (A.20) Furthermore, from Proposition A.4 we have that for each round n:

F h (x * , Y n+1 ) ≤ F h (x * , Y n ) + γ n vn , X n -x * + 1 2K γ 2 n vn 2 * (A.21)
By applying the above inequality for all rounds from 1, ..., n and creating the telescopic sum we get

F h (x * , Y n+1 ) ≤ F h (x * , Y 0 ) + n k=0 γ k vk , X k -x * + 1 2K n k=0 γ 2 k vk 2 * (A.22)
Remember that for the payoff vector holds that

vn = v(X n ) + Z n + b n We now rewrite (A.22) F h (x * , Y n+1 ) ≤ F h (x * , Y 0 ) + n k=0 γ k v(X k ), X k -x * + n k=0 γ k Z k , X k -x * + n k=0 γ k b k , X k -x * + 1 2K n k=0 γ 2 k vk 2 * (A.23) Let τ n = n k=0 γ k then F h (x * , Y n+1 ) ≤ F h (x * , Y 0 ) + n k=0 γ k v(X k ), X k -x * + τ n ( n k=0 γ k b k , X k -x * τ n ) + τ n ( n k=0 γ k Z k , X k -x * τ n + 1 2K n k=0 γ 2 k vk 2 * τ n ) (A.24)
We focus on the asymptotic behavior of each particular term of the previous inequality. We remind that F n denotes the history of X n up to stage n (inclusive) and thus the feedback signal, vn is not

F n -measurable in general. • Let R n = n k=0 γ 2 k vk 2 * . Then E[R n ] ≤ n k=0 γ 2 k E[ vk 2 * ] = n k=0 γ 2 k E[E[ vk 2 * | F k ]] ≤ n k=0 γ 2 k M 2 k < ∞ (A.25)
where n k=0 γ 2 k M 2 k is finite by assumption (A2). Hence by Fact 1 and (A.25) R n is an L 1 bounded submartingale while Doob's convergence theorem (Theorem 4) shows that almost surely

lim n→∞ τ -1 n R n = 0 (A.26) lim n→∞ τ -1 n S n = 0 (A.35) • Let W n = n k=0 γ k b k , X k -x * then by Cauchy-Schwarz inequality |τ -1 n W n | ≤ |τ -1 n n k=0 γ k b k , X k -x * | ≤ τ -1 n n k=0 γ k | b k , X k -x * | ≤ τ -1 n n k=0 γ k b k * X (A.36)
Let J n = n k=0 γ k b k * X . Notice that W n ≤ J n and that from Fact 1 J n is a submartingale with As a result, τ -1 n W n → 0. • Finally, we will examine the term n k=0 γ k v(X k ), X kx * . Recall that we had assumed that X n ∈ R \ U for all n ≥ 0, while variational stability holds in R, so by continuity there exists c > 0, such that for all n ≥ 0 v(X n ), X nx * ≤ -c (A.39)

E[J n ] = X n k=0 γ k E[ b k * ] ≤ X n k=0 γ k E[E[ b k * | F k ]] ≤ X n k=0 γ k B k < ∞ (A.

Immediate implications of Lemma B.1 are:

Corollary 3. There exists player i ∈ N and pure strategy profile (α i ; α -i ) ∈ supp(x * ), such that u i (α i ; α -i ) = 0.

Corollary 4. There exist β ′ > 0, player i, strategies a, b ∈ supp(x * i ) and pure strategy profile α -i ∈ supp(x * -i ) such that |u i (a; α -i )-u i (b; α -i )| ≥ β ′ . There also exist β ′′ > 0 and (α i ; α -i ) ∈ supp(x * ) such that |u i (α i ; α -i )| ≥ β ′′ .

x 1 x 2 x 3 x 1 x 2 x 3
x 1 x 2

x 3

Figure 3: The polar cone corresponding to different points of the simplex. For an interior point this is a line perpendicular to the simplex. For a point of the boundary, it is a plane perpendicular to the simplex tangential to the point of the boundary. For an edge the polar cone corresponds to a cone.

B.2. Deferred proof of Theorem 2

Before moving on our proof we first provide some intuition derived from the notion of the polar cone (Appendix A.3). Looking at Fig. 3, the polar cone corresponding to fully mixed or mixed Nash equilibria has a key difference with the one corresponding to strict Nash equilibria. The latter, in contrast to the former, is fully dimensional. Thus intuitively, considering a sufficiently small neighborhood of a mixed Nash equilibrium, the slightest perturbation in the dual space of the payoffs, will lead to instability of the system. Our result is based on this intuition; we prove by contradiction that there exists a sufficiently small neighborhood of a mixed Nash equilibrium, from which the sequence of play will escape with strictly positive probability. The decomposability assumption of the regularizers ensures that the proof holds also for steep regularizers (See Appendix A.2). Below, leveraging the definition of the polar cone in simplex, we prove a useful property for the difference of the aggregated payoffs of FTRL for a sequence of play that shares common pure strategies.

Lemma B.2. Let X i = Q(Y i ) ∈ X i be a mixed strategy profile and a, b ∈ supp(X i ) be two pure strategies, for some player i ∈ N . Then it holds: Y i , e ae b = ∇h i (X i ), e ae b Additionally, if (FTRL) is run then for a sequence of play X i,n 1 , . . . , X i,n 2 that maintains in its support both pure strategies a, b ∈ A i it holds Y i,k 1 -Y i,k 2 , e ae b = ∇h i (X i,k 1 ) -∇h i (X i,k 2 ), e ae b ∀k 1 , k 2 ∈ {n 1 , . . . , n 2 } By rearranging we have

θ ′ i (X ia,n+1 ) -θ ′ i (X ia,n ) -θ ′ i (X ib,n+1 ) -θ ′ i (X ib,n ) = γ n (v ia,n -vib,n ) (B.13)
As a consequence of θ i being continuously differentiable in all of (0, 1], θ ′ i is continuous in [L(ε), 1], where L(ε) is the lower bound of X ia , X ib whenever X ix * i < ε. L(ε) can be guaranteed to be positive for a sufficiently small ε < ε ′ , which ensures that all the points of the neighborhood contain the support of the equilibrium for player i. Therefore, from extreme value theorem in θ ′ i , there exist finite C a , C b corresponding to a, b equivalently, such that

θ ′ i (X ia,n+1 ) -θ ′ i (X ia,n ) ≤ C a |X ia,n+1 -X ia,n | < 2 • C a • ε (B.14) θ ′ i (X ib,n+1 ) -θ ′ i (X ib,n ) ≤ C b |X ib,n+1 -X ib,n | < 2 • C b • ε (B.15)
By applying the triangle inequality in (B.13) and using (B.14),(B.15) we get

γ n |v ia,n -vib,n | < (2 • C a + 2 • C b ) • ε (B.16)
Equivalently,

|v ia,n -vib,n | < 2 • C a + 2 • C b γ n • ε (B.17)
The above inequality holds with probability 1δ. Thus, if the sequence of play X n is contained to an ε-neighborhood of x * i.e., X nx * < ε for all n ≥ 0, then the difference of the feedback, for some player i ∈ N , to two strategies of the equilibrium is O(ε/γ n ) with probability at least 1δ.

We now fix ε to be which is a contradiction. Thus, a mixed Nash equilibrium cannot be stochastically asymptotically stable, under (FTRL) for types of payoff feedback described in Section 3.1. Notice that this analysis holds even for the first round. Once the parameters of the algorithm have been determined, asymptotic instability can be derived in whichever finite round.

ε < min ε ′ , γ n 2 • C a + 2 • C b β (B.

3 Figure 1 :

 31 Figure 1: The level sets of KL-divergence

  [START_REF] Slivkins | Introduction to multi-armed bandits[END_REF] whereB n is the upper bound of E[ b n * | F n ]. Thus, J n is a L 1 boundedsubmartingale and by Doob's convergence theorem (Theorem 4) almost surely lim n→∞ τ -1 n J n = 0 (A.38)

  [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF] and consequentlyP(|v ia,nvib,n | < β | F n ) ≥ 1δ (B.19)However, from assumption (A3), it holds thatP(|v ia,nvib,n | ≥ β) ≥ π n (B.20)Combining (B.[START_REF] Hofbauer | Evolutionary game dynamics[END_REF]),(B.20) we conclude1 = P [{|v ia,nvib,n | ≥ β} ∪ {|v ia,nvib,n | < β}] (B.21) = P [|v ia,nvib,n | ≥ β] + P [|v ia,nvib,n | < β]

  a strict Nash equilibrium of Γ. If (FTRL) is run with inexact payoff feedback satisfying Assumptions (A1) and (A2), then x * is stochastically asymptotically stable. Theorem 2. Let x * be a mixed Nash equilibrium of Γ. If (FTRL) is run with inexact payoff feedback satisfying assumption (A3), then x * is not stochastically asymptotically stable. Corollary 1. Suppose that (FTRL) is run in a generic game with oracle-based feedback as in Model 1 and a sufficiently small step-size γ n with n γ 2 n < ∞. Then, a Nash equilibrium is stochastically asymprotically stable if and only if it is strict. Corollary 2. Suppose that (FTRL) is run in a generic game with bandit feedback as in Model 2 and sufficiently small step-size and explicit exploration paramters with n

  5. Variational stability Definition 2 (Variational stability). A point x * ∈ X is said to be variationally stable if there exists neighborhood U of x * such that

	v(x), x -x * ≤ 0 for all x ∈ U	(VS)
	with equation if and only if x = x

* .

© A. Giannou, E.-V. Vlatakis-Gkaragkounis & P. Mertikopoulos.

"Uncoupled" means here that each player's update rule does not depend explicitly on the payoffs of other players.

Of course, since the feedback signal is generated only after the player chooses a strategy, vn is not Fn-measurable in general.

when all other players' also employ strategies of the equilibrium

It is always ya = y b whenever a, b ∈ supp(x).

* | F n ] described in Section

3.1. Obviously, ∞ n=0 τ -2 n E[|ψ n | 2 | F n ]< ∞ and so by the strong law of large number for martingales (Theorem 3) yields that almost surely

Therefore R n is a supermartingale and it is also L 1 bounded (each one of the terms is bounded) and so from Doob's convergence theorem (Theorem 4) R n converges to a finite random variable and so does

The above analysis shows that whenever Y 0 ∈ U * ε and thus X 0 ∈ U ε ∩ im Q, X n ∈ U 4ε ∩ im Q and converges to x * with arbitrary high probability. Hence, x * is stochastically asymptotically stable.

• Let S n = n k=0 γ k Z k , X kx * and ψ k = γ k Z k , X kx * . For the expected value of ψ n we have

and so S n is a martingale since E[S n | F n ] = S n-1 . Moreover, for the expectation of the absolute value of ψ n , Cauchy-Schwarz inequality implies

where M 2 n is the upper bound of E[ vn We return to (A. [START_REF] Leslie | Generalised weakened fictitious play[END_REF] and we equivalently we have that [START_REF] Cesa | Prediction, Learning, and Games[END_REF] we conclude to a contradiction. This implies that some instance of the sequence of play is included to every neighborhood U of x * and thus there exists subsequence X n k of X n that almost surely converges to x * .

Theorem 7 (Restatement of Theorem 1 ). Let x * be a strict Nash equilibrium. If (FTRL) is run with payoff feedback that satisfies (A1)-(A2), then x * is stochastically asymptotically stable.

Proof. Fix a confidence level δ and let

Finally, by (Reciprocity) U ε is a neighborhood of x * . Since x * is a strict Nash equilibrium, pick ε sufficiently small such that (VS) holds for all x ∈ U 4ε .

(Stability).

Assume now that Y 0 ∈ U * ε and thus F h (x * , Y 0 ) < ε ≤ 4ε. We will prove by induction that Y n ∈ U * 4ε for all n ≥ 1 with probability at least 1δ. Suppose that F h (x * , Y k ) < 4ε for all 1 ≤ k ≤ n and we will prove that Y n+1 ∈ U * 4ε and consequently X n+1 ∈ U 4ε .

From Proposition A.4 we have

For the payoff feedback, it holds vn = v(X n ) + Z n + b n . Then by telescoping the above inequality and substituting we get

We will study each term of the inequality separately.

will occur with probability at most δ/3.

Since S n is a martingale, as we discussed in Lemma A.1, Doob's maximal inequality (Theorem 6) yields

In order to calculate the above upper bound, we define

where,

n=0 E ε,n will occur with probability at most δ/3.

Similarly to the previous steps let D ε,n = {sup 0≤k≤n J k ≥ ε}, then Doob's maximal inequality (Theorem 5) yields

will happen with probability at most δ/3, which implies that with probability at most δ/3 W n will exceed ε for all n ≥ 0.

• Furthermore, if X k belongs to a neighborhood in which (VS) holds for all 0 ≤ k ≤ n, we have

By demanding the parameters of the algorithm to satisfy:

If all of Ēε , Fε , Dε hold, this happens with probability P( Ēε Fε Dε ) ≥ 1δ and from (A.42) we have F h (x * , Y n+1 ) < 4ε. This immediately yields that Y n+1 ∈ U * 4ε and consequently as we explained in the begin of the proof X n+1 ∈ U 4ε , in which variational stability holds, with probability at least 1δ.

(Convergence).

By Lemma A.1 there exists a subsequence X n k that converges to x * . By (Reciprocity) we have that lim inf n→∞ F h (x * , Y n ) = 0. In order to complete the proof, it is sufficient to prove that the limit of F h (x * , Y n ) exists. Notice that since the sequence of play remains in U 4ε variational stability holds and thus v(X n ), X nx * ≤ 0. Again using Proposition A.4 we have:

Notice that since from Proposition A.4 F h (x * , Y ) ≥ 0, if we apply absolute values in the above inequality we have

Having this in mind vi,n can be viewed as

where

Finally, similarly to (B.1) we can conclude that M 2 n = O(1/ε n ). We continue by proving that assumption (A3) is indeed satisfied for both Model 1, Model 2. This is due to the genericity of the game. Actually in the following lemma and corollaries we show that there exist player i ∈ N , strategies a, b ∈ supp(x * i ) and pure strategy profile α -i ∈ supp(x * -i ), where x * is a mixed Nash equilibrium such that |u i (a; α -i )u i (b; α -i )| ≥ β for some β > 0. In order to acquire the exact statement of (A3), we have to take into account the round in which the game is evolved. Let n > 0 be this round, then when examining the stochastic asymptotic stability of a mixed Nash equilibrium x * , the sequence of play is contained in a neighborhood of x * and thus all of the strategies belonging to the support of x * have strictly positive probability to be chosen, verifying the statement of (A3).

Lemma B.1. If the game is generic and has a mixed Nash equilibrium x * , then there exist player

Proof. Assume that for all players i ∈ N , pure strategy profiles

Then for each player i, this implies that all of the payoffs corresponding to pure strategy profiles, which consists of the support of the equilibrium, are equal. Then each pure strategy profile (α i ; α -i ) ∈ supp(x * ) is a pure Nash equilibrium, which is a contradiction to the genericity of the game.

Proof. From Proposition A.3, Y i can be analyzed as

). Since X i assigns positive probability to both a, b, by definition of the polar cone it is G a = G b . Thus,

For the second part, by applying (B.5) for both cases of Y i,k 1 , Y i,k 2 we have:

From the subtraction of the above equations, we derive the desideratum: Proof. We start by determining all the parameters of the algorithm (FTRL) and we assume ad absurdum that x * is a mixed Nash equilibrium, which is stochastically asymptotically stable. Then for all neighborhoods U of x * and δ > 0, there exists some neighborhood U 0 such that whenever X 0 ∈ U 0 , it holds that X n ∈ U for all n ≥ 0 with probability at least 1δ. This equivalently implies that for all ε, δ > 0 if X 0 ∈ U 0 , X nx * < ε for all n ≥ 0, with probability at least 1δ.

We leave ε to be chosen at the end of our analysis, but we will consider it to be fixed.

For each player i ∈ N and round n if X i,n , X i,n+1 are two consecutive instances of the sequence of play; then X i,nx * i < ε, X i,n+1x * i < ε and by the triangle inequality X i,n+1 -X i,n < 2ε (B.9)

We fix a round n and focus on player i ∈ N who has the property of (A3) However, by definition of (FTRL) Y i,n+1 -Y i,n = γ n vi,n and by taking into consideration that the regularizers used are decomposable, we get (θ ′ i (X ia,n+1 )θ ′ i (X ib,n+1 ) -(θ ′ i (X ia,n )θ ′ i (X ib,n ))) = γ n vi,n , e ae b (B.12)


Frederic Lebon

Serge Dumont

Application of the Wavelet-element Method to Linear Random Materials

This paper is devoted to the statistical study of the effective linear prop- erties of random materials, that is to say microstructures are random lattices given by a stochastic process. The local numerical procedure associated to homogenization techniques is based on a wavelet-element method. The numerical results are compared with classical theories. A new approach is obtained in order to determine these effective properties if the details of the microstructure are not well-known.

Introduction

The purpose of this paper is to determine and to compute the effective properties of linear random heterogeneous media. While natural geomaterials are heterogeneous, they are regarded as homogeneous with effective properties which manipulate the overall behavior. Grounds, for example, are usually modeled as a body consisting of homogeneous materials with such effective properties. Behavior of these grounds cannot be predicted if the effective properties are poorly determined. The necessity to incorporate more detailled informations on the microstructure is clearly recognized. In the last years, a large part of literature has presented measurements, empirical and theoretical techniques in order to determine these effective properties. Clearly, the numerical cost to attack this problem directly for a given material sample is prohibitive. In former papers, the authors have presented numerical scheme associated to homogenization techniques in order to take into account the details of the microstructure [START_REF] Dumont | Representation of plane elastostatics operators in Daubechies wavelets[END_REF][START_REF] Dumont | Wavelet-Galerkin method for heterogeneous media[END_REF][START_REF] Dumont | Wavelet-galerkin method for plane elasticity[END_REF][START_REF] Dumont | A numerical tool for periodic heterogeneous media. Application to interface in Al/ Sic composites[END_REF][START_REF] Lebon | Small parameter, homogenization and wavelets[END_REF]. These algorithms are based on wavelet basis and permit to predict the effective properties from the knowledge of the microstructure. Thus, it is possible to optimally design linear composite materials from real images of the sample. In most cases, unfortunately, the details of the microstructure are not absolutely known, and leads us to estimate the effective properties from statistical studies. In a famous paper [START_REF] Torquato | Random heterogeneous media: Microstructure and improved bounds on effective properties[END_REF], Torquato has presented results concerned with the case where a partial statistical information, as correlation functions, is given. Improved bounds on effectives properties of two-phase random heterogeneous media are obtained. In this paper, we suppose that only the volume fraction of each phase is known, and we intend to find the averaged effective properties of the composite. In addition, we suppose that the microstructure is given pixel by pixel i.e. the characteristic shape of the microstructure components is a small square and its characteristic lenght is the lenght of the pixel. In section 1, we present the notations and the mechanical problem. Section 2 is devoted to the numerical algorithm. In section 3, we present a statistical study for a AlSiC composite. The results obtained are compared with Hashin and Shtrickman bounds [START_REF] Hashin | A variational approach to the theory of the elastic behavior of multiphase materials[END_REF] and with the self-consistent schema [START_REF] Hill | A self-consistant mechanics of composite materials[END_REF]13]. At the end of the paper, perspectives to this work are presented.

The mechanical problem

We consider a two phase isotropic elastic composite and we intend to study the behaviour of this heterogeneous media. A step of homogenization consists in determining the effective properties which characterize the equivalent homogeneous medium. Let us consider a plane periodic composite fl (macroscale, variable x) and a rectangular periodicity cell Y (micro-scale, variable y). We assume that the bonds at all interfaces of the composite are perfect. The elasticity coefficients Cfjkl are supposed to be periodic on the period Y.

In elastostatics, the problem (Pc:) is written

Problem(PE:) Find uc: E V such that ac:(uc:,v) = L(v), V v E V, where ac:(u, v) = J Cfjkzekz(u)eij(v)dx, n ekz(u) = ~(uk,l + uz,k), L(v) = J fvdx + J Fvdl n a,n
The solution of the previous problem uc: tends to u in V, the space of admissible global displacements, u is the solution of problem P [START_REF] Bensoussan | Asymptotic analysis for periodic structures[END_REF] Problem(?) In this section, we focus on the solution of problem Py. This problem is solved by a wavelet-element method [START_REF] Wells | Wavelet solutions for the Dirichlet problem[END_REF] associated to Daubechies wavelets [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF]. This method is based on the standard form of the discretized operator [START_REF] Beylkin | On the representation of operators in bases of compactly supported wavelets[END_REF]. Details concerning this method can be found in previous papers of the authors [5,8,?]. Let Aj = [0,2J -1], the local displacement u = (u1,u2) is approached in the space VJmax as PJk(y) = ¢jk, (yl)¢;k 2 (y2), Pjk(y) = ~jk, (yl)~;k 2 (Y2), Pjk(y) = ~jk, (y1)¢;k2 (Y2), Pjk(y) = ¢jk, (yl)¢;k2 (y2), where ¢jk(x) = 2J1 2 ¢(2Jx -l) and ~jk(x) = 2J/ 2 ~(2Jx -l). ¢is the scale function and ~ is the associated wavelet. Problem (Py) is discretized using this approximation, well-conditioned stiffness matrices are obtained [START_REF] Wells | Wavelet solutions for the Dirichlet problem[END_REF][START_REF] Beylkin | On the representation of operators in bases of compactly supported wavelets[END_REF].

Find u E V such that a(u,v) = L(v), V v E V,

Numerical results

In this part of the paper, numerical tests are presented. They are concerned by a AlSiC composite. The influence of two parameters is studied: the volume fraction of each component (Aluminium and Silicium) and the distribution of each material in the microstructure. For each volume fraction, we proceed to about 5000 draws (random lattices) and we study from a statistical point of view the results obtained. In the following the fourth order tensor A is repre- sented as a matrix of order 3. For a volume fraction of 70 % the variations of each elasticity coefficient are presented in Fig. 1 for about 5000 microstructures. At first sight, the fluctuations seem very large. In the other hand, one The averaged values of each coefficient of the elasticity tensor are given in Fig. 3. We observe the convergence of the coefficients to an mean value along the draws. The values obtained in Fig. 3 show t hat the numerical limit is an isotropic material. In particular, we have A13 = A23 = 0 and Au = A22• Thus, it is possible to compute the bulk and shear moduli of the limit material (Averaged bulk and shear moduli).

In the following we denote by L-HS and U-HS the Lower and Upper Hashin and Shtrickman bounds [START_REF] Hashin | A variational approach to the theory of the elastic behavior of multiphase materials[END_REF] . We denote by WAV the Averaged Value obtain by the Wavelet-element method. Fig. 6 shows t hat the relative behavior of the value is split ted in three phases: in the first one, for volume fraction lower than 0.25, the LHS and the WAV values are very closed. The second phase corresponds to volume fractions between 0.25 and 0.95. In t his phase, the WAV value is intermediate between the two HS bounds. The third phase, for a volume fraction larger than 0.95, shows WAV values closed to the U-HS bound.

2 0 0 , --------------. We compare the results with the self-consistant schema for the shear modulus and for volume fractions lower than 0.5. We observe in Fig. 7 that for the lower value of the volume fraction (lower than 0.1) the L-HS value, the self-consistant schema (denoted SCS) and the WAV value are quite similar. For larger values from 0.1 to 0.25 the values L-HS and WAV are equal and the SCS value is lower than the two other one. For volume fractions larger than 0.25 and lower than 0.4, the L-HS and SCS values are closed , and lower than the WAV value.

Concluding remarks and perspectives

Generally, it is impossible to determine exactly the effective properties of random heterogeneous media. In the literature, rigorous statements about these effective properties take the form of bounds. In this paper, we obtain another kind of bounds as the form of an average and a standard deviation. An important result is the numerical convergence of the stochastic process of homogenization to an averaged solution, that is to say that the limit, when the number of draws tends to infinity, of the potential energy corresponding

3

 3 where a(u,v) = J Aijklekz(u)eij(v)dx n and Aijkl = mea:(Y) j(Cijkl + Cijpqepq(uk 1 ))dy. y The determination of the displacements uij needs to solve three local problems on Y (Problem Py) in the space H = (H~er(Y)) 2 , the set of ad- missible local displacements: Problem(Py) Eij be given, find uij E H such that ay(uiJ,v) = l(v) Vv E H, where ay(u, v) =I cijkl(y)eij(u)ekz(v)dy y and l(v) =-I cijkl(y)Eijekz(v)dy. y Numerical procedure

Fig. 1 .

 1 Fig. 1. Homogenized plane elasticity tensor (MPa) versus draws (volume fraction 70 %), linen and column m correspond to Anm

  ---------------.2 0 0 ,--------------, . --------------, 200,.------------------.200,----------------.

Fig. 2 .

 2 Fig. 2. Histogram of plane elasticity tensor (volume fraction 70 %)

Fig. 3 .Fig. 5 .Fig. 6 . 7 Hashin-Shtnckman upper bOund 4 Hashin-Fig. 7 .

 356747 Fig. 3 . Averaged homogenized elasticity tensor versus draws (volume fraction 70 %)

Acknowledgments

The authors gratefully acknowledge R. Peyroux for helpful discussions, light- ing comments and self-consistant schema software.

chanica! couplings, plasticity [START_REF] Lebon | Homogenization and wavelet-Galerkin method for a nonlinear one-dimensional problem[END_REF], ... The efficiency of our method permits us to envisage to treat this kind of problems.