Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge

Abstract

The problem of sample complexity of online reinforcement learning is often studied in the literature without taking into account any partial knowledge about the system dynamics that could potentially accelerate the learning process. In this paper, we study the sample complexity of online Q-learning methods when some prior knowledge about the dynamics is available or can be learned efficiently. We focus on systems that evolve according to an additive disturbance model of the form $S_{h+1}=f(S_h,A_h)+W_h$, where $f$ represents the underlying system dynamics, and $W_h$ are unknown disturbances independent of states and actions. In the setting of finite episodic Markov decision processes with $S$ states, $A$ actions, and episode length $H$, we present an optimistic Q-learning algorithm that achieves $\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{T})$ regret under perfect knowledge of $f$, where $T$ is the total number of interactions with the system. This is in contrast to the typical $\tilde{\mathcal{O}}(\text{Poly}(H)\sqrt{SAT})$ regret for existing Q-learning methods. Further, if only a noisy estimate $\hat{f}$ of $f$ is available, our method can learn an approximately optimal policy in a number of samples that is independent of the cardinalities of state and action spaces. The sub-optimality gap depends on the approximation error $\hat{f}-f$, as well as the Lipschitz constant of the corresponding optimal value function. Our approach does not require modeling of the transition probabilities and enjoys the same memory complexity as model-free methods.

Published in the 38th Annual AAAI Conference on Artificial Intelligence

References in corpus (15)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• SOLAR: Deep Structured Representations for Model-Based Reinforcement Learning
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Understanding Domain Randomization for Sim-to-real Transfer
• Fast active learning for pure exploration in reinforcement learning
• Online and Offline Reinforcement Learning by Planning with a Learned Model
• Provably Efficient Q-Learning with Low Switching Cost
• Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator
• $Q$-learning with Logarithmic Regret
• Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
• How Does an Approximate Model Help in Reinforcement Learning?
• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost