Auditable Regret for Online Routing with Endogenous Feasible Sets

Online routing consumes resources that change which routes remain feasible later. A deployment log can therefore support comparisons among actions on visited states without reconstructing the state trajectory that another policy would have generated. We formalize this distinction through an *auditable regret frontier* with two axes. L0/L1/L2 describe executed-action feedback, same-state candidate audit, and counterfactual-state reconstruction. Conditional on L1, a repayment window $W$ controls how long a comparator may carry positive safety pressure before repaying it. We show that unrestricted L1 comparators admit instances in which no algorithm can guarantee both sublinear reward regret and sublinear violation. In a normalized exact decision-time L1 oracle game with strict fallback, the minimax weighted cost is $0$ at $W=1$ and $\Theta (\sqrt{WT})$ for $2\le W\le T$. A CVQ-Routing specialization with exact coefficients supplies the matching-order upper bound. The deployable controller instead uses surrogates, and its pathwise certificate records coefficient mismatch, route-search error, queue drift, and comparator debt. Controlled synthetic and public-data replays probe these terms and the difference between same-state L1 evaluation and own-trajectory L2 replay. The resulting framework makes explicit which comparison objects are supported by an audit interface and how comparator strength changes their attainable cost.