文章基本信息

标题：Of Cores: A Partial-Exploration Framework for Markov Decision Processes
本地全文：下载
作者：Meggendorfer, Tobias ; Křetínský, Jan
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2020
卷号：16
期号：4
页码：1-31
语种：English
出版社：Technical University of Braunschweig
摘要：We introduce a framework for approximate analysis of Markov decisionprocesses (MDP) with bounded-, unbounded-, and infinite-horizon properties. Themain idea is to identify a "core" of an MDP, i.e., a subsystem where weprovably remain with high probability, and to avoid computation on the lessrelevant rest of the state space. Although we identify the core usingsimulations and statistical techniques, it allows for rigorous error bounds inthe analysis. Consequently, we obtain efficient analysis algorithms based onpartial exploration for various settings, including the challenging case ofstrongly connected systems.
关键词：Electrical Engineering and Systems Science - Systems and Control;Computer Science - Artificial Intelligence;Computer Science - Logic in Computer Science