# Eluder dimension: localise it!

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

## 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 (most cited first, 30 of 32)

- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [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)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach](https://mlsanity.com/paper/2112.03432/) (2021)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning](https://mlsanity.com/paper/2305.15703/) (2023)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [First- and Second-Order Bounds for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2305.00832/) (2023)
- [Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits](https://mlsanity.com/paper/1802.03386/) (2018)
- [Exploration via linearly perturbed loss minimisation](https://mlsanity.com/paper/2311.07565/) (2023)
- [Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning](https://mlsanity.com/paper/2502.13900/) (2025)
- [Likelihood Ratio Confidence Sets for Sequential Decision Making](https://mlsanity.com/paper/2311.04402/) (2023)
- [Time-Uniform Self-Normalized Concentration for Vector-Valued Processes](https://mlsanity.com/paper/2310.09100/) (2023)
- [Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning](https://mlsanity.com/paper/2403.05385/) (2024)
- [The Central Role of the Loss Function in Reinforcement Learning](https://mlsanity.com/paper/2409.12799/) (2024)
- [Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits](https://mlsanity.com/paper/2410.01112/) (2024)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)

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

- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Understanding Off- vs On-Policy Distillation: A Tale of Distinct Training Objectives](https://mlsanity.com/paper/2609.38666/) (2026)
- [On the Complexity of Preference-Based Bandits](https://mlsanity.com/paper/2609.39351/) (2026)

## 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.