Is Q-learning Provably Efficient?

Understand

Model-free reinforcement learning (RL) algorithms, such as Q-learning, directly parameterize and update value functions or policies without explicitly modeling the environment.

• They are typically simpler, more flexible to use, and thus more prevalent in modern deep RL than model-based approaches.
• However, empirical work has suggested that model-free algorithms may require more samples to learn [Deisenroth and Rasmussen 2011, Schulman et al.
• 2015].