  In many domains, worst-case guarantees on the performance (e.g., prediction
accuracy) of a decision function subject to distributional shifts and
uncertainty about the environment are crucial. In this work we develop a method
to quantify the robustness of decision functions with respect to credal
Bayesian networks, formal parametric models of the environment where
uncertainty is expressed through credal sets on the parameters. In particular,
we address the maximum marginal probability (MARmax) problem, that is,
determining the greatest probability of an event (such as misclassification)
obtainable for parameters in the credal set. We develop a method to faithfully
transfer the problem into a constrained optimization problem on a probabilistic
circuit. By performing a simple constraint relaxation, we show how to obtain a
guaranteed upper bound on MARmax in linear time in the size of the circuit. We
further theoretically characterize this constraint relaxation in terms of the
original Bayesian network structure, which yields insight into the tightness of
the bound. We implement the method and provide experimental evidence that the
upper bound is often near tight and demonstrates improved scalability compared
to other methods.
