IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v231y2013i3p645-653.html
   My bibliography  Save this article

Algorithmic aspects of mean–variance optimization in Markov decision processes

Author

Listed:
  • Mannor, Shie
  • Tsitsiklis, John N.

Abstract

We consider finite horizon Markov decision processes under performance measures that involve both the mean and the variance of the cumulative reward. We show that either randomized or history-based policies can improve performance. We prove that the complexity of computing a policy that maximizes the mean reward under a variance constraint is NP-hard for some cases, and strongly NP-hard for others. We finally offer pseudopolynomial exact and approximation algorithms.

Suggested Citation

  • Mannor, Shie & Tsitsiklis, John N., 2013. "Algorithmic aspects of mean–variance optimization in Markov decision processes," European Journal of Operational Research, Elsevier, vol. 231(3), pages 645-653.
    • Handle: RePEc:eee:ejores:v:231:y:2013:i:3:p:645-653
    DOI: 10.1016/j.ejor.2013.06.019
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713005079
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.06.019?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kawai, Hajime, 1987. "A variance minimization problem for a Markov decision process," European Journal of Operational Research, Elsevier, vol. 31(1), pages 140-145, July.
    2. Luenberger, David G., 1997. "Investment Science," OUP Catalogue, Oxford University Press, number 9780195108095.
    3. Riedel, Frank, 2004. "Dynamic coherent risk measures," Stochastic Processes and their Applications, Elsevier, vol. 112(2), pages 185-200, August.
    4. Guo, Xianping & Ye, Liuer & Yin, George, 2012. "A mean–variance optimization problem for discounted Markov decision processes," European Journal of Operational Research, Elsevier, vol. 220(2), pages 423-429.
    5. Ying Huang & L. C. M. Kallenberg, 1994. "On Finding Optimal Policies for Markov Decision Chains: A Unifying Framework for Mean-Variance-Tradeoffs," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 434-448, May.
    6. Philippe Artzner & Freddy Delbaen & Jean‐Marc Eber & David Heath, 1999. "Coherent Measures of Risk," Mathematical Finance, Wiley Blackwell, vol. 9(3), pages 203-228, July.
    7. Garud N. Iyengar, 2005. "Robust Dynamic Programming," Mathematics of Operations Research, INFORMS, vol. 30(2), pages 257-280, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Haoran Wang & Xun Yu Zhou, 2020. "Continuous‐time mean–variance portfolio selection: A reinforcement learning framework," Mathematical Finance, Wiley Blackwell, vol. 30(4), pages 1273-1308, October.
    2. Thomas Spooner & Rahul Savani, 2020. "A Natural Actor-Critic Algorithm with Downside Risk Constraints," Papers 2007.04203, arXiv.org.
    3. Jingnan Fan & Andrzej Ruszczynski, 2014. "Process-Based Risk Measures and Risk-Averse Control of Discrete-Time Systems," Papers 1411.2675, arXiv.org, revised Nov 2016.
    4. Li Xia, 2020. "Risk‐Sensitive Markov Decision Processes with Combined Metrics of Mean and Variance," Production and Operations Management, Production and Operations Management Society, vol. 29(12), pages 2808-2827, December.
    5. 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.
    6. Haoran Wang & Xun Yu Zhou, 2019. "Continuous-Time Mean-Variance Portfolio Selection: A Reinforcement Learning Framework," Papers 1904.11392, arXiv.org, revised May 2019.
    7. Haoran Wang & Shi Yu, 2021. "Robo-Advising: Enhancing Investment with Inverse Optimization and Deep Reinforcement Learning," Papers 2105.09264, arXiv.org.
    8. Xiangyu Cui & Xun Li & Yun Shi & Si Zhao, 2023. "Discrete-Time Mean-Variance Strategy Based on Reinforcement Learning," Papers 2312.15385, arXiv.org.
    9. Jingnan Fan & Andrzej Ruszczyński, 2018. "Risk measurement and risk-averse control of partially observable discrete-time Markov systems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 88(2), pages 161-184, October.
    10. Haoran Wang, 2019. "Large scale continuous-time mean-variance portfolio allocation via reinforcement learning," Papers 1907.11718, arXiv.org, revised Aug 2019.

    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. 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.
    2. Samuel N. Cohen & Tanut Treetanthiploet, 2019. "Gittins' theorem under uncertainty," Papers 1907.05689, arXiv.org, revised Jun 2021.
    3. Shapiro, Alexander, 2012. "Minimax and risk averse multistage stochastic programming," European Journal of Operational Research, Elsevier, vol. 219(3), pages 719-726.
    4. repec:hum:wpaper:sfb649dp2007-010 is not listed on IDEAS
    5. Qian Lin & Frank Riedel, 2021. "Optimal consumption and portfolio choice with ambiguous interest rates and volatility," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(3), pages 1189-1202, April.
    6. Zachary Feinstein & Birgit Rudloff, 2018. "Scalar multivariate risk measures with a single eligible asset," Papers 1807.10694, arXiv.org, revised Feb 2021.
    7. Qinyu Wu & Fan Yang & Ping Zhang, 2023. "Conditional generalized quantiles based on expected utility model and equivalent characterization of properties," Papers 2301.12420, arXiv.org.
    8. Li Xia, 2020. "Risk‐Sensitive Markov Decision Processes with Combined Metrics of Mean and Variance," Production and Operations Management, Production and Operations Management Society, vol. 29(12), pages 2808-2827, December.
    9. Alois Pichler & Ruben Schlotter, 2020. "Quantification of Risk in Classical Models of Finance," Papers 2004.04397, arXiv.org, revised Feb 2021.
    10. Fei Sun & Jingchao Li & Jieming Zhou, 2018. "Dynamic risk measures with fluctuation of market volatility under Bochne-Lebesgue space," Papers 1806.01166, arXiv.org, revised Mar 2024.
    11. Jocelyne Bion-Nadal, 2006. "Time Consistent Dynamic Risk Processes, Cadlag Modification," Papers math/0607212, arXiv.org.
    12. Yuichi Takano & Renata Sotirov, 2012. "A polynomial optimization approach to constant rebalanced portfolio selection," Computational Optimization and Applications, Springer, vol. 52(3), pages 645-666, July.
    13. Leippold, Markus & Schärer, Steven, 2017. "Discrete-time option pricing with stochastic liquidity," Journal of Banking & Finance, Elsevier, vol. 75(C), pages 1-16.
    14. Cinfrignini, Andrea & Petturiti, Davide & Vantaggi, Barbara, 2023. "Dynamic bid–ask pricing under Dempster-Shafer uncertainty," Journal of Mathematical Economics, Elsevier, vol. 107(C).
    15. Acciaio, Beatrice & Föllmer, Hans & Penner, Irina, 2012. "Risk assessment for uncertain cash flows: model ambiguity, discounting ambiguity, and the role of bubbles," LSE Research Online Documents on Economics 50118, London School of Economics and Political Science, LSE Library.
    16. Yi Shen & Zachary Van Oosten & Ruodu Wang, 2024. "Partial Law Invariance and Risk Measures," Papers 2401.17265, arXiv.org, revised Jun 2024.
    17. Beißner, Patrick, 2013. "Coherent Price Systems and Uncertainty-Neutral Valuation," VfS Annual Conference 2013 (Duesseldorf): Competition Policy and Regulation in a Global Economic Order 80010, Verein für Socialpolitik / German Economic Association.
    18. Karel Sladký, 2005. "On mean reward variance in semi-Markov processes," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 62(3), pages 387-397, December.
    19. Anthony Coache & Sebastian Jaimungal & 'Alvaro Cartea, 2022. "Conditionally Elicitable Dynamic Risk Measures for Deep Reinforcement Learning," Papers 2206.14666, arXiv.org, revised May 2023.
    20. Ola Mahmoud, 2015. "The Temporal Dimension of Risk," Papers 1501.01573, arXiv.org, revised Jun 2016.
    21. Wayne King Ming Chan, 2015. "RAROC-Based Contingent Claim Valuation," PhD Thesis, Finance Discipline Group, UTS Business School, University of Technology, Sydney, number 3-2015, January-A.

    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:eee:ejores:v:231:y:2013:i:3:p:645-653. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.