Variance-reduced $Q$-learning is minimax optimal

Markov decision processes and reinforcement learning algorithms provide a flexible framework for decision-making in dynamic settings, and have been studied for decades (e.g., [23, 27, 8, 9, 29]). Given the explosion in the amount of available data and computing power, recent years have witnessed dramatic success of reinforcement learning (RL) techniques in various application domains (e.g., [30, 19, 26, 22, 27]). In broad terms, algorithms for reinforcement learning are often separated into model-based versus model-free approaches. Model-based approaches based on directly learning a model for the dynamics of the system, and then computing optimal policies from the learned model. In contrast, a model-free approach directly targets learning of the optimal value function or policy. Naturally, a model-free approach is more robust to model mismatch; however, model-based approaches can often be more sample efficient. Providing a firm theoretical foundation to the tradeoffs intrinsic to different classes of methods, as characterized by their access to the underlying Markov decision process, is a major open question in RL.