Automata models of learning systems introduced in the 1960s were popularized as learning automata (LA) in a survey paper by Narendra and Thathachar (1974). Since then, there have been many fundamental advances in the theory as well as applications of these learning models. In the past few years, the structure of LA, has been modified in several directions to suit different applications. Concepts such as parameterized learning automata (PLA), generalized learning,automata (GLA), and continuous action-set learning automata (CALA) have been proposed, analyzed, and applied to solve many significant learning problems. Furthermore, groups of LA forming teams and feedforward networks have been shown to converge to desired solutions under appropriate learning algorithms. Modules of LA have been used for parallel operation with consequent increase in speed of convergence. All of these concepts and results are relatively new and are scattered in technical literature. An attempt has been made in this paper to bring together the main ideas involved in a unified framework and provide pointers to relevant references.

Nearest neighbor classifiers that use all the training samples for classification require large memory and demand large online testing computation. To reduce the memory requirements and the computation cost, many algorithms have been developed that perform nearest neighbor classification using only a small number of representative samples obtained from the training set. We call the classification model underlying all these algorithms as Voronoi networks (Vnets), because these algorithms discretize the feature space into Voronoi regions and assign the samples in each region to a class. In this paper we analyze the generalization capabilities of these networks by bounding the generalization error. The class of problems that can be "efficiently" solved by Vnets is characterized by the extent to which the set of points on the decision boundaries fill the feature space, thus quantifying how efficiently a problem can be solved using Vnets. We show that Vnets asymptotically converge to the Bayes classifier with arbitrarily high probability provided the number of representative samples grow slower than the square root of the number of training samples and also give the optimal growth rate of the number of representative samples. We redo the analysis for decision tree (DT) classifiers and compare them with Vnets. The bias/variance dilemma and the curse of dimensionality with respect to Vnets and DTs are also discussed.

This paper proposes a backpropagation-based feedforward neural network for learning probability distributions of outputs conditioned on inputs using incoming input-output samples only. The backpropagation procedure is shown to locally minimize the Kullback-Leibler measure in an expected sense. The procedure is enhanced to facilitate boundedness of weights and exploration of the search space to reach a global minimum. Weak convergence theory is employed to show that the longterm behavior of the resulting algorithm can be approximated by that of a stochastic differential equation, whose invariant distributions are concentrated around the global minima of the Kullback-Leibler measure within a region of interest. Simulation studies on problems involving samples arriving from a mixture of labeled densities and the well-known Iris data problem demonstrate the speed and accuracy of the proposed procedure.

Parallel algorithms are presented for modules of learning automata with the objective of improving their speed of convergence without compromising accuracy. A general procedure suitable for parallelizing a large class of sequential learning algorithms on a shared memory system is proposed. Results are derived to show the quantitative improvements in speed obtainable using parallelization. The efficacy of the procedure is demonstrated by simulation studies on algorithms for common payoff games, parametrized learning automata and pattern classification problems with noisy classification of training samples.

Studies the global asymptotic stability of a class of fuzzy systems. It demonstrates the equivalence of stability properties of fuzzy systems and linear time invariant (LTI) switching systems. A necessary and sufficient condition for the stability of such systems are given, and it is shown that under the sufficient condition, a common Lyapunov function exists for the LTI subsystems. A particular case when the system matrices can be simultaneously transformed to normal matrices is shown to correspond to the existence of a common quadratic Lyapunov function. A constructive procedure to check the possibility of simultaneous transformation to normal matrices is provided.

This paper analyzes the long-term behavior of the REINFORCE and related algorithms (Williams 1986, 1988, 1992) for generalized learning automata (Narendra and Thathachar 1989) for the associative reinforcement learning problem (Barto and Anandan 1985). The learning system considered here is a feedforward connectionist network of generalized learning automata units. We show that REINFORCE is a gradient ascent algorithm but can exhibit unbounded behavior. A modified version of this algorithm, based on constrained optimization techniques, is suggested to overcome this disadvantage. The modified algorithm is shown to exhibit local optimization properties. A global version of the algorithm, based on constant temperature heat bath techniques, is also described and shown to converge to the global maximum. All algorithms are analyzed using weak convergence techniques.

A feedforward network composed of units of teams of parameterized learning automata is considered as a model of a reinforcement learning system. The internal state vector of each learning automaton is updated using an algorithm consisting of a gradient-following term and a random perturbation term. It is shown that the algorithm weakly converges to a solution of the Langevin equation, implying that the algorithm globally maximizes an appropriate function. The algorithm is decentralized, and the units do not have any information exchange during updating. Simulation results on common payoff games and pattern recognition problems show that reasonable rates of convergence can be obtained.

Learning algorithms for feedforward connectionist systems in a reinforcement learning environment are developed and analyzed in this paper. The connectionist system is made of units of groups of learning automata. The learning algorithm used is the L/sub R-I/ and the asymptotic behavior of this algorithm is approximated by an ordinary differential equation (ODE) for low values of the learning parameter. This is done using weak convergence techniques. The reinforcement learning model is used to pose the goal of the system as a constrained optimization problem. It is shown that the ODE, and hence the algorithm exhibits local convergence properties, converging to local solutions of the related optimization problem. The three layer pattern recognition network is used as an example to show that the system does behave as predicted and reasonable rates of convergence are obtained. Simulations also show that the algorithm is robust to noise.>

A parallel stochastic algorithm for relaxation labeling is analyzed. For the case of symmetric compatibility functions, it is proved that time algorithm will always converge to a consistent labeling.>

A multi-person discrete game where the payoff after each play is stochastic is considered. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A learning algorithm for the game based on a decentralized team of learning automata is presented. It is proved that all stable stationary points of the algorithm are Nash equilibria for the game. Two special cases of the game are also discussed, namely, game with common payoff and the relaxation labelling problem. The former has applications such as pattern recognition and the latter is a problem widely studied in computer vision. For the two special cases it is shown that the algorithm always converges to a desirable solution.>

A cooperative-game-playing learning automata model is presented for a complex nonlinear associative task, namely, learning of Boolean functions. The unknown Boolean function is expressed in terms of minterms, and a team of automata is used to learn the minterms present in the expansion. Only noisy outputs of the Boolean function are assumed to be available for the team of automata that use a variation of the rapidly converging estimator learning algorithm called the pursuit algorithm. A divide-and-conquer approach is proposed to overcome the storage and computational problems of the pursuit algorithm. Extensive simulation experiments have been carried out for six-input Boolean tasks. The main advantages offered by the model are generality, proof of convergence, and fast learning.>

The problem of learning correct decision rules to minimize the probability of misclassification is a long-standing problem of supervised learning in pattern recognition. The problem of learning such optimal discriminant functions is considered for the class of problems where the statistical properties of the pattern classes are completely unknown. The problem is posed as a game with common payoff played by a team of mutually cooperating learning automata. This essentially results in a probabilistic search through the space of classifiers. The approach is inherently capable of learning discriminant functions that are nonlinear in their parameters also. A learning algorithm is presented for the team and convergence is established. It is proved that the team can obtain the optimal classifier to an arbitrary approximation. Simulation results with a few examples are presented where the team learns the optimal classifier.

Relaxation labeling processes are a class of mechanisms that solve the problem of assigning labels to objects in a manner that is consistent with respect to some domain-specific constraints. We reformulate this using the model of a team of learning automata interacting with an environment or a high-level critic that gives noisy responses as to the consistency of a tentative labeling selected by the automata. This results in an iterative linear algorithm that is itself probabilistic. Using an explicit definition of consistency we give a complete analysis of this probabilistic relaxation process using weak convergence results for stochastic algorithms. Our model can accommodate a range of uncertainties in the compatibility functions. We prove a local convergence result and show that the point of convergence depends both on the initial labeling and the constraints. The algorithm is implementable in a highly parallel fashion.

A new class of reinforcement schemes for learning automata that makes use of estimates of the random characteristics of the environment is introduced. Both a single automaton and a hierarchy of learning automata are considered. It is shown that under small values for the parameters, these algorithms converge in probability to the optimal choice of actions. By simulation it is observed that, for both cases, these algorithms converge quite rapidly. Finally, the generality of this method of designing learning schemes is pointed out, and it is shown that a very minor modification will enable the algorithm to learn in a multiteacher environment as well.

Learning automata which update their action probabilities on the basis of the responses they get from an environment are considered. The automata update the probabilities whether the environment responds with a reward or a penalty. An automation is said to possess ergodicity of the mean (EM) if the mean action probability is the total state probability of an ergodic Markov chain. The only known EM algorithm is the linear reward-penalty (LRP) scheme. For the two-action case, necessary and sufficient conditions have been derived for nonlinear updating schemes to be EM. The method of controlling the rate of convergence of this scheme is presented. In particular, a generalized linear algorithm has been proposed which is superior to the LRPscheme. The expression for the variance of the limiting action probabilities of this scheme is derived.

Two new models of nonstationary random environments whose response characteristics depend on the actios performed on them are intoduced in this paper. The models appear interesting because no one action is optimal and all the actions have to be chosen successively. A preliminary analysis of a linear learning automaton acting in such environments is presented, and certain mathematical questions of convergence which arise are brought to light. The analysis reveals that the automaton tends to equalize the penalty probabilities. Simulation studies of the abstract models as well as the routing of calls in telephone networks appear to reinforce the analytical results and the relevance of such models.

A class of nonlinear learning algorithms for the Q-and S-model stochastic automaton-random environment setup are described. Necessary and sufficient conditions for absolute expediency of these algorithms are derived. Various algorithms that are so far reported in literature can be obtained as special cases of the general algorithm given in this correspondence.

A hypothesis is proposed that predicts regions where fixations are most likely to occur on a visual pattern viewed by a human test subject. A scheme is developed for evaluating a fixation probability density function for any given pattern, based on an assumed fixation probability density function for a pattern consisting of a single dot. Predictions of the hypothesis agree with experimental data available in the literature. When the hypothesis is used in conjunction with some assumptions, it also provides interpretations for some well-known geometrical illusions, such as the Muller-Lyer illusion. It is hoped that a study of this kind will aid in understanding some aspects of the mechanisms subserving human visual pattern recognition.

Stochastic automata operating in an unknown random environment have been proposed earlier as models of learning. These automata update their action probabilities in accordance with the inputs received from the environment and can improve their own performance during operation. In this context they are referred to as learning automata. A survey of the available results in the area of learning automata has been attempted in this paper. Attention has been focused on the norms of behavior of learning automata, issues in the design of updating schemes, convergence of the action probabilities, and interaction of several automata. Utilization of learning automata in parameter optimization and hypothesis testing is discussed, and potential areas of application are suggested.

A nonparametric training procedure capable of processing an arbitrary sequence of patterns based on stochastic approximation techniques is considered. An acceleration scheme based on the adaptive Robbins-Monro procedure to increase the rate of convergence and to make the estimation asymptotically efficient is proposed. This scheme has been applied to the problem of recognition of handwritten characters.