{'fraction_non_alphanumeric': 0.055877836546664394, 'fraction_numerical': 0.014707387817778536, 'mean_word_length': 4.011200410396717, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bandit Learning in Convex Non-Strictly Monotone Games

We address learning Nash equilibria in convex games under the payoff information setting. In this setting, each agent does not know the functional form of her objective and can only receive feedback on the evaluation of her objective function at a feasible action profile chosen by her and other players. We consider the case in which the game pseudo-gradient is monotone but not necessarily strictly monotone. This relaxation of strict monotonicity enables application of learning algorithms to a larger class of games, such as a zero-sum game with a non-strictly convex-concave cost function. We derive an algorithm with provable convergence to Nash equilibria in this setting. While characterizing the convergence rate of the payoff-based algorithm in a non-strongly monotone game is challenging, we view the game as an instance of bandit online optimization. Through this lens, we quantify the regret rate of the algorithm and provide an approach to choose the algorithm's parameters to ensure minimal regret rate while converging to a Nash equilibrium.


Introduction
Game theory is a powerful framework to address optimization and learning of multiple interacting agents referred to as players. Such multi-agent problems arise in many application domains including traffic networks, internet, auctions, and adversarial learning [1,28,22,9]. In several applications, each player might not know the functional form of her objective. For example, the travel times of different routes in a traffic network [20], price functions in an electricity market [19,36,31], or outcomes of an electricity market auction [14] are unknown a priori and depend in non-trivial ways on actions of other players. By playing the game, a player can have access to the so-called payoff information. Namely, she receives objective function evaluations at feasible joint actions.
In this work, we develop a learning algorithm, based on payoff information, for a class of convex games with non-strictly monotone pseudo-gradients. We establish convergence of the players' actions to a Nash equilibrium and derive the regret rate of the algorithm. To state the contributions concretely, we briefly present the convex game setup under our consideration and the pertinent literature.

Literature review
In a convex game, each player's objective is convex in her own decision variable for any fixed action of other players. Furthermore, players' strategy sets are convex. Payoff-based learning of Nash equilibria in convex games has been addressed in [5,34,27]. Whereas the paper [27] used two-point function evaluations to estimate gradients, thus, requiring more coordination between agents, the works [5,34] leveraged the idea of estimating the gradient of a player's cost function with respect to her decision variable at a given point, using only one point function evaluations, namely, the payoff at a given joint strategy. This idea is based on similar approaches in stochastic optimization [11,23]. To establish convergence of the sequence of actions to the Nash equilibrium, the strict monotonicity of the pseudo-gradient of the game is used, see Definitions 3 and 4 for pseudo-gradient and monotonicity, respectively.
The assumption of strict monotonicity of the pseudo-gradient rules out several classes of games, such as the class of zero-sum games with non-strictly convex objective. This class of games includes mixed-strategy extension of any finite-action game. Zero-sum games have been widely adopted in robust optimization and control, in saddle point problems and more recently in adversarial training and deep learning. Thus, understanding convergence of learning algorithms under a standard convexity assumption is a fundamental problem. The non-strictly monotone game class also includes non-zero sum games (see Example 2 for a simple illustration). Furthermore, a game with coupling constraints between players' actions can be cast as a game without a coupling constraint but with additional players corresponding to the Lagrangian multipliers of the coupling constraints [10,34]. Such games have at best non-strictly monotone pseudo-gradients.
In the absence of the strict monotonicity assumption, there exists convergent algorithms, but not under the payoff-based information. In particular, leveraging the equivalence of a Nash equilibrium in convex games with the solution set of a so-called variational inequality problem, one can use approaches for solving non-strictly monotone variational inequalities, such as those based on double time-scale Tikhonov regularization (double time-scale referring to an algorithm with an inner and outer loop) or extra-gradient step [26,Chapter 12]. Recent works have generalized these approaches to the case in which stochastic samples of the pseudo-gradient are available [16,13,17]. The authors in [16] proposed a single time-scale Tikhonov regularization approach (single time-scale referring to no inner loop in contrast to the double-time scale approaches before) to guarantee convergence of the last iterate of the algorithm to the Nash equilibrium. On the other hand, [13] used a singlecall variant of extra-gradient based algorithms and proved convergence of time-average sequence of iterates rather than the last iterate. The work [17] investigated the operator extrapolation approach to optimize the convergence rate of the so called gap function estimated for a specific time-average sequence of iterates.
Even though using the payoff information one can form a stochastic estimate of the pseudogradient map at a joint strategy for which the objective functions are queried, such an estimate would not satisfy the bias and variance assumptions of the stochastic pseudo-gradient in the works [16,13]. To our knowledge, the first work addressing payoff-based learning in non-strictly monotone games was [35]. A single time-scale Tikhonov regularization term was introduced, motivated by [16]. The regularization ensured strict monotonicity of the game map during the algorithm iterates and by properly tuning its parameter, convergence to a Nash equilibrium was established. There were two shortcomings in [35]. First, the algorithm could not be implemented online since the feasibility of actions was not guaranteed during the learning. Second, the analysis lacked any convergence rate and there were no guidelines on how to set the procedure's parameters. In our current manuscript, we extend our conference contribution above to specifically address these shortcomings as follows.
To address feasibility of actions, we project the query points onto the feasible set, similar to the idea of projected stochastic gradient descent. Hence, the players evaluate their cost functions at feasible joint actions. However, different than projected stochastic gradient algorithms, we project the algorithm iterates onto a time-varying shrunk feasible set, by introducing a parameter controlling the set shrinkage. By properly tuning this shrinkage parameter with the Tikhonov regularization parameter we ensure that the bias and variance of the pseudo-gradient satisfy conditions for convergence of the algorithm iterates, see Theorem 1. The addition of this extra shrinkage parameter necessitates new analysis for convergence proof if compared to [35]. In particular, Propositions 2 and 3 are novel and needed to obtain the convergence result of Theorem 1.
To address the convergence rate, we find inspiration from the literature on minimizing regret rate in online learning. Observe that deriving convergence rate for monotone (non-strongly) variational inequalities, for which our game is a subset of, is a very challenging problem -past work has used strong monotonicity of the pseudo-gradient to establish convergence rate [5]. However, we can view our payoff-based learning as an instance of an online convex program [38]. In this problem, at every time step each player selects an action and incurs a cost corresponding to a time-varying function evaluated at her chosen action. In a repeated game setting, even though each player has the same cost function at each time step, the actions of other players change in each iteration. Since a player's cost depends on actions of others and she has no direct control over others' actions, from her perspective, her cost function changes with each iteration 1 . Further assuming a payoff information setting, the repeated game falls into class of online convex optimization with zerothorder feedback [11]. Now, the efficiency of an online learning algorithm is measured by its regret rate. Hence, in this work, leveraging this analogy, we establish the regret rate of our algorithm, see Theorem 2. The requirements on the parameters for the optimal regret rate can guide a player in choosing the algorithm parameters, see Corollary 1.
Note that the regret rate is only from the perspective of a single player, regardless of whether other players also employ the same learning algorithm. However, it is known that no-regret algorithms have further implications when all players employ such algorithms in a game. In particular, a large class of no-regret algorithms (mirror-descent) can converge to Nash equilibria under the strict monotonicity assumption on pseudo-gradients [5]. On the other hand, without strict monotonicity, such convergence does not hold in general. The work of [21] showed that even in a simple convex non-strictly monotone setting, namely, the zero-sum game of matching pennies considered in our Example 1, a large class of no-regret algorithms have no guaranteed convergence. In particular, the sequence of played actions exhibits a non-vanishing cycle. Hence, by proving the no-regret property of our algorithm, we show that there exist no-regret algorithms with provable convergence to Nash equilibrium under the payoff-based information setup and only monotonicity assumption on the pseudo-gradient.

Contribution
Summarizing the above discussion, our contributions are as follows.
• We develop, to our knowledge, the first convergent online learning algorithm in a convex game with monotone pseudo-gradient under the payoff information setting. The approach is based on a novel doubly regularized stochastic approximation scheme to deal with monotonicity and feasibility of actions; • We show that our algorithm satisfies a no-regret property, hence, providing to our knowledge the first no-regret algorithm, which, if employed by all players, converges to a Nash equilibrium; • We quantify the regret rate of our algorithm. In doing so, we provide an approach to tune the algorithm parameters to ensure fast learning quantified in terms of regret rate for each single player, and convergence to a Nash equilibrium, if employed by all players.
The rest of the manuscript is organized as follows. In Section 2 we formulate the problem and provide the background on a convex game with monotone pseudo-gradient. In Section 3 we present the algorithm. In Section 4 we derive conditions on the algorithm parameters to ensure convergence of the algorithm iterates to a minimum-norm Nash equilibrium. In Section 5 we formulate the online convex program solved by each player and quantify the regret rate of the algorithm. In Section 6 we show the simulation of the algorithm for two illustrative examples. We conclude in Section 7.

Notations
The set {1, . . . , N } is denoted by [N ]. Boldface is used to distinguish between vectors in a multidimensional space and scalars. Given N vectors vectors from R d with non-negative coordinates and Z + denotes non-negative whole numbers. The identity matrix in R d is denoted by I d . The standard inner product on R d is denoted by ·, · : The set of points within ρ distance of the boundary is denoted by The indicator function of the set Y is denoted by 1 y∈Y , which is equal to 1 if y ∈ Y and equal to 0 otherwise. The interior of the set Y is denoted by int(Y ). is considered a stable solution as it represents a joint action from which no player has an incentive to unilaterally deviate.

Background and problem setup
Our goal is to design an algorithm that learns a Nash equilibrium of the game based only on the payoff information.
Definition 2 The payoff-based information setting corresponds to a setting in which each player has no knowledge of her cost function or those of other players, the action sets of other players or their chosen actions. She can evaluate her cost function at a feasible joint action, that is, for every The problem we address here is design of an algorithm, so that if each player updates her strategy based only on the payoff information, synchronously with other players, the iterates of the algorithm converge to a Nash equilibrium of the game.
To ensure existence of Nash equilibria and to design a convergent algorithm, in this work we consider a class of convex games detailed below.

Nash Equilibria in convex games
Assumption 1 ∀i ∈ [N ] the set A i is convex and compact, the cost function J i (a i , a −i ) is defined on R N d , continuously differentiable in a, and convex in a i for fixed a −i .
Assumption 1 captures the most basic setting of a continuous action game and has been used in several past works to characterize and compute Nash equilibria [30]. Several applications satisfy these assumptions. For example, in mixed strategy extension of finite action games, the action sets are simplexes and hence, are compact and convex, whereas the cost function of each player is linear in her decision variable as it is the expected cost of her finite action cost given the probability of choosing actions. Further examples include Cournot games [25], games arising in wireless communication networks [33], electricity markets [6], electric vehicle charging [18], and route choices in transportation networks [8].
Our approach in designing a payoff-based algorithm lies in connecting Nash equilibria of the game Γ with the solution set of a variational inequality problem derived from the game. To state this connection, we first define the game pseudo-gradient and then discuss the variational inequality problem.
Definition 3 The game pseudo-gradient M : In words, the game pseudo-gradient is the stacked version of the gradient of each player's cost function with respect to her own decision variable. It is known (see [25]) that the Nash equilibria We denote this solution set by SOL(A, M ).

Monotonicity of the game pseudo-gradient
We consider a property on the pseudo-gradient map referred to as monotonicity.
The monotonicity condition is satisfied in a large class of games including those discussed in the previous section [30,6,18,33]. It is known that if the pseudo-gradient is strictly monotone then the game has at most one Nash equilibrium. Past works on using payoff-based algorithms to learn Nash equilibria in continuous action games have leveraged the strict monotonicity of pseudogradient [5,34]. In this paper, we consider convex monotone games, but only require monotonicity and not strict monotonicity.
Assumption 2 The game pseudo-gradient is monotone on A.
As an intuition for the monotonicity condition, if the cost functions J i : R N d → R are quadratic, then you can verify that the game pseudo-gradient would be an affine function in a, denoted by Ha + h, where H ∈ R N d×N d and h ∈ R N d . By evaluating the definition of monotonicity for the pseudo-gradient map Ha + h from 4, you can then verify that the strict monotonicity would correspond to the symmetric part of H, namely, H s = 1 2 (H + H T ) being a positive definite matrix whereas its monotonicity would correspond to H s being positive semi-definite 2 . Since the blockdiagonal entries of this matrix are the gradient of each player's cost function with respect to her own decision variable, observe that (strict) convexity of each player's cost with respect to her action is a necessary but not sufficient condition for (strict) monotonicity of the game pseudo-gradient.
Relaxing the strict monotonicity to monotonicity enables considering a larger class of games. This class includes non-strictly convex zero-sum game [10, page 22]. It is known that algorithms that converge under strict monotonicity may lead to cycles when applied to non-strictly monotone games [5] even in the simple zero-sum game of matching pennies (see Example 1). The class of non-strictly monotone games also includes non-zero-sum games (see Example 2). Furthermore, the variational equilibria (a subset of Nash equilibria) of convex games with linear coupling constraints can be described by solution set of an extended game with non-strictly monotone pseudo-gradient, see [10, 34, 24].

Examples
To illustrate non-strictly monotone convex games we consider two simple concrete examples.
Unlike strictly monotone games, non-strictly monotone games may have multiple Nash equilibria as shown in the following example.
Example 2 Consider a two-player non zero-sum game with A 1 = A 2 = [−1, 1] ⊂ R and J 1 (a 1 , a 2 ) = a 1 a 2 + 1 2 (a 1 ) 2 and J 2 (a 1 , a 2 ) = a 1 a 2 + 1 2 (a 2 ) 2 . The game pseudo-gradient is given by M (a 1 , a 2 ) = (a 1 + a 2 , a 1 + a 2 ) T , which is monotone but not strictly monotone as can be directly verified by the definition of monotonicity. Thus, the game satisfies Assumptions 1, 2. This game has a continuum of Nash equilibria. In particular, we can verify, using the relation (1), that a 1 = −a 2 is a Nash equilibrium, ∀a 1 ∈ A 1 . The minimum-norm Nash equilibrium is given by a 1 = a 2 = 0.

Proposed Learning Algorithm
The idea of the algorithm is that each player i estimates the gradient of its cost function J i at a played action a i using her payoff information J i (a i , a −i ). Then, player i performs a doubly regularized approximate gradient-descent, where the first regularization addresses non-strict monotonicity, Algorithm 1 Payoff-based learning of equilibria in non-strictly monotone games Require: Action set A i ⊂ R d , the sequences {σ t }, {ρ t }, {γ t }, {ǫ t }, initial state µ i (0). 1: for t = 0, 1, . . . do

2:
Sample ξ i (t) according to the probability density function defined in Equation (3).

3:
Obtain the feasible action a i (t) = Proj A i [ξ i (t)].

5:
Estimate the gradient of J i with respect to a i at point µ(t): and the second addresses feasibility of the iterates. We formalize this approach in Algorithm 1 described in Section 3.1. In Section 3.2 we comment on the assumptions leading to the desired properties of the gradient estimation procedure.

Payoff-based regularized learning
Let us denote by m i player i's estimate of the term M i in the pseudo-gradient of the game (see Definition 3). The proposed method to update the player i's so-called state of the algorithm µ i is as follows: where µ i (0) ∈ R N d is an arbitrary finite value, γ t is the step size, and ǫ t , ρ t are the two regularization parameters. The parameter ρ t is introduced to control the feasibility of the actions as will be detailed further, whereas ǫ t introduces a regularization to address the non-strictly monotone pseudo-gradient. The step size γ t needs to be chosen based on the bias and variance of the pseudo-gradient estimate m i , as well as the regularization parameters. The term m i (t) is obtained using the payoff-based feedback as described below.
Given µ i (t), let player i sample the random vector ξ i (t) according to the multidimensional normal distribution N(µ i (t) = (µ i 1 (t), . . . , µ i d (t)) ⊤ , σ t ) with the density function (3) . According to the payoff information setting under consideration, the cost value J i (t) at the joint action a(t) = (a 1 (t), . . . , a N (t)) ∈ A, denoted by J i (t) = J i (a(t)) is revealed to each player i. Taking into account that the procedure (2) updates the mean values µ i (t), we let each player i then estimates her local gradient M i evaluated at the point of the joint state µ(t) = (µ i (t)) N i=1 as follows: Putting these steps together, the procedure run by each player can be specified in Algorithm 1.
Remark 1 Player i can have her local choice of the parameters σ i

Gradient estimator properties
We denote by F t the σ-algebra generated by the random variables {µ(k), ξ(k)} k≤t . The following assumption is needed to bound the bias and variance of the gradient estimate based on the payoff information setting as defined in (4).
Assumption 3 We require the following behavior on the pseudo-gradient and the costs: 2. For each function J i the following holds: Remark 2 Due to the compactness of A, the pseudo-gradient M is bounded and Lipschitz continuous over A. Bounded and Lipschitz continuous gradients are standard assumptions in the literature on learning with payoff information information, see [5,34]. We additionally assume smoothness of the mapping M to be able to bound the approximation term arising due to the projection onto shrunk sets as will be discussed shortly. Part 2 of Assumption 3 addresses the unbounded Gaussian distribution employed in querying the actions. In particular, this assumption is used to upper bound the moments of the functions J i , i ∈ [N ], and those of their gradients in the proof of the main results, Theorems 1, 2.
The next lemma establishes the main properties of the gradient estimate defined in Equation (4).
for which Assumptions 1 and 3 hold. Choose σ t , ρ t such that lim t→∞ σ t = 0, lim t→∞ ρ t = 0, lim t→∞ ρt σt = ∞. Then the gradient estimate m i (t) introduced in Equation 4 can be decomposed as follows: where the stochastic terms Q i (t) and R i (t) satisfy We report the proof in Appendix A and provide some intuition here. The interpretation of the above result is that by using m i in the payoff-based algorithm, each agent can obtain an estimate of its gradient M i , with a bias term Q i and a zero mean noise term R i . These terms are further specified below.
Let us define the smoothed cost function for player i asJ i : is the joint probability density function. In other words,J i is the cost in mixed strategies, given the actions are distributed according to the density function in (3) (the time index t is omitted here to simplify the notation). Denote byM i (µ) : R N d → R N d the terms in the pseudo-gradient (see Definition 3) of the game with smoothed costs estimated at the point µ = (µ 1 , . . . , µ N )f , i.e., With simple addition and subtraction based on Equation (4) it is to verify that the terms in Equation (5) can be chosen as follows: Now, we can comment on the use of assumptions in establishing Proposition 1. The order of the variance in Part 2 of Proposition 1 can be established based on the Lipschitz continuity of the game pseudo-gradient M . Furthermore, Lipschitz continuity of M is used to bound term 1 in (8) relating the smoothed and original pseudo-gradients. As for term 2 in (8), observe that the projection of the states µ i (t) onto the shrunk set (1 − ρ t )A i ensures that we can bound Pr{ξ(t) ∈ R N d \ A} using concentration of the Gaussian distribution around its mean. This in turn together with smoothness of the pseudo-gradient M helps in establishing the bound for term 2 corresponding to the weighted difference between the cost evaluated at a(t) and ξ(t). In all steps mentioned above, part 2 of Assumption 3 is used to upper bound the moments of the cost function and its gradient. The variance and bias terms in Parts 2 and 3 of Proposition 1, are functions of σ t and, thus, can be controlled by appropriately choosing σ t . Furthermore, the order of these terms guide us in choosing the step size γ t and regularization terms ǫ t , ρ t to ensure convergence of the algorithm iterates. These choices are detailed in the next section.
Remark 3 One can choose to estimate the gradient by sampling the actions from the uniform distribution on a sphere, see Appendix A.4 for details. Such an approach has been used in [11] for bandit online learning and in [5] for learning Nash equilibria in strictly monotone games. Our choice of Gaussian distribution is inspired by stochastic sampling in [37,23] and lends itself to an alternative approach and analysis. In either case, the bias and variance of the estimates will be of similar order. Importantly, it is the order of these estimates that will be used in establishing convergence of the algorithm.

Convergence to a Nash Equilibrium
We demonstrate that under Assumptions 1-3, there exists a set of parameters such that the proposed payoff-based algorithm converges to the least-norm Nash equilibrium in the game Γ(N, In Section 4.1 we discuss the conditions on parameters putting them in perspective with regularized as well as with stochastic approximation procedures. In Section 4.2, we derive the proof of the result.
Assumption 4 Let the step size γ t , regularization ǫ t , variance σ t , feasibility radius ρ t , all be diminishing, that is, lim t→∞ γ t = lim t→∞ ǫ t = lim t→∞ σ t = lim t→∞ ρ t = 0, and satisfy Our main result on the convergence of iterates to a Nash equilibrium is as follows.
Theorem 1 Let the players in the game Γ(N, converges almost surely to a least norm Nash equilibrium a * , and the joint action a(t) converges in probability to a * .
We provide the proof in Section 4.2. Let us first provide intuition for the condition on the parameters and demonstrate that there exists choices of parameters that satisfy Assumption 4.

Discussion on algorithm parameters
First, we discuss the handling of the error due to approximating the pseudo-gradient m i using the payoff-based information. Notice that using one-point feedback we obtain a stochastic estimate of the gradient with bias and variance terms, as per Proposition 1. Thus, our algorithm can be interpreted as an analogue of a stochastic approximation procedure. Conditions 4), 5), 6) of Assumption 4 are standard in stochastic approximation [4]. In particular, ∞ t=0 γ t ǫ t = ∞ ensures the algorithm can make sufficient progress with time. On the other hand, ∞ t=0 γ 2 t σ 2 t < ∞ and ∞ t=0 γ t σ t < ∞ keep the perturbations caused by the stochastic nature of the algorithm under control, and are a consequence of the order of bias and variance terms derived in Proposition 1.
Condition 3) on the growth of ρ t relative to σ t arises due to requiring feasibility of actions during the learning and is used to bound term 2 in the bias defined in Equation (8) arising from projection of the actions on the feasible set (see discussion after Proposition 1). It is in particular a consequence of concentration of the Gaussian distribution around its mean.
Next, we discuss the conditions arising due to non-strict monotonicity of the pseudo-gradient. In particular, Conditions 1) and 2) allow for comparing the single time-scale regularized procedure with that of a double time-scale procedure. In this standard double time-scale approach [26] at each inner step V I((1 − ρ t )A, M + ǫ t I N d ) is solved, while ǫ t is decreased in the outer step. Moreover, Condition 2) (or its variant in Condition 2)* for the case of the interior least-norm Nash equilibria) arises as a bound we derive on the norm of the difference between the solutions of two variational This bound in turn is used to establish convergence of the algorithm by bounding the difference between our algorithm's iterates with the solutions of the above time-varying variational inequalities. As will be clarified (in the proof of Proposition 3 in the section), if the least-norm Nash equilibria belong to the interior of the set A, the convergent series ∞ t=0 |ǫt−ǫ t−1 | 2 ǫ 3 t γt is sufficient to bound this difference, resulting in Condition 2)*. Else, also convergence of the series ∞ t=0 |ρt−ρ t−1 | 2 ǫ 5+2ε t γt , which is related to the behavior of projection onto the shrunk sets, needs to be taken into account, resulting in Condition 2).
Finally, we can show that a sufficient condition for satisfying Assumption 4 is to choose the parameters as follows.
, 0 < g, e, s, r < 1. A sufficient condition for satisfying Assumption 4 is choosing g, e, s, r to satisfy the following set of linear inequalities: 2. e < r < s, g + e < 1, Moreover, if the interior int(A) of the set A is not empty and the least-norm solutions of V I(M , A) are contained in int(A), the first condition above is not needed.
The proof of the above lemma is based on the the convergence of a p-series and is provided in Appendix B.
The above conditions define a set of linear constraints with non-empty interior for the parameters. As an example of a set of parameters satisfying Lemma 1, one can pick (g, s, r, e) =

