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

Xi Chen; Yuze Chen; Shibo Dai; Yuan Zhou

cs.LGSep 2, 2025

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

Authors: Xi Chen, Yuze Chen, Shibo Dai, Yuan Zhou

Organizations: Yau Mathematical Sciences Center & Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China, Beijing Institute of Mathematical Sciences and Applications, Beijing 101408, China

Abstract

We study history-dependent online problems with a possibly inaccurate prediction of the future request sequence. Motivated by several real-world applications, we introduce a \emph{bounded-influence} framework in which past decisions and requests affect the future optimal value by only a bounded amount. Within this framework, we develop AdaSwitch, a meta-algorithm that adaptively switches between suitable offline and online oracles. AdaSwitch provides explicit guarantees on expected performance that tighten as prediction error decreases or the offline optimum increases. With perfect predictions, its guarantee approaches the offline oracle's guarantee as the offline optimum grows. It also retains a worst-case guarantee close to that of the online oracle under arbitrary predictions. Applications to online lead-time quotation, $k$ -server and caching, and online reusable resource allocation demonstrate the framework's applicability to both reward maximization and cost minimization.

Figures & tables

Figure 1 : Information flow and mode transitions in AdaSwitch.

Requirement	Exact-oracle variants	Approximate-oracle variants
Problem and sequence assumptions	Finite effective horizons under prefix replacement (Definition 3.1 ); $f$ -bounded influence (Definition 3.2 ); $(u,v)$ -Lipschitz condition (Definition 3.3 ).	Finite effective horizons under prefix replacement (Definition 3.1 ); $f$ -bounded influence (Definition 3.2 ); $(u,v)$ -strongly Lipschitz condition (Definition 3.4 ).
Prediction and planning endpoint	One request-sequence prediction revealed before period $1$ (p. 3 ); effective-horizon estimator (p. 3 ).	One request-sequence prediction revealed before period $1$ (p. 3 ); effective-horizon estimator (p. 3 ).
Oracle and simulation access	Exact fixed-history offline oracle (Definition 3.5 , $\gamma=1$ ); restartable online-oracle family (Definition 3.6 ).	$\gamma$ -approximate fixed-history offline oracle (Definition 3.5 ); restartable online-oracle family (Definition 3.6 ); resettable simulator (Section 11 ).

Table 1 : AdaSwitch requirements by offline-oracle regime.

\displaystyle\bm{a}^{*,(t)}_{t:\widehat{M}_{t}}\in\arg\max_{\bm{a}^{\prime\prime}_{t:\widehat{M}_{t}}\in\bm{A}_{t:\widehat{M}_{t}}}\mathrm{Val}\left(\mathcal{P}^{\mathcal{I}(t)},e_{t}\circ\bm{e}^{*}_{t+1:\widehat{M}_{t}},\bm{a}^{\prime\prime}_{t:\widehat{M}_{t}}\right).

(1)

Algorithm 1 AdaSwitch with an Exact Offline Oracle

\displaystyle\mathrm{Val}(\mathcal{P}^{\mathcal{I}(q)},\widetilde{\bm{e}}^{(q)}_{q:r},\bm{a}_{q:r})\geq\gamma\,\mathrm{Opt}(\mathcal{P}^{\mathcal{I}(q)},\widetilde{\bm{e}}^{(q)}_{q:r}).

Algorithm 2 AdaSwitch with a

\gamma

-Approximate Offline Oracle

Policy	Perfect-prediction guarantee at robustness $r$	Arbitrary-prediction guarantee
Q-FRACwP	$\beta(r)$	$r$
AdaSwitch-OLTQ	$\displaystyle\max\!\left\{r,\displaystyle 1-\frac{10\ell^{2}}{(\eta-r)\mathrm{Opt}_{\mathrm{pred}}}\right\}$	$\displaystyle\max\!\left\{r,\displaystyle 1-\frac{\ell(10\ell+7\eta\varphi_{M}^{*})}{(\eta-r)\mathrm{Opt}_{\mathrm{real}}}\right\}$
Here $\eta\overset{\text{\tiny def}}{=}\eta^{\mathrm{OLTQ}}$ , $\mathrm{Opt}_{\mathrm{pred}}\overset{\text{\tiny def}}{=}\mathrm{Opt}(\mathrm{OLTQ},\bm{e}^{}_{1:\infty})$ , $\mathrm{Opt}_{\mathrm{real}}\overset{\text{\tiny def}}{=}\mathrm{Opt}(\mathrm{OLTQ},\bm{e}_{1:\infty})$ , and, because clipping is inactive, $\varphi_{M}^{}=\sum_{t=1}^{M}\|e_{t}-e_{t}^{*}\|$ . The AdaSwitch entries are instance-dependent.

Table 2 : Q-FRACwP ( Huo and Cheung 2026 ) and AdaSwitch-OLTQ for sequences with a common known arrival horizon.

Figure 2 : Perfect-prediction OLTQwP performance as the guaranteed robustness target $r$ for AdaSwitch-OLTQ and Q-FRACwP varies. Higher ratios are better.

