Sensitivity-based nested partitions for solving finite-horizon Markov decision processes

In this paper, we propose a heuristic for solving finite-horizon Markov decision processes. The heuristic uses the nested partitions (NP) framework to guide an iterative search for the optimal policy. NP focuses the search on certain promising subregions, flexibly determined by the sampling weight of each action branch. Within each subregion, an effective local policy optimization is developed using sensitivity-based approach, which optimizes the sampling weights based on estimated gradient information. Numerical results show the effectiveness of the proposed heuristic.