On Terminating Stochastic Games

This paper describes a stochastic game in which the play terminates in a finite number of steps with probability 1. The game is called a terminating stochastic game. When the play terminates at any step, the play is regarded to reach to an absorbing state in the Markov chain under consideration. Hence, the terminating stochastic game is a nonstationary Markov chain with rewards in which our concern is the transient behavior before absorption. In particular, when one of the players is a dummy, the stochastic game reduces to a Markovian decision process of special type. This paper discusses such games. We introduce a new concept of rewards and formulate three problems arising in the games by linear programming. Finally, numerical examples are presented.

• 저널Management Science · 16(9) · 560–571
• 토픽Reinforcement Learning in Robotics · Artificial Intelligence
• DOI10.1287/mnsc.16.9.560
• 저자Hisashi Mine, Kazutaka YAMADA, S. Osaki