# A Short Note on the Relationship of Information Gain and Eluder Dimension

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 17 references that are in the map.
- First posted on arXiv 6 Jul 2021.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity](https://mlsanity.com/paper/2002.07125/) (2020)

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

- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Fast Rates in Pool-Based Batch Active Learning](https://mlsanity.com/paper/2202.05448/) (2022)
- [Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning](https://mlsanity.com/paper/2210.02087/) (2022)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Causal Bandits with General Causal Models and Interventions](https://mlsanity.com/paper/2403.00233/) (2024)
- [Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.04376/) (2023)
- [Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces](https://mlsanity.com/paper/2603.08287/) (2026)

## Abstract (arXiv)

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.