Solving Markov decision processes via state space decomposition and time aggregation

Rodrigo e Alvim Alexandre, Marcelo D. Fragoso, Virgílio J.M. Ferreira Filho and Edilson F. Arruda

European Journal of Operational Research, 2025, vol. 324, issue 1, 155-167

Abstract: 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.

Keywords: Markov processes; Dynamic programming; Markov decision processes; Time aggregation; Foster’s stochastic stability conditions (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725000803
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:324:y:2025:i:1:p:155-167

DOI: 10.1016/j.ejor.2025.01.037

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().