Solving Markov decision processes via state space decomposition and time aggregation
Rodrigo e Alvim Alexandre, Marcelo Dutra Fragoso, Virgílio José Martins Ferreira Filho, Edilson F. Arruda · European Journal of Operational Research · 2025
Although there are techniques to address large scale Markov decision processes (MDP), a computationally adequate solution of the so-called curse of dimensionality still eludes, in many aspects, a satisfactory treatment. In this paper, we advance in this issue by introducing a novel multi-subset partitioning scheme to allow for a distributed evaluation of the MDP, aiming to accelerate convergence and enable distributed policy improvement across the state space, whereby the value function and the policy improvement step can be performed independently, one subset at a time. The scheme’s innovation hinges on a design that induces communication properties that allow us to evaluate time aggregated trajectories via absorption analysis, thereby limiting the computational effort. The paper introduces and proves the convergence of a class of distributed time aggregation algorithms that combine the partitioning scheme with two-phase time aggregation to distribute the computations and accelerate convergence. In addition, we make use of Foster’s sufficient conditions for stochastic stability to develop a new theoretical result which underpins a partition design that guarantees that large regions of the state space are rarely visited and have a marginal effect on the system’s performance. This enables the design of approximate algorithms to find near-optimal solutions to large scale systems by focusing on the most visited regions of the state space. We validate the approach in a series of experiments featuring production and inventory and queuing applications. The results highlight the potential of the proposed algorithms to rapidly approach the optimal solution under different problem settings. • We combine state-space decomposition and time aggregation to solve MDPs. • This gives rise to an efficient class of distributed time aggregation algorithms. • The approach tackles dimensionality via Foster’s stochastic stability conditions. • The approach was validated in a series of experiments. • The algorithms were able to find near-optimal solutions to large scale systems.