Temporal Concatenation for Markov Decision Processes
Preprint
Abstract
We propose and analyze a temporal concatenation heuristic for solving large-scale finite-horizon Markov decision processes (MDP), which divides the 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. Our main results characterize the regret of temporal concatenation compared to the optimal solution. We provide upper bounds for general MDP instances, as well as a family of MDP instances in which the upper bounds are shown to be tight. Together, our results demonstrate temporal concatenation's potential of substantial speed-up at the expense of some performance degradation.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Decomposition methods for solving Markov decision processes with multiple models of the parametersIISE Transactions, 2021
- 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
- Optimal Adaptive Policies for Markov Decision ProcessesMathematics of Operations Research, 1997
- 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