Agnostic -learning with Function Approximation in Deterministic Systems: Near-Optimal Bounds on Approximation Error and Sample Complexity
Simon S. Du, Jason D. Lee, Gaurav Mahajan, Ruosong Wang
Abstract
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 δ = O ρ/ √ dim E , then one can find the optimal policy using O(dim E ) trajectories, where ρ is the gap between the optimal Q-value of the best actions and that of the second-best actions and dim E is the Eluder dimension of F. Our result has two implications: 1. In conjunction with the lower bound in [Du et al., 2020] , our upper bound suggests that the condition δ = Θ ρ/ √ dim E is necessary and sufficient for algorithms with polynomial sample complexity. 2. In conjunction with the obvious lower bound in the tabular case, our upper bound suggests that the sample complexity Θ (dim E ) is tight in the agnostic setting. Therefore, we help address the open problem on agnostic Q-learning proposed in [Wen and Van Roy, 2013] . We further extend our algorithm to the stochastic reward setting and obtain similar results.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
11 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Optimism in Reinforcement Learning with Generalized Linear Function Approximation cites Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
- An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap cites Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap cites Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
- An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap cites Learning with Good Feature Representations in Bandits and in RL with a Generative Model
- Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? cites Learning with Good Feature Representations in Bandits and in RL with a Generative Model
- Learning with Good Feature Representations in Bandits and in RL with a Generative Model cites Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
- Breaking the Deadly Triad with a Target Network cites Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs cites Optimism in Reinforcement Learning with Generalized Linear Function Approximation
- When Is Generalizable Reinforcement Learning Tractable? cites Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
- When Is Generalizable Reinforcement Learning Tractable? cites Learning with Good Feature Representations in Bandits and in RL with a Generative Model
Cited by top-tier papers11
- Breaking the Deadly Triad with a Target NetworkShangtong Zhang, Hengshuai Yao, Shimon WhitesonICML 2021 · 61 citations
- On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy ExplorationShuai Zhang, Hongkang Li, Meng Wang, Miao Liu et al.NeurIPS 2023 · 57 citations
- An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality GapYuanhao Wang, Ruosong Wang, Sham M. KakadeNeurIPS 2021 · 48 citations
- Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPsYeoneung Kim, Insoon Yang, Kwang-Sung JunNeurIPS 2022 · 46 citations
- When Is Generalizable Reinforcement Learning Tractable?Dhruv Malik, Yuanzhi Li, Pradeep RavikumarNeurIPS 2021 · 32 citations
Builds on3
- Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?Simon S. Du, Sham M. Kakade, Ruosong Wang, Lin F. YangICLR 2020 · 213 citations
- Learning with Good Feature Representations in Bandits and in RL with a Generative ModelTor Lattimore, Csaba Szepesvári, Gellért WeiszICML 2020 · 181 citations
- Optimism in Reinforcement Learning with Generalized Linear Function ApproximationYining Wang, Ruosong Wang, Simon Shaolei Du, Akshay KrishnamurthyICLR 2021 · 54 citations
Related papers
- Going Beyond Linear RL: Sample Efficient Neural Function ApproximationBaihe Huang, Kaixuan Huang, Sham M. Kakade, Jason D. Lee et al.NeurIPS 2021 · 10 citations
- Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder DimensionRuosong Wang, Ruslan Salakhutdinov, Lin F. YangNeurIPS 2020 · 168 citations
- Rethinking the Hardness of PbRL: A Provable General Regret BoundChenjie Mao, Yi Fan, Ning Zhang, Chongjie ZhangICML 2026
- Agnostic Reinforcement Learning with Low-Rank MDPs and Rich ObservationsAyush Sekhari, Christoph Dann, Mehryar Mohri, Yishay Mansour et al.NeurIPS 2021 · 15 citations
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function ApproximationHeyang Zhao, Jiafan He, Quanquan GuNeurIPS 2024 · 16 citations
