PaperlayerView exact revision on arXiv

Source-linked AI summary

Bellman-Certified Rounding for Sparse Policy Deployment in MDPs

Zhaojun Peng

arXiv:2610.00325v1cs.LG

TL;DR

Sparse deployment requires turning continuous policy updates into a limited number of complete row changes, even though those edits interact through future visitation. The paper derives reusable Bellman-envelope guarantees and trajectory-weighted curvature bounds; candidate-specific certification improves coverage, while trajectory integration tightens long-horizon bounds.

  • Problem

    Continuous policy optimization can spread updates across many states, while sparse deployment permits only a few complete row changes whose effects are coupled through future visitation.

    Source: §1 · p. 1

  • Method

    The paper uses reusable Bellman envelopes for uniform and candidate-specific rounding guarantees, then integrates rank-two exchange curvature along the realized trajectory.

    Source: §1 · p. 1, §4 · p. 8

  • Results

    Candidate-specific bounds raise pre-rounding certification coverage from 48.2% to 74.1%, and at γ = 0.95 trajectory integration lowers the median bound-to-loss ratio from 402.3 to 2.08 on coupled instances.

    Source: §7 · p. 10

  • Takeaways & Limitations

    The approach provides reusable guarantees before deployment and tighter audits once the rounding path is known.

    Source: §7 · p. 10

    The analysis assumes a known finite discounted MDP with two actions per editable row; larger action sets, estimated models, partial observability, and average reward need new arguments.

    Source: §7 · p. 10

Abstract

from arXiv · show

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. From $2d+2$ Bellman 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 from $48.2\%$ to $74.1\%$ on the structured suite. At $\gamma=0.95$, local integration lowers the median bound-to-loss ratio from $402.3$ to $2.08$ on coupled instances.

1 Introduction

The paper studies certified conversion of continuous MDP policy updates into sparse binary deployments, where row edits interact through future visitation. It develops Bellman-based guarantees and trajectory-aware bounds for that rounding problem.

1 Introduction

  • Continuous updates distribute small changes across many states, but deployment may allow only k complete row changes, whose values do not decouple because edits alter later visits.At long horizons, global maximum curvature may overstate loss by lying far from the rounding trajectory.Source: §1 · p. 1

1.3 Contributions

  • Bellman envelopes yield uniform guarantees from 2d + 2 solves, while candidate geometry sharpens the bound without another solve and rank-two exchange structure supports weighted curvature integration.The paper also reports that rounding requires at most 2(d −1) endpoint evaluations.Source: §1 · p. 1, §1.3 · pp. 2–3

1 Introduction

  • Candidate-specific bounds raise pre-rounding certification coverage from 48.2% to 74.1% on the structured suite; rounding uses a median of six return evaluations versus 26 for greedy.The reported mean normalized optimality gaps are 0.185% for rounding and 0.178% for greedy.Source: §1 · p. 2

1.1 Illustrative example

  • The illustrative example gives an explicit continuous-to-binary loss: concave returns favor assigning x_i = 1/2 to every relevant row, while deployment selects m/2 rows.The example uses m zero-reward states and an absorbing positive-reward target.Source: §1.1 · p. 2

1.2 Related work

  • Unlike related safe-policy-improvement work focused on uncertainty and baseline improvement, this paper certifies return loss when a continuous model-based update must meet a k-row deployment constraint.The paper situates its method alongside pipage rounding and sparse or discrete optimization.Source: §1.2 · p. 2

1.3 Contributions

  • The contributions include a lower-bound family showing necessary dimension dependence and an NP-hardness result for exact global curvature computation.The experiments distinguish pre-rounding certification, final policy quality, long-horizon tightness, and computation cost.Source: §1.3 · p. 3

2 Preliminaries

The preliminaries define the finite discounted MDP and its continuous row-mixture policies, then introduce sensitivity quantities used to bound rounding loss. Certification assumes exact or validated arithmetic.

2.1 Problem setting and assumptions

  • The setup uses a finite discounted MDP with d editable rows, each interpolating between a baseline and proposed action, and a budget k on total mixture weight.The return is J(x) = µ⊤V(x), with V(x) determined by the discounted transition matrix and reward vector.Source: §2.1 · p. 3
  • Exact rational arithmetic or directed outward rounding is required for Bellman bounds, interval operations, and certified endpoint comparisons; ordinary floating-point solves with residual padding do not satisfy the assumption.The paper reports that double precision gives many zero bounds on cases where exact arithmetic gives none.Source: §2.1 · p. 3

