Learning Automata

An Introduction

Kumpati S. Narendra, Mandayam A.L. Thathachar

• Éditeur: Dover Publications
• Année: 2013
• ISBN:
  9780486268460
• Sujet: Technologie et ingénierie
• Sous-sujet: Ingénierie industrielle

This self-contained introductory text on the behavior of learning automata focuses on how a sequential decision-maker with a finite number of choices responds in a random environment. Topics include fixed structure automata, variable structure stochastic automata, convergence, 0 and S models, nonstationary environments, interconnected automata and games, and applications of learning automata. A must for all students of stochastic algorithms, this treatment is the work of two well-known scientists and is suitable for a one-semester graduate course in automata theory and stochastic algorithms. This volume also provides a fine guide for independent study and a reference for students and professionals in operations research, computer science, artificial intelligence, and robotics. The authors have provided a new preface for this edition.

Chapter 1

Introduction

1.1 Introduction

The revolutionary advances in information technology that have been made during the last fifty years may be attributed, to a large extent, to parallel developments in system theoretic methodologies and computer technology. From the time the abstract concept of feedback was introduced in the early 1930s and the term cybernetics was coined by Norbert Wiener (1948) in the 1940s to describe communication and control in man and machine, systems theory has grown into a powerful discipline for the analysis and synthesis of dynamical systems. Its effects are felt throughout the industrial world and the systems that have been generated have become integral parts of our socio–economic environment.

The computer, which only a few decades ago spent its fledgling years as a mere computational tool, has developed into today’s supercomplex microelectronic device responsible for far–reaching changes in processing, storage, and communication of information. Major advances in computer technology have invariably had a profound impact on systems methodology. Even in the initial stages the computer freed the systems theorist from the notion that only closed form solutions were acceptable for practical problems. Mathematical algorithms implemented on a digital computer were recognized as viable substitutes, provided their convergence to the desired state could be established. More recently in the solution of complex problems, where algorithms cannot be developed readily, both specific and general heuristics have been proposed. The availability of microprocessors has also made practical implementation a matter of much less concern to the designer than envisaged earlier and it is only the lack of a well established theory or a good heuristic that has made the realization of practical solutions difficult.

The main objectives of systems theory in the early stages of development concerned the identification and control of well defined deterministic and stochastic systems. Over the decades, interest gradually shifted to systems which contained a substantial amount of uncertainty, since most practical systems belong to this class. Since the ability of living organisms to cope with uncertainty is well known, it is only natural that efforts were also made to incorporate similar features in engineering systems. As a result, a variety of terms borrowed from psychology and biology, such as adaptation, learning, pattern recognition, and self–organization, were introduced into the systems literature and developed into independent disciplines with their own following. The field of adaptive control at present is concerned with the stable control of complex dynamical systems when some uncertainty exists regarding the dynamics of the controlled plant. Learning deals with the ability of systems to improve their responses based on past experience. Pattern recognition, developed mainly for the analysis of cognitive processes, is the methodology for classifying objects into predetermined classes. Self–organizing systems, as the name implies, organize their structures to optimize their performance in uncertain environments. All of these areas are related to the broad field of artificial intelligence (AI), which evolved from the disciplines of computer science, psychology, and cybernetics and which refers to the machine emulation of higher mental functions.

Despite the successes of these different approaches and the large number of publications that have appeared in specialized journals that attest to their vitality, the border–lines between the different areas continue to be less than distinct. Although the sources of the problems treated and the terminologies used are different, many of the difficulties encountered are common to all of them. These include the choice of the analytical or symbolic models used to represent the unknown systems, the nature of information that needs to be obtained, the structure of the decision space, and the performance criterion to be optimized. Hence (while such a prospect is nowhere in sight), any one of the terms “adaptive,” “learning,” or “AI” could be used generically to describe the various classes of systems treated in these different areas. However, the subdisciplines continue to flourish independently and even to spawn new terms of their own. For example “intelligent control” has been used to characterize the discipline that couples advanced methodologies demonstrating machine intelligence with system theoretic approaches (Saridis, 1979).

