تقرير
Truncated Variance Reduced Value Iteration
| العنوان: | Truncated Variance Reduced Value Iteration |
|---|---|
| المؤلفون: | Jin, Yujia, Karmarkar, Ishani, Sidford, Aaron, Wang, Jiayi |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Data Structures and Algorithms, Mathematics - Optimization and Control |
| الوصف: | We provide faster randomized algorithms for computing an $\epsilon$-optimal policy in a discounted Markov decision process with $A_{\text{tot}}$-state-action pairs, bounded rewards, and discount factor $\gamma$. We provide an $\tilde{O}(A_{\text{tot}}[(1 - \gamma)^{-3}\epsilon^{-2} + (1 - \gamma)^{-2}])$-time algorithm in the sampling setting, where the probability transition matrix is unknown but accessible through a generative model which can be queried in $\tilde{O}(1)$-time, and an $\tilde{O}(s + (1-\gamma)^{-2})$-time algorithm in the offline setting where the probability transition matrix is known and $s$-sparse. These results improve upon the prior state-of-the-art which either ran in $\tilde{O}(A_{\text{tot}}[(1 - \gamma)^{-3}\epsilon^{-2} + (1 - \gamma)^{-3}])$ time [Sidford, Wang, Wu, Ye 2018] in the sampling setting, $\tilde{O}(s + A_{\text{tot}} (1-\gamma)^{-3})$ time [Sidford, Wang, Wu, Yang, Ye 2018] in the offline setting, or time at least quadratic in the number of states using interior point methods for linear programming. We achieve our results by building upon prior stochastic variance-reduced value iteration methods [Sidford, Wang, Wu, Yang, Ye 2018]. We provide a variant that carefully truncates the progress of its iterates to improve the variance of new variance-reduced sampling procedures that we introduce to implement the steps. Our method is essentially model-free and can be implemented in $\tilde{O}(A_{\text{tot}})$-space when given generative model access. Consequently, our results take a step in closing the sample-complexity gap between model-free and model-based methods. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2405.12952 |
| رقم الأكسشن: | edsarx.2405.12952 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |