# Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2018.

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

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [When to Update Your Model: Constrained Model-based Reinforcement Learning](https://mlsanity.com/paper/2210.08349/) (2022)
- [Going Beyond Linear RL: Sample Efficient Neural Function Approximation](https://mlsanity.com/paper/2107.06466/) (2021)
- [Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time](https://mlsanity.com/paper/2305.15546/) (2023)
- [Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale](https://mlsanity.com/paper/2403.00222/) (2024)
- [Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings](https://mlsanity.com/paper/2111.00185/) (2021)
- [Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2305.04819/) (2023)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [A Black Swan Hypothesis: The Role of Human Irrationality in AI Safety](https://mlsanity.com/paper/2407.18422/) (2024)
- [Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes](https://mlsanity.com/paper/2304.00232/) (2023)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environments](https://mlsanity.com/paper/2507.18606/) (2025)
- [Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.16196/) (2026)
- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Computational Hardness of Reinforcement Learning with Partial qπ-Realizability](https://mlsanity.com/paper/2510.21888/) (2025)
- [Theoretical Foundations of max@k Reinforcement Learning](https://mlsanity.com/paper/2607.17823/) (2026)

## Abstract (arXiv)

In this paper we consider the problem of computing an ε-optimal policy of a discounted Markov Decision Process (DMDP) provided we can only access its transition function through a generative sampling model that given any state-action pair samples from the transition function in O(1) time. Given such a DMDP with states S, actions A, discount factor γ∈(0,1), and rewards in range [0, 1] we provide an algorithm which computes an ε-optimal policy with probability 1 - δ where both the time spent and number of sample taken are upper bounded by [ Oleft[frac|S||A|(1-γ)3 ε2 log left(frac|S||A|(1-γ)δ ε right) logleft(frac1(1-γ)εright)right] ~. ] For fixed values of ε, this improves upon the previous best known bounds by a factor of (1 - γ)-1 and matches the sample complexity lower bounds proved in Azar et al. (2013) up to logarithmic factors. We also extend our method to computing ε-optimal policies for finite-horizon MDP with a generative model and provide a nearly matching sample complexity lower bound.