A Tutorial Introduction to Reinforcement Learning

In this paper, we present a brief survey of Reinforcement Learning (RL), with particular emphasis on Stochastic Approximation (SA) as a unifying theme. The scope of the paper includes Markov Reward Processes, Markov Decision Processes, Stochastic Approximation methods, and widely used algorithms such as Temporal Difference Learning and Q-learning. Reinforcement Learning is a vast subject, and this brief survey can barely do justice to the topic. There are several excellent texts on RL, such as [4, 27, 34, 33]. The dynamics of the Stochastic Approximation (SA) algorithm are analyzed in [25, 22, 3, 23, 2, 9, 10]. The interested reader may consult those sources for more information. In this survey, we use the phrase "reinforcement learning" to refer to decision-making with uncertain models, and in addition, current actions alter the future behavior of the system. Therefore, if the same action is taken at a future time, the consequences might not be the same.