Proof of Theorem 1
The proof consists of three steps, summarized here.
Step 1 We first introduce the auxiliary sequence y(t) = (y 1 (t), . . . , y N (t)) ∈ R N d as the solution of the variational inequality V I((1 − ρ t )A, M (y) + ǫ t y), namely The standard Tikhonov sequence corresponds to the solution of the variational inequality above with the ρ t = 0 [25, Chapter 12]. We now establish a similar result to that of the standard Tikhonov sequence. See Appendix C for proof.
Proposition 2 Under Assumptions 2 and 3, y(t) defined in (10) exists and is unique for each t. Moreover, for ǫ t ↓ 0 and ρ t → 0 and given lim t→∞ ρt ǫt = 0, y(t) is uniformly bounded and converges to the least-norm solution a * of V I(A, M ).
Step 2 Next, consider the following regularized procedure where z 0 ∈ R N d is arbitrary. Letting µ(t) = (µ i (t)) N i=1 , observe that the iterates of our algorithm (2) can be written compactly as Thus, (11) is analogous to our iterates but with the exact pseudo-gradient. Our plan now is as follows. First, we show convergence of z(t) to y(t) and thus, concluding convergence of z(t) to the minimum-norm Nash equilibrium under a subset of conditions in Assumption 4. Next, in Step 3) below we show that under the additional stepsize assumptions, our iterates µ(t) converge to z(t) and hence, the minimum norm Nash equilibrium. In contrast to a double time-scale Tikhonov approach in [26,Chapter 12], z(t) is single timescale, that is, has no inner loop, and doubly regularized (by considering ǫ t and ρ t as regularization parameters). We establish convergence of the sequence z(t) to the least norm Nash equilibrium under a subset of the conditions in Assumption 4. See Appendix D for proof. The main idea in the proof is to leverage the result from [29, Lemma 10], provided in Appendix G for completeness. This lemma states almost sure convergence to 0 of a given non-negative sequence of random numbers a t , if this sequence satisfies the following condition: where ∞ t=0 α t = ∞, ∞ t=0 φ t < ∞, and F t is the σ-algebra generated by the random variables {a k } k≤t . Namely, we demonstrate that z(t+1)−y(t) 2 satisfies (13) with a t+1 = z(t+1)−y(t) 2 under the conditions of the proposition. To do so, we estimate the distance between z(t + 1) and y(t), taking into account (11) and the fact that y(t) = Proj (1−ρt)A [y(t) − γ t (M (y(t)) + ǫ t y(t))]. Using non-expansion of the projection operator and conditions of the proposition, we obtain z(t + 1) − y(t) 2 ≤ (1 − ǫ t γ t ) z(t) − y(t) 2 . Next, to get the inequality (13), we use the relation t 1 a i ∈∂A i for any ε > 0 (for the proof of the latter relation see Lemmas 8 and 9 in Appendix D. Finally, we obtain Inequality (13) as desired: Step 3 We now analyze µ(t)−z(t) 2 . We aim again to show that the relation (13) holds with a t = µ(t)− z(t) 2 and where F t , as before, is the σ-algebra generated by the random variables {µ(k), ξ(k)} k≤t . It then follows that lim t→∞ µ(t) − z(t) 2 = 0 almost surely. Finally, using Proposition 3 we conclude µ(t) converges to a least-norm Nash equilibrium.
Let us analyze each term in µ(t + 1) − z(t + 1) 2 = N i=1 µ i (t + 1) − z i (t + 1) 2 . From the procedures for the update of µ(t) and z(t) and the non-expansion property of the projection operator, we obtain where, for ease of notation, we have defined It follows that the terms in G i (t) 2 are given as Thus, accounting for the above, for Proposition 1, which implies E{R i (t)|F t } = 0 for any t, and for the Cauchy-Schwarz inequality, we get the following from Inequality (14): where in the last inequality we used M i (µ(t)) − M i (z(t)) 2 = O( µ(t) − z(t) 2 ) implied by Assumptions 1 and 3 and Remark 2. Next, by taking into account compactness of the set A and the properties of the terms Q i and R i (see Proposition 1), we conclude As the pseudo-gradient is monotone, From Thus, (13) holds and, thus, µ(t) − z(t) 2 almost surely converges to 0 as t → ∞. Next, by taking into account Proposition 3, we obtain that Pr{lim t→∞ µ(t) = a * } = 1, where a * is the least-norm Nash equilibrium in the game Γ(N, {A i }, {J i }). Finally, since σ t → 0, we can apply Portmanteau lemma [15] to conclude that a(t) convergence in probability to a * as desired.
Remark 4 The proof of Theorem 1 implies the rate with which the sequence µ(t) converges to z(t), by applying for example, Chung's lemma [7] to the inequality (15). Similarly, we can establish the convergence rate of z(t) to y(t) defined in (10). However, the rate at which y(t) converges to the least norm solution of the variational inequality V I(A, M ) can be obtained just for very specific settings such as linear mappings with "source representable" solutions, see [3, Chapter 5.8]. Thus, characterizing the rate with which µ(t) converges to the least norm Nash equilibrium a * is a challenging open problem.
Since we cannot characterize the rate at which the iterates converge to a Nash equilibrium for a given choice of the algorithm parameters, it is not obvious which setting of parameters satisfying Assumption 4 would be desirable in terms of convergence rate. In contrast, as will be shown in the next section, we can characterize the regret rate of the algorithm by appropriate choices of the parameters. This regret rate can guide players in choosing the algorithm parameters.

No-regret Property of the Algorithm
We first interpret the problem of learning under payoff-based information as an instance of online convex optimization. Next, we derive the regret rate of Algorithm 1 in Section 5.1. The proof of the results are provided in Section 5.2.
In an online convex optimization (or online convex programming), at every time step t, each player i selects an action a i (t) ∈ A i . After the vector is selected, the player receives the cost function . Thus, the player experiences a sequence of cost functions which are a priori unknown to her due to their dependence on the actions of other players. Let us denote this sequence by {J i 1 , . . . , J i t , . . .}, where J i t (·) = J i (·, a −i (t)), J i t : R d → R. Note that each J i t is a convex function on R d due to Assumption 1, and smooth due to Assumption 3.
In an online convex optimization, efficiency of the player i's performance is measured with respect to a regret function defined below.
Definition 5 Given an algorithm updating {a i (t)} with respect to an online convex programming problem a i (2), . . .} are the vectors selected by this algorithm, then the cost of the algorithm until time T is C i a (T ) = T t=1 J i t (a i (t)). The cost of a static reference point . The regret of the algorithm until time T with respect to any reference point a i ∈ A i is Note that we are measuring the performance of a i (t) against any reference action a i given the sequence of cost functions. Furthermore, consistent with the payoff information setup of the game, each player at each time t receives only the cost of the played action, J i t (a i (t)), as feedback, rather than the full cost function J i t (.) or its gradient. This setting is referred to as bandit online convex optimization [11,32].
The goal of an online optimization algorithm applied by the player i is to guarantee no-regret. That is, the average regret of the procedure should approaches zero: Furthermore, ideally, the rate of approach to zero should be as fast as possible.

