Value set iteration for two-person zero-sum Markov games. (February 2017)

• Record Type: Journal Article
• Authors: Chang, Hyeong Soo
• Is Part Of: Automatica. Volume 76(2017)
• Page Start: 61
• Page End: 64
• Publication Date: 2017-02
• Subjects: Two-person zero-sum Markov game -- Value iteration -- Policy iteration -- Stochastic game; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2016.10.010
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: We present a novel exact algorithm called "value set iteration" (VSI) for solving two-person zero-sum Markov games (MGs) as a generalization of value iteration (VI) and as a general framework of combining multiple solution methods. We introduce a novel operator in the value function space and iteratively apply the operator with any sequence of the set of policies, extending Chang's VSI for MDPs into the MG setting. We show that VSI for MGs converges to the equilibrium value function with at least linear convergence rate and establish that VSI can potentially improve the convergence speed in terms of the number of iterations by proper setting of the sequence of the set of policies.