mlsanityData to 7 Oct 2026

An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation

arXiv 2104.07794 ↗First posted 15 Apr 2021cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning (RL) algorithms based on high-dimensional function approximation have achieved tremendous empirical success in large-scale problems with an enormous number of states. However, most analysis of such algorithms gives rise to error bounds that involve either the number of states or the number of features. This paper considers the situation where the function approximation is made either using the kernel method or the two-layer neural network model, in the context of a fitted Q-iteration algorithm with explicit regularization. We establish an tildeO(H3|mathcal A|frac14n-frac14) bound for the optimal policy with Hn samples, where H is the length of each episode and |mathcal A| is the size of action space. Our analysis hinges on analyzing the L2 error of the approximated Q-function using n data points. Even though this result still requires a finite-sized action space, the error bound is independent of the dimensionality of the state space.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 27 of its 64 references that are in the map. First posted on arXiv 15 Apr 2021.

Builds on

27 of 64 references.

References · 27

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  6. 2018Is Q-learning Provably Efficient?cited by 485
  7. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  8. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  9. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  10. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  11. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  12. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
15 more
  1. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  2. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  4. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
  5. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  6. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  7. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  8. 2020Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don'tcited by 94
  9. 2018A Priori Estimates of the Population Risk for Two-layer Neural Networkscited by 76
  10. 2020On the Similarity between the Laplace and Neural Tangent Kernelscited by 76
  11. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  12. 2019A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamicscited by 49
  13. 2019The Barron Space and the Flow-induced Function Spaces for Neural Network Modelscited by 39
  14. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  15. 2020Kolmogorov Width Decay and Poor Approximators in Machine Learning: Shallow Neural Networks, Random Feature Models and Neural Tangent Kernelscited by 19

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 4; 2023: 3; 2024: 2.

13 papers.

Sort:

  1. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  2. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  3. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  4. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  5. 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
  6. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  7. 2021Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Spacecited by 4
  8. 2023Reinforcement Learning with Function Approximation: From Linear to Nonlinearcited by 4
  9. 2022Policy evaluation from a single path: Multi-step methods, mixing and mis-specificationcited by 3
  10. 2022Inference on Time Series Nonparametric Conditional Moment Restrictions Using General Sievescited by 1
  11. 2024Analyzing and Bridging the Gap between Maximizing Total Reward and Discounted Reward in Deep Reinforcement Learningcited by 1
  12. 2023The L^∞ Learnability of Reproducing Kernel Hilbert Spacescited by 0
1 more
  1. 2024A priori Estimates for Deep Residual Network in Continuous-time Reinforcement Learningcited by 0