Temporal Concatenation for Markov Decision Processes
Preprint
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.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Optimal Management and Sizing of Energy Storage Under Dynamic Pricing for the Efficient Integration of Renewable EnergyIEEE Transactions on Power Systems, 2014
- Exact Decomposition Approaches for Markov Decision Processes: A SurveyAdvances in Operations Research, 2010
- Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic RegimeOperations Research, 2004
- Hierarchical Reinforcement Learning with the MAXQ Value Function DecompositionJournal of Artificial Intelligence Research, 2000
- Complexity of finite-horizon Markov decision process problemsJournal of the ACM, 2000
- Collective dynamics of ‘small-world’ networksNature, 1998
- Markov Decision Processes: Discrete Stochastic Dynamic ProgrammingTechnometrics, 1995
- Solving H-horizon, stationary Markov decision problems in time proportional to log(H)Operations Research Letters, 1990