Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation

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

References in corpus (16)

• Playing Atari with Deep Reinforcement Learning
• Trust Region Policy Optimization
• Addressing Function Approximation Error in Actor-Critic Methods
• Dueling Network Architectures for Deep Reinforcement Learning
• Parameter Space Noise for Exploration
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Model-Free Episodic Control
• Schema Networks: Zero-shot Transfer with a Generative Causal Model of Intuitive Physics
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion
• Neural Episodic Control
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Q-learning with Nearest Neighbors
• Learning to Control in Metric Space with Optimal Regret