IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v70y2022i3p1428-1447.html

Quantile Markov Decision Processes

Author

Listed:
  • Xiaocheng Li

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

  • Huaiyang Zhong

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

  • Margaret L. Brandeau

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

Abstract

The goal of a traditional Markov decision process (MDP) is to maximize expected cumulative reward over a defined horizon (possibly infinite). In many applications, however, a decision maker may be interested in optimizing a specific quantile of the cumulative reward instead of its expectation. In this paper, we consider the problem of optimizing the quantiles of the cumulative rewards of an MDP, which we refer to as a quantile Markov decision process (QMDP). We provide analytical results characterizing the optimal QMDP value function and present a dynamic programming-based algorithm to solve for the optimal policy. The algorithm also extends to the MDP problem with a conditional value-at-risk objective. We illustrate the practical relevance of our model by evaluating it on an HIV treatment initiation problem, in which patients aim to balance the potential benefits and risks of the treatment.

Suggested Citation

  • Xiaocheng Li & Huaiyang Zhong & Margaret L. Brandeau, 2022. "Quantile Markov Decision Processes," Operations Research, INFORMS, vol. 70(3), pages 1428-1447, May.
    • Handle: RePEc:inm:oropre:v:70:y:2022:i:3:p:1428-1447
    DOI: 10.1287/opre.2021.2123
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2021.2123
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2021.2123?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Jeremy Berkowitz & James O'Brien, 2002. "How Accurate Are Value‐at‐Risk Models at Commercial Banks?," Journal of Finance, American Finance Association, vol. 57(3), pages 1093-1111, June.
    2. Shapiro, Alexander & Tekaya, Wajdi & da Costa, Joari Paulo & Soares, Murilo Pereira, 2013. "Risk neutral and risk averse Stochastic Dual Dynamic Programming method," European Journal of Operational Research, Elsevier, vol. 224(2), pages 375-391.
    3. Erick Delage & Shie Mannor, 2010. "Percentile Optimization for Markov Decision Processes with Parameter Uncertainty," Operations Research, INFORMS, vol. 58(1), pages 203-213, February.
    4. Mason, J.E. & Denton, B.T. & Shah, N.D. & Smith, S.A., 2014. "Optimizing the simultaneous management of blood pressure and cholesterol for type 2 diabetes patients," European Journal of Operational Research, Elsevier, vol. 233(3), pages 727-738.
    5. Nicole Bäuerle & Jonathan Ott, 2011. "Markov Decision Processes with Average-Value-at-Risk criteria," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(3), pages 361-379, December.
    6. Wolfram Wiesemann & Daniel Kuhn & Berç Rustem, 2013. "Robust Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 38(1), pages 153-183, February.
    7. Steven M. Shechter & Matthew D. Bailey & Andrew J. Schaefer & Mark S. Roberts, 2008. "The Optimal Time to Initiate HIV Therapy Under Ordered Health States," Operations Research, INFORMS, vol. 56(1), pages 20-33, February.
    8. Ronald A. Howard & James E. Matheson, 1972. "Risk-Sensitive Markov Decision Processes," Management Science, INFORMS, vol. 18(7), pages 356-369, March.
    9. Dan A. Iancu & Marek Petrik & Dharmashankar Subramanian, 2015. "Tight Approximations of Dynamic Risk Measures," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 655-682, March.
    10. Daniel R. Jiang & Warren B. Powell, 2018. "Risk-Averse Approximate Dynamic Programming with Quantile-Based Risk Measures," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 554-579, May.
    11. Rockafellar, R. Tyrrell & Uryasev, Stanislav, 2002. "Conditional value-at-risk for general loss distributions," Journal of Banking & Finance, Elsevier, vol. 26(7), pages 1443-1471, July.
    12. Alessandro Arlotto & Noah Gans & J. Michael Steele, 2014. "Markov Decision Problems Where Means Bound Variances," Operations Research, INFORMS, vol. 62(4), pages 864-875, August.
    13. Arnab Nilim & Laurent El Ghaoui, 2005. "Robust Control of Markov Decision Processes with Uncertain Transition Matrices," Operations Research, INFORMS, vol. 53(5), pages 780-798, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ilbin Lee, 2024. "Is Separately Modeling Subpopulations Beneficial for Sequential Decision-Making?," Operations Research, INFORMS, vol. 72(6), pages 2595-2611, November.
    2. Nicole Bäuerle & Anna Jaśkiewicz, 2024. "Markov decision processes with risk-sensitive criteria: an overview," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 99(1), pages 141-178, April.
    3. Julien Grand-Clément & Marek Petrik, 2025. "On the Convex Formulations of Robust Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 50(3), pages 1681-1706, August.
    4. Boloori, Alireza & Saghafian, Soroush & Chakkera, Harini A. A. & Cook, Curtiss B., 2017. "Data-Driven Management of Post-transplant Medications: An APOMDP Approach," Working Paper Series rwp17-036, Harvard University, John F. Kennedy School of Government.
    5. Varagapriya, V & Singh, Vikas Vikram & Lisser, Abdel, 2024. "Rank-1 transition uncertainties in constrained Markov decision processes," European Journal of Operational Research, Elsevier, vol. 318(1), pages 167-178.
    6. Shie Mannor & Ofir Mebel & Huan Xu, 2016. "Robust MDPs with k -Rectangular Uncertainty," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1484-1509, November.
    7. Saghafian, Soroush, 2018. "Ambiguous partially observable Markov decision processes: Structural results and applications," Journal of Economic Theory, Elsevier, vol. 178(C), pages 1-35.
    8. Bren, Austin & Saghafian, Soroush, 2018. "Data-Driven Percentile Optimization for Multi-Class Queueing Systems with Model Ambiguity: Theory and Application," Working Paper Series rwp18-008, Harvard University, John F. Kennedy School of Government.
    9. Wenfan Ou & Sheng Bi, 2025. "Sequential decision-making under uncertainty: a robust MDPs review," Annals of Operations Research, Springer, vol. 353(3), pages 1239-1285, October.
    10. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    11. Nicole Bauerle & Alexander Glauner, 2020. "Distributionally Robust Markov Decision Processes and their Connection to Risk Measures," Papers 2007.13103, arXiv.org.
    12. Maximilian Blesch & Philipp Eisenhauer, 2023. "Robust Decision-Making under Risk and Ambiguity," Rationality and Competition Discussion Paper Series 463, CRC TRR 190 Rationality and Competition.
    13. Mahmutoğulları, Ali İrfan & Çavuş, Özlem & Aktürk, M. Selim, 2018. "Bounds on risk-averse mixed-integer multi-stage stochastic programming problems with mean-CVaR," European Journal of Operational Research, Elsevier, vol. 266(2), pages 595-608.
    14. Xin, Linwei & Goldberg, David A., 2021. "Time (in)consistency of multistage distributionally robust inventory models with moment constraints," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1127-1141.
    15. V Varagapriya & Vikas Vikram Singh & Abdel Lisser, 2023. "Joint chance-constrained Markov decision processes," Annals of Operations Research, Springer, vol. 322(2), pages 1013-1035, March.
    16. Zhu, Zhicheng & Xiang, Yisha & Zhao, Ming & Shi, Yue, 2023. "Data-driven remanufacturing planning with parameter uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 102-116.
    17. Nicole Bäuerle & Alexander Glauner, 2022. "Distributionally Robust Markov Decision Processes and Their Connection to Risk Measures," Mathematics of Operations Research, INFORMS, vol. 47(3), pages 1757-1780, August.
    18. Chengjun Hou, 2025. "Solution for Infinite Horizon Double-Factored Markov Decision Processes with Application," SN Operations Research Forum, Springer, vol. 6(4), pages 1-25, December.
    19. Julien Grand-Clément & Carri W. Chan & Vineet Goyal & Gabriel Escobar, 2023. "Robustness of Proactive Intensive Care Unit Transfer Policies," Operations Research, INFORMS, vol. 71(5), pages 1653-1688, September.
    20. Alexander Shapiro, 2016. "Rectangular Sets of Probability Measures," Operations Research, INFORMS, vol. 64(2), pages 528-541, April.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:70:y:2022:i:3:p:1428-1447. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.