# Understanding the Eluder Dimension

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 59 references that are in the map.
- First posted on arXiv 14 Apr 2021.

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

- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [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)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)
- [Provably Correct Optimization and Exploration with Non-linear Policies](https://mlsanity.com/paper/2103.11559/) (2021)
- [On the Sample Complexity of Reinforcement Learning with Policy Space Generalization](https://mlsanity.com/paper/2008.07353/) (2020)

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

- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback](https://mlsanity.com/paper/2307.02842/) (2023)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Second Order Bounds for Contextual Bandits with Function Approximation](https://mlsanity.com/paper/2409.16197/) (2024)
- [Causal Bandits with General Causal Models and Interventions](https://mlsanity.com/paper/2403.00233/) (2024)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)
- [Experiment Planning with Function Approximation](https://mlsanity.com/paper/2401.05193/) (2024)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits](https://mlsanity.com/paper/2602.09456/) (2026)
- [Enhanced Bayesian Optimization via Preferential Modeling of Abstract Properties](https://mlsanity.com/paper/2402.17343/) (2024)
- [Universal Rates of Empirical Risk Minimization](https://mlsanity.com/paper/2412.02810/) (2024)
- [On the Hardness of Bandit Learning](https://mlsanity.com/paper/2506.14746/) (2025)
- [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [On the Limits of Tabular Hardness Metrics for Deep RL: A Study with the Pharos Benchmark](https://mlsanity.com/paper/2509.17092/) (2025)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)
- [Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measure](https://mlsanity.com/paper/2511.01847/) (2025)
- [On the Complexity of Preference-Based Bandits](https://mlsanity.com/paper/2609.39351/) (2026)

## Abstract (arXiv)

We provide new insights on eluder dimension, a complexity measure that has been extensively used to bound the regret of algorithms for online bandits and reinforcement learning with function approximation. First, we study the relationship between the eluder dimension for a function class and a generalized notion of rank, defined for any monotone "activation" σ : ℝ→ ℝ, which corresponds to the minimal dimension required to represent the class as a generalized linear model. It is known that when σ has derivatives bounded away from 0, σ-rank gives rise to an upper bound on eluder dimension for any function class; we show however that eluder dimension can be exponentially smaller than σ-rank. We also show that the condition on the derivative is necessary; namely, when σ is the mathsfrelu activation, the eluder dimension can be exponentially larger than σ-rank. For binary-valued function classes, we obtain a characterization of the eluder dimension in terms of star number and threshold dimension, quantities which are relevant in active learning and online learning respectively.