Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization

• URL: http://arxiv.org/abs/2608.10650v1
• Date: Tue, 11 Aug 2026 08:34:28 GMT
• Title: Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization
• Abstract summary: We introduce a decision-aware approximation that targets the regret of the decision.<n>We prove a one-point bound that localises the regret at the true optimum.<n>In experiments the decision-aware compressor flips the decision less often than representation-aware compression.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reducing the number of focal elements of a mass function is classically driven by an intrinsic distance, such as Jaccard or Jousselme, that keeps the approximation close to the original as a body of evidence. We consider instead the case where the mass function feeds a linear combinatorial optimisation problem with evidential costs. What should then be preserved is not the closeness of the two mass functions, but the quality of the decision they induce. We introduce a decision-aware approximation that targets the regret of the decision: one decides with the cheaper approximation and is evaluated under the true mass function. On a minimal shortest path, the distance-optimal approximation flips the decision while a decision-aware merge preserves it, and this occurs on a non-negligible fraction of random instances. We prove a one-point bound that localises the regret at the true optimum, turn it into an exact dynamic program for the scalar case, and extend it to an online version that prunes focal elements before the final cost is known. In experiments the decision-aware compressor flips the decision less often than representation-aware compression, for both the linear criterion and a non-linear proxy read-out.

Related papers

• Finite Memory Belief Approximation for Optimal Control in Partially Observable Markov Decision Processes [1.614301262383079]
  We study finite memory belief approximation for partially observable (PO) optimal control (SOC) problems.<n>We develop a metric-based theory that directly relates information loss to control performance.
  arXiv  Detail & Related papers  (2026-01-06T16:05:20Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions [8.90721241624138]
  We consider an optimization problem with uncertainty dependent on decision variables.<n>In this problem, the gradient of the objective function cannot be obtained explicitly because the decision-dependent distribution is unknown.<n>Several zeroth-order methods have been proposed, which obtain noisy objective values by sampling and update the iterates.
  arXiv  Detail & Related papers  (2024-12-29T03:05:34Z)
• A Reliability Theory of Compromise Decisions for Large-Scale Stochastic Programs [0.0]
  This paper studies the reliability of programming solutions resulting from the "compromise decision" process. We quantify the reliability of compromise decisions by estimating the expectation and variance of the "pessimistic distance" of sampled instances from the set of true optimal decisions.
  arXiv  Detail & Related papers  (2024-05-16T19:33:00Z)
• A Hypervolume Based Approach to Rank Intuitionistic Fuzzy Sets and Its Extension to Multi-criteria Decision Making Under Uncertainty [0.0]
  Ranking intuitionistic fuzzy sets with distance based ranking methods requires to calculate the distance between intuitionistic fuzzy set and a reference point. This paper gives a mathematical proof of why this assumption is not valid for any of the non-linear distance functions. It suggests a hypervolume based ranking approach as an alternative to distance based ranking.
  arXiv  Detail & Related papers  (2022-12-25T11:57:04Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  Non-smooth non optimization problems emerge in machine learning and business making. Two core challenges impede the development of efficient methods with finitetime convergence guarantee. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results.
  arXiv  Detail & Related papers  (2022-09-12T06:53:24Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  One of the main queries on such models is to identify the SDPWCSP Function on Cost of a Posteri (MAP) Networks. We consider a traditional dualized constraint approach and a dedicated dedicated SDP/Monteiro style method based on row-by-row updates.
  arXiv  Detail & Related papers  (2021-11-24T13:38:34Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  We show that common optimization methods lead to poor variational approximations if the problem is moderately large. Motivated by these findings, we develop a more robust and accurate optimization framework by viewing the underlying algorithm as producing a Markov chain.
  arXiv  Detail & Related papers  (2020-09-01T19:12:11Z)
• Implicit differentiation of Lasso-type models for hyperparameter optimization [82.73138686390514]
  We introduce an efficient implicit differentiation algorithm, without matrix inversion, tailored for Lasso-type problems. Our approach scales to high-dimensional data by leveraging the sparsity of the solutions.
  arXiv  Detail & Related papers  (2020-02-20T18:43:42Z)

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.