Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2407.10454 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908402488180736 |
|---|---|
| author | Lee, Jongmin Rakhsha, Amin Ryu, Ernest K. Farahmand, Amir-massoud |
| author_facet | Lee, Jongmin Rakhsha, Amin Ryu, Ernest K. Farahmand, Amir-massoud |
| contents | The Value Iteration (VI) algorithm is an iterative procedure to compute the value function of a Markov decision process, and is the basis of many reinforcement learning (RL) algorithms as well. As the error convergence rate of VI as a function of iteration $k$ is $O(γ^k)$, it is slow when the discount factor $γ$ is close to $1$. To accelerate the computation of the value function, we propose Deflated Dynamics Value Iteration (DDVI). DDVI uses matrix splitting and matrix deflation techniques to effectively remove (deflate) the top $s$ dominant eigen-structure of the transition matrix $\mathcal{P}^π$. We prove that this leads to a $\tilde{O}(γ^k |λ_{s+1}|^k)$ convergence rate, where $λ_{s+1}$is $(s+1)$-th largest eigenvalue of the dynamics matrix. We then extend DDVI to the RL setting and present Deflated Dynamics Temporal Difference (DDTD) algorithm. We empirically show the effectiveness of the proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10454 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deflated Dynamics Value Iteration Lee, Jongmin Rakhsha, Amin Ryu, Ernest K. Farahmand, Amir-massoud Machine Learning Optimization and Control The Value Iteration (VI) algorithm is an iterative procedure to compute the value function of a Markov decision process, and is the basis of many reinforcement learning (RL) algorithms as well. As the error convergence rate of VI as a function of iteration $k$ is $O(γ^k)$, it is slow when the discount factor $γ$ is close to $1$. To accelerate the computation of the value function, we propose Deflated Dynamics Value Iteration (DDVI). DDVI uses matrix splitting and matrix deflation techniques to effectively remove (deflate) the top $s$ dominant eigen-structure of the transition matrix $\mathcal{P}^π$. We prove that this leads to a $\tilde{O}(γ^k |λ_{s+1}|^k)$ convergence rate, where $λ_{s+1}$is $(s+1)$-th largest eigenvalue of the dynamics matrix. We then extend DDVI to the RL setting and present Deflated Dynamics Temporal Difference (DDTD) algorithm. We empirically show the effectiveness of the proposed algorithms. |
| title | Deflated Dynamics Value Iteration |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2407.10454 |