Regular Transformations in Sequential Optimization & Reinforcement Learning

Abstract

Sequential optimization is a subfield of mathematical optimization---lying at the confluence of decision theory, operations research, game theory, artificial intelligence, and stochastic control---that focuses on problems involving notions of time and temporal dependence. Such problems center around an optimizing agent who exists within some larger environment and is assigned the task of obtaining a strategy for interacting with the environment in a manner that is optimal with respect to some underlying evaluation criteria. The canonical problem of interest in this area is that of finding a policy that maximize an expected payoff from a sequence of rewards generated by repeated interaction in Markov decision processes.

Regularity describes a wide-ranging notion of tractability from the study of formal languages and automata theory, which is exemplified by the family of regular languages. Due to a combination of convenient representability---as e.g. finite automata & regular expressions---and amenability to algorithmic methods, regular languages have long enjoyed adoption as modeling tools across a variety of disciplines within computer science including formal methods, natural language processing, software engineering, and more. Recently, regular languages have found significant roles in novel approaches to problems from sequential optimization related to non-Markovian dynamics and high-level logical objectives.

This dissertation focuses on extending the line of research at the intersection of formal languages and sequential optimization, starting with a generalization of regularity. We propose an abstract form of regularity that emphasizes a relational perspective and gives prominence to transformations of regular languages. After identifying a few types of transformations that are regular in this new sense, we explore their utility as modeling tools across a variety of aspects of sequential optimization. Our investigation yields a number of promising outcomes that include (1) advancements to existing approaches that leverage regularity towards optimization in challenging types of environments such as those with non-Markovian dynamics and those with infinite state spaces, (2) original research directions stemming from the introduction of novel optimization objectives, and (3) insights around paths and obstacles to further applications of regular transformations in sequential optimization. This thesis presents both contributions to sequential optimization that are obtained through the use of regular transformations and contributions to the theory of regular transformations that should facilitate further applications of regularity in optimization.