Module dehb 

DEHB — Differential-Evolution Hyperband, the low-budget black-box tuner for RL.

DEHB is the method the RL-HPO literature singles out as the best cheap black-box tuner — “DEHB with 64 runs beat a 810-run grid” in the ICML-2023 study — which is what earns it a slot here. It marries two ideas:

• Hyperband provides the multi-fidelity schedule: a set of successive- halving brackets over a geometric ladder of resource levels (fidelities). Each bracket allocates configurations to a low fidelity and promotes the best 1/η to the next. This is the very machinery M3.1 built for AshaPruner/HyperbandPruner: Dehb reuses RungLadder for the fidelity ladder and the same successive-halving bracket arithmetic.
• Differential evolution replaces the random configuration generation plain Hyperband/BOHB use: DEHB keeps a DE subpopulation per fidelity, and a new configuration for a fidelity is bred by DE mutation + crossover from that subpopulation, seeded across fidelities so a higher budget’s population is grown from the survivors of the lower ones.

In atune DEHB is a Sampler — it generates configurations — designed to be paired with a HyperbandPruner that does the actual multi-fidelity gating over the same ladder. Each atune trial is one DEHB job: one configuration bred for one target fidelity.

The algorithm, precisely

Everything operates in the transform-layer unit hypercube [0, 1]^d (d = SpaceSchema::len), so a single DE implementation covers every distribution kind — the mapping to the declared support is Distribution::from_unit, applied once when the config is assigned. The operators live in the de module and are unit-tested on hand-computed vectors.

Fidelity ladder and bracket schedule

From (min_fidelity, max_fidelity, η) a RungLadder yields the geometric rungs strictly below the maximum; the fidelities are those rungs plus the maximum: min·η⁰, min·η¹, …, max, indexed 0..n_fid. The Hyperband brackets are the standard ones: bracket iteration it uses fidelity s = n_fid − 1 − (it mod n_fid), running successive halving over the top s + 1 fidelities with n₀ = ⌊n_fid/(s+1)⌋·ηˢ configurations at its entry rung, ⌊n₀·η⁻ⁱ⌋ at rung i. Bracket 0 is the widest (the full ladder, most aggressive early stopping); bracket n_fid − 1 runs n_fid configurations straight at the maximum (no early stopping) — it is the joint most expensive bracket, not the cheapest, which matters when sizing a budget from this. atune drives the schedule with an explicit bracket iteration (a stateful cursor), not the storage-free crc32 assignment bracket_of — because the per-fidelity DE populations are themselves state DEHB has to carry, so the cursor rides in that same state.

Per-fidelity DE populations and the cross-budget flow

One DE subpopulation of fixed size pop_size[i] (the max configurations that fidelity takes across a Hyperband cycle, capped so the whole population stays inside MAX_TOTAL_POP_SIZE) is kept per fidelity i, each individual a unit vector with an associated fitness (None until evaluated). A job at fidelity i selects a target by a round-robin parent counter over that subpopulation and produces a child:

• Promotion (only in the first Hyperband cycle, and only above a bracket’s entry rung): copy the best evaluated configuration from the lower fidelity i − 1 that is not already in fidelity i — a warm continuation of a promising low-budget config at higher budget.
• DE evolution (otherwise): the mutation donor pool is the top num_configs survivors of the lower fidelity by fitness (filled with fresh uniform vectors when short of the three rand/1 needs — the degenerate under-filled case). Three distinct donors give a rand/1 mutant x_r1 + F·(x_r2 − x_r3); binomial crossover at rate CR mixes it with the target; a BoundaryFix pulls any stray coordinate back into [0, 1].

That “donors from the previous fidelity” rule is the DEHB modified-DE flow: a fidelity’s population is bred from the fidelity below it, so information earned cheaply at low budget propagates upward.

Selection

When a trial finishes, its objective (direction-normalized to a loss where smaller is better) competes against the fitness of the slot its config targeted: child replaces the slot iff loss ≤ slot_fitness (the ≤ is deliberate — accepting equals keeps the population moving across flat regions, Storn & Price). A non-finite loss — NaN or ±∞, the conventional report of a diverged or infeasible run — never replaces anything, so no fitness the populations hold can fail to survive the JSON state blob (see State below).

