# Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 46 references that are in the map.
- First posted on arXiv 5 Nov 2021.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [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)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [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)
- [The Barron Space and the Flow-induced Function Spaces for Neural Network Models](https://mlsanity.com/paper/1906.08039/) (2019)
- [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)
- [An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation](https://mlsanity.com/paper/2104.07794/) (2021)
- [Learning to Control in Metric Space with Optimal Regret](https://mlsanity.com/paper/1905.01576/) (2019)

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

- [Reinforcement Learning with Function Approximation: From Linear to Nonlinear](https://mlsanity.com/paper/2302.09703/) (2023)
- [Offline Supervised Learning V.S. Online Direct Policy Optimization: A Comparative Study and A Unified Training Paradigm for Neural Network-Based Optimal Feedback Control](https://mlsanity.com/paper/2211.15930/) (2022)
- [Spectral Representation-based Reinforcement Learning](https://mlsanity.com/paper/2512.15036/) (2025)
- [The L^∞ Learnability of Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2306.02833/) (2023)

## Abstract (arXiv)

Most existing theoretical analysis of reinforcement learning (RL) is limited to the tabular setting or linear models due to the difficulty in dealing with function approximation in high dimensional space with an uncertain environment. This work offers a fresh perspective into this challenge by analyzing RL in a general reproducing kernel Hilbert space (RKHS). We consider a family of Markov decision processes M of which the reward functions lie in the unit ball of an RKHS and transition probabilities lie in a given arbitrary set. We define a quantity called perturbational complexity by distribution mismatch DeltaM(ε) to characterize the complexity of the admissible state-action distribution space in response to a perturbation in the RKHS with scale ε. We show that DeltaM(ε) gives both the lower bound of the error of all possible algorithms and the upper bound of two specific algorithms (fitted reward and fitted Q-iteration) for the RL problem. Hence, the decay of DeltaM(ε) with respect to ε measures the difficulty of the RL problem on M. We further provide some concrete examples and discuss whether DeltaM(ε) decays fast or not in these examples. As a byproduct, we show that when the reward functions lie in a high dimensional RKHS, even if the transition probability is known and the action space is finite, it is still possible for RL problems to suffer from the curse of dimensionality.