On the Theory and Applications of Hierarchical Learning Automata and Object Migration Automata

Abstract

The paradigm of Artificial Intelligence (AI) and the sub-group of Machine Learning (ML) have attracted exponential interest in our society in recent years. The domain of ML contains numerous methods, and it is desirable (and in one sense, mandatory) that these methods are applicable and valuable to real-life challenges. Learning Automata (LA) is an intriguing and classical direction within ML. In LA, non-human agents can find optimal solutions to various problems through the concept of learning. The LA instances learn through Agent-Environment interactions, where advantageous behavior is rewarded, and disadvantageous behavior is penalized. Consequently, the agent eventually, and hopefully, learns the optimal action from a set of actions. LA has served as a foundation for Reinforcement Learning (RL), and the field of LA has been studied for decades. However, many improvements can still be made to render these algorithms to be even more convenient and effective. In this dissertation, we record our research contributions to the design and applications within the field of LA. Our research includes novel improvements to the domain of hierarchical LA, major advancements to the family of Object Migration Automata (OMA) algorithms, and a novel application of LA, where it was utilized to solve challenges in a mobile radio communication system. More specifically, we introduced the novel Hierarchical Discrete Pursuit Automaton (HDPA), which significantly improved the state of the art in terms of effectiveness for problems with high accuracy requirements, and we mathematically proved its ϵ-optimality. In addition, we proposed the Action Distribution Enhanced (ADE) approach to hierarchical LA schemes which significantly reduced the number of iterations required before the machines reached convergence. The existing schemes in the OMA paradigm, which are able to solve partitioning problems, could only solve problems with equally-sized partitions. Therefore, we proposed two novel methods that could handle unequally-sized partitions. In addition, we rigorously summarized the OMA domain, outlined its potential benefits to society, and listed further development cases for future researchers in the field. With regard to applications, we proposed an OMA-based approach to the grouping and power allocation in Non-orthogonal Multiple Access (NOMA) systems, demonstrating the applicability of the OMA and its advantage in solving fairly complicated stochastic problems. The details of these contributions and their published scientific impacts will be summarized in this dissertation, before we present some of the research contributions in their entirety.