2026-09-19T10:17:39Zhttps://ecommons.cornell.edu/server/oai/request

oai:ecommons.cornell.edu:1813/1097262026-05-15T19:48:30Zcom_1813_35col_1813_47

Chen, Yilun Goldberg, David Alan Kleinberg, Robert David Dai, Jim Banerjee, Sid Henderson, Shane G. 2021-09-09T17:40:40Z 2021-09-09T17:40:40Z 2021-05 ProQuest Submission ID: 12534 ProQuest Publication ID: 28494367 https://hdl.handle.net/1813/109726 https://doi.org/10.7298/pp4z-nn30 15049392 218 pages The general framework of sequential decision-making captures various important real-world applications ranging from pricing, inventory control to public healthcare and pandemic management. It is central to operations research/operations management, often boiling down to solving stochastic dynamic programs (DP). The ongoing big data revolution allows decision makers to incorporate relevant data in their decision-making processes, which in many cases leads to significant performance upgrade/revenue increase. However, such data-driven decision-making also poses fundamental computational challenges, because they generally demand large-scale, more realistic and flexible (thus complicated) models. As a result, the associated DPs become computationally intractable due to curse of dimensionality issues. We overcome this computational obstacle for three specific sequential decision-making problems, each subject to a distinct \textit{combinatorial constraint} on its decisions: optimal stopping, sequential decision-making with limited moves and online bipartite max weight independent set. Assuming sample access to the underlying model (analogous to a \textit{generative model} in reinforcement learning), our algorithm can output epsilon-optimal solutions (policies/approximate optimal values) for any fixed error tolerance epsilon with computational and sample complexity both scaling polynomially in the time horizon, and essentially independent of the underlying dimension. Our results prove for the first time the fundamental tractability of certain sequential decision-making problems with combinatorial structures (including the notoriously challenging high-dimensional optimal stopping), and our approach may potentially bring forth efficient algorithms with provable performance guarantee in more sequential decision-making settings. en Efficient Algorithms for High-Dimensional Data-Driven Sequential Decision-Making dissertation or thesis https://newcatalog.library.cornell.edu/catalog/15049392 application/pdf Operations Research and Information Engineering Cornell University Doctor of Philosophy Ph. D., Operations Research and Information Engineering https://hdl.handle.net/1813/59810 Publication Cornell Theses and Dissertations Chen, Yilun 5893a6ea-7af3-41d7-abc6-04bcd26ab5df open.access open.access <Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="02e89291-508e-4772-80af-266e5c591651"> <Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>Efficient Algorithms for High-Dimensional Data-Driven Sequential Decision-Making</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2021-05</PublicationDate> <DOI>https://doi.org/10.7298/pp4z-nn30</DOI> <Authors> <Author> <DisplayName>Chen, Yilun</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Abstract>The general framework of sequential decision-making captures various important real-world applications ranging from pricing, inventory control to public healthcare and pandemic management. It is central to operations research/operations management, often boiling down to solving stochastic dynamic programs (DP). The ongoing big data revolution allows decision makers to incorporate relevant data in their decision-making processes, which in many cases leads to significant performance upgrade/revenue increase. However, such data-driven decision-making also poses fundamental computational challenges, because they generally demand large-scale, more realistic and flexible (thus complicated) models. As a result, the associated DPs become computationally intractable due to curse of dimensionality issues. We overcome this computational obstacle for three specific sequential decision-making problems, each subject to a distinct \textit{combinatorial constraint} on its decisions: optimal stopping, sequential decision-making with limited moves and online bipartite max weight independent set. Assuming sample access to the underlying model (analogous to a \textit{generative model} in reinforcement learning), our algorithm can output epsilon-optimal solutions (policies/approximate optimal values) for any fixed error tolerance epsilon with computational and sample complexity both scaling polynomially in the time horizon, and essentially independent of the underlying dimension. Our results prove for the first time the fundamental tractability of certain sequential decision-making problems with combinatorial structures (including the notoriously challenging high-dimensional optimal stopping), and our approach may potentially bring forth efficient algorithms with provable performance guarantee in more sequential decision-making settings.</Abstract> <Access xmlns="http://purl.org/coar/access_right" > </Access> </Publication>