Reducible Markov decision processes and stochastic games | Weatherhead School at Case Western Reserve University

Reducible Markov decision processes and stochastic games

Reducible Markov decision processes and stochastic games

Authors

Published

Production and Operations Management, vol. Forthcoming, 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.