Multi-agent reinforcement learning in Markov games

Game playing has been a popular problem area for research in artificial intelligence and machine learning for many years. In almost every study of game playing and machine learning, the focus has been on games with a finite set of states and a finite set of actions. Further, most of this research has focused on a single player or team learning how to play against another player or team that is applying a fixed strategy for playing the game.; In this dissertation, we provide and evaluate algorithms for learning strategies in two player games with large state and action spaces. First, we focus on the class of differential games in which the state space and the action space are both continuous. We model these games as discrete Markov games and provide methods for representing the state and actions spaces at varying levels of resolution. Second, we explore multi-agent learning and develop algorithms for "co-learning" in which all players attempt to learn their optimal strategies simultaneously.; Specifically, in this dissertation we compare several algorithms for a single player to learn an optimal strategy against a fixed opponent. Next we combine the results of one algorithm--a genetic algorithm--with a second algorithm--a memory-based learning algorithm--to yield performance exceeding the capabilities of either algorithm alone. Then we explore two approaches to co-learning in which both players learn simultaneously. We demonstrate strong performance by a memory-based reinforcement learner and comparable but faster performance with a tree-based reinforcement learner. In addition to the experimental results, we also provide an overview of machine learning and game playing as well as an overview of differential and Markov games.