Eluder Dimension: Localise It!
Abstract
We establish a lower bound on the eluder dimension in 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.
Cite
Text
Bakhtiari et al. "Eluder Dimension: Localise It!." Advances in Neural Information Processing Systems, 2025.Markdown
[Bakhtiari et al. "Eluder Dimension: Localise It!." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/bakhtiari2025neurips-eluder/)BibTeX
@inproceedings{bakhtiari2025neurips-eluder,
title = {{Eluder Dimension: Localise It!}},
author = {Bakhtiari, Alireza and Ayoub, Alex and Robertson, Samuel McLaughlin and Janz, David and Szepesvari, Csaba},
booktitle = {Advances in Neural Information Processing Systems},
year = {2025},
url = {https://mlanthology.org/neurips/2025/bakhtiari2025neurips-eluder/}
}