Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?

Abstract

It is believed that a model-based approach for reinforcement learning (RL) is the key to reduce sample complexity. However, the understanding of the sample optimality of model-based RL is still largely missing, even for the linear case. This work considers sample complexity of finding an $\epsilon$-optimal policy in a Markov decision process (MDP) that admits a linear additive feature representation, given only access to a generative model. We solve this problem via a plug-in solver approach, which builds an empirical model and plans in this empirical model via an arbitrary plug-in solver. We prove that under the anchor-state assumption, which implies implicit non-negativity in the feature space, the minimax sample complexity of finding an $\epsilon$-optimal policy in a $\gamma$-discounted MDP is $O(K/(1-\gamma {)}^3{\epsilon }^2)$, which only depends on the dimensionality $K$ of the feature space and has no dependence on the state or action space. We further extend our results to a relaxed setting where anchor-states may not exist and show that a plug-in approach can be sample efficient as well, providing a flexible approach to design model-based algorithms for RL.

arXiv comment30 pages, to appear in NeurIPS2020

References in corpus (12)

• Playing Atari with Deep Reinforcement Learning
• StarCraft II: A New Challenge for Reinforcement Learning
• Model-Based Reinforcement Learning for Atari
• Benchmarking Model-Based Reinforcement Learning
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Model-based Reinforcement Learning and the Eluder Dimension
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Policy Error Bounds for Model-Based Reinforcement Learning with Factored Linear Models

Cited by in corpus (6)

• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Nearly Horizon-Free Offline Reinforcement Learning
• Minimax Sample Complexity for Turn-based Stochastic Game
• On the Power of Multitask Representation Learning in Linear MDP
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation