First- and Zeroth-Order Learning in Asynchronous Games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918123971543040 |
|---|---|
| author | Wang, Zifan Yi, Xinlei Zavlanos, Michael M. Johansson, Karl H. |
| author_facet | Wang, Zifan Yi, Xinlei Zavlanos, Michael M. Johansson, Karl H. |
| contents | This paper investigates the discrete-time asynchronous games in which noncooperative agents seek to minimize their individual cost functions. Building on the assumption of partial asynchronism, i.e., each agent updates at least once within a fixed-length time interval, we explore the conditions to ensure convergence of such asynchronous games. The analysis begins with a simple quadratic game from which we derive tight convergence conditions through the lens of linear control theory. Then, we provide a quasidominance condition for general convex games. Our results demonstrate that this condition is stringent since when this condition is not satisfied, the asynchronous games may fail to converge. We propose both first- and zeroth-order learning algorithms for asynchronous games, depending on the type of available feedback, and analyze their last-iterate convergence rates. Numerical experiments are presented on economic market problems to verify our results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09111 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | First- and Zeroth-Order Learning in Asynchronous Games Wang, Zifan Yi, Xinlei Zavlanos, Michael M. Johansson, Karl H. Optimization and Control This paper investigates the discrete-time asynchronous games in which noncooperative agents seek to minimize their individual cost functions. Building on the assumption of partial asynchronism, i.e., each agent updates at least once within a fixed-length time interval, we explore the conditions to ensure convergence of such asynchronous games. The analysis begins with a simple quadratic game from which we derive tight convergence conditions through the lens of linear control theory. Then, we provide a quasidominance condition for general convex games. Our results demonstrate that this condition is stringent since when this condition is not satisfied, the asynchronous games may fail to converge. We propose both first- and zeroth-order learning algorithms for asynchronous games, depending on the type of available feedback, and analyze their last-iterate convergence rates. Numerical experiments are presented on economic market problems to verify our results. |
| title | First- and Zeroth-Order Learning in Asynchronous Games |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.09111 |