IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v39y1991i1p162-175.html
   My bibliography  Save this article

Computationally Feasible Bounds for Partially Observed Markov Decision Processes

Author

Listed:
  • William S. Lovejoy

    (Stanford University, Stanford, California)

Abstract

A partially observed Markov decision process (POMDP) is a sequential decision problem where information concerning parameters of interest is incomplete, and possible actions include sampling, surveying, or otherwise collecting additional information. Such problems can theoretically be solved as dynamic programs, but the relevant state space is infinite, which inhibits algorithmic solution. This paper explains how to approximate the state space by a finite grid of points, and use that grid to construct upper and lower value function bounds, generate approximate nonstationary and stationary policies, and bound the value loss relative to optimal for using these policies in the decision problem. A numerical example illustrates the methodology.

Suggested Citation

  • William S. Lovejoy, 1991. "Computationally Feasible Bounds for Partially Observed Markov Decision Processes," Operations Research, INFORMS, vol. 39(1), pages 162-175, February.
    • Handle: RePEc:inm:oropre:v:39:y:1991:i:1:p:162-175
    DOI: 10.1287/opre.39.1.162
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.39.1.162
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.39.1.162?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
    ---><---

    Citations

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


    Cited by:

    1. Hao Zhang, 2010. "Partially Observable Markov Decision Processes: A Geometric Technique and Analysis," Operations Research, INFORMS, vol. 58(1), pages 214-228, February.
    2. Chiel van Oosterom & Lisa M. Maillart & Jeffrey P. Kharoufeh, 2017. "Optimal maintenance policies for a safety‐critical system and its deteriorating sensor," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(5), pages 399-417, August.
    3. Karabağ, Oktay & Bulut, Önder & Toy, Ayhan Özgür & Fadıloğlu, Mehmet Murat, 2024. "An efficient procedure for optimal maintenance intervention in partially observable multi-component systems," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    4. Robert Kraig Helmeczi & Can Kavaklioglu & Mucahit Cevik & Davood Pirayesh Neghab, 2023. "A multi-objective constrained partially observable Markov decision process model for breast cancer screening," Operational Research, Springer, vol. 23(2), pages 1-42, June.
    5. Nguyen, Khanh T. P. & Do, Phuc & Huynh, Khac Tuan & Bérenguer, Christophe & Grall, Antoine, 2019. "Joint optimization of monitoring quality and replacement decisions in condition-based maintenance," Reliability Engineering and System Safety, Elsevier, vol. 189(C), pages 177-195.
    6. Juri Hinz, 2021. "On Approximate Solutions for Partially Observable Decision Problems," Research Paper Series 421, Quantitative Finance Research Centre, University of Technology, Sydney.
    7. KarabaÄŸ, Oktay & Eruguz, Ayse Sena & Basten, Rob, 2020. "Integrated optimization of maintenance interventions and spare part selection for a partially observable multi-component system," Reliability Engineering and System Safety, Elsevier, vol. 200(C).
    8. Abraham Grosfeld‐Nir & Eyal Cohen & Yigal Gerchak, 2007. "Production to order and off‐line inspection when the production process is partially observable," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 845-858, December.
    9. Memarzadeh, Milad & Pozzi, Matteo, 2016. "Value of information in sequential decision making: Component inspection, permanent monitoring and system-level scheduling," Reliability Engineering and System Safety, Elsevier, vol. 154(C), pages 137-151.
    10. Lyn C. Thomas & James N. Eagle, 1995. "Criteria and approximate methods for path‐constrained moving‐target search problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(1), pages 27-38, February.
    11. Yu Zhang & Jason Leezer, 2010. "Simulating human-like decisions in a memory-based agent model," Computational and Mathematical Organization Theory, Springer, vol. 16(4), pages 373-399, December.
    12. Jingyu Zhang & Brian T. Denton & Hari Balasubramanian & Nilay D. Shah & Brant A. Inman, 2012. "Optimization of PSA Screening Policies," Medical Decision Making, , vol. 32(2), pages 337-349, March.
    13. Shoshana Anily & Abraham Grosfeld-Nir, 2006. "An Optimal Lot-Sizing and Offline Inspection Policy in the Case of Nonrigid Demand," Operations Research, INFORMS, vol. 54(2), pages 311-323, April.
    14. Harun Avci & Kagan Gokbayrak & Emre Nadar, 2020. "Structural Results for Average‐Cost Inventory Models with Markov‐Modulated Demand and Partial Information," Production and Operations Management, Production and Operations Management Society, vol. 29(1), pages 156-173, January.
    15. Vishal Ahuja & John R. Birge, 2020. "An Approximation Approach for Response-Adaptive Clinical Trial Design," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 877-894, October.
    16. Burhaneddin Sandıkçı & Lisa M. Maillart & Andrew J. Schaefer & Mark S. Roberts, 2013. "Alleviating the Patient's Price of Privacy Through a Partially Observable Waiting List," Management Science, INFORMS, vol. 59(8), pages 1836-1854, August.
    17. Yossi Aviv & Amit Pazgal, 2005. "A Partially Observed Markov Decision Process for Dynamic Pricing," Management Science, INFORMS, vol. 51(9), pages 1400-1416, September.
    18. Satya S. Malladi & Alan L. Erera & Chelsea C. White, 2021. "Managing mobile production-inventory systems influenced by a modulation process," Annals of Operations Research, Springer, vol. 304(1), pages 299-330, September.
    19. Fackler, Paul L. & Haight, Robert G., 2014. "Monitoring as a partially observable decision problem," Resource and Energy Economics, Elsevier, vol. 37(C), pages 226-241.
    20. Williams, Byron K., 2011. "Resolving structural uncertainty in natural resources management using POMDP approaches," Ecological Modelling, Elsevier, vol. 222(5), pages 1092-1102.
    21. Vikram Krishnamurthy & Bo Wahlberg, 2009. "Partially Observed Markov Decision Process Multiarmed Bandits---Structural Results," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 287-302, May.
    22. Compare, Michele & Baraldi, Piero & Marelli, Paolo & Zio, Enrico, 2020. "Partially observable Markov decision processes for optimal operations of gas transmission networks," Reliability Engineering and System Safety, Elsevier, vol. 199(C).

    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:39:y:1991:i:1:p:162-175. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.