2.2 Sensitivity identities and rounding quantities

  • The rounding analysis tracks the largest negative coordinate slope and negative pairwise exchange curvature, so coordinate increases and exchanges have bounded loss.Every coordinate derivative is at least −τ, and every exchange line has second derivative at least −β.Source: §2.2 · p. 4

3 Bellman bounds for rounding

Bellman envelopes bound policy values and occupancies across the continuous policy family, then propagate those bounds into sensitivity certificates. Budget-aware rounding converts the certificates into uniform and candidate-specific guarantees, with interval conservatism as a limitation.

3.1 Bellman envelopes; 3.2 Sensitivity certificate

  • Bellman min/max values enclose every randomized policy value and row occupancy; sensitivity intervals then certify τ ≤ bτ and β ≤ bβ.The reusable envelopes and interval quantities are constructed with 2d + 2 Bellman solves.Source: §3.1 · pp. 4–5, §3.2 · p. 5, §3.3 · p. 6

3.3 Certified rounding

  • Theorem 3.3 guarantees a deployable policy y with J(y) ≥ J(x) − Bunif for every feasible continuous candidate, and bounds the relaxation gap by Bunif.The budget coefficient satisfies cd,k ≤ k/4, and the new uniform bound is no larger than the legacy bound.Source: §3.3 · pp. 5–6
  • For a known candidate, Bcand gives J(y) ≥ J(x) − Bcand(x) and satisfies Bcand(x) ≤ Bunif, without another Bellman solve.The bound retains candidate geometry and is available before pairwise endpoint comparisons.Source: §3.3 · p. 6

3.4 Computation and interval conservatism

  • The interval calculation can overstate curvature because it treats sensitivity quantities as independent boxes, including endpoint combinations no common policy realizes.The excess width vanishes when the Bellman envelopes are tight.Source: §3.4 · p. 7

4 Dimension dependence and long-horizon conservatism

The paper shows that dimension-dependent loss bounds are necessary when the deployment budget scales with dimension, while global and segment-local curvature bounds can remain conservative at long horizons. Weighted curvature integration along the realized exchange trajectory removes this slack on the analyzed family.

Dimension dependence

  • When k = Θ(d), any budget-aware coefficient satisfying the family’s loss guarantee must grow as Ω(d).The family uses k = (d − 1)/2, with the lower bound cd ≥ (d − 1)(1 − γ)^2/[8(2 − γ)].Source: §4 · p. 7

Long-horizon conservatism

  • On the lower-bound family, the candidate-bound ratio Bcand(x⋆)/Gap(Ck) = (2 − γ)/(2δ^2) still diverges as γ approaches 1, even with tight envelopes.Here bβ = β, so interval propagation does not explain the residual slack.Source: §4 · p. 7
  • Exact segment-local curvature maxima also retain a divergent loss ratio, so local maximization alone does not remove long-horizon slack.The ratio is Bseg/Gap(Ck) = (2 − γ)(1 + δ^3)/(4δ^2).Source: §4 · p. 7

Trajectory integration

  • For γ = 0.95, weighted trajectory integration gives an exact integral ratio of 1, versus candidate and segment-maximum ratios of 210 and 105.013.Reliable 256-subinterval upper sums give a ratio of 1.044.Source: §4 · p. 7
  • Each feasible exchange has a rank-two rational representation with numerator and denominator degrees at most two, enabling computable trajectory bounds from weighted curvature integration.The resulting bound applies to general exchanges and is available during rounding; before the exchange path is known, certification still relies on Bunif or Bcand.Source: §4 · pp. 7–8

5 Complexity of exact curvature

Exact thresholding of exchange curvature is computationally hard, even in a restricted rational MDP class. The reduction from MAX-CUT establishes this boundary for curvature computation, not return maximization.

Restricted MDP class

  • B3 restricts MDPs to γ = 1/2, two actions per row, rewards in [0, 1], positive transition endpoints, and an acyclic policy-dependence graph of depth at most three.Membership in B3 is decidable in polynomial time.Source: §5 · p. 8

