# Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity

arXiv: https://arxiv.org/abs/2002.07125 · HTML: https://mlsanity.com/paper/2002.07125/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

## Built on by (most cited first, 19 of 19)

- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Going Beyond Linear RL: Sample Efficient Neural Function Approximation](https://mlsanity.com/paper/2107.06466/) (2021)
- [A Short Note on the Relationship of Information Gain and Eluder Dimension](https://mlsanity.com/paper/2107.02377/) (2021)
- [A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation](https://mlsanity.com/paper/2207.08342/) (2022)
- [Gap-Dependent Bounds for Two-Player Markov Games](https://mlsanity.com/paper/2107.00685/) (2021)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)
- [Provably Efficient Reinforcement Learning via Surprise Bound](https://mlsanity.com/paper/2302.11634/) (2023)
- [Exponential Hardness of Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2302.12940/) (2023)
- [Computational-Statistical Gaps in Reinforcement Learning](https://mlsanity.com/paper/2202.05444/) (2022)
- [Computational Hardness of Reinforcement Learning with Partial qπ-Realizability](https://mlsanity.com/paper/2510.21888/) (2025)
- [Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamics](https://mlsanity.com/paper/2603.00716/) (2026)
- [End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions](https://mlsanity.com/paper/2603.23461/) (2026)

## Abstract (arXiv)

The current paper studies the problem of agnostic Q-learning with function approximation in deterministic systems where the optimal Q-function is approximable by a function in the class F with approximation error δ ≥ 0. We propose a novel recursion-based algorithm and show that if δ = Oleft(ρ/√dimEright), then one can find the optimal policy using Oleft(dimEright) trajectories, where ρ is the gap between the optimal Q-value of the best actions and that of the second-best actions and dimE is the Eluder dimension of F. Our result has two implications: 1) In conjunction with the lower bound in [Du et al., ICLR 2020], our upper bound suggests that the condition δ = widetildeThetaleft(ρ/√dimEright) is necessary and sufficient for algorithms with polynomial sample complexity. 2) In conjunction with the lower bound in [Wen and Van Roy, NIPS 2013], our upper bound suggests that the sample complexity widetildeThetaleft(dimEright) is tight even in the agnostic setting. Therefore, we settle the open problem on agnostic Q-learning proposed in [Wen and Van Roy, NIPS 2013]. We further extend our algorithm to the stochastic reward setting and obtain similar results.