一句话：提出 noDice，扩展 Dice 以对含非确定性与条件化的离散概率程序进行推断，并用决策图缩减所构造 MDP 的状态空间。
概率编程语言（PPL）能直观表达复杂概率分布，但现代 PPL 通常不支持非确定性选择，而这类选择在马尔可夫决策过程（MDP）与强化学习中至关重要。本文提出 noDice，扩展离散概率推断引擎 Dice，为带条件化的无循环离散概率程序提供推断。其核心是构造一个 MDP，使程序所建模的分布对应 MDP 中的调度器（scheduler），从而将非确定性纳入推断。为缓解状态空间爆炸，noDice 引入决策图作为中间步骤，利用程序结构大幅缩减 MDP 状态空间。该工作填补了 PPL 对非确定性支持的空白，并面向文本分析、网络验证、人工智能与图分析等离散分布常见领域。
Probabilistic programming languages (PPLs) are an expressive and intuitive means of representing complex probability distributions. In that realm, languages like Dice target an important class of probabilistic programs: those whose probability distributions are discrete. Discrete distributions are common in many fields, including text analysis, network verification, artificial intelligence, and graph analysis. Another important feature in the world of probabilistic modeling are nondeterministic choices as found in Markov Decision Processes (MDPs) which play a major role in reinforcement learning. Modern PPLs usually lack support for nondeterminism . We address this gap with the introduction of noDice , which extends the discrete probabilistic inference engine Dice . noDice performs inference on loop-free programs by constructing an MDP so that the distributions modeled by the program correspond to schedulers in the MDP. Furthermore, decision diagrams are used as an intermediate step to exploit the program structure and drastically reduce the state space of the MDP.
@article{paperbot3805,
title = {noDice: Inference for Discrete Probabilistic Programs with Nondeterminism and Conditioning},
author = {Tobias Gürtler and Benjamin Lucien Kaminski},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA1},
year = {2026},
doi = {10.1145/3798215}
}