Value set iteration for two-person zero-sum Markov games

详细信息    查看全文

• 作者：Hyeong Soo Chang¹ ; ^{hschang@sogang.ac.kr}
• 关键词：Two-person zero-sum Markov game ; Value iteration ; Policy iteration ; Stochastic game
• 刊名：Automatica
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：76
• 期：Complete
• 页码：61-64
• 全文大小：374 K
• 卷排序：76

文摘

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.