Polynomial Convergence of Bandit No-Regret Dynamics in Congestion 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_ | 1866910300652961792 |
|---|---|
| author | Dadi, Leello Panageas, Ioannis Skoulakis, Stratis Viano, Luca Cevher, Volkan |
| author_facet | Dadi, Leello Panageas, Ioannis Skoulakis, Stratis Viano, Luca Cevher, Volkan |
| contents | We introduce an online learning algorithm in the bandit feedback model that, once adopted by all agents of a congestion game, results in game-dynamics that converge to an $ε$-approximate Nash Equilibrium in a polynomial number of rounds with respect to $1/ε$, the number of players and the number of available resources. The proposed algorithm also guarantees sublinear regret to any agent adopting it. As a result, our work answers an open question from arXiv:2206.01880 and extends the recent results of arXiv:2306.15543 to the bandit feedback model. We additionally establish that our online learning algorithm can be implemented in polynomial time for the important special case of Network Congestion Games on Directed Acyclic Graphs (DAG) by constructing an exact $1$-barycentric spanner for DAGs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09628 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polynomial Convergence of Bandit No-Regret Dynamics in Congestion Games Dadi, Leello Panageas, Ioannis Skoulakis, Stratis Viano, Luca Cevher, Volkan Computer Science and Game Theory We introduce an online learning algorithm in the bandit feedback model that, once adopted by all agents of a congestion game, results in game-dynamics that converge to an $ε$-approximate Nash Equilibrium in a polynomial number of rounds with respect to $1/ε$, the number of players and the number of available resources. The proposed algorithm also guarantees sublinear regret to any agent adopting it. As a result, our work answers an open question from arXiv:2206.01880 and extends the recent results of arXiv:2306.15543 to the bandit feedback model. We additionally establish that our online learning algorithm can be implemented in polynomial time for the important special case of Network Congestion Games on Directed Acyclic Graphs (DAG) by constructing an exact $1$-barycentric spanner for DAGs. |
| title | Polynomial Convergence of Bandit No-Regret Dynamics in Congestion Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2401.09628 |