Model Selection in Reinforcement Learning with General Function Approximations

Avishek Ghosh, Sayak Ray Chowdhury

This paper, titled "Model Selection in Reinforcement Learning with General Function Approximations," presents a theoretical breakthrough in how Reinforcement Learning (RL) agents can automatically determine the right level of complexity for their models.

TL;DR

The authors propose two new algorithms, Adaptive Bandit Learning (ABL) and Adaptive Reinforcement Learning (ARL), that automatically identify the simplest model class capable of representing an environment. Crucially, they prove that the "cost" of this automatic selection is just a small additive term in the total regret, meaning the agent performs nearly as well as an "oracle" that was told the correct model class from the start.

What Problem Does This Paper Address?

In RL, agents must learn to approximate complex functions, such as the reward function in a Multi-Armed Bandit (MAB) or the transition kernel in a Markov Decision Process (MDP). To do this, researchers usually assume the true function belongs to a specific "hypothesis class" (e.g., linear functions).

However, in the real world, we rarely know the "correct" class. This leads to a dilemma:

  1. Under-modeling: If you choose a class that is too simple (e.g., linear when the world is quadratic), the agent will never learn the true environment, leading to "linear regret" (it keeps making the same mistakes forever).
  2. Over-modeling: If you choose a class that is too complex, the agent will take a very long time to learn because it's searching through too many possibilities, leading to high "variance" and poor performance.

The goal of model selection is to give the agent a set of nested classes—from very simple to very complex—and have it automatically "adapt" to the smallest one that contains the truth.

Methods

The authors introduce a framework where an agent is given $M$ nested hypothesis classes ($\mathcal{F}_1 \subset \mathcal{F}_2 \subset \dots \subset \mathcal{F}_M$). They assume the true model lies in some unknown class $\mathcal{F}_{m^*}$.

The Core Idea: Doubling Epochs and Test Statistics

The proposed algorithms, ABL (for bandits) and ARL (for MDPs), operate in "doubling epochs." At the start of each epoch, the agent performs a model selection step:

  1. Regression Oracle: It uses data from all previous epochs to compute the minimum average squared prediction error for each class.
  2. Thresholding: Because the classes are nested, the largest class ($\mathcal{F}_M$) is guaranteed to contain the truth. The agent uses the error of this "big" class as a baseline. It then picks the smallest class whose error is close enough (within a calculated threshold) to this baseline.
  3. Optimistic Learning: Once a class is selected, the agent runs a standard "optimistic" RL algorithm (like UCRL-VTR) specifically for that class for the remainder of the epoch.

Key Assumption: Local Separability

To make this work for general function approximations (not just linear ones), the authors introduce a Local Separability condition. This essentially means there is a detectable "gap" between the true model and any model in a class that is too small to represent it.

Datasets

This is a theoretical paper focused on algorithmic analysis and regret bounds; therefore, no empirical datasets or benchmarks were used. The results are proven mathematically for any function classes that satisfy certain complexity measures (specifically, bounded metric entropy and eluder dimension).

Key Insights and Ideas

  • Additive vs. Multiplicative Cost: Previous "corralling" approaches to model selection often resulted in a multiplicative regret penalty (e.g., the total regret was multiplied by $\sqrt{M}$). This paper shows that with a nested structure and a separability assumption, the cost is additive and grows only logarithmically with time ($\log T$).
  • The "Free" Model Selection: Because the cost is additive and logarithmic, for a sufficiently long learning horizon, the model selection cost becomes negligible. The agent effectively gets the benefits of the simpler model "for free."
  • Leveraging the "Big" Class: A clever insight is using the largest class as a reliable anchor. Since we assume the truth is somewhere in the nested stack, the largest class acts as a "realizable" baseline to help judge the smaller classes.

Key Results

The authors provide rigorous "regret bounds"—mathematical guarantees on how much reward the agent loses compared to an optimal strategy:

  • Regret Scaling: The regret of ABL and ARL scales with the complexity (eluder dimension $d^*$ and metric entropy $M^*$) of the smallest correct class $\mathcal{F}_{m^*}$.
  • Oracle Match: The dominant term in their regret bound matches the performance of an agent that knew $m^*$ a priori.
  • Efficiency: They show that the agent identifies the correct model class $m^*$ with high probability after a finite number of steps, which depends on the "gap" (separability) between the classes.

Limitations and Future Work

  • The Separability Gap: The results rely on the "Local Separability" assumption. If two model classes are nearly indistinguishable, the agent might take a very long time to choose the simpler one.
  • Computational Complexity: The algorithms require solving an offline regression problem over potentially complex function classes at the start of every epoch. In practice, this could be computationally expensive.
  • Removing Separability: The authors explicitly note that achieving these "oracle-matching" results without the separability assumption is a major open challenge for future research.

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 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., \(\mathcal {F}\) and \(\mathcal {M}\)) 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},
}

Loading related content...

Figure