Design and analysis of novel fixed structure stochastic automata in non-stationary environments

Over the past four decades, the study of learning automata has taken a center-stage in the field of machine learning. A variety of frameworks have been set up for the design of such learning automata. In general, a learning automaton selects an action from a group of available actions, and then gets rewarded or penalized by the environment. Provided that the reward/penalty from the environment is only weakly related to the action selected, a learning automaton represents a suitable strategy to maximize the possibility of reward over multiple trials. Since such action selection scenarios are prevalent in various real-life situations, such as in network routing, image compression, and queuing systems, theoretical research in this field has acquired further significance in recent years. In this dissertation, I present one such learning automaton, the Probabilistically-Switch-Action-on-Failure (PSAF) learning automaton. The learning automaton is characterized by a fan-shaped state transition diagram. Each branch of the automaton contains a queue of D states associated with a particular action. The state in each queue closest to the center of the fan-shaped structure (i.e. initial state) belongs to a circle of such initial states. The PSAF automaton is a fixed structure stochastic automaton (FSSA) that can switch from its active state in any queue to the initial state of the next queue in the circle, on each failure, with some finite probability. Since the action-switching probability, as well as state-switching probability in case of penalty, can be selected in multiple ways, the PSAF becomes a framework for developing different FSSA.; In this dissertation, I present the analytical results describing the optimality properties of the PSAF automaton. I further analyze its behavior in non-stationary environments, and compare its performance with the performance of classical FSSA. Non-stationary environments selected for analysis include ones with sinusoidally varying penalty probabilities, as well as environments with periodic switching of penalty probabilities. Finally, I present an implementation of the PSAF learning automaton as a permission switching protocol in an ad hoc wireless networking environment, and show how its performance is better than permission switching protocols developed using canonical FSSA.