Fetching the paper…
Reading the bibliography…
In this paper we consider the problem of computing an $\epsilon$-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.
Dynamic Programming
Richard Bellman · 1957
Earlier work this paper cites.
Les problemes de decisions sequentielles
Guy De Ghellinck · 1960
Earlier work this paper cites.
Dynamic programming and Markov processes
Ronald A. Howard · 1960
Earlier work this paper cites.
A probabilistic production and inventory problem
F d’Epenoux · 1963
Earlier work this paper cites.
Solving h-horizon, stationary markov decision problems in time proportional to log (h)
Paul Tseng · 1990
Earlier work this paper cites.
On the complexity of solving Markov decision problems
Michael L Littman, Thomas L Dean, and Leslie Pack Kaelbling · 1995
Earlier work this paper cites.
Finite-sample convergence rates for q-learning and indirect algorithms
Michael J Kearns and Satinder P Singh · 1999
Earlier work this paper cites.
Variable resolution discretization for high-accuracy solutions of optimal control problems
Remi Munos and Andrew W Moore · 1999
Earlier work this paper cites.
On the complexity of policy iteration
Yishay Mansour and Satinder Singh · 1999
Earlier work this paper cites.
On the sample complexity of reinforcement learning
Sham M Kakade · 2003
Cited alongside, same era.
A new complexity result on solving the Markov decision problem
Yinyu Ye · 2005
Cited alongside, same era.
Reinforcement learning in finite mdps: Pac analysis
Alexander L Strehl, Lihong Li, and Michael L Littman · 2009
Cited alongside, same era.
Yinyu Ye · 2011
Cited alongside, same era.
Pac bounds for discounted mdps
Tor Lattimore and Marcus Hutter · 2012
Cited alongside, same era.
Minimax pac bounds on the sample complexity of reinforcement learning with a generative model
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen · 2013
Improved and generalized upper bounds on the complexity of policy iteration
Bruno Scherrer · 2013
Later among the works it cites.
Dileep Kalathil, Vivek S Borkar, and Rahul Jain · 2014
Later among the works it cites.
Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Later among the works it cites.
Sample complexity of episodic fixed-horizon reinforcement learning
Christoph Dann and Emma Brunskill · 2015
Later among the works it cites.
Efficient inverse maintenance and faster algorithms for linear programming
Yin Tat Lee and Aaron Sidford · 2015
Later among the works it cites.
Linear Programming and Extensions
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Abstract dynamic programming
Dimitri P Bertsekas · 2013
Cited alongside, same era.
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick · 2013
Cited alongside, same era.
George Dantzig · 2016
Later among the works it cites.
Mengdi Wang · 2017
Later among the works it cites.
Variance reduced value iteration and faster algorithms for solving markov decision processes
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye · 2018
Closest in time.