Rank-One Modified Value Iteration
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911225019891712 |
|---|---|
| author | Kolarijani, Arman Sharifi Ok, Tolga Esfahani, Peyman Mohajerin Kolarijani, Mohamad Amin Sharif |
| author_facet | Kolarijani, Arman Sharifi Ok, Tolga Esfahani, Peyman Mohajerin Kolarijani, Mohamad Amin Sharif |
| contents | In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the transition probability matrix in the policy evaluation step. This rank-one approximation is closely related to the stationary distribution of the corresponding transition probability matrix, which is approximated using the power method. We provide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)value function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01828 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rank-One Modified Value Iteration Kolarijani, Arman Sharifi Ok, Tolga Esfahani, Peyman Mohajerin Kolarijani, Mohamad Amin Sharif Optimization and Control Machine Learning In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the transition probability matrix in the policy evaluation step. This rank-one approximation is closely related to the stationary distribution of the corresponding transition probability matrix, which is approximated using the power method. We provide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)value function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems. |
| title | Rank-One Modified Value Iteration |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2505.01828 |