Abstract
We formalize the notion of nesting probabilistic programming queries andinvestigate the resulting statistical implications. We demonstrate that querynesting allows the definition of models which could not otherwise be expressed,such as those involving agents reasoning about other agents, but that existingsystems take approaches that lead to inconsistent estimates. We show how tocorrect this by delineating possible ways one might want to nest queries andasserting the respective conditions required for convergence. We furtherintroduce, and prove the correctness of, a new online nested Monte Carloestimation method that makes it substantially easier to ensure these conditionsare met, thereby providing a simple framework for designing statisticallycorrect inference engines.