SimpleStatisticalGradient-FollowingAlgorithmsfor.pdf

Machine Learning, 8, 229-256 (1992) ? 1992 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning RONALD J. WILLIAMS rjw@corwin.ccs.northeastern.edu College of Computer Science, 161 CN, Northeastern University, 360 Huntington Ave., Boston, MA 02115 Abstract. This article presents a general class of associative reinforcement learning algorithms for connectionist networks containing stochastic units. These algorithms, called REINFORCE algorithms, are shown to make weight adjustments in a direction that lies along the gradient of expected reinforcement in both immediate-reinforcement tasks and certain limited forms of delayed-reinforcement tasks, and they do this without explicitly computing gradient estimates or even storing information from which such estimates could be computed. Specific examples of such algorithms are presented, some of which bear a close relationship to certain existing algorithms while others are novel but potentially interesting in their own right. Also given are results that show how such algorithms can be naturally integrated with backpropagation. We close with a brief discussion of a number of additional issues surrounding the use of such algorithms, including what is known about their limiting behaviors as well as further considerations that might be used to help develop similar but potentially more powerful reinforcement learning algorithms. Keywords. Reinforcement learning, connectionist networks, gradient descent, mathematical analysis 1. Introduct ion The general framework of reinforcement learning encompasses a broad variety of problems ranging from various forms of function optimization at one extreme to learning control at the other. While research in these individual areas tends to emphasize different sets of issues in isolation, it is likely that effective reinforcement learning techniques for autonomous