The Xpilot-AI video game platform allows the creation of artificially intelligent and autonomous control agents. At the same time, the Xpilot environment is highly complex, with very many state variables and action choices. Basic reinforcement learning (RL) techniques are somewhat limited in their application when dealing with such large state- and action-spaces, since the repetition of exposure that is key to their value updates can proceed very slowly. To solve this problem, state abstractions are often generated, allowing learning to move more quickly, but often requiring the programmer to hand-craft state representations, reward functions, and action choices in an ad hoc manner. We apply an automated technique for generating useful abstractions for learning, adaptive Kanerva coding. This method employs a small sub-set of the original states as a proxy for the full environment, updating values over the abstract representative prototype states in a manner analogous to Q-learning. Over time, the set of prototypes is adjusted to provide more effective coverage and abstraction, again automatically. Our results show that this technique allows a simple learning agent to double its survival time when navigating the Xpilot environment, using only a small fraction of the full state-space as a stand-in and greatly increasing the potential for more rapid learning.

The worst-case complexity of general decentralized POMDPs, which are equivalent to partially observable stochastic games (POSGs) is very high, both for the cooperative and competitive cases. Some reductions in complexity have been achieved by exploiting independence relations in some models. We show that these results are somewhat limited: when these independence assumptions are relaxed in very small ways, complexity returns to that of the general case.