In today's rapidly evolving technological landscape, the development and advancement of computational tools and algorithms have become paramount across a wide range of research fields. This holds particularly true in various domains of computational mathematics, encompassing areas such as machine learning, optimization, and algorithmic game theory. The computational tools serve as essential enablers, empowering researchers and practitioners by facilitating efficient modeling, analysis, and prediction. Algorithms are essential components of computational tools, which provide instructions for data processing, pattern recognition, and decision-making.

This dissertation focuses on developing computational tools and algorithms for specific applications in the interconnected fields of optimization, machine learning (ML), and mean-field games (MFGs). First, to address the absence of a comprehensive computational tool for MFGs, we present MFGLib, an open-source Python library designed to provide a user-friendly and customizable interface for solving Nash equilibria in generic MFGs. Second, we demonstrate that the search for Nash equilibria in MFGs and various ML problems can be formulated as non-convex optimization problems, where the presence of saddle points significantly impedes the effectiveness of gradient descent algorithm and its variants. To help optimization algorithms escape saddle points efficiently, we introduce a novel perturbation mechanism based on the dynamics of vertex-repelling random walk. This leads to the development of two new algorithms, perturbed gradient descent adapted to occupation time (PGDOT) and its accelerated version (PAGDOT). Theoretical guarantees for these algorithms are established, and through extensive numerical experiments, we showcase their superiority over several state-of-the-art optimization methods. Last, we explore a relatively independent machine learning task---detecting overutilization and fraud in healthcare. We focus on developing an ensemble model based on Stacked Generalization (stacking) to detect overutilization in Medicare within the field of Ophthalmology. Our results highlight the superiority of the stacking ensemble model over traditional ML models in accurately distinguishing overutilizing ophthalmologists from non-fraudulent ones.

This paper builds a new theoretical connection between singular control of finite variation and optimal switching problems. This correspondence provides a novel method for solving high-dimensional singular control problems, and enables us to extend the theory of reversible investment: sufficient conditions are derived for the existence of optimal controls and for the regularity of value functions. Consequently, our regularity result links singular controls and Dynkin games through sequential optimal stopping problems.

Medical image is an important information source to understand the patient’s condition. As a result, interpreting the medical images is a critical part of the clinical procedure. However, physicians’ visual evaluation of medical images in clinics has a few challenges such as the limited human resources, the unavailability of appropriate experts, the increasing number ofmedical images, and so on.

Deep learning is a subarea of machine learning that uses deep neural networks to learn the patterns behind the given data set. Deep learning showed excellent performances in image analysis problems including medical image analysis. In this dissertation, I propose and evaluate new methods for evaluating the images of three different vision problems inophthalmology.

The first problem is the early detection of retinopathy of prematurity (ROP). ROP is a leading cause of childhood blindness globally, and early detection is a key to preventing ROP to progress to severe conditions. We developed two convolutional neural networks with different depths. The deeper model showed an excellent performance including bettermetrics than an experienced human expert.

The second problem is about transfer learning in retinal vascular diseases. We propose a transfer learning method that uses the detection of a well-studied retinal vascular disease as a source problem and uses the knowledge to the detection of an under-studied retinal vascular disease. Our proposed method showed better performance with more robustness tothe stochasticity in the training process and the reduction of sample size.

The final problem is to predict the treatment response to a drug from the baseline characteristics. Both symbolic features like clinical measurements and medical images are considered for the modeling. To merge the two types of input, we proposed two approaches. The results showed the potential of the proposed method to the problem.

Deep learning is successfully applied to three medical image analysis problems in ophthalmology in this dissertation. These results offer key evidence for further development of deep learning-based medical image analysis systems in the future.

The optimal placement problem studies how to optimally place orders in a limit order book to purchase/sell a fixed number of shares of a stock. Under a correlated random walk model with mean-reversion for the best ask/bid price, optimal placement strategies for both single-step and multi-step cases are derived in this thesis. In the single-step case, the optimal strategy involves only the market order, the best bid, and the second best bid. In the multi-step case, the optimal strategy is of a threshold type. Critical to the analysis is a generalized reflection principle for correlated random walks.

