# Model Selection for Generic Reinforcement Learning

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

## Key facts

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

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

- [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)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [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)
- [Open Problem: Model Selection for Contextual Bandits](https://mlsanity.com/paper/2006.10940/) (2020)

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

- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)

## Abstract (arXiv)

We address the problem of model selection for the finite horizon episodic Reinforcement Learning (RL) problem where the transition kernel P^* belongs to a family of models P^* with finite metric entropy. In the model selection framework, instead of P^*, we are given M nested families of transition kernels cP1 subset cP2 subset ldots subset cPM. We propose and analyze a novel algorithm, namely Adaptive Reinforcement Learning (General) (textttARL-GEN) that adapts to the smallest such family where the true transition kernel P^* lies. textttARL-GEN uses the Upper Confidence Reinforcement Learning (textttUCRL) algorithm with value targeted regression as a blackbox and puts a model selection module at the beginning of each epoch. Under a mild separability assumption on the model classes, we show that textttARL-GEN obtains a regret of TildeO(dE^*H2+√dE^* mathbbM^* H2 T), with high probability, where H is the horizon length, T is the total number of steps, dE^* is the Eluder dimension and mathbbM^* is the metric entropy corresponding to P^*. Note that this regret scaling matches that of an oracle that knows P^* in advance. We show that the cost of model selection for textttARL-GEN is an additive term in the regret having a weak dependence on T. Subsequently, we remove the separability assumption and consider the setup of linear mixture MDPs, where the transition kernel P^* has a linear function approximation. With this low rank structure, we propose novel adaptive algorithms for model selection, and obtain (order-wise) regret identical to that of an oracle with knowledge of the true model class.