No-Regret Learning in Strongly Monotone Games Converges to a Nash Equilibrium
Authors: Zifan Wang
Yi Shen
Michael Zavlanos
Karl Henrik Johansson
Venue: Submitted to ICLR 2023 (2023)
Keywords: Online game
no-regret learning
Nash equilibrium convergence
monotone game

Abstract: This paper studies a class of online games involving multiple agents with continuous actions that aim to minimize their local loss functions. An open question in the study of online games is whether no-regret learning for such agents leads to a Nash equilibrium. We address this question by providing a sufficient condition for strongly monotone games that guarantees Nash equilibrium convergence in a time average sense. Furthermore, we show that the class of games for which no-regret learning leads to a Nash equilibrium can be expanded if some further information on the learning algorithm is known. Specifically, we provide relaxed sufficient conditions for first-order and zeroth-order gradient descent algorithms as well as for best response algorithms in which agents choose actions that best respond to other players' actions during the last episode. We analyze the convergence rate for these algorithms and present numerical experiments on three economic market problems to illustrate their performance.


Under review as a conference paper at ICLR 2023
NO-REGRET LEARNING IN STRONGLY MONOTONE GAMES CONVERGES TO A NASH EQUILIBRIUM
Anonymous authors Paper under double-blind review
ABSTRACT
This paper studies a class of online games involving multiple agents with contin- uous actions that aim to minimize their local loss functions. An open question in the study of online games is whether no-regret learning for such agents leads to the Nash equilibrium. We address this question by providing sufficient condition for strongly monotone games that guarantees Nash equilibrium convergence in time average sense, regardless of the specific learning algorithm, assuming only that it is no-regret. Furthermore, we show that the class of games for which no-regret learning leads to Nash equilibrium can be expanded if some further information on the learning algorithm is known. Specifically, we provide relaxed sufficient conditions for first-order and zeroth-order gradient descent algorithms well for best response algorithms in which agents choose actions that best respond to other agents' actions during the last episode. We analyze the convergence rate for these algorithms and present numerical experiments on three economic market problems to illustrate their performance.
INTRODUCTION
Online convex optimization (Hazan et al.) 2016 Shalev-Shwartz et al., 2012) is used to solve decision-making problems where the cost function is unknown and optimal actions are selected with only incomplete information. Recently, online convex optimization has also been employed for the solution of games involving multiple agents with applications ranging from traffic routing
(Sessa et al. 2019) to economic market optimization (Narang et al. 2022] Wang et al. 2022, Lin al. 2020). In these online convex games, agents simultaneously take actions to minimize their loss functions, which depend on the other agents' actions.
Generally, agents in non-cooperative games have access to limited information. For example, they may not be able to observe the actions of other agents and may not even know the exact game mechanism. As a result, rational agents will focus on sequentially learning their individual optimal actions at the expense of other agents, and their ability to do so efficiently notions of regret that captures the cumulative loss of the learned online actions compared to the best actions in hindsight. An algorithm is said to achieve no-regret learning if the regret of the sequence of online actions generated by this algorithm sub-linear in the total numbers of episodes T. While no-regret learning has been studied for variety of games; see e.g., Sessa et al. (2019): Tatarenko & Kamgarpour (2018): Wang et al. (022)); Daskalakis et al. (2021) Anagnostides et al. (2022), the analysis of regret alone not sufficient characterize the limit points of learning algorithm, i.e., the sequence of actions taken by the algorithm. In fact, no- no-regret learning may not converge at all and can exhibit limit cycles, as shown in Mertikopoulos et al. (2018).
be quantified using
In this paper, we adopt the notion of a Nash equilibrium, that describes a stable point at which the agents have no incentives to change their actions, analyze the convergence properties of no-regret algorithms for online convex games. A growing literature has recently focused on showing Nash equilibrium convergence for online games; see, e.g., Bravo et al. (2018); Tatarenko & Kamgarpour (2000); Drusvyatskiy & Ratlifi ()02 Lin et al. (2021) 2020); Mertikopoulos & Zhou (2019);
Narang et al. (2022); Heliou et al. (2017): Golowich et al. (2020) Azizian et al. (2020). For example, for potential games with finite actions, Heliou et al. (011)) show that the sequence of play returned
by the exponential weight algorithm converges to the Nash equilibrium. On the other hand, for
games with continuous actions, strong monotonicity, which ensures the uniqueness of the Nash

---

Under review as a conference paper at ICLR 2023
equilibrium (Rosen 1965). is sufficient condition for Nash equilibrium convergence for many specific learning algorithms, including the mirror descent algorithm (Bravo et al. 2018 Lin et al, 202I), the dual averaging algorithm (Mertikopoulos & Zhou, 2019) and the derivative- free algorithm (Drusvyatskiy & Ratlif [021]] Narang et al., 2022). Besides, an optimistie gradient algorithm is proposed in Golowich et al. (2020) that achieves tight last-iterate convergence for smooth monotone games, Similarly, Lin et al. (2020) investigate the last-iterate convergence for continuous games with unconstrained action sets that satisfy a so-called 'cocoercive' condition that includes a broader class of games with potentially many Nash equilibria. However, all these works analyze the convergence and/or regret for specific learning algorithms and for assumptions that depend on this specific choice of algorithms and games.
In this paper, we follow a different approach and instead focus on understanding for what classes of games and learning algorithms Nash equilibrium convergence can be guaranteed. Specifically, we are interested in understanding whether and for what class of online convex games with continuous action sets no-regret learning converges to a Nash equilibrium regardless of the specific algorithm. Moreover, we are interested in understanding whether and how this class of online convex games can be expanded when the no-regret learning algorithm is known.
In our main result, we show that for m-strongly monotone games with parameter m > 2T.V 1, where I. is a Lipschitz constant of the gradient function with respect to the actions of other agents, and N is the number of agents, any no-regret algorithm leads to Nash equilibrium convergence. While Nash equilibrium convergence has been analyzed for different combinations of learning algo- rithms and games, to the best of our knowledge, this is the first effort to understand for what classes of games and learning algorithms Nash equilibrium convergence can be guaranteed, and thus bridge regret analysis with Nash equilibrium convergence in games. We note that this result applies to any no-regret algorithm and thus can provide theoretical support for the convergence of any such algorithm for which regret analysis is easy but Nash equilibrium convergence is difficult to show. Furthermore, we show that the class of games > 2L - I can be expanded if additional infor- mation about a specific no-regret algorithm is known. First, for the class of gradient- descent (GD) algorithms including first-order and zeroth-order orddr algorithms, we show that m > 0 is sufficient condition for Nash equilibrium convergence. Note that Drusvyatskiy & Ratliff (202T) also show convergence of the zeroth-order algorithm to Nash equilibrium, but with the additional assump- tion that the Jacobian of the gradient function is Lipschitz continuous which they need to ensure that the smoothed game induced by the zeroth-order oracle is strongly monotone. In this work, we show that this assumption is not necessary and Nash equilibrium convergence can still be guaran- teed even when the smoothed game is not strongly monotone. In addition, we study the class of the best response algorithms, where every agent selects the best action in the next episode given the other agents' current actions. Best response algorithms have been studied for several classes of games, including potential games (Swenson et al. 2018 Durand & Gaujal 2016) and zero-sum games (Leslie et al., 2020). However, none of these works study games with continuous actions or provides sufficient conditions that guarantee convergence to Nash equilibrium. We show that for m-strongly monotone games, the best response algorithm ensures Nash equilibrium convergence m > LVN I. This is, to the best of our knowledge, the first convergence analysis of the best response algorithm in continuous games.
We numerically validate the proposed algorithms using three online marketing examples, specifi- cally the Cournot game, the Kelly auction, and the Retailer pricing competition, that satisfy different conditions on the parameter m and, therefore, belong to different game classes. We show that for games that do not satisfy the sufficient condition m > Lv/N- - 1, such as the Cournot game, the best response algorithm may diverge. As a result, gradient descent algorithms may be better suited to solve games in this class. We also compare the performance of these algorithms for games for which Nash equilibrium convergence best response algorithm outperforms first-order gradient descent which, in turns, outperforms the zeroth-order method. On the other hand, when 0 < m < LVN-I, first-order gradient descent outperforms the zeroth-order method. summary, by defining sufficient conditions for Nash equi- librium convergence that depend only on the properties of the game, i.e., the parameter m. and not the learning algorithm used to solve it, our analysis allows to identify classes of games for which no-regret learning guarantees convergence to a Nash equilibrium without analyzing specific algo- rithms or identify specific no-regret learning algorithms with no guaranteed convergence to a Nash equilibrium, both fundamental questions in the analysis of online convex games.
guaranteed. We observe that when m > Lv/N - 1, the
2

