On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces

Abstract

The classical theory of reinforcement learning (RL) has focused on tabular and linear representations of value functions. Further progress hinges on combining RL with modern function approximators such as kernel functions and deep neural networks, and indeed there have been many empirical successes that have exploited such combinations in large-scale applications. There are profound challenges, however, in developing a theory to support this enterprise, most notably the need to take into consideration the exploration-exploitation tradeoff at the core of RL in conjunction with the computational and statistical tradeoffs that arise in modern function-approximation-based learning systems. We approach these challenges by studying an optimistic modification of the least-squares value iteration algorithm, in the context of the action-value function represented by a kernel function or an overparameterized neural network. We establish both polynomial runtime complexity and polynomial sample complexity for this algorithm, without additional assumptions on the data-generating model. In particular, we prove that the algorithm incurs an $\tilde{\mathcal{O}}({\delta }_{\mathcal{F}}{H}^2\sqrt{T})$ regret, where ${\delta }_{\mathcal{F}}$ characterizes the intrinsic complexity of the function class $\mathcal{F}$, $H$ is the length of each episode, and $T$ is the total number of episodes. Our regret bounds are independent of the number of states, a result which exhibits clearly the benefit of function approximation in RL.

76 pages. The short version of this work appears in NeurIPS 2020

References in corpus (20)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Local and global asymptotic inference in smoothing spline models
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• Frequentist coverage and sup-norm convergence rate in Gaussian process regression
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• On Kernelized Multi-armed Bandits
• Streaming kernel regression with provably adaptive mean, variance, and regularization
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions

Cited by in corpus (7)

• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Towards General Function Approximation in Zero-Sum Markov Games
• A Short Note on the Relationship of Information Gain and Eluder Dimension
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Improved Algorithms for Misspecified Linear Markov Decision Processes