Furthermore, a simple linear price impact model is also presented, which gives insight into the price impact of executing large orders on placement decisions.

The availability of detailed limit order book information enables more accurate estimation of the order execution probability and price dynamics. Motivated by various optimization problems and models in algorithmic trading, a limiting behavior for order positions and related best bid/ask queues in a limit order book is studied in this thesis. In addition to the fluid and diffusion limits for the processes, fluctuations of the order position and related queues around their fluid limit are analyzed. As a corollary, explicit analytical expressions for various quantities of interests in a limit order book are derived.

Stochastic games with large populations are notoriously difficult to solve due to their intractability and dimensionality. How to analyze game strategies under full information and how to design efficient learning algorithms under partial or no information are among the key questions that need to be answered in order to better understanding such complex stochastic systems.

In this thesis, we provide some attempts to tackle these two questions.

First, we formulate and analyze an $N$-player stochastic game of the classical fuel follower problem and its mean field game (MFG) counterpart. For the $N$-player game, we obtain the Nash equilibrium (NE) explicitly by deriving and analyzing a system of Hamilton--Jacobi Bellman (HJB) equations and by establishing the existence of a unique strong solution to the associated Skorokhod problem on an unbounded polyhedron with an oblique reflection. For the MFG, we derive a bang-bang type NE under some mild technical conditions and by the viscosity solution approach. We also show that this solution is an $\epsilon$-NE to the $N$-player game,

with $\epsilon= O\left(\sqrt{\frac{{1}}{{{N}}}}\right)$. The $N$-player game and the MFG differ in that the NE for the former is state-dependent while the NE for the latter is a threshold-type bang-bang policy where the threshold is state-independent. Our analysis shows that the NE for a stationary MFG may not be the NE for the corresponding MFG.

Second, we propose a class of stochastic $N$-player games and discuss its connection to the free boundary problems, where both the associated fully nonlinear partial differential equations (PDEs) and the boundaries separating the action and waiting regions are integral parts of the problems. We show how ``moving'' boundaries come into play due to the game nature, which distinguishes our results from the existing single-agent literature. We present explicit NE by solving a sequence of Skorokhod problems. For the special case of resource allocation problems, we show how players change their strategies based on different network structures among players and resources, with insights from a sharing economy perspective.

Third, we analyze the Pareto optimality (PO) solution for a class of $N$-player collaborative games. This is achieved by connecting the collaborative game with an auxiliary central controller problem. The main contributions to solving the auxiliary central controller problem are two-fold. First, we show the regularity $\mathcal{W}^{2,\infty}(\mathbb{R}^N)$ of the central controller's value function, which is the unique solution to a high-dimensional HJB equation with complex gradient constraints. Second we show the optimal strategy is a sequence of Skorokhod problems, where the regularity of the boundary is $\mathcal{W}^{1,\infty}(\mathbb{R}^N)$. With some properties of the PO solution, we then provide an upper bound on the Price of Anarchy (PoA) of this game, which bridges the set of NEs and the PO solution. Some insights are also discussed when $N=2$, with explicit solutions and exact PoA values.

Fourth, motivated by the advertisement auction problem for online advertisements, we consider the general problem of simultaneous learning and decision-making in a stochastic game setting with a large population. We formulate this type of game with unknown rewards and dynamics as a generalized mean field game (GMFG), incorporating action distributions. We first analyze the existence of the solution to this GMFG and show that naively combining Q-learning with the three-step fixed-point approach in classical MFGs yields unstable algorithms. We then propose an alternating approximating Q-learning algorithm and establish its convergence property and complexity result. The numerical performance of this new algorithm on the repeated Ad auction problem shows superior computational efficiency.

Studies of stock market crashes are as sparse as the occurrence of

crashes. The mainstream theoretical models on stock market crashes are rooted in rational

expectations equilibrium models and classical

market microstructure models. Compared to theoretical works, there are

even fewer works done on the empirical side. This is because most of

the theoretical models do not provide straightforward tests against