---

Under review as a conference paper at ICLR 2023
The rest of the paper is organized follows. In Section 2 define the online convex games under consideration and provide some assumptions. The main result is presented in Section where provide sufficient conditions on the class of games for which no-regret learning leads Nash equilibrium convergence. In Sections 4 and we study two specífic classes of no-regret learning algorithms and show that the classes of games for which Nash equilibrium convergence can be guaranteed can be expanded if the algorithm is known. In section 6 examples validate the proposed algorithms and conditions. We conclude this work in Section 7
we use three online marketing
PROBLEM DEFINITION
Consider an online convex game with N agents, whose goal is to learn their best individual ac- tions that minimize their local loss functions. For each agent i E N {I..... N]. denote by (==) + the individual loss function, where x; E X, the action of agent i, x- are the actions of all agents except for agent i, and we define X' n 1 K to be the joint action space since each agent takes actions independently. For ease of notation, we collect all agents' actions in vector := (#1...... ZNN) ). We assume that (x(x) is convex in z; for all z X-j. where X_, is the joint action space excluding agent i. In addition, we assume that the diameter of the convex set X; is bounded by D, for all i ,,...,N.. N. The goal of every agent i is to determine the action x; that minimizes its individual loss function, i.e.
min C(x,, EEE;;
(1)
As shown in Rosen (1965), convex games always have at least one Nash equilibrium. In what follows, we denote by x a Nash equilibrium the game (I) Then, for each agent i, we have C((=") C,(,,,=",,, Va, X, N. At this Nash equilibrium point, agents are strategically stable in the sense that each agent lacks incentives to change its action. Since the agents' loss functions are convex, the Nash equilibrium can also be characterized by the first-order optimality condition, i.c., (V,,C(<")) - 2 O, Vr, E X,, i E N,, where V (x() is the partial derivative of the loss function with respect to each agent' action. We write V,C,(x) instead of c. whenever it is clear from the context. Throughout the paper, we make the following assumptions on the convex loss functions.
Assumption 1. For each agent we have that (x) is Lo -ipschitt continuous in x and (C,( U.
Assumption 2. For each agent i, we have that v.C,() is Li-Lisschitz continuous in x and [[VC(( < B.
The above assumptions are very common in the literature and hold in many applications, e.g.. Cournot Games, retailer pricing games; see Bravo et al. 2018); Duvocelle et al. (2018); Lin et al. (2021).
In general. it is not easy to show convergence to a Nash equilibrium for games with multiple Nash Equilibria. For this reason, recent studies often focus games that are so-called strongly monotone and are well-known to have a unique Nash equilibrium (Rosen) 1965). In this case, convergence the Nash equilibrium is shown, e.g., in Drusvyatskiy & Ratlifi (202]) Bravo al, (2018). The game (1) is said to be m-strongly monotone if for Va, x E X we have that
Σ -VCC(()-V.C(())))
x m 1 2'112.
The ability of the agents to efficiently learn their optimal actions can be quantified using the notion of regret that captures the cumulative loss of the learned online actions compared to the best actions in hindsight, and can be formally defined as
Reg,
Ea(x)) min Σ c(
d for sequences of actions {a.,)] 1 I,..., N. An algorithm is said to be no-regret if the regret of each agent is sub-linear in the total number of episodes T, i.e., Reg, O(T)), (0, vi E N.
3

---

Under review as a conference paper at ICLR 2023
In this work, interested in understanding for what classes of games and learning algorithms Nash equilibrium convergence can be guaranteed. Specifically, we are interested in understanding whether and for what class of online convex games with continuous action sets no-regret learning converges to a Nash equilibrium regardless of the specific algorithm; see Section 3 Moreover, we interested in understanding whether and how this class of online convex games can be expanded when the no-regret learning algorithm is known; see Sections 4
and
3 NO-REGRET LEARNING CONVERGES TO A NASH EQUILIBRIUM
In this section, we provide our main result which shows that any no-regret learning algorithm can guarantee Nash equilibrium convergence for the class of m-strongly monotone games that satisfy an additional condition on the parameter m. We start with single-agent learning and then extend it to multi-agent games.
3.1 SINGLE-AGENT LEARNING
Consider single agent whose goal is to minimize its convex loss function C(x) by optimizing its action x E X. Let x = argmin, C(x). Suppose that an online algorithm generates a sequence {o:)/_11 and the regret is defined as Reg = Σt= C(x²) - C(x*). In the following lemma, we show that strong convexity of the loss function C(x) guarantees that no-regret learning leads to Nash equilibrium convergence.
Lemma 1. Suppose that the loss function C(x) is m-strongly convex in with the parameter
m > O. If the regret is sub-linear in T such that Reg O(T)) with a E [0, 1), then we have EL |0 - x=1 = ((T)).
Proof. The strong convexity of the loss function C(x) implies that C(x) C(x*) 2 m 1|a-=*1] x²I'
Vz X. Substituting in this inequality the agent's action xe at time and summing over I, obtain that Reg- Σ (C(x:) C(x*)) 2 7 Σr || -=11² The result follows by the fact that m is a constant that does not depend on T.
2
Lemma shows that no-regret learning for single-agent learning guarantees time-averaged conver-
gence to the stable point when the loss function is strongly convex, i.e, + Σi= || - x=12 - 0 as T oc. It's well known that strong convexity is equivalent the condition
VC(()) - VC(x',, x x') 2 m || - 2'112
(4)
Moreover, note that the strong monotonicity condition 2 is equivalent to 4 in the case single- agent learning, i.e., when N 1. This observation inspires the following analysis for multi-agent games.
3.2 MULTI-AGENT GAMES
As discussed in Section 3.1, strong monotonicity is sufficient for the convergence of no-regret single- agent learning to an equilibrium point. However, the extension of this result from single-agent learning to multi-agent games non-trivial, due to the structure of the agents' loss functions that are coupled by the other agents' actions. Besides, every time an agent updates its action, the other agents also react to this change. Therefore, since the actions v-i,; also change, the function -,()) becomes non-stationary from the perspective of agent i. In the following result, we show that if the game is sufficiently strongly monotone, no-regret learning can still guarantee Nash equilibrium convergence.
Theorem 1. Suppose that the game ( is m-strongly monotone and V C. is L-Lipschitz continuous in x= for every Is X. Suppose that an algorithm generates the action sequences (xi,), I,...,N, and that the regret of each agent satisfies Reg, ΣT, (Cu(zre)
Clyf (((f)==1.)) O(T"), vi= =i where y argmin y. Σt= G(Vi, and a E [0, 1). Let x" denote the unique Nash equilibrium and y² (vi, ... ..y) Then, the following hold:
4

---

Under review as a conference paper at ICLR 2023
1. |2- - 1-ll NL 2t=1 22 x=
2. m 21 N O, then Σ 1 x= 12 O(TO).
The proof can be found in Appendix 8.2 Theorem implies that any no-regret algorithm can lead
to Nash equilibrium whenever m 2 I 0. Note that the condition m 2Lv -I 0 always holds for single-agent learning where N = 1, as long as > O, which coincides with Lemma II
Remark 1. Recall that L1 and L are the Lipschitz constants of the function V,C((z) with respect to and x-s- respectively. From the definitions we can conclude that S L1. The Lipschitz constant L1 provides upper bound on the variation of gradients and is always greater than the strongly monotone parameter mi which provides a lower bound, i.e., m S L,. However, it is still likely to have m 2TNNN - 1 O. For example, in the extreme case where C₁ only depends on Is we have that and thus the condition naturally holds as long as m >> 0.
Remark We provide here some intuition regarding regarding the condition m 2LL/N -I> O. Rearranging the terms in the inequality gives T, < 2VN-I. Recall that T, is the Lipschitz constant of the function (,C, x-4) with respect to z-t, which can be interpreted as bound on the maximum influence of the other agents' actions. We need this influence of the other agents' actions and, therefore, L,, to be small for the game to converge. the other hand, the presence of multiple agents (N is large) makes the game increasingly involved, which restricts the class of games for which no-regret learning converges to a Nash Equilibruim.
In general, it is easier to analyze the regret of an algorithm compared to analyzing the Nash equilib- rium convergence. Theorem provides an alternative way to analyze the Nash equilibrium conver- gence: As long as we can show an algorithm no-regret and a game m-strongly monotone with directly obtain Nash equilibrium convergence.
m 2L,N T> >
SUFFICIENT CONDITIONS FOR CONVERGENCE OF GRADIENT DESCENT ALGORITHMS
In this section, we provide sufficient conditions for the convergence of multi-agent games to Nash cquilibrium with the additional knowledge that the no-regret learning algorithm is cradient-descent (GD) algorithm. Specifically, we investigate two types of GD al algorithms: first-order algorithm and a zeroth-order algorithm. Note that, under Assumptions and 2 can be easily verified that both first-order and zeroth-order GD algorithms ensure that the regret of each agent in (3) is sub-linear in T; see Hazan et al. (2016); Flaxman et al. (2004). In what follows, we show that Nash equilibrium convergence can be guaranteed for both algorithms as long m >> 0.
4.1 FIRST-ORDER ALGORIHTM
We first consider the case where the agents have access to their gradient information. Specifically, we assume that each agent can obtain an unbiased gradient estimate G, of (xC,(x) with finite variance given the joint action profile where E[G,] (zC,(z) and E[G; - (x)] o?. During learning, we assume that each agent performs the following action update
(5) where E|G,,,] = v.Ca(xt) and Px, projects the agent's actions to its action space X, In the fol- lowing result, we present the Nash equilibrium convergence analysis of the first-order GD algorithm 5)
F1,111 Px, (
Theorem 2. Let Assumptions 7 andd Lond2holl hold. Suppose that the game is m--trongly monotone with parameter m >> 0. Then, the first-order GD algorithm (5) with n mi satisfies that
E
|
1²11 O(T-1).
(6)
See Appendix 8.3 for the detailed proof. Note that equation
6 implies that there exists
constant Co such that E. || - 1012 & Cot-1 for Vt
1....,T. Summing over t.
5

---

Under review as a conference paper at ICLR 2023
we get E E || - x² - Ei Cot & Co (1+ tdtt) 1 Co(1 + In,,, and thus
E ||= x²1² O(I T). Therefore, the last iteration convergence implies the time-averaged convergence of the algorithm.
4.2 ZEROTH-ORDER ALGORITHMS
In many games, the agents have access to limited information and cannot observe the other agents' actions. For example, in the Cournot competition and Kelly auction games (Bravo al., [018) Lin et al. 2021), each company (agent) is not willing to share its strategy (action) with the rivals and would rather keep it as a secret. In this case, first-order gradient information not available since it depends on the joint action of all agents. Instead, here, we assume that the agents can only access their own loss function evaluation, which also referred to as bandit feedback. this case, common and effective approach to estimate the unknown gradient is to utilize zeroth-order methods. Specifically,
each episode, the agents perturb their actions Vi, by an amount òu,, where u1, E gd is a random variable sampled from the unit sphere $4. C R2 and is the size of this perturbation. Then, the agents play their perturbed actions åi,t Ti, du;, and receive as feedback their local losses C,())). Using this information, every agent constructs its own gradient estimate gt., 4; (og)))s,,, and performs the following update
0i,+1 = P(1-8)x; (Zi, T)...t))
where the projection set (1 - 8) is to ensure the feasibility of the next played action.
To facilitate the analysis, we define the 8-smoothed function C.² (xx)
Bu,.B,.arr__.. (c: + o + ōu-:)], where S-, i and Bj, S; denote the unit ball and unit sphere in Rdd,
respectively. As shown in Drusvyatskiy & Ratliff 2021 Bravo et al. 2018), the function Cf(2)) satisfies the following properties.
Lemma 2. Let Assumptions
Z and hold. Then we have that
1. (x is convex in sz;
2. (x) is Lo Lo-Liscchizz continuous in x:;
3. Cf (x) Cx(x)) SLoVNN
4. C(..)u)) V.C.
Note that, since the game with the loss function C,(x) assumed strongly monotone, it has a unique Nash equilibrium. However, without assuming that the Jacobian of V, (xC) is Lipschitz continuous as in Drusvyatskiy & Ratliff (2021), the smoothed game defined by the loss function C (x) over the set (1 (1-88) 8)X is possibly not strongly monotone and have multiple Nash Equlibria. As discuss below, even if the smoothed game has multiple Nash Equilibria, is still possible to show that the original game converges to Nash equilibrium. To do so, first provide lemma that bounds the distance between the Nash Equilibria of the smoothed game. In this lemma, for given 6, we denote by A the of Nash Equilibria of the smoothed game with loss C (xr contained in the (1 X). Since (x) is convex in Tú we know that there exists at least one Nash equilibrium in the smoothed game, i.e., A + 0.
Lemma 3. Suppose that Assumptions andd 2 hold and that the game T is m-strongly monotone. Moreover, assume that the smoothed game with losses (z) has multiple Nash Equilibria in the set (1 11-5) 5).. Then the distance between any arbitrary two Nash Equilibria is bounded by 2L,5N
The detailed proof can be found in Appendix 8.4
Lemma 3 states that, although there may exist multiple Nash Equilibria in the smoothed game, the distance between these Nash Equilibria can be bounded by the parameter 8. Based on this observation, we can further bound the distance between the Nash equilibrium x² of the original game and the Nash Equilibria of the smoothed game, as shown in the following lemma.

