Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach
We present BRIEE (Block-structured Representation learning with Interleaved Explore Exploit), an algorithm for efficient reinforcement learning in Markov Decision Processes with block-structured dynamics (i.e., Block MDPs), where rich observations are generated from a set of unknown latent states. BRIEE interleaves latent states discovery, exploration, and exploitation together, and can provably learn a near-optimal policy with sample complexity scaling polynomially in the number of latent states, actions, and the time horizon, with no dependence on the size of the potentially infinite observation space. Empirically, we show that BRIEE is more sample efficient than the state-of-art Block MDP algorithm HOMER and other empirical RL baselines on challenging rich-observation combination lock problems that require deep exploration.
Code (1)
Tasks
reinforcement-learningReinforcement Learning (RL)Representation LearningSimilar Papers 제목 키워드 기반
Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs
In reward-free reinforcement learning (RL), an agent explores the environment first without any reward information, in order to achieve certain learning goals afterwards for any given reward. In this paper we focus on re…
reinforcement-learningReinforcement Learning (RL)Representation LearningExploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Supervised learning is often computationally easy in practice. But to what extent does this mean that other modes of learning, such as reinforcement learning (RL), ought to be computationally easy by extension? In this w…
regressionReinforcement Learning (RL)Density-Based Bonuses on Learned Representations for Reward-Free Exploration in Deep Reinforcement Learning
In this paper, we study the problem of representation learning and exploration in reinforcement learning. We propose a framework to compute exploration bonuses based on density estimation, that can be used with any repre…
Deep Reinforcement LearningDensity Estimationreinforcement-learningReinforcement Learning (RL)+1Solving Finite-Horizon MDPs via Low-Rank Tensors
We study the problem of learning optimal policies in finite-horizon Markov Decision Processes (MDPs) using low-rank reinforcement learning (RL) methods. In finite-horizon MDPs, the policies, and therefore the value funct…
Reinforcement Learning (RL)Model-free Representation Learning and Exploration in Low-rank MDPs
The low rank MDP has emerged as an important model for studying representation learning and exploration in reinforcement learning. With a known representation, several model-free exploration strategies exist. In contrast…
Reinforcement Learning (RL)Representation Learning