Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity
<|reference_start|>Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity: We study the problem of estimating the optimal Q-function of $\gamma$-discounted Markov decision processes (MDPs) under the synchronous setting, where independent samples for all state-action pairs are drawn from a generative model at each iteration. We introduce and analyze a novel model-free algorithm called Variance-Reduced Cascade Q-learning (VRCQ). VRCQ comprises two key building blocks: (i) the established direct variance reduction technique and (ii) our proposed variance reduction scheme, Cascade Q-learning. By leveraging these techniques, VRCQ provides superior guarantees in the $\ell_\infty$-norm compared with the existing model-free stochastic approximation-type algorithms. Specifically, we demonstrate that VRCQ is minimax optimal. Additionally, when the action set is a singleton (so that the Q-learning problem reduces to policy evaluation), it achieves non-asymptotic instance optimality while requiring the minimum number of samples theoretically possible. Our theoretical results and their practical implications are supported by numerical experiments.<|reference_end|>
@article{boveiri2024variance-reduced,
    title={Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity},
    author={Mohammad Boveiri and Peyman Mohajerin Esfahani},
    journal={arXiv preprint arXiv:2408.06544},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.06544},
    primaryClass={stat.ML cs.LG cs.SY eess.SY math.OC}
}