Convergence to Nash in the potential Linear Quadratic games and accelerated learning in games
department or school: Applied Science, Faculty of
department or school: Electrical and Computer Engineering, Department of
data provider: DSpace
degree campus: UBCV
creator: Alian Porzani, Alireza
issued: 2022-10-31T18:55:04Z
issued: 2022
related degree: Master of Applied Science - MASc
degree grantor: University of British Columbia
description: 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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/83095
note: 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 engineeri…
has type: Thesis/Dissertation
date issued: 2022-11
is shown at: 10.14288/1.0421706
language: eng
degree discipline: Electrical and Computer Engineering
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Kamgarpour, Maryam
type: Text
identifier URI: http://hdl.handle.net/2429/83095