Reducible Markov Decision Processes and Stochastic Games
Production and Operations Management · 2021 · Volume 30 · Issue 8
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 introducereducible MDPswhoseexactsolutions can be obtained by solving simpler MDPs, termed thecoordinate 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 introducereducible stochastic games. We show that these games reduce to simplercoordinate gamesthat 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 andnonlinearmodels 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.
Keywords
Markov decision processes, stochastic games, dimension reduction, applications, nonlinear models
Enable JavaScript for citation tools and additional paper interactions.