mlsanityData to 7 Oct 2026

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

arXiv 1806.01492 ↗First posted 5 Jun 2018math.OCcited by 22

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 2; 2023: 4; 2024: 2; 2025: 2; 2026: 5.

22 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  3. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  4. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  5. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 35
  6. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  7. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  8. 2022When to Update Your Model: Constrained Model-based Reinforcement Learningcited by 14
  9. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  10. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  11. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  12. 2021Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settingscited by 5
10 more
  1. 2023Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learningcited by 4
  2. 2024A Black Swan Hypothesis: The Role of Human Irrationality in AI Safetycited by 3
  3. 2023Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processescited by 2
  4. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  5. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  6. 2025Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environmentscited by 1
  7. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  8. 2026Minimax PAC Bounds for Learning in Exogenous Contextual MDPscited by 1
  9. 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizabilitycited by 0
  10. 2026Theoretical Foundations of max@k Reinforcement Learningcited by 0