The Efficacy of Pessimism in Asynchronous Q-Learning
This provides theoretical support for using pessimism in offline reinforcement learning with non-i.i.d. data, addressing a key bottleneck for sample efficiency in near-expert scenarios.
The paper tackles the problem of asynchronous Q-learning with Markovian data by incorporating pessimism via lower confidence bounds, achieving near-optimal sample complexity and allowing partial coverage of state-action space, unlike prior methods that required uniform coverage.
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.