Deep Reinforcement Learning for Adversarial Games on Graphs

Abstract

The game of cops and robbers is a multi-agent adversarial game played on graphs. Previous research on agent strategies for this game has focused on designing heuristics for minimax strategies and often imposes strict restrictions on the graph structure. This thesis develops a methodology that instead uses Deep Reinforcement Learning and Graph Convolutional Networks by training a cop and robber iteratively against each other. In addition, an efficient Vertex Pooling method is introduced that allows the approach to be scaled to large graphs with only a sub-linear increase in the neural network depth. The approach proposed in this thesis is also compared with traditional algorithms that may use heuristics.