Of Cores: A Partial-Exploration Framework for Markov Decision Processes
This provides a method for more efficient MDP analysis, which is incremental as it builds on existing simulation and statistical techniques to improve computational handling in complex scenarios.
The paper tackles the problem of approximate analysis for Markov decision processes (MDPs) with various horizon properties by introducing a framework that identifies a 'core' subsystem to avoid computation on less relevant state space, resulting in efficient algorithms with rigorous error bounds for settings like strongly connected systems.
We introduce a framework for approximate analysis of Markov decision processes (MDP) with bounded-, unbounded-, and infinite-horizon properties. The main idea is to identify a "core" of an MDP, i.e., a subsystem where we provably remain with high probability, and to avoid computation on the less relevant rest of the state space. Although we identify the core using simulations and statistical techniques, it allows for rigorous error bounds in the analysis. Consequently, we obtain efficient analysis algorithms based on partial exploration for various settings, including the challenging case of strongly connected systems.