Algorithms, Heuristics and Learned Procedures

Part IWhere the obligation sits

An algorithm is a quantified claim

In casual engineering speech, “algorithm” often means any repeatable computational recipe. That usage hides the feature that matters here. A serious algorithmic claim has a declared input domain, a transition rule and a property that should hold across the whole domain. The property might be exact correctness, completeness, a bound on solution quality, termination, or a resource limit.

The logical shape can be written compactly. Let D be the allowed inputs, P the precondition, A the procedure and Q the promised postcondition:

Published evidence
Hoare’s axiomatic account of programs made program properties objects of proof rather than impressions gathered from examples. In shortest-path search, Dijkstra’s procedure and the later formalisation of heuristic search by Hart, Nilsson and Raphael show how a choice rule can be linked to a global result under stated conditions.

This does not make algorithms infallible. A proof can apply to an inaccurate map, an incomplete objective or an implementation that violates the specification. A shortest-path algorithm can faithfully find the cheapest route through a graph whose edge costs omit danger, delay or legal restriction. Formal certainty is conditional certainty. Its advantage is that the condition and obligation can be inspected separately.

A heuristic is advice whose authority is designed

A heuristic estimates which option looks promising. In search, it may estimate the remaining cost from a node to a goal. In scheduling, it may prioritise the job with least slack. In theorem proving, it may select the clause most likely to help. The heuristic itself need not be correct everywhere. What matters is how the surrounding procedure uses it.

Suppose a search frontier contains ten nodes. A heuristic can choose which node to inspect first while the frontier retains all ten. A bad estimate wastes work, but the omitted-looking node remains recoverable. The same estimate can instead delete nine nodes and commit to the favoured one. Now the estimate controls completeness. Nothing about the numeric prediction changed. Its authority changed.

A heuristic is not defined by being hand-written. Euclidean distance is a heuristic. A neural network’s cost-to-go estimate is also a heuristic when an explicit search procedure consumes it as advice. Conversely, a compact hand-written rule becomes a policy when it directly decides the next action and suppresses alternatives. The useful distinction is architectural, not sociological.

A learned procedure makes a distributional claim

A learned policy is usually written as π_θ(a | s): a parameterised rule assigning actions a to states s. Training chooses parameters θ that minimise an empirical loss, maximise reward, imitate demonstrations or satisfy another objective over sampled experience. Its native claim is therefore statistical: expected behaviour under a training or evaluation distribution.

That claim can be strong and valuable. Learned procedures absorb perceptual variation, adapt to preferences and discover guidance too complicated to specify manually. AlphaGo and AlphaZero, for example, combined learned policy and value estimates with explicit tree search rather than asking a policy network to carry the whole decision alone. Differentiable planners such as Neural A* likewise learn guidance while retaining search structure.

The mismatch appears when local predictive success is read as a universal procedural guarantee. An action classifier can be 99% accurate on states sampled from expert trajectories while failing badly after its first mistake moves it to a state the expert rarely visited. The DAgger analysis isolates this sequential dependence: a policy’s actions alter the distribution of observations it later receives.

Learning can enter at four different layers

The phrase “learned algorithm” often compresses several designs that deserve separate assurance. The first learns a representation. A vision model converts pixels into a traversability grid, after which an explicit planner searches that grid. The planner may still be complete and optimal for the represented graph. Its guarantee says nothing about an obstacle the perception model failed to place in that graph. Assurance is split between perceptual validity and algorithmic search.

The second learns the objective or cost. A routing model may predict travel time for each road, while Dijkstra or A* finds the cheapest path under those predictions. The search result is exact for the supplied edge costs. It is only as useful as the relationship between predicted cost and the real decision objective. A procedure can therefore remain algorithmically exact while becoming empirically dependent upstream.

The third learns guidance. A model estimates cost-to-go, chooses landmarks, ranks branches or proposes candidate solutions. Here a wrapper can preserve completeness, exact optimality or bounded suboptimality, depending on how guidance affects frontier membership and stopping. Research on learned heuristics and focal search is important precisely because it treats the predictor as fallible input to a designed algorithm rather than as an oracle.

The fourth learns control. The model chooses the next action and may decide when the task is complete. This supplies the broadest semantic reach because no explicit search state need be engineered. It also places the largest burden on induced-state evaluation, runtime containment and recovery. A fifth pattern sometimes complements all four: a learned proposer generates a candidate while an exact checker verifies a certificate. Sorting, constraint satisfaction, compilation and mathematical proof can sometimes exploit this asymmetry because finding is difficult while checking is cheaper.

Guarantees compose only across the interfaces that are themselves specified. “The planner is optimal” cannot repair a faulty perception map. “The verifier accepted” is meaningful only if the certificate covers the claimed property. “The policy passed evaluation” applies only to the evaluated population and action budget. Layering does not eliminate uncertainty; it lets the team state which uncertainty belongs where.

Thought experiment oneOne predictor, three wirings

Imagine a predictor that estimates the number of steps remaining from any grid cell to a destination. Freeze its weights and its outputs. We now vary only one causal feature: where the estimate enters the procedure.

Wiring A uses the estimate only to break ties. The search still orders nodes primarily by an admissible cost expression, retains every candidate and stops under the original rule. If the predictor is excellent, it resolves ties efficiently. If it is absurd, search does extra work. The correctness argument does not mention predictor accuracy.

Wiring B multiplies the estimate and adds it to path cost. Search now favours apparent progress more aggressively. With a standard weighted-A* construction and an admissible heuristic, one can obtain an explicit suboptimality bound. The guarantee is weaker than exact optimality, but it remains procedural and inspectable.

Wiring C asks the predictor for the next move and follows it. Alternatives disappear unless a separate recovery mechanism restores them. The procedure may be much cheaper and may handle visual inputs that classical search cannot consume directly. Yet completeness and optimality no longer follow from the search structure because the search structure has gone.

The predictor did not become less intelligent from A to C. The surrounding system granted it more authority. This isolates the paper’s causal claim: the guarantee changes when learned advice becomes learned control, even when predictive quality is held constant.

Part IISame graph, different authority

Consider four nodes. From start S, path S → A → G costs 2 + 2 = 4. Path S → B → G costs 1 + 100 = 101. Let the heuristic estimate be h(A) = 2, h(B) = 0 and h(G) = 0. The estimate is informative enough to look plausible, but badly optimistic around B.

Greedy best-first search selects the node with the smallest h value. It visits B, sees G with h = 0 and may return the first goal at cost 101. A* selects using f(n) = g(n) + h(n), where g is cost already incurred. It may also inspect B first, but it does not erase A. Once the expensive B → G edge is revealed, A remains the better frontier node and the route of cost 4 is recovered.

The formal boundary around a*

Let h*(n) denote the true cheapest remaining cost from node n to the goal. A heuristic is admissible when it never overestimates that cost:

For the common graph-search form, consistency provides a convenient stronger condition: h(n) ≤ c(n,n′) + h(n′) for every edge from n to n′. It prevents f values from decreasing along a path. With finite branching, appropriate positive or non-negative cost conditions and correct duplicate handling, the stopping rule then supports completeness and optimality. Alternative implementations can work with admissibility and node reopening, but the proof obligations change.

Hart, Nilsson and Raphael did more than propose a useful ranking formula. They supplied a formal basis for comparing heuristic search strategies. That distinction matters today: a learned cost estimate can be inserted into an algorithm whose obligations remain explicit, or it can be used as a direct policy whose obligations are empirical.

Weighted A* uses f_w(n) = g(n) + w h(n), with w greater than one. Under standard conditions and an admissible h, it trades exact optimality for a stated bound, commonly C ≤ wC*, where C is returned path cost and C* is optimum. The point is not that bounded suboptimality is always preferable. It is that the weakening is named before deployment rather than discovered after failure.

Which guarantees migrate

The phrase “the learned method performs like the algorithm” is incomplete until it says which property, on which population, under which resource budget. Output agreement on a test set does not transfer the algorithm’s proof. It supplies evidence that the learner approximated the procedure on sampled inputs.

The labels are about obligation, not implementation material

An algorithm need not be deterministic. Randomised algorithms can make exact or high-probability claims over declared inputs and internal randomness. A learned model can also participate in a theorem. Neural-network outputs may be verified over a bounded region, projected into a feasible set, or paired with a certificate whose checker is exact. In each case, the useful question remains: which mechanism establishes which property?

Likewise, “heuristic algorithm” is established terminology for procedures that directly return approximate answers without a general exactness guarantee. This article uses heuristic more narrowly for a signal that guides another procedure, because that isolates authority. When a heuristic itself commits the answer, analyse it in the policy column of the inventory, whether it was hand-crafted or learned.

A learned component does not become unprovable by origin, and an explicit component does not become guaranteed by appearance. Assurance may come from a proof, a probabilistic bound, exhaustive checking on a finite domain, a runtime shield, a certificate verifier or empirical evidence. The migration argument asks whether replacing a transition rule has silently replaced one of those evidence types with another.

Correctness becomes coverage

An algorithmic proof quantifies over an input class. A learned evaluation samples that class or a distribution believed to represent use. Once the direct policy replaces the algorithm, the team needs evidence about coverage: sizes, topologies, edge cases, perturbations and states induced by the policy’s own mistakes. A random split of near-identical examples can make interpolation look like procedural generality.

Optimality becomes expected regret or observed quality

A learned procedure may minimise average path length, imitation loss or task reward. These objectives are not interchangeable with returning the optimum on each admissible input. Even a low mean cost ratio can hide rare catastrophic routes, and a ratio calculated only on successful cases can hide failure altogether. If exact or bounded quality matters, keep an algorithmic bound or independent certificate.

Termination becomes runtime containment

An explicit loop can have a decreasing variant or a finite frontier. A policy rollout has no comparable property unless the environment or controller supplies one. Step limits prevent infinite execution, but they convert looping into abstention or failure. That is often the right operational choice. It should be recognised as a newly added runtime guarantee, not attributed to the learned policy.

Determinism becomes a release choice

A learned model can be deterministic under fixed weights, inputs and numerical execution, or stochastic through sampling and environment interaction. Neither form is inherently inferior. Yet replay, testing and incident analysis need the choice recorded. A distribution over outputs requires distribution-aware evaluation; one successful replay cannot establish what the earlier system was likely to do.

Explanation changes from invariant to evidence

For an explicit algorithm, an explanation can cite the transition rule, state and proof obligation. For a learned policy, attention maps, feature importance or verbal rationales may describe correlates without proving why an action followed. The durable production explanation is usually external: what state was observed, what alternatives were eligible, what score was assigned, which invariant allowed the action and what outcome followed.

Empirical assurance needs an expiry condition

Moving an obligation from proof to evaluation does not make assurance optional. It changes what the release record must contain. Name the model and wrapper versions, the decision population, the generator for shifted and induced states, the action budget and the metrics that include failed runs. Report quality both conditional on success and across all cases. Otherwise a system can improve its mean path ratio by quietly abstaining or timing out on the maps that expose its weakness.

The same record needs an expiry trigger. A new sensor, action, map topology, cost definition or policy rule can invalidate the population that supported release even when model weights remain fixed. When the system leaves that declared region, it should fall back, abstain or enter review according to consequence. The expiry event should create a reviewable decision receipt, not merely a monitoring alert. This is not a universal guarantee over future inputs. It is a bounded operating claim with an explicit condition for withdrawing authority.

Part IIIThe matched search laboratory

The laboratory below is deliberately small. It does not claim to benchmark robotics or learned planning. Its purpose is to vary the placement of guidance while holding the task, grid representation, movement costs and test maps constant.

Each 21 by 21 map contains a vertical wall in the centre and unit-cost movement in four directions. Training-like maps open the wall near the top. Shifted maps mirror that opening near the bottom. Two per cent of other cells are blocked at random, and unsolvable maps are rejected. Start and goal remain fixed on opposite sides of the wall.

A tabular behaviour-cloned policy is trained from 1,000 Dijkstra shortest-path demonstrations on training-like maps. Its observation is deliberately lossy: coarse side of wall, coarse vertical band, direction to goal and local blocked-neighbour flags. It does not receive the full map or an explicit opening location.

