mlsanityData to 14 Oct 2026

Eluder dimension: localise it!

arXiv 2601.09825 ↗First posted 14 Jan 2026cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

We establish a lower bound on the eluder dimension of generalised linear model classes, showing that standard eluder dimension-based analysis cannot lead to first-order regret bounds. To address this, we introduce a localisation method for the eluder dimension; our analysis immediately recovers and improves on classic results for Bernoulli bandits, and allows for the first genuine first-order bounds for finite-horizon reinforcement learning tasks with bounded cumulative returns.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 32 of its 45 references that are in the map. First posted on arXiv 14 Jan 2026.

Builds on

32 of 45 references.

References · 32

  1. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  4. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  5. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  6. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  7. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  8. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  9. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 57
  10. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  11. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  12. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
20 more
  1. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  2. 2017Generalized Self-Concordant Functions: A Recipe for Newton-Type Methodscited by 33
  3. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  4. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
  5. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 29
  6. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  7. 2015First-order regret bounds for combinatorial semi-banditscited by 26
  8. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  9. 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
  10. 2023Exploration via linearly perturbed loss minimisationcited by 13
  11. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  12. 2023Likelihood Ratio Confidence Sets for Sequential Decision Makingcited by 10
  13. 2023Time-Uniform Self-Normalized Concentration for Vector-Valued Processescited by 9
  14. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learningcited by 8
  15. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  16. 2024Almost Free: Self-concordance in Natural Exponential Families and an Application to Banditscited by 8
  17. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  18. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  19. 2024Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learningcited by 3
  20. 2025Rectifying Regression in Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  2. 2026Understanding Off- vs On-Policy Distillation: A Tale of Distinct Training Objectivescited by 0
  3. 2026On the Complexity of Preference-Based Banditscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Horizon-Free Regret for Linear Markov Decision Processes
  2. 2025Regret Bounds for Robust Online Decision Making
  3. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
  4. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds
  5. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning
  6. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  7. 2026Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
  8. 2026Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory