On the Convergence of Single-Timescale Actor-Critic
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_ | 1866918045021110272 |
|---|---|
| author | Kumar, Navdeep Agrawal, Priyank Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie |
| author_facet | Kumar, Navdeep Agrawal, Priyank Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie |
| contents | We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces. To this end, we introduce an elegant analytical framework for handling complex, coupled recursions inherent in the algorithm. Leveraging this framework, we establish that the algorithm converges to an $ε$-close \textbf{globally optimal} policy with a sample complexity of \( O(ε^{-3}) \). This significantly improves upon the existing complexity of $O(ε^{-2})$ to achieve $ε$-close \textbf{stationary policy}, which is equivalent to the complexity of $O(ε^{-4})$ to achieve $ε$-close \textbf{globally optimal} policy using gradient domination lemma. Furthermore, we demonstrate that to achieve this improvement, the step sizes for both the actor and critic must decay as \( O(k^{-\frac{2}{3}}) \) with iteration $k$, diverging from the conventional \( O(k^{-\frac{1}{2}}) \) rates commonly used in (non)convex optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08868 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Convergence of Single-Timescale Actor-Critic Kumar, Navdeep Agrawal, Priyank Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie Machine Learning We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces. To this end, we introduce an elegant analytical framework for handling complex, coupled recursions inherent in the algorithm. Leveraging this framework, we establish that the algorithm converges to an $ε$-close \textbf{globally optimal} policy with a sample complexity of \( O(ε^{-3}) \). This significantly improves upon the existing complexity of $O(ε^{-2})$ to achieve $ε$-close \textbf{stationary policy}, which is equivalent to the complexity of $O(ε^{-4})$ to achieve $ε$-close \textbf{globally optimal} policy using gradient domination lemma. Furthermore, we demonstrate that to achieve this improvement, the step sizes for both the actor and critic must decay as \( O(k^{-\frac{2}{3}}) \) with iteration $k$, diverging from the conventional \( O(k^{-\frac{1}{2}}) \) rates commonly used in (non)convex optimization. |
| title | On the Convergence of Single-Timescale Actor-Critic |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.08868 |