Six procedures then face exactly the same 200 training-like and 200 shifted maps: Dijkstra, A* with Manhattan distance, weighted A* with w = 1.8, greedy best-first search, A* using the learned policy only to break equal-f ties, and direct rollout of the learned policy. The random seeds are fixed in the executable artefact.

Measured results

Dijkstra and A* completed every map and returned optimal paths in both regimes. Weighted A* also completed every map in this finite sample; its observed paths were nearly optimal, but the experiment does not turn that observation into a universal claim. Greedy search completed the sample while returning more non-optimal paths after shift.

The learned signal produced the clearest comparison. Used as an A* tie-breaker, it reduced mean node expansions from 150.84 to 94.93 on training-like maps. Under shift, its advantage almost disappeared: 144.10 expansions versus 151.24 for ordinary A*. Yet completion and optimality remained at 100% because the signal could not discard the frontier or alter the primary f score.

Used as the direct policy, the same learned information completed 95.5% of training-like maps and only 1.5% of shifted maps. Its reported cost ratio among shifted successes was 1.000, which sounds excellent until the denominator is noticed: only three of two hundred cases succeeded. Quality conditional on success is not a substitute for coverage.

Why local accuracy can become trajectory failure

Consider a second thought experiment. A policy has a fixed 2% chance of choosing the wrong action at every step, errors are independent, and one wrong action ends the task. The probability of a clean fifty-step trajectory is 0.98⁵⁰, about 36%. At a 5% local error rate it is about 8%. This arithmetic is illustrative rather than a model of real policies, because real errors are correlated and recoverability varies.

The real problem can be worse. A mistake changes state; the next observation may sit farther from the training distribution; error probability can then rise. That is why sequential imitation learning cannot be evaluated as ordinary independent classification. The learner must be tested on the states its own behaviour induces, including recovery states.

Executable artefact

The script uses only the Python standard library. It trains the tabular policy, generates both map regimes, runs all six methods and prints the full table. A positive case is the training-like regime. The negative case mirrors the wall opening without retraining. Expected values below assume Python’s deterministic random implementation and the fixed seeds shown.

Training Like (200 maps)
Method                  Success   Cost/opt     Effort   Non-opt
Dijkstra                 100.0%     1.0000     346.79      0.0%
A*                       100.0%     1.0000     150.84      0.0%
Weighted A*              100.0%     1.0000      77.47      0.0%
Greedy                   100.0%     1.0013      49.62      2.0%
A* + learned tie         100.0%     1.0000      94.93      0.0%
Learned policy            95.5%     1.0060      31.67      8.5%

Shifted (200 maps)
Method                  Success   Cost/opt     Effort   Non-opt
Dijkstra                 100.0%     1.0000     346.04      0.0%
A*                       100.0%     1.0000     151.24      0.0%
Weighted A*              100.0%     1.0026      79.70      3.5%
Greedy                   100.0%     1.0121      51.25     17.5%
A* + learned tie         100.0%     1.0000     144.10      0.0%
Learned policy             1.5%     1.0000      80.48      0.0%

#!/usr/bin/env python3
"""Matched search laboratory for 'Algorithms, Heuristics and Learned Procedures'.

Synthetic mechanism experiment. It is not a robotics benchmark and should not be
used to make deployment claims. The code uses only Python's standard library.

Positive case: maps resemble the demonstrations: a central wall opens near the top.
Negative case: the wall opening is mirrored to the bottom while the learned policy
is held fixed. Classical algorithms receive the same map and cost function.
"""
from __future__ import annotations

from collections import Counter, defaultdict
from dataclasses import dataclass
import heapq
import math
import random
import statistics
from typing import Callable, DefaultDict, Dict, Iterable, List, Mapping, Optional, Sequence, Set, Tuple

Point = Tuple[int, int]
Action = Tuple[int, int]
ACTIONS: Tuple[Action, ...] = ((1, 0), (0, -1), (0, 1), (-1, 0))  # right, up, down, left
ACTION_NAME: Mapping[Action, str] = {(1, 0): "R", (0, -1): "U", (0, 1): "D", (-1, 0): "L"}


