EUVIMEDEUVIMED entdecken
Crossref

Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis

Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, Yuejie Chi

Operations Research · 2024-01 · 72 (1) · 222-236

DOI: 10.1287/opre.2023.2450 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Operations Research, 2024-01. Verfasst von Gen Li und 4 weiteren Autor:innen. Die Arbeit wurde bisher 36-mal zitiert (Crossref) und nennt 43 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper investigates a model-free algorithm of broad interest in reinforcement learning, namely, Q-learning. Whereas substantial progress had been made toward understanding the sample efficiency of Q-learning in recent years, it remained largely unclear whether Q-learning is sample-optimal and how to sharpen the sample complexity analysis of Q-learning. In this paper, we settle these questions: (1) When there is only a single action, we show that Q-learning (or, equivalently, TD learning) is provably minimax optimal. (2) When there are at least two actions, our theory unveils the strict suboptimality of Q-learning and rigorizes the negative impact of overestimation in Q-learning. Our theory accommodates both the synchronous case (i.e., the case in which independent samples are drawn) and the asynchronous case (i.e., the case in which one only has access to a single Markovian trajectory).

Zitieren

APA

Li, G., Cai, C., Chen, Y., Wei, Y., & Chi, Y. (2024). Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis. Operations Research, 72(1), 222-236. https://doi.org/10.1287/opre.2023.2450

Vancouver

Li G, Cai C, Chen Y, Wei Y, Chi Y. Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis. Operations Research. 2024;72(1):222-236. doi:10.1287/opre.2023.2450

BibTeX
@article{Li2024,
  author = {Li, Gen and Cai, Changxiao and Chen, Yuxin and Wei, Yuting and Chi, Yuejie},
  title = {Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis},
  journal = {Operations Research},
  year = {2024},
  volume = {72},
  number = {1},
  pages = {222--236},
  doi = {10.1287/opre.2023.2450}
}
Kostenlos starten →