Abstract
Eluder dimension and information gain are two widely used methods of complexity measures in bandit and reinforcement learning. Eluder dimension was originally proposed as a general complexity measure of function classes, but the common examples of where it is known to be small are function spaces (vector spaces). In these cases, the primary tool to upper bound the eluder dimension is the elliptic potential lemma. Interestingly, the elliptic potential lemma also features prominently in the analysis of linear bandits/reinforcement learning and their nonparametric generalization, the information gain. We show that this is not a coincidence—eluder dimension and information gain are equivalent in a precise sense for reproducing kernel Hilbert spaces.
Introduction
In the study of multi-armed bandits and Reinforcement Learning (RL), a central challenge is approximating unknown reward or value functions from sequential observations. To determine the sample complexity—how many samples are required to learn these functions effectively—researchers rely on "complexity measures." Two of the most prominent measures are the Eluder dimension and Information Gain.
While both have been used extensively to derive regret bounds, they stem from different mathematical traditions. The Eluder dimension is a sequential, worst-case metric measuring how many samples are needed to adaptively infer unobserved points. Conversely, Information Gain is an information-theoretic measure tracking the reduction of uncertainty in a function after seeing noisy observations. This paper bridges the gap between these two frameworks, proving that they are fundamentally equivalent when operating within Reproducing Kernel Hilbert Spaces (RKHS).
The Complexity Measure Divide
Historically, the Eluder dimension was proposed as a general measure for any function class. However, its practical application often defaulted to vector spaces where the elliptic potential lemma served as the primary tool for establishing upper bounds. This same lemma is a cornerstone in the analysis of linear bandits and their nonparametric generalizations via Information Gain.
The observation that both measures rely on the same underlying mathematical machinery led to a natural question: Are these two distinct metrics actually measuring the same underlying property of the function space?
Theoretical Framework and Methodology
The authors focus their analysis on function classes defined as balls within an RKHS. To establish a formal link, they introduce a new concept: the Increment of Information Gain. The core of their proof rests on two pivotal lemmas:
- Lemma 3.4: Establishes that if a point is "$\\epsilon$-independent" (the foundational concept of Eluder dimension), then adding that point to a dataset necessarily results in a significant increment in Information Gain.
- Lemma 3.5: Conversely, if adding a point to a dataset results in a large increment of Information Gain, that point must be $\\epsilon$-independent.
By connecting these concepts, the authors demonstrate that the length of an $\\epsilon$-independent sequence (which defines the Eluder dimension) is bounded both above and below by the Critical Information Gain—the threshold where information gain transitions from linear growth to a sublinear plateau.
Key Insights: Submodularity and Dimensionality
A major contribution of this work is the realization that the sequential nature of the Eluder dimension is mirrored by the submodularity of the log-determinant function used in Information Gain. Because Information Gain is submodular, any sequence of points can be rearranged such that the gain is monotonically decreasing. This behavior directly mimics the structure of an Eluder sequence.
Furthermore, the authors argue that both measures capture the "extrinsic" dimensionality of the vector space. They are effective at measuring the overall size of the space but are less sensitive to "intrinsic" structures, such as sparsity or low-rank properties, which might exist within that space.
Results and Implications
The theoretical analysis culminates in Theorems 3.1 and 3.2, which provide formal equivalence bounds. For an RKHS ball of radius $S$, the $\\epsilon$-eluder dimension and the critical information gain are shown to be equivalent up to constant multiplicative factors.
To demonstrate the practical impact of this equivalence, the authors compared two existing RL algorithms:
- KOVI, which utilizes Information Gain.
- $\\mathcal{F}$-LSVI, which utilizes Eluder dimension.
Their findings indicate that in scenarios where the kernel's eigenvalues decay polynomially, the regret bounds derived from Information Gain are actually tighter than those currently provided by Eluder-based analyses. This suggests that the information-theoretic perspective may offer more refined performance guarantees in specific kernelized settings.
Conclusion
By proving the equivalence of Eluder dimension and Information Gain in RKHS, this paper provides a unified perspective on complexity in reinforcement learning. While the Eluder dimension remains a more general tool for arbitrary function classes, in the common case of kernelized RL, the two measures are two sides of the same coin.
Future research is encouraged to look beyond these extrinsic measures. As neither Eluder dimension nor Information Gain is particularly adept at capturing hidden structures like sparsity, the development of "structure-adaptive" complexity measures remains a vital frontier for designing the next generation of efficient RL algorithms.
Summary updated