SNAPP Seminar || David Goldberg (Cornell University) || March 17, 2025

Speaker: David Goldberg (Cornell University)

Title: PTAS for Network Revenue Management with General Correlations and Long Horizon

Abstract: There has been a growing interest in studying online decision-making problems such as NRM under more general correlation structures, motivated by the complex data sets, generative models, and high-variance phenomena driving modern applications. Although there has been interesting recent progress on our understanding of such NRM models, these works either posit a particular structure for the possible correlations, or have a complexity scaling with the number of Markovian “states of the world" driving the correlations (which may be exponentially large in complex models).

We make progress on both these fronts by showing that the NRM problem (suitably normalized) has an additive Polynomial Time Approximation Scheme (with runtime independent of the number of “states of the world", and scaling at worst polynomially in the time horizon and other relevant parameters) under a completely general model of correlations, assuming access to a natural Monte Carlo simulator for the demand dynamics, and that the maximum number of resources used by a product is uniformly bounded.

Our result follows by observing that NRM may be viewed as a multistage stochastic integer program, just like optimal stopping, and showing that the phenomena recently proven by Chen and Goldberg regarding existence of a PTAS for optimal stopping extends to a much broader family of multistage stochastic problems. At the heart of this extension is a new way to conceptualize and implement stochastic (sub)gradient methods ``on-the-fly" for the massive linear programs (on scenario trees) associated with natural relaxations of these problems, based on the simple idea that to implement a policy one needs only compute the relevant values along the sample path presented to you. The poly(1/epsilon) number of iterations of (sub)gradient descent required to achieve epsilon-accurate solutions "translates" to computing (noisy estimates of) nested conditional expectations with poly(1/epsilon) levels of nesting, which can be implemented recursively in polynomial time for any given sample path using the simulator (independent of the size of the overall scenario tree).

In contrast to several past works on PTAS for multi-stage stochastic programs, our methods have a runtime at worst polynomial in the time horizon. Furthermore, when the number of resources is held fixed, the runtime required by our algorithms to make each accept/reject decision can be made essentially independent of the time horizon altogether (by approximating certain sums which appear in subgradients using an extra layer of sampling). In addition, we derive new algorithms and insights for several online combinatorial optimization problems with general correlation structure, as well as for optimal stopping itself. Joint work with Sabri Cetin and Yilun Chen.

Speaker's Bio: David A. Goldberg is an Associate Professor in Cornell's ORIE department. Previously, he was the A. Russell Chandler III Associate Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. He received his Ph.D. in Operations Research at MIT in 2011, and his B.S. in Computer Science (minors in Operations Research and Applied Math) from Columbia University in 2006. Goldberg’s research is in applied probability, on topics including optimal stopping and control, the theory of inventories and queues, and applied Operations Research. His work has been recognized with accolades including an NSF CAREER award, 2019 INFORMS Applied Probability Society Best Publication award, 2019 INFORMS Nicholson Competition first place, 2018 INFORMS Finance Student Paper Competition finalist, 2015 INFORMS Nicholson Competition first place, 2015 INFORMS JFIG Competition second place, and 2014 MSOM and 2010 INFORMS Nicholson Competitions finalist. He is also an associate editor for the journals Stochastic Systems and Stochastic Models, former associate editor of the journals Operations Research and Queueing Systems, and former chair of the INFORMS Applied Probability Society. In addition, Goldberg has recently led an initiative to engage more undergraduates in OR/analytics research at Cornell (while serving as Director for Undergraduate Studies in ORIE), for which he was awarded both the 2023 Sonny Yau ’72 Teaching Award of the College of Engineering and the 2025 Community-Engaged Practice and Innovation Award of the Einhorn Center for Community Engagement.