Reducible Markov Decision Processes and Stochastic Games

Jie Ning

Production and Operations Management, 2021, vol. 30, issue 8, 2726-2751

Abstract: Markov decision processes (MDPs) provide a powerful framework for analyzing dynamic decision making. However, their applications are significantly hindered by the difficulty of obtaining solutions. In this study, we introduce reducible MDPs whose exact solutions can be obtained by solving simpler MDPs, termed the coordinate MDPs. The value function and an optimal policy of a reducible MDP are linear functions of those of the associated coordinate MDP. Because the coordinate MDP does not involve the multi‐dimensional endogenous state, we achieve dimension reduction on a reducible MDP. Extending the MDP framework to multiple players, we introduce reducible stochastic games. We show that these games reduce to simpler coordinate games that do not involve the multi‐dimensional endogenous state. We specify sufficient conditions for the existence of a pure‐strategy Markov perfect equilibrium in reducible stochastic games and derive closed‐form expressions for the players’ equilibrium values. The reducible framework encompasses a variety of linear and nonlinear models and offers substantial simplification in analysis and computation. We provide guidelines and illustrative examples on formulating problems as reducible models. We demonstrate the applicability and modeling flexibility of reducible models in a wide range of contexts including capacity and inventory management and duopoly competition.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1111/poms.13404

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:popmgt:v:30:y:2021:i:8:p:2726-2751

Ordering information: This journal article can be ordered from
http://onlinelibrary ... 1111/(ISSN)1937-5956

Access Statistics for this article

Production and Operations Management is currently edited by Kalyan Singhal

More articles in Production and Operations Management from Production and Operations Management Society
Bibliographic data for series maintained by Wiley Content Delivery ().