Risk-Aware Optimal Control with Rulebooks

Tichakorn Wongpiromsarn

Source-linked AI summary

Risk-Aware Optimal Control with Rulebooks

Tichakorn Wongpiromsarn

arXiv:2609.05199v1Sep 4, 2026eess.SYcs.RO

TL;DR

Safety-critical control requires choosing policies across uncertain, differently prioritized requirements without reducing the problem to a single scalar objective. The paper formulates this choice as lexicographic optimization over thresholded excess risks and develops an anytime filtering and branch-and-bound algorithm for black-box risk evaluations. It provides finite-budget gap certificates, convergence under additional assumptions, and demonstrations on synthetic and highway-merging tasks.

Problem
Safety-critical control lacks a direct policy-selection formulation for multiple prioritized risk criteria under uncertain outcomes.
Method
The paper combines risk-aware rulebooks, lexicographic excess-risk optimization, and anytime filtering with Lipschitz branch-and-bound for black-box risk-evaluation functions.
Results
The algorithm returns valid optimality-gap certificates for any finite computational budget, with convergence to zero under additional assumptions, and is demonstrated on synthetic and highway-merging tasks.
Takeaways & Limitations
The approach characterizes potentially optimal policy sets while progressively tightening certified suboptimality bounds in risk-aware control.
Takeaways & Limitations
The convergence analysis relies on conservative global Lipschitz constants, sampling assumptions, and deterministic black-box evaluations.

Abstract

from arXiv · show

We consider safety-critical control problems involving multiple requirements with different priorities and uncertainty in their evaluation. We represent these requirements using risk-aware rulebooks, where each requirement is assigned a risk measure and an acceptable threshold, and a priority relation is defined among the requirements. Each requirement induces a risk-evaluation function that maps a policy to the risk associated with its violation. We formulate risk-aware optimal control with rulebooks as a lexicographic optimization problem over excess risks and develop an anytime filtering and branch-and-bound algorithm that progressively tightens the certified optimality gap while characterizing the corresponding set of policies at each priority level. The algorithm returns a policy together with these gaps, which bound its suboptimality. We prove that these gaps are valid for any finite computational budget and, under additional assumptions, converge to zero as the computational budget increases. We evaluate the algorithm on a synthetic benchmark with a known optimum and a realistic highway-merging simulation with CVaR-based collision, rear-braking, headway, and comfort rules.

I. INTRODUCTION

Safety-critical control must balance uncertain, differently prioritized requirements rather than optimize a single scalar objective. The paper formulates this setting with risk-aware rulebooks and develops an anytime algorithm that characterizes potentially optimal policies with certified gaps.

Safety-critical control must prioritize requirements such as collision avoidance over lower-priority objectives like headway when all cannot be satisfied.
Expectation can obscure rare severe outcomes, motivating risk measures such as worst-case risk, VaR, and CVaR for uncertain policy evaluation.
Existing risk-aware control methods do not directly address policy selection under multiple prioritized risk criteria.
Risk-aware rulebooks assign each requirement a risk measure, acceptable threshold, and priority, treating below-threshold policies as equally acceptable for that rule.
The paper formulates rulebook control as lexicographic optimization over excess risks and supports multiple rule levels with distinct risk measures and thresholds.
The anytime filtering and branch-and-bound algorithm uses black-box risk evaluations to characterize all potentially optimal policies and provide finite-budget optimality-gap guarantees.

II. PRELIMINARIES

The preliminaries define rulebooks as priority structures over violation-measuring rules. Their preorder supports strict priority, incomparability, and equal rank, generalizing weighted and lexicographic formulations.

A rule maps an object to a nonnegative violation degree, with zero indicating satisfaction and larger values indicating greater violation.
A rulebook consists of a rule set and a preorder specifying relative priorities among rules.
The preorder permits strict priority, incomparability, and equal rank among rules.
Equal-rank rulebooks generalize weighted formulations, while total priority orderings recover classical lexicographic formulations.
The rulebook-induced policy preorder favors an object when any worse lower-priority violation is offset by a better higher-priority rule.

