Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

ABSTRACT

We present two new algorithms for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP). The first one is an adaptation of an algorithm of Young, Tarjan and Orlin for finding minimum mean weight cycles. It runs in O(mn + n² log n) time, where n is the number of vertices (or states) and m is the number of edges (or actions). The second one is an adaptation of a classical algorithm of Karp for finding minimum mean weight cycles. It runs in O(mn) time. The first algorithm has a slightly slower worst-case complexity, but is faster than the first algorithm in many situations. Both algorithms improve on a recent O(mn²)-time algorithm of Andersson and Vorobyov. We also present a randomized Õ(m^1/2n²)-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving several previous algorithms.

REFERENCES

• 1: D. Andersson and S. Vorobyov. Fast algorithms for monotonic discounted linear programs with two variables per inequality. TR NI06019-LAA, Isaac Newton Institute, Cambridge, United Kingdom, 2006.
• 2: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 3: Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific, 2001
• 4: Henrik Björklund , Sergei Vorobyov, Combinatorial structure and randomized subexponential algorithms for infinite games, Theoretical Computer Science, v.349 n.3, p.347-360, 16 December 2005 [doi>10.1016/j.tcs.2005.07.041]
• 5: Edith Cohen , Nimrod Megiddo, Improved Algorithms for Linear Inequalities with Two Variables per Inequality, SIAM Journal on Computing, v.23 n.6, p.1313-1350, Dec. 1994 [doi>10.1137/S0097539791256325]
• 6: Anne Condon, The complexity of stochastic games, Information and Computation, v.96 n.2, p.203-224, Feb. 1992 [doi>10.1016/0890-5401(92)90048-K]
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: F. d'Epenoux. A probabilistic production and inventory problem. Manag. Science, 10(1):98--108, 1963.
• 9: Cyrus Derman, Finite State Markovian Decision Processes, Academic Press, Inc., Orlando, FL, 1970
• 10: A. Ehrenfeucht and J. Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 8:109--113, 1979.
• 11: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 12: V. A. Gurvich , A. V. Karzanov , L. G. Khachivan, Cyclic games and an algorithm to find minimax cycle means in directed graphs, USSR Computational Mathematics and Mathematical Physics, v.28 n.5, p.85-91, 1988 [doi>10.1016/0041-5553(88)90012-2]
• 13: Nir Halman, Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games Are All LP-Type Problems, Algorithmica, v.49 n.1, p.37-50, September 2007 [doi>10.1007/s00453-007-0175-3]
• 14: Dorit S. Hochbaum, Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality, SIAM Journal on Computing, v.23 n.6, p.1179-1192, Dec. 1994 [doi>10.1137/S0097539793251876]
• 15: R. A. Howard. Dynamic programming and Markov processes. MIT Press, 1960.
• 16: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 17: R. M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23(3):309--311, 1978.
• 18: L. G. Khachiyan. A polynomial time algorithm in linear programming. Soviet Math. Dokl., 20:191--194, 1979.
• 19: Michael Lederman Littman, Algorithms for sequential decision-making, Brown University, Providence, RI, 1996
• 20: Walter Ludwig, A subexponential randomized algorithm for the simple stochastic game problem, Information and Computation, v.117 n.1, p.151-155, Feb. 15, 1995 [doi>10.1006/inco.1995.1035]
• 21: Omid Madani , Richard Anderson, Complexity results for infinite-horizon markov decision processes, University of Washington, 2000
• 22: Omid Madani, On policy iteration as a Newton's method and polynomial policy iteration algorithms, Eighteenth national conference on Artificial intelligence, p.273-278, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 23: O. Madani. Polynomial value iteration algorithms for detrerminstic MDPs. In Proc. of the 18th UAI, pages 311--318, 2002.
• 24: Y. Mansour and S. P. Singh. On the complexity of policy iteration. In Proc. of the 15th UAI, pages 401--408, 1999.
• 25: M. Melekopoglou and A. Condon. On the complexity of the policy improvement algorithm for markov decision processes. ORSA Journal on Computing, 6(2):188--192, 1994.
• 26: Christos Papadimitriou , John N. Tsitsiklis, The complexity of Markov decision processes, Mathematics of Operations Research, v.12 n.3, p.441-450, August 1, 1987 [doi>10.1287/moor.12.3.441]
• 27: M. L. Puterman. Markov decision processes. Wiley, 1994.
• 28: L. S. Shapley. Stochastic games. Proc. Nat. Acad. Sci. U.S.A., 39:1095--1100, 1953.
• 29: Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]
• 30: Yinyu Ye, A New Complexity Result on Solving the Markov Decision Problem, Mathematics of Operations Research, v.30 n.3, p.733-749, August 2005 [doi>10.1287/moor.1050.0149]
• 31: N. E. Young, R. E. Tarjan, and J. B. Orlin. Faster parametric shortest path and minimum-balance algorithms. Networks, 21:205--221, 1991.
• 32: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]
• 33: Uri Zwick , Mike Paterson, The complexity of mean payoff games on graphs, Theoretical Computer Science, v.158 n.1-2, p.343-359, May 20, 1996 [doi>10.1016/0304-3975(95)00188-3]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms