In this paper we consider the problem of computing an $\epsilon$-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
$\gamma\in(0,1)$, and rewards in range $[0, 1]$ we provide an algorithm which
computes an $\epsilon$-optimal policy with probability $1 - \delta$ where
\emph{both} the time spent and number of sample taken are upper bounded by \[
O\left[\frac{|S||A|}{(1-\gamma)^3 \epsilon^2} \log
\left(\frac{|S||A|}{(1-\gamma)\delta \epsilon}
\right)
\log\left(\frac{1}{(1-\gamma)\epsilon}\right)\right] ~. \] For fixed values
of $\epsilon$, this improves upon the previous best known bounds by a factor of
$(1 - \gamma)^{-1}$ and matches the sample complexity lower bounds proved in
Azar et al. (2013) up to logarithmic factors. We also extend our method to
computing $\epsilon$-optimal policies for finite-horizon MDP with a generative
model and provide a nearly matching sample complexity lower bound.