Solving H-horizon, stationary Markov decision problems in time proportional to log(H)

By Paul Tseng. 1990

How researchers see this paper

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

Citations in the corpus

RUDDER: Return Decomposition for Delayed Rewards (2018, background): “espect to a weighted sup-norm. That the Bellman operator is a contraction mapping with respect to a weighted sup-norm has been proved in Tseng, 1990, in Lemma 3 with equation (13) and text thereafter [111]. Also Proposition 1 in Bertsekas and Tsitsiklis, 1991, [10], Theorems 3 and 4(b) & 4(c) in”
An Analysis of Stochastic Shortest Path Problems (1991, background): “Furthermore, µ is improper if and only if under P (µ), there exists an ergodic class other than {1}.”
On the undecidability of probabilistic planning and related stochastic optimization problems (2003, background): “The computational complexity of finite-horizon control problems has received considerable attention recently, see for example [10,20,39,48].”
Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time (2017, background): “Its convergence and complexity have been thoroughly analyzed; see e.g. [28, 22].”
Algorithms for Sequential Decision Making (1996, methodology): “When combined with a result by Tseng [162], presented here as Lemma 2.”
Planning and Acting in Partially Observable Stochastic Domains (1998, background): “It can be shown [52] that there exists a t , polynomial in jSj, jAj, the magnitude of the largest value of R(s; a), and 1=(1 ), such that the greedy policy with respect to Vt is equal to the optimal in nite-horizon policy, .”
The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate (2011, methodology): “The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate”
A survey of computational complexity results in systems and control (2000, background): “Still, (Tseng, 1990) shows that for any "xed a(1, the problem V.”
Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems (2017, methodology): “Three major deterministic approaches are the value iteration method [2, 24, 18] , the policy iteration method [12, 19, 28, 22], and linear programming methods [11, 10, 28, 22, 27].”