# Minimax Optimal Q Learning with Nearest Neighbors

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

## 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 (most cited first, 30 of 39)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems](https://mlsanity.com/paper/2203.01387/) (2022)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Deep Reinforcement Learning with a Natural Language Action Space](https://mlsanity.com/paper/1511.04636/) (2015)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Challenges and Opportunities in Offline Reinforcement Learning from Visual Observations](https://mlsanity.com/paper/2206.04779/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/2007.05078/) (2020)
- [Analysis of KNN Density Estimation](https://mlsanity.com/paper/2010.00438/) (2020)
- [Kernel-Based Reinforcement Learning: A Finite-Time Analysis](https://mlsanity.com/paper/2004.05599/) (2020)

## Built on by (most cited first, 8 of 8)

- [CT-PatchTST: Channel-Time Patch Time-Series Transformer for Long-Term Renewable Energy Forecasting](https://mlsanity.com/paper/2501.08620/) (2025)
- [Effects of Prompt Length on Domain-specific Tasks for Large Language Models](https://mlsanity.com/paper/2502.14255/) (2025)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Enhancing Customer Contact Efficiency with Graph Neural Networks in Credit Card Fraud Detection Workflow](https://mlsanity.com/paper/2504.02275/) (2025)
- [Journey into Automation: Image-Derived Pavement Texture Extraction and Evaluation](https://mlsanity.com/paper/2501.02414/) (2025)
- [Developing Cryptocurrency Trading Strategy Based on Autoencoder-CNN-GANs Algorithms](https://mlsanity.com/paper/2412.18202/) (2024)
- [Tutorial on Using Machine Learning and Deep Learning Models for Mental Illness Detection](https://mlsanity.com/paper/2502.04342/) (2025)
- [On Theoretical Limits of Learning with Label Differential Privacy](https://mlsanity.com/paper/2502.14309/) (2025)

## 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.