Adaptivity, Structure, and Objectives in Sequential Decision-Making

Sequential decision-making algorithms are ubiquitous in the design and optimization of large-scale systems due to their practical impact, leading to a renaissance of incorporating machine learning for decision-making. This widespread societal adoption includes improving data centers with machine-learned advice and managing supply chain optimization for mobile food pantry services. The typical algorithmic paradigm ignores the sequential notion of these problems: use a historical dataset to predict future uncertainty and solve the resulting offline planning problem. Reinforcement learning (RL) provides a more natural highfidelity model for these systems, giving theoretical tools for the design and analysis of an algorithm’s performance. These algorithms have seen historical success, but mainly in the context of large-scale game playing and robotics with tabula rasa algorithms. The fundamental gap in their adoption and performance in operations management domains is theoretically understanding how algorithms adapt to additional structure observed in these problems by improving over min-max bounds, incorporating domain-specific constraints, and adjusting to multi-criteria objectives.In this thesis, we will develop machine learning algorithms for data-driven sequential decision making in the framework of RL, with applications to social good, societal systems, and operations management. We will consider designing methods for sequential decision-making (bandits, reinforcement learning) that leverage auxiliary data sources (imitation learning, exogenous datasets, geometric assumptions). We will specialize this framework to areas including nonparametric RL algorithms for memory management and metrical task systems, fair resource allocation, and data-driven algorithm design for bin packing with applications in cloud computing. Central to this, we will additionally discuss our open-source code instrumentation and methodology to analyze the multi-criteria performance of algorithms on these problems.To summarize, we will outline an approach toProvide techniques to scale reinforcement learning algorithms to societal systems through three lenses: adaptivity, structure, and objectives.In more detail, this thesis will be separated into three distinct parts each focused on considering the following questions: (1) Adaptivity: How can we design algorithms which optimally exploit geometry in the data to provide enhanced performance and reduce run-time and storage complexity? (2) Structure: What additional structure and constraints, either on the operational behavior of the algorithm or on the system, lead to provably improved domain-specific algorithms?(3) Objectives: How can we characterize and attain the Pareto frontier of tradeoffs between the multi-criteria objectives in sequential decision-making problems?