The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis

Abstract

We study the sample complexity of the plug-in approach for learning $\epsilon$-optimal policies in average-reward Markov decision processes (MDPs) with a generative model. The plug-in approach constructs a model estimate then computes an average-reward optimal policy in the estimated model. Despite representing arguably the simplest algorithm for this problem, the plug-in approach has never been theoretically analyzed. Unlike the more well-studied discounted MDP reduction method, the plug-in approach requires no prior problem information or parameter tuning. Our results fill this gap and address the limitations of prior approaches, as we show that the plug-in approach is optimal in several well-studied settings without using prior knowledge. Specifically it achieves the optimal diameter- and mixing-based sample complexities of $\tilde{O}\left(SA\frac{D}{{\epsilon }^2}\right)$ and $\tilde{O}\left(SA\frac{\ddot{I}{„}_{\mathrm{unif}}}{{\epsilon }^2}\right)$, respectively, without knowledge of the diameter $D$ or uniform mixing time $\ddot{I}{„}_{\mathrm{unif}}$. We also obtain span-based bounds for the plug-in approach, and complement them with algorithm-specific lower bounds suggesting that they are unimprovable. Our results require novel techniques for analyzing long-horizon problems which may be broadly useful and which also improve results for the discounted plug-in approach, removing effective-horizon-related sample size restrictions and obtaining the first optimal complexity bounds for the full range of sample sizes without reward perturbation.

Accepted to 36th International Conference on Algorithmic Learning Theory (ALT 2025)