Global Versus Local Constructive Function Approximation For On-Line Reinforcement Learning

In order to scale to problems with large or continuous state-spaces, reinforcement learning algorithms need to be combined with function approximation techniques. The majority of work on function approximation for reinforcement learning has so far focused either on global function approximation with a static structure (such as multi-layer perceptrons), or on constructive architectures using locally responsive units. The former, whilst achieving some notable successes, has also been shown to fail on some relatively simple tasks. The locally constructive approach has been shown to be more stable, but may scale poorly to higher-dimensional inputs, as it will require a dramatic increase in resources. This paper explores the use of two constructive algorithms using non-locally responsive neurons based on the popular Cascade-Correlation supervised-learning algorithm. The algorithms are applied within the sarsa reinforcement learning algorithm, and their performance compared against both a multi-layer perceptron and a locally constructive algorithm (the Resource Allocating Network) across three reinforcement learning tasks. It is shown that the globally constructive algorithms are less stable, but that on some tasks they can achieve similar performance to the locally constructive approach, whilst generating much more compact solutions