Research map / Bandits and online learning / RL theory and MDPs
Eluder dimension: localise it!
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows global eluder dimension for GLM classes forces curvature dependence that defeats first-order regret, introduces a localised l1-eluder dimension, and uses it to get first-order bounds for bandits (l-UCB) and finite-horizon RL (l-GOLF).
Problem
Standard eluder-dimension analyses of bandits and RL with GLM function approximation introduce a curvature parameter kappa into the leading regret term, cancelling small-cost (first-order) gains; first-order regret bounds are needed for bounded costs.
Approach
Localise the l1-eluder dimension to a small-excess-loss neighbourhood (sigma-localised) so that curvature terms move into lower-order terms; combine with a version-space optimistic algorithm (l-UCB) using a generic loss with Bernstein variance and triangle conditions, extended to RL as l-GOLF.
Key results
- Proves a lower bound showing the global l1-eluder dimension of GLM classes grows like exp(min{S, d}) for logistic links, so global-eluder analyses cannot give first-order bounds.
- Proposition gives logistic-bandit regret R_n <= C sqrt(n eta(a*) d beta_n)(1+log(1+Sn)) + lower-order terms, with localised eluder dimension bounded by C d log(1+S^2 L/epsilon).
- Gives the first kappa-free first-order regret bound for finite-horizon episodic RL with bounded costs (l-GOLF).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| localise the eluder dimension to a small-excess-loss neighbourhood | eluder-dimension-based regret analysis for generalised linear bandits · Generalised linear bandits | first-order regret bound | Helped |
| use global rather than localised eluder dimension | eluder-dimension-based analysis for generalised linear models · Generalised linear models | eluder dimension dependence on curvature | Hurt |
| use squared loss instead of a loss satisfying the triangle condition | small-cost regret analysis · Stochastic bandits | small-cost regret bound | Hurt |
| Bernoullise bounded observations before feeding them to the algorithm | first-order logistic-bandit algorithm · Bounded-reward bandits | second-order adaptivity: Ω(1/√n) | Hurt |
Surprising findings
- Global eluder dimension of GLM classes can be exponential in the parameter norm S for the sigmoid link, nullifying small-cost gains.
- Bernoullisation of bounded costs destroys second-order adaptivity of the algorithm.
Limitations
- Triangle condition is one-sided, so the results give small-cost bounds only, not simultaneous small-cost and small-reward bounds (e.g. not v(a*) for logistic bandits).
- Optimisation over the confidence set is difficult in general; convex relaxation only described for self-concordant models.
- Analysis-only localisation relies on a good event and does not give an algorithmic warm-up.
Experimental setup
Metrics: regret eluder dimension
Baselines: GLM-UCB GOLF logistic bandit algorithm of Abeille et al. adversarial small-cost algorithms
Builds on: eluder dimension GOLF GLM bandits optimism in the face of uncertainty
Closest papers by meaning
- A General Framework for Sequential Decision-Making under Adaptivity Constraints (ICML 2024 · similarity 0.87)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.86)
- Eluder-based Regret for Stochastic Contextual MDPs (ICML 2024 · similarity 0.86)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.86)
- On the necessity of adaptive regularisation: Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls (NeurIPS 2025 · similarity 0.84)
- Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.