Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles

Abstract

Reinforcement learning (RL) methods have been shown to be capable of learning intelligent behavior in rich domains. However, this has largely been done in simulated domains without adequate focus on the process of building the simulator. In this paper, we consider a setting where we have access to an ensemble of pre-trained and possibly inaccurate simulators (models). We approximate the real environment using a state-dependent linear combination of the ensemble, where the coefficients are determined by the given state features and some unknown parameters. Our proposed algorithm provably learns a near-optimal policy with a sample complexity polynomial in the number of unknown parameters, and incurs no dependence on the size of the state (or action) space. As an extension, we also consider the more challenging problem of model selection, where the state features are unknown and can be chosen from a large candidate set. We provide exponential lower bounds that illustrate the fundamental hardness of this problem, and develop a provably efficient algorithm under additional natural assumptions.

References in corpus (12)

• Continuous control with deep reinforcement learning
• Learning Dexterous In-Hand Manipulation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Transfer from Simulation to Real World through Learning Deep Inverse Dynamics Model
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Model selection for contextual bandits
• No-regret Exploration in Contextual Reinforcement Learning
• Online learning in MDPs with side information

Cited by in corpus (6)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Efficient Episodic Learning of Nonstationary and Unknown Zero-Sum Games Using Expert Game Ensembles