Novel Time Aggregation-Based Algorithms for Markov Decision Processes

doi:10.1109/TAC.2025.3583262

Novel Time Aggregation-Based Algorithms for Markov Decision Processes

2025-12-01

0

PRE

AI

J

João Marcelo Leal Gomes Leite *

L

Lino Guimarães Marujo

E

Edilson F. Arruda

DOI：10.1109/TAC.2025.3583262

Original

Original request for help

Save

Abstract

En 中文

In this article, we present two novel approaches to accelerate the convergence of a class of Markov decision problems with stationary state space components, which iterate on reduced state and action spaces and converge to an optimal policy. The time aggregation-based algorithm partitions the state space into disjoint sets, one for each possible combination of the nonstationary components, and iterates in the sets. The local search policy set iteration algorithm introduces a novel modified policy evaluation procedure that seamlessly performs a local search over a very large set of candidate policies, by sampling a reduced subset of actions at each state's value function update. Both approaches, as well as a combination of them, are validated by means of a mining supply chain application with a large number of stationary state components and a large set of feasible actions. The experiments suggest that the proposed frameworks are very efficient for such a class of problems.

Keywords:

Heuristic algorithms

Convergence

Supply chains

Approximation algorithms

Aerospace electronics

Optimization

Uncertainty

Space stations

Partitioning algorithms

Markov decision processes

Markov decision processes (MDPs)

optimization under uncertainty

stochastic systems

supply chains

Novel Time Aggregation-Based Algorithms for Markov Decision Processes

Abstract

Journal

Organization