Browse Books

Reviewer: Ernst L. Leiss

The capability and accessibility of modern digital computers, one of the most powerful scientific tools ever invented, have resulted in computer simulations assuming the role of traditional experiments in many areas of scientific investigation. This is particularly true of complex interconnected information systems. Such systems are generally both hierarchical and distributed in structure and contain a large number of decision makers operating in the presence of great uncertainty. Simulations of these systems, under widely different conditions using heuristic assumptions, provide a qualitative understanding of their performance. This in turn has led to a search for new theoretical principles, paradigms, and methods to explain failure and extend successful results. The learning automaton presented in this book is one such paradigm. The rationale underlying the learning approach is based on the desire for adaptive decision making in highly uncertain stochastic environments. The learning automaton achieves this, and in addition, can be implemented in a distributive manner, a critical feature for dealing with large complex systems. Perhaps most important, unlike heuristic techniques, the automaton approach has been developed in a systematic and analytically tractable fashion. Work on learning automata was started in the 1960s in the Soviet Union by M. L. Tsetlin and his co-workers. However, the term “automaton theory” used by Tsetlin had little in common with the research followed by western automaton theorists and was much closer in spirit to the models of mathematical learning theory and learning machines such as the perceptron. In fact, some of the mathematical models studied intensively by American psychologists in the 1950s could be regarded as the forerunners of the developments in this field. In the 1970s it was realized that similar problems had been independently and extensively investigated in many other fields, including statistics and operations research, but the common basis of these parallel developments was masked by different terminologies. Although the basic questions are quite similar in the different areas, the viewpoint is conditioned to a great extent by the practitioners. During the past two decades research workers in the systems field in different countries have consistently used the term “learning automaton” to describe systems that improve their performance in random environments. It is this class of systems that is treated in this book. …[Its] principal theme is how a sequential decision maker with a finite number of choices in the action set would choose an action at every instant, based on the responses of a random environment (from the Preface). Narendra and Thathachar provide a welcome comprehensive treatment of how automata are used in learning by pulling together results from mathematical systems theory, psychology, and automata theory. Chapter 1 gives a brief survey of some learning strategies, with chapter 2 introducing the basic model of a learning automaton. Chapters 3 and 4 examine fixed- and variable-structure automata and their variants in more detail. The important notion of convergence is explored and analyzed in chapter 5. Chapter 6 presents a major generalization of the previously discussed models by admitting as a response to an action any real value within a finite interval. Chapter 7 introduces time; specifically, it discusses what can and cannot be achieved if the characteristics of the learning environment vary over time. The final two chapters discuss interconnected automata and games, as well as applications of learning automata, such as network routing. Three brief appendices (on Markov chains, Martingales, and distance diminishing operators) survey some formal notions fundamental to the material of the book.