Fetching the paper…
Reading the bibliography…
In this paper we provide faster algorithms for approximately solving discounted Markov Decision Processes in multiple parameter regimes.
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.
Probability inequalities for sums of bounded random variables
Wassily Hoeffding · 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.
Dynamic programming and optimal control
Dimitri P Bertsekas · 1995
Earlier work this paper cites.
Neuro-dynamic programming: an overview
Dimitri P Bertsekas and John N Tsitsiklis · 1995
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.
On the complexity of policy iteration
Yishay Mansour and Satinder Singh · 1999
Earlier work this paper cites.
A sparse sampling algorithm for near-optimal planning in large markov decision processes
Michael Kearns, Yishay Mansour, and Andrew Y Ng · 2002
Cited alongside, same era.
A new complexity result on solving the markov decision problem
Yinyu Ye · 2005
Cited alongside, same era.
Pac model-free reinforcement learning
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman · 2006
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.
On the sample complexity of reinforcement learning with a generative model
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Later among the works it cites.
Improved and generalized upper bounds on the complexity of policy iteration
Bruno Scherrer · 2013
Later among the works it cites.
The value iteration algorithm is not strongly polynomial for discounted dynamic programming
Eugene A Feinberg and Jefferson Huang · 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.
Markov decision processes: discrete stochastic dynamic programming
Martin L Puterman · 2014
Later among the works it cites.
Efficient inverse maintenance and faster algorithms for linear programming
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Mohammad Gheshlaghi Azar, Rémi Munos, and Bert Kappen · 2012
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
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.
Yin Tat Lee and Aaron Sidford · 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
George Dantzig · 2016
Later among the works it cites.
Lower bound on the computational complexity of discounted markov decision problems
Yichen Chen and Mengdi Wang · 2017
Closest in time.
Mengdi Wang · 2017
Closest in time.