In machine learning, choosing the right model complexity is a fundamental balancing act. If a model is too simple, it fails to capture the underlying patterns of the data (high bias); if it is too complex, it overfits to noise and requires excessive data to converge (high variance). Traditionally, researchers have relied on cross-validation to find this "Goldilocks" zone, but in dynamic settings like Reinforcement Learning (RL) or online bandits, we often cannot afford the luxury of a hold-out set.
A growing body of research proposes a structured solution: organizing potential models into a nested hierarchy of hypothesis classes and adaptively "graduating" to higher complexity only when the data demands it.
The Logic of Nested Hierarchies
The core idea, rooted in Structural Risk Minimization (SRM), is to define a sequence of model classes $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \dots \subset \mathcal{H}_M$ with increasing complexity, such as neural networks of increasing width or polynomials of increasing degree.
By starting with the simplest class $\mathcal{H}_1$, an algorithm can achieve very low "estimation error" (the cost of learning parameters) because the search space is small. As Stamouli et al. demonstrate in the context of nonlinear dynamics, this allows a system to identify the most generalizable model by balancing this estimation error against the "approximation error" (how well the model class can actually represent the truth).
Detecting Misspecification
The critical challenge is knowing when to move from a simple model to a more complex one. If we move too early, we suffer from high regret; if we move too late, we fail to learn the task.
Recent algorithms use statistical tests to detect misspecification. For example, Foster et al. introduced ModCB, which uses a novel estimator to sense when a larger model is needed. The algorithm monitors the performance of the current simple model; if the observed rewards deviate significantly from what the simple model predicts, it signals that the model class is insufficient.
Similarly, Muthukumar and Krishnamurthy and Muthukumar developed algorithms that start with a basic multi-armed bandit model and only transition to a complex linear contextual model if a statistical test confirms that the rewards are truly context-dependent. This "one-way permanent switch," also explored by Chatterji et al. in their OSOM algorithm, ensures the learner achieves the "best of both worlds": optimal performance in simple environments without losing the ability to solve complex ones.
Efficiency Through Parsimony
This hierarchical approach is not just about accuracy; it is about efficiency. In computer vision, Jepson showed that rigid motion segmentation can be made orders of magnitude faster by starting with simple 2D affine transformations and only upgrading to 3D models when error residuals indicate the 2D model has failed.
In the realm of active learning, Hanneke proved that navigating a hierarchy of hypothesis classes allows a learner to minimize label requests, starting with coarse models and refining them as more data accumulates. This follows the principle of parsimony: the simplest explanation that fits the data is usually the best.
Meta-Algorithms and Generalization
The beauty of this framework is its modularity. Meta-algorithms like Explore-Commit-Eliminate (ECE), proposed by Lee et al., treat the underlying learning models as "black boxes." This allows researchers to apply hierarchical selection to a wide variety of problems, from offline RL Dai et al. to general function approximations Ghosh and Chowdhury.
Even in boosting, the principle holds. Cortes et al. showed that adaptively selecting base learners from subfamilies of varying complexity—applying SRM at every iteration—provides the formal generalization guarantees that explain the practical success of modern gradient boosting libraries.
The Adaptivity Gap
Despite these successes, there are fundamental limits. Hanneke et al. identified an "adaptivity gap" in transfer learning, proving that without some prior knowledge of how tasks relate, an algorithm might still be slower than an "oracle" that knows the optimal complexity in advance. However, by using nested hierarchies, modern algorithms come as close as theoretically possible to this oracle performance, automatically scaling their complexity to match the hidden structure of the world.
Key Foundational Work
Three Approaches to Probability Model Selection (1994) — contributed 1 concept elements to this direction.
Structural Risk Minimization for Character Recognition (1991) — contributed 1 concept elements to this direction.