@dataclass(frozen=True)
class Grid:
    width: int
    height: int
    blocked: frozenset[Point]
    start: Point
    goal: Point

    def inside(self, p: Point) -> bool:
        return 0 <= p[0] < self.width and 0 <= p[1] < self.height

    def neighbours(self, p: Point) -> Iterable[Tuple[Point, Action]]:
        for action in ACTIONS:
            q = (p[0] + action[0], p[1] + action[1])
            if self.inside(q) and q not in self.blocked:
                yield q, action


def manhattan(a: Point, b: Point) -> int:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def reconstruct(parent: Mapping[Point, Point], goal: Point) -> List[Point]:
    path = [goal]
    while path[-1] in parent:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def best_first(
    grid: Grid,
    mode: str,
    policy: Optional["TabularPolicy"] = None,
    weight: float = 1.8,
) -> Tuple[Optional[List[Point]], int]:
    """Run Dijkstra, A*, weighted A*, greedy, or A* with a learned tie-break.

    The primary A* key is always g+h. In the learned-tie arm, the learned policy
    only orders nodes whose f values are identical. It cannot remove a node or
    change its g score, which is why the search proof obligations remain intact.
    """
    start, goal = grid.start, grid.goal
    counter = 0
    frontier: List[Tuple[float, float, int, Point]] = []
    g: Dict[Point, float] = {start: 0.0}
    parent: Dict[Point, Point] = {}
    closed: Set[Point] = set()

    def keys(node: Point, parent_node: Optional[Point], action: Optional[Action]) -> Tuple[float, float]:
        gv = g[node]
        hv = float(manhattan(node, goal))
        if mode == "dijkstra":
            return gv, 0.0
        if mode == "astar":
            return gv + hv, 0.0
        if mode == "weighted":
            return gv + weight * hv, 0.0
        if mode == "greedy":
            return hv, gv
        if mode == "learned_tie":
            tie = 0.0
            if policy is not None and parent_node is not None and action is not None:
                tie = -policy.probability(grid, parent_node, action)
            return gv + hv, tie
        raise ValueError(f"unknown mode: {mode}")

    p0, t0 = keys(start, None, None)
    heapq.heappush(frontier, (p0, t0, counter, start))
    expansions = 0

    while frontier:
        _, _, _, node = heapq.heappop(frontier)
        if node in closed:
            continue
        closed.add(node)
        expansions += 1
        if node == goal:
            return reconstruct(parent, goal), expansions

        for nxt, action in grid.neighbours(node):
            candidate = g[node] + 1.0
            if candidate < g.get(nxt, math.inf):
                g[nxt] = candidate
                parent[nxt] = node
                counter += 1
                primary, tie = keys(nxt, node, action)
                heapq.heappush(frontier, (primary, tie, counter, nxt))
    return None, expansions


def shortest_path(grid: Grid) -> Optional[List[Point]]:
    return best_first(grid, "dijkstra")[0]


def action_between(a: Point, b: Point) -> Action:
    return (b[0] - a[0], b[1] - a[1])


def make_grid(rng: random.Random, regime: str, random_obstacle_rate: float = 0.02) -> Grid:
    """Create a 21x21 map with one central barrier and a regime-specific opening."""
    width = height = 21
    start, goal = (0, 10), (20, 10)
    wall_x = 10
    if regime == "training_like":
        gap_centre = rng.choice((3, 4, 5, 6))
    elif regime == "shifted":
        gap_centre = rng.choice((14, 15, 16, 17))
    else:
        raise ValueError(regime)
    gap = {gap_centre - 1, gap_centre, gap_centre + 1}
    blocked: Set[Point] = {(wall_x, y) for y in range(height) if y not in gap}

    for x in range(width):
        for y in range(height):
            p = (x, y)
            if p in blocked or p in (start, goal) or x == wall_x:
                continue
            if rng.random() < random_obstacle_rate:
                blocked.add(p)

    return Grid(width, height, frozenset(blocked), start, goal)


def solvable_grid(rng: random.Random, regime: str) -> Grid:
    while True:
        grid = make_grid(rng, regime)
        if shortest_path(grid) is not None:
            return grid


