Abstract
Deep reinforcement learning (RL) has achieved significant empirical success but often suffers from high sample complexity and a lack of theoretical guarantees. To address these challenges, we introduce a theoretically principled nearest neighbor (NN) function approximator designed to enhance value networks in deep RL. By estimating action values through rollouts on historical observations, our approach achieves a regret bound dependent solely on the environment's intrinsic complexity. We demonstrate the effectiveness of this approach through two implementations: Nearest Neighbor Actor-Critic (NNAC) and a modular NN update component for existing algorithms. Empirical evaluations on OpenAI Gym and MuJoCo benchmarks show that NN-accelerated agents exhibit superior sample efficiency and stability compared to state-of-the-art baselines.
Introduction
While deep RL has revolutionized fields like robotics and game-playing, its practical application is often hindered by extreme sample inefficiency. Current methods frequently require millions of interactions to learn effective policies. Furthermore, the "black-box" nature of deep neural networks makes it difficult to provide formal performance guarantees. In contrast, traditional "tabular" RL offers robust theoretical foundations but fails in high-dimensional continuous state spaces due to the curse of dimensionality.
This work bridges the gap between the theoretical rigor of tabular methods and the representational power of deep learning. We propose using Nearest Neighbor (NN) function approximation to leverage the underlying low-dimensional structure often present in high-dimensional inputs, such as raw pixels.
Methodology
The core of our approach is the use of NN function approximation for value estimation. Instead of relying exclusively on a neural network's global generalization, we estimate the value of a state by examining similar historical observations and applying a "Lipschitz bonus" to account for the distance between the current state and its neighbors.
Nearest Neighbor Actor-Critic (NNAC)
NNAC is an online policy gradient algorithm. It utilizes a neural network "Actor" for action selection and a non-parametric NN "Critic." The critic evaluates actions by performing rollouts based on the most similar past experiences, providing a more stable and theoretically grounded value estimate during early training.
Soft Nearest Neighbor Update Module
To enhance existing deep RL frameworks, we developed a "plug-and-play" NN update module. This module is compatible with off-policy algorithms like Deep Deterministic Policy Gradient (DDPG) and Twin Delayed DDPG (TD3). It employs an exponentially decaying weight to allow the NN-based critic to guide the agent during the initial stages of learning—where neural networks are most prone to instability and overestimation—before gradually transitioning to the fully parametric neural network critic.
Empirical Results
We evaluated our methods on standard control benchmarks, focusing on sample efficiency and stability.
Performance on Classical Control
In the OpenAI Gym CartPole-v1 environment, NNAC was tested against several established baselines, including PPO, TRPO, and SAC. As shown in the figure below, NNAC reaches the maximum reward threshold significantly faster than its competitors. This efficiency holds even when the input dimensionality is artificially increased, supporting our theoretical claim that performance depends on intrinsic rather than ambient dimensionality.
Scaling to Complex Locomotion
The modular NN update was applied to TD3 and DDPG and tested on MuJoCo locomotion tasks (Ant, Hopper, Walker2d, and HalfCheetah). The results indicate that the NN-accelerated versions (NNTD3 and NNDDPG) consistently outperform their standard counterparts. Notably, the NN-enhanced agents show much lower variance across training runs, indicating improved stability. For instance, in the Hopper task, NNTD3 achieved an average return of ~3704 compared to TD3's ~2708.
Discussion and Conclusion
Our results suggest that NN function approximation provides a powerful mechanism for accelerating deep RL. By focusing on the intrinsic complexity of the environment, our method maintains efficiency even in high-dimensional state spaces. The Lipschitz-based exploration bonus also provides a principled way to encourage the agent to visit novel states.
Despite these advantages, the computational overhead of nearest neighbor searches remains a challenge. While Kd-trees mitigate this, search times still scale with the size of the experience buffer. Future research will focus on more efficient approximate search techniques and extending the theoretical framework to stochastic environments. Overall, this work provides a promising path toward more sample-efficient and theoretically sound deep reinforcement learning.
Summary updated