Hidden Symmetries in Markov Decision Processes

A Markov decision process (MDP) is a stochastic framework used to model decision making problems. Some problems and their MDPs are too large to be solved by algorithms in a reasonable time. One common approach for reducing MDPs is symmetry breaking. Here, only directly accessible symmetries are currently considered. However, there are problems with symmetries that are not captured by this type of symmetries. This thesis introduces the new concept of hidden symmetries and the induced model reduction framework. Hidden symmetries of an MDP are essentially directly accessible symmetries of equivalent MDPs. In this, two MDPs are equivalent if their state transition structure and optimal policies are the same up to labeling. Thus, hidden symmetries extend the concept of directly accessible symmetries and therefore provide greater potential for reducing MDPs. Furthermore, this thesis presents an approach to reveal hidden symmetries for multi-period problems that operate deterministically and are perturbed stochastically from the outside. This approach is then applied to the stonevendor problem, which is a variant of the newsvendor problem, and a more sophisticated supply chain problem.