def observation(grid: Grid, p: Point) -> Tuple[int, int, int, int, int, int, int]:
    """Deliberately lossy policy observation.

    It contains coarse location and local occupancy, but not a map or explicit wall
    opening. This creates a realistic distinction between a procedure that searches
    the represented state space and a policy that acts from a compressed view.
    """
    x, y = p
    side = -1 if x < 10 else (1 if x > 10 else 0)
    y_band = 0 if y <= 6 else (1 if y <= 13 else 2)
    dx_sign = 1 if grid.goal[0] > x else (0 if grid.goal[0] == x else -1)
    flags = []
    for a in ACTIONS:
        q = (x + a[0], y + a[1])
        flags.append(int((not grid.inside(q)) or q in grid.blocked))
    return (side, y_band, dx_sign, *flags)


class TabularPolicy:
    def __init__(self) -> None:
        self.counts: DefaultDict[Tuple[int, ...], Counter[Action]] = defaultdict(Counter)
        self.global_counts: Counter[Action] = Counter()

    def add(self, grid: Grid, state: Point, action: Action) -> None:
        key = observation(grid, state)
        self.counts[key][action] += 1
        self.global_counts[action] += 1

    def distribution(self, grid: Grid, state: Point) -> Dict[Action, float]:
        counts = self.counts.get(observation(grid, state), self.global_counts)
        total = sum(counts.values()) + len(ACTIONS)  # Laplace smoothing
        return {a: (counts.get(a, 0) + 1) / total for a in ACTIONS}

    def probability(self, grid: Grid, state: Point, action: Action) -> float:
        return self.distribution(grid, state)[action]

    def choose(self, grid: Grid, state: Point, visited: Set[Point]) -> Optional[Action]:
        ranked = sorted(
            ACTIONS,
            key=lambda a: (-self.probability(grid, state, a), ACTIONS.index(a)),
        )
        for action in ranked:
            nxt = (state[0] + action[0], state[1] + action[1])
            if grid.inside(nxt) and nxt not in grid.blocked and nxt not in visited:
                return action
        return None


def train_policy(seed: int = 7, demonstrations: int = 1000) -> TabularPolicy:
    rng = random.Random(seed)
    policy = TabularPolicy()
    for _ in range(demonstrations):
        grid = solvable_grid(rng, "training_like")
        path = shortest_path(grid)
        assert path is not None
        for a, b in zip(path, path[1:]):
            policy.add(grid, a, action_between(a, b))
    return policy


def rollout(grid: Grid, policy: TabularPolicy, step_limit: int = 180) -> Tuple[Optional[List[Point]], int]:
    state = grid.start
    path = [state]
    visited: Set[Point] = {state}
    for step in range(step_limit):
        if state == grid.goal:
            return path, step
        action = policy.choose(grid, state, visited)
        if action is None:
            return None, step + 1
        state = (state[0] + action[0], state[1] + action[1])
        path.append(state)
        visited.add(state)
    return None, step_limit


@dataclass
class Metrics:
    successes: int = 0
    ratios: List[float] = None  # type: ignore[assignment]
    effort: List[int] = None  # type: ignore[assignment]
    nonoptimal: int = 0

    def __post_init__(self) -> None:
        self.ratios = []
        self.effort = []

    def record(self, path: Optional[Sequence[Point]], optimum: int, effort: int) -> None:
        self.effort.append(effort)
        if path is None:
            return
        cost = len(path) - 1
        self.successes += 1
        self.ratios.append(cost / optimum)
        if cost > optimum:
            self.nonoptimal += 1


