Distributed Stochastic Nash Equilibrium Learning in Locally Coupled Network Games with Unknown Parameters

Yuanhanqing Huang, Jianghai Hu
Proceedings of The 4th Annual Learning for Dynamics and Control Conference, PMLR 168:342-354, 2022.

Abstract

In stochastic Nash equilibrium problems (SNEPs), it is natural for players to be uncertain about their complex environments and have multi-dimensional unknown parameters in their models. Among various SNEPs, this paper focuses on locally coupled network games where the objective of each rational player is subject to the aggregate influence of its neighbors. We propose a distributed learning algorithm based on the proximal-point iteration and ordinary least-square estimator, where each player repeatedly updates the local estimates of neighboring decisions, makes its augmented best-response decisions given the current estimated parameters, receives the realized objective values, and learns the unknown parameters. Leveraging the Robbins-Siegmund theorem and the law of large deviations for M-estimators, we establish the almost sure convergence of the proposed algorithm to solutions of SNEPs when the updating step sizes decay at a proper rate.

Cite this Paper

BibTeX
@InProceedings{pmlr-v168-huang22a, title = {Distributed Stochastic Nash Equilibrium Learning in Locally Coupled Network Games with Unknown Parameters}, author = {Huang, Yuanhanqing and Hu, Jianghai}, booktitle = {Proceedings of The 4th Annual Learning for Dynamics and Control Conference}, pages = {342--354}, year = {2022}, editor = {Firoozi, Roya and Mehr, Negar and Yel, Esen and Antonova, Rika and Bohg, Jeannette and Schwager, Mac and Kochenderfer, Mykel}, volume = {168}, series = {Proceedings of Machine Learning Research}, month = {23--24 Jun}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v168/huang22a/huang22a.pdf}, url = {https://proceedings.mlr.press/v168/huang22a.html}, abstract = {In stochastic Nash equilibrium problems (SNEPs), it is natural for players to be uncertain about their complex environments and have multi-dimensional unknown parameters in their models. Among various SNEPs, this paper focuses on locally coupled network games where the objective of each rational player is subject to the aggregate influence of its neighbors. We propose a distributed learning algorithm based on the proximal-point iteration and ordinary least-square estimator, where each player repeatedly updates the local estimates of neighboring decisions, makes its augmented best-response decisions given the current estimated parameters, receives the realized objective values, and learns the unknown parameters. Leveraging the Robbins-Siegmund theorem and the law of large deviations for M-estimators, we establish the almost sure convergence of the proposed algorithm to solutions of SNEPs when the updating step sizes decay at a proper rate.} }
Endnote
%0 Conference Paper %T Distributed Stochastic Nash Equilibrium Learning in Locally Coupled Network Games with Unknown Parameters %A Yuanhanqing Huang %A Jianghai Hu %B Proceedings of The 4th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2022 %E Roya Firoozi %E Negar Mehr %E Esen Yel %E Rika Antonova %E Jeannette Bohg %E Mac Schwager %E Mykel Kochenderfer %F pmlr-v168-huang22a %I PMLR %P 342--354 %U https://proceedings.mlr.press/v168/huang22a.html %V 168 %X In stochastic Nash equilibrium problems (SNEPs), it is natural for players to be uncertain about their complex environments and have multi-dimensional unknown parameters in their models. Among various SNEPs, this paper focuses on locally coupled network games where the objective of each rational player is subject to the aggregate influence of its neighbors. We propose a distributed learning algorithm based on the proximal-point iteration and ordinary least-square estimator, where each player repeatedly updates the local estimates of neighboring decisions, makes its augmented best-response decisions given the current estimated parameters, receives the realized objective values, and learns the unknown parameters. Leveraging the Robbins-Siegmund theorem and the law of large deviations for M-estimators, we establish the almost sure convergence of the proposed algorithm to solutions of SNEPs when the updating step sizes decay at a proper rate.
APA
Huang, Y. & Hu, J.. (2022). Distributed Stochastic Nash Equilibrium Learning in Locally Coupled Network Games with Unknown Parameters. Proceedings of The 4th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 168:342-354 Available from https://proceedings.mlr.press/v168/huang22a.html.

Related Material