Asynchronous Q-learning from a single trajectory achieves near-optimal sample complexity with explicit dependence on environment structure (hitting times and state-action frequencies), and a data-driven step-size selection rule makes the algorithm practical without prior knowledge.
This paper analyzes how quickly asynchronous Q-learning converges when learning from a single trajectory of a Markov decision process. The authors prove that with a constant step size, the algorithm reaches a target accuracy using a sample complexity that depends on the horizon, minimum state-action probability, and hitting times of the environment.