Figure 3 : Perfect-prediction CAwP performance as AdaSwitch-CA’s guaranteed robustness upper bound varies for $k=10$ . The comparator policies are independent of $\epsilon$ . Lower ratios are better.

Figure 4 : CAwP performance as the effective horizon increases. Lower ratios are better.

\displaystyle\bm{a}^{*,(t)}_{t:\widehat{M}_{t}}\in\arg\min_{\bm{a}^{\prime\prime}_{t:\widehat{M}_{t}}\in\bm{A}_{t:\widehat{M}_{t}}}\mathrm{Val}\!\left(\mathcal{P}^{\mathcal{I}(t)},e_{t}\circ\bm{e}^{*}_{t+1:\widehat{M}_{t}},\bm{a}^{\prime\prime}_{t:\widehat{M}_{t}}\right).

(33)

Algorithm 3 Changes to Algorithm 1 for cost minimization

C^{\mathrm{off}}_{\tau,t}\overset{\text{\tiny def}}{=}\mathrm{Val}(\mathcal{P}^{\mathcal{I}(\tau)},\bm{e}_{\tau:t},\bm{a}^{\mathrm{off}}_{\tau:t}).

Algorithm 4 Changes to Algorithm 2 for cost minimization

Method	Worst-case bound	Prediction-dependent bound
Blum–Burch	$(1+\delta)C_{B}+\mathcal{O}(k/\delta)$	$(1+\delta)C_{P}+\mathcal{O}(k/\delta)$
DART	$\begin{gathered}\min\bigl\{R_{\delta}C_{B},\\ (4+4/\delta)C_{B}+(4/\delta+2)k\bigr\}\end{gathered}$	$(1+\delta)C_{P}$
Exact-oracle AdaSwitch	$(\eta+\epsilon)\mathrm{Opt}$	$\mathrm{Opt}+A_{\epsilon}\bar{k}+B_{\epsilon}\varphi_{M}^{*}$

Table 3 : Expected cost bounds in the shared caching scenario.

Figure 5 : OLTQwP performance versus arrival horizon $T$ . Both panels use $p=0.1$ , $\ell=20$ , and $r=0.425$ . Higher ratios are better.

Figure 6 : OLTQwP performance under short bursts and random gaps. All panels use $T=20000$ , $p=0.1$ , $\ell=20$ , and $r=0.425$ . Higher ratios are better.

Figure 7 : CAwP performance under six prediction models. Lower ratios are better.

Explore similar work

Adapt Only When It Pays: Budgeted Decision-Loss Priority for Delayed Online Time-Series Adaptation
Jun 23, 2026Xibai WangTest-Time Adaptation Continual Test-Time Adaptation
NeuroQuant Labs Limited Hong Kong SAR, China
Linear Bandits under Exact Sliding-Window Constraints
Oct 6, 2026Seyed Mohammad Hadi Hosseini, Yasin Abbasi-Yadkori, Sattar VakiliMulti-Armed Bandits
Budgeted Online Influence Maximization
Apr 21, 2026Pierre Perrault, Jennifer Healey, Zheng Wen +1
Adobe Research, San Jose, CA · ENS Paris-Saclay · DeepMind +1

Jun 23, 2026, cs.LGJ/K move · Enter open · S save

Adapt Only When It Pays: Budgeted Decision-Loss Priority for Delayed Online Time-Series Adaptation

Xibai Wang

NeuroQuant Labs Limited Hong Kong SAR, China

Test-Time Adaptation Continual Test-Time Adaptation Time Series Forecasting Online Learning

Open paper AskPDF arXiv

Online time-series forecasters receive labels only after horizon-dependent delays, while every adaptation step spends limited compute. We study when an online learner should update, not how to adapt at every opportunity, and introduce ADOWIP: a residual-adapter framework with sealed delay queues, exact budget accounting, and auditable update telemetry. Its main scheduler is an observed decision-loss priority gate that updates only after feedback is revealed, when downstream loss, optionally penalized by prediction MSE, exceeds a calibrated empirical quantile and budget remains. We prove hard-budget feasibility, projected-OGD regret for a convex linear accepted-update subproblem, and stability plus conditional finite-sample gate-selection statements. On public ETT capacity-planning tasks, a frozen calibration/evaluation split selects a gate that lowers held-out decision loss against always, fixed-period, and drift-triggered exact-update baselines under matched compute. Secondary threshold/load-index ETT suites are mixed: 33 of 41 selected contrasts clear the stricter cross-artifact Holm family, and the 8 nonpassing rows are explicitly excluded from primary claims. The same protocol improves an external UCI Bike capacity proxy with 20/0 held-out wins, and a fixed gate passes three full-year Capital Bikeshare station-rebalancing contrasts. Probe-based and finance experiments remain negative, delimiting the current scope of decision-prioritized adaptation.

Abstract

Explore similar work

Adapt Only When It Pays: Budgeted Decision-Loss Priority for Delayed Online Time-Series Adaptation

Linear Bandits under Exact Sliding-Window Constraints

Budgeted Online Influence Maximization