When dealing with complex, high-stakes computational problems—such as verifying the safety of a deep neural network, calculating reachability in continuous stochastic systems, or planning in infinite-horizon reinforcement learning—exact computation is often mathematically or computationally intractable. Traditional approximation methods, like Monte Carlo sampling, provide point estimates but lack rigorous guarantees. If you stop a sampling algorithm early, you are left with an estimate of unknown accuracy.
An elegant alternative is to "sandwich" the true, intractable value between a lower bound and an upper bound, forming a valid interval. Crucially, rather than computing this interval just once, we can use an iterative process where the lower bound monotonically increases and the upper bound monotonically decreases over time.
This paradigm shifts our computational objective: instead of waiting indefinitely for a single exact answer, we progressively squeeze the uncertainty interval. This approach guarantees that at any point during execution, we possess a mathematically valid safety envelope that continuously shrinks until we choose to stop.
Iteration 1: [L_1 --------------------------------------- U_1]
Iteration 2: [L_2 ----------------------- U_2]
Iteration 3: [L_3 ------------- U_3]
^
True Value (V*)
Why It Works: The Mechanics of Refinement
To tighten an interval without violating its mathematical validity, each iteration must incorporate finer-grained information or more expressive representations while preserving the bounding property. Across different domains, researchers achieve this through three primary mechanisms:
1. Hierarchical Partitioning of State Spaces
In systems with continuous variables or time horizons, uncertainty often stems from the sheer size of the continuous space. By systematically splitting these spaces into smaller sub-regions, we can compute local bounds that aggregate into tighter global bounds.
For example, in hybrid probabilistic logic programming, Michels et al. introduce an anytime refinement strategy that iteratively splits the most significant continuous variable ranges. As the algorithm partitions the continuous space into finer intervals, the gap between the upper and lower probability estimates narrows predictably. Similarly, when analyzing continuous-time Markov chains with imprecise observation times, Badings et al. progressively refine time partitions within an Interval Markov Decision Process (iMDP), systematically driving down uncertainty.
2. Monotonic Contractive Operators
In decision-making frameworks like Reinforcement Learning (RL), value functions can be bounded using iterative operators analogous to standard value iteration. By designing these operators to be monotonic, each update is guaranteed to shrink the interval envelope.
To optimize infinite-horizon planning in Bayesian RL, Lee et al. perform value iterations using modified transition dynamics, ensuring that the resulting value estimates remain valid while reducing approximation error step-by-step. For off-policy evaluation, Tang et al. leverage the Lipschitz continuity of value functions to construct monotonic update procedures, providing reliable performance envelopes at any point during computation. This concept is also powerful for policy transfer; Vora applies iterative refinement to Q-value bounds to safely prune suboptimal actions, guaranteeing that optimal actions are never accidentally discarded.
3. Increasing Model Complexity
When bounding a complex system, one can start with a simple, highly restricted approximation and gradually increase its complexity.
This principle underpins early work in knowledge compilation by Selman et al., who sandwich a complex logical theory between a stronger lower bound and a weaker upper bound using Horn approximations. In control theory, Ang et al. calculate the minimum dwell time required to guarantee the stability of switched linear systems. They generate a sequence of non-increasing upper bounds by iteratively increasing the complexity and number of components in a piecewise quadratic Lyapunov function.
The Anytime Property and Retrospective Computing
The most significant practical benefit of monotonic interval refinement is that it naturally yields anytime algorithms. Because the bounds are guaranteed to be valid at every intermediate step, the computation can be safely interrupted at any moment to return the best available interval with a known level of precision.
This behavior enables what Li et al. term retrospective computing. In many applications, we do not actually need to know the exact value of a variable; we only need to make a reliable decision based on a threshold. For instance, if we need to verify whether a system's failure probability is below a safety threshold $\theta$, we can stop the algorithm the moment the upper bound $U$ drops below $\theta$.
Iteration t: [L_t ----------- U_t] | Threshold (θ)
|
Iteration t+1: [L_t+1 --- U_t+1] | <-- STOP! Safe to terminate early.
Li et al. leverage this property using Gauss-type quadrature to bound bilinear matrix inverse forms, achieving up to 1,000x speedups by terminating as soon as a clear decision can be made. Similarly, Wu et al. apply anytime interval estimation to evaluate the global robustness of deep neural networks under the Hamming distance, allowing users to halt the evaluation once the provable precision reaches an acceptable threshold.
A Shared Tool Across Diverse Domains
While the mathematical tools vary—ranging from semidefinite programming to formal logic—the core intuition of iterative bound refinement remains remarkably consistent across computer science:
- Logic and Knowledge Compilation: Expanding on classical theory approximation, Bogaerts et al. utilize approximation fixpoint theory to compile logic programs with negation. They demonstrate that the well-founded induction process naturally functions as an anytime algorithm, providing valid intermediate bounds for large or complex logical structures.
- Stochastic and Continuous Systems: For complex stochastic processes where exact integration is impossible, Ottobre et al. use semidefinite programming to compute stationary averages of polynomial diffusions, producing sequences of decreasing upper bounds and increasing lower bounds. For continuous state-space planning, Grover et al. provide the first anytime procedures for reachability probabilities in uncountable Markov Decision Processes.
- Probabilistic Networks and Verification: The strategy is equally effective for structural reasoning. Liu et al. exploit qualitative relationships between variables to efficiently bound probability distributions in Bayesian networks. When the underlying transition model must be learned from data, Ashok et al. introduce Probably Approximately Correct (PAC) statistical model checking for MDPs and stochastic games, delivering valid confidence intervals that narrow progressively as more samples are collected.
By focusing on narrowing the envelope of what could be true, iterative interval refinement provides a mathematically rigorous bridge between theoretical correctness and finite computational resources.
Key Foundational Work
Using Qualitative Relationships for Bounding Probability Distributions (1998) — contributed 1 concept elements to this direction.
Knowledge Compilation using Horn Approximations (1991) — contributed 1 concept elements to this direction.