Regret rate of the algorithm
We now demonstrate that Algorithm 1 corresponds to a no-regret learning for each player.
Theorem 2 Choose the parameters in Algorithm 1 as t r , with 0 < g, e, s, r < 1, and 1. r < s.

g − 2s > 0.
Then, under Assumptions 1-3, Algorithm 1 is no-regret for each player i with We report the proof details in Section 5.2. Let us now discuss the regret rate as a function of the algorithm parameters.
Observe that any parameters satisfying Assumption 4 and chosen based on the p-series conditions in Lemma 1 ensure the parameter conditions in the theorem above are satisfied. Hence, the algorithm converging to a minimum-norm Nash equilibrium is also no-regret.
Next, what choices of parameters above would optimize the regret rate? Below, we address this question.
Corollary 1 Let ε > 0 denote a small constant. Let the reference point in Definition 5 be a i .

Consider the reference point lying in the interior: a i ∈ int(A i ). The optimal regret rate is
Under the additional requirement of convergence of the actions a i (t) to a Nash equilibrium, the optimal regret is O 1 T 1/4−ε .
2. Consider the reference point lying on the boundary: a i ∈ ∂A i . The optimal regret rate is O 1 T 1/4−ε . Under the requirement of convergence to a Nash equilibrium, the optimal regret rate is O 1 T 3/20−ε .
Proof: The rates above are obtained by maximizing the minimum exponent of 1/T in (17) under the condition of Theorem 2, namely, 0 < g, e, s, r < 1, r < s, g − 2s > 0. For the rates pertaining to the Nash equilibrium convergence, additional conditions in Lemma 1 are accounted.
For the first statement in Part 1 of the lemma, the following choice of parameters g = 2/3 + ε, s = 1/6, e ≥ 1/3 provides the optimal rate of O 1 T 1/3−ε . For the second statement in this part, it can be verified that the set of parameters that optimize the regret rate and also satisfy Lemma 1 Parts 2, 3 pertaining to the interior Nash equilibrium are g = 3/4 + ε, s = 1/4, r = 1/4 − ε/2, e = 1/4 − ε, with ε any small positive constant.
For the first statement in Part 2 of the lemma, the term 1 T r in the regret rate (17) is active. In this case, once again it can be verified that g = 3/4 + ε, s = 1/4, r = 1/4 − ε/2, e = 1/4 − ε, with ε a small positive constant, achieves the lowest regret rate for the algorithm. On the other hand, for convergence to a Nash equilibrium, the more stringent condition in Part 1 is needed. It can be verified that such the set of parameters as g = 3/4 + ε, s = 1/4, r = 1/4 − ε/2, e = 3/20 − ε, with ε a small positive constant achieve the optimal regret rate. in [32]. We have been able to achieve this improved regret rate only for an interior reference point. Furthermore, requiring convergence to a Nash equilibrium worsens the regret rate of the algorithm in both interior and boundary Nash case. We believe the regret rate can be improved by considering more general class of learning algorithms.