Hardness result

  • Thresholding the continuous-cube curvature quantity βM is NP-hard, while the binary threshold language is NP-complete.These results hold for the restricted class B3.Source: §5 · p. 8

Hardness construction

  • The reduction maps unweighted MAX-CUT to a rational B3 instance and isolates one designated exchange whose curvature encodes the graph’s cut objective.The construction preserves local exchange feasibility under budget k = n + 1.Source: §5 · p. 8

Implications

  • The hardness result concerns exact exchange-curvature thresholding rather than return maximization, so it rules out a polynomial-time thresholding alternative unless P = NP.The proof establishes NP-completeness for the binary language using a polynomial certificate and a MAX-CUT reduction.Source: §5 · p. 8

6 Evaluation

Across the evaluation, candidate-specific bounds increase pre-rounding certification coverage, and trajectory integration sharply tightens loss bounds on coupled instances. The study also reports soundness audits, rounding outcomes, and the additional cost of tighter computation.

6 Evaluation

  • Candidate geometry raises pre-rounding certification coverage from 67/139 = 48.2% to 103/139 = 74.1% on the active structured cases.The table distinguishes pre-rounding certificates from a post-trace audit and exact direct checks.Source: Table 1 · p. 9, §6 · p. 9
  • On the exact-rational grid of 144 cases, every witnessed continuous-to-binary advantage is bounded by BBell, while naive midpoint FP64 reports a false zero in 97 cases.This grid tests soundness rather than active rounding because 141 candidates are already binary.Source: §6 · p. 9
  • Across 139 active structured cases, Algorithm 1 reaches the exact binary optimum in 119; its mean normalized optimality gap is 0.185%, versus 0.178% for greedy.Median return-evaluation counts are 6 for Algorithm 1 and 26 for greedy.Source: §6 · p. 9
  • Direct verification accepts all 20 closed-form deployments, compared with 5 legacy, 10 budget-aware, and 10 candidate-bound acceptances.The exact check adds no return evaluation because the final endpoint’s return is already cached.Source: §6 · p. 9
  • At γ = 0.95, the median bound-to-loss ratio falls from 402.3 for Bcand to 2.08 for Bloc on the 24-instance coupled suite.The trajectory bound certifies improvement in all 24 cases while preserving the rounded policy.Source: §6 · p. 10
  • 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.The tighter guarantee incurs additional computation on this small synthetic suite.Source: §6 · p. 10

Scaling and validated arithmetic.

  • Full validated certification takes 4.45 s at S = d = 128 and 1.31 s at (S, d) = (256, 16).For (S, d) = (256, 16), Bellman solves account for 1.28 s and interval propagation for 0.031 s.Source: Scaling and validated arithmetic · p. 10
  • Validated intervals contain exact recomputations in all six audited reference cases, while naive FP64 passes the Bellman audit in none.At S = d = 16, the validated implementation is about 14.8× faster than the existing exact-rational pipeline; the audit covers only small reference cases.Source: Scaling and validated arithmetic · p. 10

7 Conclusion

The conclusion frames sparse deployment as a coupled policy problem and separates reusable pre-rounding guarantees from tighter trajectory audits. Its claims are scoped to known finite discounted MDPs with two actions per editable row.

Conclusion

  • Bellman envelopes control policy-dependent visitation uniformly, while budget and candidate geometry sharpen guarantees available before rounding.A rank-two representation supports weighted curvature integration on the realized exchange path.Source: §7 · p. 10
  • On the structured suite, candidate geometry raises pre-rounding certification coverage from 48.2% to 74.1%; at γ = 0.95, trajectory integration lowers the coupled-instance median ratio from 402.3 to 2.08.These results distinguish reusable pre-deployment guarantees from tighter audits once the rounding path is known.Source: §7 · p. 10

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.The paper also identifies open questions on universal dimension constants, continuous-curvature thresholding, and validated trajectory-bound implementations.Source: §7 · p. 10

A Proofs for Section 3

The proof rounds a feasible fractional point by first reaching an integer-sum point, then making feasible exchanges until the policy is binary. Potential-based accounting bounds the return loss, with candidate-specific and uniform versions.

Phase 1

  • The monotone Phase-1 fill raises the coordinate sum to an integer while losing at most τ in return.The fill adds mass η = ⌈1⊤x⌉ − 1⊤x, with η < 1.Source: A Proofs for Section 3 · p. 14

