Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Games
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915440569090048 |
|---|---|
| author | Faizal, Fathima Zarin Ozdaglar, Asuman Wainwright, Martin J. |
| author_facet | Faizal, Fathima Zarin Ozdaglar, Asuman Wainwright, Martin J. |
| contents | We study best-response type learning dynamics for zero-sum polymatrix games under two information settings. The two settings are distinguished by the type of information that each player has about the game and their opponents' strategy. The first setting is the full information case, in which each player knows their own and their opponents' payoff matrices and observes everyone's mixed strategies. The second setting is the minimal information case, where players do not observe their opponents' strategies and are not aware of any payoff matrices (instead they only observe their realized payoffs). For this setting, also known as the radically uncoupled case in the learning in games literature, we study a two-timescale learning dynamics that combine smoothed best-response type updates for strategy estimates with a TD-learning update to estimate a local payoff function. For these dynamics, without additional exploration, we provide polynomial-time finite-sample guarantees for convergence to an $ε$-Nash equilibrium. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_20128 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Games Faizal, Fathima Zarin Ozdaglar, Asuman Wainwright, Martin J. Optimization and Control Computer Science and Game Theory Machine Learning We study best-response type learning dynamics for zero-sum polymatrix games under two information settings. The two settings are distinguished by the type of information that each player has about the game and their opponents' strategy. The first setting is the full information case, in which each player knows their own and their opponents' payoff matrices and observes everyone's mixed strategies. The second setting is the minimal information case, where players do not observe their opponents' strategies and are not aware of any payoff matrices (instead they only observe their realized payoffs). For this setting, also known as the radically uncoupled case in the learning in games literature, we study a two-timescale learning dynamics that combine smoothed best-response type updates for strategy estimates with a TD-learning update to estimate a local payoff function. For these dynamics, without additional exploration, we provide polynomial-time finite-sample guarantees for convergence to an $ε$-Nash equilibrium. |
| title | Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Games |
| topic | Optimization and Control Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2407.20128 |