2024/10/10 by Matthew Zurek, Zurek, Matthew, Yudong Chen +1 · 3 citations
Decision Sciences · #Auction Theory and Applications #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2410.07616
openalex publication_date 2024/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the sample complexity of the plug-in approach for learning ε-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 \widetildeO(SA (D)/(ε2)) and \widetildeO(SA \fracτunifε2), respectively, without knowledge of the diameter D or uniform mixing time τ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.