Abstract
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.
Introduction
Standard Q-learning theory typically rests on the "uniform coverage" assumption, requiring that every state-action pair in the environment be visited frequently enough to guarantee the convergence of the learned policy. However, in practical offline reinforcement learning (RL) scenarios, data is often pre-collected and may only partially cover the state-action space. For instance, an expert demonstration might only cover optimal trajectories, leaving vast regions of the state space unexplored. Applying vanilla Q-learning to such "partial" data often results in vacuous theoretical bounds, as the minimum visit probability ($\mu_{min}$) for unvisited states is zero.
Incorporating Pessimism via LCB Penalization
To overcome the coverage barrier, this paper introduces the "pessimism principle" into asynchronous Q-learning. The core idea is to penalize state-action pairs that have been infrequently visited in the offline data. This is achieved by subtracting a penalty term, derived from a Lower Confidence Bound (LCB), from the Q-value estimates during each update step.
By incorporating this pessimism, the algorithm avoids over-optimistically pursuing unexplored paths, effectively focusing its learning on the "near-expert" regions of the data. This approach allows the algorithm to learn a policy that is as good as the one demonstrated in the data, even without global coverage.
Achieving Near-Optimality with Variance Reduction
While simple LCB penalization addresses the coverage issue, it often suffers from a suboptimal dependency on the "effective horizon" (determined by the discount factor $\gamma$). To refine the sample efficiency, the authors propose a variance-reduced framework. This method utilizes an epoch-based structure where a "reference" value function is periodically updated to stabilize stochastic updates and reduce the variance of the gradient estimates.
As shown in Algorithm 2, the process involves alternating between estimating empirical transitions and performing variance-reduced Q-learning epochs. This combination of pessimism and variance reduction is particularly challenging to analyze in the context of Markovian data—where samples are collected along a single continuous trajectory—compared to the simpler i.i.d. sampling models used in previous literature.
Theoretical Results and Sample Complexity
The paper establishes rigorous sample complexity bounds for achieving $\epsilon$-accuracy. The standard LCB-penalized version requires approximately $\tilde{O}\left(\frac{SC^*}{(1-\gamma)^5 \epsilon^2}\right)$ samples. By integrating variance reduction, the complexity is improved to $\tilde{O}\left(\frac{SC^*}{(1-\gamma)^3 \epsilon^2}\right)$.
These results are significant for several reasons:
- Adaptivity: The sample complexity depends on a "concentrability coefficient" ($C^*$) rather than the total size of the action space ($A$). If the data is high-quality (near-expert), $C^*$ is much smaller than $A$.
- Optimal Horizon Dependency: The variance-reduced version achieves the "minimax optimal" scaling of $1/(1-\gamma)^3$, matching the best-known theoretical limits even for independent samples.
- Markovian Data Support: This work provides the first theoretical justification for using the pessimism principle with non-i.i.d. Markovian trajectories.
Conclusion and Future Directions
This research bridges the gap between the theoretical success of pessimism in batch RL and the practical, asynchronous nature of Q-learning. While the current analysis is restricted to the tabular setting, it provides a solid foundation for future work. Key areas for extension include applying these pessimistic guarantees to function approximation (such as Deep Q-Learning) and sharpening the dependency on the Markov chain's mixing time ($t_{mix}$).
Summary updated