Is Q-Learning Provably Efficient? An Extended Analysis

Kushagra Rastogi, Jonathan Lee, Fabrice Harel-Canada, Aditya Joglekar

Abstract

This work extends the analysis of the theoretical results presented within the paper Is Q-Learning Provably Efficient? by Jin et al. We include a survey of related research to contextualize the need for strengthening the theoretical guarantees related to perhaps the most important threads of model-free reinforcement learning. We also expound upon the reasoning used in the proofs to highlight the critical steps leading to the main result showing that Q-learning with UCB exploration achieves a sample efficiency that matches the optimal regret that can be achieved by any model-based approach.
BibTeX
@misc{rastogi2020is,
  author = {Kushagra Rastogi and Jonathan Lee and Fabrice Harel-Canada and Aditya Joglekar},
  title = {{Is Q-Learning Provably Efficient? An Extended Analysis}},
  year = {2020},
  eprint = {2009.10396},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.10396},
}

Loading related content...

Figure