Many systems solve a long stream of related optimization problems. Examples are a scheduler re-solving a placement problem every few seconds, a planner re-planning as the world changes, and a dynamic benchmark whose landscape shifts every few thousand evaluations. The standard way to pick a solver for each problem is per-instance algorithm selection: look at the instance, predict which solver in a portfolio will be fastest, and run it. Each choice is treated as independent. On a drifting stream that assumption is false. A solver that just ran on problem $t$ holds a warm start for problem $t+1$: a population, an incumbent solution, learned clauses, a loaded container. Choosing solver A now makes A cheap next time and lets the warm state of solver B go stale. Solver selection on a correlated stream is therefore a sequential decision problem, a Markov decision process (MDP: states, actions, and transitions that the actions influence). It is not the one-shot or bandit problem the literature treats it as.
The core claim is that the value of running a solver is its immediate cost plus the warm state it leaves behind. We propose to capture this with a small state: one staleness number per solver, recording how far the stream has drifted since that solver last ran, together with the remaining compute budget and the queue backlog. A policy trained on that state should beat both greedy online selectors and budget-aware bandits, but only at intermediate drift rates. If problems are nearly independent, warm state is worthless and the problem collapses to a bandit. If they are nearly identical, "always continue the current solver" is enough. That inverted-U prediction is the experiment that decides whether the idea holds.
What exists and what is missing
Three lines of work come close, and each drops one ingredient.
Selection within a single run. Dynamic algorithm configuration casts solver or heuristic switching as a contextual MDP. Learning Heuristic Selection with Dynamic Algorithm Configuration switches FastDownward heuristics per expansion step and reaches 505.1/600 coverage, against 488.2 for round-robin alternation. DACBench standardizes such tasks. In both, the MDP lives inside one run on an instance drawn from a stationary generator. There is no stream, no drift between instances, and no shared budget across them. We move the MDP up one level: the decision is made between instances, and the coupling comes from warm state that carries over.
Online selection on a stream. Online Algorithm Selection treats this as a contextual bandit on ASlib streams. A greedy online regression-forest selector beat the offline selector in 15 of 18 scenarios, and ε-greedy and UCB exploration often did worse than offline. This paper motivates ours: it shows that online updating helps when the stream drifts. It is also a direct competitor, since its bandit formulation is correct whenever instances are uncoupled. ASlib instances are uncoupled, which is why we cannot use ASlib to test our claim.
Budgeted control on a time-varying stream. Cost Optimization for Serverless Edge Computing with Budget Constraints using DRL runs DQN and PPO on raw capacity state over 141 days of Huawei traces. It stays within a cost factor of 1.03 of an ILP solver that needs more than 24 hours. Its cold-start cost is exactly a warm-state effect, but its actions are placements, not solver choices.
Two further lines play different roles.
Time-varying optimization supplies the intuition. Prediction-correction methods show that discarding the previous iterate wastes the temporal correlation between consecutive problems. λ-DGREEDY shows the same thing combinatorially: backtracking from the previous greedy path beats restarting when knapsack budgets change. Both concern one algorithm; neither chooses among warm-startable solvers.
State compression supplies the justification for our small state. The full state, meaning every solver's internal memory, explodes in dimension. Metrics for Finite MDPs bounds value differences by a bisimulation distance, a measure of how differently two states behave in reward and transitions. If a solver's warm-start benefit depends on its internal state only through how far the instance has drifted, then states with equal staleness profiles are near-bisimilar and can be merged with bounded value loss. We do not compute Kantorovich metrics, which that paper notes are expensive. We test the bisimulation assumption empirically and use it to motivate the compression.
Core formulation
At stream step $t$ the state is $$s_t = (\delta_t^{1},\dots,\delta_t^{K},\, b_t,\, q_t,\, \phi_t).$$ Here $\delta_t^{k}$ is the drift accumulated since solver $k$ last ran, estimated from cheap instance features or from changes in the observed objective. $b_t$ is the remaining compute budget for the horizon, $q_t$ is the queue backlog, and $\phi_t$ is the usual instance feature vector. The action picks a solver $k$ and a mode, either warm-continue or cold-restart. Running $k$ resets $\delta^k$ to zero, lets the other staleness values grow, and draws its cost from $b_t$.
The policy maximizes cumulative solution quality subject to the budget: $$\max_\pi \; \mathbb{E}\Big[\sum_{t} \gamma^t\, r(s_t,a_t)\Big] \quad \text{s.t.} \quad \sum_t c(s_t,a_t) \le B.$$ In this objective, $r$ is negative solution error or time-to-target, $c$ is compute cost, $\gamma$ is a discount factor between 0 and 1 that weights near-term quality more heavily, and $B$ is the total budget.
We handle the budget constraint with the same Lagrangian multiplier the bandit baseline uses. This keeps the comparison focused on whether lookahead over warm state helps.
Research Program
We build stream environments in which warm-start coupling is a tunable dial. We then train small value-based and PPO policies on the compressed state and compare them against the baselines below while varying drift rate and budget tightness.
The analysis has two parts. First, we measure how well staleness predicts warm-start benefit, which is the empirical bisimulation check: two solver states with equal $\delta$ should yield similar next-step costs. Second, we inspect whether the learned policy has threshold structure, in the spirit of the threshold optimality found by Yang et al.. If the optimal policy is a simple staleness threshold, that is itself a useful result: it would give a cheap rule with a learned justification.
Baselines
Naive references. The first is the single best solver run cold on every instance. The second is "always warm-continue the solver that ran last," a fixed solver with prediction-correction-style continuation. These bracket the problem from the uncoupled and fully coupled ends.
Strongest existing method. This is the greedy online regression-forest selector of Online Algorithm Selection. We augment it with two things: a primal-dual budget multiplier in the style of Liu et al., and the warm/cold mode as part of each arm. With both additions it can see that a warm solver is cheap now; what it lacks is any account of what each choice does to future warm states. Its reported result is outperforming the offline selector in 15 of 18 ASlib scenarios. There is no reported result on Lacuna for it on GMPB or on drifting MILP streams, so we will run it ourselves. It gets the same features plus the current $\delta$ values as context, the same budget, and the same hyperparameter-search budget as our policy, 50 configurations each. Beating it means a statistically significant improvement in offline error or time-to-target at equal budget use, across at least 10 seeds, in the intermediate-drift regime.
Sliding-window bandit. This is a sliding-window UCB selector following Zhou, with its window tuned on the same budget. It addresses drift without lookahead.
Raw-state deep RL. This is PPO on the uncompressed state, meaning solver population statistics and all features, as in the serverless DRL work. It tests whether the compression matters.
Ablations. One removes the $\delta$ features from our policy. A second sets $\gamma=0$, which turns our policy into a budgeted bandit. Together they isolate lookahead over warm state.
Why not just…?
Why not just use a greedy online selector with a budget multiplier? This is the main threat. When instances are uncoupled it is essentially optimal, and Degroote's finding that greedy beats exploration suggests that simple rules go far. It fails in one specific situation: keeping a second solver's warm state fresh is an investment that only pays off several steps later, and a myopic selector never makes that investment. The $\gamma=0$ ablation together with the drift sweep settles the question. If the advantage does not appear at intermediate drift, the claim is wrong.
Why not just stick with the current solver until drift exceeds a threshold? This rule could plausibly match us with two solvers. It cannot decide which of several stale warm states to refresh, and it ignores the budget. We include a tuned version of it. If it matches the learned policy, we report that the optimal structure is a threshold and recommend the rule.
Why not just run deep RL on the raw state? The DACBench profiling reports that tasks with large state and action spaces and high noise, such as CMA-ES and ModEA, are particularly hard. Raw solver internals add exactly that kind of noise. The raw-state PPO baseline at equal sample budget measures whether compression buys sample efficiency.
Proposed Experiments
Primary testbed. We use the Generalized Moving Peaks Benchmark with dimensions 5–20 and change intervals of 1,000 to 10,000 evaluations, which act as the coupling dial. The portfolio is four optimizers, including CMA-ES, each with warm and cold modes, under a total evaluation budget. Metrics are offline error and best-error-before-change. No reported result was found on Lacuna for portfolio selection on GMPB.
Combinatorial testbed. We use dynamic knapsack submodular streams on the FLIC and Berkeley Earth tasks (Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings). The portfolio is λ-DGREEDY with backtracking, restarted λ-GREEDY, and a cold continuous-relaxation method.
Systems-flavored testbed. We generate drifting Set Covering and Combinatorial Auctions MILP streams from Ecole generators and solve them with SCIP, warm-starting each solve from the previous incumbent. Arrival times come from the Huawei invocation traces, so that queue backlog and budget matter.
Decisive checks. The first is the inverted-U. Plotting our policy's gain over the strongest baseline against drift rate should show near-zero gain at both extremes and a peak in between. A flat or monotone curve refutes the warm-state account. The second is the bisimulation check. The correlation between staleness and the realized warm-start benefit must be high, and merged states should differ little in observed returns; if not, the compression is unjustified and the raw-state baseline should win. The third is budget tightness. The gain should grow as $B$ shrinks, because refreshing warm state is the action that becomes most costly to get wrong.
References
- Learning Heuristic Selection with Dynamic Algorithm Configuration
- DACBench: A Benchmark Library for Dynamic Algorithm Configuration
- Online Algorithm Selection
- Cost Optimization for Serverless Edge Computing with Budget Constraints Using Deep Reinforcement Learning
- Prediction-correction methods for time-varying convex optimization
- Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings
- Metrics for Finite Markov Decision Processes
- Traffic-aware transmission mode selection in D2D-enabled cellular networks with token system
- Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints
- No-Regret Algorithms for Time-Varying Bayesian Optimization
- Generalized Moving Peaks Benchmark