More Like this

1. A Distributed Douglas-Rachford Based Algorithm for Stochastic GNE Seeking with Partial Information

   https://doi.org/10.23919/ACC53348.2022.9867201  

   Huang, Yuanhanqing; Hu, Jianghai (June 2022, Proc. 2022 American Control Conference)

   We consider the stochastic generalized Nash equilibrium problem (SGNEP) where a set of self-interested players, subject to certain global constraints, aim to optimize their local objectives that depend on their own decisions and the decisions of others and are influenced by some random factors. A distributed stochastic generalized Nash equilibrium seeking algorithm is proposed based on the Douglas-Rachford operator splitting scheme, which only requires local communications among neighbors. The proposed scheme significantly relaxes assumptions on co-coercivity and contractiveness in the existing literature, where the projected stochastic subgradient method is applied to provide approximate solutions to the augmented best-response subproblems for each player. Finally, we illustrate the validity of the proposed algorithm through a Nash-Cournot production game. 

   more » « less
2. Distributed Solution of GNEP over Networks via the Douglas-Rachford Splitting Method

   https://doi.org/10.1109/CDC45484.2021.9682862  

   Huang, Yuanhanqing; Hu, Jianghai (December 2021, 60th IEEE Conference on Decision and Control (CDC))

   The aim of this paper is to find the distributed solution of the generalized Nash equilibrium problem (GNEP) for a group of players that can communicate with each other over a connected communication network. Each player tries to minimize a local objective function of its own that may depend on the other players’ decisions, and collectively all the players’ decisions are subject to some globally shared resource constraints. After reformulating the local optimization problems, we introduce the notion of network Lagrangian and recast the GNEP as the zero finding problem of a properly defined operator. Utilizing the Douglas-Rachford operator splitting method, a distributed algorithm is proposed that requires only local information exchanges between neighboring players in each iteration. The convergence of the proposed algorithm to an exact variational generalized Nash equilibrium is established under two different sets of assumptions. The effectiveness of the proposed algorithm is demonstrated using the example of a Nash-Cournot production game. 

   more » « less
3. Distributed algorithms of stochastic games for robot systems in smart manufacturing

   https://doi.org/10.1063/5.0236086  

   He, Xiongnan; Lin, Zongli; Chang, Qing (February 2025, Chaos: An Interdisciplinary Journal of Nonlinear Science)

   In this paper, we study the problem of distributed generalized stochastic Nash equilibrium seeking for robot systems over a connected undirected graph. We use the cost functions containing uncertainty to represent the system’s performance under varying conditions. To mitigate the challenges posed by this uncertainty, we employ the Tikhonov regularization scheme, which also helps us to relax the strongly monotone condition of the cost functions to the strictly monotone condition. We also consider the inequality constraints, which represent the feasible working space of robots. Additionally, auxiliary parameters are introduced in the control laws to facilitate seeing the variational generalized stochastic Nash equilibrium. The convergence of the proposed control laws is analyzed by using the operator splitting method. Finally, we demonstrate the effectiveness of the proposed algorithm through an example involving multiple robots connected through a communication network. 

   more » « less
4. Learning Nash Equilibria in Zero-Sum Stochastic Games via Entropy-Regularized Policy Approximation

   Q. Zhang, Y. Guan (January 2021, 30th International Joint Conference on Artificial Intelligence)

   We explore the use of policy approximations to reduce the computational cost of learning Nash equilibria in zero-sum stochastic games. We propose a new Q-learning type algorithm that uses a sequence of entropy-regularized soft policies to approximate the Nash policy during the Q-function updates. We prove that under certain conditions, by updating the regularized Q-function, the algorithm converges to a Nash equilibrium. We also demonstrate the proposed algorithm’s ability to transfer previous training experiences, enabling the agents to adapt quickly to new environments. We provide a dynamic hyper-parameter scheduling scheme to further expedite convergence. Empirical results applied to a number of stochastic games verify that the proposed algorithm converges to the Nash equilibrium while exhibiting a major speed-up over existing algorithms. 

   more » « less
5. Scenario-Game ADMM: A Parallelized Scenario-Based Solver for Stochastic Noncooperative Games

   https://doi.org/10.1109/CDC49753.2023.10383423  

   Li, Jingqi; Chiu, Chih-Yuan; Peters, Lasse; Palafox, Fernando; Karabag, Mustafa; Alonso-Mora, Javier; Sojoudi, Somayeh; Tomlin, Claire; Fridovich-Keil, David (December 2023, Proceedings of the IEEE Conference on Decision Control)

   Decision-making in multi-player games can be extremely challenging, particularly under uncertainty. In this work, we propose a new sample-based approximation to a class of stochastic, general-sum, pure Nash games, where each player has an expected-value objective and a set of chance constraints. This new approximation scheme inherits the accuracy of objective approximation from the established sample average approximation (SAA) method and enjoys a feasibility guarantee derived from the scenario optimization literature. We characterize the sample complexity of this new game-theoretic approximation scheme, and observe that high accuracy usually requires a large number of samples, which results in a large number of sampled constraints. To accommodate this, we decompose the approximated game into a set of smaller games with few constraints for each sampled scenario, and propose a decentralized, consensus-based ADMM algorithm to efficiently compute a generalized Nash equilibrium (GNE) of the approximated game. We prove the convergence of our algorithm to a GNE and empirically demonstrate superior performance relative to a recent baseline algorithm based on ADMM and interior point method. 

   more » « less