MDPs中稀疏策略部署的Bellman认证舍入方法

# Bellman-Certified Rounding for Sparse Policy Deployment in MDPs
Source: [https://arxiv.org/html/2610.00325](https://arxiv.org/html/2610.00325)
###### Abstract

Continuous policy optimization may spread an update across many states, even when deployment permits only a few complete state\-level changes\. We study how much discounted return can be retained when continuous row mixtures are rounded to sparse binary policies in finite MDPs\. Policy\-dependent visitation couples the row edits, while long horizons make global curvature bounds conservative\. From2​d\+22d\+2Bellman solves, we derive reusable envelopes that support uniform and candidate\-specific guarantees before rounding\. A rank\-two rational representation of each exchange further permits weighted curvature integration along the realized trajectory\. We prove that linear dimension dependence is unavoidable when the budget scales, and that exact global curvature thresholding is hard\. Candidate\-specific bounds raise pre\-rounding certification coverage from48\.2%48\.2\\%to74\.1%74\.1\\%on the structured suite\. Atγ=0\.95\\gamma=0\.95, local integration lowers the median bound\-to\-loss ratio from402\.3402\.3to2\.082\.08on coupled instances\.

## 1Introduction

Continuous policy optimization naturally distributes small updates across many states\. Deployment may instead require each modified state\-level decision to be implemented as a complete row change, with onlykksuch changes affordable\. We study the return lost when a continuous policy is mapped to this sparse deployment class\.

We considerddeditable rows in a finite discounted Markov decision process\. Each row retains its baseline action or adopts one proposed action\. A binary vectoryyspecifies these choices, giving the deployment problem

maxy∈\{0,1\}d,1⊤​y≤k⁡J⁡\(y\)\\max\_\{y\\in\\\{0,1\\\}^\{d\},\\,\\mathbf\{1\}^\{\\top\}y\\leq k\}J\(y\)\. Continuous row mixtures belong to𝒞k=\{x∈\[0,1\]d:𝟏⊤​x≤k\}\\mathcal\{C\}\_\{k\}=\\\{x\\in\[0,1\]^\{d\}:\\mathbf\{1\}^\{\\top\}x\\leq k\\\}, and𝒞kbin=𝒞k∩\{0,1\}d\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}=\\mathcal\{C\}\_\{k\}\\cap\\\{0,1\\\}^\{d\}is the deployable class\. Their mismatch is

Gap⁡\(𝒞k\)=maxx∈𝒞k⁡J⁡\(x\)−maxy∈𝒞kbin⁡J⁡\(y\)\.\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=\\max\_\{x\\in\\mathcal\{C\}\_\{k\}\}J\(x\)\-\\max\_\{y\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}\}J\(y\)\.\(1\)Our goal is to convert a continuous candidate into a feasible binary policy with a return guarantee\. Changing one row alters later visits to other rows, so the values of the edits do not decouple\. At long horizons, the largest curvature over the policy cube may also lie far from the rounding trajectory and substantially overstate its loss\.

Every fractional row mixture is a stationary randomized policy in an auxiliary two\-action MDP\. Extremal Bellman values bracket both policy values and row occupancies\. The resulting sensitivity envelopes require2​d\+22d\+2solves and giveJ⁡\(y\)≥J⁡\(x\)−BunifJ\(y\)\\geq J\(x\)\-B\_\{\\mathrm\{unif\}\}for everyx∈𝒞kx\\in\\mathcal\{C\}\_\{k\}, withcd,k≤k/4c\_\{d,k\}\\leq k/4\. Once a candidate is known, its geometry sharpens the bound without another Bellman solve\. For the remaining long\-horizon slack, we use the rank\-two rational form of each exchange and integrate curvature with the interpolation weight that determines endpoint loss\.

#### Advance certification and deployment\.

A uniform loss bound controls the relaxation gap over the policy family\. For a particular candidate, the conditionJ⁡\(x\)−B\>J⁡\(0\)J\(x\)\-B\>J\(0\)certifies improvement over the baseline before the discrete policy is constructed\. The same Bellman envelopes can be reused across candidates and budgets that share the baseline and proposed rows\. On the structured suite, candidate\-specific bounds increase pre\-rounding certification coverage from48\.2%48\.2\\%to74\.1%74\.1\\%\. Rounding uses a median of six return evaluations, compared with 26 for greedy, while their mean normalized optimality gaps are0\.185%0\.185\\%and0\.178%0\.178\\%\. AtS=d=16S=d=16, validated arithmetic makes certificate construction14\.8×14\.8\\timesfaster than the exact\-rational pipeline\. The realized return can then be checked directly once rounding is complete\.

### 1\.1Illustrative example

Considermmzero\-reward states and one absorbing target with positive reward\. At each zero\-reward state, the baseline action self\-loops and the proposed action moves to the target\. The deployment budget isk=m/2k=m/2, with one dummy editable coordinate at the target givingd=m\+1d=m\+1\. The return separates across themmrelevant rows,

J⁡\(x\)=1m​∑i=1mγ​xi\(1−γ\)​\(1−γ\+γ​xi\)\.J\(x\)=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\\frac\{\\gamma x\_\{i\}\}\{\(1\-\\gamma\)\(1\-\\gamma\+\\gamma x\_\{i\}\)\}\.Each summand is increasing and concave\. The continuous optimum assignsxi=1/2x\_\{i\}=1/2to every relevant row, whereas a deployable policy selectsm/2m/2rows and leaves the others unchanged\. The continuous\-to\-binary loss is therefore explicit\. Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)evaluates both the gap and its certificate in closed form\.

### 1\.2Related work