Proof of Theorem 2
First, we connect the regret R i (T, a i ) with one estimated for the mean (state) vectors µ i (t), t = 1, 2, . . .. Let us introduce the following notation: Next, for any a i ∈ A i define the µ-regret R i µ (T, a i ) as follows: The lemma below connects R i µ (T, a i ) and R i (T, a i ).
Lemma 2 Choose the parameters σ t = 1 t s and ρ t = 1 t r with 0 < s, r, r < s. Then, under Assumption 3 1), We refer the reader to Appendix E for the proof of the lemma above. Now we focus on the estimation of the expected value of the µ-regret, namely ER i µ (T, a i ), for the procedure defined by Algorithm 1. Due to definition of Q i in Equation (8), the procedure (2) for each player i can be rewritten as follows: where is the term 2 in the definition of Q i (see (8)). Taking into account Lemma 4 in Appendix A, we conclude that almost surely Next, let the functionJ i t,µ be defined as follows: where p k (x) denotes the density function of the random variable ξ k defined in Equation (3). Then (19) can be written as where we used Equations (7) and (21) to get Next, we provide a result connecting the function J i t,µ (µ i ) with its mixed strategy versionJ i t,µ (µ i ).
Lemma 3 Under Assumption 1 and Part 1 of Assumption 3, the functionsJ i t,µ : R d → R enjoy the following properties: 1.J i t,µ , t = 1, . . ., are convex on R d and their gradients ∇J i t,µ are bounded over A.
2. The deviation between the smooth costJ i t,µ and original cost J i t,µ can be bounded as Note that Lemma 3 has been derived in [23] for the Gaussian smoothing and in [2] in the case of the smoothing technique based on the uniform distribution over the unit sphere. We provide a proof in Appendix F for completeness. We now proceed further with the proof of Theorem 2. Let us consider any a i ∈ ∂A i . Then, Due to the compactness of A i and smoothness ofJ i t,µ as per Lemma 3 Part 1,J i t,µ is Lipschitz continuous over A and, thus, for some positive constantL i . Furthermore, taking into account that for any a i ∈ A i (see Lemma 7 in Appendix D for an analogous proof) On the other hand, if a i / ∈ ∂A i , let us choose ρ t such that for all t we have a i ∈ (1 − ρ t )A i and, thus, a i = Proj (1−ρt)A i a i . Hence, we can rewrite Equation (24) as follows: Moreover, due to Lemma 3 the functionJ i t,µ defined by Equation (21) is convex on A i for any t. Thus, for any Finally, due to the fact that |J i t,µ (a i ) −J i t,µ (a i )| = O(σ 2 t ), ∀a i ∈ A i , (see Lemma 3 Part 2, we obtain Thus, given any reference point a i ∈ A i , in view of Inequalities (25), (26), and (27), we can write We focus further on the term ∇J i t,µ (µ i (t)), µ i (t) − Proj (1−ρt)A i a i . In the following analysis, for the sake of presentation clarity, we use the following notations: Proj (1−ρt)A i a i = a i P,t . Due to non-expansion of the projection operator and Equation (22), we get for any a i ∈ A i Thus, taking into account the properties of the term R i (t) from Proposition 1, boundedness of ∇J i t,µ (µ i (t)) from Lemma 3 1), and (20), we obtain, given r < s, Hence, by taking the full expectation of the both sides and rearranging the terms, we get By summing up the left and the right hand side over t and taking into account that Thus, due to Inequality (28), Finally, applying Lemma 2, we obtain the result.

