Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension

Abstract

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of general function approximation schemes largely remains missing. In this paper, we establish a provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class $\mathcal{F}$, our algorithm achieves a regret bound of $\tilde{O}(\mathrm{poly}(dH)\sqrt{T})$ where $d$ is a complexity measure of $\mathcal{F}$ that depends on the eluder dimension [Russo and Van Roy, 2013] and log-covering numbers, $H$ is the planning horizon, and $T$ is the number interactions with the environment. Our theory generalizes recent progress on RL with linear value function approximation and does not make explicit assumptions on the model of the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.

References in corpus (19)

• Playing Atari with Deep Reinforcement Learning
• Dueling Network Architectures for Deep Reinforcement Learning
• Solving Rubik's Cube with a Robot Hand
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Deep Exploration via Randomized Value Functions
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• On Lower Bounds for Regret in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

Cited by in corpus (25)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Understanding Domain Randomization for Sim-to-real Transfer
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Adaptive Discretization in Online Reinforcement Learning
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Adaptive Discretization for Model-Based Reinforcement Learning
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Online Learning for Unknown Partially Observable MDPs
• A Simple Reward-free Approach to Constrained Reinforcement Learning
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Towards General Function Approximation in Zero-Sum Markov Games
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning
• Learning Stochastic Shortest Path with Linear Function Approximation
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Improved Algorithms for Misspecified Linear Markov Decision Processes
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation