An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap

Abstract

A fundamental question in the theory of reinforcement learning is: suppose the optimal $Q$-function lies in the linear span of a given $d$ dimensional feature mapping, is sample-efficient reinforcement learning (RL) possible? The recent and remarkable result of Weisz et al. (2020) resolved this question in the negative, providing an exponential (in $d$) sample size lower bound, which holds even if the agent has access to a generative model of the environment. One may hope that this information theoretic barrier for RL can be circumvented by further supposing an even more favorable assumption: there exists a \emph{constant suboptimality gap} between the optimal $Q$-value of the best action and that of the second-best action (for all states). The hope is that having a large suboptimality gap would permit easier identification of optimal actions themselves, thus making the problem tractable; indeed, provided the agent has access to a generative model, sample-efficient RL is in fact possible with the addition of this more favorable assumption. This work focuses on this question in the standard online reinforcement learning setting, where our main result resolves this question in the negative: our hardness result shows that an exponential sample complexity lower bound still holds even if a constant suboptimality gap is assumed in addition to having a linearly realizable optimal $Q$-function. Perhaps surprisingly, this implies an exponential separation between the online RL setting and the generative model setting. Complementing our negative hardness result, we give two positive results showing that provably sample-efficient RL is possible either under an additional low-variance assumption or under a novel hypercontractivity assumption (both implicitly place stronger conditions on the underlying dynamics model).

References in corpus (21)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Better Agnostic Clustering Via Relaxed Tensor Norms
• Outlier-robust moment-estimation via sum-of-squares
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• $Q$-learning with Logarithmic Regret
• Efficient Planning in Large MDPs with Weak Linear Function Approximation

Cited by in corpus (5)

• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
• Efficient Local Planning with Linear Function Approximation
• TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation