Predictions and Policy Optimization in Online Decision Making

Citation

Lin, Yiheng (2025) Predictions and Policy Optimization in Online Decision Making. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/37t0-7n77. https://resolver.caltech.edu/CaltechTHESIS:05292025-064811885

Abstract

Predictions are ubiquitous in modern systems, offering insights into how environments might evolve by encoding our prior knowledge and assumptions. Recent advances in artificial intelligence have significantly expanded the scope and accuracy of such models, creating vast new opportunities across domains. At the same time, online decision making remains a fundamental challenge in many real-world problems, concerned with challenges such as limited information, delayed feedback, and irrevocable actions. This dissertation focuses on the interplay between predictions and online decision making---how predictive information can be effectively leveraged to improve performance in dynamic, uncertain environments.

While incorporating predictions often enhances decision-making, the degree of improvement can vary substantially. This variability arises from two key factors. First, the potential benefit of using predictions is fundamentally determined by both the nature of the predictions (e.g., their targets, errors, and distributions) and the characteristics of the decision-making process (e.g., costs and dynamics). Second, standard predictive policies frequently fall short of realizing such potential, especially in changing environments or when critical system parameters are unknown.

This dissertation introduces a unified theoretical framework to quantify the benefit of leveraging predictions across a broad range of online decision-making problems. To close the gap between the maximum potential and achievable performance, we formulate a general policy optimization framework and design efficient algorithms capable of tracking optimal (predictive) policies in time-varying settings. Additionally, we address practical considerations such as scalability and computational efficiency, enabling the application of our methods in large-scale networks and on resource-constrained devices.

Thesis Files