Sequence-Learning Algorithm Based on Backward Chaining

Abstract

This article considers the problem of learning the correct temporal sequence of discrete behaviors from a finite behavior set that will lead to completion of a complex task, using only stochastic reinforcement from the environment. A trial-and-error learning algorithm is proposed that is inspired by backward chaining from the animal training discipline. The procedure is analytically formulated using a serial composition of finite action-set learning automata with delay. Simulation of the proposed algorithm shows that the algorithm does indeed lead to sequence learning. The effect of parametric variation in the magnitude and quality of reinforcement is investigated in both theory and simulation. It is shown that a fundamental tradeoff exists between quality and speed of learning. It is also shown that the algorithm has the ability to learn desirable action sequences among several feasible action sequences through the use of relative rewards, which may be interpreted using the Bellman principle of optimality.