Simulation of the examples
We illustrate the performance of the algorithm by addressing Examples 1 and 2 from Section 2.2. For comparison, we plot the iterates of the payoff-based mirror-descent algorithm of [5], herein referred to as the mirror-descent algorithm as a benchmark. This algorithm is closest to our setting since it can also be implemented using payoff-based information, ensures feasibility of actions and is no-regret. However, note that in general no-regret online algorithms proposed for strictly monotone games, such as the mirror-descent algorithm above, do not have provable convergence to Nash equilibria in the non-strictly monotone settings here. Figure 1 illustrates the iterates of the mirror-descent algorithm (top panels) and the proposed algorithm (bottom panels) for Example 1. We see that the mirror-descent algorithm does not converge while Algorithm 1 is converging to the unique Nash equilibrium. Figure 2 illustrates the iterates of the above two algorithms for Example 2. Here, we see that the mirror-descent algorithm converges to a Nash equilibrium but not necessarily the minimum norm one (the particular Nash equilibrium it converges to seems to be dependent on the initial condition of the iterates). Our proposed algorithm converges to the minimum-norm Nash equilibrium as predicted by Theorem 1.
For both examples, we set the parameters of our algorithm according to Corollary 1 Part 1 to minimize the regret rate while satisfying the conditions derived in Lemma 1 Parts 2, 3 corresponding to a Nash equilibrium in the interior of the feasible set, namely, (g, s, r, e) = (.76, .25, .24, .23). We set the parameters p, q of the mirror-descent algorithm (see Theorem 5.1 and 5.2 in [5]) as p = 1, q = 1/3 to achieve the fastest rate for convergence to the Nash equilibrium in case of strictly monotone pseudo-gradient 3 .
Finally, we consider the game of Example 1, but with the strategy sets reduced to A 1 = A 2 = [1/2, 1]. It can be verified that for any a 2 > 1/2, the strategy (1/2, a 2 ) is a Nash equilibrium. The least-norm Nash equilibrium is (1/2, 1/2). Since the Nash equilibria lie on the boundary of the feasible set, we set the parameters of our algorithm according to Corollary 1 Part 2 to minimize the regret rate while satisfying the conditions derived in Lemma 1, namely, (g, s, r, e) = (.76, .25, .24, .12). Figure 3 illustrates the iterates of the algorithms for this case. We observe the convergence of our algorithm's iterates to the least-norm Nash equilibrium. Once again, we observe that the mirror-descent approach also converges to a Nash equilibrium but not to the least-norm one.

