  Model-based Reinforcement Learning (RL) is a popular learning paradigm due to
its potential sample efficiency compared to model-free RL. However, existing
empirical model-based RL approaches lack the ability to explore. This work
studies a computationally and statistically efficient model-based algorithm for
both Kernelized Nonlinear Regulators (KNR) and linear Markov Decision Processes
(MDPs). For both models, our algorithm guarantees polynomial sample complexity
and only uses access to a planning oracle. Experimentally, we first demonstrate
the flexibility and efficacy of our algorithm on a set of exploration
challenging control tasks where existing empirical model-based RL approaches
completely fail. We then show that our approach retains excellent performance
even in common dense reward control benchmarks that do not require heavy
exploration. Finally, we demonstrate that our method can also perform
reward-free exploration efficiently. Our code can be found at
https://github.com/yudasong/PCMLP.
