Efficient Distributed Learning in Stochastic Non-cooperative Games without Information Exchange
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917081515032576 |
|---|---|
| author | Li, Haidong Sheng, Anzhi Peng, Yijie Wang, Long |
| author_facet | Li, Haidong Sheng, Anzhi Peng, Yijie Wang, Long |
| contents | In this work, we study stochastic non-cooperative games, where only noisy black-box function evaluations are available to estimate the cost function for each player. Since each player's cost function depends on both its own decision variables and its rivals' decision variables, local information needs to be exchanged through a center/network in most existing work for seeking the Nash equilibrium. We propose a new stochastic distributed learning algorithm that does not require communications among players. The proposed algorithm uses simultaneous perturbation method to estimate the gradient of each cost function, and uses mirror descent method to search for the Nash equilibrium. We provide asymptotic analysis for the bias and variance of gradient estimates, and show the proposed algorithm converges to the Nash equilibrium in mean square for the class of strictly monotone games at a rate faster than the existing algorithms. The effectiveness of the proposed method is buttressed in a numerical experiment. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_11324 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Efficient Distributed Learning in Stochastic Non-cooperative Games without Information Exchange Li, Haidong Sheng, Anzhi Peng, Yijie Wang, Long Computer Science and Game Theory In this work, we study stochastic non-cooperative games, where only noisy black-box function evaluations are available to estimate the cost function for each player. Since each player's cost function depends on both its own decision variables and its rivals' decision variables, local information needs to be exchanged through a center/network in most existing work for seeking the Nash equilibrium. We propose a new stochastic distributed learning algorithm that does not require communications among players. The proposed algorithm uses simultaneous perturbation method to estimate the gradient of each cost function, and uses mirror descent method to search for the Nash equilibrium. We provide asymptotic analysis for the bias and variance of gradient estimates, and show the proposed algorithm converges to the Nash equilibrium in mean square for the class of strictly monotone games at a rate faster than the existing algorithms. The effectiveness of the proposed method is buttressed in a numerical experiment. |
| title | Efficient Distributed Learning in Stochastic Non-cooperative Games without Information Exchange |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2201.11324 |