mlsanityData to 7 Oct 2026

Understanding the Eluder Dimension

arXiv 2104.06970 ↗First posted 14 Apr 2021cs.LG stat.MLcited by 19

Not on the map. Why?

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.

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

Builds on

17 of 59 references.

References · 17

  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  4. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  5. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  6. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  7. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  8. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  9. 2018Private PAC learning implies finite Littlestone dimensioncited by 73
  10. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  11. 2020An Equivalence Between Private Classification and Online Predictioncited by 63
  12. 2014Minimax Analysis of Active Learningcited by 61
5 more
  1. 2021Adversarial Laws of Large Numbers and Optimal Regret in Online Classificationcited by 39
  2. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  3. 2020Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexitycited by 25
  4. 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
  5. 2020On the Sample Complexity of Reinforcement Learning with Policy Space Generalizationcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 5; 2025: 6; 2026: 5.

19 papers.

Sort:

By area:

  1. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  2. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 13
  3. 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
  4. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  5. 2024Causal Bandits with General Causal Models and Interventionscited by 7
  6. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  7. 2024Experiment Planning with Function Approximationcited by 5
  8. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  9. 2024Enhanced Bayesian Optimization via Preferential Modeling of Abstract Propertiescited by 3
  10. 2024Universal Rates of Empirical Risk Minimizationcited by 3
  11. 2025On the Hardness of Bandit Learningcited by 2
  12. 2026Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Banditscited by 2
7 more
  1. 2025On the Limits of Tabular Hardness Metrics for Deep RL: A Study with the Pharos Benchmarkcited by 1
  2. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  3. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  4. 2026Sign-Rank, Index, and List Replicability: Connections and Separationscited by 1
  5. 2025Constrained Online Decision-Making: A Unified Frameworkcited by 0
  6. 2025Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measurecited by 0
  7. 2026On the Complexity of Preference-Based Banditscited by 0