Back to search

Cornell University

EXPLOITING MODEL SMOOTHNESS IN DYNAMIC DECISIONS

Abstract

dc:description.abstract

Utilizing 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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Amy B.Z.
Chair dc:contributor.chair
  • Gurvich, Itai
Committee members dc:contributor.committeemember
  • Artzi, Yoav
  • Topaloglu, Huseyin
  • Frazier, Peter

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Attribution-ShareAlike 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15578913
Dc Identifier Other
ProQuest Submission ID: 13227
ProQuest Publication ID: 29321967

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Amy B.Z.. EXPLOITING MODEL SMOOTHNESS IN DYNAMIC DECISIONS. Doctor of Philosophy thesis, Cornell University, 2022. https://hdl.handle.net/1813/112102