  Analyzing the Markov decision process (MDP) with continuous state spaces is
generally challenging. A recent interesting work \cite{shah2018q} solves MDP
with bounded continuous state space by a nearest neighbor $Q$ learning
approach, which has a sample complexity of
$\tilde{O}(\frac{1}{\epsilon^{d+3}(1-\gamma)^{d+7}})$ for $\epsilon$-accurate
$Q$ function estimation with discount factor $\gamma$. In this paper, we
propose two new nearest neighbor $Q$ learning methods, one for the offline
setting and the other for the online setting. We show that the sample
complexities of these two methods are
$\tilde{O}(\frac{1}{\epsilon^{d+2}(1-\gamma)^{d+2}})$ and
$\tilde{O}(\frac{1}{\epsilon^{d+2}(1-\gamma)^{d+3}})$ for offline and online
methods respectively, which significantly improve over existing results and
have minimax optimal dependence over $\epsilon$. We achieve such improvement by
utilizing the samples more efficiently. In particular, the method in
\cite{shah2018q} clears up all samples after each iteration, thus these samples
are somewhat wasted. On the other hand, our offline method does not remove any
samples, and our online method only removes samples with time earlier than
$\beta t$ at time $t$ with $\beta$ being a tunable parameter, thus our methods
significantly reduce the loss of information. Apart from the sample complexity,
our methods also have additional advantages of better computational complexity,
as well as suitability to unbounded state spaces.
