Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913096429207552 |
|---|---|
| author | Kumar, Navdeep Dahan, Tehila Cohen, Lior Barua, Ananyabrata Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie |
| author_facet | Kumar, Navdeep Dahan, Tehila Cohen, Lior Barua, Ananyabrata Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie |
| contents | We establish an optimal sample complexity of $O(ε^{-2})$ for obtaining an $ε$-optimal global policy using a single-timescale actor-critic (AC) algorithm in infinite-horizon discounted Markov decision processes (MDPs) with finite state-action spaces, improving upon the prior state of the art of $O(ε^{-3})$. Our approach applies STORM (STOchastic Recursive Momentum) to reduce variance in the critic updates. However, because samples are drawn from a nonstationary occupancy measure induced by the evolving policy, variance reduction via STORM alone is insufficient. To address this challenge, we maintain a buffer of small fraction of recent samples and uniformly sample from it for each critic update. Importantly, these mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_01505 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum Kumar, Navdeep Dahan, Tehila Cohen, Lior Barua, Ananyabrata Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie Machine Learning We establish an optimal sample complexity of $O(ε^{-2})$ for obtaining an $ε$-optimal global policy using a single-timescale actor-critic (AC) algorithm in infinite-horizon discounted Markov decision processes (MDPs) with finite state-action spaces, improving upon the prior state of the art of $O(ε^{-3})$. Our approach applies STORM (STOchastic Recursive Momentum) to reduce variance in the critic updates. However, because samples are drawn from a nonstationary occupancy measure induced by the evolving policy, variance reduction via STORM alone is insufficient. To address this challenge, we maintain a buffer of small fraction of recent samples and uniformly sample from it for each critic update. Importantly, these mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability. |
| title | Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2602.01505 |