Conclusions
We derived a payoff-based algorithm to learn Nash equilibria in convex games with monotone pseudo-gradients. Our approach introduced two regularization: the first addressed the non-strictly monotone pseudo-gradients and the second addressed feasibility of queried actions. We furthermore established that the procedure is no-regret and quantified its regret rate based on optimal choices of the algorithm parameters. Our work open up some directions for future research. First, addressing the rate of convergence of the algorithm to a minimum-norm Nash equilibrium as a function of parameters is an open challenge. Second, the regret rate established under the requirement of convergence to Nash equilibrium appears suboptimal to us. There is a need to explore other convergent algorithms or analysis approaches that could potentially improve this regret rate.

A Proof of Proposition 1
First, let us derive the terms Q i , R i defined in Equation (5). Consider the gradient estimation in (4). Let p(x; µ, σ) = N i=1 p i (x i 1 , . . . , x i d ; µ i , σ) denote the density function of the joint distribution of the agents' sampling variables (ξ 1 , . . . , , is the i-th player's cost function in mixed strategies, namelỹ This mapping is the pseudo-gradient corresponding to the game with mixed strategy cost functions J i defined in (32). Next, observe that for all i ∈ [N ] we can equivalently write m i (t) defined in (4) as where Q i and R i are defined as With the definitions of Q i and R i in place, we proceed with establishing the properties of the stochastic terms Q i (t) and R i (t) as stated in parts 1-3 in the following three sections.

