Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error

Ally Yalei Du, Lin F. Yang, Ruosong Wang

Introduction

In Reinforcement Learning (RL), practitioners often rely on linear function approximation to estimate the optimal $Q$-function ($Q^*$). However, real-world models are frequently misspecified, meaning the true $Q^*$ lies at a distance $\epsilon$ from the best possible linear fit. In such scenarios, finding an $O(\epsilon)$-optimal policy can require a number of samples that grows exponentially with the feature dimension $d$.

This research explores whether a sparsity assumption—the idea that only a small subset $k$ of the $d$ features are actually relevant—can mitigate this exponential barrier. The authors prove that sparsity indeed enables polynomial sample complexity and establish a tight error bound of $O(H\epsilon)$.

The "Factor of 2" Barrier and Bellman Rank

A key theoretical contribution of this work is the identification of the "Factor of 2" barrier. In misspecified settings, it is information-theoretically impossible for a bandit algorithm to estimate the rewards of all arms within an error of $2\epsilon$ without an exponential number of samples. This explains why standard RL methods, which rely on global Bellman backups, fail when models are even slightly off. Furthermore, the authors demonstrate that existing metrics like "Bellman Rank" are insufficient for this problem, as even simple sparse linear MDPs can exhibit high Bellman rank, leading to suboptimal guarantees.

The Elimination Algorithm

To overcome these challenges, the authors propose an Elimination Algorithm for Finding the Optimal Hypotheses. Unlike traditional level-by-level approaches that propagate errors and lead to exponential growth, this algorithm manages each level $h$ of the horizon independently.

The algorithm functions through three primary mechanisms:

  • Independent Level Management: Candidate parameters are maintained for each level $h$ separately.
  • Optimistic Value Function Elimination: The algorithm selects parameters that maximize the initial value, collects data using the resulting policy, and evaluates the Bellman Error to ensure consistency between levels $h$ and $h+1$.
  • Sparsity-Aware Pruning: By leveraging the $k$-sparse assumption, the algorithm maintains a manageable "version space" of possible functions, permanently eliminating any parameters that result in high empirical Bellman error.

Hard Instances and Lower Bounds

To prove the tightness of their bounds, the authors construct "Hard Instances" based on binary trees. These mathematical worst-case scenarios demonstrate that without specific structural assumptions, any algorithm would fail to find a near-optimal policy.

Figure 1: A binary tree construction used to establish lower bounds, showing state transitions and reward structures at different levels of the horizon.

The construction is further refined into a hierarchical tree structure to demonstrate how errors compound over longer horizons $H$. This recursive design is crucial for proving the $\Omega(H\epsilon)$ lower bound.

Figure 2: The hierarchical tree structure used to prove that the $O(H\epsilon)$ error bound is information-theoretically tight.

Key Results

The paper establishes two primary theoretical bounds:

  • Upper Bound: The proposed algorithm achieves a suboptimality of approximately $O(H\epsilon)$ with a sample complexity of $O(d^k \cdot \text{poly}(H, 1/\epsilon))$. For a fixed sparsity $k$, this complexity is polynomial in $d$.
  • Lower Bound: A matching lower bound of $\Omega(H\epsilon)$ is provided, confirming that $O(H\epsilon)$ is the fundamental limit for suboptimality in this setting.

Conclusion

This work provides a definitive answer to the limits of sparse linear function approximation in misspecified RL. While the $O(d^k)$ dependence suggests that the approach remains computationally expensive as sparsity decreases, it offers a theoretically sound path for high-dimensional RL where a few features dominate. Future work may explore tighter dependencies on the horizon $H$ under more restrictive structural assumptions.

Summary updated

BibTeX
@inproceedings{du2025misspecified,
  author = {Ally Yalei Du and Lin F. Yang and Ruosong Wang},
  title = {{Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=nIEjY4a2Lf},
}
Figure