Eluder dimension: localise it!
Pith reviewed 2026-05-16 14:08 UTC · model grok-4.3
The pith
Localising the eluder dimension overcomes its size limitations for generalised linear models and produces the first genuine first-order regret bounds for finite-horizon reinforcement learning.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors establish a lower bound showing that the eluder dimension of generalised linear model classes is too large for standard analysis to produce first-order regret bounds. They introduce a localisation method for the eluder dimension that addresses this shortcoming, recovering and improving classic results for Bernoulli bandits and delivering the first genuine first-order regret bounds for finite-horizon reinforcement learning tasks with bounded cumulative returns.
What carries the argument
The localisation construction for the eluder dimension, which restricts attention to local subsets of the function class to obtain tighter bounds on the relevant complexity measure.
If this is right
- Standard global eluder dimension analysis cannot achieve first-order regret bounds for generalised linear model classes.
- The localisation method recovers and improves upon classic regret bounds for Bernoulli bandits.
- Genuine first-order regret bounds become available for finite-horizon reinforcement learning with bounded cumulative returns.
- Regret analysis can now exploit local structure in function classes where the global eluder dimension is large.
Where Pith is reading between the lines
- The same localisation idea could tighten other global complexity measures such as covering numbers in online learning settings.
- Empirical verification on concrete GLM instances like logistic bandits would confirm whether the improved bounds translate to practical gains.
- Extending the approach to infinite-horizon or average-reward settings would require additional control on long-run behavior.
Load-bearing premise
The localisation construction remains valid for the function classes and noise models considered, and the bounded cumulative return assumption is sufficient to control the relevant quantities.
What would settle it
A concrete finite-horizon RL instance with bounded cumulative returns where the localised eluder dimension still produces regret that grows faster than first-order would falsify the central claim.
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves a lower bound on the eluder dimension of generalized linear model classes that rules out first-order regret bounds under standard eluder-dimension analysis. It then introduces a localization construction for the eluder dimension, shows that the construction recovers and strengthens known bounds for Bernoulli bandits, and applies it to obtain the first genuine first-order regret bounds for finite-horizon RL under bounded cumulative returns.
Significance. If the localization step is shown to be valid for the relevant function classes and noise models, the result would be a meaningful technical advance: it supplies a concrete way to circumvent the lower bound while preserving the dimension-based proof template, and it yields the first horizon-independent first-order bounds for finite-horizon RL with bounded returns. The Bernoulli-bandit recovery also provides a useful sanity check.
major comments (3)
- [§3] §3 (Lower bound): the claimed lower bound on eluder dimension for GLM classes is stated without an explicit statement of the function class, link function, and noise model under which it holds; the proof sketch must be expanded to confirm that the construction does not inadvertently rely on horizon-dependent quantities that the localization is later supposed to remove.
- [§4] §4 (Localization construction): the definition of the localized eluder dimension must be shown to remain finite and independent of horizon when applied to value or Q-function classes in finite-horizon MDPs; the current argument appears to absorb the return bound only through a variance term, but it is unclear whether this absorption survives the covering-number or chaining steps used in the regret decomposition.
- [§5] §5 (RL application): the claim that the resulting bound is the 'first genuine first-order bound' requires an explicit comparison table against prior eluder-dimension analyses (e.g., those in Russo & Van Roy 2013 and subsequent works) to demonstrate that the horizon dependence has indeed been eliminated rather than hidden inside constants.
minor comments (3)
- [Definition 4.1] Notation for the localized dimension (Definition 4.1) uses the same symbol as the classical eluder dimension; a distinct symbol or subscript would reduce confusion.
- [§2] The abstract states that the method 'immediately recovers and improves on classic results for Bernoulli bandits'; the improvement factor should be stated quantitatively in the main text.
- [Figures 1-3] Several figure captions are missing axis labels or legend entries; this is a minor but recurring presentation issue.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for highlighting areas where additional clarity would strengthen the presentation. We address each major comment in turn below.
read point-by-point responses
-
Referee: [§3] §3 (Lower bound): the claimed lower bound on eluder dimension for GLM classes is stated without an explicit statement of the function class, link function, and noise model under which it holds; the proof sketch must be expanded to confirm that the construction does not inadvertently rely on horizon-dependent quantities that the localization is later supposed to remove.
Authors: We agree with this observation. In the revised version, we will explicitly define the GLM function class as linear predictors composed with a fixed link function (e.g., the logistic link for Bernoulli GLMs), specify the sub-Gaussian noise model with variance proxy σ², and expand the proof sketch into a complete proof in the appendix. We will also include a remark confirming that the lower bound construction is entirely horizon-independent, as it applies to the static function class without reference to any MDP or time horizon. revision: yes
-
Referee: [§4] §4 (Localization construction): the definition of the localized eluder dimension must be shown to remain finite and independent of horizon when applied to value or Q-function classes in finite-horizon MDPs; the current argument appears to absorb the return bound only through a variance term, but it is unclear whether this absorption survives the covering-number or chaining steps used in the regret decomposition.
Authors: We will revise §4 to include a formal proof that the localized eluder dimension for Q-function classes remains finite and independent of the horizon H under the bounded cumulative return assumption. The proof will show that the localization radius is chosen proportional to the return bound B, and that the covering numbers and chaining arguments in the regret analysis depend only on this localized radius, not on H directly. This ensures the absorption of the return bound propagates through the entire analysis. revision: yes
-
Referee: [§5] §5 (RL application): the claim that the resulting bound is the 'first genuine first-order bound' requires an explicit comparison table against prior eluder-dimension analyses (e.g., those in Russo & Van Roy 2013 and subsequent works) to demonstrate that the horizon dependence has indeed been eliminated rather than hidden inside constants.
Authors: We will add a comparison table in §5 (or as a new subsection) that contrasts our regret bound with those from Russo & Van Roy (2013), and related works such as Osband et al. (2016) and others using eluder dimension for RL. The table will highlight the dependence on horizon H, total return bound, and other parameters, clearly showing that our bound is independent of H while previous ones scale at least linearly with H or worse. revision: yes
Circularity Check
No circularity: new lower bound and localisation construction are independent derivations
full rationale
The paper derives a lower bound on eluder dimension for GLM classes directly from the definition of eluder dimension and GLM structure, then introduces localisation as a new construction on the dimension that is applied to recover bandit results and obtain RL bounds. No step reduces by construction to a fitted parameter, self-citation chain, or renamed input; the bounded-return assumption is used explicitly to control terms in the regret decomposition rather than being smuggled in. The central claim remains self-contained against the stated assumptions.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.