{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/109726"},"canonical_url":"https://search.dev.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/109726","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Efficient Algorithms for High-Dimensional Data-Driven Sequential Decision-Making","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_html":"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_has_math":false,"creators":["Chen, Yilun"],"institution":"Cornell University","degree_name":"Ph. D., Operations Research and Information Engineering","degree_level":"Doctor of Philosophy","degree_discipline":"Operations Research and Information Engineering","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":["Kleinberg, Robert David","Dai, Jim","Banerjee, Sid","Henderson, Shane G."],"year":2021,"date_issued":"2021-05","date_published":"2021-05","updated_at":"2026-07-24T01:48:58Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/pp4z-nn30"],"render_values":[{"text":"https://doi.org/10.7298/pp4z-nn30","href":"https://doi.org/10.7298/pp4z-nn30","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 12534","ProQuest Publication ID: 28494367"],"render_values":[{"text":"ProQuest Submission ID: 12534","href":null,"code":true},{"text":"ProQuest Publication ID: 28494367","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/1813/109726","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Kleinberg, Robert David","Dai, Jim","Banerjee, Sid","Henderson, Shane G."]},{"key":"dc:creator","label":"Author","values":["Chen, Yilun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-09-09T17:40:40Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-09-09T17:40:40Z"]},{"key":"dc:date.issued","label":"Date","values":["2021-05"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Operations Research and Information Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Operations Research and Information Engineering"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/pp4z-nn30"]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 12534","ProQuest Publication ID: 28494367"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/109726"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["218 pages"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Efficient Algorithms for High-Dimensional Data-Driven Sequential Decision-Making"]}]}],"canonical_facts":{"dc:contributor.committeemember":["Kleinberg, Robert David","Dai, Jim","Banerjee, Sid","Henderson, Shane G."],"dc:creator":["Chen, Yilun"],"dc:date.accessioned":["2021-09-09T17:40:40Z"],"dc:date.available":["2021-09-09T17:40:40Z"],"dc:date.issued":["2021-05"],"dc:description":["218 pages"],"dc:description.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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.doi":["https://doi.org/10.7298/pp4z-nn30"],"dc:identifier.other":["ProQuest Submission ID: 12534","ProQuest Publication ID: 28494367"],"dc:identifier.uri":["https://hdl.handle.net/1813/109726"],"dc:language.iso":["en"],"dc:title":["Efficient Algorithms for High-Dimensional Data-Driven Sequential Decision-Making"],"dc:type":["dissertation or thesis"],"thesis:degree_discipline":["Operations Research and Information Engineering"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Operations Research and Information Engineering"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-07-24T01:48:58Z"}