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

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.

We study linear bandits under exact sliding-window constraints, where every consecutive block of actions must belong to a prescribed feasible set. In the offline setting, where the reward function is known, we show that convexity and cyclic-shift invariance make a stationary solution optimal when $w\mid T$ and within an additive $O(w)$ gap otherwise. In the online setting, we show that geometric structure alone is insufficient for learning, and sublinear regret can be impossible. We introduce a transition diameter $τ$ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret $\widetilde{O}(d\sqrt{T}+τd+w)$ against the offline-optimal feasible trajectory. Finally, we remove cyclic invariance and consider general sliding-window constraints, where optimal behavior may be non-stationary. We represent recent action history as the state of a finite-memory control problem and introduce a history-state diameter $D$ that measures feasible communication between viable histories. Combining optimistic remaining-horizon planning with rare policy updates, we obtain a regret bound of $\widetilde{O}(d\sqrt{T}+dD+w)$. We evaluate our approach on real-world and synthetic benchmarks, showing that it maintains exact feasibility while achieving reward and regret comparable to baselines with substantially fewer policy updates.

We introduce a new budgeted framework for online influence maximization, considering the total cost of an advertising campaign instead of the common cardinality constraint on a chosen influencer set. Our approach better models the real-world setting where the cost of influencers varies and advertisers want to find the best value for their overall social advertising budget. We propose an algorithm assuming an independent cascade diffusion model and edge level semi-bandit feedback, and provide both theoretical and experimental results. Our analysis is also valid for the cardinality constraint setting and improves the state of the art regret bound in this case.