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:
- Model-Based RL: Researchers like Chenlu Ye and Tong Zhang 0001 use the Total Variation (TV)-eluder dimension to bound how many times a transition model can be surprised by new environment dynamics, as seen in Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption.
- Human Feedback (RLHF): In Thompson Sampling in Online RLHF with General Function Approximation, Songtao Feng applies the Bellman eluder dimension to prove that learning from human preferences can be statistically efficient even with complex reward models.
- Multi-Agent Games: Baihe Huang and Zhaoran Wang extended these concepts to zero-sum games in Towards General Function Approximation in Zero-Sum Markov Games, showing that the interaction between two agents can also be bounded by the complexity of their shared hypothesis space.
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.