AdaSwitch: An Adaptive Switching Meta-Algorithm for Learning-Augmented Bounded-Influence Problems

• URL: http://arxiv.org/abs/2509.02302v1
• Date: Tue, 02 Sep 2025 13:26:23 GMT
• Title: AdaSwitch: An Adaptive Switching Meta-Algorithm for Learning-Augmented Bounded-Influence Problems
• Authors: Xi Chen, Yuze Chen, Yuan Zhou,
• Abstract summary: We study a class of multi-period online decision-making problems with sequence-based predictions.<n>In each period, the decision-maker observes the realized request and must take an irrevocable action that yields a reward or incurs a cost.<n>We introduce a bounded-influence framework, in which past decisions and requests exert only limited impact on the future optimal reward.<n>Within this framework, we propose the AdaSwitch meta-algorithm, which exploits predictions to attain performance close to the offline benchmark when predictions are accurate.
• Score: 9.387255955861162
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a class of multi-period online decision-making problems with sequence-based predictions, which may be generated by machine learning models but whose accuracy is not guaranteed. In each period, the decision-maker observes the realized request and must take an irrevocable action that yields a reward or incurs a cost, without knowledge of future arrivals. We introduce a bounded-influence framework, in which past decisions and requests exert only limited impact on the future optimal reward. Within this framework, we propose the AdaSwitch meta-algorithm, which exploits predictions to attain performance close to the offline benchmark when predictions are accurate, while preserving classical competitive-ratio guarantees under highly inaccurate predictions. Our framework and meta-algorithm apply to diverse settings, including lead-time quotation in processing systems, the $k$-server problem, and online allocation of reusable resources. These applications illustrate the flexibility and broad applicability of our approach to learning-augmented online decision-making.

Related papers

• Deadline-Aware Online Scheduling for LLM Fine-Tuning with Spot Market Predictions [11.849924812127371]
  We show the power of prediction in enabling cost-efficient scheduling and its sensitivity to estimation errors.<n>We propose an online allocation algorithm with prediction based on the committed horizon control approach.<n>An online policy selection algorithm is developed that learns the best policy from a pool constructed by varying the parameters of both algorithms.
  arXiv  Detail & Related papers  (2025-12-24T05:47:27Z)
• Aligning Learning and Endogenous Decision-Making [5.84228364962637]
  We introduce an end-to-end method under endogenous uncertainty to train ML models to be aware of their downstream.<n>We also introduce a robust optimization variant that accounts for uncertainty in ML models.<n>We prove guarantees that this robust approach can capture near-optimal decisions with high probability as a function of data.
  arXiv  Detail & Related papers  (2025-07-01T15:22:56Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
  We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback.<n>It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time.<n>We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget
  arXiv  Detail & Related papers  (2025-06-16T08:42:31Z)
• A Minimax-MDP Framework with Future-imposed Conditions for Learning-augmented Problems [10.827221988826484]
  We study a class of sequential decision-making problems with augmented predictions, potentially provided by a machine learning algorithm.<n>In this setting, the decision-maker receives prediction intervals for unknown parameters that become progressively refined over time.<n>We propose a minimax Markov Decision Process (minimax-MDP) framework, where the system state consists of an adversarially evolving environment state and an internal state controlled by the decision-maker.
  arXiv  Detail & Related papers  (2025-05-02T03:28:35Z)
• Online Conformal Probabilistic Numerics via Adaptive Edge-Cloud Offloading [52.499838151272016]
  This work introduces a new method to calibrate the HPD sets produced by PLS with the aim of guaranteeing long-term coverage requirements.<n>The proposed method, referred to as online conformal prediction-PLS (OCP-PLS), assumes sporadic feedback from cloud to edge.<n>The validity of OCP-PLS is verified via experiments that bring insights into trade-offs between coverage, prediction set size, and cloud usage.
  arXiv  Detail & Related papers  (2025-03-18T17:30:26Z)
• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric. We propose a single framework built on their equivalence in learning scenarios. Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
  arXiv  Detail & Related papers  (2024-05-09T12:52:22Z)
• Online Algorithms with Uncertainty-Quantified Predictions [11.951228732915936]
  We investigate the problem of optimally utilizing uncertainty-quantified predictions in the design of online algorithms. In particular, we study two classic online problems, ski rental and online search, where the decision-maker is provided predictions augmented with UQ. We demonstrate that non-trivial modifications to algorithm design are needed to fully leverage the UQ predictions.
  arXiv  Detail & Related papers  (2023-10-17T20:09:41Z)
• Optimizing Credit Limit Adjustments Under Adversarial Goals Using Reinforcement Learning [42.303733194571905]
  We seek to find and automatize an optimal credit card limit adjustment policy by employing reinforcement learning techniques. Our research establishes a conceptual structure for applying reinforcement learning framework to credit limit adjustment.
  arXiv  Detail & Related papers  (2023-06-27T16:10:36Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Online Caching with no Regret: Optimistic Learning via Recommendations [15.877673959068458]
  We build upon the Follow-the-Regularized-Leader (FTRL) framework to include predictions for the file requests. We extend the framework to learn and utilize the best request predictor in cases where many are available. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions.
  arXiv  Detail & Related papers  (2022-04-20T09:29:47Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust. We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
  arXiv  Detail & Related papers  (2020-10-22T04:51:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.