The Efficacy of Pessimism in Asynchronous Q-Learning

Yuling Yan, Gen Li, Yuxin Chen, Jianqing Fan

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper is concerned with the asynchronous form of Q-learning, which applies a stochastic approximation scheme to Markovian data samples. Motivated by the recent advances in offline reinforcement learning, we develop an algorithmic framework that incorporates the principle of pessimism into asynchronous Q-learning, which penalizes infrequently-visited state-action pairs based on suitable lower confidence bounds (LCBs). This framework leads to, among other things, improved sample efficiency and enhanced adaptivity in the presence of near-expert data. Our approach permits the observed data in some important scenarios to cover only partial state-action space, which is in stark contrast to prior theory that requires uniform coverage of all state-action pairs. When coupled with the idea of variance reduction, asynchronous Q-learning with LCB penalization achieves near-optimal sample complexity, provided that the target accuracy level is small enough. In comparison, prior works were suboptimal in terms of the dependency on the effective horizon even when i.i.d. sampling is permitted. Our results deliver the first theoretical support for the use of pessimism principle in the presence of Markovian non-i.i.d. data.

Original languageEnglish (US)
Pages (from-to)7185-7219
Number of pages35
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 1 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Library and Information Sciences
  • Computer Science Applications


  • Asynchronous Q-learning
  • model-free algorithms
  • offline reinforcement learning
  • partial coverage
  • pessimism principle
  • variance reduction


Dive into the research topics of 'The Efficacy of Pessimism in Asynchronous Q-Learning'. Together they form a unique fingerprint.

Cite this