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 c

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keyalharbi2023sample

Related papers

• Pessimistic Q-learning For Offline Reinforcement Learning: Towards Optimal Sample Complexity (2022)0.00
• Breaking The Sample Complexity Barrier To Regret-optimal Model-free Reinforcement Learning (2021)0.00
• Posterior Sampling-based Online Learning For Episodic Pomdps (2023)0.00
• Distributionally Robust Model-based Offline Reinforcement Learning With Near-optimal Sample Complexity (2022)0.00
• Is Q-learning Minimax Optimal? A Tight Sample Complexity Analysis (2021)0.00
• Sample Complexity Of Asynchronous Q-learning: Sharper Analysis And Variance Reduction (2020)11.19
• Q-learning With UCB Exploration Is Sample Efficient For Infinite-horizon MDP (2019)0.00
• Stochastic Primal-dual Methods And Sample Complexity Of Reinforcement Learning (2016)0.00