The theories and applications presented in this book relate – on a prescriptive level – to all of the areas above. The models, algorithms, and analysis are readily applicable to the design of adaptive or learning systems. However, the basic learning paradigm, discussed in detail in Chapter 2, is also closely related to many of the descriptive learning theories developed over a long period by psychologists. Such theories have been propounded by major schools of psychology, for example, behaviorism, gestalt, and cognitivism; and the names of Thorndike, Pavlov, Guthrie, Hull, Tollman, Skinner, and Estes are associated with them (Bower and Hilgard 1981). In these paradigms, learning is used to explain the processes that are necessary for the occurrence of changes in the behavior of organisms while adjusting to their environments. Since adjustment to complex environments is also desirable on the part of man–made decision makers and controllers, it is not surprising that the same principles were gradually adopted for prescriptive use in their design. In the descriptive learning paradigm as well as the learning automaton model treated in this book, a decision maker operates in a random environment and updates its strategy for choosing actions on the basis of the elicited response. The decision maker, in such a feedback configuration of decision maker (or automaton) and environment, is referred to as a learning automaton. The automaton has a finite number of actions and corresponding to each action, the response of the environment can be either favorable or unfavorable with a certain probability. The uses of deterministic and stochastic strategies by which the automaton can achieve different performance objectives are treated in the first few chapters. Methods by which the basic building blocks can be interconnected in a hierarchical or decentralized fashion are described in the chapters that follow. Using the theory of Markov processes, the asymptotic behavior of collectives of automata is stated precisely for different interconnections. The theory presented in the book applies to either a prescriptive or a descriptive viewpoint of the basic learning scenario.

The need for learning in identification or control problems depends on the prior information that is available regarding the system, the characteristics of the noise present, and the constraints that exist on the inputs. For low levels of uncertainty, learning may not be the most effective approach. But for highly uncertain systems it may be essential for adequate system performance. The inverted pendulum or pole balancing problem treated in undergraduate text books on control theory is a simple example of this. The problem is to exert a force on the base of a cart so as to balance a pole that is hinged to it. When the relevant parameters of the system, such as the mass of the cart and the mass and length of the pole are given, the resulting problem is a deterministic one. Well known principles of control theory can be used to balance the pole in such a case. When some of the parameters are unknown, we have an adaptive control problem and the necessary stabilizing input can be generated following the estimation of the unknown parameters, based on repeated trials. When even the dynamic relations are not used to determine the control, the problem becomes significantly more difficult and learning must be invoked. Learning control for this problem has been suggested in the past by many authors including Widrow and Smith (1964), and has been revisited recently in the context of adaptive networks (Barto, Sutton and Anderson, 1983). In the latter approach associations are made between input and output by searching under the influence of reinforcement feedback, which is similar in spirit to the approach used by the learning automaton. Hence, the pole balancing problem can be considered to be qualitatively typical of the class of problems to which the methods developed in the book can be applied.

In more complex systems, the controllers or decision makers are organized in a hierarchical or decentralized fashion and must operate with incomplete information regarding either the structure or parameters of the system. The distributed nature of the system also necessitates that control action be taken using local information. To deal with such systems effectively, an understanding of the principles of adaptation, learning, pattern recognition, artificial intelligence, and self–organization may be necessary, depending on the nature of the problem. For example, pattern recognition ba...

Table des matières

• Cover Page
• Title Page
• Copyright Page
• Dedication
• Contents
• Preface
• 1: Introduction
• 2: The Learning Automaton
• 3: Fixed Structure Automata
• 4: Variable Structure Stochastic Automata
• 5: Convergence
• 6: Q and S Models
• 7: Nonstationary Environments
• 8: Interconnected Automata and Games
• 9: Applications of Learning Automata
• Epilogue
• Appendix A: Markov Chains
• Appendix B: Martingales
• Appendix C: Distance Diminishing Operators
• Bibliography
• Index
• Back Cover