Adaptive Adversarial Multi-Armed Bandit Approach to Two-Person Zero-Sum Markov Games

Author

Chang, Hyeong Soo ; Hu, Jiaqiao ; Fu, Michael C. ; Marcus, Steven I.

Author_Institution

Dept. of Comput. Sci. & Eng., Sogang Univ., Seoul, South Korea

Volume

55

Issue

2

fYear

2010

Firstpage

463

Lastpage

468

Abstract

This technical note presents a recursive sampling-based algorithm for finite horizon two-person zero-sum Markov games (MGs) based on the Exp3 algorithm developed by Auer et al. for adaptive adversarial multi-armed bandit problems. We provide a finite-iteration bound to the equilibrium value of the induced ??sample average approximation game?? of a given MG and prove asymptotic convergence to the equilibrium value of the given MG. The time and space complexities of the algorithm are independent of the state space of the game.

Keywords

Markov processes; approximation theory; computational complexity; convergence; game theory; iterative methods; Exp3 algorithm; adaptive adversarial multiarmed bandit approach; asymptotic convergence; equilibrium value; finite horizon two-person zero-sum Markov games; finite-iteration bound; induced sample average approximation game; recursive sampling-based algorithm; space complexity; state space; time complexity; Approximation algorithms; Computer science; Convergence; Mathematics; Probability distribution; Sampling methods; State-space methods; Statistics; Multi-armed bandit; sample average approximation; sampling; two-person zero-sum Markov game (MG);

fLanguage

English

Journal_Title

Automatic Control, IEEE Transactions on

Publisher

ieee

ISSN

0018-9286

Type

jour

DOI

10.1109/TAC.2009.2036333

Filename

5378483