Exact Inference for Nested Discrete Probabilistic Programs
summary
Reduces nested discrete probabilistic programs to a probabilistic pushdown automata and then to a monotone system of polynomial equations whose variables are termination/return probabilities; shows those solutions are often irrational and not solvable by radicals, so uses optimistic value iteration to compute certified lower and upper bounds that converge arbitrarily close. Reports fast solutions on a Schelling coordination benchmark and notes WebPPL cannot handle the nested inference case tested.
AI-written summary · about