def evaluate(regime: str, policy: TabularPolicy, seed: int, cases: int = 200) -> Dict[str, Metrics]:
    rng = random.Random(seed)
    names = ("Dijkstra", "A*", "Weighted A*", "Greedy", "A* + learned tie", "Learned policy")
    out = {name: Metrics() for name in names}

    for _ in range(cases):
        grid = solvable_grid(rng, regime)
        optimum_path, _ = best_first(grid, "dijkstra")
        assert optimum_path is not None
        optimum = len(optimum_path) - 1

        for name, mode in (
            ("Dijkstra", "dijkstra"),
            ("A*", "astar"),
            ("Weighted A*", "weighted"),
            ("Greedy", "greedy"),
            ("A* + learned tie", "learned_tie"),
        ):
            path, expansions = best_first(grid, mode, policy=policy)
            out[name].record(path, optimum, expansions)

        path, decisions = rollout(grid, policy)
        out["Learned policy"].record(path, optimum, decisions)
    return out


def summarise(metrics: Mapping[str, Metrics], cases: int) -> List[Dict[str, object]]:
    rows = []
    for name, m in metrics.items():
        rows.append({
            "method": name,
            "success_pct": 100.0 * m.successes / cases,
            "mean_cost_ratio": statistics.mean(m.ratios) if m.ratios else math.nan,
            "mean_effort": statistics.mean(m.effort),
            "nonoptimal_pct_of_all": 100.0 * m.nonoptimal / cases,
        })
    return rows


def print_table(regime: str, rows: Sequence[Mapping[str, object]]) -> None:
    print(f"\n{regime.replace('_', ' ').title()} (200 maps)")
    print(f"{'Method':<21} {'Success':>9} {'Cost/opt':>10} {'Effort':>10} {'Non-opt':>9}")
    for row in rows:
        ratio = row['mean_cost_ratio']
        ratio_text = "n/a" if isinstance(ratio, float) and math.isnan(ratio) else f"{ratio:.4f}"
        print(
            f"{row['method']:<21} "
            f"{row['success_pct']:>8.1f}% "
            f"{ratio_text:>10} "
            f"{row['mean_effort']:>10.2f} "
            f"{row['nonoptimal_pct_of_all']:>8.1f}%"
        )


def main() -> None:
    policy = train_policy(seed=7, demonstrations=1000)
    for regime, seed in (("training_like", 41), ("shifted", 43)):
        rows = summarise(evaluate(regime, policy, seed=seed, cases=200), 200)
        print_table(regime, rows)


if __name__ == "__main__":
    main()

The experiment supports one bounded conclusion. It does not show that a tabular policy is representative of modern learned planners, nor that A* is always affordable. It shows that the same learned signal can fail abruptly as authority and degrade gracefully as advice. That causal distinction is available only because the search wrapper is a matched negative control.

Part IVA production-shaped example: the case-work scheduler

Consider a regulated case-work service that must assemble evidence, run a deterministic calculation, draft a narrative and obtain approval before a deadline. Cases vary in document quality, urgency and specialist availability. A learned scheduler might plausibly reduce cycle time by predicting which eligible task should run next.

For one case, task R retrieves source records. Task C computes ratios and depends on R. Task N drafts the narrative and depends on both R and C. Task A records a qualified human approval and depends on N. A final release task depends on A and requires a named authority. Arrivals from other cases create a shared queue.

A direct policy receives the queue and chooses the next operation. On familiar traffic, it learns useful patterns: retrieve in parallel, prioritise cases likely to unblock quickly, and reserve scarce reviewers for near-complete packs. Under a new policy rule or a surge of unusual cases, however, a superficially efficient choice could run N before the calculation is final, miss a statutory deadline or repeatedly defer a low-frequency case.

The hybrid first computes an eligible set algorithmically. Dependency checks, deadline floors, authority, case isolation and no-duplicate-effect rules determine which transitions are currently allowed. The learned ranker orders only that set. If its score is unavailable, the scheduler falls back to earliest deadline with deterministic tie-breaking. After every operation, the runtime reads the resulting case state before offering another transition.

The model improves allocation; the state machine owns admissibility. This does not guarantee that the overall business objective is correct or that every document interpretation is accurate. It preserves the narrower properties whose violation would create an invalid sequence regardless of prediction quality.

The serious objection: specifications are brittle

A defence of explicit guarantees can become a defence of narrow, unrealistic models. Many important tasks are underspecified. The world supplies ambiguous language, partial observation, strategic actors and changing norms. Writing a complete algorithm may be more expensive than the task, and a brittle rule can fail more predictably than a learned model while still failing more often.