One exchange

  • Each exchange chooses an endpoint that loses at most β(−a)b/2, no more than β/8, and makes at least one coordinate integral.The bound follows from convexity of g(t) + βt^2/2 on the feasible exchange interval.Source: A Proofs for Section 3 · pp. 14–15

Potential accounting

  • The exchange potential decreases by 2(−a)b, so telescoping bounds accumulated Phase-2 loss by βΦ(z)/4.The fractional support shrinks until the policy is binary, in at most d − 1 exchanges.Source: A Proofs for Section 3 · p. 15

Budget-aware and candidate-specific bounds

  • The model-only bound is τ + c_d,kβ, while the candidate-specific bound charges fill-path gradients and curvature on the realized fractional support.The candidate-specific bound is no larger than the uniform bound, which is no larger than the legacy Bellman bound.Source: A Proofs for Section 3 · p. 15

B Proof of Proposition 4.1

This proof develops an m-independent continuous-to-binary gap and weighted exchange bounds, then uses a depth-three transition-edit graph in a MAX-CUT reduction. It shows that cut-polynomial maximizers are complementary and that a designated row pair strictly maximizes exchange curvature, with that maximum attainable under the reduction’s row budget.

B.3 Continuous and binary optima

  • The continuous optimum spreads the budget equally across bad rows, while a binary optimum repairs any m/2 rows; their gap is independent of m.The construction includes a dummy editable coordinate that does not affect return, so the continuous optimum leaves it at zero and uses the full budget on bad rows.Source: §B.3 · p. 16

B.4 Interval certificate computation

  • The interval certificate gives bτ = τ = 0 and zero cross-Hessian intervals for distinct bad rows, yielding Proposition 4.1’s exchange certificate.The passage attributes the zero cross-Hessian to distinct bad rows having no transition coupling.Source: §B.4 · p. 17

B.5 Certificate and ratio

  • At m = 4 and γ = 1/2, bβ = 2, BBell = 1, and Gap(Ck) = 1/6; at fixed γ, the gap remains Θ(BBell) as m grows.Thus no sound bound of the form τ + cβ can use a dimension-independent c on this family.Source: §B.5 · p. 18

B.6 Weighted exchange interpolation

  • Weighted exchange integration gives Bint = γ2/[2δ(2 −γ)] = Gap(Ck), and endpoint curvature bounds on subintervals provide reliable upper sums.On this family, the interpolation identity is exact for actual loss because g′′ < 0 and the exchange endpoints have equal return.Source: §B.6 · p. 19

B.7 General exchange computation

  • Each exchange return has a rank-two rational representation with degree-at-most-two numerator and denominator, and the trajectory bounds satisfy Bhyb ≤ Btrace ≤ Bcand ≤ Bunif.The exchange curvature is g′′ = h/q3 with deg h ≤ 3; no ordering between Bloc and Bcand is required.Source: §B.7 · pp. 19–20

C.1 MDP construction

  • The MAX-CUT proof constructs a restricted MDP with γ = 1/2 and a transition-edit graph of depth at most three.Its construction uses a padded graph and establishes valid stochastic transitions and bounded rewards.Source: C Proof of Theorem 5.2 · p. 20, §C.1 · pp. 20–21

C.2 Resolvent and reduced objects

  • The rank-one baseline transition matrix yields a closed-form resolvent, reducing the performance identity to objects C, a, and u.Depth three makes the Neumann inverse for the reduced objective truncate after the cubic term.Source: §C.2 · pp. 21–22, §C.3 · p. 22

C.3 Expansion of the objective; C.4 Maximizing the cut polynomial

  • The reduced objective is multi-affine, and the proof identifies a designated exchange Hessian before showing every vertex maximizer of the cut polynomial is complementary.Complementarity means r_i = 1 −ℓ_i for every i.Source: §C.3 · p. 22, §C.4 · p. 23

C.4 Maximizing the cut polynomial

  • Every cut-polynomial maximizer is complementary: its value is at least Λn − m, exceeding the non-complementary bound Λn − m − 1.A complementary assignment encodes a graph partition, and cutG(S) ≥ 0; the positive part in κ does not alter the supremum.Source: §C.4 · p. 23

