Truncated Variance Reduced Value Iteration

We provide faster randomized algorithms for computing an ε-optimal policy in a discounted Markov decision process with Aₜₒₜ-state-action pairs, bounded rewards, and discount factor γ. We provide an Õ(Aₜₒₜ[(1 - γ)⁻³ε⁻² + (1 - γ)⁻²])-time algorithm in the sampling setting, where the probability transition matrix is unknown but accessible through a generative model which can be queried in Õ(1)-time, and an Õ(s + (1-γ)⁻²)-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 Õ(Aₜₒₜ[(1 - γ)⁻³ε⁻² + (1 - γ)⁻³]) time [Sidford, Wang, Wu, Ye 2018] in the sampling setting, Õ(s + Aₜₒₜ (1-γ)⁻³) 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 Õ(Aₜₒₜ)-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.