Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running 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.

An efficient method for weighted sampling without replacement

Chak-Kuen Wong and Malcolm C. Easton · 1980

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.

The linear programming approach to approximate dynamic programming

Daniela Pucci de Farias and Benjamin Van Roy · 2003

Cited alongside, same era.

Stochastic Approximation and Recursive Algorithms and Applications

Harold J Kushner and George Yin · 2003

Cited alongside, same era.

An efficient stochastic approximation algorithm for stochastic saddle point problems

Arkadi Nemirovski and Reuven Y Rubinstein · 2005

Cited alongside, same era.

A new complexity result on solving the Markov decision problem

Yinyu Ye · 2005

Cited alongside, same era.

Stochastic approximation: a dynamical systems viewpoint

Vivek S. Borkar · 2008

Cited alongside, same era.

Robust stochastic approximation approach to stochastic programming

Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro · 2009

Cited alongside, same era.

Abstract dynamic programming

Dimitri P Bertsekas · 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

Yin Tat Lee and Aaron Sidford · 2015