A.1 Part 1 of Proposition 1
Lemma 4 Under Assumption 1 Proof: For Part 1, we verify that the differentiation under the integral sign iñ is justified. It can then readily be verified that the statement 2 holds, by taking the differentiation inside the integral. A sufficient condition for differentiation under the integral is that the integral of the formally differentiated function with respect to µ i k converges uniformly over the domain set of the parameter µ i k , whereas the differentiated function is continuous (see [39,Chapter 17]). Continuity of the functions J i (x)p(x; µ, σ) and ∂J i (x)p(x;µ,σ) follows from continuity of J i (x) and p(x; µ, σ). We demonstrate uniform convergence of the integral we can apply the Hölder's inequality to conclude that Next, According to Assumption 3 Part 2, there exists the constants c such that for any x ∈ R N d and µ ∈ A. Thus, taking into account that we conclude the uniform convergence over A follows from (37) and the fact that converges uniformly over A i according to Dirichlet's test for uniform convergence of integrals. Note that, as a consequence of the above lemma, E{R i (t)|F t } = 0 for all i and any t and thus, part 1 in Proposition 1 is proven. Furthermore, we can see that the term R i (t) can be interpreted as a zero mean noise term in the gradient estimation. This implies that the expression is an unbiased one-point estimation of the gradient of the agent i's cost function in mixed strategies,J i , with respect to her decision variable.

A.2 Part 2 of Proposition 1
From the definition of R i in (36), notice that (38) Next, according to the Hölder's inequality (E|XY | ≤ (E(X 2 )) 1/2 (E(Y 2 )) 1/2 ), we have where in the inequality above for the safe of notation simplicity we used E{·} = E{·|ξ(t) ∼ (µ(t), σ t )}. We continue analysing the term E{J i 4 (ξ(t))}: According to Assumption 3 Part 2, there exists the constants C such that for any t, x ∈ R N d , and µ ∈ A. Thus, taking into account that

A.3 Part 3 of Proposition 1
Recall the definition of Q i in (4). We address proving this part of the proposition by first bounding the last term (J i (a(t)) − J i (ξ(t))) ξ i (t)−µ i (t) σ 2 t in the biased bias term Q i (t). Our next lemma bounds the norm of this bias term in terms of ρ t and σ t .
where the second equality above is due to the fact that Proj A x = x for any x ∈ A. The first inequality was obtained by taking into account that |J i (Proj A x) − J i (x)| 2 ≤ 2(J i (Proj A x)) 2 + 2(J i (x)) 2 , whereas the last one is due to the inequality (J i (Proj A x)) 2 ≤ K for some constant K and any x (since A is compact and J i is continuous). Thus, let us estimate Pr{ξ(t) ∈ R N d \ A} above. The idea is that since ξ(t) is sampled from the Gaussian distribution with mean µ(t), ξ(t) concentrates around its mean µ(t) with high probability. Since the mean is projected onto a shrunk version of the set A, namely, (1 − ρ t )A, by appropriately tuning ρ t and the variance of the distribution σ t we can ensure that ξ(t) stays within the original feasible set with high probability.
Then, taking into account the fact that O ρt (x) is contained in A and ρ t < 1, we obtain that for any t and any bounded σ > σ t : for some finite k 1 > 0. The last inequality holds because and, thus, due to the diminishing ρ t there exists 0 < k 1 < ∞: Taking into account Assumption 3 2, we conclude existence of some constant C 1 such that Hence, analogously to (44), we have where the last inequality is due to the fact that From Lemma 5, it follows that the second term of Q i defined in (35) converges to zero exponentially fast as lim t→∞ ρt σt = ∞. We proceed with bounding the first term in (35). Taking into account Assumption 3 Part1 and the mean value theorem, we have where ∇M i (x) is the gradient of the vector function M i at the pointx = x + θ(µ(t) − x) with θ ∈ [0, 1] being a constant dependent on x and µ(t). Next, applying the Hölder's inequality to (46) and using the notations E{·} = E{·|ξ(t) ∼ (µ(t), σ t )} andξ = ξ + θ(µ(t) − ξ), we obtain where the last equality is due to the fact that the first central absolute moment of a random variable with a normal distribution N(µ, σ) is O(σ). Taking into account Assumption 3 Part 2 we can conclude that ∇M i (x) 2 = O(exp{ x α ′ }) as x → ∞, where α ′ < 2. Hence, analogously to (40), we can demonstrate existence of some constant C 1 such that E{ ∇M i (ξ) 2 } ≤ C 1 . Thus, (47) implies the result.

A.4 Uniform Distribution for Gradient Estimation
Let the agent i sample the random vector ξ i (t) according to the multidimensional uniform distribution over the unit sphere. Then the action the agent i chooses is a i (t) = µ i (t) + σ t ξ i (t), where σ t is some time dependent parameter. As before, the cost value J i (t) at the joint action a(t) = (a 1 (t), . . . , a N (t)) ∈ A, J i (t) = J i (a(t)) is revealed to each agent i. Based on this information, the agent i estimates the local gradient ∂J i ∂µ i at the point of the joint state µ(t) = (µ 1 (t), . . . , µ N (t)) as: We note that ensuring the feasibility of actions as well as the properties of the terms Q i and R i in the case of the estimations based on the uniform distribution in (48) are investigated in the works of [11], [5]. In particular, as shown in [5, Section 4] the gradient estimator has the same order of variance and bias as those derived in Proposition 1.

B Proof of Lemma 1
Proof: The series ∞ t=0 1/t p converges for p > 1 and diverges otherwise. Thus, it is trivial to verify all statements for Assumption 4, except Part 2. To show the condition for that part, let us consider the term (ǫ t − ǫ t−1 ) 2 in the first summand of Part 2, namely, ∞ t=0 Combining the above with the denominator ǫ 3 t γ t , we obtain that ∞ t=0 (ǫt−ǫ t−1 ) 2 ǫ 3 t γt converges if g + e <

Repeating the same analysis for
Thus, Part 2 is verified.

