NeurIPS 2025spotlight0 citations
Eluder dimension: localise it!
Alireza Bakhtiari, Alex Ayoub, Samuel McLaughlin Robertson, David Janz, Csaba Szepesvari
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.
eluder dimensionbanditsreinforcement learning
BibTeX
@inproceedings{
bakhtiari2025eluder,
title={Eluder dimension: localise it!},
author={Alireza Bakhtiari and Alex Ayoub and Samuel McLaughlin Robertson and David Janz and Csaba Szepesvari},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=e8R0ytPhLv}
}