  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.
