Learning from Delayed Rewards

Abstract

In behavioural ecology, stochastic dynamic programming may be used as a general method for calculating animals' optimal behavioural policies. But how might the animals themselves learn optimal policies from their experience? The aim of the thesis is to give a systematic analysis of possible computational methods of learning efficient behaviour. First, it is argued that it does not follow from the optimality assumption that animals should learn optimal policies, even though they may not always follow them. Next, it is argued that Markov decision processes are a general formal model of an animal's behavioural choices in its environment. The conventional methods of determining optimal policies by dynamic programming are then described. It is not plausible that animals carry out calculations of this type. However, there is a random of alternative methods of organising the dynamic programming calculation, in ways that are plausible computational models of animal learning. In particular, there is an incremental Monte-Carlo method that enables the optimal values (or 'canonical costs') of actions to be learned directly, without any requirement for the animal to model its environment, or to remember situations and actions for more than a short period of time. A proof is given that this learning method works. Learning methods of this type are also possible for hierarchical policies. Previously suggested learning methods are reviewed, and some even simpler learning methods are presented without proof. Demonstration implementations of some of the learning methods are described.