Towards solving 2-TBSG efficiently. (3rd July 2020)

• Record Type: Journal Article
• Authors: Jia, Zeyu; Wen, Zaiwen; Ye, Yinyu
• Is Part Of: Optimization methods and software. Volume 35:Number 4(2020)
• Page Start: 706
• Page End: 721
• Publication Date: 2020-07-03
• Subjects: Markov decision process -- two-player turn-based stochastic game -- simplex strategy iteration -- strongly polynomial time; 90C05 -- 90C40 -- 68Q25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1695131
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : Two-player turn-based stochastic game (2-TBSG) is a two-player game model which aims to find Nash equilibriums and is widely utilized in reinforcement learning and AI. Inspired by the fact that the simplex method for solving the deterministic discounted Markov decision processes is strongly polynomial independent of the discount factor, we are trying to answer an open problem whether there is a similar algorithm for 2-TBSG. We develop a simplex strategy iteration where one player updates its strategy with a simplex step while the other player finds an optimal counterstrategy in turn, and a modified simplex strategy iteration. Both of them belong to a class of geometrically converging algorithms. We establish the strongly polynomial property of these algorithms by considering a strategy combined from the current strategy and the equilibrium strategy. Moreover, we present a method to transform general 2-TBSGs into special 2-TBSGs where each state has exactly two actions.