III. PROBLEM FORMULATION

The problem formulation evaluates policies through rule-specific risk measures and thresholds, then compares them lexicographically by excess risk. Compactness and Lipschitz continuity provide the assumptions needed for a well-defined optimization problem.

Uncertainty is modeled on a probability space, while policies lie in a compact nonempty subset of R^d.
Each rule assigns a risk measure to its policy-dependent violation random variable, allowing different rules to use expected value, worst-case risk, VaR, or CVaR.
A policy satisfies rule r_i when q_i(π) ≤ γ_i, and its excess risk is e_i(π) = [q_i(π) − γ_i]+.
Policies are compared by whether lower-priority excess-risk increases are offset by improvements in higher-priority rules.
The optimization problem seeks a policy for which no other policy is strictly better under the induced rulebook preorder.
Lipschitz-continuous risk evaluations and a compact policy space support a well-posed problem and prevent preference cycles through the induced preorder.

IV. ANYTIME LEXICOGRAPHIC OPTIMIZATION VIA FILTERING AND BRANCH-AND-BOUND

The algorithm refines the rulebook to a total order and solves the resulting lexicographic problem through nested candidate sets. Filtering handles satisfiable thresholds, while Lipschitz branch-and-bound supplies certified bounds and incumbents for anytime progress.

The rulebook can be refined to a total order without contradicting any original policy preference, and an optimum for the refinement remains optimal for the original rulebook.
The refined problem compares policies lexicographically using the excess-risk vector, whose components are continuous under Lipschitz risk evaluations.
For each rule level, nested sets contain policies lexicographically optimal for the rules processed so far, yielding a well-defined final optimal set.
When a rule is satisfiable among surviving candidates, the algorithm filters for feasibility because all below-threshold policies are equally acceptable at that level.
When a rule is unsatisfiable, minimizing its excess risk is equivalent to minimizing its risk, so branch-and-bound optimization is required.
The algorithm maintains box-based lower bounds and feasible incumbent upper bounds to progressively restrict candidate policies and certify optimality gaps.

A. Admissible Domains, Box Bounds and Certificates

The paper constructs certified admissible domains from box-based risk bounds, preserving the exact lexicographic solution sets while quantifying their relaxation through optimality gaps.

Admissible domains: Certified admissible domains are recursively constructed to contain the exact lexicographic solution sets at every rule level.When every level gap is zero, the certified domains coincide with the exact solution sets.
Box bounds: Box representations use centers, covering radii, and Lipschitz continuity to derive lower and upper bounds on risks and excess risks.The uncertainty width w_i(B) measures the bound width induced by Lipschitz continuity.
Box bounds: The bound construction is valid whenever the resulting inequalities hold for every policy in each box, regardless of how the bounds are computed.The algorithm therefore does not depend specifically on the center-based construction.
Certificates: At each rule level, boxes cover all minimizers while certified incumbents provide upper certificates and box bounds provide lower certificates.The algorithm maintains these certificates together with a certified optimality gap and updates them during pruning and refinement.
Certificates: A box whose lower excess-risk bound exceeds the incumbent upper certificate cannot contain a minimizer and can be safely pruned.This defines competitive boxes by the condition e_i(B) ≤ ᾱ_i.
Admissible domains: For satisfiable rules, threshold bounds distinguish certified feasible, certified infeasible, and ambiguous boxes, and complete elimination of ambiguity certifies the admissible set.The resulting threshold-based set equals the exact feasible set when all retained boxes have upper risk bounds below the threshold.

B. Certified Anytime Algorithm

Algorithm 1 processes rule levels sequentially, using pruning, box refinement, sampling, and certificate updates to produce certified admissible domains under a finite computational budget.