C.5 Bounds for all row pairs

  • The designated pair (p, q) strictly realizes the all-pairs maximum β, while each undesignated pair type has a bound below 9M/4, 17M/4, or 4M.The bounds are 4M for (p, Li)/(p, Rj), 17M/4 for (q, Li)/(q, Rj), and 9M/4 for (Li, Rj).Source: §C.5 · pp. 24–25

C.6 Feasibility under a row budget

  • The designated curvature maximum is attainable under the row budget in the reduction image: a feasible fractional exchange and a complementary binary witness both fit the budget.The exchange preserves total mass, while the binary witness uses mass n ≤ k = n + 1; the bridge is specific to the reduction image.Source: §C.6 · pp. 25–26

C.7 Reduction and encoding size

The reduction connects MAX-CUT to curvature-threshold decision problems while retaining polynomial encoding size. The evaluation protocol uses exact rational checks for certificates and optima, with heuristic search supplying continuous candidates.

C.7 Reduction and encoding size

  • The constructed dense MDP has N = 2n + 3 states and O(N^2) rational entries, each with O(log N) bits, so its encoding size is polynomial in n.The reduction recomputes its parameters from the padded graph.Source: §C.7 · p. 26
  • The binary threshold language is NP-complete: a pair of rows and a binary control vector form a polynomially verifiable certificate, and the reduction establishes NP-hardness.The verification uses exact rational arithmetic.Source: §C.7 · p. 26
  • The reduction image has a continuous maximum attained at binary graph controls, proving continuous NP-hardness.The equivalence chain adds the padding constant and scales by a positive factor before applying the threshold condition.Source: §C.7 · p. 26

D Evaluation protocol

  • Evaluation records use the legacy Bellman bound unless otherwise marked, and the structured-suite coverage and scaling-time baselines are retained.The revised uniform bound is evaluated on the closed-form and coupled suites.Source: D Evaluation protocol · p. 27

D.1 Arithmetic discipline

  • Exact rational arithmetic checks model entries, returns, and certificates, while continuous multistart search supplies feasible candidates that are rationalized before exact evaluation.The large-scale study instead uses outward-rounded binary64 arithmetic with corrected Bellman inequalities and outward-rounded interval operations.Source: §D.1 · p. 27

D.2 Grid specification

The evaluation spans a deterministic grid of MDP cases and applies certificate computation, binary enumeration, and several rounding methods. It also checks exact-zero behavior and a mechanistic family, while reporting computational costs.

D.2 Grid specification

  • The grid contains 144 cases crossing four domains, three dimensions, two budgets, two discounts, and three edit types.Case identifiers and random seeds are deterministic functions of the grid indices.Source: §D.2 · p. 27

D.3 Per-case execution sequence

  • Each case computes Bellman envelopes and interval certificates, enumerates the binary optimum, and applies pipage, top-k, greedy, and random selection; pipage reaches the exact binary optimum in every case.The fractional candidate comes from multistart SLSQP and is rationalized before exact evaluation.Source: §D.3 · pp. 27–28

D.4 Calibration records

  • Table 2 records exact rational bτ, bβ, BBell, and witnessed advantage values for one case per domain at d = S = 8, k = 2, and γ = 1/2.The cases use mixed edits, repair scale 3/5, a strong baseline, and 37 feasible binary vectors each.Source: Table 2 · p. 29, §D.4 · p. 29

D.5 Environment

  • Experiments ran on one Intel Core i9 workstation with 64 GiB RAM, using Python 3.12 and SciPy 1.14, with no GPU.Exact rational calculations used fractions.Fraction.Source: §D.5 · p. 29

D.6 Domain generators

  • The four generators model a cyclic gridworld, birth–death queue, deterioration-and-repair maintenance chain, and random sparse Garnet transitions.Garnet transition matrices are drawn from a Dirichlet distribution.Source: §D.6 · p. 29

D.7 Runtime breakdown

  • Across all 144 cases, the full sweep takes 519 s; enumeration becomes the larger cost at d = 10, after certification costs more at d = 6 and d = 8.Bellman solves take 23.5 s, interval calculation 15.8 s, and binary enumeration 39.1 s.Source: §D.7 · p. 29

D.8 Exact-zero affine construction

  • All twelve exact-zero cases have bτ = bβ = BBell = 0, and enumeration confirms equal continuous and binary optimum returns.The affine maximum on Ck is attained at a vertex.Source: §D.8 · p. 30