C Proof of Proposition 2
We use the following well-established result, see, for example, [25].
Lemma 6 Consider a mapping T (·) : R d → R d and a convex closed set Y ⊆ R d . Given θ > 0, y * ∈ SOL(Y, T ) ⇐⇒ y * = Proj Y (y * − θT (y * )). (49) Proof: The proof is motivated by the work on solving monotone stochastic variational inequalities [16]. In contrast to the above work, we have an additional regularization term ρ t . This regularization arises because we need to estimate the gradient using zero-order information at feasible points of the action set. Let a * be the least-norm solution of V I(A, M ). Moreover, let a p be the projection of a * onto the set (1 − ρ t )A. Next, let y(t) be the unique solution of the doubly regularized inequality, namely y(t) ∈ SOL((1 − ρ t )A, M + ǫ t I N d ). Thus, we conclude that M (a * ), y(t) − a * ≥ 0, M (y(t)) + ǫ t y(t), a p − y(t) ≥ 0.
Using the above two inequalities we obtain that 0 ≤ M (a * ), y(t) − a * + M (y(t)) + ǫ t y(t), a * − y(t) + M (y(t)) + ǫ t y(t), a p − a * = − M (a * ) − M (y(t)), a * − y(t) + ǫ t y(t), a * − y(t) + M (y(t)) + ǫ t y(t), a p − a * ≤ǫ t y(t), a * − ǫ t y(t) 2 + M (y(t)), a p − a * + ǫ t y(t), a p − a * , where in the last inequality we took into account monotonicity of M , Hence, where in the first inequality we used Remark 2 and in the second one we applied Lemma 7. Hence, By taking the upper limit as t → ∞ above and due to the settings for ǫ t and ρ t , we obtain lim t→∞ [ y(t) 2 ] ≤ a * lim t→∞ y(t) + lim t→∞ y(t) lim t→∞ O(ρ t ).
It implies that lim t→∞ y(t) ≤ a * , and, thus, the sequence y

D Proof of Proposition 3
Our goal is to establish z(t) defined in (11) converges to y(t). Then, from Proposition 2 we can establish convergence to a Nash equilibrium for the sequence z(t).
First, let us focus on proving the above lemma by establishing some useful properties of projecting onto the sets (1 − ρ t )A.
Lemma 7 For any x ∈ R N d the following holds: Proof: Without loss of generality, assume x / ∈ (1−ρ t−1 )A (otherwise, Proj (1−ρ t−1 )A x−Proj (1−ρt)A x = 0). Due to convexity of the set A ⊂ R N d there exists a convex function g : R N d → R such that A = {x : g(x) ≤ 0}, so that (1 − ρ t )A = {x : g(x) ≤ −ρ t } for any t. Moreover, define x ′ := Proj (1−ρt)A x, and observe that Proj ( where d is the optimal cost corresponding to the following optimization problem The optimization problem has a solution y * for which the gradient of the corresponding Lagrangian is zero, namely where λ > 0 is the dual multiplier of the problem under consideration. Due to Assumption 1 and the choice of ρ t , that guarantees nonempty interior of (1 − ρ t )A for all t, the Slator's condition for the constraints g(x) ≤ −ρ t holds for all t. Hence, for any x ∈ R N d there exists a constant Λ > 0 such that λ < Λ (see [12]). Thus, we conclude that Next, due to convexity of the function g, g(x ′ ) ≥ g(y * ) + (∇g(y * ), x ′ − y * ) = −ρ t−1 + y * − x ′ 2 λ y * − x ′ ≥ −ρ t−1 + y * − x ′ Λ .
With the above lemma in place, we proceed one step closer to prove Proposition 3. Our approach for this proof is to bound z(t + 1) − y(t) by the previous terms in the sequence, namely, z(t) − y(t − 1) and apply a well-established lemma on convergence of a random sequence, namely, [29, Lemma 10, page 49] (see Theorem 3 provided in Appendix G). To do so though, first we need to bound the variations of y(t) as below.
We consider ω t such that ω t < ǫ t .
Lemma 9 Assume that the interior of the set A, int(A), is not empty and the least-norm Nash equilibria are contained in int(A). Then under Assumptions 1 and 3, the Tikhonov sequence y(t) defined in (10) satisfies for all sufficiently large t.
Proof: Let a * ∈ int(A) be the least-norm Nash equilibrium which is the limit of the sequence y(t) (see Proposition 2). As a * ∈ int(A), we conclude existence of R > 0 such that the ball B R (a * ) with the center at a * and the radius R is contained in the set A, i.e. B R (a * ) ⊆ A. Thus, dist(a * , ∂A) ≥ R, where dist(x, ∂A) denotes the distance between the point x and the boundary ∂A of the compact set A. Moreover, as lim t→∞ y(t) = a * , there exists such T R that for all t ≥ T R we have y(t)−a * ≤ R 2 . Thus, due to the triangle inequality dist(a * , ∂A) ≤ y(t) − a * + dist(y(t), ∂A), we obtain dist(y(t), ∂A) ≥ dist(a * , ∂A) − y(t) − a * ≥ R 2 for such t ≥ T R . Hence, for such t for all ρ < R 2 . As ρ t → 0 there exists T ρ such that ρ t < R 2 . Next, let T = max(T R , T ρ ). Then for all t > T and all t ′ > T we have In words, there exists a finite time T after which the sequence y(t) is contained in the set (1−R/2)A. This set, in its turn, is contained in the shrunk sets (1−ρ t ′ )A for any t ′ > T . Hence, for any t > T +1 we conclude that y(t) ∈ (1 − R/2)A ⊆ (1 − ρ t−1 )A and, thus, (M (y(t − 1)) + ǫ t−1 y(t − 1), y(t) − y(t − 1)) ≥ 0, (M (y(t)) + ǫ t y(t), y(t − 1) − y(t)) ≥ 0.
By repeating the Part 1 of the proof of Lemma 8, we conclude the result.
We proceed with estimating E{J i (ξ(t)) − J i (µ(t))|F t }: where p = N i=1 p i and p i is defined in (3) andμ = µ + θ(x − µ), for some θ ∈ [0, 1] given x and µ, and ∇ 2 J i (μ) is the Hessian matrix of the function J i at the point (which exists according to Assumption 3 1). The first inequality above is obtained by the mean value theorem (which is applicable again according to Assumption 3 1) and the second one is due to the definition of the density function p implying R Nd (∇J i (µ), x − µ)p(x; µ, σ t )dx = 0.
By applying the Hölder's inequality and the boundedness of the integral R Nd ∇ 2 J i (μ) x − µ 2 p(x; µ, σ t )dx from Assumption 3 Part 2 (see (40) for an analogous result), we obtain Next, to address E{J i (a(t)) − J i (ξ(t))|F t } in (53), repeating the proof of Lemma 5 we obtain Thus, bringing the inequalities (53), (55), (56) together, and taking the full expectation, we conclude the result due to the condition σ t = 1 t s , ρ t = 1 t r , with 0 < g, e, s, r, r < s.

F Proof of Lemma 3
Proof: Part 1: To show convexity ofJ i t,µ consider µ i 1 , µ i 2 ∈ A i , a 1 , a 2 ∈ R. From the definition ofJ i t,µ (see (21)) and definition of p j in (3), we havẽ