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

arXiv: https://arxiv.org/abs/2104.07794 · HTML: https://mlsanity.com/paper/2104.07794/

## Key facts

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

## Builds on (most cited first, 27 of 27)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't](https://mlsanity.com/paper/2009.10713/) (2020)
- [A Priori Estimates of the Population Risk for Two-layer Neural Networks](https://mlsanity.com/paper/1810.06397/) (2018)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics](https://mlsanity.com/paper/1904.04326/) (2019)
- [The Barron Space and the Flow-induced Function Spaces for Neural Network Models](https://mlsanity.com/paper/1906.08039/) (2019)
- [Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension](https://mlsanity.com/paper/2005.10804/) (2020)
- [Kolmogorov Width Decay and Poor Approximators in Machine Learning: Shallow Neural Networks, Random Feature Models and Neural Tangent Kernels](https://mlsanity.com/paper/2005.10807/) (2020)

## Built on by (most cited first, 13 of 13)

- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theory](https://mlsanity.com/paper/2202.04970/) (2022)
- [Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations](https://mlsanity.com/paper/2106.11519/) (2021)
- [Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration](https://mlsanity.com/paper/2209.07376/) (2022)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2111.03469/) (2021)
- [Reinforcement Learning with Function Approximation: From Linear to Nonlinear](https://mlsanity.com/paper/2302.09703/) (2023)
- [Policy evaluation from a single path: Multi-step methods, mixing and mis-specification](https://mlsanity.com/paper/2211.03899/) (2022)
- [Inference on Time Series Nonparametric Conditional Moment Restrictions Using General Sieves](https://mlsanity.com/paper/2301.00092/) (2022)
- [The L^∞ Learnability of Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2306.02833/) (2023)
- [Analyzing and Bridging the Gap between Maximizing Total Reward and Discounted Reward in Deep Reinforcement Learning](https://mlsanity.com/paper/2407.13279/) (2024)
- [A priori Estimates for Deep Residual Network in Continuous-time Reinforcement Learning](https://mlsanity.com/paper/2402.16899/) (2024)

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