Solving Infinite-Horizon Discounted Markov Games Using a Superharmonic Least-Element Algorithm

In this paper we present an algorithm for solving infinite-horizon discounted Markov games based upon the fact that the value function is a least element of a superharmonic set. The algorithm produces a pair of policies whose value function is within a specified error of the solution to the fixed point equation. Part of the algorithm involves solving a set of fractional programs which are replaced by equivalent linear programs.

• 저널Management Science · 39(1) · 93–100
• 토픽Complexity and Algorithms in Graphs · Computational Theory and Mathematics
• DOI10.1287/mnsc.39.1.93
• 저자D. J. White