The Design of ϵ-Optimal Strategy for Two-Person Zero-Sum Markov Games

This letter focuses on designing approximate Nash strategies for the two-person zero-sum Markov game. Using the receding horizon method, the & varepsilon;-optimal strategies are designed to approximate Nash strategies by executing finite Gauss-Seidel iterations. The relationship between the approximation value of & varepsilon; and the number of iterations is also analyzed. Additionally, the & varepsilon;-optimal strategies are designed for two scenarios with imprecise parameters. For scenarios with imprecise values, the value of & varepsilon; is determined based on the errors between imprecise and iteration values. It provides a theoretical basis for efficiently designing & varepsilon;-optimal strategies using heuristic algorithms or approximate dynamic programming. For scenarios with imprecise transition probabilities, the value of & varepsilon; is determined based on the errors between the estimated and practical transition probabilities. It enables the use of pattern recognition technology or other methods to estimate practical transition probabilities for designing & varepsilon;-optimal strategies.