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

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 $\mathcal{F}$ with approximation error $\delta \ge 0$. We propose a novel recursion-based algorithm and show that if $\delta =O\left(\rho /\sqrt{{\dim }_E}\right)$, then one can find the optimal policy using $O\left({\dim }_E\right)$ trajectories, where $\rho$ 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 $\mathcal{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 $\delta =\tilde{\Theta }\left(\rho /\sqrt{{\dim }_E}\right)$ 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 $\tilde{\Theta }\left({\dim }_E\right)$ 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.

References in corpus (11)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Variance Reduction Methods for Sublinear Reinforcement Learning
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits

Cited by in corpus (20)

• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• $Q$-learning with Logarithmic Regret
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Minimax Sample Complexity for Turn-based Stochastic Game
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• A Short Note on the Relationship of Information Gain and Eluder Dimension
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Gap-Dependent Bounds for Two-Player Markov Games