This objection is correct. The answer is not to encode every judgement as rules. It is to separate the properties that can be stated from the interpretations that cannot. Identity, dependency, schema, arithmetic, transaction uniqueness and authority often admit crisp checks. Relevance, semantic alignment, prioritisation and anomaly interpretation often benefit from learning. Use specification where the invariant is real, not where certainty is merely desired.

Learning-augmented algorithm research makes this constructive rather than nostalgic. Work on learned predictions for graph algorithms seeks speed when predictions are good while retaining a classical baseline when they are poor. Recent theory describes properties such as consistency, robustness and smoothness. The design ambition is not to choose between rigid algorithms and unconstrained policies. It is to make prediction error change performance gradually rather than destroy correctness suddenly.

The explicit failure boundary

The hybrid mechanism stops helping when the wrapper cannot represent the property that matters. If the grid omits a collapsing floor, optimal search over the grid is unsafe. If the scheduler’s state lacks a newly binding obligation, eligibility is falsely permissive. If the objective rewards speed while harm lies outside the cost function, a proof of optimality certifies the wrong thing.

Search may also be computationally infeasible. A complete algorithm that cannot finish within the decision window supplies little operational value. Bounded search, approximate algorithms or direct policies can be rational choices when delay itself is harmful. The assurance case should then state which guarantee was relaxed, what empirical evidence replaces it, which actions remain reversible and how the system fails when its evidence no longer applies.

A learned heuristic can also cost more to evaluate than the nodes it saves. Node expansions are therefore an explanatory metric, not a universal latency proxy. Real decisions need end-to-end measurements including model inference, batching, memory movement, tool calls and recovery.

The procedure-substitution test

Before replacing an explicit algorithm, heuristic or ruleset with a learned procedure, complete one record for the decision population. The record forces the proposed benefit and the surrendered guarantee into the same review.

A compact architecture decision rule

Use a direct learned policy when the action space is semantically rich, consequences are reversible, search is unavailable or too expensive, and shift can be detected before accumulated error becomes harmful. Use explicit algorithms when the state and objective are sufficiently specified and the guarantee matters more than average-case flexibility.

Prefer a hybrid when a learned signal can improve ranking or representation while an explicit procedure can still preserve eligibility, bounds, stopping and recovery. This pattern is especially attractive when prediction error should affect cost rather than correctness. It turns “the model was wrong” from a terminal explanation into a measured efficiency degradation.

Open hypothesis
For high-consequence combinatorial decisions, learning used as bounded advice will often offer a better assurance-to-performance frontier than an equally trained direct policy. The hypothesis is testable only through matched budgets, the same learned signal, explicit shift, and separate measures for coverage, quality and escaped consequence.

Keep the proof where the consequence is

An explicit algorithm, a heuristic and a learned procedure may agree on every demonstration and still be different engineering objects. The difference appears when the map changes, a rare state is reached, the budget tightens or a wrong action cannot be undone.

The architecture decision should therefore begin with a guarantee inventory. Identify the current universal claim and its assumptions. Place the learned signal at a named point in the control loop. Determine whether prediction error can only increase cost or can erase the path to a valid answer. Then run a matched negative control in which the same prediction remains inside the old procedural wrapper.

The search laboratory changed one design decision. The learned policy looked efficient on familiar maps and failed on the mirrored opening. The same learned information, restricted to tie-breaking, retained completion and exact path quality while its efficiency benefit faded gracefully. That is the practical signature of a well-placed learned component: its error spends performance before it spends correctness.

None of this diminishes learning. It gives learning a sharper role. Use it to perceive, rank and generalise where hand specification is weak. Keep explicit state, invariants, bounds, stopping and recovery wherever a consequential promise can genuinely be stated. When a guarantee must be relaxed, name the relaxation, test the shift that threatens it and make the new empirical burden visible.

The changed research programme is equally concrete: stop asking whether a network “learned the algorithm” from output accuracy alone. Ask which invariants it reproduces, on which induced states, at which sizes, with what fallback, and whether the learned signal can be moved outside the proof without losing its value. That experiment can fail, and that is what makes it informative.