D.9 Mechanistic active-family study

  • On the mechanistic family, weighted calculation is exact even at long horizons, while the new uniform-to-candidate ratio has only mild dimension dependence.For every tested m, Bunif/Bcand = (m + 2)/(m + 1), whereas BBell/Bcand = 2.Source: §D.9 · p. 30

D.10 Structured active suite

A separately frozen active-geometry suite tests rounding on structured dynamics with genuinely fractional candidates. Algorithm 1 has deployment-quality advantages over simple heuristics, while often reaching the exact binary optimum.

Suite construction

  • The separate active-geometry grid contains 144 cases across four domains, three editable dimensions, two discounts, two budgets, and three fixed holdout seeds.Persistence creates repeated visits and diminishing returns, while a common favorable region induces competition among repairs.Source: §D.10 · pp. 30–31

Candidate protocol

  • Candidates are searched before computing the exact binary optimum, then quantized to feasible rational points with maximum coordinate change 1.27 × 10^-9.The binary optimum is not used to initialize the continuous optimizer.Source: §D.10 · p. 31

Active candidates

  • Of 144 cases, 139 are active; the median active candidate has four fractional coordinates and requires three pairwise exchanges.Active counts range from 32/36 to 36/36 by domain, and from 44/48 to 48/48 by editable dimension.Source: §D.10 · p. 31

Rounding outcomes

  • Algorithm 1 reaches the exact binary optimum in 119 of 144 cases, including 114 of 139 active cases; the remaining active policies have median gap approximately 0.017.The maximum binary-optimality gap among the 25 active non-optimal policies is approximately 0.064.Source: §D.10 · p. 31

Deployment baselines

  • Algorithm 1 nearly matches greedy’s mean normalized optimality gap with fewer than one quarter as many median return evaluations, and beats top-k on both reported quality measures.It more than halves non-optimal deployments and reduces the mean normalized gap by over an order of magnitude relative to top-k.Source: §D.10 · p. 31

D.11 Tightness and deployment diagnostics

The diagnostics compare pre-rounding certificates, direct verification, validated scaling, and trajectory-based bounds across several suites. Candidate-specific and trace bounds improve certification coverage or tightness, while exact checks support the reported numerical guarantees.

D.11 Tightness and deployment diagnostics

  • Coverage on the 139 active cases is 48.2% for the legacy bound, 74.1% for the candidate bound, and 87.8% for the post-trace audit; all rounded policies improve over baseline.At γ = 4/5, the corresponding counts are 0/71, 35/71, and 54/71, so uncovered cases are abstentions in this suite.Source: §D.11 · p. 32, Table 5 · p. 32

D.12 Direct verification baseline

  • Direct verification certifies all 20 closed-form outputs, reusing selected-endpoint returns without extra evaluations; the structured-suite records imply 139/139 direct acceptances.In a general run without an exchange or cached output return, a final policy evaluation may be needed.Source: §D.12 · p. 33

D.13 Scaling and validated arithmetic

  • Validated arithmetic passes exact audits in 6/6 cases, while naive midpoint-FP64 solutions pass in 0/6; at S = d = 16 it is approximately 14.8× faster than the exact-rational pipeline.The validated procedure applies outward residual corrections until every Bellman inequality is satisfied.Source: §D.13 · pp. 33–34, Table 6 · p. 33

D.14 General exchange study and complete costs

  • The 24-instance study uses exact rational arithmetic for candidate evaluation, exchange updates, and integral enclosures, and checks every exchange at both endpoints and an interior point.The ring scaling checks use fractional candidates and report single-run rounding times, excluding continuous search.Source: §D.14 · pp. 34–35, Table 9 · p. 35
  • On the new 24-instance coupled suite, all instances satisfy [J(x) − J(y)]+ ≤ Bhyb ≤ Btrace ≤ Bcand ≤ Bunif, and all four rounding variants attain the same policy quality.The table quantifies computation costs of tightening trajectory bounds; its comparisons use the same policy quality.Source: §D.14 · pp. 34–35, Table 7 · p. 34
  • An independent audit checks the rational return and second-derivative representation at five points on each of 16 dense-MDP exchanges, yielding 80 exact checks.The audit assumes no absorbing-target structure.Source: §D.14 · p. 34
Loading 2610.00325v1…