A Short Note on the Relationship of Information Gain and Eluder Dimension
Not on the map. Why?
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.
Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 9 of its 17 references that are in the map. First posted on arXiv 6 Jul 2021.
Builds on
9 of 17 references.
References · 9
- 2017On Kernelized Multi-armed Banditscited by 348
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
- 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
- 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
- 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
- 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
- 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
- 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
Built on by
Citing papers per year: 2021: 1; 2022: 2; 2023: 2; 2024: 1; 2025: 0; 2026: 1.
7 papers.
- 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
- 2022Fast Rates in Pool-Based Batch Active Learningcited by 15
- 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
- 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
- 2024Causal Bandits with General Causal Models and Interventionscited by 7
- 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
- 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2
- 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces9 Mar 2026
- 2024Causal Bandits with General Causal Models and Interventions1 Mar 2024
- 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning8 Feb 2023
- 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications7 Feb 2023
- 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning5 Oct 2022
- 2022Fast Rates in Pool-Based Batch Active Learning11 Feb 2022
- 2021Uniform Generalization Bounds for Overparameterized Neural Networks13 Sep 2021