为不确定决策过程提供在线统计验证的新方法，大幅减少所需样本量。
Confidence Sequences for Online Statistical Model Checking of Markov Decision Processes
- 设计适用于在线场景的置信序列，动态更新统计结论
- 实验表明平均只需前人1/50的样本量即可达成可靠验证
- 特别适合实时系统、生物过程等难以精确建模的应用
马尔可夫决策过程（MDPs）是不确定性环境下决策的经典模型，兼具非确定性选择与概率不确定性。传统方法假设已知精确的概率分布，但在建模网络物理系统或生物过程时往往不现实。本文提出多种专为在线场景设计的置信序列，可在持续采样中实时生成可信区间。我们实现了这些方法，并证明其显著优于经典的“并集界”方法，在实际应用中平均仅需前人最优方法1/50的样本量即可获得可靠验证结果。
原文摘要 · Abstract (English)
Markov decision processes (MDPs) are a classic model of decision making under uncertainty, exhibiting both non-deterministic choice as well as probabilistic uncertainty. Traditionally, exact knowledge of the underlying probabilities is assumed. However, this often is unrealistic, e.g.\ when modelling cyber-physical systems or biological processes. Here, statistical methods provide a way towards obtaining meaningful guarantees. The classical approach is to gather samples in the MDP, use these to draw statistical conclusions about the transition probabilities, and from there obtain bounds on the true value; then, if these bounds are too broad, repeat. However, existing implementations of this approach are either subtly incorrect or sub-optimal, and quite often both. We present several \emph{confidence sequences}, which are specifically designed for such \enquote{online} settings, implement all of them in an efficient tool, and show their practical applicability. In particular, we show that they outperform classical \enquote{union-bound} style approaches, and overall our implementation requires 50x less samples on average than previous state of the art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。