9409912 Moore Reinforcement learning is a promising method for robots and other complex autonomous systems to program and improve themselves. It requires no fixed, pre-programmed decision routines and no pre- programmed system model. Its high degree of autonomy comes at a severe price: the curse of dimensionality, in which costs increase exponentially with the number of state variables. The proposed research will address this problem by adaptively partitioning the state space of the system into homogenous regions while the system is learning. Unimportant or unvarying regions are always represented by large partitions whilst critical regions or important problem features emerge as finely partitioned areas. The algorithms take advantage of two surprisingly powerful assumptions which are frequently true in problems with multivariate real-valued state spaces. First, that all possible paths through state space are continuous, and secondly that high quality execution of a task does not require perfect knowledge of the whole of state space. An important part of the proposal concerns the development of a suite of cheap robotic experiments, carefully designed to involve a wide variety of interesting non-linear problems. A learning algorithm which could learn many different real-world tasks automatically would be academically interesting and also have industrial impact.
