Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909187166961664 |
|---|---|
| author | Cai, Yang Luo, Haipeng Wei, Chen-Yu Zheng, Weiqiang |
| author_facet | Cai, Yang Luo, Haipeng Wei, Chen-Yu Zheng, Weiqiang |
| contents | We study policy optimization algorithms for computing correlated equilibria in multi-player general-sum Markov Games. Previous results achieve $O(T^{-1/2})$ convergence rate to a correlated equilibrium and an accelerated $O(T^{-3/4})$ convergence rate to the weaker notion of coarse correlated equilibrium. In this paper, we improve both results significantly by providing an uncoupled policy optimization algorithm that attains a near-optimal $\tilde{O}(T^{-1})$ convergence rate for computing a correlated equilibrium. Our algorithm is constructed by combining two main elements (i) smooth value updates and (ii) the optimistic-follow-the-regularized-leader algorithm with the log barrier regularizer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15240 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games Cai, Yang Luo, Haipeng Wei, Chen-Yu Zheng, Weiqiang Machine Learning Computer Science and Game Theory Optimization and Control We study policy optimization algorithms for computing correlated equilibria in multi-player general-sum Markov Games. Previous results achieve $O(T^{-1/2})$ convergence rate to a correlated equilibrium and an accelerated $O(T^{-3/4})$ convergence rate to the weaker notion of coarse correlated equilibrium. In this paper, we improve both results significantly by providing an uncoupled policy optimization algorithm that attains a near-optimal $\tilde{O}(T^{-1})$ convergence rate for computing a correlated equilibrium. Our algorithm is constructed by combining two main elements (i) smooth value updates and (ii) the optimistic-follow-the-regularized-leader algorithm with the log barrier regularizer. |
| title | Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games |
| topic | Machine Learning Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2401.15240 |