Online Algorithms with Unreliable Guidance
This paper introduces online algorithms with unreliable guidance (OAG), a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic components, thus offering a single, well-defined analysis framework that depends only on the problem at hand. Formulated through the lens of request-answer games, the OAG model brings multiple concepts (predictions from the answer space, guide, anytime competitiveness) which enable learning-augmented algorithms to be analyzed independently of predictor-specific choices - such as prediction semantics, error functions, or probing strategies - that would otherwise restrict the algorithm's generality and applicability. The clean framework of the OAG model allows to build the first generic compiler, the drop-or-trust-blindly (DTB) compiler, that turns almost any standard, prediction-free online algorithm into a learning-augmented one. Although simple, we show that the DTB compiler produces new learning-augmented algorithms with strong consistency-robustness guarantees for three classic online problems: we achieve new trade-offs for bipartite matching with adversarial arrival order, and obtain optimal solutions for caching and uniform metrical task systems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LaGO: Latent Action Guidance for Online Reinforcement Learning
Large language models (LLMs) have shown strong potential for planning and sequential decision-making, but prior work often relies on using them as direct controllers, which requires precise action generation and can be u…
Reinforcement LearningLearning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift
Learning-augmented algorithms improve online decisions using predictions, but unreliable advice may harm efficiency and fairness. We study an online allocation problem with finite candidate sets, irreversible decisions, …
3D Path-Following Guidance via Nonlinear Model Predictive Control for Fixed-Wing Small UAS
This paper presents the design, implementation, and flight test results of two novel 3D path-following guidance algorithms based on nonlinear model predictive control (MPC), with specific application to fixed-wing small …
Nonlinear Model Based Guidance with Deep Learning Based Target Trajectory Prediction Against Aerial Agile Attack Patterns
In this work, we propose a novel missile guidance algorithm that combines deep learning based trajectory prediction with nonlinear model predictive control. Although missile guidance and threat interception is a well-stu…
Model Predictive ControlTrajectory Prediction3D Fragment Reassembly Using Integrated Template Guidance and Fracture-Region Matching
This paper studies matching of fragmented objects to recompose their original geometry. Solving this geometric reassembly problem has direct applications in archaeology and forensic investigation in the computer-aided re…