一句话：提出一种 anytime 算法，能以给定精度逼近广义可达性随机博弈的 Pareto 前沿并给出误差界。
简单随机博弈是回合制的 2½ 人博弈，其目标为可达性：判断一个玩家能否以至少给定概率到达目标。一个自然扩展是目标为多个可达性条件的合取，即广义可达性随机博弈。尽管多目标系统分析已有大量结果，该基本问题的可判定性仍然开放。本文不直接解决可判定性，而是提出一种近似算法，能以给定精度逼近可实现值的 Pareto 前沿。该算法是 anytime 的，即在任意时刻停止都能返回当前近似值及其误差上界。
Simple stochastic games are turn-based 2½-player games with a reachability objective. The basic question asks whether one player can ensure reaching a given target with at least a given probability. A natural extension is games with a conjunction of such conditions as objective. Despite a plethora of recent results on the analysis of systems with multiple objectives, the decidability of this basic problem remains open. In this paper, we present an algorithm approximating the Pareto frontier of the achievable values to a given precision. Moreover, it is an anytime algorithm, meaning it can be stopped at any time returning the current approximation and its error bound.
@inproceedings{paperbot5540,
title = {Approximating Values of Generalized-Reachability Stochastic Games},
author = {Pranav Ashok and Krishnendu Chatterjee and Jan Křetínský and Maximilian Weininger and Tobias Winkler},
booktitle = {LICS},
year = {2020},
doi = {10.1145/3373718.3394761}
}