Algorithm state: Algorithm 1 maintains a certified admissible domain, a box collection, and a finite certified incumbent set at each rule level.The initial domain is Π, the box collection covers it, and the incumbent set is nonempty and finite.
Pruning: Competitive pruning removes boxes with excess-risk lower bounds above the incumbent certificate, while threshold pruning retains boxes whose risk lower bounds meet the rule threshold.Domain pruning additionally removes boxes incompatible with previously processed rules.
Refinement: When ambiguity remains, the algorithm selects the refinable box with greatest uncertainty width and bisects it along its longest dimension.The two child boxes replace the selected box before further pruning and sampling.
Propagation: After each level, the algorithm propagates the threshold-defined domain, filters incumbents, and returns a policy together with the gaps.The domain need not be explicitly constructed because membership can be tested using stored thresholds.
Sampling: Sampled policies from new boxes are certified against the current admissible domain and added to the incumbent set when eligible.For later levels, eligibility is checked against the preceding excess-risk thresholds.

C. Correctness of Algorithm 1

The correctness analysis establishes invariants for pruning, coverage, and certificates, culminating in finite-budget optimality guarantees for the returned policy.

Invariants: Pruning preserves coverage of the relevant ε-optimal sets throughout each while-loop iteration.This holds across competitive pruning, threshold pruning, and domain pruning.
Invariants: The incumbent set remains nonempty and contained in the preceding admissible domain before every certificate initialization and update.New incumbents are added only when CSAMPLES certifies their membership.
Main guarantee: The final incumbent is nonempty, belongs to every certified domain, and therefore satisfies every rule-level threshold defining the returned domains.Nested domain construction gives bπ ∈ D_i for all rule levels.
Main guarantee: If every rule level terminates under the stated assumptions, the returned policy satisfies e_i(bπ) − α_i(D_i−1) ≤ ε_i for every rule.Thus each ε_i is a valid finite-budget optimality certificate.

D. Convergence

The algorithm’s refinement width is monotonically reduced and converges to zero. Under additional assumptions, its certified optimality gap also converges to zero, and accumulation points of returned policies belong to the rule-level solution set.

Certified-gap convergence: The certified gap εi(N) is monotonically nonincreasing and converges to a nonnegative limit.The gap is the difference between nondecreasing lower and nonincreasing upper certificates, so it remains nonnegative.
Feasibility: Assumption 3 ensures every generated box and its center remain inside the feasible policy domain Π.Axis-aligned bisection preserves containment, and box convexity keeps each center feasible.
Policy convergence: As box sizes shrink, centers of boxes in the active collection approach the certified admissible domain Di−1.Lemma 13 states that l(Bk) → 0 implies dist(c(Bk), Di−1) → 0.
Certified-gap convergence: Under Assumptions 3 and 4, the certified optimality gap satisfies εi(N) → 0.Assumption 3 requires a finite box representation of Π, while Assumption 4 requires certified incumbents to approach the optimum at the refinement-width rate.
Policy convergence: Under Assumptions 3 and 4, every convergent sequence of returned policies has its limit in the rule-level solution set Mi.The result applies to policies bπNk selected from certified incumbent sets along snapshots with Nk → ∞.

V. EXPERIMENTAL RESULTS

The algorithm is evaluated in two complementary settings: a synthetic benchmark with a known ground-truth solution and a highway-merging simulation demonstrating practical applicability to black-box risk-aware control.

The synthetic benchmark enables quantitative evaluation against a known ground-truth solution.
The highway-merging simulation demonstrates the algorithm’s practical applicability to black-box risk-aware control.

A. Synthetic Benchmark

The synthetic benchmark uses a shifted Rosenbrock-type single-rule problem with a known optimum to assess convergence, certificate quality, and anytime behavior. Algorithm 1 matches the thresholded baseline’s certified gap while contracting the candidate cover faster than both best-first variants.

