Last-iterate Convergence in Regularized Graphon Mean Field Game
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910645379661824 |
|---|---|
| author | Dong, Jing Wang, Baoxiang Yu, Yaoliang |
| author_facet | Dong, Jing Wang, Baoxiang Yu, Yaoliang |
| contents | To model complex real-world systems, such as traders in stock markets, or the dissemination of contagious diseases, graphon mean-field games (GMFG) have been proposed to model many agents. Despite the empirical success, our understanding of GMFG is limited. Popular algorithms such as mirror descent are deployed but remain unknown for their convergence properties. In this work, we give the first last-iterate convergence rate of mirror descent in regularized monotone GMFG. In tabular monotone GMFG with finite state and action spaces and under bandit feedback, we show a last-iterate convergence rate of $O(T^{-1/4})$. Moreover, when exact knowledge of costs and transitions is available, we improve this convergence rate to $O(T^{-1})$, matching the existing convergence rate observed in strongly convex games. In linear GMFG, our algorithm achieves a last-iterate convergence rate of $O(T^{-1/5})$. Finally, we verify the performance of the studied algorithms by empirically testing them against fictitious play in a variety of tasks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08746 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Last-iterate Convergence in Regularized Graphon Mean Field Game Dong, Jing Wang, Baoxiang Yu, Yaoliang Computer Science and Game Theory To model complex real-world systems, such as traders in stock markets, or the dissemination of contagious diseases, graphon mean-field games (GMFG) have been proposed to model many agents. Despite the empirical success, our understanding of GMFG is limited. Popular algorithms such as mirror descent are deployed but remain unknown for their convergence properties. In this work, we give the first last-iterate convergence rate of mirror descent in regularized monotone GMFG. In tabular monotone GMFG with finite state and action spaces and under bandit feedback, we show a last-iterate convergence rate of $O(T^{-1/4})$. Moreover, when exact knowledge of costs and transitions is available, we improve this convergence rate to $O(T^{-1})$, matching the existing convergence rate observed in strongly convex games. In linear GMFG, our algorithm achieves a last-iterate convergence rate of $O(T^{-1/5})$. Finally, we verify the performance of the studied algorithms by empirically testing them against fictitious play in a variety of tasks. |
| title | Last-iterate Convergence in Regularized Graphon Mean Field Game |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2410.08746 |