Eluder Dimension for General Function Approximation in Reinforcement Learning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2114 papers142 conceptsfrozen 2026-10-04

In classical reinforcement learning (RL), we often prove that an algorithm works by counting. If an environment has a finite number of states and actions, we can guarantee that an agent will eventually explore everything. However, modern RL uses deep neural networks to handle near-infinite state spaces where "counting" is impossible. To provide the same theoretical guarantees for these complex models, researchers have moved away from counting states and toward measuring the complexity of the functions themselves.

The core breakthrough in this direction is the Eluder dimension, a metric that quantifies how many samples are needed to "pin down" a function within a broad, non-linear class.

The Challenge of General Function Approximation

When an agent uses a function approximator—like a neural network—to estimate the value of an action, it is making a bet that what it learned in one part of the state space applies to another. In simple linear models, this is easy to track: if you know the rewards for a set of linearly independent actions, you can calculate the rewards for any action in their span.

But neural networks are non-linear. Knowing the value of $f(x_1)$ and $f(x_2)$ might tell you absolutely nothing about $f(x_3)$, even if $x_3$ is "between" them. This creates a problem for exploration: how do we know when an agent has seen enough to be "optimistic" or "certain"?

As Daniel Russo and Daniel Russo 0001 identified in Eluder Dimension and the Sample Complexity of Optimistic Exploration, we need a way to measure the "effective dimensionality" of these non-linear spaces.

The Intuition of Elusion

The Eluder dimension measures the length of the longest possible sequence of "surprising" actions.

Imagine an adversary chooses a sequence of actions $a_1, a_2, \dots, a_n$. An action is "surprising" (or "eluding") if its reward cannot be accurately predicted even if we know the rewards of all previous actions in the sequence. In a simple 2D linear world, you can only be surprised twice; the third action's reward is mathematically constrained by the first two. In a complex non-linear world, you might be surprised many more times.

The Eluder dimension is the maximum number of times an agent can be significantly misled before the function class is "constrained" enough to predict future outcomes. As Ruosong Wang and Lin F. Yang demonstrate in Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension, if this dimension is small, the agent can achieve low regret because it cannot be "surprised" indefinitely.

From Bandits to the Bellman Equation

While the original Eluder dimension was designed for bandits (where you pull a lever and get a reward), RL is more complex because actions have long-term consequences. This led to the development of the Bellman Eluder (BE) dimension.

In RL, we don't just want to learn a function; we want to solve the Bellman equation. The BE dimension measures how many samples are needed to constrain the Bellman error—the difference between our current value estimate and the actual expected future rewards.

Christoph Dann and colleagues in Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation show that this metric allows us to provide sample complexity guarantees for general function approximators. It effectively replaces the "number of states" in classical proofs with the "complexity of the value function class."

A Unified Framework for Modern RL

This research direction has expanded to cover almost every frontier of modern decision-making:

Why It Works: The Information Gain Intuition

The reason Eluder-based methods work is that they formalize the relationship between exploration and information.

In algorithms like $\mathcal{F}$-LSVI-PHE, proposed by Haque Ishfaq in Randomized Exploration in Reinforcement Learning with General Value Function Approximation, the agent uses randomized perturbations to ensure it explores. The Eluder dimension provides the "budget" for this exploration. It guarantees that every time the agent makes a mistake (high regret), it gains a significant amount of information about the function class. Because the Eluder dimension is finite, the agent eventually runs out of ways to be significantly mistaken, forcing it to converge toward the optimal policy.

By shifting the focus from the size of the world to the complexity of the agent's internal model, this line of research provides the theoretical bridge between simple "toy" problems and the high-dimensional reality of deep reinforcement learning.

Papers in this version

Showing 60 of 114 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 91 papers
  2. Version 1 · 2026-10-04 · 114 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_eluder_dimension_077bd45b,
  title = {eluder dimension},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eluder-dimension/rdr_077bd45b507b401e8436d600080167a9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_eluder_dimension_for_general_function_ap_077bd45b_v1,
  title = {Eluder Dimension for General Function Approximation in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eluder-dimension-for-general-function-approximation-in-reinforcement-learning/rdr_077bd45b507b401e8436d600080167a9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}