Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization

The paper introduces a decision-aware approximation method for belief functions used in evidential combinatorial optimization, where the goal is not to keep the approximation close to the original mass function by an intrinsic distance (such as Jaccard or Jousselme), but to preserve the quality of the downstream decision. The authors state: "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."

The core contribution is the definition of approximation regret: R(m̂) = Crit(x⋆(m̂); m) − Crit(x⋆(m); m) ≥ 0, where one decides with the approximation m̂ but is evaluated under the true mass function m. The paper proves a one-point bound: R(m̂) ≤ ∆(x⋆(m)) for any monotone approximation, meaning the regret is controlled by the distortion at the single true optimum. The proof relies on the fact that Since x̂ minimises Crit(·; m̂), Crit(x̂; m̂) ≤ Crit(x⋆; m̂) and uses the monotonicity ∆(x) ≥ 0.

The paper provides a minimal shortest-path example (a diamond graph with three focal boxes) showing that the distance-optimal approximation flips the decision while a decision-aware merge preserves it. In this example, merging boxes A2 and A3 is the most similar by both Jaccard and Jousselme measures, yet it changes the decision (regret R = 1.4), while the other two safe merges keep the decision unchanged (R = 0).

For the algorithmic side, the paper gives an exact dynamic program for the scalar case: the grouping of the N focal boxes into K groups that minimises w⊤(c̄(m̂) − c̄(m))... is found exactly in O(N2K). The proof sorts boxes by their relevant bound and shows an optimal grouping uses contiguous blocks, leading to the recurrence D[j, K] = min i≤j D[i−1, K−1] + cost(i, j) with cost(i, j) = a j W(i, j).

The paper also extends to an online version: At step t, with mt the accumulated belief and m̂t its compression to K boxes, the compressor picks the K-grouping minimising wt(c̄(m̂t)−c̄(mt)), where wt ≥ 0 is a local sensitivity of the decision. This is needed because along a path the cost so far is built by combining the edge beliefs, and the focal count grows fast, so we must compress before the final cost, hence before the true optimum, is known.

Experiments use random shortest-path instances (2500 per study, 5 seeds). In the static study at K=2, the decision-aware Bound-DA changes the decision in only 2.5% of cases, versus 13.6% for Jousselme, 16.9% for Jaccard, 14.2% for largest-mass, and 18.0% for random safe merge. The mean regret for Bound-DA is 0.010 versus 0.085–0.143 for baselines, and its 95th-percentile regret is 0.00 versus 0.67–1.04. Bound-DA nearly matches the non-deployable Oracle-DA (1.8% decision changes). The paper notes: "Bound-DA nearly matches the Oracle-DA lower bound, changes the decision about six times less often than the representation-aware methods, and has smaller mean and tail regret, at the price of less faithfulness (larger dJou)."

In the online study, under the linear read-out, Online-DA changes the decision least at every K (11.1% at K=2, 6.0% at K=3, 4.5% at K=4) compared to greedy-Jousselme (13.8%, 9.4%, 7.0%), Jaccard (16.9%, 12.2%, 8.6%), largest-mass (17.3%, 14.8%, 13.0%), and random (18.6%, 17.4%, 16.0%). Under the non-linear read-out (plausibility of exceeding a budget), Online-DA ties greedy-Jousselme (19.6% vs 21.1% at K=2, 10.5% vs 10.8% at K=3, 7.0% vs 6.5% at K=4) but remains well below mass-based and random baselines.

The paper concludes: "We proposed a decision-aware way to approximate a belief function that feeds a combinatorial decision: control the decision regret rather than an intrinsic distance, via a one-point bound, an exact scalar dynamic program, and an online version. Two open points are noted: exact grouping in the vector case is not one-dimensional clustering (our scalar program is then a projection heuristic), and the monotonicity behind Theorem 1 is only conjectured for a minimax regret criterion. The approach is general: Theorem 1 needs only a criterion monotone under the safe merge over x ∈ X ⊆ 0,1 n, and the scalar program depends on the focal count, not on X. Any linear evidential 0–1 problem, such as knapsack or assignment, fits the same template with its own deterministic solver."