Selection is only applied to a trial that actually evaluated the bred configuration. A trial created from a TrialTemplate — enqueued, retried or forked — still passes through sample_relative (the study loop samples every trial), but the loop’s suggest-priority chain then hands the objective the template’s fixed values, not the bred ones. Writing that trial’s loss onto the bred vector would record a fitness for a point nobody ran, and then breed donors from it. So after_trial re-derives the evaluated point from the trial’s recorded parameters and drops the job — without selecting — whenever it differs from the vector the job was bred with.

Promotion as warm continuation

A promotion to a higher fidelity is a warm restart of a config at a bigger budget. On an executor that supports it this is the M4.0 fork/checkpoint resume; on one that does not (oniro today) it is a fresh higher-budget evaluation. Dehb generates the configuration and records each job’s target fidelity (Dehb::target_fidelity); wiring an executor to run each job to its budget — and to warm-continue promotions — is the paired-scheduler integration the M4 exit oracle exercises. Pairing Dehb with a HyperbandPruner over the same ladder realises the multi-fidelity gating through the trial’s report cadence.

State: DEHB is stateful

Unlike Tpe (which recomputes from the StudyView), DEHB carries genuine mutable state — the per-fidelity populations, the parent counters, the bracket cursor, and the trial→job map. It is therefore the framework’s first stateful sampler and the first real exercise of the M4.0 state seam (before CMA-ES at M4.3): state serializes the whole machine and restore_state rebuilds it, so a study torn down and reopened continues identically — see determinism, honestly. The populations hold only unit coordinates in [0, 1] and their fitness as Option<f64> — and a non-finite loss is refused at selection — so nothing non-finite ever reaches the JSON state blob (the StateBlob-null trap, where a Some(±∞) would come back as None and silently turn an evaluated individual into an unevaluated one); the M2 float-exactness path round-trips the coordinates bit for bit, which a reopen test proves.

The blob also carries the ladder identity (min_fidelity, max_fidelity, η) the populations were sized for, and restore_state refuses a blob saved under a different ladder (Error::Sampler) rather than adopting subpopulations shaped for a schedule this sampler does not run. Restoring the state of a Dehb::new(1, 9) study into a Dehb::new(1, 27) one is a user error — the two are different searches — and it is reported as one.

Determinism

Every random choice — the initial populations, the three donor draws, the F/CR crossover coin flips, the boundary repairs — is drawn from a [ChaCha8Rng] seeded from the study seed via the per-trial sampler_seed, never ambient entropy. Under a single worker with a fixed seed DEHB is fully reproducible: the bracket cursor advances one job per ask, the state mutates deterministically at each finish, and a reopen restores it exactly. Under parallelism the order in which trials finish — and therefore how the populations evolve — depends on thread scheduling, so a parallel DEHB study is replayable, not pre-determined, exactly the standing of every history-dependent seam here. It does not get the trial-number-indexed promise, and this documents it.

Where a resume is exact, and where it is not

DEHB mutates state at two points: at ask (the cursor advances and the job is recorded) and at trial end (DE selection). The study loop persists seam state after trial end, not after ask — so a resume is exact when the previous handle stopped on a trial boundary, which is what a completed optimize (or any ask followed by its tell) always does, and is the case the reopen test pins. If a handle is instead torn down between an ask and its tell, that trial’s cursor advance was never persisted and the resumed study re-issues the job to the next trial number. Nothing is corrupted — the populations stay consistent and an orphaned job is simply ignored by after_trial — but the trace is then the replayable, not the pre-determined, one.

Modules

de

The pure differential-evolution operators, in the unit hypercube [0, 1]^d.

Structs

Dehb

Differential-Evolution Hyperband: a stateful DE sampler over a Hyperband fidelity schedule.

Constants

DEFAULT_CROSSOVER_PROB

The default DE crossover rate CR for binomial crossover (the DEHB reference default).

DEFAULT_MUTATION_FACTOR

The default DE scale factor F in the rand/1 mutation x_r1 + F·(x_r2 − x_r3) (the DEHB reference default).

MAX_TOTAL_POP_SIZE

The hard cap on the DE population summed over every fidelity — the bound on the whole live state, not on one subpopulation.