Model Selection in Reinforcement Learning with General Function Approximations

Avishek Ghosh, Sayak Ray Chowdhury

Abstract

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 $\mathcal{F}$ and $\mathcal{M}$, where the true models — reward generating function for MABs 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 matches that of an oracle which knows the correct function classes (i.e., $\mathcal{F}$ and $\mathcal{M}$) a priori. Furthermore, for both 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$.

Introduction

In modern Reinforcement Learning (RL), agents must navigate environments with vast state and action spaces by approximating complex functions, such as reward distributions in Multi-Armed Bandits (MABs) or transition kernels in Markov Decision Processes (MDPs). Traditionally, these agents rely on a pre-defined hypothesis class (e.g., linear or kernel-based functions). However, choosing the correct class presents a fundamental trade-off: a class that is too simple (under-modeling) leads to persistent errors and linear regret, while a class that is too complex (over-modeling) suffers from high variance and slow convergence.

This paper addresses the challenge of model selection by introducing algorithms that automatically identify the simplest viable model class from a set of nested candidates. By doing so, the agent can achieve performance comparable to an "oracle" that knows the optimal model complexity from the start.

Problem Formulation

We consider a set of $M$ nested hypothesis classes $\mathcal{F}_1 \subset \mathcal{F}_2 \subset \dots \subset \mathcal{F}_M$. The true environment model is assumed to reside within an unknown class $\mathcal{F}_{m^*}$, where $m^* \in \{1, \dots, M\}$ is the index of the smallest class containing the truth. The objective is to design an algorithm that minimizes cumulative regret by adapting to $\mathcal{F}_{m^*}$ without prior knowledge of $m^*$.

To facilitate this in general function spaces, we utilize complexity measures such as the eluder dimension and metric entropy. A critical requirement for the proposed approach is the Local Separability condition, which ensures a detectable statistical gap between the true model and any model belonging to a class that is too restrictive to represent the environment.

Methodology: ABL and ARL

The authors propose two primary algorithms: Adaptive Bandit Learning (ABL) for MABs and Adaptive Reinforcement Learning (ARL) for MDPs. These algorithms operate through a structured process of "doubling epochs."

1. Model Selection via Regression Oracle

At the beginning of each epoch, the agent evaluates the candidate classes using data accumulated from all previous epochs. It employs a regression oracle to calculate the minimum average squared prediction error for each class. Because the classes are nested, the largest class $\mathcal{F}_M$ is guaranteed to contain the true model and serves as a reliable baseline.

2. Thresholding and Selection

The agent compares the error of each smaller class against the baseline established by $\mathcal{F}_M$. It selects the smallest index $m$ such that the error of $\mathcal{F}_m$ is within a mathematically derived threshold of the baseline error. This ensures that the agent does not settle for an under-modeled class while avoiding the unnecessary complexity of over-modeled ones.

3. Optimistic Learning

Once a class $\mathcal{F}_m$ is selected, the agent executes a standard optimistic RL strategy (such as UCRL-VTR) tailored to that specific class for the duration of the epoch. This allows the agent to exploit the environment efficiently while continuing to gather data for future model selection steps.

Theoretical Results

The primary contribution of this work is the derivation of rigorous regret bounds for ABL and ARL. The analysis reveals several key insights:

  • Oracle-Matching Performance: The dominant term in the regret bound scales with the complexity of the smallest correct class $\mathcal{F}_{m^*}$. This means the agent eventually performs as well as if it had been told $m^*$ at time zero.
  • Additive Cost of Selection: Unlike previous "corralling" methods that often result in multiplicative regret penalties (e.g., $\sqrt{M}$ factors), this framework demonstrates that the cost of model selection is merely additive. This cost grows only logarithmically with the time horizon $T$.
  • Efficiency of Identification: Under the local separability assumption, the algorithms identify the correct model index $m^*$ with high probability after a finite number of steps, rendering the model selection cost negligible over long horizons.

Discussion and Limitations

While the paper provides a significant theoretical advancement, it acknowledges certain practical and mathematical constraints. The Local Separability assumption is vital for the additive regret result; without it, distinguishing between nearly identical classes becomes significantly more difficult. Furthermore, the reliance on an offline regression oracle at the start of each epoch may pose computational challenges when dealing with highly complex function classes.

Future research directions include exploring ways to relax the separability requirement and developing more computationally efficient versions of the regression steps for real-time applications. Nonetheless, this work establishes a robust foundation for adaptive model selection in general RL environments.

Summary updated

Abstract

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 $\mathcal{F}$ and $\mathcal{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 \emph{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$.
BibTeX
@inproceedings{ghosh2022model,
  author = {Avishek Ghosh and Sayak Ray Chowdhury},
  title = {{Model Selection in Reinforcement Learning with General Function Approximations}},
  booktitle = {ECML/PKDD},
  year = {2022},
  url = {https://openreview.net/forum?id=FltXNpNN9Y},
}
Figure