Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • NSF Public Access
  • Search Results
  • A Primal-Dual Approach to Constrained Markov Decision Processes with Applications to Queue Scheduling and Inventory Management
Title: A Primal-Dual Approach to Constrained Markov Decision Processes with Applications to Queue Scheduling and Inventory Management
In many operations management problems, we need to make decisions sequentially to minimize the cost, satisfying certain constraints. One modeling approach to such problems is the constrained Markov decision process (CMDP). In this work, we develop a data-driven primal-dual algorithm to solve CMDPs. Our approach alternatively applies regularized policy iteration to improve the policy and subgradient ascent to maintain the constraints. Under mild regularity conditions, we show that the algorithm converges at rate [Formula: see text], where T is the number of iterations, for both the discounted and long-run average cost formulations. Our algorithm can be easily combined with advanced deep learning techniques to deal with complex large-scale problems with the additional benefit of straightforward convergence analysis. When the CMDP has a weakly coupled structure, our approach can further reduce the computational complexity through an embedded decomposition. We apply the algorithm to two operations management problems: multiclass queue scheduling and multiproduct inventory management. Numerical experiments demonstrate that our algorithm, when combined with appropriate value function approximations, generates policies that achieve superior performance compared with state-of-the-art heuristics. This paper was accepted by Baris Ata, stochastic models and simulation. Funding: Y. Chen was supported by the Hong Kong Research Grants Council, Early Career Scheme Fund [Grant 26508924], and partially supported by a grant from the National Natural Science Foundation of China [Grant 72495125]. J. Dong was supported by the National Science Foundation [Grant 1944209]. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2022.03736 .  more » « less
Award ID(s):
1944209
PAR ID:
10591738
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
INFORMS
Date Published:
Journal Name:
Management Science
ISSN:
0025-1909
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Mathematics of Operations Research)
    We study monotone function-constrained variational inequalities (FCVIs) whose feasible region is the intersection of a projection-friendly set and several convex function constraints; both the operator and the constraint functions may be smooth, nonsmooth, and/or stochastic. Computing the projection operator is challenging for FCVIs. We introduce the adaptive operator extrapolation (AdOpEx) method, which employs an operator extrapolation on the Karush–Kuhn–Tucker operator of the FCVI in a smooth deterministic setting. Because this operator is not uniformly Lipschitz continuous in the Lagrange multipliers, we employ an adaptive two-timescale algorithm leading to bounded multipliers and achieving the optimal [Formula: see text] convergence rate. For the nonsmooth and stochastic VIs, we introduce design changes to the AdOpEx method and propose a novel P-OpEx method that takes a partial extrapolation. It converges at the rate of [Formula: see text] when both the operator and constraints are stochastic or nonsmooth. This method has suboptimal dependence on the noise and Lipschitz constants of function constraints. We propose a constraint extrapolation approach leading to the OpConEx method that improves this dependence by an order of magnitude. All our algorithms also extend to solving saddle point problems with jointly convex function constraints that couple the primal and dual variables. Within this structured class of problems, our methods preserve their respective complexity guarantees, establishing what we believe to be the first such comprehensive complexity results. Funding: D. Boob and M. Khalafi were partially supported by the National Science Foundation [Grants 2245705 and 2340858]. D. Boob was partially supported by the Office of Naval Research [Grant N000142412749]. Q. Deng was partially supported by the National Natural Science Foundation of China [Grants 12571325 and 72394364/72394360] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300]. 
    more » « less
  2. ; ; ; ; (, Manufacturing & Service Operations Management)
    Problem definition: Inventory management problems with periodic and controllable resets occur in the context of managing water storage in the developing world and dynamically optimizing endcap promotion duration in retail outlets. In this paper, we consider a set of sequential decision problems in which the decision maker must not only balance holding and shortage costs but discard all inventory before a fixed number of decision epochs with the option for an early inventory reset. Methodology/results: Finding optimal policies for these problems through dynamic programming presents unique challenges because of the nonconvex nature of the resulting value functions. Moreover, this structure cannot be readily analyzed even with extended convexity definitions, such as K-convexity. Managerial implications: Our key contribution is to present sufficient conditions that ensure the optimal policy has an easily interpretable structure, which generalizes the well-known [Formula: see text] policy from the operations management literature. Furthermore, we demonstrate that, under these rather mild conditions, the optimal policy exhibits a four-threshold structure. We then conclude with computational experiments, thereby illustrating the policy structures that can be extracted in various inventory management scenarios. Funding: This work was supported by the National Science Foundation [Grant CMMI-1847666] and the Division of Graduate Education [Grant DGE-2125913]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0318 . 
    more » « less
  3. ; ; ; (, Management Science)
    We consider the problem of learning an optimal prescriptive tree (i.e., an interpretable treatment assignment policy in the form of a binary tree) of moderate depth from observational data. This problem arises in numerous socially important domains, such as public health and medicine, where interpretable and data-driven interventions are sought based on data gathered in deployment rather than from randomized trials. We propose a method for learning optimal prescriptive trees using mixed-integer optimization technology assuming that our data satisfy standard causal inference assumptions (conditional exchangeability and positivity) and are discrete/discretized. We show that under mild conditions, our method is asymptotically exact (i.e., it converges to an optimal out-of-sample treatment assignment policy as the number of historical data samples tends to infinity). Contrary to the existing literature, our approach (a) does not require data to be randomized, (b) does not impose stringent assumptions on the learned trees, and (c) has the ability to model domain-specific constraints. Through extensive computational experiments, we demonstrate that our asymptotic guarantees translate to significant performance improvements in finite samples as well as showcase our uniquely flexible modeling power by incorporating budget and fairness constraints. This paper was accepted by Chung Piaw Teo, optimization. Funding: N. Jo acknowledges support from the Epstein Institute at the University of Southern California. N. Jo, S. Aghaei, and P. Vayanos acknowledge support from the Home for Good Foundation [Grant C.E.S. Triage Tool Research & Refinement], the Conrad N. Hilton Foundation [Grant C.E.S. Triage Tool Research & Refinement], and the Homeless Policy Research Institute [Grant C.E.S. Triage Tool Research & Refinement]. S. Aghaei and P. Vayanos are funded in part by the National Science Foundation [Grant 2046230]. A. Gómez is funded in part by the National Science Foundation [Grant 2006762]. A. Gómez and P. Vayanos are also supported by the National Science Foundation [NRT Grant 2346058]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2021.02813 . 
    more » « less
  4. ; (, Operations Research)
    Price-based revenue management is an important problem in operations management with many practical applications. The problem considers a seller who sells one or multiple products over T consecutive periods and is subject to constraints on the initial inventory levels of resources. Whereas, in theory, the optimal pricing policy could be obtained via dynamic programming, computing the exact dynamic programming solution is often intractable. Approximate policies, such as the resolving heuristics, are often applied as computationally tractable alternatives. In this paper, we show the following two results for price-based network revenue management under a continuous price set. First, we prove that a natural resolving heuristic attains O(1) regret compared with the value of the optimal policy. This improves the [Formula: see text] regret upper bound established in the prior work by Jasin in 2014. Second, we prove that there is an [Formula: see text] gap between the value of the optimal policy and that of the fluid model. This complements our upper bound result by showing that the fluid is not an adequate information-relaxed benchmark when analyzing price-based revenue management algorithms. Funding: This work was supported in part by the National Science Foundation [Grant CMMI-2145661]. 
    more » « less
  5. ; ; ; (, Mathematics of Operations Research)
    Bilevel optimization has gained significant attention in recent years because of its broad applications in machine learning. This paper focuses on bilevel optimization in decentralized networks and proposes a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is built on the basis of the SOBA framework, and it is a fully single-loop method that approximates the hypergradient by using merely two matrix-vector multiplications per iteration. Importantly, by incorporating the gradient tracking and projection techniques, our algorithm does not require any gradient heterogeneity assumption, which distinguishes it from existing methods for decentralized bilevel optimization and federated bilevel optimization. We establish the convergence rate of the proposed algorithm. Moreover, we present experimental results on hyperparameter optimization and data hyper-cleaning problems, which demonstrate the efficiency of our proposed algorithm. Funding: This work was supported by the National Science Foundation Division of Mathematical Sciences [Grant 2243650]; the Division of Computing and Communication Foundations [Grants 2308597 and 2311275]; the Division of Electrical, Communications and Cyber Systems [Grant 2326591]; the National Natural Science Foundation of China [Grants 12431011, 12371301 and 12501425]; the Key Laboratory of NSLSCS, Ministry of Education of China; and the Natural Science Foundation of Jiangsu Province [Grant SBK20250404650]. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Text Encoded Conversion
  • XML
  • Save / Share this Record
  • Send to Email