Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation

• URL: http://arxiv.org/abs/2606.24672v1
• Date: Tue, 23 Jun 2026 15:04:51 GMT
• Title: Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation
• Abstract summary: We present a branch-and-bound algorithm with variable-selections, pruning, and caching.<n>Experiments on random instances demonstrate scalability and quantify the efficiency-quality trade-off of a greedy beam-search variant.<n>We prove that the problem is $#P$-hard and contained in $mathrmSPACEP$.
• Score: 4.473327661758546
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many decision-making scenarios, acquiring information incurs different costs. We consider the problem of constructing a deterministic evaluation strategy that minimizes the expected cost of evaluating a propositional formula under variable costs and a probability distribution over truth assignments. We present a branch-and-bound algorithm with variable-selection heuristics, pruning, and caching. To the best of our knowledge, it is the first practical exact algorithm for this level of generality. Experiments on random instances demonstrate scalability and quantify the efficiency-quality trade-off of a greedy beam-search variant. We additionally evaluate a structured heart-disease diagnosis instance. Finally, we prove that the problem is $\#P$-hard and contained in $\mathrm{PSPACE}$.

Related papers

• Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
  We formalize this question as *budgeted heteroskedastic multi-judge estimation*.<n>Given $K$ prompt-response pairs, $J$ judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an $ell_p$-error.<n>We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget.
  arXiv  Detail & Related papers  (2026-05-22T08:26:08Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs [3.1269598124014264]
  We propose a novel algorithm for the extension of the BOCVS problem with random and unknown costs.<n>Our algorithm achieves a sub-linear rate in both quality regret and cost regret, addressing the objective of the BOCVS problem more effectively than previous analyses.
  arXiv  Detail & Related papers  (2024-12-20T13:00:39Z)
• A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization [4.608510640547952]
  We prove near-optimal optimization error guarantees for Dy Search. We show that the classical dependence on the global Lipschitz constant in the error bounds is an artifact of the granularity of the budget.
  arXiv  Detail & Related papers  (2022-08-13T19:57:04Z)
• Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
  In this paper, we design the first instance-optimal algorithm for general interactive decision making problems with finite number of decisions under mild conditions. Our results, instantiated on concrete problems, recover the classical gap-dependent bounds for multi-armed bandits and prior works on linear bandits.
  arXiv  Detail & Related papers  (2022-06-06T02:56:10Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Distributionally Robust Optimization with Markovian Data [8.126833795693699]
  We study a program where the probability distribution of the uncertain problem parameters is unknown. We propose a data-driven distributionally to estimate the problem's objective function and optimal solution.
  arXiv  Detail & Related papers  (2021-06-12T10:59:02Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.