Abstract
We propose and analyze a Temporal Concatenation (TC) heuristic for solving large-scale finite-horizon Markov decision processes (MDP). The Temporal Concatenation divides a finite-horizon MDP into smaller sub-problems along the time horizon, and generates an overall solution by simply concatenating the optimal solutions from these sub-problems. As a "black box" architecture, Temporal Concatenation works with a wide range of existing MDP algorithms with the potential of substantial speed-up at the expense of minor performance degradation. Our main results characterize the regret of Temporal Concatenation, defined as the gap between the expected rewards from Temporal Concatenation's solution and that from the optimal solution. We provide upper bounds that show, when the underlying MDP satisfies a bounded-diameter criterion, the regret of Temporal Concatenation is bounded by a constant independent of the length of the horizon. Conversely, we provide matching lower bounds that demonstrate that, for any finite diameter, there exist MDP instances for which the regret upper bound is tight. We further contextualize the theoretical results in an illustrative example of dynamic energy management with storage, and provide simulation results to assess Temporal Concatenation's average-case regret within a family of MDPs related to graph traversal.

This publication has 8 references indexed in Scilit: