# Q-learning with Nearest Neighbors

arXiv: https://arxiv.org/abs/1802.03900 · HTML: https://mlsanity.com/paper/1802.03900/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2018.

## Built on by (most cited first, 30 of 37)

- [The Surprising Effectiveness of Representation Learning for Visual Imitation](https://mlsanity.com/paper/2112.01511/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [q-Learning in Continuous Time](https://mlsanity.com/paper/2207.00713/) (2022)
- [DINOBot: Robot Manipulation via Retrieval and Alignment with Vision Foundation Models](https://mlsanity.com/paper/2402.13181/) (2024)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications](https://mlsanity.com/paper/2312.02828/) (2023)
- [Memory-Consistent Neural Networks for Imitation Learning](https://mlsanity.com/paper/2310.06171/) (2023)
- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation](https://mlsanity.com/paper/2110.04422/) (2021)
- [Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity](https://mlsanity.com/paper/2111.06781/) (2021)
- [Accountability in Offline Reinforcement Learning: Explaining Decisions with a Corpus of Examples](https://mlsanity.com/paper/2310.07747/) (2023)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale](https://mlsanity.com/paper/2403.00222/) (2024)
- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge](https://mlsanity.com/paper/2312.12558/) (2023)
- [Improving Policy Exploitation in Online Reinforcement Learning with Instant Retrospect Action](https://mlsanity.com/paper/2601.19720/) (2026)
- [Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/2409.14557/) (2024)
- [Coarse-Grained Smoothness for RL in Metric Spaces](https://mlsanity.com/paper/2110.12276/) (2021)
- [Learning conditional distributions on continuous spaces](https://mlsanity.com/paper/2406.09375/) (2024)
- [Robust Q-Learning under Corrupted Rewards](https://mlsanity.com/paper/2409.03237/) (2024)
- [Ego-centric Learning of Communicative World Models for Autonomous Driving](https://mlsanity.com/paper/2506.08149/) (2025)
- [Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spaces](https://mlsanity.com/paper/2510.04355/) (2025)
- [Deep SIMBAD: Active Landmark-based Self-localization Using Ranking -based Scene Descriptor](https://mlsanity.com/paper/2109.02786/) (2021)
- [Open-World Distributed Robot Self-Localization with Transferable Visual Vocabulary and Both Absolute and Relative Features](https://mlsanity.com/paper/2109.04569/) (2021)
- [RELDEC: Reinforcement Learning-Based Decoding of Moderate Length LDPC Codes](https://mlsanity.com/paper/2112.13934/) (2021)
- [Active Semantic Localization with Graph Neural Embedding](https://mlsanity.com/paper/2305.06141/) (2023)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)

## Abstract (arXiv)

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 γ ∈ (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 tildeObig(L/(varepsilon3(1-γ)7)big) samples. For instance, for a well-behaved MDP, the covering time of the sample path under the purely random policy scales as  tildeObig(1/varepsilondbig), so the sample complexity scales as tildeObig(1/varepsilond+3big). Indeed, we establish a lower bound that argues that the dependence of  tildeOmegabig(1/varepsilond+2big) is necessary.