Prof. Rasoul Etesami, University of Illinois Urbana‑Champaign

Title: Efficient and Independent Learning of Nash Equilibria in Structured Stochastic Games with Unknown Independent Dynamics

Abstract: Learning and computing Nash equilibria (NE) in dynamic stochastic games constitutes a significant challenge in many fields. In general, computing an NE is PPAD-hard and is unlikely to admit an efficient polynomial-time algorithm. One approach to overcome this fundamental barrier is to restrict the search for NE to special structured games that frequently arise in applications. In this talk, we study efficient learning of NE in structured stochastic games beyond the two-player case. Specifically, we consider a subclass of n-player stochastic games in which players have their own internal state and action spaces while being coupled through their payoff functions. It is assumed that the players’ internal state transitions are governed by unknown and independent transition probabilities. Moreover, players have only partial observations of the game, in the sense that they can observe only realizations of their payoffs and cannot observe each other’s states or actions. For this class of games, we propose a polynomial-time algorithm that converges in the averaged Nikaido–Isoda gap distance to the set of ε-NE policies with arbitrarily high probability. Furthermore, under additional assumptions on the reward functions, such as social concavity, we show that the iterates converge to an ε-NE policy with high probability. Finally, we complement this result by showing that the proposed algorithm converges asymptotically to a stable ε-NE policy with arbitrarily high probability, assuming the existence of a variationally stable NE policy. We discuss real-world applications of these games in bandwidth allocation for wireless communication networks and energy management in smart grids, and we evaluate the effectiveness of the proposed algorithms through numerical experiments.

Brief bio: Rasoul Etesami is an Assistant Professor in the Department of Industrial and Systems Engineering at the University of Illinois Urbana-Champaign. He is also affiliated with the Coordinated Science Laboratory (CSL), where he is a member of the Decision and Control (DCL) group. From 2016 to 2017, he was a Postdoctoral Research Fellow in the Department of Electrical Engineering at Princeton University and WINLAB. He received his Ph.D. in Electrical and Computer Engineering from the University of Illinois Urbana-Champaign in December 2015, during which he spent one summer as a Research Intern at Alcatel-Lucent Bell Labs. His research interests include analysis of complex social, communication, and decision-making systems using tools from control and game theory, optimization, and learning theory. He was a recipient of the Best CSL Ph.D. Thesis Award at the Engineering College of the University of Illinois Urbana–Champaign in 2016, Springer Outstanding Ph.D. Thesis Award in 2017, and NSF CAREER Award in 2020. He currently serves as an Associate Editor of the Journal of IET Smart Grid.