The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate

By Yinyu Ye. 2011

229 citations recorded by the source corpus.

Subfields: Management Information Systems, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Information Systems

In Management Science and Operations Research

Citations in the corpus

Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “Ye (2011) shows that the policy iteration of discounted MDP is a form of dual simplex method, which is strongly polynomial for the equivalent linear program and terminates in run time O ( |A×S| 2 1 γ ).”
Primal-dual algorithms for discounted Markov decision processes (2015, background): “Collectively, the recent papers [7], [17], [8], [9], [15] have established that policy iteration runs in polynomial time if a certain input parameter (the discount factor) remains fixed across problem instances, but can run in exponential time if the discount factor is allowed to vary for problem in”
The Value Function Polytope in Reinforcement Learning (2019, methodology): “, 1995), namely the worst case convergence in exponential time, it was demonstrated that the simplex algorithm applied to MDPs with an adequate pivot rule converges in polynomial time (Ye, 2011).”
Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time (2017, methodology): “Value Iteration |S|2|A|L log(1/(1−γ)) 1−γ and |S| 2|A| log(1/(1−γ) ) 1−γ [28, 22] Policy Iteration (Block Simplex) |S|(4)|A|(2) 1−γ log( 1 1−γ ) [32],[27] LP Algorithm Õ(|S|2.”
Safe Policy Iteration (2013, background): “When either Qπk or the corresponding greedy policy πk+1 cannot be computed exactly, approximate policy iteration (API) algorithms (refer to (Bertsekas, 2011) for a recent survey on API) need to be considered.”
An online primal-dual method for discounted Markov decision processes (2016, background): “A seminal paper [25] shows that the policy iteration for the MDP is a form of simplex method, which is strongly polynomial for the equivalent linear program.”
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes (2019, background): “There are other results for obtaining an exactly optimal policy for the MDP M as well, for instance the SIMPLEX policy iteration Ye (2011), which runs in time O (poly( N/ (1 − γ )) .”