empirical data. Secondly, the relatively small

sample size (rare occurrence) of stock market crashes is always an obstacle for

empirical testing.

In this dissertation, we build a strategic trading model to link two major US stock market

crashes: the 1987 crash and the 2010 Flash Crash. We then provide

cross-sectional empirical evidence to verify our model hypothesis and evaluate price impact due

to the information asymmetry effect and the limited risk-bearing capacity effect. We use statistical learning

methods to compare our model based predictors with other predictors

for the maximum cross-sectional price drawdown of SP500 stocks during the 2010 Flash Crash and

check the robustness of our

findings.

This paper analyzes a class of singular control problems for which value functions are not necessarily smooth. Necessary and su±cient conditions for the well-known smooth ¯t principle, along with the regularity of the value functions, are given. Explicit solutions for the optimal policy and for the value functions are provided. In particular, when payo® functions satisfy the usual Inada conditions, the boundaries between action and no-action regions are smooth and strictly monotonic as postulated and exploited in the existing literature (Dixit and Pindyck (1994); Davis, Dempster, Sethi, and Vermes(1987); Kobila (1993); Abel and Eberly (1997); Âksendal (2000); Scheinkman and Zariphopoulou (2001); Merhi and Zervos (2007); Alvarez (2006)). Illustrative examples for both smooth and non-smooth cases are discussed, to highlight the pitfall of solving singular control problems with a priori smoothness assumptions.

In recent years, there has been an ever-increasing demand for building reliable and versatile agents in applications arising from numerous fields including autonomous driving, supply chain, manufacturing, e-commerce and finance. To meet these challenging demands, researches in decision making systems have drawn upon a wide range of tools from applied probability, reinforcement learning (RL), stochastic control and game theory. This dissertation focuses on developing new methodologies and efficient algorithms with provable performance guarantees to deal with complex environments such as large population competitions and continuous-time systems.

The first part of this dissertation focuses on designing and analyzing RL algorithms for large population games. Large population games have appeared in many real-world problems. Examples include massive multiplayer online role-playing games, high frequency trading, and the sharing economy. However, in general, it becomes increasingly difficult to solve such problems as the number of players in the game grows. Mean field game (MFG) provides an ingenious and tractable aggregation approach to approximate the otherwise challenging N-player stochastic games. In Chapter 1, we present a general mean-field game (GMFG) framework for simultaneous learning and decision-making in stochastic games with a large population. It first establishes the existence of a unique Nash Equilibrium to this GMFG, and demonstrates that naively combining reinforcement learning with the fixed-point approach in classical MFGs yields unstable algorithms. It then proposes value-based and policy-based reinforcement learning algorithms (GMF-V and GMF-P, respectively) with smoothed policies, with analysis of their convergence properties and computational complexities. Experiments on an equilibrium product pricing problem demonstrate that GMF-V-Q and GMF-P-TRPO, two specific instantiations of GMF-V and GMF-P, respectively, with Q-learning and TRPO, are both efficient and robust in the GMFG setting. Moreover, their performance is superior in convergence speed, accuracy, and stability when compared with existing algorithms for multi-agent reinforcement learning in the $N$-player setting.

