Efficient Algorithms for High-Dimensional Data-Driven Sequential Decision-Making
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
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.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
Publisher
Keywords
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Dai, Jim
Banerjee, Sid
Henderson, Shane G.