Artificial Intelligence

When an opponent with a stationary and stochastic policy is encountered in a two-player competitive game, model-free Reinforcement Learning (RL) techniques such as Q-learning and Sarsa(λ) can be used to learn near-optimal counter strategies given enough time. When an agent has learned such counter strategies against multiple di-verse opponents, it is not trivial to decide which one to use when a new unidentified opponent is encountered. Opponent modeling provides a sound method for accom-plishing this in the case where a policy has already been learned against the new op-ponent; the policy corresponding to the most likely opponent model can be employed. When a new opponent has never been encountered previously, an appropriate policy may not be available. The proposed solution is to use model-based RL methods in conjunction with separate environment and opponent models. The model-based RL algorithms used were Dyna-Q and value iteration (VI). The environment model allows an agent to reuse general knowledge about the game that is not tied to a specific oppo-nent. Opponent models that are evaluated include Markov chains, Mixtures of Markov chains, and Latent Dirichlet Allocation on Markov chains. The latter two models are latent variable models, which make predictions for new opponents by estimating their latent (unobserved) parameters. In some situations, I have found that this allows good predictive models to be learned quickly for new opponents given data from previous opponents. I show cases where these models have low predictive perplexity (high accuracy) for novel opponents. In theory, these opponent models would enable model-based RL agents to learn best response strategies in conjunction with an environment model, but converting prediction accuracy to actual game performance is non-trivial. This was not achieved with these methods for the domain, which is a two-player soccer game based on a physics simulation. Model-based RL did allow for faster learning in the game, but did not take full advantage of the opponent models. The quality of the environment model seems to be a critical factor in this situation. ii