---

Under review as a conference paper at ICLR 2023
Lemma 4. Suppose that Assumptions 1 [ hold and that the game ① is m-strongly monotone. Then, any Nash equilibrium xd E A of the smoothed game satisfies that
1 2 ((1+
LIVN
N m
|
We provide the detailed proof in Appendix 8.5
Lemma shows that even if the smoothed game is not strongly monotone and possibly has multiple Nash Equilibria, we can still upper bound the distance between these Nash Equilibria and the Nash equilibrium of the original game. The result in Lemma Tis the same that in Drusvyatskiy & Rathiff (202T), with the difference that yrtssyy & Ratlifi (202I) make the additional assumption that the Jacobian of the gradient of the cost function is Lipschitz continuous. Here, show that this assumption is not needed and the statement the lemma still holds. We now present the main result.
Theorem 3. Let Assumptions A and hold. Suppose that the game ① is m-strongly monotone with parameter m >> O. Then, the zeroth-orde GD algorithu with Te me and = T satisfies that
E |2T - x²1 ().
(9)
See Appendix 8.6 for the proof.
Since Σ + S 1 dt +1+ 37 we obtain that E EE | x²1|²=
83
O Thus the time-averaged convergence of the game is guaranteed.
5 SUFFICIENT CONDITIONS FOR CONVERGENCE OF THE BEST RESPONSE ALGORITHM
In the previous section, we showed that gradient descent algorithms guarantee convergence of m- strongly monotone games to a Nash equilibrium provided that m 0. In this section, we provide sufficient conditions for Nash equilibrium convergence for the best response algorithm. The best response is a common strategy the game theory literature, especially that on fully competitive games, that produces the most favorable outcome given the other agents plays. In continuous games (T), the best response defined as:
argmin C, (1i, x
(10)
i.e., each agent takes the action that provides the best response to the other agents' actions from the previous episode. The convergence analysis of the best response algorithm presented below.
Theorem 4. Suppose that the game I is m-strongly monotone with parameter m > LVN -1 Then the best response algorithm TOP satisfies that
10 x112 S 0- 1000 x x²1
(11)
-21 where p m²
The proof is provided in Appendix 8.7 From the inequality 11. it is easy to obtain that E | - 11 < Et= p² || 1²
1-p ||00=01112 = O(1). Theorem shows that the best
response algorithm converges to the Nash equilibrium at a linear rate. Indeed, it is no-regret learning algorithm for each agent as well, as shown in Theorem 5 in Appendix 8.8
To the best of knowledge, this is the first effort to provide a sufficient condition (m LVN - under which the best-response algorithm achieves Nash equilibrium convergence in convex games. Moreover, we experimentally show that when m > LVN does not hold, the best-response algorithm may lead cycles, which further supports theoretical results.

---

Under review as a conference paper at ICLR 2023
6 NUMERICAL EXPERIMENTS
In this section, we illustrate and compare the proposed algorithms on the Cournot game problems. Additional experiments on retailer pricing games and Kelly auction games can be found in Appendix 8.9 and 8.10 respectively. We show that, by defining sufficient conditions for Nash equilibrium convergence that depend only the properties of the game, i..., the parameter m, and not the learning algorithm used to solve it, our analysis allows to identify classes of games for which no-regret learn- ing guarantees convergence to a Nash equilibrium without analyzing specific algorithms or identify specific no-regret learning algorithms with no guaranteed convergence to a Nash equilibrium.
We first consider Cournot game with agents whose goal is to minimize their local loss by appropriately setting the production quantity I₁, i = 1, The loss function of each agent is given by C,xx) ( ( -b + where a; > 0, bi, e; are constant parameters, and x denotes the production quantity of the opponent of agent i. It is easy to show that (xC,(z) 0;æ; + d Recalling that L is the Lipschitz constant of the function (zC,(x) with respect to T- we have V2C2()) and let G(z) denote the Jacobian of g(x), ie., G(x) = [a1, b1; U2]. According to Rosen (1955), the strong monotonicity parameter m in this simple example coincides with the smallest eigenvalue of the matrix G())+G'(a) In what follows, we verify and compare the effectiveness of the first-order gradient descent algorithm (FO), the zeroth-order gradient descent algorithm (ZO), and the best response algorithm (BR), analyzed in Sections| 4 and [5] To apply the first-order algorithm, we assume that the gradient subject to noise sampled from the normal distribution. For all algorithms, the feasible set is defined as X; = {2: (2; E (0.3]]
L = max(b, b2). Define g(z)
.0P
1.50
10"4
1.25
0.75
10'2
0.50
0.00
800
1000
(a) Error to Nash equilibrium of the first-order method (FO) and the zeroth-order method (7O).
(b) Action values of the best response algorithm (BR).
Figure 1: Cournot game when m LVN- I.
We validate our methods for two different selections of parameters. First, we select the parameters (a1, 02) = (2, (bi,
(0.5, 0.5), (e1, 62) = (1.8, 1.9). Using these parameters, we get that m 0.79, L 0.5, and, therefore, m > LVV I, so that the sufficient conditions for all three algorithms are satisfied. The results are shown in Figure [ where the solid lines and shades are averages and +: standard deviations over 60 runs, respectively. Specifically, in [ the two gradient-descent algorithms both converge to the Nash equilibrium, and the first-order algorithm outperforms the zeroth-order algorithm in terms of convergence speed and variance. Figure (bb illustrates the action updates of the best response algorithm. Since the best response algorithm performs the action update in a way that each agent selects the optimal actions against other agents' actions, this algorithm converges very fast to the Nash equilibrium point (0.4857, 1.657).
Next we select the parameters (a1, a2) = (2, 1). (b,, b2) = (-1.5, 1.5), (21,02) = (1.8, 1.9). In this case, we have that m = 1, L = 1.5, and, therefore, m LVV II As a result, the sufficient condition for the best response algorithm is not satisfied. The simulation results in this case presented in Figure 2 When m LVN-1, 1, the first-order and zeroth-order gradient descent methods still converge to the Nash equilibrium, as shown in Figure 2 (a). Figure (b) shows that the agents' actions of the best response algorithm oscillate in regular pattern after episodes and fail to converge to the Nash equilibrium. Therefore, the best response algorithm does not guarantee convergence the Nash equilibrium when the sufficient condition is not satisfied.
8

---

Under review as a conference paper at ICLR 2023
agant
20-
2013
20.2
0.0
1000
aphode
Error Nash equilibrium of the first-order method (FO) and the zeroth-order method (70).
Action values of the best response algorithm (BR).
(b)
Figure 2: Cournot game when 0 < m < INN-1.
We also consider a Cournot game with 5 agents, = 1,2,3, 4,5. The loss function cach agent is (x)) = z,( Ea + 6, Lizt f 2 e4) 1, where [2,2, 1.8, 2]. 6 [0.2, 0.3, 0.3, 0.2, 0.3], e = [1.8, 1.9, 1.5, 1.6, 1.8]. In this case m = 1.2844, I. = 0.6, and therefore m > IvN - so that the sufficient conditions satisfied for all three algorithms. The Nash equilibrium is xx [0.672, 0.512, 0.631, 0.538). Figure 3 shows that all three algorithms converge to this Nash cquilibrium.
PO
107
10:1
10"4
10-3
1004
10-
10
1019
101
400
(a) Error to Nash equilibrium of the first-order method (FO) and the zeroth-order method (70).
(b) Error to Nash equilihrium of hest re- sponse algorithm (BR).
Figure 3: Cournot game with multiple agents N when m > LVN-L
7 CONCLUSION
In this work, we study the connection between no-regret learning and time-average Nash equilib- rium convergence for the class of strongly monotone games. Specifically, we provided sufficient condition on the class of strongly monotone games for which any no-regret learning algorithm leads Nash equilibrium convergence. Moreover, we showed that the class of these games can be ex- panded when additional information about a specific no-regret algorithm is considered, including the first-order and zeroth-order gradient descent algorithms and the best response algorithm. We numerically validated our theoretical results for different games that belong to different classes, in- cluding Cournot games, retailer pricing games, and Kelly auction games. Compared to existing literature that analyzes the regret and Nash equilibrium convergence for specific algorithms and for assumptions that depend on the specific choice of algorithms and games, here we proposed a differ- ent approach that focuses understanding the fundamental relationship between no-regret learning and Nash equilibrium convergence, regardless of the specific learning algorithm and based only on the game type.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 736-749, 2022.
Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradient- based methods for whole spectrum of differentiable games. International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2020.
Mario Bravo, David Leslie, and Panayotis Mertikopoulos. Bandit learning in concave r-рerson games. arXiv preprint
2018.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-27616, 2021.
Dmitriy Drusvyatskiy and Lillian Ratliff. Improved rates for derivative free play in convex games. arXiv preprint 0tti::/111.094550 2021.
Stéphane Durand and Bruno Gaujal. Complexity and optimality of the best response algorithm in random potential games. International Symposium on Algorithmic Game Theory, pp. 40-51. Springer, 2016.
Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen. Multi-agent online learning in time-narying games. arXiv preprint arXiv: arXiv:1809.00 1809.03066, 2018.
Abraham Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. arXiv preprint cs/0408007, 2004.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. Advances in neural information processing systems, 33:20766-20771 2020.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 313-4):157-335,20000 2016.
Amélie Heliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. Advances in Neural Information Processing Systems, 30, 2017.
David S Leslie, Steven Perkins, and Zibo Xu. rest-nesponse dynamics zero-sum stochastic games. Journal of Economic Theory,
2020.
Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-time last-iterate convergence for multi-agent learning in games. In International Conference on Machine Learn- ing. pp. 6161-6171. PMLR, 2020.
Tianyi Lin, Zhengyuan Zhou, Wenjia Ba, and Jiawei Zhang. Optimal no-regret learning in strongly monotone games with bandit feedback. arXiv preprint arXiv:21 2021.
Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 173(1):465-500 507, 2019.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithmss, pp. 2703-2717, SIAM, 2018.
Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian Ratliff. Learn- ing in stochastic monotone games with decision-dependent data. In International Conference on Artificial Intelligence and Statistics, pp. 5891-5912. PMLR, 2022.
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica: Journal of the Econometric Society, pp. 520-534, 1965.
10

---

Under review as a conference paper at ICLR 2023
Halsey Lawrence Royden and Patrick Fitzpatrick. Real analysis, volume 32. Macmillan New York, 1988.
Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. No-regret learn- ing in unknown games with correlated payoff's. Advances in Neural Information Processing Sys- tems, 32, 2019.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 422):077-94, 2012.
Brian Swenson, Ryan Murray, and Soummya Kar. On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 56(4):2734 2767, 2018.
Tatiana Tatarenko and Maryam Kamgarpour. Minimizing regret of bandit online optimization in unconstrained action spaces. arXiv preprint arXiv:1806.05063 2018.
Tatiana Tatarenko and Maryam Kamgarpour. Bandit online learning of nash equilibria in monotone games. arXiv preprint urXiv:2009.04255 2020.
Zifan Wang, Shen, and Michael Zavlanos. Risk-averse no-regret learning in online convex games. In International Conference on Machine Learning, pp. 22999-23011 PMLR, 2022.

---

Under review as a conference paper at ICLR 2023
8 APPENDIX
8.1
AUXILIARY LEMMAS
Lemma 5. BBavo al. 2018)) Let Oro 11,,.... be non-negative sequence such that
an+1 S an2(
(12)
n
where > O, and A, E > 0. Then, assuming A > we have that
E
On S (A q)ng
+
0
(13)
119
8.2 PROOF OF THEOREM
We first show useful lemma that lays the foundation for the subsequent analysis.
Lemma 6. If the game with the cost C; (x is strongly monotone with parameter m, then the function C=(2, x-i) is strongly convex in z.
Proof. From the strong monotonicity condition 2 it follows that
(14) Define h₂(2) c((z,_1). Then, incquality (14) becomes (Vh,(2) Vh,(z'), 2²) m z'112. The result follows from the fact that differentiable function strongly convex and only if domain convex and (Vf(x) Vf(x'), x²) 2 m | ='1
(V.C((z,z_4)- =. z/) 2 m 1 21
>
Using Lemma 6 we have that the function ==) is strongly convex in z, which means that C(y/.=..) 2 (V -(-)) lla/ 1ill² for any fixed E X_ Recall that yf- = argmin,, E Cy,,, and x denotes the Nash equilibrium of the game (T). Since the sum operator preserves convexity, we have that E, (.....r is also convex in yi. Moreover, from the necessary condition of optimality, we have that Σ, (V.C. x.,,)), V/ ut) 2 for ky, E X. Since xº E X,, replacing y: with x; gives that
Σ EVV.Cili x (.), vi) 2 0.
(15)
Next, we analyze the distance between x" and y", where y² = (vi, ....,.),)))) By strong monotonic- ity of C,(2,, ()),, we have that (V,C, x =i.)) - V,Ci( x ,, yt xf) 2 m llv x; 1| Summing this inequality over t 1. ....., T. and combining the inequality (5]. we have that
-it)
mT |x 1 Σ (vv.
C.C. x (,)), of x5}--
(16)
Summing the inequality 16 over = ,....,,, we further obtain
mf || - y"' 212 -
x
(VVCC(**) V,C,(1], -x1) ΣΣ
(V.C(("",, x1)
((V.C((**)
- -x²)
Σ - - 0",كه || - v.
ΣΣ L || x= || w'
<NL 1|2 y²1l 2
| x ||,
12

---

Under review as a conference paper at ICLR 2023
where the second inequality is due to the fact that x² is Nash equilibrium and the third inequality follows from the Lipschitz continuous property of the function V,C, with respect to 2-5. Rearrang- ing the terms in the above inequality, we obtain the first of the two theorem statements.
Next, we analyze the regret of the action sequence {1r,e} for = I,,.,,N. N. By the definition of regret in we have that
Regret:+ - - - Ecilvi x.1,))
(C((E)) C1 x-1)) + Σ -CC
- C((((
E (VV.Ci(o) 11) Fis 21) + m || z2.ell3) + Σ =-))) v.)
m llve x;
Ri,
> (V, x x211), Tzi T2,
x;) + m
|| - xs,ell 11
+
mf
l1 - xz 1|
(17)
2
2
where the first inequality follows from the strong convexity of the function (2, x-:) with respect to z for any x-i E X_ and the second inequality follows from the necessary condition of optimality. Summing the regret in (17 over -I....;,,, N, we have that
Σ Regret,- = ΣΣ
(((x)) - C((1i,0-.11
Σ || - 20l1 2+ mT
V.Ca 2 -2) x;¹) 2
2 11y - 2211
V C2 (xx") 3, x2) + mt
Σ Σ CG
V,C((""), -.G(') x1) + ΣΣ
11y* xx" x=1
+ Σ | 2111
Σ v.C(+)
+
m
Σ 11 - -ell2+
mT
I1y - x²1
2
2
(-( - I1 - 2;1l + m Σ
2
|| - x2l12 + mT
11y" - x x²1
(18)
2
where the second to the last inequality follows from the fact that x" is a Nash equilibrium and, therefore, satisfies (V.C,(z)) ), x4 xx} 2 for Va E X', and the last inequality is due to the fact that v.C,(x) is Lipschitz continuous in x- Applying the inequality ab S 2/4 a² + 2b?, AA to the term ||-_i, - 1= - x; in (88), we have that
Σ Regret, 2 - L ΣΣ Σ
| =.,ell + X
+ || - xx-..113))
Σ
||
xel1 +
mf
2 11y x=
2X
2
2
- こ 2X ||"
2.11 + +2
2 (N 1) 11=0 - -xxl1))
m
Σ
|| xel1? 2 + m.T
11 x= 11
2
(19)
where the last inequality follows from the fact that E3 1|2= -- 11 (N 1) 1|00 x3 112
Inequality (19] holds for Vλ > O. Substituting x = (N - 1)- in (9).
we get that
Σ Regret, 2 - LVN 1 Σ ||-- - 12+112+ + m Σ
11~0" - -rell
mT
11 - x111
2
2
t
2L
m.T
||0
x² 121 +
I1y"
x²122
(20)
2
2
Since we assume that the learning algorithm is no-regret, we have that m 2L-N-I E, || - 11+
m E, ||0" 2xll2 < Σ, Regret, O(T"). Given that the two terms in the left hand of this
13

---

Under review as a conference paper at ICLR 2023
inequality are always positive, conclude that Ee ||00 22 O(T²) and mf. 11y x012 O(T"). The proof is complete.
8.3 PROOF OF THEOREM 2
According to Theorem 2 in Rosen (165).. strongly monotone games have unique Nash equilib-
rium. Let x= (x), "0,,""> denote the Nash equilibrium of the game (T). Using the update equation 5).
we have that
|04441 x;1l² lipx; (3r4,e (1, - x111
1 || 2 - -n.Gi,ll'
1 |0 2/ +
ni GG,,ll 2 2m7 (G x;),
where the first inequality follows from the facts that Px (x() = z and x( I ||||| for any vector z. Taking the expectation of both sides of above inequality, we get
F1 11 <E
21 + of ||G 27 (Gi, Feet x;} ||a.,
< - - -,,1 + o (x,)l + n,o²
2n V V,C, Fiit x1)) (21)
Since x² a Nash equilibrium of the convex game, we have that (V,C,(**) Fiet - x;)) 2 0, i 1 N. Summing the inequality (2l) over I,..,, N, get that
E |1+11
x²1
<B
112 + th [vC((=)))l + No= 2nt (V.CC(L))) 214-
<B D2 x= 11? + tp NB + n1. No² - 2 E(vic(E))) - v,c,(=", x
<(1 2m.m) B B|
x= 11? + N2 + No²
<(1 || =2"1 N(B² + 0²)
2
m²t²
where the second inequality follows from Assumption and the fact that x" is Nash equilibrium, the third inequality follows from the strong monotonicity of the game (I), and the last inequality is obtained by substituting Y mi Then, using Lemma we obtain
E |ZT 1ZT 21
N(B² + +
+
(t)
T
m²T
which completes the proof.
8.4 PROOF OF LEMMA 3
In the analysis that follows, the expectations taken w.r. W; B, and u-; S_4. Since C₁ bounded and with finite support, by Lebesgue's dominated convergence theorem (Chapter 4 in Royden & Fitzpatrick (1988)), we can interchange the order of integration and differentiation. From the definition of C. (z). it follows that
v.C.(z)
(x) v,
v.C.(x) - V.E[C, dw,, x= du_.)]
E E(V,C(()) V.Ci(x + 5w; + 8u,;)
< EE L1 [[ w.
S L,8VN.
(22)
where the first inequality follows from the Lipsehitz continuous property the function (xC. with respect to Recall that A denotes the set of Nash Equilibria of the smoothed game with
14

---

Under review as a conference paper at ICLR 2023
losses C. (x)) Take two arbitrary points y8 23 E A.. Then, we have that
- v.CC =3,)
E (V.C.(0)) V,CC, vb: - -2a,) + V
-2%))
Σ (V.C V.C.(z)), - - - Σ 2 115. - =
2m 115 1 2T, 18 11 =8
(23)
where the first inequality follows from the inequality 22 and the second inequality is derived using
the strong monotonicity condition and the fact that < || - 2 1l) s N Σ, 1 - = 1l
N 11v5 =-
Since y3. 2g are Nash Equilibria of the smoothed game, for Vx; E (1 - 8)2, we have that (v.C 24 vτ,) 2 and (xf)) - 2z,} 2 O. Replacing x; in the above two inequalities
with 2x, and vb.- respectively, obtain that
(v.C, z5. -,8,) 2 0, (V.C( v3. z3,) 2
Adding these two inequalities together gives that
(v.C) v,c₁ (2 vo
2x,/ S0.
(24)
Combining inequalities 23 and 24 we get that m 1 z311 ON 108
-2ill S Rear-
ranging the terms in this inequality completes the proof.
8.5 PROOF OF LEMMA 4
Let J² be the Nash equilibrium of the game defined by the losses C, over the set (1 - 8)X, and recall that x= is the Nash equilibrium of the original game with losses C, over the set X' and æd is one Nash equilibrium of the smoothed game with losses C. over the set (1 - 8).X. Since the losses C, are strongly monotone, the Nash equilibrium i² is unique and well-defined.
By the triangle inequality, we have that ||a= اااهة || 1' This bound has already been derived by Drusvyatskiy & Ratliff (2221). and takes the form
< || - x=1| + ||ا5 - xz |. We first bound
La L m
|| 111l S
||="||
(25)
Next we focus on the term libria satisfy the following property:
| 8.1|. The convexity of the game guarantees that the Nash Equi-
(V,C,("") mイ) 2 0, Vzz - 6),44,
(V (x 2.ا 2 O, Va, E (1 100-6. 8)
(26)
Replacing x; in the above two inequalities in 26 with v, 3. and 3ú, respectively, and summing the two inqqualities, we have that
- - ), ; 2 0. Combining 27 with the strong monotonicity condition we have that
(27)
m ||ا 1+ (V.C((29)) V.C,(t*) ) zz)
-
I(Vici(ad)) - v.c. 5.5 )
LLIV | 1-55- x:1
SLION |1o -2'1--
15

---

Under review as a conference paper at ICLR 2023
where the first inequality is due the strong monotonicity condition 2 the second inequality follows from (27) and the third inequality follows from (22). Therefore, for any Nash equilibrium IJJ A we have that
|| - x²1l - L,ON
(28)
m
Combining 28
with 25
we have that || - 2dd ||
11 - -0'1 + | xz
LIVN 8
1
+
L1 m
which completes the proof.
m
8.6 PROOF OF THEOREM
Recall that the Nash Equilibria of the smoothed game with losses C over the set (1 8) are x&J,
From the update equation (7) for any xd E AA, we have that
Tis+1
5,5
P(t ()-6))x (Fi,t mhgi,s) - x
fJ - -7.91.
-
04.e - zi
xi., _ú ssl $12
+ nē |1.g.. 2 2n (gi,,, Fi, -x, (,55)
where the first inequality holds since 69 E (1 - 6). Taking expectations with respect to uA of both sides of the above inequality, we have that
du 2m
E Filt1 - 2 5.
- (. (29)
Fi.
+
8²
Since r 6.5 is Nash equilibrium of the smoothed game, it satisfies (V, C. (x (1) Iz -I: 0, Vx;
(1 2,. Summing the inequality (2) over i = 1, 1,..., N, we get
n BUNUUN
E |e+1 - 10 SE x4
2n Eiv.c((rr) - V v.C. (2 Izit L
8²
SE o4 - 10 + 11
uU
(m - -2, || - -555
2111
82
1/
TUUUU
<( 2m.m) E ||,, - -
+ 4A,
(30)
82
where the second inequality can be obtained using similar techniques in 23 mt into (30). we get that
Substituting 1/:
E
[ - x
A 11
S(1
2
=
E
rt - x 2 +
dURN
+
ND
t
4m2
mt
$1 - -
2
- x 101
+
Ei
E2
(31)
t.
1282
where Ej
2U 4m
ND, Eg = ND
Using induction, it can be verified that for Vt 2 1,
there exists constant Ag such that
E Eg8, Ao
[
1
+0)}
E || E|| S max
(32)
to
Replacing t with T and setting
== T 1 in
32
we
get
E FT 2ل 2 <max 7
Ej
Egd,
Ao
T b
2A,T 8
(33)
where A == max { E1, Ez, Ao}. Combining
(33 with Lemma
4 we have
E || x² 2|
<2E
2T - ال + 2
-x"1|"
2
((1+
LINN'
||I" ||
+
L,
-4A,T-34
T
=0
-T(T))
(34)
which completes the proof.
16

---

Under review as a conference paper at ICLR 2023
8.7 PROOF OF THEOREM
From the convexity of the loss function C; and the update rule (TO), we have that ( I; 2i.+1) 0, Vz, E X, Since the game ① strongly monotone, we also have that for all 2; N. (2,
(35)
V ( 2; 21,0+1) 2 m a 21,011l2
(36)
Replacing 2; with xi in (36) and combining with (35). we get
m || 21, - (V, x-1,)) C,C, -- ratti S (V.C(o), -
-11441)
(37)
Summing the inequality over ,,... N, follows that
|| || 1²2 < m
(x 23,0-1)
1
V.C, (2) x- -1)) v.C((x"), 2, x1,411
-| - 8-1l | - -1,++1ll
L
1
| x=11/² x
|+,,t11 - 2211
m
2X
L
N || - x=
x++1 - x²112)
(38)
2X
2t) 0, for Var E X, the third inequality follows from the Lipschitz continuous property of the function C, in -- and the second to last inequality is due the fact that ab 2x a² +
where the second inequality follows from the Nash equilibrium condition
o b² for any X 0. Setting
L and rearranging the terms in (38), we obtain that
| - 2²11 < L'(N-1)
||08 - x $1
(39)
m
Applying inequality 39
iteratively for t 1,...,T have that || - -
(N(N-1) m2
T
|1000 - 1 which completes the proof.
8.8 BR ALGORITHM IS NO-REGRET LEARNING
Theorem 5. Suppose that the game ① is m-strongly monotone with parameter m INN-1 - Then the BR Algorithm achieves no-regret learning, specifically
T
Reg, c,(x)) min 2t
(40)
Proof. Let vf == argmin,, ET= C, -..)) Recalling that 0i,++1 argmin,, C, -.)), we have that (V.C, (2i,41,, x i. - 1i,1 1) 2 O. From the definition regret in (3. we have that
Reg, (c(().)) Ci(yi x..)))
(G((zz) C( x- + -1
T
(C((xz) -((EEt1, + x. -v²)
1=1
(G((z)) -(E,)41,
17

---

Under review as a conference paper at ICLR 2023
where the first inequality is due to the convexity of the loss function (x) with respect z, and the second inequality follows from the necessary condition of optimality. Then, it follows that
T
Reg.
(((x)) (((+++1) (((++)) - (aaa:))))C(((..1a. (,(04141.
T
+ sc,(x1)+
Σ -((TA1))
t=1
SU + Lo Σ 10-1141---111
(41)
where the last inequality follows from the Lipschitz continuous property of the function C, in x. Summing the inequality 441 over I,, we have that
Reg, SNU Lo
x x-1+41 x- S NU Lov N(N 1) 2 Tzll:
(42)
where the last inequality follows from the fact that -2-iell
N WE - x-l $ N(N 1) || - =ell.. From the inequality (39) in the proof
of Theorem 4 when
LVN 1, we have that || 1=1 I 12 x=1 Using this
result, we can bound the term | 2rel1 as follows:
| - xz _12 = || - x²' + xx xel1
=1 - 2²122 + || - x² x=11² -2 2 ||x1-11 - x ||+ -x=1
< || - x² x²11 + || - x² 1|2
||:2+1 x01
vp
< || 11 || x=1l" 11?
(43)
where the last inequality holds since < 1. Then, substituting the inequality (43) into the inequality we get that
42
Reg, <NU LovN(N 1) Σ V || - x=1
| - 1²1
NU + Lov N(N 1)T |21 - x=-1
<NU LoD 1)T,
(44)
where the second inequality holds since ET az)² < T of. Using the fact that Reg, < ΣN Reg, completes the proof.
From equation (41) in the convergence proof of the best response algorithm, we have that Reg. S
-E Ca(xr)) Et min EX; Ci(xi, which indicates that the dynamic regret agent i, i.c., ΣT, C,(x)) - - ming, (,(,,,,-111) is of order OVVT). Note that this term captures the dynamic regret induced by the variation of other agents' actions.
Σ (C((x))) (G((,,,11,
O(VT),
8.9 ADDITIONAL EXPERIMENTS: RETAILER PRICING GAME
Consider a market with two retailers and four products. Each retailer is responsible for selling different products and making pricing decisions for their own products at each episode t. Suppose that Retailer 1 sells the j-th product for j 1, 2, while Retailer 2 sells the j-th product for j = 3, 4. Retailers 1 and make pricing decisions z = (pi. pb) and z (p).pá). respectively, where of denotes the decision of Retailer i, and p) denotes the price of the j-th product at episode t.
18

---

Under review as a conference paper at ICLR 2023
14'
107
10"7
10:15
10-7
10"42
1074
1000
aphode
Error Nash equilibrium of the first-order method (FO) and the zeroth-order method (70).
(b) Firor to Nash equilihrium of the best sponse algorithm (BR).
Figure 4: Retailer pricing game when LVN-1.
All products are substitutes or complements of each other and their pricing decisions influence the demand of other products. The demand of the j-th product is modeled as Dz = Eis Asppf + by. where Ajk. bj > are constants. Note that As* > 0 if the k-th product is substitute for the j-th product, Ass < 0 if the k-th product is complement of the j-th product, and A₁ < 0 for
j = 1, 2, The goal of each retailer is to minimize their own loss, where (i)) - (p) Dí (x)
Pa D2 (z)) and C2(2:) (ps Dz(x) + p4 (x)). The parameters Age are given as
-2
-0.5
0.1
-01
-0.5
-2
-0.4
0.1
A
0.1
-0.4
-2
-02
0.1
0.1
-02
2
Using these parameters, get that 2.82, L 0.3, and, therefore, LVV As result, the sufficient conditions are satisfied for all three algorithms. The results are shown in Figure where the solid lines and shaded areas denote the average and standard deviation over 60 runs. Figure 4 shows that all three algorithms converge to the Nash equilibrium.
8.10 ADDITIONAL EXPERIMENTS: KELLY AUCTION
Consider service provider (providing, c.g., bandwidth, space on website, etc.) with two bidders N = 2 that place monetary bids E [0, D] for the utilization of the resource. Each bidder receives their own bid, i.e., the i-th bidder gets Pt units of resource, where d 2 0 is the entry barrier for bidding it. We model the loss of
some unit of the resource which is proportional
21
a+ 2;
each bidder as (x(x) (g:p; - 2z), where is the bidder's marginal gain from obtaining a unit of resources. We set 9: 0.8. Vi 1,2 and 0.2. Figure presents simulation results for this example. We see that the first-order and zeroth-order methods converge to the Nash equilibrium. Note also that, in this example, m < TVN-1 always holds regardless of the choice of parameters. Therefore, the sufficient condition for the best response algorithm is satisfied. Nevertheless, as seen in Figure b), the best response algorithm still converges to the Nash equilibrium, which validates our theoretical analysis that this condition only sufficient and not necessary.
19

---

Under review as a conference paper at ICLR 2023
FO
10"4
86
10"
10"
-1P
10-13
250
400
500
10
spradd
ophods
(a) Error to Nash equilibrium of the first-order method (FO) and the zeroth-order method (ZO).
(b) Error to Nash equilibrium of the best re- sponse algorithm (BR).
Figure 5: Kelly auction game.
20


Reviews:
[{"review_id": "jGDUmk-mNr", "reviewer": "Reviewer_yhnp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to understand the convergence rates of no-regret methods in strongly monotone games to Nash equilibria. It examines first-order/zero-order/best-response instantiations proving their no-regret guarantees. The main contribution of this work is to show that the strong-monotone class of games for which no-regret learning leads to a Nash equilibrium can be expanded if only some further information on the learning algorithm is known, like the regret rate.", "summary_of_the_review": "The authors address this question by providing a sufficient condition for strongly monotone games that guarantees Nash equilibrium convergence in a time average & last-iterate sense (for some cases).  Specifically, they provide relaxed sufficient conditions for first-order and zeroth-order gradient descent algorithms as well as for best response algorithms in which agents choose actions that best respond to other players' actions during the last episode. ", "strength_and_weaknesses": "This is a paper that had created to me a very controversial feeling. The majority of the presented results, in some sense it seems to me already known from the literature, especially from the line of Mertikopoulos et al ' works. Additionally I noticed that the authors have not cited and compare their work with the following publication, \"Tight last-iterate convergence rates for no-regret learning in multi-player games\".\n\nIn general the proofs, as machinery, are tremendously used again again last years in the literature.\nHowever, I should mention that in this draft, the proofs are definitely clear.\n\nThe real strength of the arguments of this work is the clear connection of no-regret guarantee of an algorithm and its convergence guarantee if the underlying game is strongly-monotone.\n\nWhile I have worked in the area, I am not sure if such a clear connection has been established before and I would like to see from the discussion and the opinion of the Area Chair, if this is an actual novel contribution. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_JnHxkVQws", "reviewer": "Reviewer_k8bM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the convergence of no-regret dynamics in smooth strongly monotone games with sufficiently large strong convexity modulus.", "summary_of_the_review": "Ignoring the violation of the formatting guidelines, I find that the the reasons to like the paper outweigh the reasons to dislike it. However, I am slightly unconvinced about the applicability of the paper, and that weighs on my score.", "strength_and_weaknesses": "*The paper visibly exceeds the allowed margins by a significant amount, so it is not clear whether it can proceed with the review process. Unfortunately, due to understandable fairness reasons, I believe there is a chance that the paper might need to be rejected; I will let the area chairs deliberate on that. In what follows, I will focus on the content of the paper under the assumption that the paper will be allowed, hoping that even if the paper is rejected the authors will still find the comments useful.*\n\n---\n\nOverall, I have a borderline opinion of the paper, more positive than negative. I didn't find any of the results especially surprising, but I find the paper well organized, and the bundling of topic well executed, with only a few reasons to be unhappy.\n\n1. What I find the most prominent weakness of the paper is the setting of strongly monotone games, which I find pretty restrictive, though of course I would be happy to be proven wrong by the authors. In particular, I'd be interested in knowing games of interest with more than two players that satisfy strong monotonicity. All the examples considered by the authors seem to have two players.\n\n2. (Adding more to point 1). I might be being silly, but the important conditions on $m$ in Theorem 1 and Theorem 4 require that the ratio $m/L$ be $m/L > O(1)\\sqrt{N-1}$. The reason why I find this a bit surprising is that $L$ is a Lipschitz constant on the gradients of the losses (fundamentally an **upper** bound on the variation), and $m$ is a strong convexity modulus for the gradients of the losses (fundamentally a **lower** bound on the variation). Hence, at least on some intuitive level one would imagine that usually $m/L < 1$, yet the conditions in the theorem require $m/L \\ge \\sqrt{N-1} \\ge 1$ for $N \\ge 2$. Maybe this is what the authors were trying to get at with Remark 1, but unless I'm missing something, this to me further reduces the applicability and appeal of the results in the paper in a way that Remark 1 was maybe too shy to clearly point out. Please let me know if I missed anything.\n\n3. Another area where the paper might have easily been improved was in giving high probability bounds rather than only in-expectation (I imagine that that would follow easily from concentration inequalities, but please let me know if I missed something).\n\n4. I found the description of the bandit setting, so focused on whether players are comfortable or willing to reveal actions, a bit unusual. I think perhaps the motivation for the bandit setting would have been better found in whether or not the players know their payoff matrix, or whether instead they need to learn that as well.\n\nOverall, my biggest reservations lie around my points 1 and 2 above; if those were resolved, my score for the paper would easily increase.\n\nNits / Typos:\n- At the end of page 3, there is a double comma \",,\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WGSp_XeYik1", "reviewer": "Reviewer_yciX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes classes of online games for which classes of algorithms will always converge to a Nash equilibrium. The main result is: for m-strongly monotone games, any no-regret algorithm will converge to a Nash equilibrium, if m satisfies certain conditions. The paper also considers other types of algorithms: first-order and zeroth-order gradient descent algorithms. Experimental results validate the theoretical results on a few examples of strongly monotone online games. Also, best response algorithms are considered.", "summary_of_the_review": "\nI think this is a borderline paper, tending to accept, based upon my above comments.", "strength_and_weaknesses": "# Strengths\n- Finding Nash equilibria is an important problem in game theory. It is interesting to identify classes of games for which algorithms of a certain type will always converge to a Nash equilibrium. However, the m-strongly monotone games are a special type of convex game, in which all loss functions for each agent are convex. This seems to be a strong assumption on the game: for these games, only one Nash equilibrium exists. \n- The experimental analysis of the convergence of various algorithms on specific examples of Cournot games and retail pricing games is nice to see. The authors show that when their assumptions are not satisfied, some of the algorithms may cycle and never converge.\n\n# Weaknesses\n- Strong assumptions needed on the loss functions. In addition to m-strongly monotone, convex loss functions, Assumption 1 & 2 on Lipschitz continuity are needed. However, the authors identify specific applications in which these assumptions do hold, including Cournot games and retail pricing games.\n- Theorem 1 appears to be the main result of the paper. However, there is very little discussion of the Theorem or its proof in the main text. Much space is devoted to the gradient descent algorithms.\n- It would be nice if the authors identified specific algorithms, already extant in the literature, that fall into their framework but were not known to converge to Nash equilbrium. However, I did not see any discussion of this kind of result. Such algorithms would show the utility of the analysis.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IK2f2jizWpG", "reviewer": "Reviewer_MydF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper shows that any no-regret dynamic converges to a Nash equilibrium in strongly convex games, assuming the convexity is sufficiently strong relative to the Lipschitz constant of the gradient function. Somewhat better bounds are shown for specific no-regret dynamics.", "summary_of_the_review": "There seem to be few if any concrete examples where these results demonstrate something that was not previously known. The general statement is, of course, interesting. The strong assumptions reduce the attractiveness of the paper. Is it so surprising that under very strong convexity assumptions no-regret converges to Nash?", "strength_and_weaknesses": "The results are interesting but not extremely novel, given the very strong assumptions on the games that are analyzed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject