PaperlayerView exact revision on arXiv

Source-linked AI summary

A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes

Fredy Pokou

arXiv:2609.18610v1cs.LGmath.OC

TL;DR

Reconstructing an already optimal policy from black-box queries raises the question of what representation determines the information and complexity required. The paper develops a geometric framework based on policy-induced decision boundaries, finding that under structural regularity, reconstruction complexity is governed by boundary geometry rather than ambient state-space size.

  • Problem

    For black-box reconstruction of an already optimal policy, the full value function or policy representation may encode more information than the task requires.

    Source: §1 · p. 1

  • Method

    The paper formulates policy reconstruction as geometric inference from decision-boundary geometry and develops complexity measures, compression results, and boundary-estimation guarantees.

    Source: §9 · p. 61

  • Results

    Under structural regularity, policy complexity is governed by decision-boundary geometry rather than state-space cardinality, and structured policies can have more compact geometric than value-based representations.

    Source: §4.7 · p. 21, §6.8 · p. 36

  • Takeaways & Limitations

    Boundary geometry provides a common representation for policy reconstruction, estimation, oracle-query allocation, and information-theoretic compression.

    Source: §9 · p. 61

    Decision compression is not universal; it depends on structural regularities such as monotonicity, convexity, or bounded fragmentation.

    Source: §6.7 · p. 35

Abstract

from arXiv · show

Classical dynamic programming represents optimal sequential decisions through value functions and policies. While this functional representation is natural for computing optimal decisions, it does not directly identify the mathematical object governing policy reconstruction, representation complexity, or oracle-query complexity once an optimal policy is fixed. This paper addresses this question by developing a geometric theory of structured optimal policies in which the decision-boundary geometry induced by the policy becomes the primary object of analysis. We show that, under suitable structural regularity conditions, this geometry provides the minimal representation required for policy reconstruction and determines the statistical and computational complexity of the reconstruction problem. Building upon this representation, we establish structural properties of policy-induced decision geometry, introduce intrinsic notions of boundary and decision complexity, derive information-theoretic measures of decision compression, and obtain statistical guarantees for boundary estimation and policy reconstruction from black-box policy queries. Collectively, these results demonstrate that, for the structured decision problems considered here, the complexity of policy reconstruction is governed by the geometry of the decision boundary rather than by the cardinality of the ambient state space. Controlled numerical experiments examine the principal theoretical predictions and provide empirical evidence consistent with the proposed framework.

1 Introduction

The paper argues that reconstructing an already optimal policy calls for a different representation than computing one: the policy-induced decision-boundary geometry. It develops that geometry as a basis for studying policy reconstruction and its complexity, alongside controlled numerical validation.

1 Introduction

  • For black-box reconstruction of a fixed optimal policy, approximating the full value function or policy may encode more information than needed.The paper frames this as distinct from computing an optimal policy from a model.Source: §1 · p. 1
  • The interfaces where optimal decisions change determine the policy-induced partition, motivating decision-region geometry as the object for reconstruction.The paper shifts attention from the policy viewed as a function to the geometry of the regions it induces.Source: §1 · p. 2
  • The framework studies policy-induced geometry through structural properties, complexity measures, reconstruction guarantees, and information-theoretic compression.It treats the geometry as an independent representation observed through black-box policy queries.Source: §1 · p. 2
  • Under suitable structural assumptions, policy-reconstruction complexity is governed by decision-boundary geometry rather than ambient state-space cardinality.The theory develops an ordered, low-complexity representation and statistical guarantees for boundary estimation and reconstruction.Source: §1 · p. 2
  • The geometric perspective complements rather than replaces functional dynamic programming, which remains natural for computing optimal decisions.The paper uses numerical experiments to examine theoretical predictions, not to compare competing learning algorithms.Source: §1 · p. 2

2 Related Literature and Mathematical Positioning

The paper positions policy-induced decision geometry as a complement to functional dynamic programming and structural optimization. It develops this viewpoint into a framework connecting partitions, boundary estimation, intrinsic complexity, and policy learning.

2 Related Literature and Mathematical Positioning

  • The paper’s organizing perspective connects functional dynamic-programming representations with structured policies, decision geometry, and statistical inference.The literature review presents these areas as different representations of the underlying decision process.Source: §2 · p. 3

2.1 Classical Objects in Dynamic Programming

  • Dynamic programming traditionally analyzes value functions, state-action values, and policies, while this paper proposes policy-induced geometry as an additional object of study.The literature review identifies limited attention to the partition geometry generated by policies.Source: §2.1 · p. 4

2.2 Structured Optimal Policies and Decision Boundaries

  • Monotonicity shapes decision-region topology, thresholds locate interfaces, and structural regularity constrains partition complexity.The paper recasts established structural properties as geometry of the partition induced by an optimal policy.Source: §2.2 · p. 5

2.3 Geometry of Decision Regions and Structural Complexity

  • The paper treats the intrinsic geometry of decision partitions as a basis for complexity measures, reconstruction, and information-theoretic compression.This addresses a gap in frameworks that measure complexity mainly through state-space dimension or functional approximation.Source: §2.3 · pp. 5–6

2.4 Statistical Estimation of Policy-Induced Decision Boundaries

  • Policy-boundary estimation uses adaptive black-box oracle queries because the optimal policy, value functions, and boundary are unobserved.The framework measures accuracy geometrically and develops estimators, Hausdorff convergence analysis, and reconstruction guarantees.Source: §2.4 · p. 6

2.5 Complexity, Information, and Geometric Policy Learning

  • The framework links reconstruction information to boundary organization: regular, low-complexity partitions require comparatively little information, while fragmented or irregular ones require more.It unifies representation complexity, statistical complexity, active information acquisition, and reconstruction through decision geometry.Source: §2.5 · p. 7

2.6 From Functional Representations to Geometric Learning

  • The paper develops a unified geometric framework spanning representation, estimation, complexity, information acquisition, and policy learning.Its sections progress from geometric foundations and compression theory to statistical learning and controlled numerical examination.Source: §2.5 · p. 7, §2.6 · p. 8

3 Policy Geometry

This section defines a geometric representation of optimal policies for structured MDPs. It treats action regions and their interfaces as the basis for policy tessellations and geometric complexity measures.

3 Policy Geometry

  • The section’s framework makes the policy-induced geometry, rather than the policy mapping alone, a representation for subsequent analysis.Its geometric objects support the later study of structural and intrinsic complexity.Source: §3 · p. 8

3.1 Structured Markov Decision Processes

  • A structured MDP adds order or regularity properties to an MDP that can induce regularity in its optimal decision rules.The section uses these assumptions to study policy geometry rather than only policy computation.Source: §3.1 · pp. 8–9

3.2 Optimal Policies as State-Space Partitions

  • An optimal policy partitions the state space into optimal action regions, whose collection forms its policy tessellation.The action regions are the fundamental geometric cells of the representation.Source: §3.2 · p. 9

3.3 Decision Boundaries

  • Decision boundaries are interfaces between action regions, and across each shared interface the optimal action changes.These interfaces are the central geometric objects studied in the paper.Source: §3.3 · p. 10

3.4 Policy Tessellations

  • Policy geometry combines the action-region tessellation with the interfaces separating neighboring regions.Together, these components encode both action allocation and transitions between action regions.Source: §3.3 · p. 10, §3.4 · p. 10

3.6 Geometric Simplicity

  • The policy geometry complexity index aggregates boundary, region, fragmentation, length, and irregularity measures using positive weights.Geometric simplicity is defined by a bounded complexity index; smaller bounds correspond to more regular geometries.Source: §3.6 · p. 12

3.5 Geometric Complexity Measures

  • The section measures geometric complexity through interface count, region topology, fragmentation, boundary size, and irregularity.The measures capture complementary aspects of the tessellation’s structure.Source: §3.5 · p. 11, §3.6 · p. 12

3.7 Discussion

  • The framework recasts monotonicity, threshold behavior, and related structural properties as features of the induced state-space partition.It complements classical structural optimization by representing policies through action regions, boundaries, tessellations, and complexity measures.Source: §3.7 · pp. 12–13

4 Structural Dynamic Programs

This section characterizes optimal-policy regions in structured dynamic programs, deriving ordered, threshold-based, and convex geometries and relating their fragmentation and tessellation complexity to the action space. It distinguishes decision complexity from value-function complexity and connects monotonicity and threshold structure to decision compression, including when the state space is large or high-dimensional.

4.1 Structural Assumptions

  • Monotone rewards and transitions, increasing differences, submodularity, and convex action differences form the structural framework for the subsequent analysis.The assumptions apply to state spaces satisfying Assumption 1 and to partially ordered action spaces.Source: §4.1 · pp. 13–14

4.2 Monotone Optimal Policies

  • The results report an optimal policy increasing on (S, ⪯) and order-convex optimal action regions, connecting monotonicity with the geometric organization of the policy tessellation.Source: §4.2 · pp. 14–15

4.3 Threshold Representations

  • Under Assumptions 2, 3, 4, and 5, every decision boundary between adjacent action regions is the graph of a threshold function, and each optimal action region is connected.These boundaries lie on low-dimensional graphs rather than arbitrary subsets of the state space.Source: §4.3 · pp. 15–16

4.4 Convex Policy Regions

  • If pairwise dominance regions are convex, every optimal action region is convex and connected, and decision boundaries coincide with indifference surfaces between competing actions.The section characterizes convex regions as excluding disconnected action regions and highly fragmented decision structures.Source: §4.4 · pp. 16–17

4.5 Geometric Simplicity

  • With a finite action space, each action generates finitely many adjacent transitions, so nonempty pairwise boundaries grow at most linearly with the number of actions (CB ≤ |A| − 1).F = 1 is the smallest attainable fragmentation index. Structured dynamic-program policy tessellation complexity is governed primarily by the action space rather than state-space size.Source: §4.5 · p. 18
  • Theorem 15 establishes that structured dynamic programs can produce intrinsically simple policy tessellations, with regions and boundaries scaling only with the number of actions.This holds even when the underlying state space is large, continuous, or high-dimensional.Source: §4.5 · p. 19

4.6 Decision Compression

  • Under Theorem 15’s assumptions, decision complexity is O(|A|), so policy tessellation complexity remains action-space controlled even as value-function complexity may grow with state-space complexity.Decision complexity measures the geometry of the optimal policy rather than the value-function representation; large decision compression ratios indicate a simpler policy representation than the associated value function.Source: §4.6 · p. 20

4.7 Discussion

  • Monotonicity, threshold structure, and convex dominance yield ordered action regions, low-dimensional boundaries, and connected convex policy regions, leading to decision compression.The discussion situates ordered and threshold policies in monotone dynamic programming and comparative statics (Veinott, 1969; Milgrom and Shannon, 1994; Topkis, 1998; Veinott Jr, 1965; Smith and McCardle, 2002).Source: §4.7 · pp. 20–21

5 Structural Geometry of Optimal Policies

This section develops a geometric account of structured optimal policies, using their tessellations and decision boundaries to represent and recover policies. It shows how boundary identification, geometric regularity, compression, and stability under small perturbations make boundary complexity central to reconstruction, with complexity potentially dimension-free under structural assumptions.

5.1 Structural Geometry as a Compressed Representation

  • A deterministic policy’s induced tessellation uniquely determines the policy, making the geometry an equivalent description rather than merely a graphical representation.The boundary structure is not required to reconstruct the policy once its tessellation is known, though it supports later complexity and learnability analyses.Source: §5.1 · pp. 21–22

5.2 Policy Boundary Principle

  • The policy boundary is exactly the set of states where the policy is not locally constant; action-region interiors are locally invariant decision zones.Every local decision change occurs on the boundary structure, which contains the entire locus of decision transitions.Source: §5.2 · p. 23

5.3 Dimension-Free Policy Geometry

  • Under the stated structural assumptions, optimal-policy geometry has complexity controlled by the action space and independent of ambient state-space dimension.The topological complexity depends only on the tessellation’s combinatorial structure, not on volume, diameter, curvature, or ambient dimension.Source: §5.3 · pp. 24–25

5.4 Geometric Stability

  • Under uniform perturbation, a policy can change only at states with action gap g(s) ≤ 2ε; with continuous Q* functions, the gap vanishes on the boundary.Thus states deep inside action regions have a positive decision margin, while possible changes are concentrated near interfaces.Source: §5.4 · pp. 25–26

5.5 Structural Compression Theorem

  • As value-function complexity grows with problem size, policy-geometry complexity remains controlled by action structure, so the representation gap increases at least linearly.The Structural Compression Theorem assumes the conditions of Theorems 19 and 21; the paper presents compression as an asymptotic result, not a finite-dimensional artifact.Source: §5.5 · pp. 26–27

5.6 Geometry and Learnability

  • The boundary-learning problem seeks to recover the optimal policy’s boundary from observed state-action information, rather than estimate its value function or approximate the policy everywhere.Its objective is to identify the geometric locus where optimal decisions change.Source: §5.6 · p. 27
  • Boundary sample complexity is defined for a prescribed boundary-accuracy criterion and tolerance without assuming a statistical framework, isolating learning difficulty due to boundary structure.Source: §5.6 · p. 28
  • Under Theorems 18, 19, and 21, recovering the optimal policy is equivalent to identifying its boundary structure, recasting policy learning as geometric boundary identification.Source: §5.6 · p. 28

5.7 Discussion

  • An optimal policy is represented without information loss by its tessellation, whose boundary structure supports local policy variation and separates invariant decision regions from transition regions.Source: §5.7 · pp. 28–29
  • Under classical structural assumptions, policy geometry remains controlled independently of ambient dimension and stable under small problem perturbations, enabling compressed descriptions with lower complexity than value-function representations.Source: §5.7 · p. 29

5.6 Geometry and Learnability

  • Policy-learning complexity is governed by decision-boundary geometry rather than ambient state-space dimension, motivating boundary-learning and active-sampling methods.Source: §5.6 · p. 28, §5.7 · p. 29

6 Geometric Complexity and Decision Compression

This section distinguishes value-representation complexity from policy decision complexity and examines when structural regularity lets policy geometry compress representation. It relates decision complexity and policy description length to boundary structure, including how monotonicity, convexity, and bounded fragmentation control geometry and how losing these properties can erode that advantage.

6.1 Complexity Measures Revisited

  • Value complexity measures the optimal value function, whereas decision complexity measures policy geometry; structured decision complexity remains controlled by action structure.The section treats these as conceptually distinct quantities.Source: §6.1 · p. 29

6.2 Compression Regimes

  • The classification distinguishes weak, polynomial, and strong compression regimes by the asymptotic behavior of the decision compression ratio, and guides analysis of when policy geometry compresses.Weak compression gives a uniformly bounded gain; polynomial compression has a polynomially growing gap, while strong compression means decision complexity grows at least one asymptotic order more slowly than value complexity.Source: §6.2 · p. 30

6.3 Scaling Laws

  • When value complexity grows as a power of problem size and structural assumptions hold, the decision compression ratio scales with value complexity; it diverges if action size is fixed or grows more slowly.The linear-compression corollary recovers the earlier linear compression result as a special case.Source: §6.3 · p. 31

6.4 Exponential Compression

  • When value complexity grows exponentially with state-space dimension, policy geometry yields an exponential separation because its complexity remains governed by action structure rather than ambient dimension.The result is presented as a structural separation between value-based and geometry-based representations.Source: §6.4 · p. 32

6.5 Boundary Compression

  • Under the theorem’s assumptions, decision complexity is asymptotically equivalent to boundary complexity, since action-region interiors contribute only bounded complexity.Thus the boundary structure carries the asymptotically relevant geometric information.Source: §6.5 · p. 33

6.6 Information-Theoretic Compression

  • Under the structural assumptions, the information content of an optimal policy is asymptotically equivalent to that of its boundary structure.Once boundaries are specified, action-region interiors add only bounded information; the result gives a description-length counterpart to geometric compression.Source: §6.6 · p. 34

6.7 Limits of Compression

  • Compression depends on geometric regularity: when regularity is lost, policy-geometry complexity may rise substantially and become comparable to value-representation complexity.The section identifies monotonicity, threshold representations, bounded fragmentation, and controlled boundary complexity among the regularity conditions supporting its compression results.Source: §6.7 · p. 35
  • When fragmentation is unbounded or convexity or monotonicity fails, policy geometry may become irregular and its complexity may grow at the same asymptotic rate as value representation.The number of connected components may grow with value-representation complexity, action regions may require comparable numbers of parameters, and threshold representations may cease to exist.Source: §6.7 · p. 35
  • Proposition 31 shows that decision compression is not universal but depends on monotonicity, convexity, and bounded fragmentation.Compression arises when policies have a small collection of regular action regions separated by simple boundaries; losing those regularities can eliminate the advantage.Source: §6.7 · p. 35

6.8 Discussion

  • Structured policy geometry remains controlled by action structure rather than state-space size, with decision boundaries accounting for its dominant geometric complexity.The section’s scaling and information-theoretic analyses characterize policy geometry as a compressed representation of optimal decision rules.Source: §6.8 · p. 36
  • When decision complexity grows substantially more slowly than value complexity, geometric representations can mitigate the representational burden of large-scale dynamic programs.The informational and geometric content of structured policies is concentrated near their boundary structure.Source: §6.8 · p. 36

7 Learning Policy Geometry

The section makes the induced boundary geometry—not the value function or policy over all states—the target for learning an optimal policy. Because policy changes are localized at boundaries, learning can focus on estimating that geometry.

7.1 Geometric Learning Problem

  • The learning target is the boundary structure induced by the optimal policy, and the observation model is left open to multiple information sources.Observations may come from simulation, state queries, optimal-action evaluations, trajectory data, or other sources that provide evidence about policy geometry.Source: §7.1 · pp. 36–37
  • Learning the optimal policy is equivalent to estimating its target boundary geometry, which can then be used to reconstruct the policy.The framework treats the boundary geometry as the object of inference rather than estimating the value function, state-action value function, or policy directly.Source: §7.1 · pp. 36–37

7.2 Boundary Learning Principle

  • For structured dynamic programs satisfying the stated assumptions, statistically informative policy geometry is concentrated near the target boundary.Policy decisions are locally constant in action-region interiors, while observations near boundaries provide information about transitions between actions.Source: §7.2 · pp. 37–38
  • Efficient policy learning may therefore be reduced to estimating the boundary rather than the entire policy over the state space.The boundary-learning principle follows from policy variation being confined to the boundary and policy-geometry complexity being governed by boundary complexity.Source: §7.2 · p. 38

7.3 Statistical Learning Model

The statistical framework treats boundary geometry as the learning target, with geometric discrepancy measured through boundary localization. Under the stated structural assumptions, sample complexity is governed by boundary complexity, with state-space cardinality entering only through that quantity.

7.3 Statistical Learning Model

  • The observation model is agnostic to how data are sampled, and the admissible geometry class is specified abstractly.The target boundary is assumed to belong to the geometric class; later complexity bounds depend on that class's structural characteristics rather than the ambient state space itself.Source: §7.3 · p. 38
  • Geometric risk measures estimator performance by the accuracy with which the decision boundaries are recovered.The framework defines error using Hausdorff distance, which measures maximal localization error between boundary structures.Source: §7.3 · p. 39

7.4 Boundary Sample Complexity

  • The section formulates boundary sample complexity as the observations needed to localize the target geometry at a specified accuracy and confidence.It introduces the statistical objects and loss functions before establishing convergence rates or sample-complexity guarantees.Source: §7.3 · p. 38, §7.4 · p. 39
  • The sample complexity of geometric learning is governed by boundary complexity, with state-space cardinality entering only through its influence on that complexity.This result assumes the conditions of Sections 4 and 5.Source: §7.4 · pp. 39–40

7.5 Active Boundary Sampling

This subsection asks where to sample to estimate the target boundary geometry and argues that boundary neighborhoods concentrate relevant information. It presents boundary-focused sampling as more efficient in expectation than uniform exploration, while framing the principle as guidance rather than an algorithm.

7.5 Active Boundary Sampling

  • The optimal policy’s geometry is completely determined by the zero-level sets of the action-difference functions.Source: §7.5 · p. 40
  • B(τ) provides a geometric approximation of the target boundary structure, identifying states close to decision transitions.Source: §7.5 · pp. 40–41
  • Boundary neighborhoods B(τ) contain the largest amount of information about the target boundary geometry Γ∗.Observations there are expected to support more efficient geometry estimation when sampling allocates them a larger share than uniform exploration.Source: §7.5 · p. 41
  • The active-sampling principle is a structural guideline, not a concrete algorithmic prescription.Its role is to identify where information relevant to learning is concentrated; later subsections develop the statistical consequences.Source: §7.5 · p. 41

7.6 Policy Reconstruction

The paper reconstructs an optimal policy from its boundary geometry, with policy discrepancies confined to neighborhoods that shrink as boundary estimates improve. It then frames learning guarantees through this geometry and the complexity it carries.

7.6 Policy Reconstruction

  • The optimal policy is uniquely determined by its boundary geometry, so estimating Γ∗ induces an estimator of the policy.The reconstruction operator maps each admissible boundary geometry to the unique deterministic policy consistent with its induced tessellation.Source: §7.6 · p. 41
  • Consistent boundary estimation yields policy reconstruction whose possible discrepancies are confined to neighborhoods shrinking with the geometric estimation error.Outside those neighborhoods, the reconstructed policy coincides with the optimal policy.Source: §7.6 · p. 42
  • The geometric learning framework proceeds from estimating and localizing boundaries to reconstructing the policy through operator R.Source: §7.6 · p. 42

7.7 Learning Guarantees

  • The framework targets boundary geometry, ties statistical complexity to its complexity, and obtains policy estimators through the reconstruction operator.The paper concludes that structured dynamic-program learning can be analyzed through decision-boundary geometry.Source: §7.7 · pp. 42–43
  • The learning guarantee bounds policy disagreement through a nondecreasing function of geometric estimation error that vanishes at zero error.The disagreement set lies within a neighborhood of Γ∗ whose radius vanishes with the geometric estimation error.Source: §7.7 · p. 43

7.8 Discussion

The discussion argues that structured policies vary chiefly near a comparatively small decision-boundary structure, making that geometry the target for learning. It concludes that learning complexity is governed by boundary geometry rather than ambient state-space size.

7.8 Discussion

  • Policy variation is localized on a comparatively small boundary structure rather than distributed throughout the entire state space.Source: §7.8 · p. 43
  • The learning problem can be reformulated as estimating the target boundary geometry, with statistically relevant information concentrated on decision boundaries.Source: §7.8 · pp. 43–44
  • The complexity parameter controlling policy learning is boundary-geometry complexity, not the size of the ambient state space.The paper states that learnability for the structured optimal policies considered is determined by decision-boundary geometry.Source: §7.8 · p. 44

8 Numerical Validation of Geometric Learning Theory

Controlled black-box experiments assess the paper’s geometric learning theory across boundary reconstruction, decision compression, and robustness, using oracle action labels and theory-defined quantities. They evaluate theoretical predictions rather than predictive or benchmark performance in isolation.

8.1 Experimental Protocol

  • The protocol uses action-label-only black-box queries, evaluates active and uniform strategies on the same target policies, and withholds value functions, gradients, action gaps, and true boundary locations.The oracle-geometry seed is separated from the query-sampling seed.Source: §8 · p. 44, §8.1 · p. 45

8.2.1 Oracle Policy Geometry

  • The oracle policies exhibit ordered decision regions separated by non-intersecting boundaries, with complexity concentrated on a one-dimensional subset of the two-dimensional state space.Recovering transition interfaces therefore reduces policy reconstruction to a geometric estimation problem.Source: §8.2.1 · p. 46, Figure 1 · p. 47, Figure 2 · p. 47

8.2.2 Boundary Estimation Accuracy

  • Across query budgets, Hausdorff error decreased monotonically; active localization achieved uniformly smaller errors and reached each prescribed geometric tolerance with fewer queries than uniform exploration.Policy disagreement also decreased consistently with geometric error.Source: §8.2.2 · pp. 47–48, Figure 3 · p. 47, Figure 4 · p. 48

8.3.1 Boundary-to-Policy Reconstruction

  • As boundary error decreased, policy disagreement fell, errors remained localized near estimated boundaries, and reconstructed partitions preserved the oracle’s ordering and adjacency structure.The results support reconstructing the policy from its estimated boundary without approximating value functions or requiring additional oracle information.Source: §8.3.1 · p. 49, Figure 5 · p. 49

8.3.2 Geometry Controls Policy Risk

  • Across policy families and query budgets, Hausdorff error and policy disagreement showed a stable monotone, approximately linear relationship on a logarithmic scale, consistent with geometric control of reconstruction error.The fitted slope remained close to theoretical predictions, with no systematic deviations reported.Source: §8.3.2 · pp. 49–50, Figure 7 · p. 50

8.3.3 Failure under Loss of Structural Regularity

  • Structured policy classes remained reconstructible with negligible disagreement, while fragmented and unstructured geometries had several orders of magnitude larger reconstruction error under identical query budgets.The results support structural regularity as an identifiability condition, not merely a technical proof assumption.Source: §8.3.3 · p. 51, Table 3 · p. 51, Figure 8 · p. 51

8.4.1 Localization of Oracle Evaluations

  • As reconstruction progressed, oracle queries concentrated around boundary components, with few remaining in homogeneous regions, consistent with the prediction that boundary neighborhoods carry the relevant geometric information.Under identical oracle geometries and conditions, this concentration was associated with increasing relative risk reduction versus uniform exploration.Source: §8.4.1 · p. 52, Figure 9 · p. 52, Figure 10 · p. 53

8.4.2 Component-wise Convergence of the Boundary Geometry

  • The component-wise experiment tracks each connected boundary component separately as query budgets increase; the reported figure indicates that all components converge at comparable rates.The analysis tests simultaneous convergence across the complete boundary geometry.Source: Figure 9 · p. 52, §8.4.2 · p. 53
  • Across query budgets, reconstructed boundary components preserve the oracle boundary’s global topology and exhibit comparable decreases in Hausdorff error, consistent with convergence toward the complete boundary.No spurious components, crossings, or changes in ordering were observed.Source: §8.4.2 · p. 53

8.5.1 Scaling Law for Decision Compression

  • The empirical Decision Compression Ratio follows the predicted scaling with state-space size, while its exponential trend with intrinsic dimension matches the predicted separation from explicit policy representations.The estimated scaling exponent is statistically indistinguishable from Theorem 3’s prediction, and the asymptotic model explains nearly all observed variability.Source: §8.5.1 · p. 54, Figure 12 · p. 55, Figure 13 · p. 55

8.5.2 Structural Compression and Information-Theoretic Efficiency

  • Structured policies show an approximately linear relationship between boundary and decision complexity, lower description lengths than explicit tabular representations, and systematic complexity separation from unstructured policies.These patterns support the Boundary Compression Theorem and information-theoretic compression interpretation.Source: §8.5.2 · p. 55, Figure 14 · p. 56, Figure 15 · p. 56

8.5.3 Dimension-Free Geometry

  • As state spaces grow, structured policies maintain essentially constant topological complexity, while fragmented policies retain substantially larger complexity.The observed stability supports the claim that intrinsic geometric complexity is distinct from ambient state-space size.Source: §8.5.3 · p. 56, Figure 16 · p. 57

8.6.1 Robustness to Smooth Boundary Perturbations

  • Under smooth boundary deformations that preserve global topology, decision complexity rises only gradually, while the compression ratio and information-theoretic gain vary only modestly.The experiments evaluate the complexity measures across increasing perturbation amplitudes.Source: §8.6.1 · p. 58, Figure 17 · p. 58, Table 6 · p. 59

8.6.2 Stability of Policy Reconstruction Across Geometries

  • Across independently generated structured geometries, reconstructed policies show uniformly small disagreement and occupy lower-complexity, lower-risk regimes than unstructured representations.The experiments also find little overlap between the structured and unstructured complexity-risk regimes.Source: §8.6.2 · p. 59, Figure 18 · p. 59, Figure 19 · p. 60

8.7 Empirical Synthesis

  • Across the experiments, boundary geometry behaves as the primary object governing policy reconstruction, while improved geometric estimates accompany lower policy disagreement and observed compression and robustness trends match theory.The experiments provide finite-sample evidence under controlled conditions, not mathematical proof of the theoretical results.Source: §8.7 · pp. 60–61

9 Conclusion

The paper treats decision-boundary geometry as the central representation for reconstructing structured optimal policies, connecting geometric complexity to estimation, sampling, and compression. Its empirical support is limited to controlled simulations, and extensions beyond the stated regularity setting remain open.

9 Conclusion

  • Accurate estimation of decision-boundary geometry is proved to imply accurate policy reconstruction, with analysis covering Hausdorff convergence, boundary sample complexity, active sampling, and decision compression.The framework uses intrinsic geometric complexity rather than ambient state-space cardinality to characterize decision compression.Source: §9 · p. 61
  • The numerical investigation aligns with the theory within its experimental regime, but the framework is restricted to structured decision geometries satisfying Section 5 regularity assumptions.Extensions to continuous-action problems, partially observable systems, stochastic boundary evolutions, and strategic multi-agent environments require new theoretical tools.Source: §9 · p. 61
  • Minimax lower bounds, statistical optimality results for geometric boundary estimators, and a deeper account of how geometric regularity interacts with sample complexity remain important development areas.Source: §9 · p. 62
  • The paper argues that, for a broad class of structured decision problems, complexity can be understood through decision-boundary geometry rather than ambient state-space dimensionality.The paper relates estimation, computational efficiency, active sampling, and information-theoretic compression to the same underlying geometric structure.Source: §9 · p. 62

Data Availability

The paper makes its numerical results reproducible through source code and scripts.

Data Availability

Ethics Approval

The study reports no human, personal-data, or animal involvement.

Ethics Approval

  • The study does not involve human participants, personal data, or animals and therefore does not require ethics approval.Source: Ethics Approval · p. 62

Funding

The authors report no specific funding for this work.

Funding

Loading 2609.18610v1…