# Probably Approximately Correct Maximum A Posteriori Inference

arXiv: https://arxiv.org/abs/2601.16083 · HTML: https://mlsanity.com/paper/2601.16083/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 22 Jan 2026.

## Builds on (most cited first, 15 of 15)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Adversarial random forests for density estimation and generative modeling](https://mlsanity.com/paper/2205.09435/) (2022)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Joints in Random Forests](https://mlsanity.com/paper/2006.14937/) (2020)
- [Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence](https://mlsanity.com/paper/1803.04665/) (2018)
- [Solving Marginal MAP Exactly by Probabilistic Circuit Transformations](https://mlsanity.com/paper/2111.04833/) (2021)
- [Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks](https://mlsanity.com/paper/1703.06045/) (2017)
- [Maximum A Posteriori Inference in Sum-Product Networks](https://mlsanity.com/paper/1708.04846/) (2017)
- [Mixtures of All Trees](https://mlsanity.com/paper/2302.14202/) (2023)
- [High Dimensional Inference with Random Maximum A-Posteriori Perturbations](https://mlsanity.com/paper/1602.03571/) (2016)
- [Maximum a Posteriori Estimation by Search in Probabilistic Programs](https://mlsanity.com/paper/1504.06848/) (2015)

## Abstract (arXiv)

Computing the conditional mode of a distribution, better known as the maximum a posteriori (MAP) assignment, is a fundamental task in probabilistic inference. However, MAP is generally intractable, and remains hard even under many common structural constraints and approximation schemes. We take a novel approach inspired by multi-armed bandits, recasting MAP as a best arm identification task. We introduce probably approximately correct (PAC) algorithms for MAP that provide provably optimal solutions in both the fixed-confidence and fixed-budget regimes. We characterize tractability conditions using information theoretic measures that can be estimated from finite samples. Our PAC-MAP solvers are efficiently implemented using probabilistic circuits and graphical models with appropriate architectures. The algorithms we develop can be used either as standalone MAP estimators or to improve on standard heuristics, fortifying their solutions with rigorous guarantees. Experiments confirm the benefits of our method in a range of benchmarks.