Novel Time Aggregation-Based Algorithms for Markov Decision Processes

• 成果类型: Article
• 署名作者: Leite, Joao Marcelo L. G.; Marujo, Lino G.; Arruda, Edilson F.
• 署名单位: Universidade de Sao Paulo; Insper; Universidade Federal do Rio de Janeiro; University of Southampton; Solent University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3583262
• 发表日期: 2025
• 关键词: SET ITERATION; optimization

摘要

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.