Near-optimal time and sample complexities for solving Markov decision processes with a generative model

In this paper we consider the problem of computing an ε-optimal policy of a discounted Markov Decision Process (DMDP) provided we can only access its transition function through a generative sampling model that given any state-action pair samples from the transition function in O(1) time. Given such a DMDP with states S, actions A, discount factor γ ∈ (0, 1), and rewards in range [0, 1] we provide an algorithm which computes an ε-optimal policy with probability 1 − δ where both the time spent and number of sample taken are upper bounded by O₍₁^|S||A|_{− γ)32} log₍₁^|S||A|_{− γ)δ} log_{(1 −}¹_γ) . For fixed values of ε, this improves upon the previous best known bounds by a factor of (1 − γ)⁻¹ and matches the sample complexity lower bounds proved in [AMK13] up to logarithmic factors. We also extend our method to computing ε-optimal policies for finite-horizon MDP with a generative model and provide a nearly matching sample complexity lower bound.