Computational Complexity of Asynchronous Policy Iteration for Two-Player Zero-Sum Markov Games
Chenyu Xu, Sihai Zhang, Zhengdao Wang
Abstract
Bertsekas recently proposed Asynchronous Policy Iteration (API) as an alternative algorithm of Policy Iteration (PI) for solving the problem of two-player zero-sum Markov games. To quantifying the benefits of API, besides its flexibility for parallel and asynchronous implementation, the focus of this paper is to derive the computational complexity of API. We show that to reach within ϵ error to the optimal value function, the computational complexity of API is at most O (poly (n, m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> , m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> , ln(1/(1 − γ))), where n is the number of states, m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> , m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> are the number of actions for player 1 and player 2 respectively, and γ is the discount factor.
BibTeX
@inproceedings{icassp2024_computationalcom,
title = {Computational Complexity of Asynchronous Policy Iteration for Two-Player Zero-Sum Markov Games},
author = {Chenyu Xu and Sihai Zhang and Zhengdao Wang},
booktitle = {ICASSP 2024},
year = {2024}
}