Decision-Theoretic Approaches in Learning-Augmented Algorithms
In this work, we initiate the systemic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, as well as stochastic measures that allow us to balance the trade-off between the algorithm's performance and the risk associated with the imperfect oracle. These approaches help us quantify the algorithmic performance across the entire spectrum of prediction error, unlike several previous works that focus on few, and often extreme values of the error. We apply these techniques to two well-known problems from resource allocation and online decision making, namely contract scheduling and 1-max search.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingSchedulingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictors
A wide range of sustainability and grid-integration strategies depend on workload shifting, which aligns the timing of energy consumption with external signals such as grid curtailment events, carbon intensity, or time-o…
Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms
We introduce the Smoothed Online Optimization for Target Tracking (SOOTT) problem, a new framework that integrates three key objectives in online decision-making under uncertainty: (1) tracking cost for following a dynam…
On the Learning with Augmented Class via Forests
Decision trees and forests have achieved successes in various real applications, most working with all testing classes known in training data. In this work, we focus on learning with augmented class via forests, where an…
State-Augmented Learnable Algorithms for Resource Management in Wireless Networks
We consider resource management problems in multi-user wireless networks, which can be cast as optimizing a network-wide utility function, subject to constraints on the long-term average performance of users across the n…
Graph Neural NetworkManagementBelief Projection-Based Reinforcement Learning for Environments with Delayed Feedback
We present a novel actor-critic algorithm for an environment with delayed feedback, which addresses the state-space explosion problem of conventional approaches. Conventional approaches use an augmented state constructed…