Convergence Rate of Payoff-based Generalized Nash Equilibrium Learning
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_ | 1866916479441567744 |
|---|---|
| author | Tatarenko, Tatiana Kamgarpour, Maryam |
| author_facet | Tatarenko, Tatiana Kamgarpour, Maryam |
| contents | We consider generalized Nash equilibrium (GNE) problems in games with strongly monotone pseudo-gradients and jointly linear coupling constraints. We establish the convergence rate of a payoff-based approach intended to learn a variational GNE (v-GNE) in such games. While convergent algorithms have recently been proposed in this setting given full or partial information of the gradients, rate of convergence in the payoff-based information setting has been an open problem. Leveraging properties of a game extended from the original one by a dual player, we establish a convergence rate of $O(\frac{1}{t^{4/7}})$ to a v-GNE of the game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08595 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Convergence Rate of Payoff-based Generalized Nash Equilibrium Learning Tatarenko, Tatiana Kamgarpour, Maryam Optimization and Control We consider generalized Nash equilibrium (GNE) problems in games with strongly monotone pseudo-gradients and jointly linear coupling constraints. We establish the convergence rate of a payoff-based approach intended to learn a variational GNE (v-GNE) in such games. While convergent algorithms have recently been proposed in this setting given full or partial information of the gradients, rate of convergence in the payoff-based information setting has been an open problem. Leveraging properties of a game extended from the original one by a dual player, we establish a convergence rate of $O(\frac{1}{t^{4/7}})$ to a v-GNE of the game. |
| title | Convergence Rate of Payoff-based Generalized Nash Equilibrium Learning |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2411.08595 |