Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917581751844864 |
|---|---|
| author | Mondal, Washim Uddin Aggarwal, Vaneet |
| author_facet | Mondal, Washim Uddin Aggarwal, Vaneet |
| contents | We consider the problem of designing sample efficient learning algorithms for infinite horizon discounted reward Markov Decision Process. Specifically, we propose the Accelerated Natural Policy Gradient (ANPG) algorithm that utilizes an accelerated stochastic gradient descent process to obtain the natural policy gradient. ANPG achieves $\mathcal{O}({ε^{-2}})$ sample complexity and $\mathcal{O}(ε^{-1})$ iteration complexity with general parameterization where $ε$ defines the optimality error. This improves the state-of-the-art sample complexity by a $\log(\frac{1}ε)$ factor. ANPG is a first-order algorithm and unlike some existing literature, does not require the unverifiable assumption that the variance of importance sampling (IS) weights is upper bounded. In the class of Hessian-free and IS-free algorithms, ANPG beats the best-known sample complexity by a factor of $\mathcal{O}(ε^{-\frac{1}{2}})$ and simultaneously matches their state-of-the-art iteration complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_11677 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes Mondal, Washim Uddin Aggarwal, Vaneet Machine Learning Artificial Intelligence We consider the problem of designing sample efficient learning algorithms for infinite horizon discounted reward Markov Decision Process. Specifically, we propose the Accelerated Natural Policy Gradient (ANPG) algorithm that utilizes an accelerated stochastic gradient descent process to obtain the natural policy gradient. ANPG achieves $\mathcal{O}({ε^{-2}})$ sample complexity and $\mathcal{O}(ε^{-1})$ iteration complexity with general parameterization where $ε$ defines the optimality error. This improves the state-of-the-art sample complexity by a $\log(\frac{1}ε)$ factor. ANPG is a first-order algorithm and unlike some existing literature, does not require the unverifiable assumption that the variance of importance sampling (IS) weights is upper bounded. In the class of Hessian-free and IS-free algorithms, ANPG beats the best-known sample complexity by a factor of $\mathcal{O}(ε^{-\frac{1}{2}})$ and simultaneously matches their state-of-the-art iteration complexity. |
| title | Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2310.11677 |