The N-Tuple Bandit Evolutionary Algorithm for Game Agent Optimisation

This paper describes the N-Tuple Bandit Evolutionary Algorithm (NTBEA) and its application to optimising the parameters of a rolling horizon evolution game-playing agent. The NTBEA combines evolutionary search with Multi-Armed Bandit algorithms (MABs) in order to provide an algorithm which is robust to noise, has an explicit way to balance the tradeoff between exploration and exploitation, and provides a statistical model of the fitness landscape as an additional output. The applications of this type of algorithm are numerous. In our research we have already applied it successfully to hyperparameter optimisation [1] and automated game tuning [2]. Furthermore, if the inherent fitness landscape is flat, then the exploration term provides a means for performing novelty search [3]. A. Estimation of Distribution Algorithms Estimation of Distribution Algorithms (EDAs) [4], [5], [6], [7], [8] are a powerful class of Evolutionary Algorithms (EAs).