Solving Markov decision processes via state space decomposition and time aggregation
提出一种多子集划分方案，结合时间聚合实现分布式策略评估与改进，利用Foster随机稳定性条件设计近似算法，在生产和库存、排队等实验中快速逼近大规模系统的最优解。
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.