Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation

Junhong Shen, Lin F. Yang

Abstract

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

Introduction

This work, presented at AAAI-21, bridges the gap between the rigorous theoretical guarantees of tabular Reinforcement Learning (RL) and the empirical power of Deep RL. The authors introduce a nearest-neighbor-based value function approximator that significantly accelerates training and provides a provable regret bound based on the "intrinsic" rather than "ambient" dimensionality of the environment. By exploiting the intrinsic low-dimensional structure of complex state spaces, the proposed method achieves faster convergence and provides theoretical guarantees that standard deep neural networks often lack.

The Challenge of Sample Efficiency in Deep RL

Deep RL has seen massive success, but it faces three major hurdles:

  1. Sample Inefficiency: Algorithms like PPO or SAC often require millions of interactions to learn simple tasks.
  2. Lack of Theory: It is often unclear why a deep RL agent succeeds or fails in a specific environment.
  3. Instability: Online learning with deep neural networks is notoriously unstable and highly sensitive to hyperparameters.

While tabular RL has a solid theoretical foundation, it fails in the real world because state spaces are often infinite or astronomically large (the "Curse of Dimensionality"). This paper seeks a middle ground: a non-parametric approach that generalizes like a neural network but is mathematically grounded like a tabular method.

Nearest Neighbor Function Approximation

The core innovation is the Nearest Neighbor (NN) Function Approximator. Instead of relying solely on a neural network to estimate the value of a state, the system looks at the most similar states it has seen in the past.

  • The NN Critic: Given a new state-action pair, the algorithm finds the closest previously visited sample in its history. It estimates the value by taking the reward of that past sample and adding a Lipschitz confidence term ($L \cdot \text{distance}$). This term acts as an "upper-confidence bound," naturally encouraging the agent to explore areas where the distance to known data is large.
  • NNAC (Nearest Neighbor Actor-Critic): An algorithm where the "Actor" (policy) is a neural network, but the "Critic" (value estimator) is this non-parametric NN structure.
  • Plug-and-Play Module: Recognizing that neural networks eventually outperform NN search as data accumulates, the authors created a "soft update" module. It uses an exponentially decaying weight to let the NN critic guide the agent during the early "starter" phase of training, gradually handing over full control to the standard deep RL architecture (like TD3 or DDPG).

Experimental Evaluation

The authors evaluated their approach on two main benchmarks: CartPole-v1 (tested with various input dimensions and raw pixels) and MuJoCo Locomotion tasks (Ant-v2, Hopper-v2, Walker2d-v2, and HalfCheetah-v2).

NNAC performance on CartPole-v1. (a) Comparison against baselines with internal state descriptors. (b) Robustness to varying input dimensions and pixel-based inputs.

Key Results

  • Superior Efficiency: In CartPole, the NNAC agent learned significantly faster than baselines like PPO, SAC, and Neural Episodic Control (NEC).
  • Robustness to Dimensions: When the CartPole state was projected into 100 dimensions, NNAC's performance barely degraded, while other algorithms struggled.
  • MuJoCo Gains: Adding the NN "plug-and-play" module to TD3 (creating NNTD3) resulted in higher average returns across all tasks. For example, in Walker2d-v2, NNTD3 achieved a score of 5170.20 compared to the baseline TD3's 4260.23.
Performance of NNTD3 compared to baseline TD3 and other variants on the Walker2d-v2 task.
  • Stability: The NN-augmented agents showed much lower variance across different random seeds, suggesting the approach helps mitigate the "brittleness" of Deep RL.

Discussion and Future Work

The NN approach's regret bound depends on the intrinsic dimension of the environment rather than the ambient dimension of the input. This explains why it works well on high-dimensional pixel data where the underlying physics have few degrees of freedom.

However, limitations remain:

  • Computational Complexity: Finding the nearest neighbor in a massive history buffer is expensive. While the authors use Kd-trees to speed this up, search time can become a bottleneck as the experience buffer grows.
  • Deterministic Assumption: The current theoretical proofs assume a deterministic environment. Extending these guarantees to stochastic environments is a noted area for future research.
  • Metric Selection: Performance relies on having a meaningful distance metric. While $L_2$ distance worked well for physical states, more complex tasks might require learned metrics to define similarity effectively.

Summary updated

Abstract

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 replace 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.
BibTeX
@inproceedings{shen2021theoretically,
  author = {Junhong Shen and Lin F. Yang},
  title = {{Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=rkSk754LCfx},
}
Figure