一句话：提出 MDP 部分探索框架，通过识别高概率核心并给出严格误差界，高效近似分析多种时域性质。
本文提出一个针对马尔可夫决策过程（MDP）的近似分析框架，支持有界、无界和无限时域性质。其核心思想是识别 MDP 的“核”（core），即系统以高概率停留的子系统，从而避免在整个状态空间上进行计算，只对相关部分做部分探索。核的识别借助模拟和统计技术，但该框架仍能为分析结果提供严格的误差界。基于此，作者为多种设置设计了高效的部分探索分析算法，尤其覆盖了强连通系统这一具有挑战性的情形。该工作将统计模拟与形式化保证相结合，为大规模 MDP 的近似验证提供了新途径。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-1906-06931,
title = {Of Cores: A Partial-Exploration Framework for Markov Decision Processes},
author = {Jan Křetínský and Tobias Meggendorfer},
journal = {Logical Methods in Computer Science},
volume = {Volume 16, Issue 4},
year = {2020},
doi = {10.23638/lmcs-16(4:3)2020}
}