We consider model-free reinforcement learning for infinite-horizon discounted
Markov Decision Processes (MDPs) with a continuous state space and unknown
transition kernel, when only a single sample path under an arbitrary policy of
the system is available. We consider the Nearest Neighbor Q-Learning (NNQL)
algorithm to learn the optimal Q function using nearest neighbor regression
method. As the main contribution, we provide tight finite sample analysis of
the convergence rate. In particular, for MDPs with a $d$-dimensional state
space and the discounted factor $\gamma \in (0,1)$, given an arbitrary sample
path with "covering time" $ L $, we establish that the algorithm is guaranteed
to output an $\varepsilon$-accurate estimate of the optimal Q-function using
$\tilde{O}\big(L/(\varepsilon^3(1-\gamma)^7)\big)$ samples. For instance, for a
well-behaved MDP, the covering time of the sample path under the purely random
policy scales as $ \tilde{O}\big(1/\varepsilon^d\big),$ so the sample
complexity scales as $\tilde{O}\big(1/\varepsilon^{d+3}\big).$ Indeed, we
establish a lower bound that argues that the dependence of $
\tilde{\Omega}\big(1/\varepsilon^{d+2}\big)$ is necessary.

该论文研究利用最近邻回归方法的最近邻 Q 学习算法，从单一样本路径中学习具有连续状态空间和未知转移核的无限期贴现 MDPs 的最优 Q 函数，提供了紧密的有限样本收敛速率分析和样本复杂度。