The second part of this dissertation focuses on designing and analyzing RL algorithms for continuous-time stochastic dynamical systems. As most physical systems in science and engineering evolve continuously in time, many real-world control tasks, such as those in aerospace, automotive industry and robotics, are naturally formulated in terms ofcontinuous-time dynamical systems. Nevertheless, the mainstream RL algorithms have been designed for discrete-time systems, despite that they are widely applied to physical tasks in continuous-time systems. Continuous-time RL algorithms have also been developed in the past decades. But the theoretical guarantees of these works are limited to the asymptotic convergence and the non-asymptotic guarantees remain unknown. In Chapter 2, we take the first step towards designing algorithms with non-asymptotic guarantees for solving finite-time-horizon continuous-time linear quadratic (LQ) RL problems in an episodic setting, where both the state and control coefficients are unknown to the controller. We first propose a least-squares algorithm based on continuous-time observations and controls, and establish a logarithmic regret bound of magnitude $O((\ln M)(\ln\ln M))$, with $M$ being the number of learning episodes. The analysis consists of two components: perturbation analysis, which exploits the regularity and robustness of the associated Riccati differential equation; and parameter estimation error, which relies on sub-exponential properties of continuous-time least-squares estimators. We further propose a practically implementable least-squares algorithm based on discrete-time observations and piecewise constant controls, which achieves similar logarithmic regret with an additional term depending explicitly on the time stepsizes used in the algorithm. In Chapter 3, we extend the results beyond linear-quadratic problems, where the unknown linear jump-diffusion process is controlled subject to non-smooth convex costs. We show that the associated linear-convex (LC) control problems admit Lipchitz continuous optimal feedback controls and further prove the Lipschitz stability of the feedback controls. The analysis relies on a stability analysis of the associated forward-backward stochastic differential equation. We then propose a least-squares algorithm which achieves a regret of the order $O(\sqrt{N\ln N})$ on linear-convex learning problems with jumps, where $N$ is the number of learning episodes; the analysis leverages the Lipschitz stability of feedback controls and concentration properties of sub-Weibull random variables. Numerical experiment confirms the convergence and the robustness of the proposed algorithm.

The theory of mean-field games (MFGs) belongs to a branch of game theory that studies a large population of (weakly) interacting players. It serves as an analytically feasible framework to approximate stochastic differential games when the number of players is large and detailed characterization of the interactions is computationally expensive. As an effective modeling tool, the theory of MFGs attracts the attention of a variety of application fields in economics, finance and engineering. On the computation front, the development of machine learning provides abundant computational methods of solving for MFGs, which is remarkably meaningful in practice. At the same time, people may also wonder if the theory of MFGs, or stochastic analysis in general, could benefit the machine learning community.

This thesis starts with two MFG models, with singular and impulse types of controls, respectively. Theses two control types allow certain degrees of discontinuity, making them better mathematical models compared with regular controls where the interventions must be absolute continuous. However, due to the theoretical challenges brought by the discontinuous nature of the controls, these two models are less explored in existing literature compared with MFGs with regular controls. Both models are motivated by real-world problems. Explicit solutions to the MFGs are presented and shown to approximate Nash equilibria of the corresponding N-player games with an error of the order O(1⁄√N). Further analysis of the solutions reveals the game effect from interacting with the mean-field.

Obtaining analytical solutions of MFGs is difficult in general. The thesis then turns to the computation side of MFGs and establish the connection with generative adversarial networks, a celebrated deep learning tool that enjoys tremendous empirical success since its introduction to the machine learning community. It first shows a conceptual connection between GANs and MFGs: MFGs have the structure of GANs, and GANs are MFGs under the Pareto Optimality criterion. Interpreting MFGs as GANs, on one hand, enables a GANs-based algorithm (MFGANs) to solve MFGs: one neural network (NN) for the backward HJB equation and one NN for the forward FP equation, with the two NNs trained in an adversarial way. Viewing GANs as MFGs, on the other hand, reveals a new and probabilistic aspect of GANs. This new perspective, moreover, leads to an analytical connection between GANs and Optimal Transport (OT) problems, and sufficient conditions for the minimax games of GANs to be reformulated in the framework of OT. Numerical experiments demonstrate superior performance of this proposed algorithm, especially in higher dimensional case, when compared with existing NN approaches.

Finally, the thesis explores the possibility of enriching the theoretical understanding of the training of GANs from the perspective of stochastic analysis. It establishes approximations, with precise error bound analysis, for the training of GANs under stochastic gradient algorithms (SGAs). The approximations are in the form of coupled stochastic differential equations (SDEs). The analysis of the SDEs and the associated invariant measures yields conditions for the stability and the convergence of GANs training. Further analysis of the invariant measure for the coupled SDEs gives rise to a fluctuation-dissipation relations (FDRs) for GANs, revealing the trade-off of the loss landscape between the generator and the discriminator and providing guidance for learning rate scheduling.