LEARNING BY ST ATE RECURRENCE DETECfION Bruce E. Rosen, James M. Goodwint, and Jacques J. Vidal University of California, Los Angeles, Ca. 90024 ABSTRACT This research investigates a new technique for unsupervised learning of nonlinear control problems. The approach is applied both to Michie and Chambers BOXES algorithm and to Barto, Sutton and Anderson's extension, the ASE/ACE system, and has significantly improved the convergence rate of stochastically based learning automata. Recurrence learning is a new nonlinear reward-penalty algorithm. It exploits information found during learning trials to reinforce decisions resulting in the recurrence of nonfailing states. Recurrence learning applies positive reinforcement during the exploration of the search space, whereas in the BOXES or ASE algorithms, only negative weight reinforcement is applied, and then only on failure. Simulation results show that the added information from recurrence learning increases the learning rate. Our empirical results show that recurrence learning is faster than both basic failure driven learning and failure prediction methods. Although recurrence learning has only been tested in failure driven experiments, there are goal directed learning applications where detection of recurring oscillations may provide useful information that reduces the learning time by applying negative, instead of positive reinforcement.

The approach is applied both to Michie and Chambers BOXES algorithm and to Barto, Sutton and Anderson's extension, the ASE/ACE system, and has significantly improved the convergence rate of stochastically based learning automata. Recurrencelearning is a new nonlinear reward-penalty algorithm. It exploits information found during learning trials to reinforce decisions resulting in the recurrence of nonfailing states. Recurrence learning applies positive reinforcement during the exploration of the search space, whereas in the BOXES or ASE algorithms, only negative weight reinforcement is applied, and then only on failure. Simulation results show that the added information from recurrence learning increases the learning rate.

AAAI is a society devoted to supporting the progress in science, technology and applications of AI. I thought I would use this occasion to share with you some of my thoughts on the recent advances in AI, the insights and theoretical foundations that have emerged out of the past thirty years of stable, sustained, systematic explorations in our field, and the grand challenges motivating the research in our field.

Empirical evidence suggests that searching deeper in game trees using the minimax propagation rule usually improves the quality of decisions significantly. However, despite many recent theoretical analyses of the effects of minimax look ahead, however, this phenomenon has still not been convincingly explained. Instead, much attention has been given to so-called pathological behavior, which occurs under certain assumptions. This article supports the view that pathology is a direct result of these underlying theoretical assumptions. Pathology does not occur in practice, because these assumptions do not apply in realistic domains. The article presents several arguments in favor of minimaxing and focuses attention on the gap between their analytical formulation and their practical meaning. A new model is presented based on the strict separation of static and dynamic aspects in practical programs. finally, certain methods of improving minimax look-ahead are discussed, drawing on insights gained from this research.

Citing the confusing statements in the AI literature concerning the relationship between branch and bound (B&B) and heuristic search procedures were present a simple and general formulation of B&B which should help dispel much of the confusion. We illustrate the utility of the formulation by showing that through it some apparently very different algorithms for searching And/Or trees reveal the specific nature of their similarities and differences. In addition to giving new insights into the relationships among some AI search algorithms, the general formulation also provides suggestions on how existing search procedures may be varied to obtain new algorithms.

A new procedure is presented for growing min-max game trees. In large games, such as chess, decisions must be based on incomplete search trees. The new tree-growth procedure is based on “conspiracy numbers” as a measure of the accuracy of the root minimax value of an incomplete tree. Conspiracy numbers measure the number of leaf nodes whose value must change in order to change the minimax root value by a given amount. Trees are grown in a way that maximizes the conspiracy required to change the root value.

Get Citation Alerts New Citation Alert added!

In Mora, T. (Ed.), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pp. 99–110. Springer-Verlag.

As a book about search, it is thorough, at the state of the art, and contains expositions that will delight the expert with their clarity and depth. However, it is not, per se, a book about AI (nor was it intended to be) or about the history, philosophy, or cognitive aspects of heuristic knowledge.

To fully appreciate Professor Pearl's book, begin with a and the numerous techniques for representing knowledge careful reading of the title. It is a book about "..Intelligent-and uncertainty in common use in mainstream AI. ..Strategies.." for the discovery and use of "Heuristics.. " Chapter 5 begins a quantitative performance analysis of to allow computers to solve ".. Search.. ' ' problems. This includes a nice exposition on is a critical component in AI programs (Nilsson 1980, Barr branching processes, although the mathematically unsophisticated and Feigenbaum 1982), and in this sense Pearl's book is a reader may find it difficult. Here Pearl introduces strong contribution to the field of AI. It serves as an excellent probabilistic models to complement probabilistic heuristics. As a book about search, it is thorough, at analysis of search heuristics, and to a probabilistic analysis the state of the art, and contains expositions that will delight of nonadmissible heuristics in ...