Learning-Augmented Query Policies

Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter

Abstract

We study how to utilize (possibly machine-learned) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. The goal is to minimize the number of queries needed to solve the problem. We consider fundamental problems such as finding the minima of intersecting sets of elements or sorting them (these problems can also be phrased as (hyper)graph orientation problems), as well as the minimum spanning tree problem. We discuss different measures for the prediction accuracy and design algorithms with performance guarantees that improve with the accuracy of predictions and that are robust with respect to very poor prediction quality. These measures are intuitive and might be of general interest for inputs involving uncertainty intervals. We show that our predictions are PAC learnable. We also provide new structural insights for the minimum spanning tree problem that might be useful in the context of explorable uncertainty regardless of predictions. Our results prove that untrusted predictions can circumvent known lower bounds in the model of explorable uncertainty. We complement our results by experiments that empirically confirm the performance of our algorithms.

Introduction

In many real-world scenarios, the exact value of an input—such as the weight of a network link or a database entry—is hidden behind an expensive "query." Initially, we only know that the value falls within a specific uncertainty interval. The field of explorable uncertainty seeks to solve optimization problems (e.g., finding the minimum element or a Minimum Spanning Tree) using the fewest queries possible.

Historically, deterministic algorithms for these problems have been limited by a competitive ratio of 2, meaning they may require twice as many queries as an optimal algorithm with prior knowledge. This paper introduces "learning-augmented" policies that incorporate untrusted machine-learned predictions to break this classical barrier. The goal is to achieve high performance when predictions are accurate (consistency) while maintaining standard worst-case guarantees when they are not (robustness).

The Learning-Augmented Framework

The authors adopt a framework defined by $\alpha$-consistency and $\beta$-robustness. An algorithm is $\alpha$-consistent if its competitive ratio is $\alpha$ given perfect predictions, and $\beta$-robust if it never exceeds a ratio of $\beta$, regardless of prediction quality.

A key contribution is the proof that untrusted predictions allow for 1.5-consistent and 2-robust algorithms. This represents a 25% improvement over the best possible classical algorithms when predictions are correct, with no penalty for incorrect predictions. The proposed algorithms generally follow a two-stage process:

  1. Prediction-Mandatory Phase: Query elements that the ML model suggests are essential, cross-referencing them with "witness sets" (groups where at least one element must be queried) to prevent being misled.
  2. Cleanup Phase: Resolve remaining uncertainty using a vertex-cover approach on a dependency graph.

Structural Error Measures

Traditional numerical error metrics often fail to capture the structural impact of a prediction on a query policy. Instead, the authors propose new measures: Hop Distance ($k_h$) and Mandatory Query Distance ($k_M$).

Visualization of the Hop Distance ($h_i$) metric across different interval configurations.

As shown in the figure above, Hop Distance measures how many interval endpoints a prediction "jumps" over relative to the true value. This metric is more relevant because only crossings of interval boundaries change the optimal set of queries. Furthermore, the authors demonstrate that these structural error measures are PAC learnable, meaning models can be specifically trained to minimize them.

Experimental Evaluation

The algorithms were evaluated using two primary simulation environments:

  • The Minimum Problem: Complex overlapping interval sets were generated by re-interpreting Boolean Satisfiability (SAT) instances from the SATLIB library.
  • Minimum Spanning Tree (MST): Graphs from the TSPLIB (Traveling Salesman Problem Library) were used, with uncertainty intervals generated around true edge weights.

In over 230,000 simulations, the learning-augmented algorithms consistently outperformed the previous state-of-the-art "witness set" algorithm. The experiments confirmed "graceful degradation": as prediction error increases, performance slides smoothly toward the worst-case bound of 2 rather than failing abruptly.

Conclusion and Future Work

This research demonstrates that even untrusted predictions can significantly enhance query policies for fundamental optimization problems. While the current work focuses on exact solutions, future directions include exploring approximate query policies—where a small error in the final solution is traded for a large reduction in queries—and extending the model to stochastic settings where uncertain values follow known probability distributions.

Summary updated

Abstract

We study how to utilize (possibly machine-learned) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. The goal is to minimize the number of queries needed to solve the problem. We consider fundamental problems such as finding the minima of intersecting sets of elements or sorting them (these problems can also be phrased as (hyper)graph orientation problems), as well as the minimum spanning tree problem. We discuss different measures for the prediction accuracy and design algorithms with performance guarantees that improve with the accuracy of predictions and that are robust with respect to very poor prediction quality. These measures are intuitive and might be of general interest for inputs involving uncertainty intervals. We show that our predictions are PAC learnable. We also provide new structural insights for the minimum spanning tree problem that might be useful in the context of explorable uncertainty regardless of predictions. Our results prove that untrusted predictions can circumvent known lower bounds in the model of explorable uncertainty. We complement our results by experiments that empirically confirm the performance of our algorithms.
BibTeX
@misc{erlebach2020learning,
  author = {Thomas Erlebach and Murilo Santos de Lima and Nicole Megow and Jens Schlöter},
  title = {{Learning-Augmented Query Policies}},
  year = {2020},
  eprint = {2011.07385},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.07385},
}
Figure