mlsanityData to 14 Oct 2026

Q-learning with Nearest Neighbors

arXiv 1802.03900 ↗First posted 12 Feb 2018cs.LG math.OC stat.MLcited by 37

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 3; 2023: 6; 2024: 8; 2025: 5; 2026: 5.

37 papers.

Sort:

By area:

  1. 2021The Surprising Effectiveness of Representation Learning for Visual Imitationcited by 154
  2. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  3. 2022q-Learning in Continuous Timecited by 91
  4. 2024DINOBot: Robot Manipulation via Retrieval and Alignment with Vision Foundation Modelscited by 44
  5. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  6. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  7. 2022Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Pathcited by 20
  8. 2023Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applicationscited by 15
  9. 2023Memory-Consistent Neural Networks for Imitation Learningcited by 14
  10. 2021Adaptive Discretization in Online Reinforcement Learningcited by 12
  11. 2021Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximationcited by 11
  12. 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuitycited by 11
25 more
  1. 2023Accountability in Offline Reinforcement Learning: Explaining Decisions with a Corpus of Examplescited by 9
  2. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  3. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  4. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 7
  5. 2023Sample Efficient Reinforcement Learning with Partial Dynamics Knowledgecited by 4
  6. 2026Improving Policy Exploitation in Online Reinforcement Learning with Instant Retrospect Actioncited by 4
  7. 2024Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learningcited by 3
  8. 2021Coarse-Grained Smoothness for RL in Metric Spacescited by 2
  9. 2024Learning conditional distributions on continuous spacescited by 2
  10. 2024Robust Q-Learning under Corrupted Rewardscited by 2
  11. 2025Ego-centric Learning of Communicative World Models for Autonomous Drivingcited by 2
  12. 2025Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spacescited by 2
  13. 2021Deep SIMBAD: Active Landmark-based Self-localization Using Ranking -based Scene Descriptorcited by 1
  14. 2021Open-World Distributed Robot Self-Localization with Transferable Visual Vocabulary and Both Absolute and Relative Featurescited by 1
  15. 2021RELDEC: Reinforcement Learning-Based Decoding of Moderate Length LDPC Codescited by 1
  16. 2023Active Semantic Localization with Graph Neural Embeddingcited by 1
  17. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  18. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  19. 2024Reinforcement Learning in High-frequency Market Makingcited by 0
  20. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0
  21. 2024Upside-Down Reinforcement Learning for More Interpretable Optimal Controlcited by 0
  22. 2025Deep SOR Minimax Q-learning for Two-player Zero-sum Gamecited by 0
  23. 2026Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?cited by 0
  24. 2026Expert Behavior Prior Reinforcement Learningcited by 0
  25. 2026Improving Online Reinforcement Learning via Bidirectional Behavior Prior Distillationcited by 0