Improvements to AI Systems:

1. Decision-Aware Compression for Resource-Constrained Inference

• What: Replace intrinsic-distance-based belief compression (e.g., Jaccard/Jousselme) in evidential AI systems with a regret-minimizing approximation that preserves downstream decision quality.

• Improved system: An AI that, when forced to reduce belief-state complexity (e.g., limited memory, bandwidth, or real-time constraints), selects the compression that minimizes worst-case decision regret rather than maximizing representational fidelity. This yields up to 6x fewer decision flips and ** 10x lower mean regret** in combinatorial tasks (e.g., shortest-path, knapsack, assignment) compared to current methods.

2. One-Point Regret Bound for Safe Approximations

• What: Use the theorem R(m̂) ≤ ∆(x⋆(m)) to certify that any monotone approximation is safe if distortion at the true optimum is bounded.

• Improved system: An AI that, before deploying a compressed belief model, computes the distortion at the current optimal decision and automatically rejects or adjusts the compression if the bound exceeds a user-defined risk threshold. This provides provable safety guarantees in mission-critical applications (e.g., autonomous navigation, medical diagnosis) without exhaustive search.

3. Exact Dynamic Programming for Scalar Belief Grouping

• What: Apply the O(N2K) dynamic program to optimally merge focal boxes in scalar-cost evidential problems (e.g., shortest path with scalar edge costs).

• Improved system: An AI that, in real-time, finds the globally optimal K-grouping of belief masses for linear cost functions, eliminating heuristic clustering errors. This enables exact decision-aware compression in embedded systems where N (focal elements) grows rapidly (e.g., sensor fusion over time).

4. Online Decision-Aware Compression for Streaming Beliefs

• What: Use the online variant (Online-DA) that compresses accumulated beliefs at each step using local sensitivity weights w t, avoiding the need to know the final optimum in advance.

• Improved system: An AI that processes streaming evidence (e.g., robot SLAM, financial time-series) and continuously maintains a K-box belief approximation that minimizes future decision regret. This reduces decision changes by ** 30–50%** compared to greedy intrinsic-distance methods, while keeping memory bounded.

5. Generalizable Template for Any Linear Evidential 0–1 Problem

• What: Port the framework to other combinatorial problems (knapsack, assignment, matching) by swapping the deterministic solver.

• Improved system: A modular AI library where any linear objective over binary decisions with evidential costs can plug in a solver (e.g., branch-and-bound, MILP) and automatically get decision-aware compression. This enables cross-domain deployment without redesigning the approximation logic.

6. Regret-Aware Active Learning and Exploration

• What: Use the regret bound to decide which evidence to acquire next—prioritize queries that reduce distortion at the current optimal decision, not global uncertainty.

• Improved system: An AI that, during active learning, selects the most decision-critical belief updates, leading to faster convergence to high-quality decisions with fewer samples, especially in high-dimensional evidential spaces.

7. Robustness to Non-Linear Decision Criteria

• What: Extend the monotonicity condition to non-linear criteria (e.g., plausibility of exceeding a budget) via the conjectured minimax regret bound.

• Improved system: An AI that handles risk-averse or threshold-based decisions (e.g., "probability of cost > budget") with decision-aware compression, matching the performance of greedy-Jousselme while still outperforming mass-based baselines—enabling safe deployment in risk-sensitive domains like finance or disaster response.

8. Benchmarking and Validation Framework

• What: Adopt the paper’s experimental protocol (random instances, 5 seeds, regret percentiles) to evaluate any new belief-compression method.

• Improved system: A standardized evaluation harness for AI systems using evidential reasoning, allowing researchers to compare decision regret (not just distance) across methods—accelerating progress toward decision-centric AI.