Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle

Abstract

$Q$-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, approximating $Q$-functions with linear functions, it is still an open problem on how to design a provably efficient algorithm that learns a near-optimal policy. The key challenges are how to efficiently explore the state space and how to decide when to stop exploring in conjunction with the function approximation scheme. The current paper presents a provably efficient algorithm for $Q$-learning with linear function approximation. Under certain regularity assumptions, our algorithm, Difference Maximization $Q$-learning (DMQ), combined with linear function approximation, returns a near-optimal policy using a polynomial number of trajectories. Our algorithm introduces a new notion, the Distribution Shift Error Checking (DSEC) oracle. This oracle tests whether there exists a function in the function class that predicts well on a distribution ${\mathcal{D}}_1$, but predicts poorly on another distribution ${\mathcal{D}}_2$, where ${\mathcal{D}}_1$ and ${\mathcal{D}}_2$ are distributions over states induced by two different exploration policies. For the linear function class, this oracle is equivalent to solving a top eigenvalue problem. We believe our algorithmic insights, especially the DSEC oracle, are also useful in designing and analyzing reinforcement learning algorithms with general function approximation.

In NeurIPS 2019

Cited by in corpus (32)

• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Provably Efficient Exploration in Policy Optimization
• Finite-Time Analysis for Double Q-learning
• $Q$-learning with Logarithmic Regret
• Adaptive Discretization in Online Reinforcement Learning
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Robust Policy Gradient against Strong Data Corruption
• Adaptive Discretization for Model-Based Reinforcement Learning
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Breaking the Deadly Triad with a Target Network
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
• Provably Correct Optimization and Exploration with Non-linear Policies
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Efficient Local Planning with Linear Function Approximation
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Gap-Dependent Bounds for Two-Player Markov Games