Setup: The benchmark uses policy space Π = [−1, 1]2 and a shifted Rosenbrock-type risk function with a closed-form exact solution.The exact solution enables direct comparison of convergence, certificate quality, and anytime performance.
Setup: At γ = 0, only π⋆ satisfies the rule; at γ > 0, the acceptable set expands to the sublevel set {π : q(π) ≤ γ}.Every policy in the expanded sublevel set has minimum excess risk α(Π) = 0.
Experimental design: The box-based methods use 2Nmax black-box evaluations, while uniform grid search evaluates one grid point per iteration.The default budget Nmax = 900 corresponds to a 30 × 30 grid.
Results: Algorithm 1 achieves the same certified optimality gap as the thresholded baseline in both experiments, whereas uniform grid search lacks a certified gap.Uniform grid search attains comparable incumbent quality but does not produce certified lower bounds.
Results: Algorithm 1 contracts the cover measure |O(N)| substantially faster than both best-first B&B variants.Its widest-refinable-box rule spreads refinement across the competitive region, supporting faster pruning of uncompetitive regions.
Interpretation: Thresholded best-first B&B improves the certified gap, while the widest-refinable-box rule produces substantially tighter box collections.The two comparisons isolate the respective contributions of threshold exploitation and Algorithm 1’s refinement rule.

B. Highway Merging Simulation

The highway-merging experiment applies the framework to black-box risk evaluation under uncertain surrounding-vehicle interactions. A flat-output Bézier parameterization reduces the policy search to bounded control-point variables, while prioritized collision, braking, headway, and comfort rules govern refinement.

Scenario: The scenario requires an ego vehicle to merge into a target-lane gap between front and rear vehicles over a fixed horizon.Uncertain vehicle interactions make the resulting risk-evaluation functions impractical to characterize analytically, so they are treated as black boxes.
Rulebook: The rulebook prioritizes collision avoidance above rear-vehicle braking, headway, and comfort, with equal ranks for front/rear collision, front/rear headway, and the two comfort rules.Equal-rank rules are aggregated into the total order r1 > r2 > r3 > r4.
Risk evaluation: CVaR evaluates collision, rear-braking, and headway risks, while comfort depends only on the ego trajectory.The uncertain-interaction rules use CVaR; the comfort rule is trajectory-dependent.
Policy parameterization: A degree-7 Bézier parameterization fixes endpoint positions and velocities, leaving four interior control points as the eight-dimensional decision vector θ.The free points are constrained within longitudinal slabs while spanning the corridor laterally, encouraging forward progress without full trajectory discretization.
Simulation oracle: The simulation oracle uses Monte Carlo samples of surrounding-vehicle behavior, including response modes, delays, gains, clearances, and disturbances.In practice, the oracle is usually replaced by a neural-network surrogate.
Algorithm behavior: At the rear-braking level, α2 decreases from 0.28m/s2 to 0, after which threshold pruning maintains α2 = 0 while the incumbent set grows to |C| = 37.The switch occurs when a candidate satisfies the threshold, and later refinements do not increase the excess-risk certificate.

VI. CONCLUSIONS AND FUTURE WORK

The paper establishes finite-budget certificates for an anytime risk-aware control algorithm and shows convergence under additional assumptions. Experiments illustrate improved certificate quality on a synthetic benchmark and practical applicability in highway merging, while future work targets conservatism and uncertain evaluations.

The algorithm returns certificates that validly bound suboptimality for any finite computational budget.Under additional assumptions, the certified optimality gap converges to zero and every limit point of returned incumbents is optimal.
Exploiting threshold structure and widest-refinable-box selection improves certificate quality on the synthetic benchmark.
The highway-merging simulation demonstrates the method in a realistic application.
The convergence analysis relies on conservative global Lipschitz constants and sampling assumptions.Future work includes weaker convergence conditions, adaptive local Lipschitz estimates, and approaches that do not require a known Lipschitz constant.
Finite Monte Carlo estimates and neural surrogates require statistical uncertainty and approximation error to be incorporated into the box bounds.