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

arXiv: https://arxiv.org/abs/2410.07616 · HTML: https://mlsanity.com/paper/2410.07616/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 3 references that are in the map.
- First posted on arXiv 10 Oct 2024.

## Builds on (most cited first, 2 of 2)

- [Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs](https://mlsanity.com/paper/2403.11477/) (2024)
- [Span-Based Optimal Sample Complexity for Average Reward MDPs](https://mlsanity.com/paper/2311.13469/) (2023)

## Built on by (most cited first, 9 of 9)

- [Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL](https://mlsanity.com/paper/2502.11238/) (2025)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Faster Fixed-Point Methods for Multichain MDPs](https://mlsanity.com/paper/2506.20910/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs](https://mlsanity.com/paper/2606.14095/) (2026)
- [Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach](https://mlsanity.com/paper/2610.10326/) (2026)
- [Average-Reward Policy Identification from a Single Continuing Trajectory](https://mlsanity.com/paper/2610.20486/) (2026)

## Abstract (arXiv)

We study the sample complexity of the plug-in approach for learning varepsilon-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 widetildeOleft(SA fracDvarepsilon2right) and widetildeOleft(SA fracτunifvarepsilon2right), 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.