# Model Selection in Reinforcement Learning with General Function Approximations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 35 references that are in the map.
- First posted on arXiv 6 Jul 2022.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (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)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension](https://mlsanity.com/paper/2005.10804/) (2020)
- [On Online Learning in Kernelized Markov Decision Processes](https://mlsanity.com/paper/1911.01871/) (2019)
- [OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits](https://mlsanity.com/paper/1905.10040/) (2019)
- [Online Model Selection for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2011.09750/) (2020)
- [Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization](https://mlsanity.com/paper/1608.05749/) (2016)
- [Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits](https://mlsanity.com/paper/2006.02612/) (2020)
- [Corralling Stochastic Bandit Algorithms](https://mlsanity.com/paper/2006.09255/) (2020)
- [Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation](https://mlsanity.com/paper/1906.09255/) (2019)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)

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

- [On the Necessity of Collaboration for Online Model Selection with Decentralized Data](https://mlsanity.com/paper/2404.09494/) (2024)

## Abstract (arXiv)

We consider model selection for classic Reinforcement Learning (RL) environments -- Multi Armed Bandits (MABs) and Markov Decision Processes (MDPs) -- under general function approximations. In the model selection framework, we do not know the function classes, denoted by F and M, where the true models -- reward generating function for MABs and and transition kernel for MDPs -- lie, respectively. Instead, we are given M nested function (hypothesis) classes such that true models are contained in at-least one such class. In this paper, we propose and analyze efficient model selection algorithms for MABs and MDPs, that adapt to the smallest function class (among the nested M classes) containing the true underlying model. Under a separability assumption on the nested hypothesis classes, we show that the cumulative regret of our adaptive algorithms match to that of an oracle which knows the correct function classes (i.e., cF and cM) a priori. Furthermore, for both the settings, we show that the cost of model selection is an additive term in the regret having weak (logarithmic) dependence on the learning horizon T.