Q-learning with Nearest Neighbors

Abstract

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 $\epsilon$-accurate estimate of the optimal Q-function using $\tilde{O}(L/({\epsilon }^3(1-\gamma {)}^7))$ samples. For instance, for a well-behaved MDP, the covering time of the sample path under the purely random policy scales as $\tilde{O}(1/{\epsilon }^d),$ so the sample complexity scales as $\tilde{O}(1/{\epsilon }^{d+3}).$ Indeed, we establish a lower bound that argues that the dependence of $\tilde{\Omega }(1/{\epsilon }^{d+2})$ is necessary.

Accepted to NIPS 2018

Cited by in corpus (6)

• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
• Recurrent Value Functions
• Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation
• Deep SIMBAD: Active Landmark-based Self-localization Using Ranking -based Scene Descriptor
• Option Discovery in the Absence of Rewards with Manifold Analysis