# Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 45 references that are in the map.
- First posted on arXiv 9 Oct 2021.

## Builds on (most cited first, 28 of 28)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [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)
- [Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates](https://mlsanity.com/paper/1610.00633/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion](https://mlsanity.com/paper/1807.01675/) (2018)
- [Parameter Space Noise for Exploration](https://mlsanity.com/paper/1706.01905/) (2017)
- [Neural Episodic Control](https://mlsanity.com/paper/1703.01988/) (2017)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Model-Free Episodic Control](https://mlsanity.com/paper/1606.04460/) (2016)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Schema Networks: Zero-shot Transfer with a Generative Causal Model of Intuitive Physics](https://mlsanity.com/paper/1706.04317/) (2017)
- [Episodic Memory Deep Q-Networks](https://mlsanity.com/paper/1805.07603/) (2018)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Learning to Control in Metric Space with Optimal Regret](https://mlsanity.com/paper/1905.01576/) (2019)

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

- [CodePDE: An Inference Framework for LLM-driven PDE Solver Generation](https://mlsanity.com/paper/2505.08783/) (2025)
- [Thinking vs. Doing: Agents that Reason by Scaling Test-Time Interaction](https://mlsanity.com/paper/2506.07976/) (2025)
- [Specialized Foundation Models Struggle to Beat Supervised Baselines](https://mlsanity.com/paper/2411.02796/) (2024)
- [CAT: Content-Adaptive Image Tokenization](https://mlsanity.com/paper/2501.03120/) (2025)
- [RoSGAS: Adaptive Social Bot Detection with Reinforced Self-Supervised GNN Architecture Search](https://mlsanity.com/paper/2206.06757/) (2022)
- [Improving Policy Exploitation in Online Reinforcement Learning with Instant Retrospect Action](https://mlsanity.com/paper/2601.19720/) (2026)
- [Reinforcement Learning for Personalized Drug Discovery and Design for Complex Diseases: A Systems Pharmacology Perspective](https://mlsanity.com/paper/2201.08894/) (2022)
- [Hardware-Software Collaborative Computing of Photonic Spiking Reinforcement Learning for Robotic Continuous Control](https://mlsanity.com/paper/2512.00427/) (2025)
- [SAVGO: Learning State-Action Value Geometry with Cosine Similarity for Continuous Control](https://mlsanity.com/paper/2605.00787/) (2026)
- [Expert Behavior Prior Reinforcement Learning](https://mlsanity.com/paper/2607.21302/) (2026)
- [Improving Online Reinforcement Learning via Bidirectional Behavior Prior Distillation](https://mlsanity.com/paper/2609.20268/) (2026)

## Abstract (arXiv)

Recently, deep reinforcement learning (RL) has achieved remarkable empirical success by integrating deep neural networks into RL frameworks. However, these algorithms often require a large number of training samples and admit little theoretical understanding. To mitigate these issues, we propose a theoretically principled nearest neighbor (NN) function approximator that can improve the value networks in deep RL methods. Inspired by human similarity judgments, the NN approximator estimates the action values using rollouts on past observations and can provably obtain a small regret bound that depends only on the intrinsic complexity of the environment. We present (1) Nearest Neighbor Actor-Critic (NNAC), an online policy gradient algorithm that demonstrates the practicality of combining function approximation with deep RL, and (2) a plug-and-play NN update module that aids the training of existing deep RL methods. Experiments on classical control and MuJoCo locomotion tasks show that the NN-accelerated agents achieve higher sample efficiency and stability than the baseline agents. Based on its theoretical benefits, we believe that the NN approximator can be further applied to other complex domains to speed-up learning.