mlsanityData to 14 Oct 2026

Minimax Optimal Q Learning with Nearest Neighbors

arXiv 2308.01490 ↗First posted 3 Aug 2023cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

Analyzing the Markov decision process (MDP) with continuous state spaces is generally challenging. A recent interesting work citeshah2018q solves MDP with bounded continuous state space by a nearest neighbor Q learning approach, which has a sample complexity of tildeO(frac1εd+3(1-γ)d+7) for ε-accurate Q function estimation with discount factor γ. 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 tildeO(frac1εd+2(1-γ)d+2) and tildeO(frac1εd+2(1-γ)d+3) for offline and online methods respectively, which significantly improve over existing results and have minimax optimal dependence over ε. We achieve such improvement by utilizing the samples more efficiently. In particular, the method in citeshah2018q 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 β t at time t with β 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.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 39 of its 77 references that are in the map. First posted on arXiv 3 Aug 2023.

Builds on

39 of 77 references.

References · 39

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  3. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
  4. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,745
  5. 2020MOReL : Model-Based Offline Reinforcement Learningcited by 590
  6. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  7. 2018Is Q-learning Provably Efficient?cited by 487
  8. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 371
  9. 2022A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problemscited by 231
  10. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
27 more
  1. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  2. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  3. 2015Deep Reinforcement Learning with a Natural Language Action Spacecited by 88
  4. 2022Partially Observable Markov Decision Processes in Robotics: A Surveycited by 86
  5. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  6. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  7. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  8. 2022Challenges and Opportunities in Offline Reinforcement Learning from Visual Observationscited by 63
  9. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  10. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  11. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  12. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  13. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  14. 2018Q-learning with Nearest Neighborscited by 37
  15. 2023Fast Rates for Maximum Entropy Explorationcited by 33
  16. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  17. 2020Analysis of KNN Density Estimationcited by 28
  18. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  19. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  20. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  21. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  22. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16
  23. 2021Adaptive Discretization in Online Reinforcement Learningcited by 12
  24. 2019Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regressioncited by 11
  25. 2020Minimax Optimal Estimation of KL Divergence for Continuous Distributionscited by 11
  26. 2023Robust Nonparametric Regression under Poisoning Attackcited by 11
  27. 2015Markov Decision Processes with Applications in Wireless Sensor Networks: A Surveycited by 5

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 6.

8 papers.

  1. 2025CT-PatchTST: Channel-Time Patch Time-Series Transformer for Long-Term Renewable Energy Forecastingcited by 16
  2. 2025Effects of Prompt Length on Domain-specific Tasks for Large Language Modelscited by 11
  3. 2024Contextual Bandits for Unbounded Context Distributionscited by 8
  4. 2025Enhancing Customer Contact Efficiency with Graph Neural Networks in Credit Card Fraud Detection Workflowcited by 8
  5. 2025Journey into Automation: Image-Derived Pavement Texture Extraction and Evaluationcited by 7
  6. 2024Developing Cryptocurrency Trading Strategy Based on Autoencoder-CNN-GANs Algorithmscited by 3
  7. 2025Tutorial on Using Machine Learning and Deep Learning Models for Mental Illness Detectioncited by 3
  8. 2025On Theoretical Limits of Learning with Label Differential Privacycited by 1