Um novo algoritmo agregação temporal para resolver processos de decisão markovianos com custo médio

Abstract

This work introduces and proves the convergence of a new class of algorithms based on time aggregation to solve Markov decision problems with average cost. The new algorithms use a new partitioning scheme that divides the state space into multiple subsets comprised of frontier states and interior states. The frontier states give rise to a new subset that comprises the state space of the embedded Markov chain. In the first step, the algorithm sets an ad-hoc policy for interior states and iterates only on frontier states. In contrast, in the second step, the algorithm iterates only on the interior states. One of the great advantages of the proposed approach is that the new partitioning scheme generates subsets with specific communication properties that allow a distributed policy improvement in the interior states, thus limiting the computational effort. Different policy improvement strategies were implemented and evaluated using the proposed approach to solve two problems: one is a production and inventory management problem and the other is a queue management problem. The results are very encouraging, as the proposed algorithms converged up to 60(20) times faster than the policy(value) iteration in the experiments. In addition to the new algorithms, this work presents a set of conceptual maps that characterise the state-of-the-art in Markov decision processes.