Reducible Markov decision processes and stochastic games
Authors
Published
Production and Operations Management, vol.
30, issue
8, pp.
2726-2751,
2021
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 paper, we introduce <i>reducible MDPs</i> whose <i>exact</i> solutions can be obtained by solving simpler MDPs, termed the <i>coordinate MDPs</i>. The value function and an optimal policy of a reducible MDP are linear functions of those of the coordinate MDP. The coordinate MDP does not involve the multi-dimensional endogenous state. Thus, we achieve dimension reduction on a reducible MDP by solving its associated coordinate MDP.<br><br>Extending the MDP framework to multiple players, we introduce <i>reducible stochastic games</i>. We show that these games reduce to simpler<i> coordinate games</i> 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.<br><br>The reducible framework encompasses a variety of linear and <i>nonlinear</i> models and offers substantial simplification in analysis and computation. We provide guidelines for formulating problems as reducible models and illustrate ways to transform a model into the reducible framework. We demonstrate the applicability and modeling flexibility of reducible models in a wide range of contexts including capacity and inventory management and duopoly competition.
