Truncated Variance Reduced Value Iteration

We provide faster randomized algorithms for computing an ε-optimal policy in a discounted Markov decision process with Atot-state-action pairs, bounded rewards, and discount factor γ. We provide an tildeO(Atot[(1 - γ)-3ε-2 + (1 - γ)-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 tildeO(1)-time, and an tildeO(s + (1-γ)-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 tildeO(Atot[(1 - γ)-3ε-2 + (1 - γ)-3]) time [Sidford, Wang, Wu, Ye 2018] in the sampling setting, tildeO(s + Atot (1-γ)-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 tildeO(Atot)-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.