Pipage rounding originates in the classical exchange framework of\[[2](https://arxiv.org/html/2610.00325#bib.bib1)\]\. Recent work extends continuous relaxations and rounding beyond standard submodularity, including one\-sided\-smooth objectives and nonmonotone submodular maximization\[[14](https://arxiv.org/html/2610.00325#bib.bib7),[8](https://arxiv.org/html/2610.00325#bib.bib8)\]\. Here the objective is the discounted return of an MDP, and its exchange curvature is induced by the full policy\-dependent dynamics\.

Recent safe\-policy\-improvement work studies finite\-data guarantees, partial observability, scalable planning, reliable decision points, and learned models\[[37](https://arxiv.org/html/2610.00325#bib.bib9),[33](https://arxiv.org/html/2610.00325#bib.bib10),[10](https://arxiv.org/html/2610.00325#bib.bib11),[7](https://arxiv.org/html/2610.00325#bib.bib37),[6](https://arxiv.org/html/2610.00325#bib.bib12),[32](https://arxiv.org/html/2610.00325#bib.bib13),[15](https://arxiv.org/html/2610.00325#bib.bib28),[12](https://arxiv.org/html/2610.00325#bib.bib14)\]\. These methods control improvement relative to a baseline under data or model uncertainty\. We address the return lost at the next stage of the pipeline, when a continuous model\-based update must satisfy akk\-row deployment constraint\. Related work also studies stochastic optimization when the deployed solution must be deterministic\[[26](https://arxiv.org/html/2610.00325#bib.bib38)\]\. The constraint is also related to sparse and discrete optimization, where cardinality or binary structure is handled by hard thresholding, block\-coordinate methods, or continuous reformulations\[[39](https://arxiv.org/html/2610.00325#bib.bib41),[40](https://arxiv.org/html/2610.00325#bib.bib40),[38](https://arxiv.org/html/2610.00325#bib.bib42)\]\. Our starting point is an optimized continuous policy whose conversion to sparse binary deployment must be certified\.

Recent formal and robust\-MDP work studies parameter synthesis, structural constraints, uncertainty\-aware computation, and robust policy optimization\[[19](https://arxiv.org/html/2610.00325#bib.bib15),[30](https://arxiv.org/html/2610.00325#bib.bib27),[18](https://arxiv.org/html/2610.00325#bib.bib16),[5](https://arxiv.org/html/2610.00325#bib.bib17),[17](https://arxiv.org/html/2610.00325#bib.bib18),[16](https://arxiv.org/html/2610.00325#bib.bib19),[31](https://arxiv.org/html/2610.00325#bib.bib20),[34](https://arxiv.org/html/2610.00325#bib.bib21),[23](https://arxiv.org/html/2610.00325#bib.bib22),[25](https://arxiv.org/html/2610.00325#bib.bib23),[36](https://arxiv.org/html/2610.00325#bib.bib30),[22](https://arxiv.org/html/2610.00325#bib.bib31),[1](https://arxiv.org/html/2610.00325#bib.bib32),[4](https://arxiv.org/html/2610.00325#bib.bib33),[21](https://arxiv.org/html/2610.00325#bib.bib34),[41](https://arxiv.org/html/2610.00325#bib.bib35),[11](https://arxiv.org/html/2610.00325#bib.bib36),[35](https://arxiv.org/html/2610.00325#bib.bib39)\]\. Complementary second\-order policy\-optimization work analyzes Hessian information directly\[[24](https://arxiv.org/html/2610.00325#bib.bib24),[28](https://arxiv.org/html/2610.00325#bib.bib25),[20](https://arxiv.org/html/2610.00325#bib.bib29),[42](https://arxiv.org/html/2610.00325#bib.bib26)\]\. Our Bellman envelopes instead provide uniform first\- and second\-order sensitivity bounds over the policy cube, which we specialize to sparse deployment\.

### 1\.3Contributions

#### Certified deployment\.

Bellman envelopes and budget\-aware rounding geometry yield uniform and candidate\-specific return guarantees\. Algorithm[1](https://arxiv.org/html/2610.00325#alg1)constructs a binary policy with at most2​\(d−1\)2\(d\-1\)endpoint evaluations\.

#### Curvature and trajectory bounds\.

A lower\-bound family identifies the necessary dimension dependence, while an NP\-hardness result limits exact global curvature computation\. For an executed exchange, its rank\-two structure gives a weighted trajectory bound that avoids paying for curvature away from the path\.

#### Empirical behaviour\.

The experiments separate pre\-rounding certification, final policy quality, long\-horizon tightness, and computation cost\. They quantify when candidate geometry suffices, when trajectory integration is needed, and how validated arithmetic compares with exact rational computation\.

## 2Preliminaries

We useℝ\+\\mathbb\{R\}\_\{\+\}for the nonnegative reals and𝟏\\mathbf\{1\}for the all\-ones vector\. The vectorei∈ℝSe\_\{i\}\\in\\mathbb\{R\}^\{S\}selects a state row, whileεi∈ℝd\\varepsilon\_\{i\}\\in\\mathbb\{R\}^\{d\}selects a policy coordinate\. Fora∈ℝa\\in\\mathbb\{R\}, let\[a\]\+=max⁡\{a,0\}\\left\[a\\right\]\_\{\+\}=\\max\\\{a,0\\\}\. We writev=v\+−v−v=v^\{\+\}\-v^\{\-\}for the componentwise positive and negative parts of a vector\. The operatordiag⁡\(x\)\\operatorname\{diag\}\(x\)forms a diagonal matrix, and⊙\\odotdenotes outward\-rounded interval multiplication\. The cost of one discounted Bellman solve onSSstates is denoted byTBell​\(S\)T\_\{\\mathrm\{Bell\}\}\(S\)\.

### 2\.1Problem setting and assumptions

Let𝒮=\{1,…,S\}\\mathcal\{S\}=\\\{1,\\ldots,S\\\}be a finite state space\. Letγ∈\(0,1\)\\gamma\\in\(0,1\)be the discount, and letμ∈ℝ\+S\\mu\\in\\mathbb\{R\}\_\{\+\}^\{S\}satisfy𝟏⊤​μ=1\\mathbf\{1\}^\{\\top\}\\mu=1\. After relabeling, rows1,…,d1,\\ldots,dare editable, whered∈\{1,…,S\}d\\in\\\{1,\\ldots,S\\\}\. Each editable rowiihas a baseline action and one proposed action\. The weightxi∈\[0,1\]x\_\{i\}\\in\[0,1\]interpolates between them, giving

P⁡\(x\)\\displaystyle P\(x\)=P0\+∑i=1dxi​ei​di⊤,\\displaystyle=P^\{0\}\+\\sum\_\{i=1\}^\{d\}x\_\{i\}\\,e\_\{i\}d\_\{i\}^\{\\top\},r⁡\(x\)\\displaystyle r\(x\)=r0\+∑i=1dxi​ei​Δ​ri,\\displaystyle=r^\{0\}\+\\sum\_\{i=1\}^\{d\}x\_\{i\}\\,e\_\{i\}\\Delta r\_\{i\},x\\displaystyle x∈\[0,1\]d\.\\displaystyle\\in\[0,1\]^\{d\}\.\(2\)Heredi⊤d\_\{i\}^\{\\top\}is the difference between the two transition rows, andΔ​ri\\Delta r\_\{i\}is the reward difference\.

###### Assumption 2\.1\(Stochastic two\-action rows\)\.

P0P^\{0\}is stochastic\. For every editable rowii, bothP0i⋅P^\{0\}\_\{i\\cdot\}andP0i⋅\+di⊤P^\{0\}\_\{i\\cdot\}\+d\_\{i\}^\{\\top\}are probability distributions over𝒮\\mathcal\{S\}\.

Assumption[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1)makesP⁡\(x\)P\(x\)stochastic for every point in the cube\. Therefore

R⁡\(x\)=\(I−γ​P​\(x\)\)−1,V⁡\(x\)=R⁡\(x\)​r​\(x\),J⁡\(x\)=μ⊤​V​\(x\)R\(x\)=\(I\-\\gamma P\(x\)\)^\{\-1\},\\qquad V\(x\)=R\(x\)r\(x\),\\qquad J\(x\)=\\mu^\{\\top\}V\(x\)\(3\)are well defined\[[29](https://arxiv.org/html/2610.00325#bib.bib4)\]\. The functionJJis real analytic on a neighbourhood of the cube\. We use the budget sets in \([1](https://arxiv.org/html/2610.00325#S1.E1)\), withk∈\{0,…,d\}k\\in\\\{0,\\ldots,d\\\}\. Their relaxation gap is nonnegative and vanishes when the continuous and binary optima coincide\.

A second assumption concerns the arithmetic used to construct the bounds\.

###### Assumption 2\.2\(Exact or validated arithmetic\)\.

Bellman solves use exact rational arithmetic or directed outward rounding\[[27](https://arxiv.org/html/2610.00325#bib.bib5)\]\. In the latter case, the stochastic input, Bellman inequalities, residuals, and all downstream interval operations are enclosed\. Return comparisons in Algorithm[1](https://arxiv.org/html/2610.00325#alg1)are exact, or the selected endpoint is certified to have return at least that of the alternative\.

Ordinary floating\-point solves with residual padding do not satisfy this assumption\. The distinction is consequential in Section[6](https://arxiv.org/html/2610.00325#S6): double precision reports many zero bounds on the same cases for which exact arithmetic reports none\.

### 2\.2Sensitivity identities and rounding quantities

The rounding procedure uses coordinate increases and pairwise exchanges\. Differentiating \([3](https://arxiv.org/html/2610.00325#S2.E3)\) introduces three quantities,

qi​\(x\)\\displaystyle q\_\{i\}\(x\)=μ⊤​R​\(x\)​ei,\\displaystyle=\\mu^\{\\top\}R\(x\)e\_\{i\},ai​\(x\)\\displaystyle a\_\{i\}\(x\)=Δ​ri\+γ​di⊤​V​\(x\),\\displaystyle=\\Delta r\_\{i\}\+\\gamma d\_\{i\}^\{\\top\}V\(x\),bi​j​\(x\)\\displaystyle b\_\{ij\}\(x\)=γ​di⊤​R​\(x\)​ej,\\displaystyle=\\gamma d\_\{i\}^\{\\top\}R\(x\)e\_\{j\},\(4\)and the identities

∂iJ⁡\(x\)\\displaystyle\\partial\_\{i\}J\(x\)=qi​\(x\)​ai​\(x\),\\displaystyle=q\_\{i\}\(x\)a\_\{i\}\(x\),\(5\)Hi​i​\(x\)\\displaystyle H\_\{ii\}\(x\)=2​qi​\(x\)​bi​i​\(x\)​ai​\(x\),\\displaystyle=2q\_\{i\}\(x\)b\_\{ii\}\(x\)a\_\{i\}\(x\),\(6\)Hi​j​\(x\)\\displaystyle H\_\{ij\}\(x\)=qj​\(x\)​bj​i​\(x\)​ai​\(x\)\+qi​\(x\)​bi​j​\(x\)​aj​\(x\),i≠j\.\\displaystyle=q\_\{j\}\(x\)b\_\{ji\}\(x\)a\_\{i\}\(x\)\+q\_\{i\}\(x\)b\_\{ij\}\(x\)a\_\{j\}\(x\),\\quad i\\neq j\.\(7\)HereH​\(x\)=∇2J​\(x\)H\(x\)=\\nabla^\{2\}J\(x\)\. These are classical Markov\-chain sensitivity identities\[[9](https://arxiv.org/html/2610.00325#bib.bib2),[13](https://arxiv.org/html/2610.00325#bib.bib3)\]\. Their factored form is important because every factor is evaluated at the same policyxx\.

###### Definition 2\.3\(Quantities controlling the rounding loss\)\.

Define the largest negative coordinate slope and the largest negative pairwise exchange curvature as

τ\\displaystyle\\tau=maxisupx∈\[0,1\]d\[−∂iJ\(x\)\]\+,\\displaystyle=\\max\_\{i\}\\ \\sup\_\{x\\in\[0,1\]^\{d\}\}\\left\[\-\\partial\_\{i\}J\(x\)\\right\]\_\{\+\},\(8\)β\\displaystyle\\beta=max⁡supx∈\[0,1\]di<j⁡\[−\(εi−εj\)⊤​H​\(x\)​\(εi−εj\)\]\+\.\\displaystyle=\\max\_\{i<j\}\\ \\sup\_\{x\\in\[0,1\]^\{d\}\}\\left\[\-\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)^\{\\top\}H\(x\)\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)\\right\]\_\{\+\}\.\(9\)Whend=1d=1, the pairwise maximum is empty andβ=0\\beta=0\.

Thus every coordinate derivative is at least−τ\-\\tau, and every exchange line has second derivative at least−β\-\\beta\. The next section derives tractable upper bounds\. Sections[4](https://arxiv.org/html/2610.00325#S4)and[5](https://arxiv.org/html/2610.00325#S5)then study their dimension dependence and the cost of evaluatingβ\\betaexactly\.

## 3Bellman bounds for rounding

This section turns Bellman value bounds into a constructive rounding certificate\. Lemma[3\.1](https://arxiv.org/html/2610.00325#S3.Thmtheorem1)first bounds every policy in the continuous family\. Proposition[3\.2](https://arxiv.org/html/2610.00325#S3.Thmtheorem2)propagates these envelopes to the required derivatives, and Theorem[3\.3](https://arxiv.org/html/2610.00325#S3.Thmtheorem3)supplies the rounding guarantee\.

### 3\.1Bellman envelopes

Consider an auxiliary discounted control problem with the two endpoint actions at each editable row\. Every unedited row retains its fixed action\. LetV¯\\underline\{V\}andV¯\\overline\{V\}be the fixed points of the min\- and max\-Bellman operators, soV¯s≤Vsπ≤V¯s\\underline\{V\}\_\{s\}\\leq V^\{\\pi\}\_\{s\}\\leq\\overline\{V\}\_\{s\}for every stationary randomized policyπ\\piand every statess\. For each editable statejj, leth¯j\\underline\{h\}\_\{j\}andh¯j\\overline\{h\}\_\{j\}be the corresponding min/max value functions when the stage reward iseje\_\{j\}\.

###### Lemma 3\.1\(Bellman envelope\)\.

Under Assumption[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1), everyx∈\[0,1\]dx\\in\[0,1\]^\{d\}satisfies

V¯≤V⁡\(x\)≤V¯,h¯j≤R⁡\(x\)​ej≤h¯jfor every​j∈\{1,…,d\}\.\\underline\{V\}\\leq V\(x\)\\leq\\overline\{V\},\\qquad\\underline\{h\}\_\{j\}\\leq R\(x\)e\_\{j\}\\leq\\overline\{h\}\_\{j\}\\quad\\text\{for every \}j\\in\\\{1,\\ldots,d\\\}\.\(10\)All inequalities are componentwise\.

###### Proof of Lemma[3\.1](https://arxiv.org/html/2610.00325#S3.Thmtheorem1)\.

Everyx∈\[0,1\]dx\\in\[0,1\]^\{d\}defines a stationary randomized policy over the two endpoint actions at each editable row\. Standard discounted Bellman optimality therefore bounds its value componentwise,V¯≤V⁡\(x\)≤V¯\.\\underline\{V\}\\leq V\(x\)\\leq\\overline\{V\}\.Apply the same argument to the auxiliary control problem with stage rewardeje\_\{j\}\. The value of policyxxin this problem isR⁡\(x\)​ejR\(x\)e\_\{j\}, which givesh¯j≤R⁡\(x\)​ej≤h¯j\.\\underline\{h\}\_\{j\}\\leq R\(x\)e\_\{j\}\\leq\\overline\{h\}\_\{j\}\.Both statements hold simultaneously for everyxxand editablejj\. ∎

Splittingdi=di\+−di−d\_\{i\}=d\_\{i\}^\{\+\}\-d\_\{i\}^\{\-\}propagates Lemma[3\.1](https://arxiv.org/html/2610.00325#S3.Thmtheorem1)to intervals for the sensitivity quantities in \([4](https://arxiv.org/html/2610.00325#S2.E4)\),

Qi=\\displaystyle Q\_\{i\}=\{\}\[μ⊤​h¯i,μ⊤​h¯i\],\\displaystyle\[\\mu^\{\\top\}\\underline\{h\}\_\{i\},\\ \\mu^\{\\top\}\\overline\{h\}\_\{i\}\],\(11\)Ai=\\displaystyle A\_\{i\}=\{\}\[Δ​ri\+γ⁡\{\(di\+\)⊤​V¯−\(di−\)⊤​V¯\},Δ​ri\+γ⁡\{\(di\+\)⊤​V¯−\(di−\)⊤​V¯\}\],\\displaystyle\\Bigl\[\\Delta r\_\{i\}\+\\gamma\\\{\(d\_\{i\}^\{\+\}\)^\{\\top\}\\underline\{V\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\overline\{V\}\\\},\\ \\Delta r\_\{i\}\+\\gamma\\\{\(d\_\{i\}^\{\+\}\)^\{\\top\}\\overline\{V\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\underline\{V\}\\\}\\Bigr\],\(12\)Bi​j=\\displaystyle B\_\{ij\}=\{\}γ⁡\[\(di\+\)⊤​h¯j−\(di−\)⊤​h¯j,\(di\+\)⊤​h¯j−\(di−\)⊤​h¯j\]\.\\displaystyle\\gamma\\Bigl\[\(d\_\{i\}^\{\+\}\)^\{\\top\}\\underline\{h\}\_\{j\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\overline\{h\}\_\{j\},\\ \(d\_\{i\}^\{\+\}\)^\{\\top\}\\overline\{h\}\_\{j\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\underline\{h\}\_\{j\}\\Bigr\]\.\(13\)

### 3\.2Sensitivity certificate

Using Minkowski interval addition and outward\-rounded multiplication⊙\\odot, define

Gi\\displaystyle G\_\{i\}=Qi⊙Ai,\\displaystyle=Q\_\{i\}\\odot A\_\{i\},τ^\\displaystyle\\widehat\{\\tau\}=maxi\[−infGi\]\+,\\displaystyle=\\max\_\{i\}\\left\[\-\\inf G\_\{i\}\\right\]\_\{\+\},\(14\)ℋi​i\\displaystyle\\mathcal\{H\}\_\{ii\}=2​Qi⊙Bi​i⊙Ai,\\displaystyle=2\\,Q\_\{i\}\\odot B\_\{ii\}\\odot A\_\{i\},ℋi​j\\displaystyle\\mathcal\{H\}\_\{ij\}=\(Qj⊙Bj​i⊙Ai\)\+\(Qi⊙Bi​j⊙Aj\),\\displaystyle=\(Q\_\{j\}\\odot B\_\{ji\}\\odot A\_\{i\}\)\+\(Q\_\{i\}\\odot B\_\{ij\}\\odot A\_\{j\}\),\(15\)S¯i​j\\displaystyle\\underline\{S\}\_\{ij\}=infℋi​i\+infℋj​j−2​supℋi​j,\\displaystyle=\\inf\\mathcal\{H\}\_\{ii\}\+\\inf\\mathcal\{H\}\_\{jj\}\-2\\sup\\mathcal\{H\}\_\{ij\},β^\\displaystyle\\widehat\{\\beta\}=maxi<j⁡\[−S¯i​j\]\+,\\displaystyle=\\max\_\{i<j\}\\left\[\-\\underline\{S\}\_\{ij\}\\right\]\_\{\+\},\(16\)withβ^=0\\widehat\{\\beta\}=0whend=1d=1\.

###### Proposition 3\.2\(Sensitivity certificate\)\.

Let Assumptions[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1)and[2\.2](https://arxiv.org/html/2610.00325#S2.Thmtheorem2)hold\. For everyx∈\[0,1\]dx\\in\[0,1\]^\{d\}and all editablei,ji,j,qi​\(x\)∈Qi,ai​\(x\)∈Ai,bi​j​\(x\)∈Bi​j\.q\_\{i\}\(x\)\\in Q\_\{i\},\\quad a\_\{i\}\(x\)\\in A\_\{i\},\\quad b\_\{ij\}\(x\)\\in B\_\{ij\}\.Consequently,τ≤τ^,β≤β^\.\\tau\\leq\\widehat\{\\tau\},\\qquad\\beta\\leq\\widehat\{\\beta\}\.

###### Proof of Proposition[3\.2](https://arxiv.org/html/2610.00325#S3.Thmtheorem2)\.

Sinceμ≥0\\mu\\geq 0, Lemma[3\.1](https://arxiv.org/html/2610.00325#S3.Thmtheorem1)givesqi​\(x\)=μ⊤​R​\(x\)​ei∈Qiq\_\{i\}\(x\)=\\mu^\{\\top\}R\(x\)e\_\{i\}\\in Q\_\{i\}\. For any componentwise boxz¯≤z≤z¯\\underline\{z\}\\leq z\\leq\\overline\{z\}, the exact extrema ofdi⊤​z=\(di\+\)⊤​z−\(di−\)⊤​zd\_\{i\}^\{\\top\}z=\(d\_\{i\}^\{\+\}\)^\{\\top\}z\-\(d\_\{i\}^\{\-\}\)^\{\\top\}zare\(di\+\)⊤​z¯−\(di−\)⊤​z¯and\(di\+\)⊤​z¯−\(di−\)⊤​z¯\.\(d\_\{i\}^\{\+\}\)^\{\\top\}\\underline\{z\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\overline\{z\}\\quad\\text\{and\}\\quad\(d\_\{i\}^\{\+\}\)^\{\\top\}\\overline\{z\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\underline\{z\}\.Takingz=V⁡\(x\)z=V\(x\)andz=R⁡\(x\)​ejz=R\(x\)e\_\{j\}provesai​\(x\)∈Aia\_\{i\}\(x\)\\in A\_\{i\}andbi​j​\(x\)∈Bi​jb\_\{ij\}\(x\)\\in B\_\{ij\}\.

Equation \([5](https://arxiv.org/html/2610.00325#S2.E5)\) then gives∂iJ⁡\(x\)∈Gi\\partial\_\{i\}J\(x\)\\in G\_\{i\}\. Hence\[−∂iJ\(x\)\]\+≤\[−infGi\]\+≤τ^\.\\left\[\-\\partial\_\{i\}J\(x\)\\right\]\_\{\+\}\\leq\\left\[\-\\inf G\_\{i\}\\right\]\_\{\+\}\\leq\\widehat\{\\tau\}\.Taking the maximum overiiand the supremum overxxyieldsτ≤τ^\\tau\\leq\\widehat\{\\tau\}\. Equations \([6](https://arxiv.org/html/2610.00325#S2.E6)\) and \([7](https://arxiv.org/html/2610.00325#S2.E7)\) giveHi​i​\(x\)∈ℋi​iH\_\{ii\}\(x\)\\in\\mathcal\{H\}\_\{ii\}andHi​j​\(x\)∈ℋi​jH\_\{ij\}\(x\)\\in\\mathcal\{H\}\_\{ij\}\. Therefore

\(εi−εj\)⊤​H​\(x\)​\(εi−εj\)=Hi​i​\(x\)\+Hj​j​\(x\)−2​Hi​j​\(x\)≥S¯i​j\.\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)^\{\\top\}H\(x\)\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)=H\_\{ii\}\(x\)\+H\_\{jj\}\(x\)\-2H\_\{ij\}\(x\)\\geq\\underline\{S\}\_\{ij\}\.Taking negative parts, the pairwise maximum, and the supremum overxxgivesβ≤β^\\beta\\leq\\widehat\{\\beta\}\. Directed outward interval operations preserve every inclusion\. Exact rational arithmetic adds zero numerical\-roundoff width\. ∎

### 3\.3Certified rounding

Forqd,k:=min⁡\{k,⌊d/2⌋\}q\_\{d,k\}:=\\min\\\{k,\\lfloor d/2\\rfloor\\\}, define the budget coefficientcd,k:=qd,k​\(d−qd,k\)/\(4​d\)c\_\{d,k\}:=q\_\{d,k\}\(d\-q\_\{d,k\}\)/\(4d\)\.

###### Theorem 3\.3\(Budget\-aware certified rounding\)\.

Under Assumptions[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1)and[2\.2](https://arxiv.org/html/2610.00325#S2.Thmtheorem2), Algorithm[1](https://arxiv.org/html/2610.00325#alg1)returnsy∈𝒞kbiny\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}for everyx∈𝒞kx\\in\\mathcal\{C\}\_\{k\}, withJ⁡\(y\)≥J⁡\(x\)−BunifJ\(y\)\\geq J\(x\)\-B\_\{\\mathrm\{unif\}\}andGap⁡\(𝒞k\)≤Bunif\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)\\leq B\_\{\\mathrm\{unif\}\}, whereBunif:=τ^\+cd,k​β^B\_\{\\mathrm\{unif\}\}:=\\widehat\{\\tau\}\+c\_\{d,k\}\\widehat\{\\beta\}fork\>0k\>0andBunif:=0B\_\{\\mathrm\{unif\}\}:=0fork=0k=0\.

For comparison with the original experiments, we also report the legacy boundℬBell:=τ^\+\(d−1\)​β^/8\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}:=\\widehat\{\\tau\}\+\(d\-1\)\\widehat\{\\beta\}/8\. The new bound satisfiesBunif≤ℬBellB\_\{\\mathrm\{unif\}\}\\leq\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}: ford≥2d\\geq 2,cd,k≤d/16≤\(d−1\)/8c\_\{d,k\}\\leq d/16\\leq\(d\-1\)/8; ford=1d=1,β^=0\\widehat\{\\beta\}=0\. Moreover,cd,k≤k/4c\_\{d,k\}\\leq k/4, so its coefficient stays bounded at fixed budget\.

Algorithm[1](https://arxiv.org/html/2610.00325#alg1), stated in Appendix[A](https://arxiv.org/html/2610.00325#A1), first raises coordinates until their sum is integral\. It then exchanges mass between fractional coordinates and selects the better endpoint\. Each exchange makes at least one coordinate integral\. At mostd−1d\-1exchanges and2​\(d−1\)2\(d\-1\)return evaluations are required\. These endpoint evaluations are separate from the2​d\+22d\+2Bellman solves used to construct the reusable certificate\. Every endpoint comparison must be exact or certified under Assumption[2\.2](https://arxiv.org/html/2610.00325#S2.Thmtheorem2)\.

The model\-only guarantee depends on the MDP and budget, but not on the candidate\. A zero bound therefore proves equality of the continuous and binary optima\. The proof usesΦ⁡\(z\):=∑izi​\(1−zi\)\\Phi\(z\):=\\sum\_\{i\}z\_\{i\}\(1\-z\_\{i\}\)\. At the integer\-sum point after Phase 1,ℓ=𝟏⊤​z≤k\\ell=\\mathbf\{1\}^\{\\top\}z\\leq k, and Cauchy–Schwarz givesΦ⁡\(z\)≤ℓ⁡\(d−ℓ\)/d≤4​cd,k\\Phi\(z\)\\leq\\ell\(d\-\\ell\)/d\\leq 4c\_\{d,k\}\. Telescoping the exchange\-potential decrease then charges at mostβ^​Φ​\(z\)/4\\widehat\{\\beta\}\\Phi\(z\)/4in Phase 2\. Appendix[A](https://arxiv.org/html/2610.00325#A1)gives the proof without additional solves\.

The same Bellman intervals also yield a sharper guarantee once a particular continuous candidate is available\. Fix once and for all a deterministic Phase\-1 fill order \(we use increasing coordinate index\) and letz=z⁡\(x\)z=z\(x\)be the point obtained by raising coordinates in that order until𝟏⊤​z=⌈𝟏⊤​x⌉\\mathbf\{1\}^\{\\top\}z=\\lceil\\mathbf\{1\}^\{\\top\}x\\rceil\. Define

τ^i:=\[−infGi\]\+,F\(z\):=\{i:0<zi<1\},β^F⁡\(z\):=maxi<ji,j∈F⁡\(z\)\[−S¯i​j\]\+,\\widehat\{\\tau\}\_\{i\}:=\\left\[\-\\inf G\_\{i\}\\right\]\_\{\+\},\\qquad F\(z\):=\\\{i:0<z\_\{i\}<1\\\},\\qquad\\widehat\{\\beta\}\_\{F\(z\)\}:=\\max\_\{\\begin\{subarray\}\{c\}i<j\\\\ i,j\\in F\(z\)\\end\{subarray\}\}\\left\[\-\\underline\{S\}\_\{ij\}\\right\]\_\{\+\},\(17\)withβ^F⁡\(z\)=0\\widehat\{\\beta\}\_\{F\(z\)\}=0when\|F⁡\(z\)\|<2\|F\(z\)\|<2\. LetΦ⁡\(z\):=∑i=1dzi​\(1−zi\)\\Phi\(z\):=\\sum\_\{i=1\}^\{d\}z\_\{i\}\(1\-z\_\{i\}\),Δi:=zi−xi\\Delta\_\{i\}:=z\_\{i\}\-x\_\{i\}and define the candidate\-specific pre\-rounding certificateBcand​\(x\):=∑i=1dΔi​τ^i\+β^F⁡\(z\)4​Φ​\(z\)\.B\_\{\\mathrm\{cand\}\}\(x\):=\\sum\_\{i=1\}^\{d\}\\Delta\_\{i\}\\widehat\{\\tau\}\_\{i\}\+\\frac\{\\widehat\{\\beta\}\_\{F\(z\)\}\}\{4\}\\Phi\(z\)\.

###### Proposition 3\.4\(Candidate\-specific pre\-rounding certificate\)\.

Let Assumptions[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1)and[2\.2](https://arxiv.org/html/2610.00325#S2.Thmtheorem2)hold, and let Algorithm[1](https://arxiv.org/html/2610.00325#alg1)use the fixed Phase\-1 fill order above\. For everyx∈𝒞kx\\in\\mathcal\{C\}\_\{k\}, its outputy∈𝒞kbiny\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}satisfiesJ⁡\(y\)≥J⁡\(x\)−Bcand​\(x\),Bcand​\(x\)≤Bunif≤ℬBell\.J\(y\)\\geq J\(x\)\-B\_\{\\mathrm\{cand\}\}\(x\),\\quad B\_\{\\mathrm\{cand\}\}\(x\)\\leq B\_\{\\mathrm\{unif\}\}\\leq\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}\.ThusBcand​\(x\)B\_\{\\mathrm\{cand\}\}\(x\)is available once the continuous candidate is known and before any pairwise endpoint comparison\.

The sharper bound retains candidate geometry that Theorem[3\.3](https://arxiv.org/html/2610.00325#S3.Thmtheorem3)discards\. For an exchange of coordinatesi,ji,jover the maximal interval\[a,b\]\[a,b\], Proposition[3\.2](https://arxiv.org/html/2610.00325#S3.Thmtheorem2)gives the pair\-specific curvature boundβ^i​j=\[−S¯i​j\]\+\\widehat\{\\beta\}\_\{ij\}=\\left\[\-\\underline\{S\}\_\{ij\}\\right\]\_\{\+\}, and the proof of Theorem[3\.3](https://arxiv.org/html/2610.00325#S3.Thmtheorem3)yields the one\-step chargeβ^i​j​\(−a\)​b/2\\widehat\{\\beta\}\_\{ij\}\(\-a\)b/2\. Moreover, every maximal exchange satisfies the potential identityΦ⁡\(zt\)−Φ⁡\(zt\+1\)=2​\(−at\)​bt\.\\Phi\(z^\{t\}\)\-\\Phi\(z^\{t\+1\}\)=2\(\-a\_\{t\}\)b\_\{t\}\.Since the fractional support can only shrink and the final point is binary,∑t\(−at\)​bt=Φ⁡\(z\)/2\\sum\_\{t\}\(\-a\_\{t\}\)b\_\{t\}=\\Phi\(z\)/2\. This identity yields the second term ofBcandB\_\{\\mathrm\{cand\}\}\. The first term records coordinate\-specific charges along the deterministic fill path\. Appendix[A](https://arxiv.org/html/2610.00325#A1)provides the proof\.

The reusable certificate is constructed once per instance\. Computing the Bellman envelopes and interval quantities takes2​d\+22d\+2Bellman solves,O⁡\(d2​S\)O\(d^\{2\}S\)interval operations, and anO⁡\(d2\)O\(d^\{2\}\)scan\. The total cost is\(2​d\+2\)​TBell​\(S\)\+O⁡\(d2​S\)\(2d\+2\)T\_\{\\mathrm\{Bell\}\}\(S\)\+O\(d^\{2\}S\)\. Given a candidatexx,Bcand​\(x\)B\_\{\\mathrm\{cand\}\}\(x\)uses the storedGiG\_\{i\}andS¯i​j\\underline\{S\}\_\{ij\}, so no further Bellman solve is needed\. The fill and potential costO⁡\(d\)O\(d\)in total, while the support scan costs at mostO⁡\(d2\)O\(d^\{2\}\)\. This model\-only construction is most attractive whend≪Sd\\ll S\. Whend=Sd=S, the number of Bellman solves is twice the number of states\. Rounding is then performed once for each candidate\.

### 3\.4Computation and interval conservatism

The preceding operation count does not include rational bit growth\. WithLL\-bit inputs, exact rational arithmetic has bit complexity polynomial inSS,dd, andLL\. Validated floating point instead adds anO⁡\(S2\)O\(S^\{2\}\)residual pass to each solve\. Its intervals have positive width, while outward endpoints preserve Proposition[3\.2](https://arxiv.org/html/2610.00325#S3.Thmtheorem2)\.

The interval calculation treatsQiQ\_\{i\},AiA\_\{i\}, andBi​jB\_\{ij\}as independent boxes and can therefore include endpoint combinations that no commonxxrealizes\. The excess width vanishes when the Bellman envelopes are tight\. Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)givesβ^=β\\widehat\{\\beta\}=\\betaon the example family\.

## 4Dimension dependence and long\-horizon conservatism

At fixedkk, the budget\-aware coefficientcd,kc\_\{d,k\}remains bounded\. Linear dependence on dimension is nevertheless unavoidable whenk=Θ⁡\(d\)k=\\Theta\(d\)\. The family from Section[1\.1](https://arxiv.org/html/2610.00325#S1.SS1)also distinguishes exchange\-count slack from curvature conservatism\.

###### Proposition 4\.1\(Fixed\-discount lower\-bound family\)\.

For every evenm≥2m\\geq 2andγ∈\(0,1\)\\gamma\\in\(0,1\), the illustrative family is a transition\-only MDP satisfying Assumption[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1), withd=m\+1d=m\+1andk=m/2k=m/2\. Writingδ=1−γ\\delta=1\-\\gamma, it satisfiesτ^=τ=0\\widehat\{\\tau\}=\\tau=0,β^=β=4​γ2/\(m​δ3\)\\widehat\{\\beta\}=\\beta=4\\gamma^\{2\}/\(m\\delta^\{3\}\)andGap⁡\(𝒞k\)=γ2/\[2​δ​\(2−γ\)\]\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=\\gamma^\{2\}/\[2\\delta\(2\-\\gamma\)\]\. At its continuous optimum,Bcand​\(x⋆\)=γ2/\(4​δ3\)B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\)=\\gamma^\{2\}/\(4\\delta^\{3\}\),Bunif=m\+2m\+1​Bcand​\(x⋆\)B\_\{\\mathrm\{unif\}\}=\\frac\{m\+2\}\{m\+1\}B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\), andℬBell=2​Bcand​\(x⋆\)\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}=2B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\)\.

###### Corollary 4\.2\(A linear dimension coefficient is necessary\)\.

Fixγ∈\(0,1\)\\gamma\\in\(0,1\)\. Ifcd≥0c\_\{d\}\\geq 0satisfiesGap⁡\(𝒞k\)≤τ\+cd​β\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)\\leq\\tau\+c\_\{d\}\\betaon every member of this family, thencd≥\(d−1\)​\(1−γ\)2/\[8​\(2−γ\)\]c\_\{d\}\\geq\(d\-1\)\(1\-\\gamma\)^\{2\}/\[8\(2\-\\gamma\)\]\. Thuscd=Ω⁡\(d\)c\_\{d\}=\\Omega\(d\)along this family, whose budget isk=\(d−1\)/2k=\(d\-1\)/2\.

###### Proof\.

Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)givesτ=0\\tau=0andβ\>0\\beta\>0, socd≥Gap⁡\(𝒞k\)/β=m​\(1−γ\)2/\[8​\(2−γ\)\]c\_\{d\}\\geq\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)/\\beta=m\(1\-\\gamma\)^\{2\}/\[8\(2\-\\gamma\)\]\. ∎

Appendix[B](https://arxiv.org/html/2610.00325#A2)derives these formulas\. Fromx⋆x^\{\\star\}, Algorithm[1](https://arxiv.org/html/2610.00325#alg1)reaches a binary optimum afterm/2m/2exchanges, so its actual loss equalsGap⁡\(𝒞k\)\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)\. The legacy bound overcounts the exchange contribution by a factor of two\. The uniform bound reduces this slack to\(m\+2\)/\(m\+1\)\(m\+2\)/\(m\+1\)relative to the candidate bound\. Nevertheless,Bcand​\(x⋆\)/Gap⁡\(𝒞k\)=\(2−γ\)/\(2​δ2\)B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\)/\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=\(2\-\\gamma\)/\(2\\delta^\{2\}\)still diverges asγ↑1\\gamma\\uparrow 1\. Hereβ^=β\\widehat\{\\beta\}=\\beta, so interval propagation does not explain this residual slack\.

One might suspect that the long\-horizon conservatism comes only from evaluating curvature globally\. On this family, even exact segment\-local extrema retain the same divergent order\. An executed exchange hasg⁡\(t\)=J⁡\(z\+t⁡\(εi−εj\)\)g\(t\)=J\(z\+t\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)\)witht∈\[−1/2,1/2\]t\\in\[\-1/2,1/2\]\. Although it starts at two half\-integral coordinates, its endpoints set one coordinate to zero, retaining large curvature\. The exact segment maximum isβseg=2​γ2​\(δ−3\+1\)/m\\beta\_\{\\mathrm\{seg\}\}=2\\gamma^\{2\}\(\\delta^\{\-3\}\+1\)/m\. Summing its one\-step charges givesBseg=γ2​\(δ−3\+1\)/8B\_\{\\mathrm\{seg\}\}=\\gamma^\{2\}\(\\delta^\{\-3\}\+1\)/8, and henceBseg/Gap⁡\(𝒞k\)=\(2−γ\)​\(1\+δ3\)/\(4​δ2\)B\_\{\\mathrm\{seg\}\}/\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=\(2\-\\gamma\)\(1\+\\delta^\{3\}\)/\(4\\delta^\{2\}\)\. Thus segment\-local maximization alone does not remove the long\-horizon slack\.

On this family, weighted trajectory interpolation removes the residual slack\. For anyC2C^\{2\}exchange function on\[a,b\]\[a,b\]witha<0<ba<0<b, letKa,b​\(t\)=b⁡\(t−a\)/\(b−a\)K\_\{a,b\}\(t\)=b\(t\-a\)/\(b\-a\)fort≤0t\\leq 0andKa,b​\(t\)=\(−a\)​\(b−t\)/\(b−a\)K\_\{a,b\}\(t\)=\(\-a\)\(b\-t\)/\(b\-a\)fort≥0t\\geq 0\. The nonnegative kernel gives the loss bound\[g⁡\(0\)−max⁡\{g⁡\(a\),g⁡\(b\)\}\]\+≤∫abKa,b​\(t\)​\[−g′′​\(t\)\]\+​𝑑t\[g\(0\)\-\\max\\\{g\(a\),g\(b\)\\\}\]\_\{\+\}\\leq\\int\_\{a\}^\{b\}K\_\{a,b\}\(t\)\[\-g^\{\\prime\\prime\}\(t\)\]\_\{\+\}\\,dt\. A constant curvature bound recovers the old charge because∫abKa,b​\(t\)​𝑑t=\(−a\)​b/2\\int\_\{a\}^\{b\}K\_\{a,b\}\(t\)\\,dt=\(\-a\)b/2\. On this family,g′′<0g^\{\\prime\\prime\}<0andg⁡\(a\)=g⁡\(b\)g\(a\)=g\(b\), so the integral equals the actual one\-step loss\. Summing yieldsBint=Gap⁡\(𝒞k\)B\_\{\\mathrm\{int\}\}=\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)for everyγ\\gamma\. Atγ=0\.95\\gamma=0\.95, the candidate and segment\-maximum ratios are 210 and 105\.013, respectively, whereas the exact integral ratio is 1; reliable 256\-subinterval upper sums give 1\.044\. Appendix[B\.6](https://arxiv.org/html/2610.00325#A2.SS6)proves the identity and Appendix[D\.9](https://arxiv.org/html/2610.00325#A4.SS9)reports exact\-rational checks\. The same interpolation bound can be computed on general exchanges\.

###### Proposition 4\.3\(Rational exchange representation\)\.

Under Assumption[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1), every feasible exchange hasg⁡\(t\)=p⁡\(t\)/q⁡\(t\)g\(t\)=p\(t\)/q\(t\), wheredeg⁡p,deg⁡q≤2\\deg p,\\deg q\\leq 2,q⁡\(0\)=1q\(0\)=1, andq⁡\(t\)\>0q\(t\)\>0throughout its interval\. Moreover,g′′​\(t\)=h⁡\(t\)/q​\(t\)3g^\{\\prime\\prime\}\(t\)=h\(t\)/q\(t\)^\{3\}withdeg⁡h≤3\\deg h\\leq 3\.

#### Computable trajectory bound\.

Appendix[B\.7](https://arxiv.org/html/2610.00325#A2.SS7)derives the rational coefficients from a rank\-two resolvent update\. Exact quadratic extrema and Bernstein polynomial bounds enclose\[−g′′\]\+\[\-g^\{\\prime\\prime\}\]\_\{\+\}on each subinterval\. Multiplication by the exact kernel integrals gives a reliable upper sumUtU\_\{t\}for each exchange\. With Phase\-1 outputzz, defineBloc=\[J⁡\(x\)−J⁡\(z\)\]\+\+∑tUtB\_\{\\mathrm\{loc\}\}=\[J\(x\)\-J\(z\)\]\_\{\+\}\+\\sum\_\{t\}U\_\{t\}\. Then\[J⁡\(x\)−J⁡\(y\)\]\+≤Bloc\[J\(x\)\-J\(y\)\]\_\{\+\}\\leq B\_\{\\mathrm\{loc\}\}\. The resulting certificate is available during rounding and does not require global Bellman envelopes\. Section[6](https://arxiv.org/html/2610.00325#S6)evaluates its tightness and cost\. Before the exchange trajectory is known, certification still relies onBunifB\_\{\\mathrm\{unif\}\}orBcandB\_\{\\mathrm\{cand\}\}\.

## 5Complexity of exact curvature

Theorem[3\.3](https://arxiv.org/html/2610.00325#S3.Thmtheorem3)uses the tractable upper boundβ^\\widehat\{\\beta\}in place ofβ\\beta\. Could exact curvature provide an efficient, uniformly sharper alternative? The threshold problem is NP\-hard even on a strongly restricted MDP class, and its binary restriction is NP\-complete\.

AllNNrows in this section are editable\. Forv∈ℝNv\\in\\mathbb\{R\}^\{N\}, define

κℳ​\(v\)\\displaystyle\\kappa\_\{\\mathcal\{M\}\}\(v\)=supx∈\[0,1\]N\[−v⊤​∇2J​\(x\)​v\]\+,\\displaystyle=\\sup\_\{x\\in\[0,1\]^\{N\}\}\\left\[\-v^\{\\top\}\\nabla^\{2\}J\(x\)v\\right\]\_\{\+\},κℳbin​\(v\)\\displaystyle\\kappa\_\{\\mathcal\{M\}\}^\{\\mathrm\{bin\}\}\(v\)=maxx∈\{0,1\}N⁡\[−v⊤​∇2J​\(x\)​v\]\+,\\displaystyle=\\max\_\{x\\in\\\{0,1\\\}^\{N\}\}\\left\[\-v^\{\\top\}\\nabla^\{2\}J\(x\)v\\right\]\_\{\+\},\(18\)βℳ\\displaystyle\\beta\_\{\\mathcal\{M\}\}=maxa<b⁡κℳ​\(εa−εb\),\\displaystyle=\\max\_\{a<b\}\\kappa\_\{\\mathcal\{M\}\}\(\\varepsilon\_\{a\}\-\\varepsilon\_\{b\}\),βℳbin\\displaystyle\\beta\_\{\\mathcal\{M\}\}^\{\\mathrm\{bin\}\}=maxa<b⁡κℳbin​\(εa−εb\)\.\\displaystyle=\\max\_\{a<b\}\\kappa\_\{\\mathcal\{M\}\}^\{\\mathrm\{bin\}\}\(\\varepsilon\_\{a\}\-\\varepsilon\_\{b\}\)\.\(19\)
A Woodbury elimination exposes the relevant dependence on the policy variables\. LetD=\[d1⋯dN\]D=\[d\_\{1\}\\ \\cdots\\ d\_\{N\}\],X=diag⁡\(x\)X=\\operatorname\{diag\}\(x\),R0=\(I−γ​P0\)−1R\_\{0\}=\(I\-\\gamma P^\{0\}\)^\{\-1\},u⊤=μ⊤​R0u^\{\\top\}=\\mu^\{\\top\}R\_\{0\},C=γ​D⊤​R0C=\\gamma D^\{\\top\}R\_\{0\}, anda=Δ\+γ​D⊤​R0​r0a=\\Delta\+\\gamma D^\{\\top\}R\_\{0\}r^\{0\}\. ThenJ⁡\(x\)=J⁡\(0\)\+u⊤​\(I−X​C\)−1​X​a\.J\(x\)=J\(0\)\+u^\{\\top\}\(I\-XC\)^\{\-1\}Xa\.Let𝒢⁡\(C\)\\mathcal\{G\}\(C\)contain the arci→ji\\to jwhenCi​j≠0C\_\{ij\}\\neq 0\.

###### Definition 5\.1\(Restricted MDP class𝔅3\\mathfrak\{B\}\_\{3\}\)\.

The class𝔅3\\mathfrak\{B\}\_\{3\}contains rational row\-mixture MDPs satisfying Assumption[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1), withγ=1/2\\gamma=1/2, a point\-mass initial distribution, two actions per row, rewards in\[0,1\]\[0,1\], strictly positive transition endpoints, and acyclic𝒢⁡\(C\)\\mathcal\{G\}\(C\)of depth at most three\. Membership is decidable in polynomial time\.

###### Theorem 5\.2\(Complexity of exact pairwise curvature\)\.

The language\{⟨ℳ,T⟩:ℳ∈𝔅3,βℳbin≥T\}\\\{\\langle\\mathcal\{M\},T\\rangle:\\mathcal\{M\}\\in\\mathfrak\{B\}\_\{3\},\\ \\beta\_\{\\mathcal\{M\}\}^\{\\mathrm\{bin\}\}\\geq T\\\}is NP\-complete, and thresholding the continuous\-cube quantityβℳ\\beta\_\{\\mathcal\{M\}\}is NP\-hard\.

#### The construction\.

The proof maps unweighted MAX\-CUT to a rational instanceℳG∈𝔅3\\mathcal\{M\}\_\{G\}\\in\\mathfrak\{B\}\_\{3\}\. After padding the graph, the construction creates one designated exchange\(p,q\)\(p,q\)whose curvature satisfiesβℳG=βℳGbin=κℳG​\(εp−εq\)=αG​\{Λ​n−m\+MaxCut⁡\(G\)\},\\beta\_\{\\mathcal\{M\}\_\{G\}\}=\\beta\_\{\\mathcal\{M\}\_\{G\}\}^\{\\mathrm\{bin\}\}=\\kappa\_\{\\mathcal\{M\}\_\{G\}\}\(\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}\)=\\alpha\_\{G\}\\\{\\Lambda n\-m\+\\MaxCut\(G\)\\\},whereΛ=2​m\+1\\Lambda=2m\+1andαG\>0\\alpha\_\{G\}\>0has polynomial encoding length\. The reduced curvature is multi\-affine, so a maximizer exists at a vertex\. The choice ofΛ\\Lambdaforces complementary graph controls and recovers the MAX\-CUT objective\. Coefficient bounds isolate the designated pair from every other exchange\. For the binary restriction, that pair and a binary control vector form a polynomial certificate\. The construction also preserves local exchange feasibility under the row budgetk=n\+1k=n\+1\.

Appendix[C](https://arxiv.org/html/2610.00325#A3)gives the rational transition endpoints, positivity checks, path expansion, pair\-separation bounds, budget bridge, and encoding analysis\. The reduction concerns exact exchange curvature rather than return maximization\. Thus exact thresholding does not provide a polynomial\-time alternative to the Bellman\-envelope bound in general, unlessP=NP\\mathrm\{P\}=\\mathrm\{NP\}\.

## 6Evaluation

The evaluation addresses four questions: when deployment can be certified before rounding, how much return the rounded policy retains, how tight the bounds remain at long horizons, and what certification costs\. Exact rational arithmetic is used for binary optima and theorem checks\. The scaling study uses outward\-rounded validated floating point\. Appendix[D](https://arxiv.org/html/2610.00325#A4)contains the generators, fixed seeds, protocols, and complete tables\. Structured\-suite comparisons retain the legacyℬBell\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}baseline\. Budget\-awareBunifB\_\{\\mathrm\{unif\}\}results are reported for the closed\-form and coupled suites\.

#### Soundness calibration\.

On the original exact\-rational grid of 144 cases acrossgridworld,queue,maintenance, andgarnet, every witnessed continuous\-to\-binary advantage is bounded byℬBell\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}\. The smallest nonzero certificate is2\.95×10−62\.95\\times 10^\{\-6\}, while naive midpoint FP64 reports a false zero in 97/144 cases\. This grid tests soundness rather than active rounding because 141 of the 144 quantized candidates are already binary\.

#### Active rounding\.

The closed\-form family of Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)usesm∈\{4,8,16,32,64\}m\\in\\\{4,8,16,32,64\\\}andγ∈\{0\.2,0\.5,0\.8,0\.95\}\\gamma\\in\\\{0\.2,0\.5,0\.8,0\.95\\\}\. Algorithm[1](https://arxiv.org/html/2610.00325#alg1)performs exactlym/2m/2exchanges in all 20 cases, reaches a binary optimum, and incurs realized loss exactly equal toGap⁡\(𝒞k\)\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)\. Moreover,Bcand​\(x⋆\)=ℬBell/2B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\)=\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}/2, whileBunif=m\+2m\+1​Bcand​\(x⋆\)B\_\{\\mathrm\{unif\}\}=\\frac\{m\+2\}\{m\+1\}B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\)\. The exact weighted bound equals the gap, as shown in Section[4](https://arxiv.org/html/2610.00325#S4)\.

The separately frozen structured suite contains 144 cases, of which 139 have genuinely fractional candidates\. Every active candidate has positive witnessed advantage over the exact binary optimum\. The median candidate has four fractional coordinates and requires three exchanges\. All certified rounding checks pass, and Algorithm[1](https://arxiv.org/html/2610.00325#alg1)reaches the exact binary optimum in 119 of 144 cases\. Across the 139 active cases, its mean normalized optimality gap is0\.185%0\.185\\%, compared with0\.178%0\.178\\%for greedy\. The corresponding median return\-evaluation counts are 6 and 26\. Appendix D reports the complete baseline comparison\.

#### Pre\-rounding certification\.

For a pre\-rounding boundBB, define the certified marginMB​\(x\):=J⁡\(x\)−B−J⁡\(0\)M\_\{B\}\(x\):=J\(x\)\-B\-J\(0\)\. A positive margin guarantees that Algorithm[1](https://arxiv.org/html/2610.00325#alg1)returns a deployable policy withJ⁡\(y\)\>J⁡\(0\)J\(y\)\>J\(0\)\. Table[1](https://arxiv.org/html/2610.00325#S6.T1)reports coverage on the 139 active structured cases\. The legacy model\-only certificate covers67/139=48\.2%67/139=48\.2\\%of them\. Candidate geometry raises coverage to103/139=74\.1%103/139=74\.1\\%without another Bellman solve\. Atγ=4/5\\gamma=4/5, the corresponding counts are 0/71 and 35/71\. All 139 final policies improve over the baseline, so an uncovered case is an abstention rather than a failed deployment\. Appendix[D](https://arxiv.org/html/2610.00325#A4)gives the full tightness hierarchy\. The median bound\-to\-loss ratio falls from 70\.8 forℬBell\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}to 12\.1 forBcandB\_\{\\mathrm\{cand\}\}\.

Table 1:Certified deployment improvement on the 139 active structured cases\. The legacyBBellB\_\{\\rm Bell\}andBcandB\_\{\\rm cand\}are pre\-rounding certificates, whereasBtraceB\_\{\\rm trace\}is a post\-trace audit\. Direct reports the exact checkJ⁡\(y\)\>J⁡\(0\)J\(y\)\>J\(0\), with counts deduced from the stored returns\.
#### Direct rounding followed by verification\.

For a fixed candidate and rounded output, every sound bound satisfiesJ⁡\(x\)−B−J⁡\(0\)≤J⁡\(y\)−J⁡\(0\)J\(x\)\-B\-J\(0\)\\leq J\(y\)\-J\(0\)\. An exact direct check therefore accepts every deployment accepted by the bound\. Across the 20 closed\-form cases, the legacy, budget\-aware, and candidate bounds accept 5, 10, and 10 cases\. Direct verification accepts all 20\. The return of the final chosen endpoint is already cached, so verification adds no evaluation to the 496 used for rounding\. Stored exact returns similarly imply 139/139 direct acceptances on the structured suite\. Pre\-rounding certification covers 103/139 cases, while the post\-trace bound covers 122/139\. The distinction is temporal: a loss guarantee is available before deployment, whereas direct verification requires the final policy\.

#### General exchange bounds and complete costs\.

The 24\-instance coupled suite combines two transition structures,d∈\{6,8\}d\\in\\\{6,8\\\}, three discounts, and two seeds\. Every candidate has positive advantage over the enumerated binary optimum\. Atγ=0\.95\\gamma=0\.95, the median bound\-to\-loss ratio falls from 402\.3 forBcandB\_\{\\mathrm\{cand\}\}to 2\.08 forBlocB\_\{\\mathrm\{loc\}\}\. The trajectory bound certifies improvement in all 24 cases\. It preserves the rounded policy while tightening the loss guarantee\.

Including continuous search and exact setup, median total times are 7\.60 ms for direct rounding, 9\.43 ms for rank\-two rounding, and 36\.19 ms for local integration\. Each instance is timed three times\. The tighter guarantee therefore incurs additional computation on this small synthetic suite\. Appendix[D\.14](https://arxiv.org/html/2610.00325#A4.SS14)reports the complete comparison, exact audits, and separate scaling checks\.

#### Scaling and validated arithmetic\.

We next test certification beyond the exact\-enumeration regime\. The sparse family uses eitherS=d∈\{16,32,64,128\}S=d\\in\\\{16,32,64,128\\\}, ord=16d=16withS∈\{64,128,256\}S\\in\\\{64,128,256\\\}\. Full validated certification takes 4\.45 s atS=d=128S=d=128and 1\.31 s at\(S,d\)=\(256,16\)\(S,d\)=\(256,16\)\. In the latter case, Bellman solves account for 1\.28 s and interval propagation for 0\.031 s, consistent with the\(2​d\+2\)​TBell​\(S\)\+O⁡\(d2​S\)\(2d\+2\)T\_\{\\mathrm\{Bell\}\}\(S\)\+O\(d^\{2\}S\)decomposition\.

Validated intervals contain the exact recomputation in all six audited reference cases, whereas naive FP64 passes the Bellman audit in none\. This audit covers only the small reference cases\. AtS=d=16S=d=16, the validated implementation is about14\.8×14\.8\\timesfaster than the existing exact\-rational pipeline\.

## 7Conclusion

Sparse deployment changes the policy\-optimization problem because each row edit also changes future visitation\. We showed that Bellman envelopes can control this coupling uniformly, while budget and candidate geometry sharpen the guarantee available before rounding\. For the realized exchange path, a rank\-two representation supports weighted curvature integration and avoids paying for remote worst\-case policies\.

On the structured suite, candidate geometry raises pre\-rounding certification coverage from48\.2%48\.2\\%to74\.1%74\.1\\%\. On coupled instances atγ=0\.95\\gamma=0\.95, trajectory integration lowers the median bound\-to\-loss ratio from402\.3402\.3to2\.082\.08\. These findings distinguish two uses of a certificate: reusable guarantees before deployment and tighter audits once the rounding path is known\.

#### Scope and extensions\.

The analysis assumes a known finite discounted MDP with two actions per editable row\. Larger action sets, estimated models, partial observability, and average reward require new arguments\. Open questions include the best universal dimension constant, NP membership of continuous curvature thresholding, and validated floating\-point implementations of the trajectory bounds\.

## References

- \[1\]A\. Abate, T\. Badings, G\. D\. Giacomo, and F\. Fabiano\(2026\)Best\-effort policies for robust markov decision processes\.Proceedings of the AAAI Conference on Artificial Intelligence40\(43\),pp\. 36120–36128\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v40i43.40929)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[2\]A\. A\. Ageev and M\. Sviridenko\(2004\)Pipage rounding: a new method of constructing algorithms with proven performance guarantee\.Journal of Combinatorial Optimization8\(3\),pp\. 307–328\.External Links:[Document](https://dx.doi.org/10.1023/B%3AJOCO.0000038913.96607.C2)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p1.1)\.
- \[3\]T\. W\. Archibald, K\. I\. M\. McKinnon, and L\. C\. Thomas\(1995\)On the generation of Markov decision processes\.Journal of the Operational Research Society46\(3\),pp\. 354–361\.Cited by:[4th item](https://arxiv.org/html/2610.00325#A4.I4.i4.p1.1)\.
- \[4\]A\. Asadi, K\. Chatterjee, E\. Goharshady, M\. Karrabi, A\. Montaseri, and C\. Pagano\(2026\)Strongly polynomial time complexity of policy iteration forL∞L\_\{\\infty\}robust MDPs\.InProceedings of Thirty Ninth Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.336,pp\. 427–457\.External Links:[Link](https://proceedings.mlr.press/v336/asadi26a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[5\]M\. Azeem, D\. Chakraborty, S\. Kanav, J\. Křetínský, M\. Mohagheghi, S\. Mohr, and M\. Weininger\(2025\)1–2–3–go\! policy synthesis for parameterized markov decision processes via decision\-tree learning and generalization\.InVerification, Model Checking, and Abstract Interpretation,Lecture Notes in Computer Science, Vol\.15530,pp\. 97–120\.External Links:[Document](https://dx.doi.org/10.1007/978-3-031-82703-7%5F5)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[6\]F\. Bianchi, A\. Castellini, E\. Zorzi, T\. D\. Simão, M\. T\. J\. Spaan, and A\. Farinelli\(2025\)Scaling safe policy improvement: Monte Carlo tree search and policy iteration strategies\.Journal of Artificial Intelligence Research84\.External Links:[Document](https://dx.doi.org/10.1613/jair.1.19649)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[7\]F\. Bianchi, E\. Zorzi, A\. Castellini, T\. D\. Simão, M\. T\. J\. Spaan, and A\. Farinelli\(2024\)Scalable safe policy improvement for factored multi\-agent MDPs\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 3952–3973\.External Links:[Link](https://proceedings.mlr.press/v235/bianchi24b.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[8\]N\. Buchbinder and M\. Feldman\(2025\)Extending the extension: deterministic algorithm for non\-monotone submodular maximization\.InProceedings of the 57th Annual ACM Symposium on Theory of Computing,External Links:[Document](https://dx.doi.org/10.1145/3717823.3718120)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p1.1)\.
- \[9\]X\. Cao\(1998\)The maclaurin series for performance functions of markov chains\.Advances in Applied Probability30\(3\),pp\. 676–692\.External Links:[Document](https://dx.doi.org/10.1239/aap/1035228123)Cited by:[§2\.2](https://arxiv.org/html/2610.00325#S2.SS2.p1.3)\.
- \[10\]A\. Castellini, F\. Bianchi, E\. Zorzi, T\. D\. Simão, A\. Farinelli, and M\. T\. J\. Spaan\(2023\)Scalable safe policy improvement via Monte Carlo tree search\.InProceedings of the 40th International Conference on Machine Learning,A\. Krause, E\. Brunskill, K\. Cho, B\. Engelhardt, S\. Sabato, and J\. Scarlett \(Eds\.\),Proceedings of Machine Learning Research, Vol\.202,pp\. 3732–3756\.External Links:[Link](https://proceedings.mlr.press/v202/castellini23a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[11\]Z\. Chen and H\. Huang\(2024\)Accelerated policy gradient for s\-rectangular robust MDPs with large state spaces\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 6847–6880\.External Links:[Link](https://proceedings.mlr.press/v235/chen24s.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[12\]F\. Delgrange, R\. Avalos, and W\. Röpke\(2026\)Deep SPI: safe policy improvement via world models\.InInternational Conference on Learning Representations,External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2026/hash/0212b0dff7b4aa3bd8b8cc4ce24fd384-Abstract-Conference.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[13\]T\. Furmston, G\. Lever, and D\. Barber\(2016\)Approximate newton methods for policy search in markov decision processes\.Journal of Machine Learning Research17\(226\),pp\. 1–51\.External Links:[Link](https://www.jmlr.org/papers/v17/15-414.html)Cited by:[§2\.2](https://arxiv.org/html/2610.00325#S2.SS2.p1.3)\.
- \[14\]M\. Ghadiri, R\. Santiago, and B\. Shepherd\(2025\)Beyond submodular maximization via one\-sided smoothness\.Mathematical Programming\.External Links:[Document](https://dx.doi.org/10.1007/s10107-025-02301-5)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p1.1)\.
- \[15\]E\. Hamel\-De le Court, F\. Belardinelli, and A\. W\. Goodall\(2025\)Probabilistic shielding for safe reinforcement learning\.Proceedings of the AAAI Conference on Artificial Intelligence39\(15\),pp\. 16091–16099\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v39i15.33767)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[16\]A\. Hartmanns, S\. Junges, T\. Quatmann, and M\. Weininger\(2026\)The revised practitioner’s guide to MDP model checking algorithms\.International Journal on Software Tools for Technology Transfer\.External Links:[Document](https://dx.doi.org/10.1007/s10009-026-00848-y)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[17\]L\. Heck, F\. Macák, M\. Češka, and S\. Junges\(2026\)Constrained and robust policy synthesis with satisfiability\-modulo\-probabilistic\-model\-checking\.Proceedings of the AAAI Conference on Artificial Intelligence40\(43\),pp\. 36253–36261\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v40i43.40944)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[18\]L\. Heck, T\. Quatmann, J\. Spel, J\. Katoen, and S\. Junges\(2025\)Generalized parameter lifting: finer abstractions for parametric markov chains\.InAutomated Technology for Verification and Analysis,Lecture Notes in Computer Science, Vol\.16145,pp\. 207–230\.External Links:[Document](https://dx.doi.org/10.1007/978-3-032-08707-2%5F10)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[19\]S\. Junges, E\. Ábrahám, C\. Hensel, N\. Jansen, J\. Katoen, T\. Quatmann, and M\. Volk\(2024\)Parameter synthesis for markov models: covering the parameter space\.Formal Methods in System Design62,pp\. 181–259\.External Links:[Document](https://dx.doi.org/10.1007/s10703-023-00442-x)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[20\]M\. Khorasani, S\. Salehkaleybar, N\. Kiyavash, N\. He, and M\. Grossglauser\(2025\)Efficiently escaping saddle points for policy optimization\.InProceedings of the Forty\-first Conference on Uncertainty in Artificial Intelligence,Proceedings of Machine Learning Research, Vol\.286,pp\. 2143–2162\.External Links:[Link](https://proceedings.mlr.press/v286/khorasani25a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[21\]N\. Kumar, E\. Derman, M\. Geist, K\. Y\. Levy, and S\. Mannor\(2023\)Policy gradient for rectangular robust markov decision processes\.InAdvances in Neural Information Processing Systems,Vol\.36\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2023/hash/ba8aee784ffe0813890288b334444eda-Abstract-Conference.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[22\]M\. Li, D\. Kuhn, and T\. Sutter\(2026\)Policy gradient algorithms for robust MDPs with nonrectangular uncertainty sets\.SIAM Journal on Optimization36\(1\),pp\. 120–151\.External Links:[Document](https://dx.doi.org/10.1137/24M1631250)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[23\]Z\. Lin, C\. Xue, Q\. Deng, and Y\. Ye\(2024\)A single\-loop robust policy gradient method for robust markov decision processes\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 30392–30426\.External Links:[Link](https://proceedings.mlr.press/v235/lin24u.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[24\]M\. P\. Maniyar, P\. L\.A\., A\. Mondal, and S\. Bhatnagar\(2024\)A cubic\-regularized policy Newton algorithm for reinforcement learning\.InProceedings of The 27th International Conference on Artificial Intelligence and Statistics,S\. Dasgupta, S\. Mandt, and Y\. Li \(Eds\.\),Proceedings of Machine Learning Research, Vol\.238,pp\. 4708–4716\.External Links:[Link](https://proceedings.mlr.press/v238/maniyar24a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[25\]T\. Meggendorfer, M\. Weininger, and P\. Wienhöft\(2025\)Solving robust markov decision processes: generic, reliable, efficient\.Proceedings of the AAAI Conference on Artificial Intelligence39\(25\),pp\. 26631–26641\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v39i25.34865)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[26\]A\. Montenegro, M\. Mussi, A\. M\. Metelli, and M\. Papini\(2024\)Learning optimal deterministic policies with stochastic policy gradients\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 36160–36211\.External Links:[Link](https://proceedings.mlr.press/v235/montenegro24a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[27\]R\. E\. Moore, R\. B\. Kearfott, and M\. J\. Cloud\(2009\)Introduction to interval analysis\.SIAM\.Cited by:[Assumption 2\.2](https://arxiv.org/html/2610.00325#S2.Thmtheorem2.p1.1)\.
- \[28\]S\. Mu and D\. Klabjan\(2024\)On the second\-order convergence of biased policy gradient algorithms\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 36455–36485\.External Links:[Link](https://proceedings.mlr.press/v235/mu24b.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[29\]M\. L\. Puterman\(1994\)Markov decision processes: discrete stochastic dynamic programming\.Wiley\.Cited by:[§2\.1](https://arxiv.org/html/2610.00325#S2.SS1.p2.2)\.
- \[30\]L\. Rickard, A\. Abate, and K\. Margellos\(2024\)Learning robust policies for uncertain parametric Markov decision processes\.InProceedings of the 6th Annual Learning for Dynamics & Control Conference,Proceedings of Machine Learning Research, Vol\.242,pp\. 876–889\.External Links:[Link](https://proceedings.mlr.press/v242/rickard24a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[31\]Y\. Schnitzer, A\. Abate, and D\. Parker\(2026\)Robust parameter learning for uncertain MDPs\.InProceedings of the 3rd International Joint Conference on Quantitative Evaluation of Systems and Formal Modelling and Analysis of Timed Systems,Note:arXiv:2605\.01339External Links:[Link](https://arxiv.org/abs/2605.01339)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[32\]A\. Sharma, L\. Benac, S\. Parbhoo, and F\. Doshi\-Velez\(2025\)Decision\-point guided safe policy improvement\.InProceedings of The 28th International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.258,pp\. 2935–2943\.External Links:[Link](https://proceedings.mlr.press/v258/sharma25a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[33\]T\. D\. Simão, M\. Suilen, and N\. Jansen\(2023\)Safe policy improvement for POMDPs via finite\-state controllers\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.37,pp\. 15109–15117\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v37i12.26763)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[34\]M\. Suilen, T\. Badings, E\. M\. Bovy, D\. Parker, and N\. Jansen\(2024\)Robust markov decision processes: a place where AI and formal methods meet\.InPrinciples of Verification: Cycling the Probabilistic Landscape,Lecture Notes in Computer Science, Vol\.15262,pp\. 126–154\.External Links:[Document](https://dx.doi.org/10.1007/978-3-031-75778-5%5F7)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[35\]Z\. Sun, S\. He, F\. Miao, and S\. Zou\(2024\)Policy optimization for robust average reward MDPs\.InAdvances in Neural Information Processing Systems,Vol\.37\.External Links:[Document](https://dx.doi.org/10.52202/079017-0551),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/hash/1f28e9341ab99d8e5a5734f0a76601c7-Abstract-Conference.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[36\]Q\. Wang, Y\. Zha, C\. P\. Ho, and M\. Petrik\(2025\)Provable policy gradient for robust average\-reward MDPs beyond rectangularity\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 65368–65399\.External Links:[Link](https://proceedings.mlr.press/v267/wang25ei.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[37\]P\. Wienhöft, M\. Suilen, T\. D\. Simão, C\. Dubslaff, C\. Baier, and N\. Jansen\(2023\)More for less: safe policy improvement with stronger performance guarantees\.InProceedings of the Thirty\-Second International Joint Conference on Artificial Intelligence, IJCAI 2023,pp\. 4406–4415\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2023/490)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[38\]G\. Yuan and B\. Ghanem\(2016\)Binary optimization via mathematical programming with equilibrium constraints\.arXiv preprint arXiv:1608\.04425\.Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[39\]G\. Yuan, L\. Shen, and W\. Zheng\(2020\)A block decomposition algorithm for sparse optimization\.InProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,pp\. 275–285\.External Links:[Document](https://dx.doi.org/10.1145/3394486.3403070)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[40\]G\. Yuan\(2024\)Smoothing proximal gradient methods for nonsmooth sparsity constrained optimization: optimality conditions and global convergence\.InProceedings of the 41st International Conference on Machine Learning,R\. Salakhutdinov, Z\. Kolter, K\. Heller, A\. Weller, N\. Oliver, J\. Scarlett, and F\. Berkenkamp \(Eds\.\),Proceedings of Machine Learning Research, Vol\.235,pp\. 57842–57870\.External Links:[Link](https://proceedings.mlr.press/v235/yuan24a.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p2.1)\.
- \[41\]R\. Zhang, Y\. Hu, and N\. Li\(2024\)Soft robust MDPs and risk\-sensitive MDPs: equivalence, policy gradient, and sample complexity\.InInternational Conference on Learning Representations,External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/3f7f788b479a26348605a9f97c465d22-Abstract-Conference.html)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.
- \[42\]Y\. Zhang, H\. Tang, C\. Wei, C\. Wang, and W\. Ding\(2026\)Policy Newton algorithm in reproducing kernel Hilbert space\.InInternational Conference on Learning Representations,External Links:[Link](https://iclr.cc/virtual/2026/poster/10009658)Cited by:[§1\.2](https://arxiv.org/html/2610.00325#S1.SS2.p3.1)\.

## Appendix AProofs for Section[3](https://arxiv.org/html/2610.00325#S3)

Algorithm 1Constructive rounding used in Theorem[3\.3](https://arxiv.org/html/2610.00325#S3.Thmtheorem3)1:

x∈𝒞kx\\in\\mathcal\{C\}\_\{k\}, with exact or certified endpoint comparisons of

JJ
2:

y∈𝒞kbiny\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}with

J⁡\(y\)≥J⁡\(x\)−BunifJ\(y\)\\geq J\(x\)\-B\_\{\\mathrm\{unif\}\}
3:

z←xz\\leftarrow x
4:if

𝟏⊤​z∉ℤ\\mathbf\{1\}^\{\\top\}z\\notin\\mathbb\{Z\}then

5:raise coordinates of

zzin the fixed order

1,2,…,d1,2,\\ldots,duntil

𝟏⊤​z=⌈𝟏⊤​x⌉\\mathbf\{1\}^\{\\top\}z=\\lceil\\mathbf\{1\}^\{\\top\}x\\rceil⊳\\trianglerightdeterministic fill and costs at mostτ\\tau

6:endif

7:while

zzhas a fractional coordinatedo

8:pick two fractional coordinates

i≠ji\\neq j⊳\\trianglerightan integral sum forbids exactly one

9:

\[a,b\]←\[a,b\]\\leftarrowmaximal interval with

z\+t⁡\(εi−εj\)∈\[0,1\]dz\+t\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)\\in\[0,1\]^\{d\}
10:

z←z\+t⋆​\(εi−εj\)z\\leftarrow z\+t^\{\\star\}\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\), where

t⋆∈arg⁡maxt∈\{a,b\}⁡J⁡\{z\+t⁡\(εi−εj\)\}t^\{\\star\}\\in\\arg\\max\_\{t\\in\\\{a,b\\\}\}J\\\{z\+t\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)\\\}⊳\\trianglerightcosts at mostβ⁡\(−a\)​b/2\\beta\(\-a\)b/2

11:endwhile

12:return

y←zy\\leftarrow z

###### Proof of Theorem[3\.3](https://arxiv.org/html/2610.00325#S3.Thmtheorem3)\.

Ifk=0k=0, thenx=y=0x=y=0and the claim is immediate\. Assumek\>0k\>0\.

#### Phase 1\.

Writes=𝟏⊤​xs=\\mathbf\{1\}^\{\\top\}x,ℓ=⌈s⌉≤k\\ell=\\lceil s\\rceil\\leq k, andη=ℓ−s∈\[0,1\)\\eta=\\ell\-s\\in\[0,1\)\. The cube has sufficient unused capacity to raise coordinates by total massη\\eta\. Since∂iJ≥−τ\\partial\_\{i\}J\\geq\-\\taueverywhere, integrating along the monotone fill path givesJ⁡\(z\)≥J⁡\(x\)−η​τ≥J⁡\(x\)−τJ\(z\)\\geq J\(x\)\-\\eta\\tau\\geq J\(x\)\-\\tau\. The resultingzzis feasible and has integer sumℓ\\ell\.

#### One exchange\.

An integer\-sum nonbinary point has at least two fractional coordinates\. For suchi,ji,j, setv=εi−εjv=\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}andg⁡\(t\)=J⁡\(z\+t​v\)g\(t\)=J\(z\+tv\)\. The maximal feasible interval has endpointsa=max⁡\{−zi,zj−1\}<0a=\\max\\\{\-z\_\{i\},z\_\{j\}\-1\\\}<0andb=min⁡\{1−zi,zj\}\>0b=\\min\\\{1\-z\_\{i\},z\_\{j\}\\\}\>0, withb−a≤1b\-a\\leq 1\. Ifg′′≥−βg^\{\\prime\\prime\}\\geq\-\\beta, the functionh⁡\(t\)=g⁡\(t\)\+β​t2/2h\(t\)=g\(t\)\+\\beta t^\{2\}/2is convex\. Apply convexity with endpoint weightsb/\(b−a\)b/\(b\-a\)and\(−a\)/\(b−a\)\(\-a\)/\(b\-a\)to obtaing⁡\(0\)≤max⁡\{g⁡\(a\),g⁡\(b\)\}\+β⁡\(−a\)​b/2g\(0\)\\leq\\max\\\{g\(a\),g\(b\)\\\}\+\\beta\(\-a\)b/2\. The chosen endpoint therefore loses at mostβ⁡\(−a\)​b/2≤β/8\\beta\(\-a\)b/2\\leq\\beta/8and makes at least one coordinate integral\.

#### Potential identity and termination\.

DefineΦ⁡\(u\)=∑iui​\(1−ui\)\\Phi\(u\)=\\sum\_\{i\}u\_\{i\}\(1\-u\_\{i\}\)\. Ifzi\+zj≤1z\_\{i\}\+z\_\{j\}\\leq 1, the endpoints are\(0,zi\+zj\)\(0,z\_\{i\}\+z\_\{j\}\)and\(zi\+zj,0\)\(z\_\{i\}\+z\_\{j\},0\); either choice decreasesΦ\\Phiby2​zi​zj=2​\(−a\)​b2z\_\{i\}z\_\{j\}=2\(\-a\)b\. Ifzi\+zj≥1z\_\{i\}\+z\_\{j\}\\geq 1, the endpoints are\(1,zi\+zj−1\)\(1,z\_\{i\}\+z\_\{j\}\-1\)and\(zi\+zj−1,1\)\(z\_\{i\}\+z\_\{j\}\-1,1\); the decrease is2​\(1−zi\)​\(1−zj\)=2​\(−a\)​b2\(1\-z\_\{i\}\)\(1\-z\_\{j\}\)=2\(\-a\)b\. Integral coordinates are never selected again\. Thus the algorithm terminates after at mostd−1d\-1exchanges aty∈𝒞kbiny\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}, and telescoping gives∑t\(−at\)​bt=Φ⁡\(z\)/2\\sum\_\{t\}\(\-a\_\{t\}\)b\_\{t\}=\\Phi\(z\)/2\. The accumulated Phase\-2 loss is at mostβ​Φ​\(z\)/4\\beta\\Phi\(z\)/4\.

#### Budget\-aware bound\.

Cauchy–Schwarz gives∑izi2≥ℓ2/d\\sum\_\{i\}z\_\{i\}^\{2\}\\geq\\ell^\{2\}/d, henceΦ⁡\(z\)≤ℓ⁡\(d−ℓ\)/d\\Phi\(z\)\\leq\\ell\(d\-\\ell\)/d\. The maximum ofℓ⁡\(d−ℓ\)\\ell\(d\-\\ell\)over integers0≤ℓ≤k0\\leq\\ell\\leq kisqd,k​\(d−qd,k\)q\_\{d,k\}\(d\-q\_\{d,k\}\), attained atℓ=qd,k\\ell=q\_\{d,k\}\. ThereforeJ⁡\(y\)≥J⁡\(x\)−τ−cd,k​β≥J⁡\(x\)−BunifJ\(y\)\\geq J\(x\)\-\\tau\-c\_\{d,k\}\\beta\\geq J\(x\)\-B\_\{\\mathrm\{unif\}\}\. Ford=1d=1,zzis already binary andcd,k=β=0c\_\{d,k\}=\\beta=0\. Applying the guarantee to a continuous maximizer and usingJ⁡\(y\)≤max𝒞kbin⁡JJ\(y\)\\leq\\max\_\{\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}\}Jproves the gap bound\. The older charge ofβ/8\\beta/8for each of at mostd−1d\-1exchanges also proves the legacy boundℬBell\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}used in the original evaluation\. ∎

###### Proof of Proposition[3\.4](https://arxiv.org/html/2610.00325#S3.Thmtheorem4)\.

The result is immediate fork=0k=0\. Otherwise retain the deterministic Phase\-1 pointzz, incrementsΔi=zi−xi\\Delta\_\{i\}=z\_\{i\}\-x\_\{i\}, and fractional supportF⁡\(z\)F\(z\)\. Proposition[3\.2](https://arxiv.org/html/2610.00325#S3.Thmtheorem2)gives∂iJ≥−τ^i\\partial\_\{i\}J\\geq\-\\widehat\{\\tau\}\_\{i\}on the fill path, soJ⁡\(z\)≥J⁡\(x\)−∑iΔi​τ^iJ\(z\)\\geq J\(x\)\-\\sum\_\{i\}\\Delta\_\{i\}\\widehat\{\\tau\}\_\{i\}\. For an executed pair\(it,jt\)\(i\_\{t\},j\_\{t\}\), it also givesgt′′≥S¯it​jt≥−β^it​jtg\_\{t\}^\{\\prime\\prime\}\\geq\\underline\{S\}\_\{i\_\{t\}j\_\{t\}\}\\geq\-\\widehat\{\\beta\}\_\{i\_\{t\}j\_\{t\}\}, whereβ^i​j:=\[−S¯i​j\]\+\\widehat\{\\beta\}\_\{ij\}:=\[\-\\underline\{S\}\_\{ij\}\]\_\{\+\}\. The one\-step argument above thus charges at mostβ^it​jt​\(−at\)​bt/2\\widehat\{\\beta\}\_\{i\_\{t\}j\_\{t\}\}\(\-a\_\{t\}\)b\_\{t\}/2\. The support only shrinks, so every executed pair satisfiesβ^it​jt≤β^F⁡\(z\)\\widehat\{\\beta\}\_\{i\_\{t\}j\_\{t\}\}\\leq\\widehat\{\\beta\}\_\{F\(z\)\}\. Using the already proved potential identity yieldsJ⁡\(y\)≥J⁡\(x\)−∑iΔi​τ^i−β^F⁡\(z\)​Φ​\(z\)/4=J⁡\(x\)−Bcand​\(x\)J\(y\)\\geq J\(x\)\-\\sum\_\{i\}\\Delta\_\{i\}\\widehat\{\\tau\}\_\{i\}\-\\widehat\{\\beta\}\_\{F\(z\)\}\\Phi\(z\)/4=J\(x\)\-B\_\{\\mathrm\{cand\}\}\(x\)\. Finally,∑iΔi<1\\sum\_\{i\}\\Delta\_\{i\}<1,τ^i≤τ^\\widehat\{\\tau\}\_\{i\}\\leq\\widehat\{\\tau\},β^F⁡\(z\)≤β^\\widehat\{\\beta\}\_\{F\(z\)\}\\leq\\widehat\{\\beta\}, andΦ⁡\(z\)≤4​cd,k\\Phi\(z\)\\leq 4c\_\{d,k\}implyBcand​\(x\)≤BunifB\_\{\\mathrm\{cand\}\}\(x\)\\leq B\_\{\\mathrm\{unif\}\}\. Ford≥2d\\geq 2,cd,k≤d/16≤\(d−1\)/8c\_\{d,k\}\\leq d/16\\leq\(d\-1\)/8provesBunif≤ℬBellB\_\{\\mathrm\{unif\}\}\\leq\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}; ford=1d=1the curvature term vanishes\. ∎

## Appendix BProof of Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)

We prove Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)\.

### B\.1MDP construction

Use one target state with reward one andmmbad states with reward zero\. The target self\-loops under both actions\. From bad stateii, the baseline action self\-loops and the repair action jumps to the target\. The initial distribution is uniform over the bad states\. Add a dummy editable coordinate at the target whose two actions coincide, givingd=m\+1d=m\+1\.

### B\.2Return in closed form

Direct Bellman solution separates the return across rows\. Fix bad stateii\. Under the mixed policyxi∈\[0,1\]x\_\{i\}\\in\[0,1\], the transition from stateiisends massxix\_\{i\}to the target and mass1−xi1\-x\_\{i\}back to itself\. The discounted occupancy of the target, starting from stateii, satisfies the Bellman equation

Vi=γ⁡\[\(1−xi\)​Vi\+xi​Vtarget\],V\_\{i\}=\\gamma\\bigl\[\(1\-x\_\{i\}\)\\,V\_\{i\}\+x\_\{i\}\\,V\_\{\\mathrm\{target\}\}\\bigr\],whereVtarget=1/\(1−γ\)V\_\{\\mathrm\{target\}\}=1/\(1\-\\gamma\)\(the target has reward one and self\-loops\)\. Solving forViV\_\{i\}gives

Vi\\displaystyle V\_\{i\}=γ⁡\(1−xi\)​Vi\+γ​xi1−γ\\displaystyle=\\gamma\(1\-x\_\{i\}\)V\_\{i\}\+\\frac\{\\gamma x\_\{i\}\}\{1\-\\gamma\}Vi​\[1−γ⁡\(1−xi\)\]\\displaystyle V\_\{i\}\\bigl\[1\-\\gamma\(1\-x\_\{i\}\)\\bigr\]=γ​xi1−γ\\displaystyle=\\frac\{\\gamma x\_\{i\}\}\{1\-\\gamma\}Vi\\displaystyle V\_\{i\}=γ​xi\(1−γ\)​\(1−γ\+γ​xi\),\\displaystyle=\\frac\{\\gamma x\_\{i\}\}\{\(1\-\\gamma\)\(1\-\\gamma\+\\gamma x\_\{i\}\)\},\(20\)
Define

fγ​\(t\)=γ​t\(1−γ\)​\(1−γ\+γ​t\)\.f\_\{\\gamma\}\(t\)=\\frac\{\\gamma t\}\{\(1\-\\gamma\)\(1\-\\gamma\+\\gamma t\)\}\.\(21\)Since the initial distribution is uniform over themmbad states,

J⁡\(x\)=1m​∑i=1mfγ​\(xi\)\.J\(x\)=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}f\_\{\\gamma\}\(x\_\{i\}\)\.\(22\)Each summand is increasing and concave\. We verify concavity by computing the second derivative:

fγ′​\(t\)\\displaystyle f\_\{\\gamma\}^\{\\prime\}\(t\)=γ\(1−γ\)⋅\(1−γ\+γ​t\)−γ​t\(1−γ\+γ​t\)2=γ\(1−γ\+γ​t\)2,\\displaystyle=\\frac\{\\gamma\}\{\(1\-\\gamma\)\}\\cdot\\frac\{\(1\-\\gamma\+\\gamma t\)\-\\gamma t\}\{\(1\-\\gamma\+\\gamma t\)^\{2\}\}=\\frac\{\\gamma\}\{\(1\-\\gamma\+\\gamma t\)^\{2\}\},fγ′′​\(t\)\\displaystyle f\_\{\\gamma\}^\{\\prime\\prime\}\(t\)=−2​γ2\(1−γ\+γ​t\)3<0,\\displaystyle=\\frac\{\-2\\gamma^\{2\}\}\{\(1\-\\gamma\+\\gamma t\)^\{3\}\}<0,\(23\)

### B\.3Continuous and binary optima

Under budgetk=m/2k=m/2, the constraint is∑i=1m\+1xi≤m/2\\sum\_\{i=1\}^\{m\+1\}x\_\{i\}\\leq m/2\. The dummy coordinate does not affectJJ, so the optimum sets it to zero and distributes the full budget over bad rows\. Eachfγf\_\{\\gamma\}is strictly concave\. By Jensen’s inequality applied to the symmetric concave problem, the continuous optimum places equal mass:

xi⋆=km=12for every bad row​i,xm\+1⋆=0\.x\_\{i\}^\{\\star\}=\\frac\{k\}\{m\}=\\frac\{1\}\{2\}\\quad\\text\{for every bad row \}i,\\qquad x\_\{m\+1\}^\{\\star\}=0\.A binary optimum selects anym/2m/2bad rows \(setting them to 1, the rest to 0\), with the dummy row at zero\. By symmetry, all such selections achieve the same return\. Hence

Gap⁡\(𝒞k\)\\displaystyle\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=fγ​\(1/2\)−12​fγ​\(1\)−12​fγ​\(0\)\\displaystyle=f\_\{\\gamma\}\(1/2\)\-\\tfrac\{1\}\{2\}f\_\{\\gamma\}\(1\)\-\\tfrac\{1\}\{2\}f\_\{\\gamma\}\(0\)=fγ​\(1/2\)−12​fγ​\(1\)\\displaystyle=f\_\{\\gamma\}\(1/2\)\-\\tfrac\{1\}\{2\}f\_\{\\gamma\}\(1\)=γ\(1−γ\)​\(2−γ\)−γ2​\(1−γ\)\\displaystyle=\\frac\{\\gamma\}\{\(1\-\\gamma\)\(2\-\\gamma\)\}\-\\frac\{\\gamma\}\{2\(1\-\\gamma\)\}=2​γ−γ⁡\(2−γ\)2​\(1−γ\)​\(2−γ\)\\displaystyle=\\frac\{2\\gamma\-\\gamma\(2\-\\gamma\)\}\{2\(1\-\\gamma\)\(2\-\\gamma\)\}=γ22​\(1−γ\)​\(2−γ\),\\displaystyle=\\frac\{\\gamma^\{2\}\}\{2\(1\-\\gamma\)\(2\-\\gamma\)\},\(24\)The gap is independent ofmm\.

### B\.4Interval certificate computation

PutCγ=\(1−γ\)−1C\_\{\\gamma\}=\(1\-\\gamma\)^\{\-1\}\. For a bad row, the canonical construction of Section[3](https://arxiv.org/html/2610.00325#S3)gives:

Qi\\displaystyle Q\_\{i\}=\[1/m,Cγ/m\],\\displaystyle=\[1/m,\\;C\_\{\\gamma\}/m\],\(25\)Ai\\displaystyle A\_\{i\}=\[γ,γ​Cγ\],\\displaystyle=\[\\gamma,\\;\\gamma C\_\{\\gamma\}\],\(26\)Bi​i\\displaystyle B\_\{ii\}=\[−γ​Cγ,−γ\],\\displaystyle=\[\-\\gamma C\_\{\\gamma\},\\;\-\\gamma\],\(27\)andBi​j=\{0\}B\_\{ij\}=\\\{0\\\}for distinct bad rowsi≠ji\\neq j\. We derive these as follows\.

#### Derivation ofQiQ\_\{i\}\.

By \([11](https://arxiv.org/html/2610.00325#S3.E11)\),Qi=\[μ⊤​h¯i,μ⊤​h¯i\]Q\_\{i\}=\[\\mu^\{\\top\}\\underline\{h\}\_\{i\},\\;\\mu^\{\\top\}\\overline\{h\}\_\{i\}\]\. The auxiliary rewardeie\_\{i\}gives reward one at stateiionly\. Since the initial distribution is uniform over bad states,μ⊤​hi=hi​\(i\)/m\\mu^\{\\top\}h\_\{i\}=h\_\{i\}\(i\)/m\(the contribution from starting at stateii\)\. The minimum over all binary policies redirects stateiito the target, so stateiiis visited only at the initial time step:h¯i​\(i\)=1\\underline\{h\}\_\{i\}\(i\)=1\. The maximum keeps stateiiself\-looping, so it is revisited at every step:h¯i​\(i\)=1\+γ\+γ2\+⋯=Cγ\\overline\{h\}\_\{i\}\(i\)=1\+\\gamma\+\\gamma^\{2\}\+\\cdots=C\_\{\\gamma\}\. ThereforeQi=\[1/m,Cγ/m\]Q\_\{i\}=\[1/m,\\;C\_\{\\gamma\}/m\]\.

#### Derivation ofAiA\_\{i\}\.

Each bad row has zero reward under both actions and the target has reward one\. The transition editdid\_\{i\}redirects mass from self\-loop at stateiito the target\. By \([12](https://arxiv.org/html/2610.00325#S3.E12)\), the advantage interval depends on the value envelope at the target:V¯target=1/\(1−γ\)=Cγ\\underline\{V\}\_\{\\mathrm\{target\}\}=1/\(1\-\\gamma\)=C\_\{\\gamma\}when all bad states self\-loop, andV¯target=Cγ\\overline\{V\}\_\{\\mathrm\{target\}\}=C\_\{\\gamma\}identically, since the target self\-loops regardless of other rows’ actions\. However, stateii’s own value enters throughdi−d\_\{i\}^\{\-\}: the lower endpoint usesV¯i\\overline\{V\}\_\{i\}\(largest value at stateii\) and the upper usesV¯i\\underline\{V\}\_\{i\}\(smallest\)\. SinceV¯i=0\\underline\{V\}\_\{i\}=0\(self\-loop at zero reward\) andV¯i=γ​Cγ\\overline\{V\}\_\{i\}=\\gamma C\_\{\\gamma\}\(redirect to target\), the interval isAi=\[γ⁡\(Cγ−γ​Cγ\),γ​Cγ\]=\[γ,γ​Cγ\]A\_\{i\}=\[\\gamma\(C\_\{\\gamma\}\-\\gamma C\_\{\\gamma\}\),\\;\\gamma C\_\{\\gamma\}\]=\[\\gamma,\\;\\gamma C\_\{\\gamma\}\]\.

#### Derivation ofBi​iB\_\{ii\}\.

Rowii’s transition edit affects its own visitation in the opposite direction: repairing rowiireduces its self\-visits\. Formally,Bi​i=γ⁡\[\(di\+\)⊤​h¯i−\(di−\)⊤​h¯i,\(di\+\)⊤​h¯i−\(di−\)⊤​h¯i\]B\_\{ii\}=\\gamma\[\(d\_\{i\}^\{\+\}\)^\{\\top\}\\underline\{h\}\_\{i\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\overline\{h\}\_\{i\},\\;\(d\_\{i\}^\{\+\}\)^\{\\top\}\\overline\{h\}\_\{i\}\-\(d\_\{i\}^\{\-\}\)^\{\\top\}\\underline\{h\}\_\{i\}\]\. This gives the negative intervalBi​i=\[−γ​Cγ,−γ\]B\_\{ii\}=\[\-\\gamma C\_\{\\gamma\},\\;\-\\gamma\]\.

#### Computingτ^\\widehat\{\\tau\}andβ^\\widehat\{\\beta\}\.

The gradient interval for bad rowiiis

Gi=Qi⊙Ai=\[1m⋅γ,Cγm⋅γ​Cγ\]=\[γm,γ​Cγ2m\]\.G\_\{i\}=Q\_\{i\}\\odot A\_\{i\}=\\bigl\[\\tfrac\{1\}\{m\}\\cdot\\gamma,\\;\\tfrac\{C\_\{\\gamma\}\}\{m\}\\cdot\\gamma C\_\{\\gamma\}\\bigr\]=\\bigl\[\\tfrac\{\\gamma\}\{m\},\\;\\tfrac\{\\gamma C\_\{\\gamma\}^\{2\}\}\{m\}\\bigr\]\.Since every lower endpoint is positive,τ^=maxi\[−infGi\]\+=0\\widehat\{\\tau\}=\\max\_\{i\}\\left\[\-\\inf G\_\{i\}\\right\]\_\{\+\}=0\. This also meansτ=0\\tau=0, sinceτ≤τ^\\tau\\leq\\widehat\{\\tau\}\.

For the Hessian diagonal, the triple product2​Qi⊙Bi​i⊙Ai2\\,Q\_\{i\}\\odot B\_\{ii\}\\odot A\_\{i\}has one negative factor \(Bi​iB\_\{ii\}\) and two positive factors \(Qi,AiQ\_\{i\},A\_\{i\}\)\. The most negative value is attained at the largest magnitudes:q=supQi=Cγ/mq=\\sup Q\_\{i\}=C\_\{\\gamma\}/m,b=infBi​i=−γ​Cγb=\\inf B\_\{ii\}=\-\\gamma C\_\{\\gamma\},a=supAi=γ​Cγa=\\sup A\_\{i\}=\\gamma C\_\{\\gamma\}:

infℋi​i\\displaystyle\\inf\\mathcal\{H\}\_\{ii\}=2⋅Cγm⋅\(−γ​Cγ\)⋅γ​Cγ=−2​γ2​Cγ3m=−2​γ2m​\(1−γ\)3,\\displaystyle=2\\cdot\\frac\{C\_\{\\gamma\}\}\{m\}\\cdot\(\-\\gamma C\_\{\\gamma\}\)\\cdot\\gamma C\_\{\\gamma\}=\\frac\{\-2\\gamma^\{2\}C\_\{\\gamma\}^\{3\}\}\{m\}=\\frac\{\-2\\gamma^\{2\}\}\{m\(1\-\\gamma\)^\{3\}\},\(28\)
SinceBi​j=\{0\}B\_\{ij\}=\\\{0\\\}fori≠ji\\neq j\(distinct bad rows share no transition coupling\), the cross\-Hessian intervals are zero:ℋi​j=\{0\}\\mathcal\{H\}\_\{ij\}=\\\{0\\\}\. An exchange between two bad rowsi,ji,jgives

S¯i​j\\displaystyle\\underline\{S\}\_\{ij\}=infℋi​i\+infℋj​j−2​supℋi​j\\displaystyle=\\inf\\mathcal\{H\}\_\{ii\}\+\\inf\\mathcal\{H\}\_\{jj\}\-2\\sup\\mathcal\{H\}\_\{ij\}=−2​γ2m​\(1−γ\)3\+−2​γ2m​\(1−γ\)3−0=−4​γ2m​\(1−γ\)3,\\displaystyle=\\frac\{\-2\\gamma^\{2\}\}\{m\(1\-\\gamma\)^\{3\}\}\+\\frac\{\-2\\gamma^\{2\}\}\{m\(1\-\\gamma\)^\{3\}\}\-0=\\frac\{\-4\\gamma^\{2\}\}\{m\(1\-\\gamma\)^\{3\}\},\(29\)
Therefore

β^=maxi<j⁡\[−S¯i​j\]\+=4​γ2m​\(1−γ\)3,\\widehat\{\\beta\}=\\max\_\{i<j\}\\left\[\-\\underline\{S\}\_\{ij\}\\right\]\_\{\+\}=\\frac\{4\\gamma^\{2\}\}\{m\(1\-\\gamma\)^\{3\}\},\(30\)which is Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)\.

#### Exact curvature\.

The exact exchange curvature alongεi−εj\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}for two bad rows is

−\(εi−εj\)⊤​∇2J​\(x\)​\(εi−εj\)\\displaystyle\-\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)^\{\\top\}\\nabla^\{2\}J\(x\)\(\\varepsilon\_\{i\}\-\\varepsilon\_\{j\}\)=1m​\[−fγ′′​\(xi\)−fγ′′​\(xj\)\]\\displaystyle=\\frac\{1\}\{m\}\\bigl\[\-f\_\{\\gamma\}^\{\\prime\\prime\}\(x\_\{i\}\)\-f\_\{\\gamma\}^\{\\prime\\prime\}\(x\_\{j\}\)\\bigr\]=1m​\[2​γ2\(1−γ\+γ​xi\)3\+2​γ2\(1−γ\+γ​xj\)3\]\.\\displaystyle=\\frac\{1\}\{m\}\\Bigl\[\\frac\{2\\gamma^\{2\}\}\{\(1\-\\gamma\+\\gamma x\_\{i\}\)^\{3\}\}\+\\frac\{2\\gamma^\{2\}\}\{\(1\-\\gamma\+\\gamma x\_\{j\}\)^\{3\}\}\\Bigr\]\.\(31\)The supremum over\[0,1\]2\[0,1\]^\{2\}is attained atxi=xj=0x\_\{i\}=x\_\{j\}=0, giving

β=4​γ2m​\(1−γ\)3=β^\.\\beta=\\frac\{4\\gamma^\{2\}\}\{m\(1\-\\gamma\)^\{3\}\}=\\widehat\{\\beta\}\.The envelopes are exact on the worst pair\. Exchanges between the dummy row and a bad row have half the magnitude \(only one nontrivial diagonal term\), so the pairwise maximum is indeed the bad–bad exchange\.

### B\.5Certificate and ratio

Sinceτ^=0\\widehat\{\\tau\}=0andd−1=md\-1=m,

ℬBell\\displaystyle\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}=τ^\+d−18​β^=m8⋅4​γ2m​\(1−γ\)3=γ22​\(1−γ\)3,\\displaystyle=\\widehat\{\\tau\}\+\\frac\{d\-1\}\{8\}\\widehat\{\\beta\}=\\frac\{m\}\{8\}\\cdot\\frac\{4\\gamma^\{2\}\}\{m\(1\-\\gamma\)^\{3\}\}=\\frac\{\\gamma^\{2\}\}\{2\(1\-\\gamma\)^\{3\}\},\(32\)This is independent ofmm\.

Dividing \([24](https://arxiv.org/html/2610.00325#A2.E24)\) by \([32](https://arxiv.org/html/2610.00325#A2.E32)\),

Gap⁡\(𝒞k\)ℬBell\\displaystyle\\frac\{\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)\}\{\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}\}=γ22​\(1−γ\)​\(2−γ\)⋅2​\(1−γ\)3γ2\\displaystyle=\\frac\{\\gamma^\{2\}\}\{2\(1\-\\gamma\)\(2\-\\gamma\)\}\\cdot\\frac\{2\(1\-\\gamma\)^\{3\}\}\{\\gamma^\{2\}\}=\(1−γ\)22−γ,\\displaystyle=\\frac\{\(1\-\\gamma\)^\{2\}\}\{2\-\\gamma\},\(33\)It tends to1/21/2asγ↓0\\gamma\\downarrow 0and satisfiesGap⁡\(𝒞k\)/ℬBell∼\(1−γ\)2\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)/\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}\\sim\(1\-\\gamma\)^\{2\}asγ↑1\\gamma\\uparrow 1\. In particular,Gap⁡\(𝒞k\)=Θ⁡\(ℬBell\)\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=\\Theta\(\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}\)asm→∞m\\to\\inftyat any fixedγ\\gamma, so no bound of the formτ\+c​β\\tau\+c\\betawithccindependent ofddcan be sound on this family\.

Atm=4m=4,γ=1/2\\gamma=1/2:β^=2\\widehat\{\\beta\}=2,ℬBell=1\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}=1, andGap⁡\(𝒞k\)=1/6\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=1/6\.

For the candidate bound,Φ⁡\(x⋆\)=m/4\\Phi\(x^\{\\star\}\)=m/4andβ^F⁡\(x⋆\)=β^\\widehat\{\\beta\}\_\{F\(x^\{\\star\}\)\}=\\widehat\{\\beta\}, soBcand​\(x⋆\)=γ2/\[4​\(1−γ\)3\]B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\)=\\gamma^\{2\}/\[4\(1\-\\gamma\)^\{3\}\]\. Sinceqm\+1,m/2=m/2q\_\{m\+1,m/2\}=m/2, the new coefficient iscm\+1,m/2=m⁡\(m\+2\)/\[16​\(m\+1\)\]c\_\{m\+1,m/2\}=m\(m\+2\)/\[16\(m\+1\)\]andBunif=m\+2m\+1​Bcand​\(x⋆\)B\_\{\\mathrm\{unif\}\}=\\frac\{m\+2\}\{m\+1\}B\_\{\\mathrm\{cand\}\}\(x^\{\\star\}\)\. This proves the remaining claims of Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)\.

### B\.6Weighted exchange interpolation

#### General identity\.

Letg∈C2​\(\[a,b\]\)g\\in C^\{2\}\(\[a,b\]\)witha<0<ba<0<b, and use the kernelKa,bK\_\{a,b\}defined in Section[4](https://arxiv.org/html/2610.00325#S4)\. Taylor’s formula givesg⁡\(a\)=g⁡\(0\)\+a​g′​\(0\)\+∫a0\(t−a\)​g′′​\(t\)​𝑑tg\(a\)=g\(0\)\+ag^\{\\prime\}\(0\)\+\\int\_\{a\}^\{0\}\(t\-a\)g^\{\\prime\\prime\}\(t\)\\,dtandg⁡\(b\)=g⁡\(0\)\+b​g′​\(0\)\+∫0b\(b−t\)​g′′​\(t\)​𝑑tg\(b\)=g\(0\)\+bg^\{\\prime\}\(0\)\+\\int\_\{0\}^\{b\}\(b\-t\)g^\{\\prime\\prime\}\(t\)\\,dt\. Multiply byb/\(b−a\)b/\(b\-a\)and\(−a\)/\(b−a\)\(\-a\)/\(b\-a\), respectively, and add\. The first\-order terms cancel, yielding the interpolation identity

g\(0\)−b​g​\(a\)−a​g​\(b\)b−a=−∫abKa,b\(t\)g′′\(t\)dt\.g\(0\)\-\\frac\{b\\,g\(a\)\-a\\,g\(b\)\}\{b\-a\}=\-\\int\_\{a\}^\{b\}K\_\{a,b\}\(t\)g^\{\\prime\\prime\}\(t\)\\,dt\.\(34\)The weighted endpoint average does not exceed the larger endpoint\. SinceKa,b≥0K\_\{a,b\}\\geq 0, taking positive parts bounds the actual loss by∫abKa,b​\(t\)​\[−g′′​\(t\)\]\+​𝑑t\\int\_\{a\}^\{b\}K\_\{a,b\}\(t\)\[\-g^\{\\prime\\prime\}\(t\)\]\_\{\+\}\\,dt\. Integration gives∫abKa,b​\(t\)​𝑑t=\(−a\)​b/2\\int\_\{a\}^\{b\}K\_\{a,b\}\(t\)\\,dt=\(\-a\)b/2, recovering the constant\-curvature charge as a special case\.

#### Exact segment maximum on the family\.

Atx⋆x^\{\\star\}, every exchange pairs two remaining half\-integral bad rows, with interval\[−1/2,1/2\]\[\-1/2,1/2\]\. Each endpoint resolves both coordinates; afterm/2m/2exchanges the policy selectsm/2m/2bad rows and is binary\-optimal\. Letδ=1−γ\\delta=1\-\\gamma\. Up to an additive constant,g⁡\(t\)=\[fγ​\(1/2\+t\)\+fγ​\(1/2−t\)\]/mg\(t\)=\[f\_\{\\gamma\}\(1/2\+t\)\+f\_\{\\gamma\}\(1/2\-t\)\]/m\. Thus−g′′​\(t\)\-g^\{\\prime\\prime\}\(t\)equals2​γ2m​\{\[δ\+γ⁡\(1/2\+t\)\]−3\+\[δ\+γ⁡\(1/2−t\)\]−3\}\\frac\{2\\gamma^\{2\}\}\{m\}\\\{\[\\delta\+\\gamma\(1/2\+t\)\]^\{\-3\}\+\[\\delta\+\\gamma\(1/2\-t\)\]^\{\-3\}\\\}\. It is convex and symmetric, so its maximum is attained at either endpoint, givingβseg=2​γ2​\(δ−3\+1\)/m\\beta\_\{\\mathrm\{seg\}\}=2\\gamma^\{2\}\(\\delta^\{\-3\}\+1\)/m\. Multiplying by1/81/8per exchange and bym/2m/2exchanges givesBseg=γ2​\(δ−3\+1\)/8B\_\{\\mathrm\{seg\}\}=\\gamma^\{2\}\(\\delta^\{\-3\}\+1\)/8\. Dividing by the exact gap yields the ratio stated in Section[4](https://arxiv.org/html/2610.00325#S4)\.

#### Exact weighted loss and reliable upper sums\.

Hereg′′<0g^\{\\prime\\prime\}<0andg\(−1/2\)=g\(1/2\)g\(\-1/2\)=g\(1/2\), so \([34](https://arxiv.org/html/2610.00325#A2.E34)\) is an equality for actual loss\. Direct substitution gives the one\-step integral\[2​fγ​\(1/2\)−fγ​\(0\)−fγ​\(1\)\]/m=γ2/\[m​δ​\(2−γ\)\]\[2f\_\{\\gamma\}\(1/2\)\-f\_\{\\gamma\}\(0\)\-f\_\{\\gamma\}\(1\)\]/m=\\gamma^\{2\}/\[m\\delta\(2\-\\gamma\)\]\. Summing provesBint=γ2/\[2​δ​\(2−γ\)\]=Gap⁡\(𝒞k\)B\_\{\\mathrm\{int\}\}=\\gamma^\{2\}/\[2\\delta\(2\-\\gamma\)\]=\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)\. For a partition into intervalsI=\[u,v\]I=\[u,v\], convexity of−g′′\-g^\{\\prime\\prime\}on this family impliesrI:=max⁡\{−g′′​\(u\),−g′′​\(v\)\}≥\[−g′′​\(t\)\]\+r\_\{I\}:=\\max\\\{\-g^\{\\prime\\prime\}\(u\),\-g^\{\\prime\\prime\}\(v\)\\\}\\geq\[\-g^\{\\prime\\prime\}\(t\)\]\_\{\+\}onII\. The sum∑IrI​∫IKa,b​\(t\)​𝑑t\\sum\_\{I\}r\_\{I\}\\int\_\{I\}K\_\{a,b\}\(t\)\\,dtis consequently a reliable upper bound\. Rational inputs make every term rational\.

#### Scope for general MDPs\.

If reliable envelopes\[−gt′′​\(s\)\]\+≤ρt​\(s\)≤β^it​jt\[\-g\_\{t\}^\{\\prime\\prime\}\(s\)\]\_\{\+\}\\leq\\rho\_\{t\}\(s\)\\leq\\widehat\{\\beta\}\_\{i\_\{t\}j\_\{t\}\}are available along a trajectory, replacing each charge by∫atbtKat,bt​\(s\)​ρt​\(s\)​𝑑s\\int\_\{a\_\{t\}\}^\{b\_\{t\}\}K\_\{a\_\{t\},b\_\{t\}\}\(s\)\\rho\_\{t\}\(s\)\\,dsgives a bound no larger thanBtraceB\_\{\\mathrm\{trace\}\}after adding the same Phase\-1 charges\. For a general MDP, polynomial enclosures bound curvature throughout each subinterval\.

### B\.7General exchange computation

###### Proof of Proposition[4\.3](https://arxiv.org/html/2610.00325#S4.Thmtheorem3)\.

Fix the current policyzzand an exchange of rowsi,ji,j\. WriteA=I−γ​P​\(z\)A=I\-\\gamma P\(z\),R=A−1R=A^\{\-1\},V=R​r​\(z\)V=Rr\(z\), andU=\[ei,−ej\]U=\[e\_\{i\},\-e\_\{j\}\]\. LetW=γ⁡\[di,dj\]W=\\gamma\[d\_\{i\},d\_\{j\}\]andη=\(Δ​ri,Δ​rj\)⊤\\eta=\(\\Delta r\_\{i\},\\Delta r\_\{j\}\)^\{\\top\}\. ThenA⁡\(t\)=A−t​U​W⊤A\(t\)=A\-tUW^\{\\top\}andr⁡\(t\)=r⁡\(z\)\+t​U​ηr\(t\)=r\(z\)\+tU\\eta\. DefineM=W⊤​R​UM=W^\{\\top\}RU,w=η\+W⊤​Vw=\\eta\+W^\{\\top\}V, andc⊤=μ⊤​R​Uc^\{\\top\}=\\mu^\{\\top\}RU\. The resolvent identity givesV⁡\(t\)=V\+t​R​U​\(I−t​M\)−1​wV\(t\)=V\+tRU\(I\-tM\)^\{\-1\}w, henceg⁡\(t\)=J⁡\(z\)\+t​c⊤​\(I−t​M\)−1​wg\(t\)=J\(z\)\+tc^\{\\top\}\(I\-tM\)^\{\-1\}w\. Setq⁡\(t\)=det\(I−t​M\)=1−t​tr⁡M\+t2​detMq\(t\)=\\det\(I\-tM\)=1\-t\\operatorname\{tr\}M\+t^\{2\}\\det Mandp⁡\(t\)=J⁡\(z\)​q​\(t\)\+t​c⊤​adj⁡\(I−t​M\)​wp\(t\)=J\(z\)q\(t\)\+tc^\{\\top\}\\operatorname\{adj\}\(I\-tM\)w\. Both polynomials have degree at most two\. The determinant lemma givesq⁡\(t\)=detA⁡\(t\)/detAq\(t\)=\\det A\(t\)/\\det A\. Every feasible policy has an invertible discounted resolvent, soqqhas no zero on the exchange interval\. Sinceq⁡\(0\)=1q\(0\)=1, continuity givesq\>0q\>0\. Finally, letN=p′​q−p​q′N=p^\{\\prime\}q\-pq^\{\\prime\}\. Its cubic coefficients cancel, sodeg⁡N≤2\\deg N\\leq 2\. Differentiating again givesg′′=h/q3g^\{\\prime\\prime\}=h/q^\{3\}, withh=N′​q−2​N​q′h=N^\{\\prime\}q\-2Nq^\{\\prime\}anddeg⁡h≤3\\deg h\\leq 3\. ∎

#### Reliable subinterval integration\.

For a subintervalI=\[u,v\]I=\[u,v\], compute exact extrema0<qI−≤q⁡\(t\)≤qI\+0<q\_\{I\}^\{\-\}\\leq q\(t\)\\leq q\_\{I\}^\{\+\}by checking its endpoints and the quadratic stationary point when it lies insideII\. After the substitutiont=u\+\(v−u\)​st=u\+\(v\-u\)s, express−h⁡\(t\)\-h\(t\)in the Bernstein basis ons∈\[0,1\]s\\in\[0,1\]\. Nonnegative basis weights sum to one, so the minimum and maximum coefficients give boundsnI−≤−h⁡\(t\)≤nI\+n\_\{I\}^\{\-\}\\leq\-h\(t\)\\leq n\_\{I\}^\{\+\}\. Consequently,ρI−:=max⁡\{0,nI−\}/\(qI\+\)3\\rho\_\{I\}^\{\-\}:=\\max\\\{0,n\_\{I\}^\{\-\}\\\}/\(q\_\{I\}^\{\+\}\)^\{3\}andρI\+:=max⁡\{0,nI\+\}/\(qI−\)3\\rho\_\{I\}^\{\+\}:=\\max\\\{0,n\_\{I\}^\{\+\}\\\}/\(q\_\{I\}^\{\-\}\)^\{3\}enclose\[−g′′​\(t\)\]\+\[\-g^\{\\prime\\prime\}\(t\)\]\_\{\+\}onII\. Include zero as a partition boundary, soKa,bK\_\{a,b\}is linear on each piece\. The exact weightsωI=∫IKa,b​\(t\)​𝑑t\\omega\_\{I\}=\\int\_\{I\}K\_\{a,b\}\(t\)\\,dtare nonnegative\. ThereforeL=∑IρI−​ωIL=\\sum\_\{I\}\\rho\_\{I\}^\{\-\}\\omega\_\{I\}andU=∑IρI\+​ωIU=\\sum\_\{I\}\\rho\_\{I\}^\{\+\}\\omega\_\{I\}enclose the weighted curvature integral\. The implementation bisects the piece with largest uncertainty\(ρI\+−ρI−\)​ωI\(\\rho\_\{I\}^\{\+\}\-\\rho\_\{I\}^\{\-\}\)\\omega\_\{I\}\. Every finite partition is sound, even if the refinement budget is exhausted\. Exact rational inputs make coefficients, extrema, weights, and comparisons rational\.

#### Accumulation and relation to global bounds\.

LetUtU\_\{t\}be the upper sum for thettth executed exchange\. The interpolation inequality bounds each positive exchange loss byUtU\_\{t\}\. Adding\[J⁡\(x\)−J⁡\(z\)\]\+\[J\(x\)\-J\(z\)\]\_\{\+\}for Phase 1 proves\[J⁡\(x\)−J⁡\(y\)\]\+≤Bloc\[J\(x\)\-J\(y\)\]\_\{\+\}\\leq B\_\{\\mathrm\{loc\}\}\. The valueJ⁡\(z\)J\(z\)is obtained by the initial resolvent solve\. If global Bellman bounds are already available, one may instead useBhyb:=∑iΔi​τ^i\+∑tmin⁡\{Ut,β^it​jt​\(−at\)​bt/2\}B\_\{\\mathrm\{hyb\}\}:=\\sum\_\{i\}\\Delta\_\{i\}\\widehat\{\\tau\}\_\{i\}\+\\sum\_\{t\}\\min\\\{U\_\{t\},\\widehat\{\\beta\}\_\{i\_\{t\}j\_\{t\}\}\(\-a\_\{t\}\)b\_\{t\}/2\\\}\. Then\[J⁡\(x\)−J⁡\(y\)\]\+≤Bhyb≤Btrace≤Bcand≤Bunif\[J\(x\)\-J\(y\)\]\_\{\+\}\\leq B\_\{\\mathrm\{hyb\}\}\\leq B\_\{\\mathrm\{trace\}\}\\leq B\_\{\\mathrm\{cand\}\}\\leq B\_\{\\mathrm\{unif\}\}\. No ordering betweenBlocB\_\{\\mathrm\{loc\}\}andBcandB\_\{\\mathrm\{cand\}\}is required\. Both bounds are computed along the chosen rounding trajectory\.

#### Computation\.

With a stored resolvent, forming the two\-by\-two matrix and updating the selected endpoint costsO⁡\(S2\)O\(S^\{2\}\)arithmetic operations per exchange\. One initial dense inverse costsO⁡\(S3\)O\(S^\{3\}\)\. ThusTTexchanges andLLtotal subinterval computations costO⁡\(S3\+T​S2\+L\)O\(S^\{3\}\+TS^\{2\}\+L\)arithmetic operations\. Bit complexity also depends on rational operand lengths\. The same representation computes both endpoint returns with constant\-size rational operations\. The low\-rank direct baseline therefore uses precisely the same coefficient construction and resolvent updates, omitting curvature enclosures\. It selects the same endpoint as full exact policy evaluation\. Integral certification augments these updates with curvature enclosures to sharpen the trajectory loss bound\.

## Appendix CProof of Theorem[5\.2](https://arxiv.org/html/2610.00325#S5.Thmtheorem2)

This appendix proves Theorem[5\.2](https://arxiv.org/html/2610.00325#S5.Thmtheorem2)\. Begin with an arbitrary simple MAX\-CUT instance\(G0,K0\)\(G\_\{0\},K\_\{0\}\)\. Add a disjoint edge and four isolated vertices, call the padded graph\(G,K\)\(G,K\), and putK=K0\+1K=K\_\{0\}\+1\. Max\-cut values add across components, so the preprocessing preserves YES/NO\. All notation below refers to the padded graph\. In particular,

n=\|V⁡\(G\)\|≥6,m=\|E⁡\(G\)\|≥1,Λ=2​m\+1\.n=\|V\(G\)\|\\geq 6,\\qquad m=\|E\(G\)\|\\geq 1,\\qquad\\Lambda=2m\+1\.Orient every edge by increasing endpoint\. The proof constructs the restricted MDP, derives its reduced multi\-affine objective, identifies the designated exchange with a cut polynomial, separates that pair from all others, and finally checks budget feasibility and polynomial encoding size\.

### C\.1MDP construction

Use the state and control\-row ordering

p,q,L1,…,Ln,R1,…,Rn,z,N=2​n\+3,p,q,L\_\{1\},\\ldots,L\_\{n\},R\_\{1\},\\ldots,R\_\{n\},z,\\qquad N=2n\+3,and define

η=164​N2,ρ=η464​Λ​N,δ=η3,\\eta=\\frac\{1\}\{64N^\{2\}\},\\qquad\\rho=\\frac\{\\eta^\{4\}\}\{64\\Lambda N\},\\qquad\\delta=\\eta^\{3\},\(35\)so thatρ=1/\(230​Λ​N9\)\\rho=1/\(2^\{30\}\\Lambda N^\{9\}\)\. LetCChave the noncompensating entries

Cp​q\\displaystyle C\_\{pq\}=η,\\displaystyle=\\eta,Cq​Li\\displaystyle C\_\{qL\_\{i\}\}=η,\\displaystyle=\\eta,Cq​Rj\\displaystyle C\_\{qR\_\{j\}\}=η​ρ​\(Λ−deg−⁡\(j\)\),\\displaystyle=\\eta\\rho\(\\Lambda\-\\deg^\{\-\}\(j\)\),\(36\)CLi​Ri\\displaystyle C\_\{L\_\{i\}R\_\{i\}\}=−2​Λ​ρ,\\displaystyle=\-2\\Lambda\\rho,CLi​Rj\\displaystyle C\_\{L\_\{i\}R\_\{j\}\}=2ρ\(i→j∈E\),\\displaystyle=2\\rho\\quad\(i\\to j\\in E\),\(37\)and put the negative row sum in columnzzfor every nonzero row\. ThusC​𝟏=0C\\mathbf\{1\}=0\. Set

aLi=ρ⁡\(Λ−deg\+⁡\(i\)\),aRj=1,a\_\{L\_\{i\}\}=\\rho\(\\Lambda\-\\deg^\{\+\}\(i\)\),\\qquad a\_\{R\_\{j\}\}=1,\(38\)with all other entries ofaazero\.

The rank\-one baseline kernel isP0=𝟏​π⊤P^\{0\}=\\mathbf\{1\}\\pi^\{\\top\}, where

πq=πLi=δ,πRi=8​Λ​ρ,πz=14,πp=1−∑s≠pπs\.\\pi\_\{q\}=\\pi\_\{L\_\{i\}\}=\\delta,\\qquad\\pi\_\{R\_\{i\}\}=8\\Lambda\\rho,\\qquad\\pi\_\{z\}=\\frac\{1\}\{4\},\\qquad\\pi\_\{p\}=1\-\\sum\_\{s\\neq p\}\\pi\_\{s\}\.\(39\)Takeγ=1/2\\gamma=1/2,μ=εp\\mu=\\varepsilon\_\{p\},r0=0r^\{0\}=0, and define the alternative endpoints by

P1=P0\+2​C,r1=a\.P^\{1\}=P^\{0\}\+2C,\\qquad r^\{1\}=a\.\(40\)
#### Verification of the raw promises\.

We check that bothP0P^\{0\}andP1P^\{1\}are valid stochastic matrices and that rewards lie in\[0,1\]\[0,1\]\.

*Baseline positivity\.*The mass outside stateppis

∑s≠pπs\\displaystyle\\sum\_\{s\\neq p\}\\pi\_\{s\}=14\+\(n\+1\)​δ\+n⋅8​Λ​ρ=14\+\(n\+1\)​η3\+8​n​Λ​ρ\\displaystyle=\\frac\{1\}\{4\}\+\(n\+1\)\\delta\+n\\cdot 8\\Lambda\\rho=\\frac\{1\}\{4\}\+\(n\+1\)\\eta^\{3\}\+8n\\Lambda\\rho<14\+n\+1643​N6\+8​n230​N9<12,\\displaystyle<\\frac\{1\}\{4\}\+\\frac\{n\+1\}\{64^\{3\}N^\{6\}\}\+\\frac\{8n\}\{2^\{30\}N^\{9\}\}<\\frac\{1\}\{2\},\(41\)The last inequality usesn<Nn<NandN≥15N\\geq 15\. Henceπp=1−∑s≠pπs\>1/2\>0\\pi\_\{p\}=1\-\\sum\_\{s\\neq p\}\\pi\_\{s\}\>1/2\>0, and since every other component ofπ\\piis manifestly positive,P0=𝟏​π⊤P^\{0\}=\\mathbf\{1\}\\pi^\{\\top\}has all positive entries\.

*Stochasticity ofP1P^\{1\}\.*Row stochasticity ofP1=P0\+2​CP^\{1\}=P^\{0\}\+2Cfollows fromC​𝟏=0C\\mathbf\{1\}=0:P1​𝟏=P0​𝟏\+2​C​𝟏=𝟏\+0=𝟏P^\{1\}\\mathbf\{1\}=P^\{0\}\\mathbf\{1\}\+2C\\mathbf\{1\}=\\mathbf\{1\}\+0=\\mathbf\{1\}\.

*Positivity ofP1P^\{1\}\.*The only negative transition edits occur atp→zp\\to z,q→zq\\to z, andLi→RiL\_\{i\}\\to R\_\{i\}:

1. 1\.Atp→zp\\to z: the compensating entryCp​z=−ηC\_\{pz\}=\-\\eta, soPp​z1=πz\+2​Cp​z=1/4−2​η\>0P^\{1\}\_\{pz\}=\\pi\_\{z\}\+2C\_\{pz\}=1/4\-2\\eta\>0becauseη<1/8\\eta<1/8\.
2. 2\.Atq→zq\\to z: the compensating entry satisfies \|Cq​z\|\\displaystyle\|C\_\{qz\}\|=∑iCq​Li\+∑jCq​Rj=n​η\+η​ρ​∑j\(Λ−deg−⁡\(j\)\)\\displaystyle=\\sum\_\{i\}C\_\{qL\_\{i\}\}\+\\sum\_\{j\}C\_\{qR\_\{j\}\}=n\\eta\+\\eta\\rho\\sum\_\{j\}\(\\Lambda\-\\deg^\{\-\}\(j\)\)=n​η\+η​ρ​\(n​Λ−m\)<2​n​η,\\displaystyle=n\\eta\+\\eta\\rho\(n\\Lambda\-m\)<2n\\eta,\(42\)Here∑jdeg−⁡\(j\)=m\\sum\_\{j\}\\deg^\{\-\}\(j\)=m, and the final bound follows fromρ<1/Λ\\rho<1/\\Lambda\. HencePq​z1=πz−2​\|Cq​z\|\>1/4−4​n​η\>0P^\{1\}\_\{qz\}=\\pi\_\{z\}\-2\|C\_\{qz\}\|\>1/4\-4n\\eta\>0\.
3. 3\.AtLi→RiL\_\{i\}\\to R\_\{i\}:PLi​Ri1=πRi\+2​CLi​Ri=8​Λ​ρ−4​Λ​ρ=4​Λ​ρ\>0P^\{1\}\_\{L\_\{i\}R\_\{i\}\}=\\pi\_\{R\_\{i\}\}\+2C\_\{L\_\{i\}R\_\{i\}\}=8\\Lambda\\rho\-4\\Lambda\\rho=4\\Lambda\\rho\>0\.

All other edits are nonnegative\.

*Reward bounds\.*By \([38](https://arxiv.org/html/2610.00325#A3.E38)\),0<aLi=ρ⁡\(Λ−deg\+⁡\(i\)\)≤ρ​Λ<10<a\_\{L\_\{i\}\}=\\rho\(\\Lambda\-\\deg^\{\+\}\(i\)\)\\leq\\rho\\Lambda<1, andaRj=1a\_\{R\_\{j\}\}=1\. All remaining rewards are zero\.

*Support structure\.*The nonzero entries ofCCdefine a DAG with edgesp→qp\\to q,q→Liq\\to L\_\{i\},q→Rjq\\to R\_\{j\}, andLi→RjL\_\{i\}\\to R\_\{j\}\. The longest directed path isp→q→Li→Rjp\\to q\\to L\_\{i\}\\to R\_\{j\}, which has length three\. Every compensator edge ends atzz, which has no outgoing edges in the DAG\. Hence𝒢⁡\(C\)\\mathcal\{G\}\(C\)has depth at most three, confirmingℳG∈𝔅3\\mathcal\{M\}\_\{G\}\\in\\mathfrak\{B\}\_\{3\}\.

### C\.2Resolvent and reduced objects

SinceP0=𝟏​π⊤P^\{0\}=\\mathbf\{1\}\\pi^\{\\top\}is rank one andγ=1/2\\gamma=1/2, the resolvent has a closed form via the Neumann series:

R0\\displaystyle R\_\{0\}=\(I−γ​P0\)−1=\(I−12​𝟏​π⊤\)−1\\displaystyle=\(I\-\\gamma P^\{0\}\)^\{\-1\}=\(I\-\\tfrac\{1\}\{2\}\\mathbf\{1\}\\pi^\{\\top\}\)^\{\-1\}=∑t=0∞\(12\)t​\(𝟏​π⊤\)t=I\+∑t=1∞\(12\)t​𝟏​π⊤\\displaystyle=\\sum\_\{t=0\}^\{\\infty\}\(\\tfrac\{1\}\{2\}\)^\{t\}\(\\mathbf\{1\}\\pi^\{\\top\}\)^\{t\}=I\+\\sum\_\{t=1\}^\{\\infty\}\(\\tfrac\{1\}\{2\}\)^\{t\}\\mathbf\{1\}\\pi^\{\\top\}=I\+𝟏​π⊤,\\displaystyle=I\+\\mathbf\{1\}\\pi^\{\\top\},\(43\)The Neumann series converges becauseρ⁡\(12​𝟏​π⊤\)=1/2\\rho\(\\tfrac\{1\}\{2\}\\mathbf\{1\}\\pi^\{\\top\}\)=1/2\. Fort≥1t\\geq 1,\(𝟏​π⊤\)t=𝟏​π⊤\(\\mathbf\{1\}\\pi^\{\\top\}\)^\{t\}=\\mathbf\{1\}\\pi^\{\\top\}, and the remaining scalar series sums to one\.

The initial visitation vector is

u⊤=μ⊤​R0=εp⊤​\(I\+𝟏​π⊤\)=εp⊤\+π⊤\.u^\{\\top\}=\\mu^\{\\top\}R\_\{0\}=\\varepsilon\_\{p\}^\{\\top\}\(I\+\\mathbf\{1\}\\pi^\{\\top\}\)=\\varepsilon\_\{p\}^\{\\top\}\+\\pi^\{\\top\}\.\(44\)In particular,U≔up=1\+πpU\\coloneqq u\_\{p\}=1\+\\pi\_\{p\}andus=πsu\_\{s\}=\\pi\_\{s\}fors≠ps\\neq p\.

#### Reduced transition matrix\.

SinceP1−P0=2​CP^\{1\}\-P^\{0\}=2C, the reduced matrix is

γ⁡\(P1−P0\)​R0\\displaystyle\\gamma\(P^\{1\}\-P^\{0\}\)R\_\{0\}=12⋅2​C⋅\(I\+𝟏​π⊤\)=C⁡\(I\+𝟏​π⊤\)\\displaystyle=\\tfrac\{1\}\{2\}\\cdot 2C\\cdot\(I\+\\mathbf\{1\}\\pi^\{\\top\}\)=C\(I\+\\mathbf\{1\}\\pi^\{\\top\}\)=C\+C​𝟏​π⊤=C,\\displaystyle=C\+C\\mathbf\{1\}\\pi^\{\\top\}=C,\(45\)The final equality usesC​𝟏=0C\\mathbf\{1\}=0\. Thus the reduced objects are exactlyCC,aa, anduu, and the reduced performance identity \([5](https://arxiv.org/html/2610.00325#S5)\) holds\.

### C\.3Expansion of the objective

Because𝒢⁡\(C\)\\mathcal\{G\}\(C\)has depth three,\(X​C\)4=0\(XC\)^\{4\}=0for any diagonalX=diag⁡\(x\)X=\\operatorname\{diag\}\(x\)withx∈\[0,1\]Nx\\in\[0,1\]^\{N\}\. The Neumann inverse in \([5](https://arxiv.org/html/2610.00325#S5)\) therefore truncates:

\(I−X​C\)−1=I\+X​C\+\(X​C\)2\+\(X​C\)3\.\(I\-XC\)^\{\-1\}=I\+XC\+\(XC\)^\{2\}\+\(XC\)^\{3\}\.\(46\)Write

Ai=Λ−deg\+⁡\(i\),Bj=Λ−deg−⁡\(j\),ci​j=2​ρ​\(𝟏i→j−Λ​𝟏i=j\),A\_\{i\}=\\Lambda\-\\deg^\{\+\}\(i\),\\quad B\_\{j\}=\\Lambda\-\\deg^\{\-\}\(j\),\\quad c\_\{ij\}=2\\rho\(\\mathbf\{1\}\_\{i\\to j\}\-\\Lambda\\mathbf\{1\}\_\{i=j\}\),and letU=upU=u\_\{p\},ℓi=xLi\\ell\_\{i\}=x\_\{L\_\{i\}\}, andrj=xRjr\_\{j\}=x\_\{R\_\{j\}\}\.

#### Path enumeration\.

Each nonzero term inu⊤​\(I−X​C\)−1​X​au^\{\\top\}\(I\-XC\)^\{\-1\}Xacorresponds to a directed path in𝒢⁡\(C\)\\mathcal\{G\}\(C\)ending at a state with nonzero reward\. The nonzero rewards areaLi=ρ​Aia\_\{L\_\{i\}\}=\\rho A\_\{i\}andaRj=1a\_\{R\_\{j\}\}=1\. We enumerate every contributing path by length\.

*Length zero*\(the identity term\):us⋅xs⋅asu\_\{s\}\\cdot x\_\{s\}\\cdot a\_\{s\}is nonzero only fors=Lis=L\_\{i\}ors=Rjs=R\_\{j\}\. This gives∑iπLi​ℓi​ρ​Ai\+∑jπRj​rj=δ​ρ​∑iAi​ℓi\+8​Λ​ρ​∑jrj\\sum\_\{i\}\\pi\_\{L\_\{i\}\}\\ell\_\{i\}\\rho A\_\{i\}\+\\sum\_\{j\}\\pi\_\{R\_\{j\}\}r\_\{j\}=\\delta\\rho\\sum\_\{i\}A\_\{i\}\\ell\_\{i\}\+8\\Lambda\\rho\\sum\_\{j\}r\_\{j\}\.

*Length one*\(theX​CXCterm\): paths of the forms→ts\\to twithat≠0a\_\{t\}\\neq 0\. The only edges ending at a rewarded state areLi→RjL\_\{i\}\\to R\_\{j\}\(with coefficientci​jc\_\{ij\}\) andq→Liq\\to L\_\{i\}\(with coefficientη\\eta\)\. These contribute∑i,juLi​ℓi​ci​j​rj⋅1\+∑iuq​xq​η​ℓi​ρ​Ai\\sum\_\{i,j\}u\_\{L\_\{i\}\}\\ell\_\{i\}c\_\{ij\}r\_\{j\}\\cdot 1\+\\sum\_\{i\}u\_\{q\}x\_\{q\}\\eta\\ell\_\{i\}\\rho A\_\{i\}\. The first sum isδ​∑i,jci​j​ℓi​rj\\delta\\sum\_\{i,j\}c\_\{ij\}\\ell\_\{i\}r\_\{j\}\. The second isδ​η​ρ​xq​∑iAi​ℓi\\delta\\eta\\rho x\_\{q\}\\sum\_\{i\}A\_\{i\}\\ell\_\{i\}\.

*Length two and three:*pathsq→Li→Rjq\\to L\_\{i\}\\to R\_\{j\}andp→q→Li→Rjp\\to q\\to L\_\{i\}\\to R\_\{j\}\(arriving atRjR\_\{j\}with reward 1\), plusp→q→Lip\\to q\\to L\_\{i\}\(arriving atLiL\_\{i\}with rewardρ​Ai\\rho A\_\{i\}\)\. Collecting all terms involving the cut polynomialgGg\_\{G\}\(defined below\) and combining with the shorter paths gives

J⁡\(x\)=\\displaystyle J\(x\)=\{\}δ​ρ​∑iAi​ℓi\+8​Λ​ρ​∑jrj\+δ​∑i,jci​j​ℓi​rj\\displaystyle\\delta\\rho\\sum\_\{i\}A\_\{i\}\\ell\_\{i\}\+8\\Lambda\\rho\\sum\_\{j\}r\_\{j\}\+\\delta\\sum\_\{i,j\}c\_\{ij\}\\ell\_\{i\}r\_\{j\}\+δ​η​ρ​xq​gG​\(ℓ,r\)\+U​η2​ρ​xp​xq​gG​\(ℓ,r\),\\displaystyle\+\\delta\\eta\\rho\\,x\_\{q\}g\_\{G\}\(\\ell,r\)\+U\\eta^\{2\}\\rho\\,x\_\{p\}x\_\{q\}g\_\{G\}\(\\ell,r\),\(47\)where

gG​\(ℓ,r\)=Λ​∑i\(ℓi\+ri−2​ℓi​ri\)−∑i→j∈E\(ℓi\+rj−2​ℓi​rj\)\.g\_\{G\}\(\\ell,r\)=\\Lambda\\sum\_\{i\}\(\\ell\_\{i\}\+r\_\{i\}\-2\\ell\_\{i\}r\_\{i\}\)\-\\sum\_\{i\\to j\\in E\}\(\\ell\_\{i\}\+r\_\{j\}\-2\\ell\_\{i\}r\_\{j\}\)\.\(48\)

#### Derivation of the designated Hessian\.

Every monomial in \([47](https://arxiv.org/html/2610.00325#A3.E47)\) is multi\-affine \(degree at most one in each variable\)\. Hence all pure second derivatives vanish:∂p​pJ=∂q​qJ=0\\partial\_\{pp\}J=\\partial\_\{qq\}J=0\. The mixed derivative∂p​qJ\\partial\_\{pq\}Jextracts only the terms containing bothxpx\_\{p\}andxqx\_\{q\}, which is the last term in \([47](https://arxiv.org/html/2610.00325#A3.E47)\):

∂p​qJ⁡\(x\)\\displaystyle\\partial\_\{pq\}J\(x\)=∂p∂q\[U​η2​ρ​xp​xq​gG​\(ℓ,r\)\]=U​η2​ρ​gG​\(ℓ,r\)\.\\displaystyle=\\partial\_\{p\}\\partial\_\{q\}\\bigl\[U\\eta^\{2\}\\rho\\,x\_\{p\}x\_\{q\}\\,g\_\{G\}\(\\ell,r\)\\bigr\]=U\\eta^\{2\}\\rho\\,g\_\{G\}\(\\ell,r\)\.\(49\)Therefore the exchange curvature alongεp−εq\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}is

−HℳG,εp−εq​\(x\)=−\(εp−εq\)⊤​∇2J​\(x\)​\(εp−εq\)=2​∂p​qJ⁡\(x\)=αG​gG​\(ℓ,r\),\-H\_\{\\mathcal\{M\}\_\{G\},\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}\}\(x\)=\-\(\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}\)^\{\\top\}\\nabla^\{2\}J\(x\)\(\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}\)=2\\partial\_\{pq\}J\(x\)=\\alpha\_\{G\}g\_\{G\}\(\\ell,r\),\(50\)withαG=2​U​η2​ρ\>0\\alpha\_\{G\}=2U\\eta^\{2\}\\rho\>0\. The factor of22arises because the off\-diagonal entry of the Hessian appears twice \(the\(p,q\)\(p,q\)and\(q,p\)\(q,p\)entries\) and with a sign flip from the exchange directionεp−εq\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}\.

### C\.4Maximizing the cut polynomial

The maximum of a multi\-affine polynomial on a cube occurs at a vertex\. We show that every vertex maximizer ofgGg\_\{G\}over\{0,1\}2​n\\\{0,1\\\}^\{2n\}is complementary \(ri=1−ℓir\_\{i\}=1\-\\ell\_\{i\}for allii\)\.

#### Non\-complementary vertices are suboptimal\.

At a binary vertex\(ℓ,r\)∈\{0,1\}2​n\(\\ell,r\)\\in\\\{0,1\\\}^\{2n\}, letDDcount the number of indices withri≠1−ℓir\_\{i\}\\neq 1\-\\ell\_\{i\}\. For such an index, the contribution to theΛ\\Lambda\-term is:

- •If\(ℓi,ri\)=\(0,0\)\(\\ell\_\{i\},r\_\{i\}\)=\(0,0\):Λ⁡\(0\+0−0\)=0\\Lambda\(0\+0\-0\)=0\.
- •If\(ℓi,ri\)=\(1,1\)\(\\ell\_\{i\},r\_\{i\}\)=\(1,1\):Λ⁡\(1\+1−2\)=0\\Lambda\(1\+1\-2\)=0\.

In both cases, vertexiicontributes zero to theΛ\\Lambda\-sum, compared toΛ\\Lambdafor a complementary pair\. The edge terms−\(ℓi\+rj−2​ℓi​rj\)\-\(\\ell\_\{i\}\+r\_\{j\}\-2\\ell\_\{i\}r\_\{j\}\)have absolute value at most 1 per edge\. Therefore

gG​\(ℓ,r\)\\displaystyle g\_\{G\}\(\\ell,r\)≤Λ⁡\(n−D\)\+m≤Λ⁡\(n−1\)\+m\\displaystyle\\leq\\Lambda\(n\-D\)\+m\\leq\\Lambda\(n\-1\)\+m=Λ​n−Λ\+m=Λ​n−\(2​m\+1\)\+m=Λ​n−m−1,\\displaystyle=\\Lambda n\-\\Lambda\+m=\\Lambda n\-\(2m\+1\)\+m=\\Lambda n\-m\-1,\(51\)The first inequality bounds the edge terms bymm\. The second usesD≥1D\\geq 1, and the last equality substitutesΛ=2​m\+1\\Lambda=2m\+1\.

#### Complementary vertices achieve the cut value\.

A complementary assignmentri=1−ℓir\_\{i\}=1\-\\ell\_\{i\}givesℓi\+ri−2​ℓi​ri=1\\ell\_\{i\}\+r\_\{i\}\-2\\ell\_\{i\}r\_\{i\}=1for everyii, so theΛ\\Lambda\-sum equalsΛ​n\\Lambda n\. For each edgei→j∈Ei\\to j\\in E, letSi=ℓiS\_\{i\}=\\ell\_\{i\}encode the partition\. Then

ℓi\+rj−2​ℓi​rj\\displaystyle\\ell\_\{i\}\+r\_\{j\}\-2\\ell\_\{i\}r\_\{j\}=Si\+\(1−Sj\)−2​Si​\(1−Sj\)\\displaystyle=S\_\{i\}\+\(1\-S\_\{j\}\)\-2S\_\{i\}\(1\-S\_\{j\}\)=Si\+1−Sj−2​Si\+2​Si​Sj=1−Si−Sj\+2​Si​Sj\\displaystyle=S\_\{i\}\+1\-S\_\{j\}\-2S\_\{i\}\+2S\_\{i\}S\_\{j\}=1\-S\_\{i\}\-S\_\{j\}\+2S\_\{i\}S\_\{j\}=1−𝟏Si≠Sj,\\displaystyle=1\-\\mathbf\{1\}\_\{S\_\{i\}\\neq S\_\{j\}\},\(52\)Hence∑i→j\(ℓi\+rj−2​ℓi​rj\)=m−cutG⁡\(S\)\\sum\_\{i\\to j\}\(\\ell\_\{i\}\+r\_\{j\}\-2\\ell\_\{i\}r\_\{j\}\)=m\-\\operatorname\{cut\}\_\{G\}\(S\), and

gG​\(ℓ,r\)=Λ​n−\(m−cutG⁡\(S\)\)=Λ​n−m\+cutG⁡\(S\)\.g\_\{G\}\(\\ell,r\)=\\Lambda n\-\(m\-\\operatorname\{cut\}\_\{G\}\(S\)\)=\\Lambda n\-m\+\\operatorname\{cut\}\_\{G\}\(S\)\.\(53\)SincecutG⁡\(S\)≥0\\operatorname\{cut\}\_\{G\}\(S\)\\geq 0, a complementary vertex achieves at leastΛ​n−m\>Λ​n−m−1\\Lambda n\-m\>\\Lambda n\-m\-1, which exceeds the non\-complementary bound \([51](https://arxiv.org/html/2610.00325#A3.E51)\)\. Therefore every maximizer is complementary, and

max\[0,1\]2​n⁡gG=Λ​n−m\+MaxCut⁡\(G\)\.\\max\_\{\[0,1\]^\{2n\}\}g\_\{G\}=\\Lambda n\-m\+\\MaxCut\(G\)\.\(54\)The right side is positive, so the positive part inκ\\kappadoes not alter the supremum\.

### C\.5Bounds for all row pairs

Equation \([47](https://arxiv.org/html/2610.00325#A3.E47)\) lists every possible nonzero mixed derivative\. We show that the designated pair\(p,q\)\(p,q\)strictly dominates all others\.

#### Zero pairs\.

Pairs containingzzare zero becausexzx\_\{z\}appears in no term of \([47](https://arxiv.org/html/2610.00325#A3.E47)\)\. Pairs within theLLblock \(Li,LjL\_\{i\},L\_\{j\}withi≠ji\\neq j\) are zero because no monomial containsℓi​ℓj\\ell\_\{i\}\\ell\_\{j\}\(multi\-affinity and the DAG structure preclude such products\)\. Similarly, pairs within theRRblock are zero\.

#### Coefficient bounds for nonzero pairs\.

For a multi\-affine polynomialh⁡\(x1,…,xN\)h\(x\_\{1\},\\ldots,x\_\{N\}\), the supremum of\|h\|\|h\|over\[0,1\]N\[0,1\]^\{N\}is at most theℓ1\\ell\_\{1\}\-norm of its coefficients \(the sum of absolute values of all coefficients\)\. Define

M=U​η2​ρ​Λ=αG​Λ2\.M=U\\eta^\{2\}\\rho\\Lambda=\\frac\{\\alpha\_\{G\}\\Lambda\}\{2\}\.\(55\)The absolute column sums ofci​jc\_\{ij\}are

∑j\|ci​j\|=2​ρ​\(Λ\+deg\+⁡\(i\)\),∑i\|ci​j\|=2​ρ​\(Λ\+deg−⁡\(j\)\),\\sum\_\{j\}\|c\_\{ij\}\|=2\\rho\(\\Lambda\+\\deg^\{\+\}\(i\)\),\\qquad\\sum\_\{i\}\|c\_\{ij\}\|=2\\rho\(\\Lambda\+\\deg^\{\-\}\(j\)\),\(56\)since each rowiiofcchas one entry−2​Λ​ρ\-2\\Lambda\\rho\(the diagonal\) anddeg\+⁡\(i\)\\deg^\{\+\}\(i\)entries of\+2​ρ\+2\\rho\.

We bound each pair type\. Letdddenote the relevant in\- or out\-degree\.

*Pair\(p,Li\)\(p,L\_\{i\}\)or\(p,Rj\)\(p,R\_\{j\}\):*The only term in \([47](https://arxiv.org/html/2610.00325#A3.E47)\) involving bothxpx\_\{p\}and a graph variable is the last termU​η2​ρ​xp​xq​gG​\(ℓ,r\)U\\eta^\{2\}\\rho\\,x\_\{p\}x\_\{q\}\\,g\_\{G\}\(\\ell,r\)\. The coefficientℓ1\\ell\_\{1\}\-norm ofgGg\_\{G\}restricted to terms involvingℓi\\ell\_\{i\}\(orrjr\_\{j\}\) is at most3​Λ\+deg\+⁡\(i\)3\\Lambda\+\\deg^\{\+\}\(i\):

‖gG\|ℓi‖1\\displaystyle\\\|g\_\{G\}\|\_\{\\ell\_\{i\}\}\\\|\_\{1\}=\(Λ−deg\+⁡\(i\)\)\+2​Λ\+2​deg\+⁡\(i\)=3​Λ\+deg\+⁡\(i\)\.\\displaystyle=\(\\Lambda\-\\deg^\{\+\}\(i\)\)\+2\\Lambda\+2\\deg^\{\+\}\(i\)=3\\Lambda\+\\deg^\{\+\}\(i\)\.\(57\)The three terms come from the linear coefficient, the bilinearℓi​ri\\ell\_\{i\}r\_\{i\}coefficient, and the outgoing\-edge bilinears, respectively\. Hence\|∂p,LiJ\|≤U​η2​ρ​\(3​Λ\+deg\+⁡\(i\)\)\|\\partial\_\{p,L\_\{i\}\}J\|\\leq U\\eta^\{2\}\\rho\(3\\Lambda\+\\deg^\{\+\}\(i\)\)\. Sincedeg\+⁡\(i\)≤m<2​m\+1=Λ\\deg^\{\+\}\(i\)\\leq m<2m\+1=\\Lambda,

U​η2​ρ​\(3​Λ\+d\)<U​η2​ρ⋅4​Λ=4​M\.U\\eta^\{2\}\\rho\(3\\Lambda\+d\)<U\\eta^\{2\}\\rho\\cdot 4\\Lambda=4M\.\(58\)
*Pair\(q,Li\)\(q,L\_\{i\}\)or\(q,Rj\)\(q,R\_\{j\}\):*Both theδ​η​ρ​xq​gG\\delta\\eta\\rho\\,x\_\{q\}\\,g\_\{G\}andU​η2​ρ​xp​xq​gGU\\eta^\{2\}\\rho\\,x\_\{p\}x\_\{q\}g\_\{G\}terms contribute\. The combined coefficient is\(δ​η\+U​η2\)​ρ​\(3​Λ\+deg\+⁡\(i\)\)\(\\delta\\eta\+U\\eta^\{2\}\)\\rho\(3\\Lambda\+\\deg^\{\+\}\(i\)\)\. Sinceδ/\(η​U\)=η3/\(η​U\)=η2/U\\delta/\(\\eta U\)=\\eta^\{3\}/\(\\eta U\)=\\eta^\{2\}/U, andU=1\+πp\>1U=1\+\\pi\_\{p\}\>1whileη2<1/16\\eta^\{2\}<1/16, we haveδ​η<U​η2/16\\delta\\eta<U\\eta^\{2\}/16\. Therefore

\(δ​η\+U​η2\)​ρ​\(3​Λ\+deg\+⁡\(i\)\)<1716​U​η2​ρ⋅4​Λ=174​M\.\(\\delta\\eta\+U\\eta^\{2\}\)\\rho\(3\\Lambda\+\\deg^\{\+\}\(i\)\)<\\frac\{17\}\{16\}U\\eta^\{2\}\\rho\\cdot 4\\Lambda=\\frac\{17\}\{4\}M\.\(59\)
*Pair\(Li,Rj\)\(L\_\{i\},R\_\{j\}\):*The terms involving bothℓi\\ell\_\{i\}andrjr\_\{j\}come fromδ​ci​j​ℓi​rj\\delta c\_\{ij\}\\ell\_\{i\}r\_\{j\},δ​η​ρ​xq​\(terms in​gG\)\\delta\\eta\\rho x\_\{q\}\(\\text\{terms in \}g\_\{G\}\), andU​η2​ρ​xp​xq​\(terms in​gG\)U\\eta^\{2\}\\rho x\_\{p\}x\_\{q\}\(\\text\{terms in \}g\_\{G\}\)\. The coefficient bound is\|ci​j\|​\(δ\+δ​η\+U​η2\)\|c\_\{ij\}\|\(\\delta\+\\delta\\eta\+U\\eta^\{2\}\)\. Sinceδ⁡\(1\+η\)/\(U​η2\)=η⁡\(1\+η\)/U<1/16\\delta\(1\+\\eta\)/\(U\\eta^\{2\}\)=\\eta\(1\+\\eta\)/U<1/16\(usingη<1/8\\eta<1/8andU\>1U\>1\),

\|ci​j\|​\{δ⁡\(1\+η\)\+U​η2\}<1716​\|ci​j\|​U​η2\.\|c\_\{ij\}\|\\\{\\delta\(1\+\\eta\)\+U\\eta^\{2\}\\\}<\\frac\{17\}\{16\}\|c\_\{ij\}\|U\\eta^\{2\}\.\(60\)The largest\|ci​j\|\|c\_\{ij\}\|is2​Λ​ρ2\\Lambda\\rho\(the diagonal entry\)\. Hence

\|∂Li,RjJ\|<1716⋅2​Λ​ρ⋅U​η2=178⋅M<94​M\.\|\\partial\_\{L\_\{i\},R\_\{j\}\}J\|<\\frac\{17\}\{16\}\\cdot 2\\Lambda\\rho\\cdot U\\eta^\{2\}=\\frac\{17\}\{8\}\\cdot M<\\frac\{9\}\{4\}M\.\(61\)
These bounds are summarized in the following table:

#### Separation of the designated pair\.

Exchange curvature is twice the corresponding mixed derivative\. Thus every undesignated pair satisfies

κ⁡\(εa−εb\)<2⋅174​M=172​M\.\\kappa\(\\varepsilon\_\{a\}\-\\varepsilon\_\{b\}\)<2\\cdot\\frac\{17\}\{4\}M=\\frac\{17\}\{2\}M\.\(62\)In contrast, the designated pair\(p,q\)\(p,q\)achieves

κ⁡\(εp−εq\)\\displaystyle\\kappa\(\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}\)=αG​max\[0,1\]2​n​gG=αG​\(Λ​n−m\+MaxCut⁡\(G\)\)\\displaystyle=\\alpha\_\{G\}\\max\_\{\[0,1\]^\{2n\}\}g\_\{G\}=\\alpha\_\{G\}\(\\Lambda n\-m\+\\MaxCut\(G\)\)=2​M​\(n−m/Λ\)≥2​M​\(n−m2​m\+1\)\\displaystyle=2M\(n\-m/\\Lambda\)\\geq 2M\\left\(n\-\\frac\{m\}\{2m\+1\}\\right\)\>2​M​\(6−12\)=11​M,\\displaystyle\>2M\\left\(6\-\\frac\{1\}\{2\}\\right\)=11M,\(63\)HereαG​Λ=2​M\\alpha\_\{G\}\\Lambda=2M,m/Λ<1/2m/\\Lambda<1/2, andn≥6n\\geq 6\. Since11​M\>17​M/211M\>17M/2, the designated pair strictly realizes the all\-pairs maximumβ\\beta, proving \([5](https://arxiv.org/html/2610.00325#S5.SS0.SSS0.Px1)\)\.

### C\.6Feasibility under a row budget

For completeness, define the exchange\-feasible and binary curvature restricted to the budget set by

βℳ,k↔\\displaystyle\\beta\_\{\\mathcal\{M\},k\}^\{\\leftrightarrow\}:=maxa<bsupx∈𝒞k:x±δ⁡\(εa−εb\)∈𝒞k​for some​δ\>0\[−Hℳ,εa−εb\(x\)\]\+,\\displaystyle:=\\max\_\{a<b\}\\ \\sup\_\{\\begin\{subarray\}\{c\}x\\in\\mathcal\{C\}\_\{k\}:\\\\ x\\pm\\delta\(\\varepsilon\_\{a\}\-\\varepsilon\_\{b\}\)\\in\\mathcal\{C\}\_\{k\}\\ \\text\{for some \}\\delta\>0\\end\{subarray\}\}\\left\[\-H\_\{\\mathcal\{M\},\\varepsilon\_\{a\}\-\\varepsilon\_\{b\}\}\(x\)\\right\]\_\{\+\},\(64\)βℳ,kbin\\displaystyle\\beta\_\{\\mathcal\{M\},k\}^\{\\mathrm\{bin\}\}:=maxa<b⁡maxx∈𝒞kbin​\[−Hℳ,εa−εb​\(x\)\]\+\.\\displaystyle:=\\max\_\{a<b\}\\ \\max\_\{x\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}\}\\left\[\-H\_\{\\mathcal\{M\},\\varepsilon\_\{a\}\-\\varepsilon\_\{b\}\}\(x\)\\right\]\_\{\+\}\.\(65\)These quantities are used only to state the budget bridge for the reduction image\. Theorem[5\.2](https://arxiv.org/html/2610.00325#S5.Thmtheorem2)itself concerns the unrestricted\-cube quantities\.

Equation \([50](https://arxiv.org/html/2610.00325#A3.E50)\) shows that the designated exchange curvature depends only on\(ℓ,r\)\(\\ell,r\), not onxp,xq,xzx\_\{p\},x\_\{q\},x\_\{z\}\. We show that the curvature maximum is attainable within𝒞n\+1\\mathcal\{C\}\_\{n\+1\}\.

#### Mass accounting\.

The proof of \([54](https://arxiv.org/html/2610.00325#A3.E54)\) shows that every maximizing graph assignment is complementary:

ℓi\+ri=1\(i=1,…,n\)\.\\ell\_\{i\}\+r\_\{i\}=1\\quad\(i=1,\\ldots,n\)\.The total mass of such an assignment is

∑i=1n\(ℓi\+ri\)\\displaystyle\\sum\_\{i=1\}^\{n\}\(\\ell\_\{i\}\+r\_\{i\}\)=∑i=1n1=n\.\\displaystyle=\\sum\_\{i=1\}^\{n\}1=n\.\(66\)
Settingxp=xq=1/2x\_\{p\}=x\_\{q\}=1/2andxz=0x\_\{z\}=0gives total mass

𝟏⊤​x=n\+12\+12\+0=n\+1≤k,\\mathbf\{1\}^\{\\top\}x=n\+\\frac\{1\}\{2\}\+\\frac\{1\}\{2\}\+0=n\+1\\leq k,\(67\)sox∈𝒞n\+1x\\in\\mathcal\{C\}\_\{n\+1\}\.

#### Exchange feasibility\.

The exchange directionεp−εq\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}satisfies𝟏⊤​\(εp−εq\)=0\\mathbf\{1\}^\{\\top\}\(\\varepsilon\_\{p\}\-\\varepsilon\_\{q\}\)=0, so moving along it preserves𝟏⊤​x=n\+1\\mathbf\{1\}^\{\\top\}x=n\+1\. Starting fromxp=xq=1/2x\_\{p\}=x\_\{q\}=1/2, bothxp\+ε≤1x\_\{p\}\+\\varepsilon\\leq 1andxq−ε≥0x\_\{q\}\-\\varepsilon\\geq 0hold forε∈\(−1/2,1/2\)\\varepsilon\\in\(\-1/2,1/2\)\. Therefore the exchange can move a nonzero distance in both directions while remaining in𝒞n\+1\\mathcal\{C\}\_\{n\+1\}, and the maximum ofgGg\_\{G\}is attained\. It follows that

βℳG,k↔=βℳG\.\\beta\_\{\\mathcal\{M\}\_\{G\},k\}^\{\\leftrightarrow\}=\\beta\_\{\\mathcal\{M\}\_\{G\}\}\.\(68\)

#### Binary witness\.

For the binary quantity, setxp=xq=xz=0x\_\{p\}=x\_\{q\}=x\_\{z\}=0and choose any complementary binary assignment for the graph variables\. The total mass isn≤n\+1=kn\\leq n\+1=k, sox∈𝒞kbinx\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}\. The designated exchange evaluates toαG​gG​\(ℓ,r\)\\alpha\_\{G\}g\_\{G\}\(\\ell,r\), which equalsβℳG\\beta\_\{\\mathcal\{M\}\_\{G\}\}at any cut\-maximizing complementary assignment\. HenceβℳG,kbin=βℳG\\beta\_\{\\mathcal\{M\}\_\{G\},k\}^\{\\mathrm\{bin\}\}=\\beta\_\{\\mathcal\{M\}\_\{G\}\}\. Combined with \([68](https://arxiv.org/html/2610.00325#A3.E68)\),

βℳG,k↔=βℳG=βℳG,kbin\.\\beta\_\{\\mathcal\{M\}\_\{G\},k\}^\{\\leftrightarrow\}=\\beta\_\{\\mathcal\{M\}\_\{G\}\}=\\beta\_\{\\mathcal\{M\}\_\{G\},k\}^\{\\mathrm\{bin\}\}\.\(69\)
The bridge is specific to the reduction image\.

### C\.7Reduction and encoding size

Map the padded thresholdK=K0\+1K=K\_\{0\}\+1to

TG=αG​\(Λ​n−m\+K\)\.T\_\{G\}=\\alpha\_\{G\}\(\\Lambda n\-m\+K\)\.
#### Correctness of the reduction\.

Equations \([54](https://arxiv.org/html/2610.00325#A3.E54)\) and \([5](https://arxiv.org/html/2610.00325#S5.SS0.SSS0.Px1)\) yield a chain of equivalences:

MaxCut⁡\(G0\)≥K0\\displaystyle\\MaxCut\(G\_\{0\}\)\\geq K\_\{0\}⇔MaxCut⁡\(G\)≥K\\displaystyle\\iff\\MaxCut\(G\)\\geq K⇔Λ​n−m\+MaxCut⁡\(G\)≥Λ​n−m\+K\\displaystyle\\iff\\Lambda n\-m\+\\MaxCut\(G\)\\geq\\Lambda n\-m\+K⇔αG​\(Λ​n−m\+MaxCut⁡\(G\)\)≥TG\\displaystyle\\iff\\alpha\_\{G\}\(\\Lambda n\-m\+\\MaxCut\(G\)\)\\geq T\_\{G\}⇔βℳG≥TG,\\displaystyle\\iff\\beta\_\{\\mathcal\{M\}\_\{G\}\}\\geq T\_\{G\},\(70\)The first equivalence uses the disjoint padding edge\. The remaining steps add the constantΛ​n−m\\Lambda n\-m, multiply byαG\>0\\alpha\_\{G\}\>0, and apply \([5](https://arxiv.org/html/2610.00325#S5.SS0.SSS0.Px1)\)\.

#### Encoding size\.

All parameters are recomputed from the padded graph\. From \([35](https://arxiv.org/html/2610.00325#A3.E35)\) andm=O⁡\(n2\)m=O\(n^\{2\}\):

log2⁡η\\displaystyle\\log\_\{2\}\\eta=O⁡\(log⁡N\),\\displaystyle=O\(\\log N\),log2⁡ρ\\displaystyle\\log\_\{2\}\\rho=4​log2​η\+O⁡\(log⁡\(Λ​N\)\)=O⁡\(log⁡N\),\\displaystyle=4\\log\_\{2\}\\eta\+O\(\\log\(\\Lambda N\)\)=O\(\\log N\),log2⁡δ\\displaystyle\\log\_\{2\}\\delta=3​log2​η=O⁡\(log⁡N\)\.\\displaystyle=3\\log\_\{2\}\\eta=O\(\\log N\)\.\(71\)Each rational entry ofP0,P1,r0,r1P^\{0\},P^\{1\},r^\{0\},r^\{1\}has numerator and denominator withO⁡\(log⁡N\)O\(\\log N\)bits\. The MDP hasN=2​n\+3N=2n\+3states,NNcontrol rows, two actions per row, andN2N^\{2\}transition entries per action, givingO⁡\(N2\)O\(N^\{2\}\)rational entries total\. The dense raw MDP therefore has encoding sizeO⁡\(N2​log⁡N\)=poly⁡\(n\)O\(N^\{2\}\\log N\)=\\mathrm\{poly\}\(n\)\.

#### NP\-completeness of the binary language\.

A certificate for the binary threshold problemβℳbin≥T\\beta^\{\\mathrm\{bin\}\}\_\{\\mathcal\{M\}\}\\geq Tconsists of:

1. 1\.A pair of rows\(a,b\)\(a,b\)\.
2. 2\.A binary control vectorx∈\{0,1\}Nx\\in\\\{0,1\\\}^\{N\}\.

Given this certificate, verification proceeds in three steps: \(i\) checkℳ∈𝔅3\\mathcal\{M\}\\in\\mathfrak\{B\}\_\{3\}\(polynomial from the rational input, by Definition[5\.1](https://arxiv.org/html/2610.00325#S5.Thmtheorem1)\)\. \(ii\) computeR0=\(I−γ​P0\)−1R\_\{0\}=\(I\-\\gamma P^\{0\}\)^\{\-1\}via exact Gaussian elimination \(polynomial intermediate bit length\)\. \(iii\) evaluate−Hℳ,εa−εb​\(x\)\-H\_\{\\mathcal\{M\},\\varepsilon\_\{a\}\-\\varepsilon\_\{b\}\}\(x\)from the reduced form and compare withTT\. All steps run in polynomial time with exact rational arithmetic\. Hence the binary language is in NP, and the reduction from MAX\-CUT shows it is NP\-hard\. Therefore the binary language is NP\-complete\.

On the reduction image, the continuous maximum is attained at binary graph controls \(a maximizer ofgGg\_\{G\}can be chosen at a vertex\), proving continuous NP\-hardness\.

## Appendix DEvaluation protocol

This appendix describes the protocol behind Section[6](https://arxiv.org/html/2610.00325#S6)\. Unless explicitly markedBunifB\_\{\\mathrm\{unif\}\}, the recorded model\-only values use the legacyℬBell=τ^\+\(d−1\)​β^/8\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}=\\widehat\{\\tau\}\+\(d\-1\)\\widehat\{\\beta\}/8\. The revised uniform bound is evaluated on the closed\-form and coupled suites\. The structured\-suite coverage and recorded scaling times retain their original baseline\.

### D\.1Arithmetic discipline

The evaluation uses exact and validated quantities for different purposes\. Whenever binary optima, witnessed advantages, or exact theorem checks are reported, all model entries, returns, and certificates are represented with Python’s fractions\. Fraction\. Continuous multistart search is heuristic and supplies a feasible candidate quantized to a rational point before exact evaluation\. Certificate checks use this fixed candidate\. The large\-scale study uses directed outward\-rounded binary64 arithmetic: Bellman solutions are corrected until their inequalities hold outward, and every downstream interval operation is outward rounded\. Naive midpoint floating point supplies the uncertified comparison\.

### D\.2Grid specification

The evaluation grid crosses five factors:

1. 1\.Domain\(4 levels\):gridworld,queue,maintenance, andgarnet\.
2. 2\.Dimension\(3 levels\):d∈\{6,8,10\}d\\in\\\{6,8,10\\\}withS=dS=dstates\.
3. 3\.Budget\(2 levels\): a smaller budgetklo=⌈d/4⌉k\_\{\\mathrm\{lo\}\}=\\lceil d/4\\rceiland a larger budgetkhi=⌊d/2⌋k\_\{\\mathrm\{hi\}\}=\\lfloor d/2\\rfloor\.
4. 4\.Discount factor\(2 levels\):γ∈\{1/2,4/5\}\\gamma\\in\\\{1/2,\\,4/5\\\}\.
5. 5\.Edit type\(3 levels\): transition\-only, reward\-only, and mixed \(both transition and reward\)\.

The Cartesian product contains4×3×2×2×3=1444\\times 3\\times 2\\times 2\\times 3=144cases\. The domain generator also assigns a repair scale of35\\frac\{3\}\{5\}or11and a weak or strong baseline\. Each domain appears in3636cases, each budget, discount, and edit\-type level appears in7272cases\. Case identifiers and random seeds are deterministic functions of the grid indices\. The base seed is20260813002026081300, fixed before execution\.

### D\.3Per\-case execution sequence

Each case follows the same sequence of seven stages\.

#### Stage 1: model construction\.

The code constructs the rational MDP from the domain generator\. Every transition probability and reward is stored as an exact rational\. The domain generator uses the case seed to produce the state graph, transition kernels, and reward vectors\.

#### Stage 2: Bellman bounds\.

The code computes the2​d\+22d\+2extremal Bellman value and visitation vectors:V¯,V¯\\overline\{V\},\\underline\{V\}\(the upper and lower value bounds\) andh¯i,h¯i\\overline\{h\}\_\{i\},\\underline\{h\}\_\{i\}for each editable rowii\(the upper and lower auxiliary visitation bounds\)\. Each solve is a rational linear system\(I−γ​P\)​V=r\(I\-\\gamma P\)\\,V=runder a specific binary policy\. Every Bellman inequality is verified exactly after computation:

V¯≤Vπ≤V¯for every binary policy​π,\\underline\{V\}\\leq V^\{\\pi\}\\leq\\overline\{V\}\\quad\\text\{for every binary policy \}\\pi,using the fact that the extremal policies attain the bounds\.

#### Stage 3: certificate computation\.

The code computes the interval quantities \([14](https://arxiv.org/html/2610.00325#S3.E14)\) through \([16](https://arxiv.org/html/2610.00325#S3.E16)\):

- •The gradient intervalsGi=Qi⊙AiG\_\{i\}=Q\_\{i\}\\odot A\_\{i\}for each rowii, yieldingτ^=maxi\[−infGi\]\+\\widehat\{\\tau\}=\\max\_\{i\}\\left\[\-\\inf G\_\{i\}\\right\]\_\{\+\}\.
- •The Hessian diagonal intervalsℋi​i\\mathcal\{H\}\_\{ii\}and cross intervalsℋi​j\\mathcal\{H\}\_\{ij\}, yielding the exchange boundS¯i​j\\underline\{S\}\_\{ij\}for each pair\(i,j\)\(i,j\)\.
- •The curvature boundβ^=maxi<j⁡\[−S¯i​j\]\+\\widehat\{\\beta\}=\\max\_\{i<j\}\\left\[\-\\underline\{S\}\_\{ij\}\\right\]\_\{\+\}\.
- •The combined certificateℬBell=τ^\+d−18​β^\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}=\\widehat\{\\tau\}\+\\frac\{d\-1\}\{8\}\\widehat\{\\beta\}\.

As a cross\-check, the calculation is repeated from saved rational inputs and verified to yield identical results\.

#### Stage 4: binary enumeration\.

The exact binary optimum is computed by complete enumeration\. The smaller budget contains\|𝒞klobin\|=22\|\\mathcal\{C\}\_\{k\_\{\\mathrm\{lo\}\}\}^\{\\mathrm\{bin\}\}\|=22,3737, and176176feasible binary vectors ford=6,8,10d=6,8,10, respectively\. The largest budget contains at most638638feasible vectors\. Every return is evaluated in exact rational arithmetic\.

#### Stage 5: fractional search\.

A multistart SLSQP solver proposes a continuous pointx~∈𝒞k\\tilde\{x\}\\in\\mathcal\{C\}\_\{k\}\. The solver runs5050random starts per case with tolerance10−1210^\{\-12\}and a maximum of500500iterations, using SciPy 1\.14\. The best feasible point is projected onto𝒞k\\mathcal\{C\}\_\{k\}and then quantized to a rational with denominator at most10610^\{6\}using nearest\-fraction rounding\. Budget feasibility \(𝟏⊤​x≤k\\mathbf\{1\}^\{\\top\}x\\leq k\) is verified exactly after quantization\. If violated, the smallest nonzero coordinate is reduced until feasibility holds\.

#### Stage 6: rounding methods\.

Four rounding and selection methods are applied, each starting from the quantized fractional point or from scratch:

- •*Algorithm[1](https://arxiv.org/html/2610.00325#alg1)*\(pipage rounding\): the constructive rounding procedure from Theorem[3\.3](https://arxiv.org/html/2610.00325#S3.Thmtheorem3), which produces a deployabley∈𝒞kbiny\\in\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}from the fractional point\.
- •*Top\-kkselection*: rank theddcoordinates by their marginal returnJ⁡\(εi\)−J⁡\(𝟎\)J\(\\varepsilon\_\{i\}\)\-J\(\\mathbf\{0\}\)and select thekkhighest\.
- •*Greedy forward selection*: start withy=𝟎y=\\mathbf\{0\}and iteratively add the coordinate giving the largest return increase, breaking ties by index\. This is a sequential greedy that accounts for interaction effects\.
- •*Uniform random selection*: draw a uniformly randomkk\-subset of coordinates and repeat100100times, reporting the best return found\.

All methods use exact rational return evaluations\. Every method has an explicit return\-query limit, and all query counts are recorded\.

#### Stage 7: verification\.

The witnessed advantageΔwit=\[J⁡\(xcand\)−Jbin⋆\]\+\\Delta\_\{\\mathrm\{wit\}\}=\\left\[J\(x\_\{\\rm cand\}\)\-J\_\{\\mathrm\{bin\}\}^\{\\star\}\\right\]\_\{\+\}is computed using the main\-text definition, wherexcandx\_\{\\rm cand\}is the quantized fractional candidate andJbin⋆J\_\{\\mathrm\{bin\}\}^\{\\star\}is the enumerated binary optimum\. The certificate inequalityΔwit≤ℬBell\\Delta\_\{\\mathrm\{wit\}\}\\leq\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}is verified exactly\. Algorithm[1](https://arxiv.org/html/2610.00325#alg1)achieves the exact binary optimum in every case\.

### D\.4Calibration records

Table[2](https://arxiv.org/html/2610.00325#A4.T2)reports one case per domain at common factor levels\. The values ofτ^\\widehat\{\\tau\},β^\\widehat\{\\beta\},ℬBell\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}, andΔwit\\Delta\_\{\\mathrm\{wit\}\}are exact rationals reported to four significant digits\.

Table 2:One case per domain atd=S=8d=S=8,k=2k=2,γ=1/2\\gamma=1/2, mixed edits, repair scale3/53/5, and a strong baseline\. Each case has\|𝒞kbin\|=37\|\\mathcal\{C\}\_\{k\}^\{\\mathrm\{bin\}\}\|=37\.
### D\.5Environment

All experiments ran on a single workstation with an Intel Core i9 processor and 64 GiB RAM, using Python 3\.12 and fractions\.Fraction for exact rational arithmetic\. SciPy 1\.14 provided the SLSQP solver\. Memory was measured by the peak resident set size of the Python process\. No GPU was used\.

### D\.6Domain generators

Each domain generator takes a seed, state countS=dS=d, and an edit type \(transition\-only, reward\-only, or mixed\) and outputs a rational MDP satisfying Assumption[2\.1](https://arxiv.org/html/2610.00325#S2.Thmtheorem1):

- •Gridworld: cyclic nearest\-neighbour transitions on a one\-dimensional ring\. Repair rows redirect to a distant target\.
- •Queue: birth–death chain with load\-dependent service\. Repair rows increase the service rate\.
- •Maintenance: deterioration chain with repair actions that reset to a better state\.
- •Garnet: random sparse transition matrices drawn from a Dirichlet distribution\[[3](https://arxiv.org/html/2610.00325#bib.bib6)\]\. Repair rows replace one action with an independently drawn row\.

The companion code artifact contains the full generator source\.

### D\.7Runtime breakdown

Across all144144cases, the Bellman solves take23\.5​s23\.5\\,\\mathrm\{s\}, the interval calculation takes15\.8​s15\.8\\,\\mathrm\{s\}, and binary enumeration takes39\.1​s39\.1\\,\\mathrm\{s\}\. Model construction takes less than0\.2​s0\.2\\,\\mathrm\{s\}in total\. The complete sweep, including the fractional search and four rounding methods, takes519​s519\\,\\mathrm\{s\}\. Certification costs more than enumeration atd=6d=6andd=8d=8\. Enumeration is the larger term atd=10d=10, reflecting its combinatorial growth\(dk\)\\binom\{d\}\{k\}\.

### D\.8Exact\-zero affine construction

The exact\-zero examples use a separate affine construction designed so thatJ⁡\(x\)J\(x\)has no curvature and the certificate is provably zero\.

#### Construction\.

Rowiisends massε=1/10\\varepsilon=1/10to every state and sends the remaining mass1−S​ε1\-S\\varepsilonto itself\. The two actions have identical transition rows:P0i⋅=P1i⋅P^\{0\}\_\{i\\cdot\}=P^\{1\}\_\{i\\cdot\}for every editable rowii\. The proposed action increases only the reward:ri1\>ri0r^\{1\}\_\{i\}\>r^\{0\}\_\{i\}\. SinceP0=P1P^\{0\}=P^\{1\}, the policy\-induced transition matrixP\(x\)=\(1−xi\)Pi⋅0\+xiPi⋅1=Pi⋅0P\(x\)=\(1\-x\_\{i\}\)P^\{0\}\_\{i\\cdot\}\+x\_\{i\}P^\{1\}\_\{i\\cdot\}=P^\{0\}\_\{i\\cdot\}is independent ofxx\. Therefore the resolvent\(I−γ​P​\(x\)\)−1\(I\-\\gamma P\(x\)\)^\{\-1\}is constant andJ⁡\(x\)J\(x\)is affine inxx\.

#### Consequence for the certificate\.

An affine function has zero second derivatives everywhere:

∇2J​\(x\)=0for all​x∈\[0,1\]d\.\\nabla^\{2\}J\(x\)=0\\quad\\text\{for all \}x\\in\[0,1\]^\{d\}\.Thereforeβ=0\\beta=0\. Moreover, each directional derivative along a coordinate\-increasing direction is constant and nonnegative \(the proposed action increases reward\), soτ=0\\tau=0\. The interval propagation inherits this:τ^=β^=0\\widehat\{\\tau\}=\\widehat\{\\beta\}=0, henceℬBell=0\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}=0\.

#### Verification\.

All twelve combinations ofd∈\{4,6,8,10\}d\\in\\\{4,6,8,10\\\}andγ∈\{12,45,910\}\\gamma\\in\\\{\\frac\{1\}\{2\},\\frac\{4\}\{5\},\\frac\{9\}\{10\}\\\}giveτ^=β^=ℬBell=0\\widehat\{\\tau\}=\\widehat\{\\beta\}=\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}=0\. Enumeration confirms that the continuous and binary optima have the same exact return: the affine maximum on𝒞k\\mathcal\{C\}\_\{k\}is attained at a vertex, soGap⁡\(𝒞k\)=0\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\)=0\. This validates that the interval propagation correctly identifies zero\-curvature instances\.

### D\.9Mechanistic active\-family study

We use the family in Proposition[4\.1](https://arxiv.org/html/2610.00325#S4.Thmtheorem1)\. The dimensions arem∈\{4,8,16,32,64\}m\\in\\\{4,8,16,32,64\\\}; the discount factors areγ∈\{0\.2,0\.5,0\.8,0\.95\}\\gamma\\in\\\{0\.2,0\.5,0\.8,0\.95\\\}\. These give 20 deterministic cases\. We retain the dummy coordinate, sod=m\+1d=m\+1andk=m/2k=m/2\. The initial candidate hasxi=1/2x\_\{i\}=1/2on themmbad rows and zero at the dummy\. No optimizer or random seed is used\. Every trajectory has exactlym/2m/2exchanges and reaches a binary optimum\.

The new verification script evaluates every chosen endpoint in exact rational arithmetic, checks the resulting loss against the closed\-form gap, and independently integrates the rational second derivative against the interpolation kernel\. It also computes reliable upper sums on 16, 64, and 256 uniform subintervals; all sums dominate the exact integral and decrease under refinement\. All 20 cases and 248 executed exchanges pass\. The script additionally checks 1,325 dimension\-budget combinations and 27 polynomial instances of the kernel identity\.

Table 3:Recomputed mechanistic ratios toGap⁡\(𝒞k\)\\operatorname\{Gap\}\(\\mathcal\{C\}\_\{k\}\), shown atm=4m=4\. Only theBunifB\_\{\\mathrm\{unif\}\}ratio depends onmm;B256B\_\{256\}uses reliable 256\-subinterval upper sums\.For every testedmm,Bunif/Bcand=\(m\+2\)/\(m\+1\)B\_\{\\mathrm\{unif\}\}/B\_\{\\mathrm\{cand\}\}=\(m\+2\)/\(m\+1\), whereasℬBell/Bcand=2\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}/B\_\{\\mathrm\{cand\}\}=2\. Thus the new uniform ratio has a mild dimension dependence, while the other ratios in Table[3](https://arxiv.org/html/2610.00325#A4.T3)are unchanged across the tested dimensions\. The weighted calculation is exact on this family even at long horizons\.

### D\.10Structured active suite

The original 144\-case calibration grid is intentionally broad but produces mostly vertex candidates\. To test nontrivial rounding under structured dynamics, we freeze a separate active\-geometry grid before evaluation\. It uses four domains \(gridworld,queue,maintenance, andgarnet\),d∈\{6,8,10\}d\\in\\\{6,8,10\\\},γ∈\{1/2,4/5\}\\gamma\\in\\\{1/2,4/5\\\}, two budgets, and three fixed holdout seeds, giving4×3×2×2×3=1444\\times 3\\times 2\\times 2\\times 3=144cases\.

Starting from each domain’s baseline dynamics and rewards, each editable baseline row receives a seeded persistence coefficientλi∈\{0\.55,0\.60,0\.65\}\\lambda\_\{i\}\\in\\\{0\.55,0\.60,0\.65\\\}\. The repair endpoint redirects a seeded fractionsi∈\{0\.45,0\.50,0\.55\}s\_\{i\}\\in\\\{0\.45,0\.50,0\.55\\\}toward a fixed favorable state chosen by the domain semantics\. The initial distribution is uniform\. Persistence creates repeated visits and diminishing returns, while the common favorable region induces competition among repairs\. No case is selected or discarded based on its outcome\.

The continuous search is completed before the exact binary optimum is computed, unlike the original runner, the binary optimum is never used as a continuous\-optimizer start\. A raw coordinate is classified as fractional when it lies in\(10−6,1−10−6\)\(10^\{\-6\},1\-10^\{\-6\}\)\. The candidate is then quantized to a feasible rational point\. The maximum coordinate change from quantization is1\.27×10−91\.27\\times 10^\{\-9\}\.

Of the 144 cases, 139 are active after continuous search\. All 139 have strictly positive witnessed advantage over the exact binary optimum\. The median active candidate has four fractional coordinates, fractional mass∑imin⁡\{xi,1−xi\}=1\.00\\sum\_\{i\}\\min\\\{x\_\{i\},1\-x\_\{i\}\\\}=1\.00, and three pairwise exchanges\. The maximum exchange count is nine\. Domain\-level active counts are 35/36 forgridworld, 36/36 forqueue, 36/36 formaintenance, and 32/36 forgarnet\. By editable dimension, the active counts ford=6,8,10d=6,8,10are 44/48, 47/48, and 48/48, with median fractional\-coordinate counts 3, 4, 5 and median exchange counts 2, 3, 4, respectively\.

All exact certificate and rounding checks pass\. Algorithm[1](https://arxiv.org/html/2610.00325#alg1)reaches the exact binary optimum in 119/144 cases, or 114/139 active cases\. The 25 active non\-optimal rounded policies have median binary\-optimality gap approximately 0\.017 and maximum approximately 0\.064\.

#### Deployment baselines\.

We compare Algorithm 1 with the three simple deployment rules defined in Section D\.3\. For each method we report the fraction of active cases that attain the exact binary optimum, the mean normalized binary\-optimality gap

Jbin⋆−J⁡\(y\)Jbin⋆−J⁡\(0\),\\frac\{J^\{\\star\}\_\{\\rm bin\}\-J\(y\)\}\{J^\{\\star\}\_\{\\rm bin\}\-J\(0\)\},and the median number of exact return evaluations\. Random selection reports the best of 100 uniformly sampled feasiblekk\-subsets\.

Table 4:Deployment baselines on the 139 active structured cases\. Gap is the mean normalized binary\-optimality gap and Queries is the median number of return evaluations\.Greedy attains the binary optimum most often, but at substantially higher query cost\. Algorithm 1 has nearly the same mean normalized optimality gap while using fewer than one quarter as many median return evaluations\. Relative to the cheaper top\-kkheuristic, Algorithm 1 more than halves the number of non\-optimal deployments and reduces the mean normalized gap by over an order of magnitude\. The table measures deployment quality only\. Unlike the three heuristics, Algorithm 1 is coupled to the pre\-rounding certificate of Theorem 3\.3 and Proposition 3\.4\.

### D\.11Tightness and deployment diagnostics

For each active structured case, let

Lrnd:=\[J⁡\(xcand\)−J⁡\(y\)\]\+L\_\{\\rm rnd\}:=\\left\[J\(x\_\{\\rm cand\}\)\-J\(y\)\\right\]\_\{\+\}be the realized rounding loss\. In addition to the model\-onlyℬBell\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}and the candidate\-specific pre\-rounding certificateBcandB\_\{\\mathrm\{cand\}\}, we record the post\-trace pair\-specific audit bound

Btrace:=∑iΔi​τ^i\+12​∑tβ^it​jt​\(−at\)​bt\.B\_\{\\rm trace\}:=\\sum\_\{i\}\\Delta\_\{i\}\\widehat\{\\tau\}\_\{i\}\+\\frac\{1\}\{2\}\\sum\_\{t\}\\widehat\{\\beta\}\_\{i\_\{t\}j\_\{t\}\}\(\-a\_\{t\}\)b\_\{t\}\.The proof of Proposition[3\.4](https://arxiv.org/html/2610.00325#S3.Thmtheorem4)gives

Lrnd≤Btrace≤Bcand≤ℬBell\.L\_\{\\rm rnd\}\\leq B\_\{\\rm trace\}\\leq B\_\{\\mathrm\{cand\}\}\\leq\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}\.All 139 active cases satisfy this recorded hierarchy exactly\. The revised theorem additionally placesBunifB\_\{\\mathrm\{unif\}\}betweenBcandB\_\{\\mathrm\{cand\}\}andℬBell\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}, but its per\-instance values and coverage are not reported here\.

The median ratios to realized loss are

med⁡ℬBellLrnd=70\.8,med⁡BcandLrnd=12\.1,med⁡BtraceLrnd=9\.20\.\\operatorname\{med\}\\frac\{\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}\}\{L\_\{\\rm rnd\}\}=70\.8,\\qquad\\operatorname\{med\}\\frac\{B\_\{\\mathrm\{cand\}\}\}\{L\_\{\\rm rnd\}\}=12\.1,\\qquad\\operatorname\{med\}\\frac\{B\_\{\\rm trace\}\}\{L\_\{\\rm rnd\}\}=9\.20\.The median shrinkageℬBell/Bcand\\mathcal\{B\}\_\{\\mathrm\{Bell\}\}/B\_\{\\mathrm\{cand\}\}is 6\.33\. Candidate geometry reduces the exchange\-count and support slack, while the remaining gap is consistent with the global\-versus\-local curvature mismatch of Section[4](https://arxiv.org/html/2610.00325#S4)\.

For deployment, defineMB​\(x\)=J⁡\(x\)−B−J⁡\(0\)M\_\{B\}\(x\)=J\(x\)\-B\-J\(0\)\. A positive margin certifies that the rounded deployable policy improves over the baseline\. Table[5](https://arxiv.org/html/2610.00325#A4.T5)includes the post\-trace audit in addition to the two pre\-rounding certificates\.

Table 5:Deployment\-improvement coverage on the 139 active structured cases\. Direct is inferred from the existing exact\-return records\.Coverage is 48\.2% for the legacy bound, 74\.1% for the candidate bound, and 87\.8% for the post\-trace audit\. Atγ=4/5\\gamma=4/5, the corresponding counts are 0/71, 35/71, and 54/71\. All 139 rounded policies actually improve over the baseline\. A nonpositive certified margin is therefore an abstention event in this suite\.

### D\.12Direct verification baseline

#### Protocol\.

The new experiment reruns the 20 closed\-form cases in Appendix[D\.9](https://arxiv.org/html/2610.00325#A4.SS9)\. Both methods receive the same candidate, baseline return, and candidate return, and use the same deterministic pair and endpoint selection\. The pre\-rounding tests evaluateJ⁡\(x\)−B−J⁡\(0\)\>0J\(x\)\-B\-J\(0\)\>0forB∈\{ℬBell,Bunif,Bcand\}B\\in\\\{\\mathcal\{B\}\_\{\\mathrm\{Bell\}\},B\_\{\\mathrm\{unif\}\},B\_\{\\mathrm\{cand\}\}\\\}before any exchange\. All candidates are then rounded, including those not certified, so both tests refer to the same output\. The direct test uses its cached exact return to checkJ⁡\(y\)\>J⁡\(0\)J\(y\)\>J\(0\)\. All arithmetic and comparisons use rational numbers\.

#### Coverage and accounting\.

Atγ=0\.2\\gamma=0\.2, all three pre\-rounding bounds certify all five dimensions\. Atγ=0\.5\\gamma=0\.5, only the budget\-aware and candidate bounds certify them\. Atγ=0\.8\\gamma=0\.8and0\.950\.95, none of these three bounds certifies an instance\. Direct verification certifies all 20 outputs\. There are 40 shared setup evaluations for candidate and baseline returns, followed by 496 endpoint evaluations across 248 exchanges\. Direct verification uses the retained selected\-endpoint values and adds no return evaluations\. Certificate values are computed from the family’s closed forms\. In a general run with no exchange and no cached output return, a final policy evaluation may be needed\.

#### Dominance under exact evaluation\.

The rounding guarantee givesJ⁡\(y\)≥J⁡\(x\)−BJ\(y\)\\geq J\(x\)\-B\. SubtractingJ⁡\(0\)J\(0\)shows that the direct margin dominates the certified margin\. Therefore, a positive certified margin implies a positive direct margin\. This observation applies to any sound candidate\-level loss bound for the same output, including a post\-trace bound\. The pre\-rounding guarantee is available beforeyyis constructed\. Under validated interval arithmetic, confirming a positive direct margin may require refining return enclosures\. Zero additional evaluation cost is established here for the exact\-rational runs with cached endpoint returns\.

#### Structured\-suite inference\.

The original records reportJ⁡\(y\)\>J⁡\(0\)J\(y\)\>J\(0\)under exact arithmetic in all 139 active cases\. These records imply direct\-verification coverage of 139/139, including 68/68 atγ=1/2\\gamma=1/2and 71/71 atγ=4/5\\gamma=4/5\. The table’s Direct column reinterprets those recorded returns as a verification baseline using the original experiment records\. Structured\-suite coverage is reported for the legacy, candidate, and trace bounds\.

### D\.13Scaling and validated arithmetic

The scaling experiment uses a sparse ring MDP withSSstates and only the firstddrows editable\. Transition probabilities are dyadic, so the binary64 model input is represented exactly\. Axis A usesS=d∈\{16,32,64,128\}S=d\\in\\\{16,32,64,128\\\}\. Axis B fixesd=16d=16and usesS∈\{64,128,256\}S\\in\\\{64,128,256\\\}, directly testing thed≪Sd\\ll Sregime\. Each configuration uses three fixed seeds\. Large cases omit binary enumeration\.

Validated floating point first solves the Bellman systems in binary64, then applies outward residual corrections until every Bellman inequality is satisfied\. All subsequent interval operations are also rounded outward\. Memory is measured in an independent process for each run to avoid inherited high\-water marks\. Table[6](https://arxiv.org/html/2610.00325#A4.T6)reports median runtime and peak resident\-set size\.

Table 6:Validated\-certification scaling\. Times are medians over three fixed seeds\. RSS is measured in independent processes\.For numerical auditing we use six small cases with\(S,d\)∈\{\(8,8\),\(16,16\)\}\(S,d\)\\in\\\{\(8,8\),\(16,16\)\\\}\. Each binary64 validated envelope is reinterpreted as an exact dyadic rational, and every Bellman inequality is then rechecked with exact arithmetic\. All 6/6 validated cases pass this audit\. Recomputing the interval primitives from the same endpoints using exact Fraction arithmetic also confirms outward containment of the validated certificate in all 6/6 cases\. In contrast, the corresponding naive midpoint\-FP64 solutions pass the exact Bellman audit in 0/6 cases even though their printed certificate values are numerically close to the validated values\. AtS=d=16S=d=16, the validated implementation is approximately14\.8×14\.8\\timesfaster than the existing exact\-rational envelope\-and\-certificate pipeline\.

### D\.14General exchange study and complete costs

#### New instances\.

This suite is separate from the original structured suite\. We evaluate the full Cartesian product of two transition structures,d∈\{6,8\}d\\in\\\{6,8\\\},γ∈\{1/2,4/5,19/20\}\\gamma\\in\\\{1/2,4/5,19/20\\\}, and seeds 11 and 29, giving 24 instances\. Each hasS=d\+1S=d\+1states and budgetk=d/2k=d/2\. The last state is an absorbing target with reward one\. A baseline bad\-state row puts a seeded fraction between72/10072/100and90/10090/100on itself and the remainder on one other bad state\. That successor follows a ring or is randomly selected\. The proposed row redirects a seeded fraction between40/10040/100and65/10065/100of its baseline transition mass to the target\. Baseline bad\-state rewards belong to\{0,1/100,2/100,3/100\}\\\{0,1/100,2/100,3/100\\\}, and proposed reward changes belong to\{0,−1/100,−2/100,−3/100\}\\\{0,\-1/100,\-2/100,\-3/100\\\}\. The initial distribution is uniform over bad states\. The off\-diagonal transitions couple the editable rows\. All configurations are retained\. This suite is synthetic and designed to exercise fractional rounding\.

#### Candidates and exact references\.

Continuous search uses SLSQP with analytic gradients, three deterministic starts, tolerance10−1010^\{\-10\}, and at most 150 iterations per start\. No binary optimum is supplied to the search\. Coordinates are rounded to denominator10610^\{6\}and any excess budget is removed in index order\. Every resulting candidate has strictly positive return advantage over the exactly enumerated binary optimum\. All subsequent returns, Bellman envelopes, endpoint choices, low\-rank updates, and integral enclosures use rational arithmetic\. Every one of the 135 exchanges is checked against direct policy evaluation at both endpoints and an interior point\. All rounded outputs and returns agree between the full\-solve and rank\-two implementations\.

#### Integral refinement and independent audit\.

The refinement target isU−L≤0\.05​U\+10−12U\-L\\leq 0\.05U\+10^\{\-12\}with a cap of 64 cells per exchange\. The target holds on every executed exchange, with 2,003 cells in total\. This tolerance concerns the curvature integral, not its ratio to actual rounding loss\. The standalone method usesBlocB\_\{\\mathrm\{loc\}\}and no global envelopes\. The hybrid method also computes global Bellman bounds and clips each integral charge as defined in Appendix[B\.7](https://arxiv.org/html/2610.00325#A2.SS7)\. The two bounds coincide on this suite\. All instances satisfy\[J⁡\(x\)−J⁡\(y\)\]\+≤Bhyb≤Btrace≤Bcand≤Bunif\[J\(x\)\-J\(y\)\]\_\{\+\}\\leq B\_\{\\mathrm\{hyb\}\}\\leq B\_\{\\mathrm\{trace\}\}\\leq B\_\{\\mathrm\{cand\}\}\\leq B\_\{\\mathrm\{unif\}\}\. An independent audit uses 16 exchanges in fully dense five\-state MDPs, with strictly positive rational transition endpoints and signed rewards\. At five points per exchange, direct resolvent calculations agree exactly with the rational representation for both return and second derivative, giving 80 exact checks\. No absorbing\-target structure is assumed in this audit\.

Table 7:New coupled suite\. Ratios are medians of bound divided by actual rounding loss\. Coverage counts certified baseline improvements\. Each discount has eight instances\. Local and hybrid bounds coincide here and use the trajectory\.
#### Cost accounting and baselines\.

All methods use the same exact return arithmetic\. Direct rounding solves a policy\-evaluation system for each endpoint\. Its rank\-two baseline uses the same rational exchange coefficients and resolvent updates as local integration, but omits derivative enclosures\. Candidate top\-kkselects the largest candidate coordinates\. Greedy starts from the baseline and adds the best positive\-return edit until the budget is reached or no improvement remains\. The global\-certificate pipeline adds all2​d\+22d\+2Bellman envelope problems before rank\-two rounding\. Local integration needs no global preprocessing\. Hybrid integration includes both global preprocessing and local enclosures\. Candidate\-based totals include continuous optimization, exact candidate and baseline evaluations, and all subsequent computation\. Greedy is timed from the model and does not pay for continuous optimization\. Final verification reuses evaluated returns\. Exact enumeration and independent audit evaluations are reference checks and are excluded from method runtimes\. Each small instance is run three times with numerical linear\-algebra libraries restricted to one thread\. We first take the median over repetitions for each instance, then the median across instances\.

Table 8:Complete costs on the new 24\-instance suite\. The normalized gap is\(Jbin⋆−J⁡\(y\)\)/\(Jbin⋆−J⁡\(0\)\)\(J\_\{\\rm bin\}^\{\\star\}\-J\(y\)\)/\(J\_\{\\rm bin\}^\{\\star\}\-J\(0\)\), averaged across instances\.The table quantifies the computation cost of tightening trajectory bounds\. All four rounding variants attain the same policy quality on this suite\.

#### Exact scaling checks\.

We also test the ring construction at\(S,d\)=\(16,8\),\(32,8\),\(64,16\)\(S,d\)=\(16,8\),\(32,8\),\(64,16\), with seed 11 andγ=19/20\\gamma=19/20\. Additional noneditable states retain their baseline rows\. All candidates are fractional and all exact rounding and bound checks pass\. Binary optima are not enumerated\. These timing checks use one run per configuration and are reported separately from the repeated small\-suite comparison\. Table[9](https://arxiv.org/html/2610.00325#A4.T9)includes initial inversion and all per\-exchange work in each rounding time, but excludes continuous search\. Saved results also report full end\-to\-end times\.

Table 9:Exact scaling checks\. Ratios use realized rounding loss\. Rounding times are in seconds and are single\-run measurements\.The rational implementation provides exact numerical certification\. Its runtime includes arithmetic on the accumulated numerators and denominators\.