Path-dependent Discrete Amortized Inference

We consider the problem of sampling compositional and discrete objects from a given unnormalized posterior distribution. Notably, recent studies have shown that this problem can be efficiently solved by learning a deterministic Markov Decision Process (MDP) that progressively builds each object in proportion to the posterior. In this work, however, we demonstrate that the Markovian assumption can both hamper signal propagation during training and catastrophically reduce the learned sampler's expressivity due to state aliasing. To address these issues, we propose lifting the MDP with a learnable latent dynamics that allows the underlying policy to depend on the entire past trajectory---and not only on the current state. In view of this, we refer to the resulting method as \emph{path-dependent discrete amortized inference}. Importantly, we provably extend existing learning algorithms for amortized samplers to our setting. In experiments on standard benchmark problems, we also show that our approach often leads to faster learning convergence and improved state space exploration relatively to prior techniques.

Complex statistical models are at the core of many applications in engineering, biology, and finance. A model is only as useful, however, as our ability to extract knowledge from it---i.e., to make predictions about the world and to evaluate them against our observations. Nonetheless, as our modelling techniques grow in complexity, exact calculations cease to be possible, and inference can only be carried out through approximate computer simulations. A special and, until recently, underexplored instance of the above setting is when our decision space---the uncertainty of which is measured by our statistical model---is finite (or, discrete). Under these conditions, a well-established approach for designing the corresponding simulators is to assume path-independence (or, Markovianity). This means, in rough terms, that future outcomes do not depend on past actions, given the current state. Our work challenges this assumption, and demonstrates that path-dependent (or, non-Markovian) simulators provide more accurate approximations to common target statistical models than their Markovian counterparts---even when a Markovian approach could (in theory) yield a perfect simulation.