A Comparison of Traversal Strategies for Tangled Program Graphs under the Arcade Learning Environment

Abstract

Tangled program graphs provides a framework for constructing modular genetic programming solutions to visual reinforcement learning tasks. In order to guard against the development of cycles within the resulting graph, and therefore introduce the halting problem, a traversal strategy forbidding the revisiting of vertices was originally assumed. In this thesis an alternative traversal strategy wherein vertex revisits are allowed but edge revisits are not is explored. An empirical study is performed using 20 game titles from the Arcade Learning Environment in order to assess the relative impact of the different traversal strategies on the resulting agent behaviours and underlying graph characteristics. Ultimately both strategies appear to result in behaviours that are statistically very similar. The most notable differences appear in distributions of actions used to reach the same performance.