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

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2020.

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

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [MADE: Exploration via Maximizing Deviation from Explored Regions](https://mlsanity.com/paper/2106.10268/) (2021)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theory](https://mlsanity.com/paper/2202.04970/) (2022)
- [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022)
- [Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation](https://mlsanity.com/paper/2108.08765/) (2021)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Towards a Dimension-Free Understanding of Adaptive Linear Control](https://mlsanity.com/paper/2103.10620/) (2021)
- [Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2406.13633/) (2024)
- [Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Data](https://mlsanity.com/paper/2403.11841/) (2024)

## Abstract (arXiv)

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 tildeO(δF H2 √T) regret, where δF characterizes the intrinsic complexity of the function class 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.