We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real @math , let us call a stochastic game @math -ergodic, if its values from any two initial positions differ by at most @math . The proposed new algorithm outputs for every @math in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an @math -range, or identifies two initial positions @math and @math and corresponding stationary strategies for the players proving that the game values starting from @math and @math are at least @math apart. In particular, the above result shows that if a stochastic game is @math -ergodic, then there are stationary strategies for the players proving @math -ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is @math -ergodic, then there are @math -optimal stationary strategies for every @math . The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.
The following four algorithms for undiscounted stochastic games are based on stronger "ergodicity type" conditions: the strategy iteration algorithm by Hoffman and Karp @cite_17 requires that for any pair of stationary strategies of the two players the obtained Markov chain has to be irreducible; two value iteration algorithms by Federgruen are based on similar but slightly weaker requirements; see @cite_16 for the definitions and more details; the recent algorithm of Chatterjee and Ibsen-Jensen @cite_20 assumes a weaker requirement than the strong ergodicity required by Hoffman and Karp @cite_17 : they call a stochastic game almost surely ergodic if for any pair of (not necessarily stationary) strategies of the two players, and any starting position, some strongly ergodic class (in the sense of @cite_17 ) is reached with probability 1.
@cite_16 @cite_20 @cite_17
2039151826 2156268532
This paper considers undiscounted two-person, zero-sum sequential games with finite state and action spaces. Under conditions that guarantee the existence of stationary optimal strategies, we present two successive approximation methods for finding the optimal gain rate, a solution to the optimality equation, and for any ϵ > 0, ϵ-optimal policies for both players. A stochastic game is played in a sequence of steps; at each step the play is said to be in some state i, chosen from a finite collection of states. If the play is in state i, the first player chooses move k and the second player chooses move l, then the first player receives a reward akli, and, with probability pklij, the next state is j. The concept of stochastic games was introduced by Shapley with the proviso that, with probability 1, play terminates. The authors consider the case when play never terminates, and show properties of such games and offer a convergent algorithm for their solution. In the special case when one of the players is a dummy, the nonterminating stochastic game reduces to a Markovian decision process, and the present work can be regarded as the extension to a game theoretic context of known results on Markovian decision processes.