EXPLOITING MODEL SMOOTHNESS IN DYNAMIC DECISIONS

184 pagesUtilizing structure in mathematical modeling is instrumental for better model de- sign, creation, and solution. In this dissertation, we explore smoothness-based structure for problems, specifically involving decisions in uncertain environments, in different stages of the modeling process. What we offer in each case is a new framework to approach the question, as well as improvements in either algorithmic effectiveness or theoretical guarantees. First, we consider repeated decision problems under stochastic environments as modeled by Markov Decision Processes (MDPs), where one aims to minimize in- finite horizon cumulative discounted value. The standard Dynamic Programming (DP) approaches suffer from the curse-of-dimensionality, while existing approxima- tion methods often rely on ad-hoc decisions and lack informative guarantees. We develop an approximation framework that is efficient, while also guided by theory and with proven guarantees. State aggregation, where the problem is transformed to a smaller state space, is our approximation vehicle, which is then related to the original problem through their mutual connection to a Partial Differential Equa- tion (PDE). The smoothness of the primitives enables the PDE analysis, which in turn guides the design of the approximation and provides guarantee on the per- formance, even when the problem is transformed to a state space on the order of square root of the original size. Next, we consider the same stochastic environment but where dynamics must be learned from interactions, in a model-based Reinforcement Learning (RL) setting. Specifically, the goal is to evaluate the value of a Markov Reward Process (MRP), with transition probabilities estimated empirically via a generative sam- pling regime. We draw on the same connection to PDE to focus the learning onto the transition moments, and provide sample complexity guarantees that bounds the high probability accuracy gap for a given number of samples. The guarantees we provide complement previous studies especially in small sample regime that was previously uncovered. Lastly, we consider the application of sequential online recommender systems, where the goal is to suggest next-items that a user might be interested in, based on interaction histories. It has long been recognized that users may not always want items highly similar to recent interactions. We propose new measurements to quantify the level of spread in a user’s most recent window of interacted items, and further characterizes the change in this interest spread over timesteps to discover trends in user intention. We demonstrate the informativeness of these measure- ments with e-commerce data, and show improvements in proof-of-concept examples for next-item recommendation as well as next-action prediction