# Reinforcement Learning with Function Approximation: From Linear to Nonlinear

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 63 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 30 of 35)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [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)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [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)
- [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)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [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)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [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)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [A Priori Estimates of the Population Risk for Two-layer Neural Networks](https://mlsanity.com/paper/1810.06397/) (2018)
- [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)
- [Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2206.09421/) (2022)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)

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

- [Unified continuous-time q-learning for mean-field game and mean-field control problems](https://mlsanity.com/paper/2407.04521/) (2024)
- [Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields](https://mlsanity.com/paper/2305.00322/) (2023)
- [Graph Exploration for Effective Multi-agent Q-Learning](https://mlsanity.com/paper/2304.09547/) (2023)
- [The L^∞ Learnability of Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2306.02833/) (2023)

## Abstract (arXiv)

Function approximation has been an indispensable component in modern reinforcement learning algorithms designed to tackle problems with large state spaces in high dimensions. This paper reviews recent results on error analysis for these reinforcement learning algorithms in linear or nonlinear approximation settings, emphasizing approximation error and estimation error/sample complexity. We discuss various properties related to approximation error and present concrete conditions on transition probability and reward function under which these properties hold true. Sample complexity analysis in reinforcement learning is more complicated than in supervised learning, primarily due to the distribution mismatch phenomenon. With assumptions on the linear structure of the problem, numerous algorithms in the literature achieve polynomial sample complexity with respect to the number of features, episode length, and accuracy, although the minimax rate has not been achieved yet. These results rely on the L^∞ and UCB estimation of estimation error, which can handle the distribution mismatch phenomenon. The problem and analysis become substantially more challenging in the setting of nonlinear function approximation, as both L^∞ and UCB estimation are inadequate for bounding the error with a favorable rate in high dimensions. We discuss additional assumptions necessary to address the distribution mismatch and derive meaningful results for nonlinear RL problems.