Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Alian Porzani, Alireza
Master of Applied Science - MASc
University of British Columbia
Game theory and online optimization have a close relationship with each other. In some literature, online optimization has been employed for solving game theory problems. Many accelerated algorithms are proposed for offline optimization problems. However, to the best of our knowledge, there is not enough work done to accelerate zero-order online optimization. The goal is to propose a Nesterov accelerated online algorithm with the hope that it will converge to the Nash, with a fast convergence rate in Cournot games and Quadratic games. It is desired that this online algorithm also minimize the regret of a sequence of functions for both zero-order and first-order feedback. In potential Linear Quadratic (LQ) games, we also study the convergence of the policy gradient algorithms, a class of conventional reinforcement learning methods. LQ games have applications in engineering. It has been shown that using policy gradient algorithms by agents does not guarantee convergence to the Nash equilibrium. However, in the LQR problem, which is essentially a one-player LQ game, the policy gradient converges to the optimum. In this work, we show that using policy gradient algorithms leads to convergence to Nash equilibrium in potential LQ games. Additionally, we identify the characteristics of potential games in both open-loop and closed-loop settings. We will demonstrate that the class of closed-loop potential games is generally trivial, and if we put restrictions on players' actions, we can have non-trivial potential games too.
Convergence to Nash in the PotentialLinear Quadratic Games andAccelerated Learning in GamesbyAlireza Alian PorzaniB.Sc., Sharif University of Technology, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)October 2022© Alireza Alian Porzani 2022The following individuals certify that they have read, and recommend tothe Faculty of Graduate and Postdoctoral Studies for acceptance, the thesisentitled:Convergence to Nash in the Potential Linear Quadratic Gamesand Accelerated Learning in Gamessubmitted by Alireza Alian Porzani in partial fulfillment of the require-ments for the degree of Master of Applied Sciences in Electrical andComputer EngineeringExamining Committee:Dr. Maryam Kamgarpour, Assistant Professor, Sycamore lab, EPFLSupervisorDr. Lele Wang, Assistant Professor, Electrical and Computer Engineering, UBCCo-supervisorDr. Lutz Lampe, Professor, Electrical and Computer Engineering, UBCSupervisory Committee MemberiiAbstractGame theory and online optimization have a close relationship with eachother. In some literature, online optimization has been employed for solvinggame theory problems. Many accelerated algorithms are proposed for offlineoptimization problems. However, to the best of our knowledge, there is notenough work done to accelerate zero-order online optimization. The goal isto propose a Nesterov accelerated online algorithm with the hope that it willconverge to the Nash, with a fast convergence rate in Cournot games andQuadratic games. It is desired that this online algorithm also minimize theregret of a sequence of functions for both zero-order and first-order feedback.In potential Linear Quadratic (LQ) games, we also study the conver-gence of the policy gradient algorithms, a class of conventional reinforcementlearning methods. LQ games have applications in engineering. It has beenshown that using policy gradient algorithms by agents does not guaranteeconvergence to the Nash equilibrium. However, in the LQR problem, whichis essentially a one-player LQ game, the policy gradient converges to theoptimum. In this work, we show that using policy gradient algorithms leadsto convergence to Nash equilibrium in potential LQ games. Additionally, weidentify the characteristics of potential games in both open-loop and closed-loop settings. We will demonstrate that the class of closed-loop potentialgames is generally trivial, and if we put restrictions on players’ actions, wecan have non-trivial potential games too.iiiLay SummaryOptimization in a multi-agent and a single-agent environments have somesimilarities and differences. In a multi-agent setting, due to the presenceof other agents, co-operations and competitions might help us or hold usback from getting to the optimum point. This thesis works on studyingand developing methods to lead the agents to their desired stable point.In this work, we specifically narrow our focus on convex games and LinearQuadratic games.ivPrefaceThis thesis is an original, unpublished work by the author, Alireza AlianPorzani. The basis of this thesis is unpublished work supervised by MaryamKamgarpour. The second chapter, Accelerated Algorithms in games, waswritten with Mohammad Amin Roohi. The mathematical analyzes in part2.3 and 2.4 is done by him. And the third chapter, LQ games, was writtenwith Sara Hosseinirad. To be more precise 3.3.1 is completely done by her.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . 31.3 Problem Settings . . . . . . . . . . . . . . . . . . . . . . . . . 31.3.1 Game and Converging to the Nash . . . . . . . . . . 31.3.2 LQ Games . . . . . . . . . . . . . . . . . . . . . . . . 52 Accelerated algorithms in games . . . . . . . . . . . . . . . . 82.1 Preliminaries for Online algorithms and games . . . . . . . . 82.2 Algorithm for noisy gradient feedback . . . . . . . . . . . . . 102.3 3-stage online Nesterov method . . . . . . . . . . . . . . . . 142.4 2-stage online Nesterov method . . . . . . . . . . . . . . . . 202.4.1 Quadratic Games . . . . . . . . . . . . . . . . . . . . 252.5 Conclusion and Summary . . . . . . . . . . . . . . . . . . . . 292.6 Next steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 LQ games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.1 Review of the definitions . . . . . . . . . . . . . . . . . . . . 323.1.1 Dynamic System . . . . . . . . . . . . . . . . . . . . . 32viTable of Contents3.1.2 Quadratic Cost Function . . . . . . . . . . . . . . . . 333.1.3 Stochasticity in LQ games . . . . . . . . . . . . . . . 363.1.4 Potential Games . . . . . . . . . . . . . . . . . . . . . 363.2 An examples of LQ game . . . . . . . . . . . . . . . . . . . . 383.3 Potential games and their Conditions . . . . . . . . . . . . . 393.3.1 Convergence of Potential LQ games . . . . . . . . . . 393.3.2 Open loop potential LQ games . . . . . . . . . . . . . 403.3.3 Closed loop potential LQ games . . . . . . . . . . . . 423.3.4 Special cases of closed-loop . . . . . . . . . . . . . . . 473.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524 Conclusion and Future works . . . . . . . . . . . . . . . . . . 53Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54AppendicesA Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57viiList of Tables2.1 We present the regret order of different online algorithms inthis table. All these functions are differentiable and smooth.The best regret rate can be achieved without strong convexityO(√T ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30viiiList of Figures2.1 Gradient descent and accelerated solution . . . . . . . . . . . 262.2 Gradient descent and accelerated solution . . . . . . . . . . . 272.3 Gradient descent and accelerated solution . . . . . . . . . . . 272.4 Convergence Trajectories . . . . . . . . . . . . . . . . . . . . 282.5 Convergence Trajectories . . . . . . . . . . . . . . . . . . . . 293.1 Closed loop and open loop flowchart . . . . . . . . . . . . . . 343.2 Convergence Trajectories . . . . . . . . . . . . . . . . . . . . 503.3 Trivial Closed Loop Potential . . . . . . . . . . . . . . . . . . 513.4 Special Potential Case . . . . . . . . . . . . . . . . . . . . . . 52ixAcknowledgementsFirst of all, to my parents and my sister, who warmly supported me through-out my journey away from home. They were always available to me, evenfrom thousands of miles away. Without their help, I would not be here theplace I am.To my supervisor, Dr. Maryam Kamgarpour, who supported me through-out this long process. Even though we were working in different time zones,and she had lots of personal and professional tasks in her life, she alwayshelped me with feedback that shed light along my research path.To Dr. Lele Wang, who was responsible for being my formal supervisorand her helpful reading group. She always lifted my spirit and helped mewhen I had a meeting with her. To my dear friend and lab mate, MohammadAmin Roohi, who was an important part of my trip to Canada and doingthis research.To my friend and group mate, Sara Hosseinirad, who always helped mewith her very helpful comments throughout this work. She has made thiswork a lot better with her work and feedbacks that she provided to me.To my friend and lab mate, Kai Ren, who kept following my progress andprovided feedbacks during our meetings.xChapter 1IntroductionGame theory studies mathematical models of rational agents when theyhave strategic interactions [19]. It comes into use whenever we have severalagents in our environment, and we want to understand the behavior theyshow to increase their utility or minimize their loss. We may see applica-tions of game theory in economics where there are multiple rational agentsinvolved and strategical scenarios such as supply and demand markets andauctions. Game theory also has many applications in engineering, wherethe goal is to control a system in the presence of a disturbance, which isseen as an adversary agent. Game theory can also come in handy when wewish to optimize several scalar functions at the same time (multi-objectiveoptimization) [18].On the other hand, online optimization is popular in computer scienceand is the study of optimizing an unknown time-varying function. As thetarget function is not constant over time, optimization might seem meaning-less because we can’t do optimization for every single time step. Moreover,optimization may seem unreasonable as the function is unknown, so thatwe cannot know the optimal point in every time step and compute it. Toovercome this problem, regret is used as a means to see how well the on-line algorithm is performing. Regret is a function that evaluates the overallproximity of our selected points to the best single point one could choose inhindsight. In chapter two, we introduce the definition of regret that is usedin our work.Game theory and online optimization are strongly connected while hav-ing their own differences. In a game, each player is optimizing a functionthat is also a function of other players’ actions, so it changes when otherplayers decide to change what they are playing. Thus, we can see that eachplayer is solving an online optimization problem. Moreover, in online opti-mization, we are interested in having a sublinear regret (which will be talkedabout later on) because it is reasonable to expect that our overall payoff isnot much worse than the case we select the best-fixed point [16]. An onlinealgorithm that has a sublinear regret is called a no-regret algorithm. Con-trary to many optimization problems, where it is allowed to assume that11.1. Motivationthe first order or higher orders of feedback are provided to us, in games it isusually assumed that zero-order feedback is given because we can only askfor the value of the function for one extra point at each step, which is morerealistic.1.1 MotivationAs opposed to the conventional optimization problems, in games, we areinterested in converging to the Nash equilibrium instead of finding a pointthat optimizes one single function. The goal is to find algorithms that theplayers that are participating in the game employ, and as an outcome, theyreach the Nash equilibrium. In games, it is not enough that each player playsa no-regret algorithm because there are examples where if all the playersemploy a no-regret algorithm, the player’s actions may cycle in perpetuity[15, 28] and never converge to the Nash. It is also demonstrated that no-regret algorithms lead to the min-max optimal solution for the class of zero-sum games [6], demonstrating that if all players use a no-regret algorithm,their actions will converge to the Nash equilibrium, and the convergencerate depends on the regret of the algorithm that is used, i.e., the smaller theregret is, the faster the convergence to the Nash.Generally, to the best of our knowledge, there has been little work done toimprove the convergence rate of players’ actions to the Nash equilibrium [5].Vaswani et al. [25] tried to use a Nesterov algorithm to accelerate stochasticoptimization, and they were able to obtain a convergence guarantee with aproof of rate. Nesterov Algorithms were not used in games or online learningin any of the works mentioned above. The motivation is to change NesterovAlgorithms to online algorithms to have a better game convergence rate.In addition, there is a further convergence issue that we will addressin this thesis. Here we are given a family of algorithms, Policy Gradient,used mainly in reinforcement learning. In a single agent mode, [4] foundconvergence guaranteed under some conditions. However, [13] showed thatin a multi-agent setting, there exist examples where using a policy gradientleads to cycling around the Nash equilibrium. We also know that the classof potential games behaves like a single-player system. Finding the class ofpotential LQ games and determining whether or not they have a convergenceguarantee is motivating.21.2. Thesis Organization1.2 Thesis OrganizationIn the rest of this chapter, we bring the basic concepts, mathematical def-initions, and the formulation of our problems into a simple mathematicalform. Furthermore, we go over some of the most relevant works on the topicand their outcomes to see what has been done and what has been lackingin this field.In Chapter 2, we focus specifically on accelerated algorithms, go throughthe concepts underlying them, extend them to online optimization, and seehow well they work there. We present our accelerated online algorithms andanalyze their performance when players of a game follow them to find theiroptimal actions. We are particularly interested when they are used in gamesbecause acceleration has not previously been employed in them.Chapter 3 discusses the problems that may occur in a multi-agent LQsystem and studies a subset of such games where policy gradient methodswill safely ensure actions converge to Nash equilibrium. We demonstratehow potential games can show single-player behavior and identify the simplerLQ games that are potential. We also raise some conjectures about thegeneral form of the potential LQ games. The last chapter summarizes theresults and draws conclusions about what is contributed to this field, theupcoming questions, and possible future work in this area.1.3 Problem Settings1.3.1 Game and Converging to the NashIn a game, there are N players, each with a utility function. For example,the utility function of player i is fi(x) = fi(xi;x−i) : X = X1× · · · ×XN →R, where x−i = (x1, . . . , xi−1, xi+1, . . . , xN ), xj ∈ Xj where Xj is set ofavailable actions for player j. The trio of (N, f,X) defines a game. If theplayers are rational, which we assume they are, they will aim to maximizetheir utility function.Example: Quadratic games are defined as the games with the followingcost function (Negative of the utility function) to the players:fi(xi, x−i) =12xTi Γiixi + xTi giΓi,−ix−i + xTi + hi(x−i). (1.1)with Γii ≻ 0 and xi ∈ Rdi .As we mentioned in the example above, players may have cost functionsinstead of utility functions; in other words, rational players wish to mini-31.3. Problem Settingsmize the given function instead of maximizing it. These two problems areequivalent because we can use the old trick of having a cost function withthe value of a negative utility function.argminxf(x) = argmaxx−f(x) (1.2)Example: In a matrix game, the utility function can be written inmatrix form. For example, consider a two-player game, where each playercan play one action 1 or 2. The associated utility function to the players isshown in the following matrix:F =[(1,−1) (3,−3)(−2, 2) (−4, 4)]. (1.3)Fi,j , where i, j ∈ {1, 2} is the corresponding utility pair for our players,when the first player plays i and the second player plays j. For exampleif first player plays 1 and the second player plays 2, the first player will berewarded by 3 and the second player will be rewarded by −3.By paying attention to the utility function in 1.3, one can realize thatthe sum of utilities in each scenario is zero. This family of games where thesum of utilities is zero are called zero-sum games. Another notable notein 1.3 is that if both players play action 1, they do not have any motivationto change their actions. In other words, if only one of them single-handedlyattempts to change its action, it will get a lower reward. It implies that theyare in an equilibrium called Nash Equilibrium.Definition 1.3.1. Nash equilibrium is called a choice of actions (x∗1, . . . , x∗N ) ∈ΠNi=1Xi = X that satisfies the following inequalities. For every xi ∈ Xi andfor all i ∈ {1, 2, . . . , N}, we have:fi(x∗1, . . . , x∗i−1, xi, x∗i+1, . . . , x∗N ) ≤ fi(x∗1, . . . , x∗i−1, x∗i , x∗i+1, . . . , x∗N ). (1.4)Definition 1.3.2. Concave (Convex) games are the games where each player’sset of action are convex and also fi(xi, x−i) is concave (convex) with respectto xi.Examples of convex games are quadratic games are introduced earlier.Example: Cournot game is defined as an N player game with payofffunction of player i as fi(x) = p(∑Nj=1 xj)xi − Ci(xi), xi ≥ 0. In the afore-mentioned formula, p(.) represents the product’s market price, which is afunction of the product’s global supply in the entire market, whereas Ci(.)represents the product’s production cost for player i [24].Under the following assumptions on p(.) and Ci(.), Cournot games areconcave and admit unique Nash equilibrium.41.3. Problem Settings1. p(.) is concave, twice differentiable, p(0) > 0, and strictly decreasingwhen p(x) > 0.2. Ci are convex, strictly increasing and twice differentiable with p(0) >C ′i(0)f ′′i (x) = p′′(∑xj)xi + 2p′(∑xj)− C ′′i (xi) < 0.As a result, as shown above, fi(x) is concave in xi for all i, implying thatthe game is concave.Definition 1.3.3. A game is monotone if it satisfies the following for x, x′ ∈X:⟨m(x)−m(x′), x− x′⟩ ≤ 0, (1.5)where m(x) = ∇1f1(x)...∇NfN (x) is the game map, and the equality happens onlyif x = x′.There is a famous result that monotone concave games will go to theirunique Nash equilibrium when players use gradient methods to optimizetheir actions. However, with the mentioned assumptions, we may not havea monotone concave Cournot game, so the former result does not implyanything.Shi and Zhang [24] proved that employing no-regret algorithms by theplayers leads to convergence in measure to Nash equilibrium. Convergencein measure means that the sequence of actions will converge to optimalactions with the probability of 1.Definition 1.3.4. Let µ be a measure on N, convergence in measure of atto a means that ∀ϵ > 0, limt→∞ µ(∥at − a∗∥ > ϵ) = 0 [24].1.3.2 LQ GamesA Linear Quadratic (LQ) optimization problem is defined as minimizing aloss function of∑Tt=0 ctxt.ut = xTt Qxt + uTt Rut (quadratic cost), where xtis the state of the system, and ut is the input to the system at the time t.51.3. Problem SettingsAnd the dynamics of this system is linear with respect to states and inputs(actions). xt+1 = Axt +But + wt, where wt represents the noise at time t.mintf∑t=0xTt Qxt + uTt Rut, (1.6)such that xt+1 = Axt +But + wt.This game can have different properties depending on the length of thetime horizon. Dynamic games are usually divided into these two classes:• Finite Horizon LQ System: A LQ system is called a finite horizonif tf <∞.• Infinite Horizon LQ System: A LQ system is called an infinitehorizon if tf = ∞. It is proven [2] that if A and B are such that theminimum cost is finite, the optimal play for such closed-loop games arein the form of ut = −Kxt. The coefficient K is derived from algebraicRiccati Equation. In this class of problem we are also concerned ofstability, i.e. if we choose coefficients K in a careless way, as the costfunction is an infinite series, we may end up with an unbounded costfunction.LQ systems can also be divided into the following categories:• A system with known parameters: In this setting, we are givenwith the all parameters such as Q, R, A, B, and to achieve the optimalplay, we can use Algebraic Riccati Equations written bellow [1]P ∗tf = Qtf (1.7)P ∗t = Qt +ATt (P∗t+1 − P ∗t+1Bt(BTt Pt+ 1∗Bt +Rt)1BTt P ∗t+1)At, (1.8)K∗t = (Rt +BTt P∗t+1Bt+1)−1BTt P∗t+1At. (1.9)• A system with unknown parameters: In this setting, we want tooptimize a system without knowing the parameters. This problem isalso known as the model-free LQ system. When we play the input K1(or u1 in an open-loop setting), we get the feedback Ji(x,K1) (the lossfunction). One common way to approach an optimal solution is to usePolicy Gradient (PG) methods.61.3. Problem SettingsIt is proven that under mild assumption, in the infinite horizon LQ systemsPG will give us the global optimum point [13].The introduced LQ settings above can be extended to a multi-agentsetting and be seen as a game. A LQ game is defined as an N playerdynamic game, with the following cost functions:Ji(x, u) =tf∑t=0xTt Qixt + uTi,tRiui,t, (1.10)andxt+1 = Axt +N∑i=1Biui,t + wt. (1.11)The Nash can be calculated by the following coupled Algebraic Riccati Equa-tion [7]:P ∗i,t = Qi,t + (K∗i,t)TRi,tK∗i,t + (At −N∑j=1Bj,tK∗j,t)TP ∗i,t+1(At −N∑j=1Bj,tK∗j,t),(1.12)K∗i,t = (Ri,t +BTi,tP∗i,t+1Bi,t+1)−1BTi,tP∗i,t+1(At −N∑j=1,j ̸=iBj,tKj,t).(1.13)Mazumdar [13] showed that, in a multi-agent LQ system, there is noguarantee of convergence to Nash using PG. However, in zero-sum LQ games[27] there is a convergence guarantee. There is a class of games called Po-tential games, which can behave like a single-player game. As we have aconvergence guarantee in the single-player mode, it motivates us to identifysuch a class of games and study if potential LQ games converge to theirNash equilibrium.7Chapter 2Accelerated algorithms ingamesWe present three new accelerated online optimization algorithms, adaptedfrom the Nesterov Accelerated algorithms in offline optimization, by settingthe parameters, and determine their regret. The goal is to speed up conver-gence in games that feature a convex set of actions. The online algorithmsthat are introduced in this chapter are inspired by non-online Nesterov algo-rithms that already exist but have never been used in an online algorithm.Additionally, we demonstrate through simulations that applying these algo-rithms speeds up convergence in quadratic and Cournot gamesIn games, from each individual’s perspective with utility function ofui(xi,t;x−i,t), if we restrict its domain to his controllable actions, the pay-off would be a time-varying function ft(xi) = ui(xi,t;x−i,t). It means thateach player is performing some online optimization. In order to acceleratethe convergence in the game, we try to use accelerated algorithms in onlinesetting and hope that when the players are using the new algorithms, theconvergence speed improves.2.1 Preliminaries for Online algorithms andgamesA function f(x) : D → R is called L-Lipschitz continuous if:|f(x)− f(y)| ≤ L∥x− y∥2 ∀x, y ∈ D, (2.1)and it is calledM -smooth if the gradients∇f(x) areM -Lipschitz continuous,i.e.,∥∇f(x)−∇f(y)∥2 ≤M∥x− y∥2. (2.2)Similarly we call a convex function µ−strongly convex if:µ∥x− y∥2 ≤ ∥∇f(x)−∇f(y)∥2, (2.3)82.1. Preliminaries for Online algorithms and gamesfor every x, y ∈ D. In the above definitions L,M, µ > 0. Besides M -smoothness and µ−strongly convex condition for convex functions, respec-tively are equivalent to:0 ≤ f(x)− f(y)−∇f(x)⊤(x− y) ≤ M2∥x− y∥22. (2.4)f(x)− f(y) ≤ ∇f(x)⊤(x− y)− µ2∥x− y∥22. (2.5)Definition 2.1.1. [8] Let A be a deterministic algorithm for online convexoptimization (OCO), which at each time step t, selects action xt ∈ X , whereX is the set of possible actions. After xt is selected, algorithm incurs a costof ft(xt). For all t, ft is unknown and chosen by an oblivious adversary. Weassume all the payoff functions f1, . . . , fT ∈ F , where F is the set of boundedfunctions. So, after T iterations, the total cost collected by algorithm Ais∑Ti=1 ft(xt). In addition, the total cost of a static feasible action x0 is∑Ti=1 ft(x0). We formally define the regret of A after T iterations as:RegA(T ) =T∑t=1ft(xt)−minx∈XT∑t=1ft(x). (2.6)Also, in case the algorithm is non-deterministic, we generalize the defi-nition regret by taking an expectation over uncertainties:RegA(T ) = E[T∑t=1ft(xt)]−minx∈XT∑t=1ft(x).Intuitively, an algorithm performs well if its regret is sublinear as a func-tion of T , i.e., RegA(T ) = o(T ), since this implies that on the average thealgorithm performs as well as the best fixed strategy on the hindsight. Inthis case, we say A is a no-regret algorithm.In convex offline optimization, gradient descent is the most commonway to get the optimum point. xt+1 = xt − ηt∇f(xt) is the update rule.The problem with this algorithm is that, the rate of convergence is slow,i.e. O(1/t). That is, f(x(t) − f(x∗) is decreasing proportionally to 1/t.To address this problem, there are accelerated algorithms such as PolyakHeavy Ball [22] or Nesterov Methods [20]. The update rules for the Nesterovmethod are as follows:{xt+1 = yt − ηt∇f(yt)yt+1 = xt+1 +tt+3(xt+1 − xt)This algorithm and its variant to an online optimization algorithm are usedto accelerate game convergence.92.2. Algorithm for noisy gradient feedback2.2 Algorithm for noisy gradient feedbackHere we try to solve an online optimization problem with first-order feed-back, with Nesterov’s accelerated method 1, under the assumption of boundedvariation of objective functions. In other words, we are trying to minimizefunctions ft(x), with the property that ”they change slowly” at each step.Formally we can write:For each t here exist a ϵt such that for all x we have:|ft+1(x)− ft(x)| ≤ ϵt, (2.7)where ϵt is fairly small. Our motivation for this assumption comes from thefact that we will use such an algorithm in games, and as cost functions thatwe are considering in games are not changing and they are smooth, such anassumption can be realistic.We also assume that for all ft and all x (strong growth with additivenoise):Ezt ∥∇ft(xt, zt)∥2 ≤ ρ∥∇ft(xt)∥2 + σ2t . (2.8)Our first proposed online algorithm is as follows:Algorithm 1 Accelerated Online Nesterov1: Starting from w0, ν0 and arbitrary point ζ02: for k = 1, 2, . . . , T do3: Update wk+1 = ζk − η∇fk(ζk, zk)4: Update ζk = αkνk + (1− αk)wk5: Update νk+1 = βkνk + (1− βk)ζk − γkη∇fk(ζk, zk)6: end forThis is fully motivated by [25], where they used such an algorithm toimprove stochastic gradient descent. We extended their algorithm for acase where the function is not constant and is time-varying. In the followingsection, we will see how we can reduce this algorithm to an online zero-orderalgorithm.In addition to the above assumptions, we assume the followings:• Strong convexity and smoothness: Here, we assumed that ourfunctions µ−strongly convex and L−smooth.• Decreasing variance: We also assume that the running sum of vari-102.2. Algorithm for noisy gradient feedbackances is sublinear as well, i.e,,T∑k=0k∑j=0σ2j = o(T ). (2.9)• We also assume that our functions are twice differentiable.where σ2j refers to the noise of gradient estimator at the jth step of thealgorithm. The decreasing variance assumption in games is not unrealis-tic because, as we approach Nash, players have less motivation to deviatefrom their current actions, and the gradient query would be less noisy. Atthe end of this section, we will see that our gradient estimator’s noise canbe controlled by making the search area smaller, which implies that ourassumption can make sense.Theorem 2.2.1. If the following conditions hold:γk =1ρ.[1 +βk(1− αk)αk], (2.10)αk =γkβkb2k+1ηγkβkb2k+1η + a2k, (2.11)βk ≥ 1− γkµη, (2.12)ak+1 = γk√ηρbk+1, (2.13)bk+1 ≤ bk√βk, (2.14)b2k+1γ2kηρ = a2k+1, (2.15)b2k+1γkη − a2k+1 + a2k = 0, (2.16)η ≤ 1ρL, (2.17)the regret bound for algorithm 1 is:Reg(T ) ≤T∑j=1[12b2jγ2j−1ηρ(2a20C1 + b20C2+j−1∑k=1[2b2k+1γ2k+1η2σ2k + 4b2k+1γ2k+1ηρϵk])]. (2.18)where C1 = f0(x0) − f0(x∗) and C2 = ∥x0 − x∗∥2 and x∗ is the best actionplayed on the hindsight. Proof in Appendix A.112.2. Algorithm for noisy gradient feedbackLemma 2.2.2. : If we run algorithm 1 with parameters bellow, if∑Tk=0∑kj=0 ϵj =o(T ), then we get a sublinear regret.η = 1/(ρL), γ = 1/√ηµρ,γk =1√µηρ, βk = 1−√µηρ, (2.19)ak =1βk/2k, bk =√µβk/2k.Proof.Reg(T ) ≤ o(T∑k=11b2kγ2k−1[a20ρηC1 +b202ρηC2]+T∑k1b2k+1γ2kk∑i=0[γ2i b2[i+1](σ2i + ϵi)])= o(T∑kβk+1k+1µηρµ[a20ρηC1 +b202ρηC2]+T∑k1b2k+1γ2kk∑i=0[γ2i b2[i+1](σ2i + ϵi)])≤ o(T∑kβk/+1k+1 µηρµ[a20ρηC1 +b202ρηC2]+T∑kk∑i=0[σ2i + ϵi])= C3 + (o(T ) + o(T )) = o(T ) according to 2.9.Where C3 =∑Tkβk/+1k+1 µηρµ[a20ρηC1 +b202ρηC2]because it is a geometric series(βk was chosen to be constant).Where C3 =∑Tkβk/+1k+1 µηρµ[a20ρηC1 +b202ρηC2]because it is a geometric series(βk was chosen to be constant).Now we discuss how our results from previous theorems are related to thezero-order online optimization. Nesterov designed a two-point estimation ofgradient, which satisfies the strong growth with additive noise assumption[21].If f ∈ C0,0 (Lipschitz):Eu(∥gµ∥2∗) ≤ L2(d+ 4)2, (2.20)If f ∈ C1,1 (smoothness):Eu(∥gµ∥2∗) ≤µ22M2(d+ 6)3 + 2(d+ 4)∥∇f(x)∥2∗, (2.21)122.2. Algorithm for noisy gradient feedbackEu(∥gˆµ∥2∗) ≤µ28M2(d+ 6)3 + 2(d+ 4)∥∇f(x)∥2∗, (2.22)where in above expression gµ =f(x+µu)−f(x)µ .Bu, gˆµ =f(x+µu)−f(x−µu)2µ .Bu,fµ = Eu(f(x + µu)), u is a random vector distributed uniformly over theunit sphere in Rd, M is smoothness factor of f(x), and L is the Lipschitzconstant of f(x).For example, is smooth case gµ, the gradient estimator gives us ρ =2(d+ 4) and σ2 = µ22 L21(f)(d+ 6)3 in the equation 2.23. it implies that bymaking µ smaller with the rate of o(2−n), then 2.9 will be o(1). However,we should decrease µ moderately because numerical calculations could beproblematic if µ gets too small. In fact, at some point, we miss-estimate thegradient as 0, and our algorithm stops.Besides, the two-point gradient estimation is not a reasonable game as-sumption. Because players are constantly changing their actions and whenwe are sampling the function at different points, it is most likely that ourfunction is totally changed and our estimation is not valid anymore. Bylooking into eqs. (A.10) and (A.12) the gradient is achieved at the point ζk,and we assumed that we play the action wk. So if we try to use one of thetwo points used in 2.21, then we need to only have one query.As it’s mentioned earlier, in games, from each player’s perspective,they are solving an online optimization problem, where the functions thatthey are given are ft(xi) = ui(xi,t;x−i,t), which comes from a constantfunction ui(.). Thus, with the assumption that ui(.) is smooth, if the playersbegin to change their actions in very small amounts at some point, we have|ft+1(x)−ft(x)| ≤ ϵt, where ϵt is fairly small (with continuity assumptions).With this in mind, below we explain why we had the assumption of 2.7 andwe bring the intuition that we expect the gradient estimation to be less noisyas we approach the Nash.• We assumed that |ft+1(x)− ft(x)| ≤ ϵt. Although it is a valid condi-tion for all continuous functions defined over a compact set (note thatfunctions ft(.) are coming from one universal continuous function), itis important to express regret regarding such differences. Because,as we argued, when we are getting close to the Nash, the continuityof gradient implies that players tend to change their actions in smallamounts (as we assume that player’s are using gradient based algo-rithms), which leads to having smaller ϵt’s. As a result, we see itharmless to have this assumption, and more importantly, to introducethis difference bound so we can have it in the regret.132.3. 3-stage online Nesterov method• We expect our gradient queries to be less noisy as we get close toNash. Because same as the previous case, as we have the assumptionof twice differentiability of the cost functions, when we get close toNash (where gradient w.r.t each player’s action is zero), gradient ofthe cost function w.r.t players’ action is close to zero. It also meansthat players will change their actions slowly. It also means that thefunction ft(x) is close to ft+1(x), which is used to estimate the gradientso that we would have smaller noise σ2t .Next we calculate the optimization error of algorithm 1 for the deter-ministic and stochastic cases.Theorem 3.2: The algorithm 1 enjoys deterministic and stochasticoptimization error of:f(wT+1)− f∗ ≤ 12a2T+1(2a20ϕ0 + b20r20), (2.23)E f(wT+1)− f∗ ≤ 12a2T+1(2a20ϕ0 + b20 E[r20] +T∑k=1[2a2k+1σ2kηρ]). (2.24)respectively, wereϕk = E fk(wK)− f∗k (2.25)rk+1 = ∥νk+1 − w∗∥ (2.26)The terms above will converge to 0 and∑Tk=1σ2kηρ respectively.Proof: As we had in the proofE fT+1(wT+1)− f∗T+1 ≤12a2T+1(2a20ϕ0 + b20 E[r20]− b2T+1 E[r2T+1]+T∑k=1[2a2k+1σ2kηρ+ 4a2k+1ϵk] ).we assumed fk = f and therefore ϵk = 0. Replacing σ2 = 0 for stochasticcase we get the desired result.2.3 3-stage online Nesterov methodThis thesis presents a further three-stage online Nesterov algorithm withsublinear regret. It differs from the algorithm in the preceding section as a142.3. 3-stage online Nesterov methodresult of the different hyperparameters. To show that an online acceleratedalgorithm is a no-regret algorithm, we use the same idea as [11]. They usea 3-stage accelerated method for non-differentiable functions. We tried toshow that a 3-stage Nesterov accelerated method in an online setting is ano-regret for differentiable functions. After this step, we picked the simplestversion of the accelerated method in an online setting, called it the 2-stageaccelerated method, and showed it is also a no-regret algorithm for somespecific hyper-parameters.This section assumes that for any t ≥ 1, ft, ft is a convex, differen-tiable and L-smooth function. Also, we assume that each ft has a boundedgradient, i.e., for all x, ∥∇ft(x)∥2 ≤ G, where G ≥ 0. Now we want toprove that algorithm 2 is a no-regret algorithm. The idea is to bound theft(xt)− ft(x∗), where x∗ is the optimum point that we can choose in hind-sight. Based on the properties we assumed for ft we have, we can find anupper bound for ft(xt+1)− ft(x). Then, we try to find an upper bound forft(xt)− ft(xt+1) based on the updated policy. We do this to find an appro-priate upper bound for ft(xt)− ft(x). The following proofs are inspired by[11]. Lemma 2.3.1 is a famous lemma and it presents in other references.This algorithm is modified version of what is introduced in [11], and thealgorithm in the next section is completely novel. In [11], we do not haveany equivalent for Lemma 2.3.2 or Lemma 2.3.3, but we decomposed theirproof into these easier-to-follow lemmas to help the reader.For the following algorithms, the idea of the proof is to bound ft(xt) −ft(x). To make this upper bound, we introduced some lemmas to get anupper bound for ft(xt) − ft(x). At some steps, we got an upper bound forft−1(xt)−ft−1(x), and we needed to make finite variation assumption to getour desired upper bound. This helped us to get our bounds without finitevariation assumption.Algorithm 2 3 stage-accelerated Online Optimization1: Input: Sequences {0 < αt < 1} and {Lt} > L.2: Initialize z1 = y1.3: for t = 1, . . . , T do4: xt = (1− αt)yt−1 + αtzt−15: yt = xt − 1Lt∇ft−1(xt).6: zt = zt−1 − αt(xt − yt).7: end for152.3. 3-stage online Nesterov methodLemma 2.3.1. For t > 1, ft(x) can quadratically bounded from below asft−1(x) ≥ ft−1(yt) + ⟨∇ft−1(xt), x− xt⟩+ 2Lt − L2L2t∥∇ft−1(xt)∥2. (2.27)Proof. From smoothness of ft−1(x) we know:ft−1(yt) ≤ ft−1(xt) + ⟨∇ft−1(xt), y − xt⟩+ L2∥yt − xt∥2, (2.28)and from the updating rule, we know that yt − xt = − 1Lt∇ft−1(xt). As aresult, we have:ft−1(yt) ≤ ft−1(xt) + ⟨∇ft−1(xt),− 1Lt∇ft−1(xt)⟩+ L2L2t∥∇ft−1(xt)∥2(2.29)=⇒ ft−1(yt) ≤ ft−1(xt) + L− 2Lt2L2t∥∇ft−1(xt)∥2 (2.30)=⇒ ft−1(yt)− L− 2Lt2L2t∥∇ft−1(xt)∥2 ≤ ft−1(xt). (2.31)In addition, from convexity of ft−1(x) we know:ft−1(x) ≥ ft−1(xt) + ⟨∇ft−1(xt), x− xt⟩, (2.32)now, we substitute ft−1(xt) with the lower bound we found in equation (1.4),then we have:ft−1(x) ≥ ft−1(yt) + ⟨∇ft−1(xt), x− xt⟩+ 2Lt − L2L2t∥∇ft−1(xt)∥2. (2.33)Lemma 2.3.2. From the update rule of zt, we can say:zt =x Vt(x) ≡ ⟨∇ft−1(xt), x− xt⟩+ Lt2αt∥x− zt−1∥2.Proof. By setting the gradient of Vt(x) equal to zero, we have:∇ft−1(xt) + Ltαt(x− zt−1) = 0 =⇒ x = zt−1 − αtLt∇ft−1(xt), (2.34)and from the update rule of yt, we have ∇ft−1(xt) = Lt(xt − yt), and thisimplies argminx Vt(x) = zt−1−αt(xt−yt) and this completes the proof.162.3. 3-stage online Nesterov methodLemma 2.3.3. For any x and t ≥ 1, we have:ft−1(yt)− ft−1(x) ≤⟨∇ft−1(x), xt − zt⟩ − 2Lt − L2L2t∥∇ft−1(xt)∥ (2.35)− Lt2αt∥zt − zt−1∥2 + Lt2αt∥x− zt−1∥2 − Lt2αt∥x− zt∥2.Proof. From the definition of Vt(x), we can say it is a µ−strongly con-vex function where µ = Ltαt . Based on Lemma 2.3.3., we know zt in theargminx Vt(x). So, we can say:Vt(zt) ≤ Vt(x)− µ∥x− zt∥2 = Vt(x)− Ltαt∥x− zt∥2 (2.36)= ⟨∇ft−1(xt), x− xt⟩+ Lt2αt∥x− zt−1∥2 − Lt2αt∥x− zt∥2, (2.37)also, from Lemma 2.3.1 we know ⟨∇ft−1(xt), x− xt⟩ ≤ ft−1(x)− ft−1(yt)−2Lt−L2L2t∥∇ft−1(xt)∥2. So, using the later inequality and 2.37, we have:Vt(zt) ≤ ft−1(x)− ft−1(yt)− 2Lt − L2L2t∥∇ft−1(xt)∥2 (2.38)+Lt2αt∥x− zt−1∥2 − Lt2αt∥x− zt∥2,now if we put x = zt in the definition of the Vt(x), we have:ft−1(yt)− ft(x) ≤⟨∇ft−1(xt), xt − zt⟩ − Lt2αt∥zt − zt−1∥2 (2.39)− 2Lt − L2L2t∥∇ft−1(xt)∥2 + Lt2αt∥x− zt−1∥2 − Lt2αt∥x− zt∥2,Proposition 2.3.4. Suppose ∥∇ft(x)∥∗ ≤ g for any t ≥ 1. Then for anyx, we have:ft−1(yt−1)− ft−1(x) ≤ g22(1− αt)(Lt − L) +Lt2αt∥x− zt−1∥2 − Lt2αt∥x− zt∥2+(1− αt)2Lt − αt(1− αt)L2∥yt−1 − zt−1∥2 − Lt2∥yt − zt∥2.172.3. 3-stage online Nesterov methodProof. At first note that we have:⟨∇ft−1(xt), xt − zt⟩ − ∥∇ft−1(xt)∥22Lt= ⟨Lt(xt − yt), xt − zt⟩ − Lt∥xt − yt∥22=Lt2(xt − yt, 2(xt − zt)− ⟨xt − yt, xt − yt⟩) (2.40)Lt2(⟨xt − yt, xt + yt − 2zt⟩) = Lt2(∥zt − xt∥2 − ∥zt − yt∥2),(2.41)in addition, from the update rule of xt, we have xt = (1 − αt)yt + αtzt−1.So, we can say:∥zt − xt∥2 = ∥zt − (1− αt)yt − αtzt−1∥2 = ∥(1− αt)(zt − yt) + αt(zt − zt−1)∥2≤ (1− αt)2∥zt − yt∥2 + α2t ∥zt − zt−1∥2≤ (1− αt)∥zt − yt∥2 + αt∥zt − zt−1∥2≤ (1− αt)∥zt − yt∥2 + 1αt∥zt − zt−1∥2, (2.42)as a result, we have:⟨∇ft−1(xt), xt − zt⟩ − ∥∇ft−1(xt)∥22Lt≤ Lt2αt∥zt − zt−1∥2+Lt(1− αt)2∥zt−1 − yt−1∥2 − Lt2∥zt − yt∥2. (2.43)Now, if putting the later inequality in the Lemma 2.3.3, gives us:ft−1(yt)− ft−1(x) ≤ Lt(1− αt)2∥zt−1 − yt−1∥2 − Lt2∥zt − yt∥2 (2.44)− Lt − L2L2t∥∇ft−1(xt)∥2 + Lt2αt∥x− zt−1∥2 − Lt2αt∥x− zt∥2.(2.45)In addition, from the convexity of ft−1(x) we know:ft−1(yt−1)− ft(yt) ≤ ⟨∇ft−1(xt), yt − yt−1⟩. (2.46)From the Young’s inequality, for every a > 0 we know ⟨x, y⟩ ≤ ∥x∥22a + a∥y∥22 .So, by using Young’s inequality and considering a = (1 − αt)(Lt − L), we182.3. 3-stage online Nesterov methodcan say:ft−1(yt−1)− ft(yt) ≤ ∥∇ft−1(xt)∥22(1− αt)(Lt − L) +(1− αt)(Lt − L)2∥yt−1 − yt∥2(2.47)≤ g22(1− αt)(Lt − L) +(1− αt)(Lt − L)2∥yt−1 − yt∥2.(2.48)Besides, from the update rule of yt, we can say:∥yt−1 − yt∥2 = ∥(yt−1 − xt) + (xt − yt)∥2 = ∥αt(yt−1 − zt−1) + (xt − yt)∥2(2.49)≤ α2∥yt−1 − zt−1∥2 + (1− αt)2∥xt − yt∥2 ≤ α∥yt−1 − zt−1∥2(2.50)+11− αt ∥xt − yt∥2= αt∥yt−1 − zt−1∥2 + ∥∇ft−1(xt)∥2(1− αt)L2t. (2.51)By using 2.51 in 2.48, we have:ft−1(yt−1)− ft−1(yt) ≤ g22(1− αt)(Lt − L) +αt(1− αt)(Lt − L)2∥yt−1 − zt−1∥2+Lt − L2L2t∥∇ft−1(xt)∥2. (2.52)In the end, by adding the 2.52 to 2.47 we get the inequality of proposition.Theorem 2.3.5. By setting αt = a where 0 < a < 1 and Lt = aL√t− 1+L,we have:T∑t=1ft(xt)−T∑t=1ft(x∗) = O(√T ).Proof. We can easily check the result by using proposition 2.4.5 and takinga summation.It is apparent from the Theorem 2.3.5 that algorithm 2 is no-regret.Based on [24], in a game theoretic setting, if each player follows a no-regretalgorithm, we can guarantee they will converge (in measure) to the Nashequilibrium.192.4. 2-stage online Nesterov method2.4 2-stage online Nesterov methodAgain, we assume that for any t ≥ 1, ft is a convex, differentiable andL-smooth function. Also, we assume that each ft has bounded gradienti.e., for all x, ∥∇ft(x)∥2 ≤ G, where G ≥ 0.The goal is to prove algorithm 2 is a no regret algorithm. The ideais to bound the ft(xt) − ft(x∗), where x∗ is the optimum point that wecan choose in hindsight. Based on properties we assumed for ft, we willfind an upper bound for ft(xt+1) − ft(x). Then, we try to find an upperbound for ft(xt) − ft(xt+1) based on the update policy. These two givesus an appropriate upper bound for ft(xt)− ft(x). The following proofs areinspired by [11].Algorithm 3 2-stage Nesterov method in online setting1: Input: Parameters µt, ηt, x12: Pick y1 = x1.3: for t = 1, . . . , T do4: Observe the payoff function gradient ∇ft(yt).5: Update xt+1 = yt − ηt∇ft(yt).6: Update yt+1 = xt+1 + µt(xt+1 − xt).7: end forLemma 2.4.1. For any t ≥ 1,ft(xt+1)− ft(x) ≤ (L2− 1ηt)∥yt − xt+1∥22 +(yt − xt+1)T (yt − x)ηt, (2.53)where xt+1 and yt are corresponding variables in iteration t while we runningalgorithm 3.Proof. This lemma can be proved just by combining the convexity andL−smoothness definitions. From the convexity definition, we can say:ft(x) ≥ ft(yt) +∇ft(yt)T (x− yt) =⇒ ft(yt)− ft(x) ≤ ∇ft(yt)T (yt − x),(2.54)and since from the update rule, we have ∇ft(yt) = yt−xt+1ηt , we can say:ft(yt)− ft(x) ≤ (yt − xt+1)T (yt − x)ηt. (2.55)202.4. 2-stage online Nesterov methodFurthermore, from the L−smoothness definition, we have:ft(yt − ηt∇ft(yt))− ft(yt) ≤ ⟨∇ft(yt),−ηt∇ft(yt)⟩+L2∥ηt∇ft(yt)∥22 = (Lη2t2− ηt)∇ft(yt), (2.56)moreover, again from the update rule we have ∇ft(yt) = yt−xt+1ηt , so we cansay:ft(yt − ηt∇ft(yt))− ft(yt) ≤ (L2− 1ηt)∥yt − xt+1∥22. (2.57)Since xt+1 = yt − ηt∇ft(yt), if we add 2.57 to 2.55, we get:ft(xt+1)− f(x) ≤ (L2− 1ηt)∥yt − xt+1∥22 +(yt − xt+1)T (yt − x)ηt. (2.58)As we said earlier, we are aiming to bound ft(xt)−f(x). To that end, wetry to introduce an appropriate bound for ft(x)− ft+1(xt+1). To introducethis bound, We’re inspired by [8].Lemma 2.4.2. For any t ≥ 1 and α ≥ 0:ft(xt)− ft(xt+1) ≤ G22α+αµt2∥xt−1 − xt∥22 +α2(1− µt)∥yt − xt+1∥22. (2.59)Proof. from the convexity definition, we have:ft(xt)− ft(xt+1) ≤ ⟨∇ft(xt+1), xt − xt+1⟩. (2.60)By Young’s inequality, for any α > 0, we have:⟨∇ft(xt+1), xt − xt+1⟩ ≤ ∥∇ft(xt+1)∥222α+α2∥xt − xt+1∥22. (2.61)Now, since in 2.58 we have ∥yt−xt+1∥22, let us create a similar term here.By adding and subtracting yt, we have:∥xt − xt+1∥22 = ∥(xt − yt) + (yt − xt+1)∥22= ∥µt(xt − xt+1) + (yt − xt+1)∥22≤ µt∥xt − xt+1∥22 +11− µt ∥yt − xt+1∥22. (2.62)212.4. 2-stage online Nesterov methodNow, since ∥∇ft(x)∥ ≤ G for all t ≥ 1, if we substitute 2.62 in 2.61, we get:ft(xt)− ft(xt+1) ≤ G22α+aµt2∥xt−1 − xt∥22 +a2(1− µt)∥yt − xt+1∥22. (2.63)The next step, is to find an upper bound for (yt−xt+1)ηt (yt − x). To dothis, we use use an idea from [8]. Note that in [8], they talk about a 3-stagealgorithm and basically, we have different analysis here. But the ideas aresimilar.Lemma 2.4.3. For any t ≥ 1,ft(xt+1)− ft(x) ≤ (L2− 12ηt)∥yt − xt+1∥22 +12ηt∥x− yt∥22 −12ηt∥x− xt+1∥22.(2.64)Proof. Define:Vt(x) = ⟨yt − xt+1ηt, x− yt⟩+ 12ηt∥x− yt∥22. (2.65)Actually, Vt(x) is a1ηt-strongly convex function. Also, by setting its gradientequal to zero, we see that it’s minima is x = yt − ηt∇ft(yt). In fact, xt+1 isthe minima of Vt(x). From the definition of strong convexity, we can say:V (xt+1) ≤ Vt(x)− 12ηt∥x− xt+1∥22 (2.66)⟨yt − xt+1ηt, x− yt⟩+ 12ηt∥x− yt∥22 −12ηt∥x− xt+1∥22 (2.67). (2.68)Now by using Lemma 5.1., we can say:V (xt+1) ≤ ft(x)− ft(xt+1) + (L2− 1ηt)∥yt − xt+1∥22+12ηt∥x− yt∥22 −12ηt∥x− xt+1∥22, (2.69)Besides, from the definition we have Vt(x) = ⟨yt−xt+1ηt , x− yt⟩+ 12ηt ∥x− yt∥22.So, we can say:ft(xt+1)− ft(x) ≤ (L2− 12ηt)∥yt − xt+1∥22 +12ηt∥x− yt∥22 −12ηt∥x− xt+1∥22.(2.70)222.4. 2-stage online Nesterov methodLemma 2.4.4. For any t ∈ N, we have:1√1+ · · ·+ 1√t≤ 2√t− 1. (2.71)By induction we can prove this lemma.Proposition 2.4.5. For any t ≥ 1,ft(xt)− ft(x) ≤ G22(1− µt)( 1ηt − L2 )+µt(1− µt)( 12ηt − L2 )2∥xt−1 − xt∥22+12ηt∥x− yt∥22 −12ηt∥x− xt+1∥22. (2.72)Proof. In Lemma 2.4.2, put α = (1− µt)( 1ηt − L). Then we have:ft(xt)− ft(xt+1) ≤ G22(1− µt)( 1ηt − L)+µt(1− µt)( 1ηt − L)2∥xt−1− xt∥22 +(1− µt)( 1ηt − L)2(1− µt) ∥yt − xt+1∥22 (2.73)=G22(1− µt)( 1ηt − L)+µt(1− µt)( 1ηt − L)2∥xt−1 − xt∥22+ (12ηt− L2)∥yt − xt+1∥22. (2.74)Now if we add 2.74 to 2.70, we get:ft(xt)− ft(x) ≤ G22(1− µt)( 1ηt − L2 )+µt(1− µt)( 12ηt − L2 )2∥xt−1 − xt∥22+12ηt∥x− yt∥22 −12ηt∥x− xt+1∥22.(2.75)Theorem 2.4.6. If we assume that the diameter of the cost function’s do-main is at most D, by setting ηt =1√t+L2and µt =12t in algorithm 3, we geta no-regret algorithm.232.4. 2-stage online Nesterov methodProof. From the proposition 2.4.5, we have:ft(xt)− ft(x) ≤ G22(1− 12t)(√t)+12t(1− 12t)(√t+L22 − L2 )2∥xt−1 − xt∥22+√t+ L22∥x− yt∥22 −√t+ L22∥x− xt+1∥22.(2.76)Note that for any t ≥ 1, we have:G22(1− 12t)(√t)≤ G2√t, (2.77)12t(1− 12t)(√t+L22 − L2 )2∥xt−1 − xt∥22 ≤18√t∥xt−1 − xt∥22. (2.78)Also, from the update rule, we have yt = xt+µt(xt−xt−1). So, we can say:∥x− yt∥22 = ∥x− (xt + µt−1(xt−1 − xt))∥22 (2.79)= ∥(x− xt) + µt−1(xt − xt−1)∥22 ≤ µt−1∥xt−1 − xt∥22+11− µt−1 ∥x− xt∥22 (2.80)≤ µt−1(∥xt−1 − xt∥22 +11− µt−1 ∥x− xt∥22) + ∥x− xt∥22 (2.81)≤ µt−1(∥xt−1 − xt∥22 +11− µ0 ∥x− xt∥22) + ∥x− xt∥22. (2.82)Putting all these together, we can say (the assumption the diameter of costfunction’s domain is at most D, means that ∥xt−1 − xt∥22 ≤ D2 and ∥x −xt∥22 ≤ D2, and we consider µt−1ηt ≤ 1√t , note that based on value of L,there is k > 0 such that µt−1ηt ≤ k√t , and the value of k is not importantfor the rate regret that we are looking for):ft(xt)− ft(x) ≤ G2√t+18√tD2 +1√t(D2 +11− µ0D2) + (12ηt+1− 12ηt)D.(2.83)242.4. 2-stage online Nesterov methodFinally, we can say:T∑t=1ft(xt)−T∑t=1ft(x∗) ≤ G2(2√T − 1) + D28(2√T − 1)+ (D2 +11− µ0D2)(2√T − 1) + ( 12ηT+1− 12η0)D= O(√T ). (2.84)And this means we have a no-regret algorithm. Moreover, the regret it inthe order of O(√T ).2.4.1 Quadratic GamesThe goal is to study the behavior of gradient-based algorithms, includ-ing gradient descent and our accelerated algorithm, on different games likeQuadratic games, which were introduced in [12]. We want to simplify it toa deterministic game and study its equilibrium.With the following cost function to the players:πi(ai, a−i) =12aTi Γiiai + aTi Γi,−ia−i + aTi gi + hi(a−i), (2.85)with Γii ≻ 0 which gives:∇iπi(ai, a−i) = Γiiai + Γi,−ia−i + gi.We can re-write Γi,−ia−i =∑j ̸=i Γijaj and define ϕi =∑j Γijaj . Then thefirst order equilibrium condition gives:∇iπi(a∗i , a∗−i) = Γiia∗i +∑j ̸=iΓija∗j + gi = 0, (2.86)= Γiia∗i + (ϕi − Γiia∗i ) + gi = 0. (2.87)Consecutively:ϕi = −gi∑jΓija∗j = −gi, ∀i. (2.88)Solving this set of linear equations will gives the solutions of Nash equilibria.Γ11 . . . Γ1N... . . . ...ΓN1 . . . ΓNN a∗ = −g,252.4. 2-stage online Nesterov methodwhere a∗ is the stacked vector of player’s Nash actions and g is a stackedvector of gi’s. From this, we conclude that the condition for having a uniqueNash is to have matrixΓ11 . . . Γ1N... . . . ...ΓN1 . . . ΓNN full rank.To study the case where each player uses the gradient descent algorithmto optimize their cost functions, we haveai,t+1 = ai,t − ηt∇iπi(ai,t, a−i,t), (2.89)= ai,t − ηt(Γiiai,t +∑j ̸=iΓija−i,t + gi) (2.90)= ai,t − ηt(∑jΓijaj,t + gi), (2.91)at+1 = (I − ηtΓ11 . . . Γ1N ,... . . . ...,ΓN1 . . . ΓNN)at − ηtg. (2.92)which implies that the necessary condition for this dynamic system’s stabil-ity is eig(I − ηtΓ11 . . . Γ1N... . . . ...ΓN1 . . . ΓNN) is located inside the unit circle.Simulations:In this part, we perform simulations to evaluate the speed of convergenceof our algorithm when it is used on a quadratic game. Also, in this part, werepeat this simulation on 3 different randomly generated quadratic games.Here we randomly select matrices Γii’s and Γij with i > j and then set Γji =ΓTij to make the big matrix Γ symmetric. As we see in the following graphs,the momentum method converges faster than gradient descent.(a) without momentum (b) with momentumFigure 2.1: Gradient descent and accelerated solution262.4. 2-stage online Nesterov method(a) without momentum (b) with momentumFigure 2.2: Gradient descent and accelerated solution(a) without momentum (b) with momentumFigure 2.3: Gradient descent and accelerated solutionThrough the simulations, we observed that accelerated algorithms enjoybetter convergence in games. Let us take a look at an example of Cournotgame.Setup: We consider a four-player Cournot games with different marketprice and individual cost functions. Consider a Cournot game where p(x) =1− (∑i xi), and a linear production cost function is Ci(xi) = 0.05xi.This game proceeds as follows. Every player simultaneously picks a pro-duction level at each time step, and then the market price is determined bytheir joint production and broadcast back to all players. Then, each playercalculates his payoff, πi(xi) = Ptxi−Ci(xi), where Pt is the market price atiteration t. The Nash equilibrium of this games is x∗1 = x∗2 = x∗3 = x∗4 = 0.19.Also, since the payoff function is differentiable, one can confirm this by set-ting the derivative of payoff equal to zero and validating this value for NE.Below, we referrer the reader an accelerated method’s convergence trajec-tory compared to Online gradient descent. (step size in both algorithms wasset to the same value)272.4. 2-stage online Nesterov method(a) Algorithm 1 (b) Algotithm 3(c) Online Gradient Descent algo-rithmFigure 2.4: Convergence TrajectoriesAlso, we repeat the same example for the case we do not have accessto the gradient. We used the finite difference method for estimating thegradient. Mathematically, we considered:∂f∂xi=f(x+ δei)− f(x)δ, (2.93)where ei denotes the vector with a 1 in the i−th coordinate, 0’s elsewhere,and δ is a positive number. We chose different values for δ, and below, youcan see the convergence trajectories:282.5. Conclusion and Summary(a) Algotithm 3, delta = 0.1 (b) Algotithm 3, delta = 1(c) Online Gradient Descent algo-rithm, delta = 0.1(d) Online Gradient Descent algo-rithm, delta = 1Figure 2.5: Convergence Trajectories2.5 Conclusion and SummaryNesterov methods are well known accelerated methods. Nesterov showedin an offline setting they enjoy a fast convergence rate [20]. We can getO( 1t2) rate of convergence, which is much faster than gradient descent. Wedeveloped these algorithms in an online setting and proved that for somespecial hyper-parameters, they become no-regret algorithms. To the best ofour knowledge, it has not been shown that the 2-stage Nesterov algorithmin an online setting is a no-regret algorithm. As for the 3-stage algorithmin the online setting, in [8], a proof presented for cases that cost functionsare made of a differentiable and a non-differentiable function showed that byusing sub-gradient, we can get a no-regret algorithm for some especial hyper-parameters. By employing our algorithm in Cournot games and Quadraticgames, we observed faster convergence compared to Online Gradient De-scent. We also extended the Nesterov accelerated algorithm for stochasticsettings to online settings, in which we use zero-order estimation for the gra-dient. Under certain assumptions, in a game theoretic setting, if all players292.6. Next stepsAlgorithm OracletypeStrongcon-vexityFinitevaria-tionBoundedGradi-entRegret order OptimizationerrorAlgorithm1Noisyfirstorderor zero-orderYes Yes No O(∑Tk ∑ki=0[σ2i+ϵi])O(βT )Algorithm2First or-derNo No Yes O(√T ) O(1t )Algorithm3First or-derNo No Yes O(√T ) O(1t )OnlineGradientDescent[8]First or-derNo No Yes O(√T ) O(1t )OnlineGradientDescent[8]First or-derYes No Yes O(log(T )) O(exp(−t))Table 2.1: We present the regret order of different online algorithms in thistable. All these functions are differentiable and smooth. The best regretrate can be achieved without strong convexity O(√T ).follow no-regret algorithms, they converge to the Nash equilibrium [24]. Insimulations, we saw that if the player follows these accelerated methods,they converge faster to the Nash equilibrium in comparison to the case thatthey follow the Online mirror descent algorithm suggested by Shi [24].2.6 Next stepsIn the first section, we derived regret in terms of o(∑Tk∑ki=0[σ2i + ϵi]). Asfor the next, one can find the corresponding regret in terms of T , whenthe algorithm is used on Cournot games defined in [24]. It is also remainsto extend algorithm 2 or 3 to a zero-order algorithm and then compare itto algorithm 1 performance in practice. Moreover, a theoretical proof for302.6. Next stepswhat we’ve seen in the simulation is needed. It can be done by finding theconvergence rate of these algorithms. Furthermore, as we said earlier, onedifference between algorithm one and algorithms 2 and 3 is that we did nothave any assumption on the finite variation in the latter. So it is motivatingto use the same ideas and relax the assumption we had in the first algorithm.31Chapter 3LQ gamesWhen the parameters of the Linear Quadratic (LQ) system are unknown tous, we use PG to calculate the optimum action to play. It has been proventhat using Policy Gradient (PG) will get us to the optimum global feedbackin LQR systems [4]. While it looks promising that it works well in the games,some counter examples indicate that PG does not have any guarantee ofconvergence for LQ games in a general setting [13, 14]. However, Hamblyand Roudneshin [7, 23] proved that in other non-general settings, PG hasa convergence guarantee. It motivates us to study other non-general LQgames, recognize them, and see if they have any PG convergence guarantee.In potential games, the cost functions of players are connected to eachother via one global potential function. This property of theirs makes themshow one-player system characteristic when the players are using PG. Inthis thesis, we chose the class of potential LQ games to study. In the restof this chapter, we go through the definitions, properties, and theoremsassociated with potential games. We identify the class of potential LQ gamesunder certain assumptions and prove that using PG will converge to a Nashsolution.3.1 Review of the definitions3.1.1 Dynamic SystemA discrete dynamic system is defined as a set of states X ⊆ Rm and a setof actions U ⊆ Rn a set of evaluation functions ft : X × U → X, wherext+1 = ft(xt, ut) for t ∈ {0, 1, 2, . . . }. For example the following can be adynamic function:xt+1 =1∥ut∥+ 1xt. (3.1)If functions ft are linear with respect to xt’s and ut’s for all t, we call ita linear dynamic system, i.e., ft(xt, ut) = Atxt + Btut. The below function323.1. Review of the definitionsis an example of a linear dynamic for m = n = 2:ft(xt, ut) = xt/2 + ut. (3.2)with At =12I2×2 and Bt = I2×2.A time-invariant linear dynamic system is asymptotically stable if matrixA has a spectral radius of smaller than one [10]. In other words, if all theeigenvalues of A lie inside the unit circle, then the dynamic 3.2 is a time-invariant, stable linear dynamic. The system’s stability is important to uswhen dealing with an infinite horizon system, especially in the closed loopsetting, because, if we have an unstable system, it can easily give us anunbounded cost functions which is not desirable.3.1.2 Quadratic Cost FunctionA Linear Quadratic Regulator (LQR) is a linear dynamic system with aquadratic cost function on states and actions. In other words, each timeepisode has a cost function as ct = xTt Qtxt + uTt Rtut where Qt ⪰ 0 andRt ≻ 0 for all t. Here we with to minimize the sum of J(x, u) =∑Tt=1 ct,where u and x are vectors over time horizon T , and T can be infinity.The optimal action at time t is proven to be a linear function of thestate at time t, i.e., u∗t = −Ktxt, and if the horizon is infinity, u∗t = −Kxt.This encourages us to search for the optimal coefficient K∗t rather than theoptimal action u∗t .Whether the agent gets feedback on each time step or not, there are twosettings: open-loop and closed-loop. In an open-loop LQR, the agent will beprovided with no feedback. In a closed-loop LQR, however, the agent willbe given with xt at each time step, and based on that, it plays its action.333.1. Review of the definitions(a) Open Loop(b) Closed LoopFigure 3.1: Closed loop and open loop flowchartKnown and Unknown Parameters: There are two major settings inwhich the game is dealt with; one is where all the parameters of At, Bt, Qt,and Rt are given. As opposed to this setting, in real-world problems, thereis no access to any of them. All that is permitted is to query the value ofthe cost function J(x, u) and receive a noisy or accurate value as feedback.The optimum solution to this problem in a closed-loop setting, whenthere is access to all the parameters, is achieved by solving the followingAlgebraic Riccati equations [4]:P = ATPA+Q−ATPB(BTPB +R)−1BTPA (3.3)K∗ = −(BTPB +R)−1BTPA (3.4)for infinite horizon setting andPt = ATPt+1A−ATPt+1B(R+BTPt+1B)−1BTPt+1A+Q, (3.5)K∗t = −(BTPt+1B +R)−1BTPt+1A0 (3.6)for finite horizon setting. These equations can be solved by Lyapunov itera-tion. However, if the parameters are unknown to us, none of the mentionedequations can be used to derive the value of Kt.As a generalization of LQR systems with only one-player to play itsinputs, we have LQ games where N players interact with the environment,penalizing their actions and the states they are in with a quadratic costfunction. Also, all players’ actions impact the state of the next time step ina linear fashion.343.1. Review of the definitionsci,t = xTt Qixt + uTi,tRiui,t ∀i, t, (3.7)xt+1 = Axt +N∑j=1Bjuj,t ∀t. (3.8)Like in LQR systems, the Nash in LQ games has the Nash in the form ofu∗i,t = −K∗i,txt. When the parameters are known, the Nash will be calculatedby the following equations:P ∗i,t = Qi,t + (K∗i,t)TRi,tK∗i,t + (At −N∑j=1Bj,tK∗j,t)TP ∗i,t+1(At −N∑j=1Bj,tK∗j,t),(3.9)K∗i,t = (Ri,t +BTi,tP∗i,t+1Bi,t+1)−1BTi,tP∗i,t+1(At −N∑j=1,j ̸=iBj,tKj,t).(3.10)for finite horizon andP ∗i = Qi + (K∗i )TRiK∗i + (A−N∑j=1BjK∗j )TP ∗i (A−N∑j=1BjK∗j ), (3.11)K∗i = (Ri +BTi P∗i Bi)−1BTi P∗i (A−N∑j=1,j ̸=iBjKj)0 (3.12)for infinite horizon.As shown in the previous part, if all the parameters are known, we cananalytically calculate the optimum input for the LQR system or Nash forLQ games. However, as mentioned, it is not a reasonable assumption tohave access to any of the parameters of the game, as the game/system isunknown to us in real-world problems. Thus, we need to have a differentapproach, the policy gradient. Policy Gradient (PG) is a popular methodused in many Reinforcement Learning problems to optimize policies usingestimated or actual cost functions. Here we use all the feedback we got tocalculate or estimate the gradient of the cost function concerning our policyand change our policy accordingly:Km+1i,t = Kmi,t − η∇Kmi,tJi. (3.13)353.1. Review of the definitionsThe gradient of the cost function is calculated by the following equation [7]:∇Kmi,tJi = 2(Ri,tKmi,t −BTi,tPmi,t+1(At −N∑j=1Bj,tKmj,t))Σt. (3.14)wherePmi,t = Qi,t + (K∗i,t)TRi,tK∗i,t + (At −N∑j=1Bj,tK∗j,t)TPmi,t+1(At −N∑j=1Bj,tK∗j,t),(3.15)Σt = E[xtxTt ]. (3.16)Because we do not have access to the parameters of the game, the exactgradient is unknown. However, we need to use the gradient’s exact valuefor simulations to see how the policy gradient method is doing in differentsettings. One simple way to estimate gradients is to use zero-order methods,such as examples in the last chapter.3.1.3 Stochasticity in LQ gamesLike in many other games and systems around us, randomness plays animportant role due to our lack of knowledge. This stochasticity can comeinto play when we have an LQR system or an LQ game. This randomnesscan be attributed to the state’s random initialization, where the initial stateis drawn from a distribution D, i.e., x0 ∼ D. Alternatively, it could be dueto the presence of noise in our environment, which can affect the game’sdynamics, i.e., xt+1 = Axt +∑Ni=1Biui,t + wt, where the noise wt at timet can be a Gaussian random variable. It is observed that this randomnesscan have a meaningful impact on the convergence of the PG algorithm [7].In this work, we mainly focus on deterministic LQ games and stochastic LQgames with random initialization.3.1.4 Potential GamesAs we said earlier, our focus is on the convergence of the policy gradient inpotential LQ games because we expect them to have a convergence guar-antee. So let us review the definition and properties of a static potentialgame.363.1. Review of the definitionsDefinition 3.1.1. The game Ji(ui, u−i) is exact potential if there exists apotential function Π such that for every u and i we have:Ji(ui, u−i)− Ji(vi, u−i) = Π(ui, u−i)−Π(vi, u−i). (3.17)With assumptions on differentiability, we have a necessary and sufficientcondition for a game to be potential. Because this potential function is noteasily visible to us, the following condition assists us in determining whethera game is potential or not [9]:∂2Ji∂ui∂uj= [∂2Jj∂ui∂uj]T . (3.18)We might come across different definitions for Dynamic Potential Games(DPG). We mention a few of them:Definition 3.1.2. The game Ji(x0, ui, u−i) is dynamic potential if there isa potential function Π such that for every x0, u and i we have:Ji(x0, ui, u−i)− Ji(x0, vi, u−i) = Π(x0, ui, u−i)−Π(x0, vi, u−i). (3.19)Definition 3.1.3. The game Ji(x0, ui, u−i) is DPG if there is a family ofpotential functions Πt such that for every x0, u, t and i [26]:∞∑t=0βt(ci,t(xt, ui, u−i)− ci,t(xt, vi, u−i)) =∞∑t=0βt(Πt(xt, ui, u−i)−Πt(xt, vi, u−i)). (3.20)Definitions 3.17 and 3.22 are equivalent to condition 3.18 and they areeasily used for the case when the game is deterministic. However for 3.20,condition 3.18 it has a sufficient condition in the form of:∂2ci,t∂ui,t∂uj,t=∂2cj,t∂uj,t∂ui,t. (3.21)There are also different, but similar definitions like what is used in [17],but we do not work with them. It’s worth mentioning that when we haverandom initialization, we can change 3.22 to:ED[Ji(x0, ui, u−i)− Ji(x0, vi, u−i)] = ED[Π(x0, ui, u−i)−Π(x0, vi, u−i)],(3.22)373.2. An examples of LQ gameremember that D was the distribution that we draw the initial state x0 from.Or we can take the expectation w.r.t. any randomness we have in the gameand call it the condition for potentialness of that game.There are also two terms that we will use further down at the end of thischapter.• Dummy player: A dummy player is whose utility function is inde-pendent of his/her actions, i.e., fi(xi, x−i) = fi(x−i).• Dummy game: A dummy game is a game that all of it’s player aredummy, i.e., for every i, fi(xi, x−i) = fi(x−i).Theorem 3.1.4. A dummy game is potential with the potential functionΠ = 0.Proof. Using differentiation rules.3.2 An examples of LQ gameNow we bring an example of linear quadratic game mentioned in [26]. Con-sider a dynamic in the form xt+1 = Axt +∑i∈N Biuit and utility functionsci,t = (xt−xt−1)TQ(xt−xt−1)+ (Dixt−uit)TRi(Dixt−uit), where matricesRi and Q are negative semi-definite and definite respectively.By defining augmented state and action vectors:x˜tT := [xTt , xTt−1]T , u˜tT := Dixt − uit.we can rewrite the problem as follows:max{uit}∈∏∞t=0 Ui∞∑t=0βt(x˜tT R˜x˜t + u˜itTRiu˜ti),s.t. x˜t+1 = Ax˜t −N∑i=1B˜iu˜ti,∀i ∈ N .whereA˜ :=[A+∑i∈N BiDi 0S×SIS 0S×S], B˜i :=[Bi0S×Ai],Q˜ :=[Q −Q−Q Q].383.3. Potential games and their Conditionswhere S and Ai are the appropriate dimensions. Now we can rewrite utilitiesas follows:ci,t(x˜t, u˜t) = x˜Tt R˜x˜t + u˜itTRiu˜it.which is a LQ game.3.3 Potential games and their ConditionsThis part aims to introduce the tools we have to identify the sub-class ofpotential LQ games and find a theoretical motivation for working with them.We use theorems to drive the sufficient and necessary conditions for a gameto be potential. In addition, there will be a brief analysis that shows usingPG in a potential game is the equivalent of using PG in a one-player system.3.3.1 Convergence of Potential LQ gamesLet us take a look at 3.17. One by dividing the sides by ∥ui−vi∥ and takingthe limit when vi → ui can get∇iJi(x0, ui, u−i) = ∇iΠ(x0, ui, u−i), (3.23)this means that the game map’s gradient equals the gradient of the potentialfunction. Now, if all the players use a policy gradient with an equal learningrate η, we will have:u+1 = u+1 − η∇1J1(x0, u), (3.24)...u+N = u+N − η∇NJN (x0, u). (3.25)by replacing ∇iJi(x0, u) with ∇iΠ(x0, u) stacking the above equations:u+ = u+ − η∇Π(x0, u), (3.26)which is the policy gradient for a single-player game with the cost functionof Π(.). The dynamic for this single player game isxt+1 = Axt + B˜ut, (3.27)B˜ =[B1 . . . Bn]. (3.28)Connecting this observation to [4] motivates us to have a potential LQ gamewith the quadratic potential function. Such a game should converge tothe Nash because the optimum point for the potential function is a Nashequilibrium for the original game.393.3. Potential games and their Conditions3.3.2 Open loop potential LQ gamesIn this part the objective is to derive the conditions for a finite-horizondeterministic LQ game to be potential for horizon of tf . Here we try towrite cost function and then use 3.18 to see what should be relation betweenparameters of the game to make that happen. The cost function for suchgame looks like:Ji(u1, . . . ,uN , x0) =tf−1∑t=0(xTt Qixt + uTi,tRiui,t)+ xTtfQixtf , (3.29)where xt = Axt1 +∑Ni=1Biui,t−1. So we want to replace xt’s such that 3.29will be only a function of x0 and ui,t’s. We define ui = [uTi,0, . . . , ui,tf−1]Tthe stacked vector of all actions played by the i’th player, then we can easilyuse 3.18 to see what are the conditions. LetX =x1...xtf , Sx = A...Atf , Sui =Bi . . . 0AB . . . 0.... . ....Atf−1Bi . . . Bi . (3.30)We can re-write X as [3]:X = Sxx0 +N∑i=1Suiui, (3.31)andJi(x,u) = xT0Qix0 + X T Q˜iX + uTi R˜iui, (3.32)where u and x are respectively stacked vectors of ui’s and xt’s, and Q˜(mtf×mtf )i =blockdiag{Qi, . . . , Qi}, and R˜(ditf×ditf )i = blockdiag{Ri, . . . , Ri}. To makext for t > 0 disappear, we re-write is as follow:Ji(u, x0) = xT0 (Yi +Qi)x0 + 2xT0N∑j=1F ijuj +N∑j=1N∑l=1uTj Hij,lul + uTi R˜iui,(3.33)Y i = SxT Q˜iSx, F ij = SxT Q˜iSuj , H ij,l = SujT Q˜iSul . (3.34)Theorem 3.3.1. The LQ game is potential if and only if H ij,i = Hjj,i for allplayers.403.3. Potential games and their ConditionsProof. Let us apply Lemma 4. Recall ∇uiJi as a linear function of actions∇uiJi = 2F iiTx0 + 2N∑j=1H ii,juj + 2R˜iui. (3.35)The second derivative with respect to actions of other players is ∂2Ji∂ujui= H ij,i.According to 3.18, ∂2Ji∂ujui=( ∂2Jj∂uiuj)T. Thus, H ij,i = Hjj,i.If we open this condition up, we will get:tf∑f=tβf[2B⊤i (A⊤)f−tQiAf−tBj]=tf∑f=tβf[2B⊤j (A⊤)f−tQjAf−tBi]T,for all t. Where 0 < β < 1 is the discount factor of the game.One simple case to satisfy such condition is to have Qi = Q for all i. Toadd more detail, let’s re-write the cost function as:Ji(u1, . . . ,uN , x0) =tf−1∑t=0(xTt Qixt +N∑j=1uTj,tRjuj,t)+ xTtfQixtf−tf−1∑t=0∑j ̸=iuTj,tRjuj,t. (3.36)So the cost function of player i is sum of two terms∑tf−1t=0(xTt Qixt +∑Nj=1 uTj,tRjuj,t)+ xTtfQixtf and −∑tf−1t=0∑j ̸=i uTj,tRjuj,t. The first termis the same for all the players. A game with such a cost function is calledan identical interest game. Identical interest games are potential, with thepotential function the same as each player’s cost function. Now look to thesecond term. This term does not depend on ith player’s action. This gameis called a dummy game, which is also a potential game with a potentialfunction of 0. It is known that a game whose players’ cost functions are thesum of two other potential game cost functions is a potential game [Bringthe proof/ reference]. So as a sanity check, it implies that an open-loop LQgame with Qi = Q for all i is a potential game.However, this is not a necessary condition for a game being potential.Below, there is a game that Q1 ̸= Q2 and it is open-loop potential:413.3. Potential games and their ConditionsA =[1 00 1], B1 =[10], B2 =[11], Q1 =[5 −2−2 1], Q2 =[1 22 5].It is easily checkable that the following identities always hold:BT1 (AT )t′−tQ1At′−tB2 = BT2 (AT )t′−tQ2At′−tB1, t′ > t.which is the same as Su2H12,1Su1T = Su2H22,1Su1T .3.3.3 Closed loop potential LQ gamesSimple scalar case:We consider a case where all actions and states are scalar. Here we as-sume that we play the same feedback coefficient at all time steps. The costfunction for such a game is as follows.Ji(K,x0) =T∑t=0(A+∑rBrKr)2t(Qi +K2i Ri)x20, (3.37)∂2Ji∂Ki∂Kj=∑t((2t)(2t− 1)BiBj(A+∑rBrKr)2t−2(Qi +K2i Ri) (3.38)+Bj(2t)(A+∑rBrKr)2t−1(2KiRi))x20 i ̸= j,∂2Ji∂Ki∂Kj=∑t((2t)(2t− 1)B2i (A+∑rBrKr)2t−2(Qi +K2i Ri) (3.39)+2(2t)Bi(A+∑rBrKr)2t−1(2KiRi)+(A+∑rBrKr)2t(2Ri))x20 i = j.so the necessary and sufficient condition for it to be potential is:BiBj(Qi +K2i Ri) +Bj(A+∑rBrKr)(2KiRi) (3.40)= BiBj(Qj +K2jRj) +Bi(A+∑rBrKr)(2KjRj).for every i, j, and for all K. Which implies that in the two following casesthe game is potential:For every pair of i, j we have at least one of the followings cases:423.3. Potential games and their Conditions• Bi = Bj = 0.• Ri = Rj = 0, and Qi = Qj .The first case implies that players i and j are decoupled from the game(their actions will not affect other players’ actions because they are notaffecting the dynamic). In contrast, the second case implies that players iand j are playing the same game of sending the state to zero.Lemma 3.3.2. For the first case, i.e, when Bi = Bj = 0 the Nash is toselect Ki = Kj = 0.Proof. when our player’s action ui,t is not affecting xt+1, it means that wehave no control over the term xTt Qixt. However for the other term in ourcost function, which is uTi,tRiui,t, all we can do is to minimize it by selectingui,t = 0, so Ki = 0. More precisely, according to the equation (7a) in [1]:u∗i (x) = −R−1i BTi MiΛ−1A¯x.which is zero if Bi = 0. The solution K = 0 also satisfies in equation 16 in[1].We performed the simulation for two cases of scalar actions, scalar statesand scalar actions, 2d states, and the policy gradient method converged tothe Nash equilibrium. For the second case, as we have in equation 7a in [1],we cannot compute the Nash equilibrium, because of the existence of R−1i inthe equation. However, intuitively, as the only term, they have in their costfunction is xTt Qxt, they are interested in directing the states to the pointthat the mentioned term is close to zero.As a conclusion, using the sufficient conditions we derived for the closedloop case to be potential, our players are partitioned into equivalency classesof decoupled players and players that are clones of one single player. Forthe first set of players, we will have a trivial solution of Ki = 0, and for thesecond set of players, we have to calculate the optimum with the methodwe were using in a single-player LQR system.Scalar case with time horizon of 2:In the next step, we study the case that the horizon is finite, and we playdifferent K’s at each time step. If we assume that time horizon is T = 1,433.3. Potential games and their Conditionsthe cost functions will be:J1(K,x0) =xT0Q1x0 + xT0KT1 R1K1x0xT0 A¯TQ1A¯x0 + xT0 A¯TKT1 R1K1A¯x0,J2(K,x0) =xT0Q2x0 + xT0KT2 R2K2x0xT0 A¯TQ1A¯x0 + xT0 A¯TKT2 R2K2A¯x0.where A¯ = A+B1K1 +B2K2.∂J1∂K1= 2K1R1x20 + 2A¯Q1B1x20 + 2B1A¯R1K21x0 + 2A¯2K1R1x20,∂J1∂K2= 2A¯Q1B2x20 + 2A¯R1K21B2x20,∂2J1∂K2∂K1= 2B1B2Q1x20 + 2R1K21B1B2x20 + 4A¯R1K1B2x20.similarly:∂J2∂K2= 2K2R2x20 + 2A¯Q2B2x20 + 2B2A¯R2K22x0 + 2A¯2K2R2x20,∂J2∂K1= 2A¯Q2B1x20 + 2A¯R2K22B1x20,∂2J2∂K2∂K1= 2B1B2Q2x20 + 2R2K22B1B2x20 + 4A¯R2K2B1x20.Again if we put these to 3.18, we’ll get same results as above. Which is thatat least one of the followings holds:• B1 = B2 = 0.• R1 = R2 = 0 and Q1 = Q2.The first condition indicates that the game is uncoupled, and players haveno control over the state xt. The second condition means that both playersenjoy the same cost function and it’s an identical interest game. As it isapparent, the necessary and sufficient conditions for the game to be potentialremained the same.2 dimensional case with time horizon 2:For the next step, we relax our assumption to find conditions for the game,that its dimension is higher than 1. We check the case that the states are inR2 and our actions are in R. To simplify our calculations keep the followingsin mind:443.3. Potential games and their Conditions1. In the closed-loop finite-horizon LQ game, at each step, we play ui,t =−Ki,txt, which is a linear feedback of our current state.2. The necessary and sufficient condition for our game be potential is that∂2Ji∂uj∂ui=∂2Jj∂ui∂uj, where ui and uj are the stacked vectors of the actionsthat are played by player i. As here the actions we are playing are thecoefficients k, so the mentioned condition turns to: ∂2Ji∂kj∂ki=∂2Jj∂ki∂kj,where ki is the stacked matrix of coefficients of player i.3. The calculation of the above condition is extremely hard to achieve,but we can break the condition down to the following equivalent con-ditions, ∂2Ji∂kj,τ∂ki,τ ′=∂2Jj∂ki,τ ′∂kj,τ, for all τ, τ ′ ≤ T , where T is the horizonof the game.Let us take a look at structure of cost functions for a two player game.J1(k1, k2) =xT0 [Q1 + kT1,0R1k1,0]x0+ xT0 (A−B1k1,0 −B2k2,0)T [Q1 + kT1,0R1k1,0](A−B1k1,0 −B2k2,0)x0...+ xT0 A¯T0 . . . A¯Tt−1[Q1 + kT1,tR1k1,t]A¯t−1 . . . A¯0x0...+ xT0 A¯T0 . . . A¯TT−1[Q1 + kT1,TR1k1,T ]A¯T−1 . . . A¯0x0.where A¯t = A−B1k1,t −B2k2,t.To simplifying the explanation let’s call the term xT0 A¯T0 . . . A¯Tt−1[Q1 +kT1,tR1k1,t]A¯t−1 . . . A¯0x0 as c1,t. Now note that for calculation of∂2Ji∂kj,τ∂ki,τ ′=∂2Jj∂ki,τ ′∂kj,τall the c1,t with t < τ or t < τ′ has no say in the final expression,because their differentiation with respect to one of the kj,τ and ki,τ ′ will bezero. So we can re-write our condition as follows:∑t′≥max{τ,τ ′}∂2ci,t′∂kj,τ∂ki,τ ′=∑t′≥max{τ,τ ′}∂2cj,t′∂ki,τ ′∂kj,τ(3.41)Now we only focus on∂2ci,t′∂kj,τ∂ki,τ ′with t′ ≥ max{τ, τ ′}.c1,t′ = xT0 A¯T0 . . . A¯Tt′−1[Q1 + kT1,t′R1k1,t′ ]A¯t′−1 . . . A¯0x0.453.3. Potential games and their ConditionsAs our functions are smooth, we can change the order of differentiation ifwe want. Due to symmetry without loss of generality, we assume τ ≤ τ ′.We calculate∂2c1,t′∂ki,τ ′∂kj,τ:∂c1,t′∂kj,τ=2(A¯τ−1 . . . A¯0x0)(A¯τ−1 . . . A¯0x0)T ([A¯Tτ+1 . . . A¯Tt′−1[Q1 + kT1,t′R1k1,t′ ]A¯t′−1 . . . A¯τ+1])A¯τBj .So∂2c1,t′∂ki,τ ′∂kj,τ=2BTi (A¯τ−1 . . . A¯0x0)(A¯τ−1 . . . A¯0x0)T ([A¯Tτ ′+1 . . . A¯Tt′−1[Q1 + kT1,t′R1k1,t′ ]A¯t′−1 . . . A¯τ ′+1])A¯τ . . . A¯τ ′Bj .Putting all together gives us: ∑t′≥max{τ,τ ′}∂2c1,t′∂kj,τ∂ki,τ ′=∑t′≥max{τ,τ ′}2BTi (A¯τ−1 . . . A¯0x0)(A¯τ−1 . . . A¯0x0)T ([A¯Tτ ′+1 . . . A¯Tt′−1[Q1 + kT1,t′R1k1,t′ ]A¯t′−1 . . . A¯τ ′+1])A¯τ . . . A¯τ ′Bj =∑t′≥max{τ,τ ′}2BTj (A¯τ−1 . . . A¯0x0)(A¯τ−1 . . . A¯0x0)T ([A¯Tτ ′+1 . . . A¯Tt′−1[Q2 + kT2,t′R2k2,t′ ]A¯t′−1 . . . A¯τ ′+1])A¯τ . . . A¯τ ′Bi =∑t′≥max{τ,τ ′}∂2c2,t′∂ki,τ ′∂kj,τ.The above condition should be correct for all τ, τ ′ < T .In the first part of this section, we studied the case of scalar gameswhere the actions played by each player are constant over time. Here our463.3. Potential games and their Conditionsgoal is to compare these conditions to the case that actions and states areall scalars. If we do the same analysis for the finite horizon case, we willhave the following conditions for this game’s potential.∑t′≥max{τ,τ ′}x20(Q1 + k21,t′R1)A¯20 . . . A¯2t′−1A¯τ A¯τ ′B1B2 =∑t′≥max{τ,τ ′}x20(Q2 + k22,t′R2)A¯20 . . . A¯2t′−1A¯τ A¯τ ′B1B2.Note that the division by A¯τ A¯τ ′ is informal and we don’t have problem withdividing anything by zero.The conditions above for a game with time horizon of T = 1 will be:(Q1 + k21,1R1)B1B2 = (Q2 + k22,1R2)B1B20which leads the same conclusion as we had before. Now we do the samewith the conditions of a 2d game we have had.BT1 (Q1 + kT1,1R1k1,1)B2 = BT2 (Q2 + kT2,1R2k2,1)B1.Both the right-hand and left-hand sides are symmetric (They are eitherscalar or the second derivative matrix of one smooth cost function.) So wecan summarize it as follows:BT2 (Q2 −Q1 + kT2,1R2k2,1 − kT1,1R1k1,1)B1 = 0. (3.42)For every k1,1 and k2,1. Similarly if any of B1 or B2 are zero then the gameis uncoupled and potential. Also if Q1 = Q2 and R1 = R2 = 0 we have thesame thing.Note that as it is a finite horizon case we don’t care about stability. Soki,1 can be anything. So if B1 and B2 are not zero then we can make theexpression non-zero. Which means that at least one of the Ri’s should bezero to make the game potential, which is in contrary to our assumption Ribeing non-zero.For higher time horizons, the condition will have the same structure as3.42, so again when we have to unite the expression to zero, we come to thesame conclusion.3.3.4 Special cases of closed-loopAs seen above, because K1 and K2 could be arbitrary, we had to makethe coefficient zero to eliminate them. With the hope of overcoming this473.3. Potential games and their Conditionsproblem, let us consider a case in which one of the players follows the other,so it does not have the freedom to make potential games trivial. We definetrivial as matrices Bi or Ri having to be zero. We are now interested ingames that are less trivial. Except for one agent, whose utility dependssolely on its own action, i.e., f1(x1, x−1) = f1(x1), every other agent in thegame is a dummy. These games are potential too, because ∂2fi∂xi∂xj= 0.What happens if the game is not trivial? i.e., Qi’s are different Ri’s andBi’s are non-zero, but Ki,t = λiK1,t (One Leader and others are Follower),λi can be a matrix. In this game, if λi’s are parameters (not variables)player’s one loss function is only a function of its actions because we can re-place all other players’ feedback with λiK1. All other players’ cost functionsare only a function of player one’s action. So it means the game is potential,and also, the game is not trivial.Furthermore, this game corresponds to an LQ system with B′1 = B1 +∑i ̸=1 λiBi. Thus, the policy gradient guarantees the convergence of playerone to its optimum action for the leader. However, going to the optimumaction is meaningless for the followers because their optimum action is notin the form of Ki,t = λiK1,t. Generally, if all other players follow the firstplayer’s action by a function, i.e., ai = hi(a1), we conjecture that the sameargument can be repeated and the game has non-trivial potential.In all these cases we discussed above, other players were all supposed toplay a single function of the first player’s action. Now, the question is, whathappens if they had some freedom to choose that function? For example,they could choose λi,t = αi,tλi at each time sequence to scale K1 differentlyat each step. Here are, players are not dummies anymore. Because theyhave a say in their cost function by choosing the αi,t, also the potentialconditions will be:∂2fi∂K21=∂2fj∂K21. (3.43)The above-mentioned law is derived from the chain rule when i’s are scalar.It also implies that the potential condition for such a game is that the gameis trivial (Qi = Q, Ri = 0).Another way of looking at this game can be to model it as an LQ systemwith a time-varying matrix B = Bt = B1 +∑i ̸=1 αi,tλiBi.This system is anonline optimization for the first player because parameters Bt are determinedby other players and change over time. Here we should note that every gameis a kind of online optimization, but when we restrict the actions of otherplayers to λiK1xt, the time-varying function is changing limited compared483.4. Simulationsto the general case. In other words, the only parameter changing is Bt, onlywith linear combinations of Bi’s i ̸= 1.3.4 SimulationsHere in this section, we perform simulations on the number of games to seeif open-loop LQ games have any convergence guarantee when played in aclosed-loop setting. The parameters of these two games are the followings.The first one:Q1 = Q2 =[0.01 00 1], B1 =[11], B2 =[01],A =[0.6491 0.64770.7317 0.4509],Keq =[0.7239 0.4483−0.0390 0.1025].And for the second one:Q1 =[0.01 00 1], Q2 =[1 00 0.001], B1 =[11], B2 =[01],A =[0.4253 0.16150.3127 0.1788],Keq =[0.3096 0.17700.1145 −0.0154].For both of them x0 selected randomly from the same distribution.As you see, the first game is open-loop potential because Q1 = Q2.However, as it is apparent in the figure bellow, K2 and Keq2 have differentvalues while the iterations are going forward. However, the second game isnot potential and converges to the Nash equilibrium.The takeaway from this experiment is that, although we know that po-tential open-loop LQ games must converge to Nash while PG is used asthe learning tool, there is no guarantee when the same game is used in aclosed-loop setting.493.4. Simulations(a) PG for first game(b) PG for the second gameFigure 3.2: Convergence TrajectoriesMoreover, to sanity check, we have done another experiment for trivialpotential closed-loop games and observed the convergence to the Nash. Here503.4. Simulationsare the specifications of the game:Q1 =[0.01 00 1], Q2 =[1 00 0.001], B1 =[11], B2 =[00],A =[0.0542 0.66280.1771 0.3308],Keq =[0.1741 0.33100 0].You can see the results in the figure bellow:Figure 3.3: Trivial Closed Loop PotentialNote that as the optimal action by the second player is Keq = 0, we depictthe difference between the action played and the optimal action in the figureabove.As a verification for the special cases that discusses in the previous part,a simulation on the following leader-follower setting is performed.Q1 =[0.01 00 1], Q2 =[1 00 0.001], B1 =[11], B2 =[10],A =[0.0542 0.66280.1771 0.3308],Keq =[0.1753 0.3276−0.1200 0.3319],K2 = 0.5K1.513.5. DiscussionAs expected, the leader converged to the optimum action, but the followerdid not.Figure 3.4: Special Potential Case3.5 DiscussionWe identified the class of deterministic potential LQ games, both for open-loop and closed-loop settings. In the last section, we tried to use an open-loop potential game in a closed-loop setting, and we observed that it didn’tconverge to Nash equilibrium, given by the Riccati equations. It suggeststhat, although potential games have the property of one-player games, theymight not do so when they are used in a different setting. For the closed-loopcase, there are no non-trivial potential games.We also analyzed some imaginary leader-follow settings and proved thatthey are equivalent to a single-player LQ game, so potential. This result,along with the conclusion for the trivial closed-loop and potential open-loopgames (when used in an open-loop setting), is our convergence guarantee inLQ games.52Chapter 4Conclusion and Future worksTo address the slow convergence to Nash in games, this work provides novelaccelerated online algorithms with proofs of their regret bounds. As it isshown that their regret is sub-linear, they have a convergence guaranteewhen they are employed in Cournot games. These algorithms have beenput into the simulations with zero-order feedback, and we observed thatthey are doing better in terms of speed of convergence compared to oldalgorithms that had the same regret bound, both in Cournot games andQuadratic games, but without providing a mathematical proof.As for the next step, we would work on providing a convergence ratewith a mathematical proof. Moreover, one could extend the derived regretbound for the algorithms 2 and 3 to the zero-order setting. Also, it wouldbe helpful to calculate the regret bound of algorithm 1 in terms of T .The unknown parameters of LQ games need PG to find the Nash so-lution. In general, however, PG may not converge to the Nash. To finda category of LQ games where PG has a convergence guarantee, we recog-nized the class of potential LQ games in open-loop. We did the same forthe closed-loop settings, but under some assumptions on the dimensions ofthe actions and states. By performing experiments, the results are verified.The next step for this work is to do the same for infinite horizon stochas-tic LQ games to identify more potential LQ games. Besides, in this work, weconsidered the conventional cost function of xTt Qixt + uTi,tRiui,t. However,they could be extended with new cross terms of xTt Sut and similar terms, asin [7]. As such, if the cost function is more general, other classes of potentialgames might exist that we don’t know about.53Bibliography[1] Tamer Bas¸ar and Geert Jan Olsder. Dynamic noncooperative gametheory. SIAM, 1998.[2] Dimitri P Bertsekas et al. Dynamic programming and optimal control3rd edition, volume ii. Belmont, MA: Athena Scientific, 2011.[3] Francesco Borrelli, Alberto Bemporad, and Manfred Morari. Predictivecontrol for linear and hybrid systems. Cambridge University Press,2017.[4] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Globalconvergence of policy gradient methods for the linear quadratic regu-lator. In International Conference on Machine Learning, pages 1467–1476. PMLR, 2018.[5] Simon Fischer, Harald Ra¨cke, and Berthold Vo¨cking. Fast convergenceto wardrop equilibria by adaptive sampling methods. SIAM Journal onComputing, 39(8):3700–3735, 2010.[6] Yoav Freund and Robert E Schapire. Adaptive game playing usingmultiplicative weights. Games and Economic Behavior, 29(1-2):79–103,1999.[7] Ben Hambly, Renyuan Xu, and Huining Yang. Policy gradient meth-ods find the nash equilibrium in n-player general-sum linear-quadraticgames. arXiv preprint arXiv:2107.13090, 2021.[8] Elad Hazan. Introduction to online convex optimization. arXiv preprintarXiv:1909.05207, 2019.[9] Joa˜o P Hespanha. Noncooperative game theory: An introduction forengineers and computer scientists. Princeton University Press, 2017.[10] Joao P Hespanha. Linear systems theory. Princeton university press,2018.54Bibliography[11] Chonghai Hu, Weike Pan, and James Kwok. Accelerated gradient meth-ods for stochastic optimization and online learning. Advances in NeuralInformation Processing Systems, 22:781–789, 2009.[12] Nicolas S Lambert, Giorgio Martini, and Michael Ostrovsky. Quadraticgames. Technical report, National Bureau of Economic Research, 2018.[13] Eric Mazumdar, Lillian J Ratliff, Michael I Jordan, and S ShankarSastry. Policy-gradient algorithms have no guarantees of convergencein linear quadratic games. arXiv preprint arXiv:1907.03712, 2019.[14] Eric Mazumdar, Lillian J Ratliff, and S Shankar Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics ofData Science, 2(1):103–131, 2020.[15] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Pil-iouras. Cycles in adversarial regularized learning. In Proceedings of theTwenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,pages 2703–2717. SIAM, 2018.[16] Panayotis Mertikopoulos and Mathias Staudigl. Convergence to nashequilibrium in continuous games with noisy first-order feedback. In2017 IEEE 56th Annual Conference on Decision and Control (CDC),pages 5609–5614. IEEE, 2017.[17] David HMguni, YutongWu, Yali Du, Yaodong Yang, Ziyi Wang, MinneLi, Ying Wen, Joel Jennings, and Jun Wang. Learning in nonzero-sum stochastic games with potentials. In International Conference onMachine Learning, pages 7688–7699. PMLR, 2021.[18] Faisal A Mohamed and Heikki N Koivo. Multiobjective optimizationusing modified game theory for online management of microgrid. Eu-ropean Transactions on Electrical Power, 21(1):839–854, 2011.[19] Roger B Myerson. Game theory: analysis of conflict. Harvard universitypress, 1997.[20] Yu E Nesterov. A method for solving the convex programming problemwith convergence rate o( 1k2). In Dokl. Akad. Nauk SSSR,, volume 269,pages 543–547, 1983.[21] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimiza-tion of convex functions. Foundations of Computational Mathematics,17(2):527–566, 2017.55[22] Boris T Polyak. Some methods of speeding up the convergence of iter-ation methods. USSR Computational Mathematics and MathematicalPhysics, 4(5):1–17, 1964.[23] Masoud Roudneshin, Jalal Arabneydi, and Amir G Aghdam. Reinforce-ment learning in nonzero-sum linear quadratic deep structured games:Global convergence of policy optimization. In 2020 59th IEEE Confer-ence on Decision and Control (CDC), pages 512–517. IEEE, 2020.[24] Yuanyuan Shi and Baosen Zhang. No-regret learning in cournot games.arXiv preprint arXiv:1906.06612, 2019.[25] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and fasterconvergence of sgd for over-parameterized models and an acceleratedperceptron. In The 22nd International Conference on Artificial Intelli-gence and Statistics, pages 1195–1204. PMLR, 2019.[26] Santiago Zazo, Sergio Valcarcel Macua, Matilde Sa´nchez-Ferna´ndez,and Javier Zazo. Dynamic potential games with constraints: Funda-mentals and applications in communications. IEEE Transactions onSignal Processing, 64(14):3806–3821, 2016.[27] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimiza-tion provably converges to nash equilibria in zero-sum linear quadraticgames. Advances in Neural Information Processing Systems, 32, 2019.[28] Martin Zinkevich. Theoretical guarantees for algorithms in multi-agentsettings. Carnegie Mellon University, 2004.56Appendix AAppendixTheorem:2.2.1 If the following conditions are hold:γk =1ρ.[1 +βk(1− αk)αk], (A.1)αk =γkβkb2k+1ηγkβkb2k+1η + a2k, (A.2)βk ≥ 1− γkµη, (A.3)ak+1 = γk√ηρbk+1, (A.4)bk+1 ≤ bk√βk, (A.5)b2k+1γ2kηρ = a2k+1, (A.6)b2k+1γkη − a2k+1 + a2k = 0, (A.7)η ≤ 1ρL. (A.8)the regret bound for algorithm 1 is:Reg(T ) ≤T∑j=1[12b2jγ2j−1ηρ(2a20C1 + b20C2+j−1∑k=1[2b2k+1γ2k+1η2σ2k + 4b2k+1γ2k+1ηρϵk])]. (A.9)where C1 = f0(x0)− f0(x∗) and C2 = ∥x0 − x∗∥2 and x∗ is the best actionplayed on the hindsight.Proof. This proof is fully inspired from [25]. Essentially all the main stepsare same with [25] except in eqs. (A.13) and (A.16), where we upgraded thealgorithm to online optimization.57Appendix A. AppendixLet wk, ζk and νk be updated as below:wk+1 = ζk − η∇fk(ζk, zk), (A.10)ζk = αkνk + (1− αk)wk, (A.11)νk+1 = βkνk + (1− βk)ζk − γkη∇fk(ζk, zk). (A.12)And let rk+1 = ∥νk+1 − w∗∥, so we have:r2k+1 = ∥βkνk + (1− βk)ζk − w∗ − γkη∇fk(ζk, zk)∥2,r2k+1 =∥βkνk + (1− βk)ζk − w∗∥2+ γ2kη2∥fk(ζk, zk)∥2 + 2γkη⟨w∗ − βkνk − (1− βk)ζk,∇fk(ζk, zk)⟩.Taking expectation w.r.t zk,E[r2k+1] = E[∥βkνk + (1− βk)ζk − w∗∥2] + γ2kη2 E[∥fk(ζk, zk)∥2]+ 2γkη[E⟨w∗ − βkνk − (1− βk)ζk,∇fk(ζk, zk)⟩]≤ ∥βkνk + (1− βk)ζk − w∗∥2 + γ2kη2ρ∥fk(ζk)∥2+ 2γkη⟨w∗ − βkνk − (1− βk)ζk,∇fk(ζk)⟩+ γ2kη2σ2k= ∥βk(νk − w∗) + (1− βk)(ζk − w∗)∥2 + γ2kη2ρ∥fk(ζk)∥2+ 2γkη⟨w∗ − βkνk − (1− βk)ζk,∇fk(ζk)⟩+ γ2kη2σ2k≤ βk∥νk − w∗∥2 + (1− βk)∥ζk − w∗∥2+ γ2kη2ρ∥fk(ζk)∥2 + 2γkη⟨w∗ − βkνk − (1− βk)ζk,∇fk(ζk)⟩+ γ2kη2σ2k (By convexity of norm)= βkr2k + (1− βk)∥ζk − w∗∥2 + γ2kη2ρ∥fk(ζk)∥2+ 2γkη⟨w∗ − βkνk − (1− βk)ζk,∇fk(ζk)⟩+ γ2kη2σ2k= βkr2k + (1− βk)∥ζk − w∗∥2 + γ2kη2ρ∥fk(ζk)∥2+ 2γkη[⟨βk(1− αk)αk(wk − ζk) + w∗ − ζk,∇fk(ζk)⟩] + γ2kη2σ2k= βkr2k + (1− βk)∥ζk − w∗∥2 + γ2kη2ρ∥fk(ζk)∥2+ 2γkη[βk(1− αk)αk⟨(wk − ζk),∇fk(ζk)⟩+ ⟨w∗ − ζk,∇fk(ζk)⟩]+ γ2kη2σ2k≤ βkr2k + (1− βk)∥ζk − w∗∥2 + γ2kη2ρ∥fk(ζk)∥2+ 2γkη[βk(1− αk)αk(fk(wk)− fk(ζk)) + ⟨w∗ − ζk,∇fk(ζk)⟩]+ γ2kη2σ2k. (By convexity)58Appendix A. AppendixBy strong convexity:E[r2k+1] ≤ βkr2K + (1− βk)∥ζk − w∗∥2 + γkη2ρ∥∇fk(ζk)∥2+ 2γkη[βk(1− αk)αk(fk(wk)− fk(ζk)) + f∗k − fk(ζk)−µ2∥ζk − w∗∥2]+ γ2kη2σ2k.Also we have:fk(wk+1)− fk(ζk) ≤ ⟨∇fk(ζk), wk+1 − ζk⟩+ L2∥wk+1 − ζk∥2− η⟨∇fk(ζk),∇fk(ζk, zk)⟩+ Lη22∥∇fk(ζk, zk)∥2.Taking expectation of both sides w.r.t zk (if η ≤ 1ρL):E[fk+1(wk+1)− fk(ζk)] ≤ −η∥∇fk(ζk)∥2 + Lρη22∥∇fk(ζk)∥2 + Lη2σ2k2+ ϵk(A.13)∥∇fk(ζk)∥2 ≤ (2η)E[fk(ζk)− fk+1(wk+1)] + Lησ2k +2ηϵk.Combining it with the previous inequality we conclude that:E[r2k+1] ≤ βkr2k + (1− βk)∥ζk − w∗∥2 + 2γ2kρη E[fk(ζk)− fk(wk+1)]+ 2γkη[βk(1− αk)αk(fk(wk)− fk(ζk)) + f∗k − fk(ζk)−µ2∥ζk − w∗∥2]+ γ2kη2σ2k + Lγ2kη3ρσ2k + 2γ2kρηϵk≤ βkr2k + ∥ζk − w∗∥2[(1− βk)− γµη] + fk(ζk)[2γ2kηρ− 2γkη.βk(1− αk)αk− 2γkη]− 2γ2kηρE fk+1(wk+1) + 2γkηf∗ +[2γkη.βk(1− αk)αk]fk(wk) + 2γ2kη2σ2k + 2γ2kρηϵk.59Appendix A. AppendixNow multiplying both sides by b2k+1 and because of A.1 and A.3,b2k+1 E[r2k+1] ≤ b2k+1βkr2k + ∥ζk − w∗∥2[(1− βk)− γµη]+ b2k+1fk(ζk)[2γ2kηρ− 2γkη.βk(1− αk)αk− 2γkη]− 2b2k+1γ2kηρE fk+1(wk+1)+ 2b2k+1γkηf∗ + b2k+1[2γkη.βk(1− αk)αk]fk(wk) + 2b2k+1γ2kη2σ2k+ 2b2k+1γ2kρηϵk= b2k+1βkr2k − 2b2k+1γ2kηρE(fk+1(wk+1)) + 2b2k+1γkηf∗+[2b2k+1γkη.βk(1− αk)αk]fk+1(wk) + 2b2k+1γ2kη2σ2k + 2b2k+1γ2kρηϵk.Since b2k+1βk ≤ b2k, b2k+1γ2kηρ = a2k+1, γkηβk(1−αk)αk =a2kb2k+1b2k+1 E[r2k+1] ≤ b2kr2k − 2a2k+1 E fk+1(wk+1) + 2b2k+1γkηf∗k + 2a2kfk(wk)(A.14)+2a2k+1σ2kηρ+ 2a2k+1ϵk≤ b2kr2k − 2a2k+1[E fk+1(wk+1)− f∗k+1] + 2a2k[fk(wk)− f∗k ](A.15)+2a2k+1σ2kηρ+ 4a2k+1ϵk (A.16)+ 2[b2k+1γkη − a2k+1 + a2k]f∗k .Since [b2k+1γkη − a2k+1 + a2k] = 0,b2k+1 E[r2k+1] ≤ b2kr2k − 2a2k+1[E fk+1(wk+1)− f∗k+1] + 2a2k[fk(wk)− f∗k ]+2a2k+1σ2kηρ+ 4a2k+1ϵkDenoting E fk(wK)− f∗k as ϕk,2a2k+1ϕk+1 + b2k+1 E[r2k+1] ≤ 2a2kϕk + b2k E[r2k] +2a2k+1σ2kηρ+ 4a2k+1ϵk.60Appendix A. AppendixBy recursion,2a2T+1ϕT+1 + b2T+1 E[r2T+1] ≤2a20ϕ0 + b20 E[r20]+T∑k=1[2a2k+1σ2kηρ+ 4a2k+1ϵk], (A.17)ϕT+1 ≤ 12a2T+1(2a20ϕ0 + b20 E[r20]− b2T+1 E[r2T+1]+T∑k=1[2a2k+1σ2kηρ+ 4a2k+1ϵk]), (A.18)Reg(T ) =T∑j=1ϕj ≤T∑j=1[12a2j(2a20ϕ0 + b20 E[r20]− b2j E[r2j ]+j−1∑k=1[2a2k+1σ2kηρ+ 4a2k+1ϵk])], (A.19)Reg(T ) =T∑j=1ϕj ≤T∑j=1[12b2jγ2j−1ηρ(2a20C1 + b20C2+j−1∑k=1[2b2k+1γ2k+1η2σ2k + 4b2k+1γ2k+1ηρϵk])]. (A.20)61
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Kamgarpour, Maryam
Convergence to Nash in the potential Linear Quadratic games and accelerated learning in games
Text