A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes Fredy POKOU ∗1 1
Inria, CNRS, Univ. of Lille, Centrale Lille, UMR 9189 - CRIStAL, F-59000 Lille, France
arXiv:2609.18610v1 [cs.LG] 16 Sep 2026
September 17, 2026
Abstract 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 decisionboundary 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.
Keywords: Markov Decision Processes; Policy Geometry; Decision Complexity; Black-Box Policy Reconstruction; Information-Theoretic Compression.
1
Introduction
The mathematical theory of dynamic programming has traditionally represented optimal sequential decision problems through functional objects, namely the optimal value function, the optimal stateaction value function, and the optimal policy. This representation has provided the foundation for stochastic control, Markov decision processes, and reinforcement learning, and has led to a mature mathematical theory concerning optimality, approximation, convergence, and computational complexity. Virtually all existing analyses of sequential decision-making are therefore expressed in terms of functions defined over the state space. For many questions, this functional representation is entirely appropriate. However, there exists an important class of questions for which it appears unnecessarily rich. Suppose that the objective is not to compute an optimal policy from a model, but rather to reconstruct an already optimal policy from black-box observations, to quantify its intrinsic representation complexity, to determine how many oracle queries are required for reliable recovery, or to understand which structural properties govern statistical learnability. For such questions, approximating an entire value function or policy over the state space may encode substantially more information than is actually required. ∗
1
Indeed, once an optimal policy is fixed, only the interfaces at which the optimal decision changes determine the partition of the state space induced by that policy. This observation suggests that the mathematical object governing policy reconstruction is not necessarily the policy viewed as a function, but rather the geometry of the decision regions that the policy induces. In structured stochastic optimization problems, optimal policies frequently exhibit monotonicity, threshold behavior, convexity, or other forms of regularity. Consequently, they partition the state space into relatively simple regions associated with distinct optimal actions. The boundaries separating these regions form a geometric object that is uniquely determined by the policy itself. Although these decision boundaries appear implicitly throughout the literature on structured dynamic programming, they are generally interpreted as consequences of optimal decision rules rather than as mathematical objects possessing their own statistical, computational, structural, and informationtheoretic properties. Adopting this geometric viewpoint fundamentally changes the mathematical questions that arise. Instead of studying approximation errors for functional representations, one may ask whether the decision-boundary geometry can itself be estimated consistently, whether its intrinsic complexity admits quantitative characterization, whether geometric regularity governs statistical sample complexity, and whether the complexity of policy representation should be measured through the ambient state space or through the geometry of the induced decision partition. These questions are largely orthogonal to the computation of optimal policies and concern instead the mathematical structure of policies that already exist. The objective of this paper is to develop a geometric theory of structured optimal policies observed through black-box policy queries. The central mathematical object considered throughout the paper is the decision-boundary geometry induced by an optimal policy. Rather than treating this geometry as a secondary by-product of dynamic programming, we study it as an independent representation possessing its own structural properties, statistical estimators, complexity measures, reconstruction guarantees, and information-theoretic characteristics. Within this framework, policy reconstruction, oracle-query allocation, decision complexity, and information-theoretic compression are shown to arise from a common geometric representation. The theoretical development proceeds progressively. We first formalize the geometry induced by structured optimal policies and establish conditions under which this geometry admits an ordered, lowcomplexity representation. We then investigate the mathematical properties of this representation, derive intrinsic notions of geometric and decision complexity, characterize the relationship between geometric complexity and information-theoretic compression, and develop statistical guarantees for boundary estimation and policy reconstruction from black-box observations. These results collectively show that, under suitable structural assumptions, the mathematical complexity governing policy reconstruction is determined by the geometry of the decision boundary rather than by the cardinality of the ambient state space. The perspective proposed here is complementary to the classical functional theory of dynamic programming rather than a replacement for it. Functional representations remain the natural language for computing optimal decisions. Once an optimal policy has been obtained, however, its induced geometry provides an alternative mathematical representation that exposes properties largely invisible from the functional viewpoint alone. In particular, it reveals direct connections between structural regularity, statistical estimation, active oracle sampling, intrinsic complexity, and information-theoretic compression that are difficult to formulate using functional representations alone. The numerical investigation is designed to examine these theoretical predictions. Rather than comparing competing learning algorithms, every numerical experiment estimates a mathematical quantity introduced by the theory and evaluates whether the corresponding theoretical prediction is supported under a controlled black-box protocol. The empirical study therefore serves as a validation of the proposed mathematical framework rather than as an independent performance comparison. The remainder of the paper is organized as follows. Section 2 positions the geometric viewpoint within the mathematical literature and classical structural dynamic programming. Section 3 formalizes policy-induced geometry, while Sections 4-7 develop its structural, geometric, complexity, and statistical foundations. Section 8 provides controlled numerical validation of the theory, and Section 9 discusses its scope and extensions.
page 2
2
Related Literature and Mathematical Positioning
The objective of this section is twofold. First, we position the present work within the mathematical literature on dynamic programming, stochastic optimization, computational geometry, and statistical learning. Second, we identify the mathematical objects that naturally emerge from these research directions and motivate the geometric formulation developed in the remainder of the paper. Accordingly, the discussion is organized around mathematical representations rather than research communities, application domains, or algorithmic paradigms. The mathematical theory of sequential decision-making has traditionally been formulated through functional representations of optimality, most notably value functions, state-action value functions, and optimal policies. Structural optimization subsequently established qualitative properties of these policies, including monotonicity, threshold behavior, and lattice structures. Computational geometry provides a rigorous language for describing partitions and geometric organization, whereas statistical learning studies the estimation of geometric objects from partial observations. Although these research directions have developed largely independently, they progressively reveal increasingly rich mathematical representations of the same underlying decision process. Viewed collectively, these developments suggest a common observation. In many structured stochastic optimization problems, an optimal policy induces a partition of the state space into regions associated with distinct optimal actions. The interfaces separating these regions define a geometric object that is completely determined by the optimal policy. Nevertheless, existing theory generally treats this geometry as a consequence of functional representations rather than as an independent mathematical object possessing its own statistical, structural, computational, and information-theoretic properties. The present paper adopts precisely this alternative perspective. Instead of taking the value function or the policy as the primary object of analysis, the subsequent sections investigate the geometry induced by the optimal policy and examine the mathematical questions that naturally arise from this change of representation. As will become apparent throughout this review, this perspective progressively leads from functional representations to structured policies, from structured policies to decision-boundary geometry, from geometry to statistical inference, and ultimately from statistical inference to a unified theory of geometric complexity, information, and policy learning. The remainder of this section is organized according to this mathematical progression. Section 2.1 reviews the classical functional objects underlying dynamic programming. Section 2.2 discusses the structural theory of optimal policies and the emergence of decision boundaries. Section 2.3 examines the geometry and intrinsic complexity of the induced state-space partitions. Section 2.4 positions the statistical estimation of policy-induced decision boundaries with respect to existing boundaryestimation theory. Finally, Section 2.5 explains how this geometric viewpoint naturally leads to a unified perspective on statistical complexity, information acquisition, and geometric policy learning.
2.1
Classical Objects in Dynamic Programming
Since the pioneering work of Bellman, the mathematical theory of sequential decision-making has been formulated around three closely related objects: the optimal value function V ⋆ , the optimal state-action value function Q⋆ , and the optimal policy π ⋆ . These objects constitute the fundamental mathematical representations underlying Markov decision processes and stochastic dynamic programming, and they remain the basis of both classical optimal control theory and modern reinforcement learning (Bellman, 1957; Puterman, 2014; Bertsekas, 2012; Hernández-Lerma and Lasserre, 2012; Feinberg and Shwartz, 2012). Within this framework, optimal decision-making is characterized through recursive optimality equations whose solutions determine both the optimal expected return and the corresponding optimal decision rule. Consequently, the theoretical analysis of dynamic programming is expressed almost exclusively in terms of functional objects. Questions concerning existence, uniqueness, convergence, stability, approximation, and computational complexity are formulated with respect to either V ⋆ , Q⋆ , or the policy π ⋆ , leading to a mature mathematical theory encompassing value iteration, policy iteration, stochastic control, approximate dynamic programming, and large-scale optimization (Powell, 2007; Whittle, 1982; Bertsekas, 2025).
page 3
As increasingly complex decision problems have been considered, the principal computational challenge has become the approximation of these functional representations. Approximate dynamic programming and reinforcement learning therefore focus primarily on constructing computationally tractable approximations of value functions, action-value functions, or policies while preserving nearoptimal decision quality. The resulting notions of statistical efficiency and computational complexity are consequently defined relative to these functional objects. This functional viewpoint has profoundly influenced the mathematical development of the field. At the same time, it implicitly determines the representation through which optimal decisions are analyzed. Once an optimal policy has been obtained, it induces a partition of the state space into regions associated with distinct optimal actions. While this partition is fundamental for understanding the qualitative structure of optimal decision-making, its geometric properties are generally regarded as secondary consequences of the policy itself rather than as primary mathematical objects. Existing theory therefore provides a comprehensive analysis of optimal values and optimal policies, but comparatively little attention has been devoted to the intrinsic geometry generated by the policy partition. This observation suggests an alternative mathematical perspective. Rather than asking how accurately one can approximate V ⋆ , Q⋆ , or π ⋆ , one may instead ask whether the geometric structure induced by the optimal policy can itself serve as the primary object of statistical inference. Adopting this viewpoint fundamentally changes the mathematical questions under consideration. Instead of studying approximation error for functional representations, the subsequent sections investigate geometric estimation, boundary reconstruction, structural complexity, information-theoretic compression, and the statistical properties of the geometry induced by structured optimal policies.
2.2
Structured Optimal Policies and Decision Boundaries
Beyond the existence of optimal policies, a major direction of stochastic dynamic programming has been devoted to identifying qualitative structural properties of optimal decision rules. Rather than viewing an optimal policy as an arbitrary mapping from states to actions, this line of research seeks conditions under which optimal decisions possess regularity properties that admit concise mathematical descriptions. Such structural characterizations have played a central role in operations research because they often reveal the intrinsic organization of optimal solutions independently of the numerical algorithms used to compute them. The mathematical foundations of this theory are provided by the monotonicity and latticeprogramming results established by Veinott, Topkis, and subsequent authors. Under suitable assumptions involving submodularity, supermodularity, stochastic monotonicity, or lattice orderings, optimal actions evolve monotonically with respect to the underlying state variables, leading naturally to threshold-type decision rules (Veinott Jr, 1965; Veinott, 1969; Topkis, 1978, 1998). Similar structural properties have subsequently been established for a broad range of stochastic optimization problems, including inventory control, queueing systems, partially observed Markov decision processes, and stochastic resource allocation (Stidham Jr and Weber, 1989; Sobel, 1982; Lovejoy, 1987; Smith and McCardle, 2002; Krishnamurthy, 2016; Koole, 2007). From a mathematical viewpoint, these structural results admit a common interpretation. A threshold policy does not merely specify where the optimal action changes; it partitions the state space into subsets on which the optimal decision remains constant. In one-dimensional problems, this partition is determined by a finite collection of switching points. In higher-dimensional settings, the same principle extends naturally to switching curves, hypersurfaces, or more general decision interfaces separating neighboring action regions. Consequently, every structured optimal policy induces a partition of the state space whose organization is governed by a collection of decision boundaries. This observation reveals an important shift of perspective. Classical structural optimization formulates its conclusions in terms of monotone policies, threshold values, or comparative statics. Yet these properties are mathematically equivalent to statements concerning the geometry of the induced partition.
page 4
Monotonicity determines the topology of the decision regions, thresholds determine the location of decision interfaces, and structural regularity constrains the geometric complexity of the resulting partition. In this sense, the geometry of the state-space partition is not an additional feature of the optimal policy; it is an equivalent representation of the structural information established by the classical theory. Despite this close relationship, the existing literature almost exclusively treats these geometric objects as implicit consequences of structural optimality. The principal mathematical objects remain the optimal policy, the threshold parameters, or the monotone decision rule itself. Comparatively little attention has been devoted to the statistical estimation of decision boundaries, to quantitative measures of their geometric complexity, or to the role that these geometric structures play in determining the sample complexity of policy reconstruction and the information-theoretic complexity of policy representation. The developments presented in the subsequent sections adopt precisely this alternative viewpoint. Rather than regarding decision boundaries as by-products of structural optimization, the paper considers them as primary mathematical objects that encode the organization of structured optimal policies. This change of representation naturally transforms several classical questions. Policy reconstruction becomes a problem of geometric estimation; statistical accuracy is measured through boundary approximation; structural complexity becomes a property of the induced partition; and information-theoretic compression is governed by the complexity of the decision-boundary geometry rather than by the size of the ambient state space.
2.3
Geometry of Decision Regions and Structural Complexity
The structural interpretation developed in the previous subsection naturally leads to a broader mathematical question. Once an optimal policy partitions the state space into regions associated with distinct optimal actions, the resulting partition becomes a mathematical object that may be studied independently of the optimization procedure that generated it. Consequently, the analysis of structured decision processes is no longer restricted to functional representations such as value functions or policies; it also involves the geometry induced by the partition itself. The mathematical study of geometric structures has long occupied a central role in convex analysis and computational geometry. Convex analysis characterizes the geometry of feasible sets, supporting hyperplanes, variational representations, and convex decompositions, whereas computational geometry investigates partitions, arrangements, polytopes, cell complexes, and their combinatorial complexity (Rockafellar, 1997; Boyd and Vandenberghe, 2004; Ziegler, 2012; Edelsbrunner, 1987; Preparata and Shamos, 2012). Although these theories were not originally developed for stochastic dynamic programming, they provide a rigorous mathematical language for describing geometric objects that arise naturally from structured optimization problems. From this perspective, a partition possesses intrinsic properties that are independent of the objective function from which it originates. Its connected components, decision interfaces, adjacency relations, topological organization, and combinatorial complexity are properties of the partition itself. These quantities remain well defined regardless of the particular numerical representation of the value function and therefore describe structural aspects of an optimal decision process that cannot be inferred solely from functional approximation. For structured optimal policies, this distinction becomes particularly significant. The monotonicity and threshold properties discussed previously imply that neighboring decision regions are organized according to a relatively simple geometric structure. Consequently, the intrinsic complexity of the induced partition may remain substantially smaller than the apparent complexity suggested by the cardinality or dimensionality of the ambient state space. This observation indicates that geometric complexity should be regarded as an independent mathematical quantity rather than merely as a secondary consequence of value-function representations. Despite these connections, the existing operations research literature rarely formulates complexity directly in terms of the geometry induced by optimal policies. Computational complexity is traditionally measured through the dimension of the state space, the complexity of functional approximation, or the computational cost of optimization algorithms. Likewise, statistical analyses typically quantify approximation error for value functions, policies, or estimators without explicitly characterizing the intrinsic complexity of the underlying decision partition. page 5
As a consequence, no general mathematical framework currently relates the geometric organization of structured decision regions to statistical estimation, policy reconstruction, or information-theoretic representation. The viewpoint adopted in the present paper is motivated by this gap. Rather than measuring the complexity of a decision problem exclusively through its functional representation, the subsequent sections investigate the intrinsic complexity of the geometry induced by the optimal policy. This change of mathematical representation provides the foundation for the notions of boundary complexity, decision complexity, and decision compression developed later in the paper. Under this perspective, statistical estimation, sample complexity, and information-theoretic compression are interpreted as consequences of the geometric organization of the decision partition rather than of the dimensionality of the ambient state space.
2.4
Statistical Estimation of Policy-Induced Decision Boundaries
The geometric formulation developed in the previous subsections naturally transforms the underlying statistical inference problem. Once the partition induced by an optimal policy is regarded as the primary mathematical object, the objective is no longer to approximate a value function or a policy mapping, but rather to estimate the geometric interfaces separating neighboring optimal decision regions. Consequently, the statistical analysis shifts from functional approximation to geometric inference. The estimation of geometric boundaries has been extensively investigated in several areas of mathematical statistics and statistical learning. Density level-set estimation considers the recovery of regions determined by unknown probability densities (Tsybakov, 1997; Polonik, 1995), statistical learning theory studies classification boundaries generated by discriminant functions or supervised prediction models (Vapnik, 1999; Devroye et al., 2013; Anthony and Bartlett, 2009; Shalev-Shwartz and Ben-David, 2014), and free-boundary theory analyzes interfaces arising from variational inequalities and partial differential equations (Caffarelli, 2005; Petrosyan et al., 2012). Although these research directions rely on different mathematical assumptions, they all investigate geometric interfaces generated by an underlying probabilistic, analytical, or variational model. From a mathematical perspective, however, the object considered in the present paper is fundamentally different. In the aforementioned settings, the boundary is induced by an observable statistical mechanism, such as a probability density, a regression function, a discriminant function, or the solution of a variational problem. By contrast, the boundary investigated here is generated implicitly by an unknown optimal policy associated with a stochastic decision process. The value function, the state-action value function, threshold parameters, gradients, and the boundary itself are all unobserved. The only available information consists of evaluations of the optimal action returned by a black-box decision oracle. This distinction fundamentally changes the statistical formulation of the estimation problem. Classical boundary estimation relies on observations generated by an underlying statistical model, whereas policy-induced boundary estimation relies on adaptive interactions with an optimization oracle. The statistical object is therefore not a density contour, a classification surface, or a free boundary, but the collection of state-space interfaces at which the optimal decision changes. Likewise, statistical accuracy is naturally quantified through geometric discrepancies between estimated and true decision boundaries rather than exclusively through prediction or classification error. The change of statistical object also modifies the notions of information acquisition and sample complexity. Since observations are obtained through adaptive oracle queries rather than passive sampling, the allocation of samples becomes an integral component of the inference problem. In particular, structural regularity may be exploited to concentrate observations near decision interfaces, suggesting that the statistical efficiency of boundary estimation is governed by the geometry of the induced partition rather than by the ambient state-space dimension alone. The viewpoint adopted throughout this paper is motivated by these observations. Rather than interpreting policy learning as the approximation of functional representations, the subsequent analysis formulates it as the statistical estimation of a policy-induced geometric object observed exclusively through label-only oracle interactions. This formulation provides the mathematical foundation for the geometric estimators, Hausdorff convergence analysis, boundary sample complexity, and policy reconstruction guarantees developed in Section 7, where statistical inference is characterized directly in terms of the geometry generated by structured optimal policies. page 6
2.5
Complexity, Information, and Geometric Policy Learning
The statistical formulation developed in the previous subsection naturally leads to a final mathematical question. Once the decision-boundary geometry induced by an optimal policy is regarded as the primary object of statistical inference, what determines the intrinsic difficulty of the corresponding learning problem? Within the geometric perspective adopted throughout this paper, this question is no longer answered solely by the complexity of functional representations, but by the amount of information encoded in the geometry of the induced decision partition. Classical learning theories quantify statistical complexity through functional approximation. Approximate dynamic programming studies the approximation of value functions and policies, reinforcement learning analyzes the statistical efficiency of policy optimization and value estimation, while statistical learning theory characterizes generalization through the complexity of hypothesis classes (Powell, 2007; Sutton et al., 1998; Lagoudakis and Parr, 2003; Munos and Szepesvári, 2008; Lazaric et al., 2010; Vapnik, 1999). Although these theories differ substantially in their mathematical formulation, they all measure learning complexity with respect to functional representations of the underlying decision problem. The geometric viewpoint developed in the previous subsections suggests a complementary interpretation. Once an optimal policy induces a partition of the state space, the information required to reconstruct the policy is encoded by the organization of the induced decision boundaries rather than exclusively by the numerical representation of the value function. Consequently, the intrinsic difficulty of policy learning depends not only on the approximation of functional objects but also on the geometric regularity of the decision partition itself. This observation establishes a direct connection between geometry and statistical complexity. Smooth decision interfaces, low-complexity partitions, and regular geometric organization require comparatively little information for accurate reconstruction, whereas fragmented or highly irregular partitions demand substantially larger observational effort. Under this interpretation, statistical complexity becomes an intrinsic property of the geometry induced by the optimal policy rather than a consequence of the dimensionality of the ambient state space alone. From an information-theoretic perspective, this change of viewpoint has important implications. The amount of information required to represent, estimate, and reconstruct an optimal policy is governed by the structural organization of the induced decision partition. Representation complexity, statistical complexity, active information acquisition, and policy reconstruction therefore become different manifestations of the same underlying geometric object. Rather than constituting independent questions, they admit a unified interpretation through the intrinsic complexity of the decision-boundary geometry. Despite the extensive literature on dynamic programming, reinforcement learning, statistical learning, and computational geometry, these different notions of complexity have largely been investigated independently. Existing theories typically analyze optimization, approximation, statistical estimation, or information representation in isolation. Comparatively little attention has been devoted to developing a unified mathematical framework in which geometric organization simultaneously determines representation complexity, statistical efficiency, information acquisition, and policy reconstruction. The remainder of the paper develops precisely such a framework. Section 3 introduces the geometric representation of structured optimal policies. Sections 4 and 5 establish the corresponding structural and geometric foundations. Section 6 develops a theory of boundary complexity, decision complexity, and information-theoretic decision compression. Section 7 formulates the associated statistical learning theory through geometric estimators, Hausdorff convergence, active boundary sampling, and boundary sample complexity. Section 8 finally examines whether the theoretical predictions established throughout the paper are supported by controlled numerical experiments.
2.6
From Functional Representations to Geometric Learning
The preceding discussion reveals a common mathematical theme underlying several research directions in operations research, stochastic optimization, computational geometry, and statistical learning. Although these fields have developed largely independently, they progressively describe increasingly rich representations of the same underlying decision process.
page 7
Classical dynamic programming characterizes optimal decisions through functional objects; structural optimization establishes qualitative regularity properties of optimal policies; computational geometry provides a language for describing the partitions induced by these policies; and statistical learning investigates the estimation of geometric objects from partial observations. Viewed collectively, these developments suggest that the geometry induced by an optimal policy constitutes a mathematical object deserving analysis in its own right. Once this viewpoint is adopted, several questions that traditionally appear unrelated become naturally connected. Policy reconstruction may be interpreted as geometric reconstruction of a decision partition. Statistical estimation becomes boundary estimation under oracle observations. Complexity becomes an intrinsic property of the induced geometry rather than of the ambient state space alone. Likewise, information acquisition and representation efficiency are governed by the structural organization of the decision boundaries rather than exclusively by functional approximation. The theoretical developments presented in the remainder of this paper are organized around this change of mathematical representation. Section 3 introduces the geometric representation of structured optimal policies and formalizes the associated decision-boundary geometry. Sections 4 and 5 establish the structural, topological, and geometric properties of this representation. Section 6 develops a theory of boundary complexity, decision complexity, and information-theoretic decision compression. Section 7 formulates the corresponding statistical learning framework through geometric estimators, active boundary sampling, Hausdorff convergence, and boundary sample complexity. Finally, Section 8 examines whether the theoretical predictions established throughout the paper are supported by controlled numerical experiments. Rather than extending existing approximation methods, the paper therefore develops a unified mathematical framework in which representation, statistical estimation, structural complexity, information acquisition, and policy learning are all interpreted through the geometry induced by structured optimal policies. The subsequent sections show that this geometric perspective provides a common language through which these questions may be analyzed within a single theoretical framework.
3
Policy Geometry
This section introduces the geometric framework that underlies the subsequent analysis. Building upon the classical theory of stochastic dynamic programming (Bellman, 1957; Puterman, 2014; Bertsekas, 2012; Hernández-Lerma and Lasserre, 2012), we formalize the mathematical objects through which optimal policies will be studied. The objective is not yet to establish structural results, but rather to define a geometric representation of optimal decision rules that will serve as the foundation for the theory developed in later sections.
3.1
Structured Markov Decision Processes
We consider a discounted Markov decision process (MDP) M = (S, A, P, r, γ),
(1)
where S denotes the state space, A is a finite action space, P (· | s, a) is the transition kernel, r : S × A → R is the one-period reward function, and γ ∈ (0, 1) is the discount factor. Definition 1 (Structured Markov Decision Process). A structured Markov decision process is an MDP of the form (1) endowed with additional order, monotonicity, convexity, submodularity, or stochastic-ordering properties that induce regularity in the corresponding optimal decision rules. Let π:S→A denote a stationary deterministic policy. The associated value function is defined by "∞ # X V π (s) = Eπ γ t r(St , π(St )) S0 = s . t=0
page 8
(2)
(3)
The optimal value function is given by V ∗ (s) = sup V π (s),
s ∈ S,
(4)
∀s ∈ S.
(5)
π
and an optimal policy π ∗ satisfies ∗
V π (s) = V ∗ (s),
The class of structured MDPs encompasses many models arising in operations research, including inventory systems, queueing networks, maintenance planning, admission-control problems, and partially observed decision processes (Veinott Jr, 1965; Topkis, 1998; Milgrom and Shannon, 1994; Smith and McCardle, 2002). In such settings, the state space often possesses an intrinsic ordering that plays a fundamental role in the characterization of optimal decisions. Accordingly, we assume that the state space is endowed with a partial order relation (6)
(S, ⪯).
Assumption 1 (Ordered State Space). The state space S is a partially ordered set under the relation ⪯. Assumption 1 is deliberately weak and serves only to establish a common framework encompassing the monotone dynamic programs considered in the literature. More restrictive assumptions involving monotonicity, submodularity, convexity, and increasing differences will be introduced in Section 4, where they will be used to derive geometric properties of optimal policies. The purpose of Definition 1 and Assumption 1 is to provide a mathematical environment in which geometric regularities of optimal decision rules may emerge. Classical structural assumptions are typically employed to establish monotonicity, threshold behavior, or comparative-statics properties. In contrast, our objective is to investigate how such assumptions shape the geometry of the optimal policy itself.
3.2
Optimal Policies as State-Space Partitions
The optimal policy π ∗ induces a decomposition of the state space according to the actions selected under optimal decision making. For each action a ∈ A, define Ra = {s ∈ S : π ∗ (s) = a} .
(7)
Definition 2 (Optimal Action Region). For a given action a ∈ A, the set Ra defined in (7) is called the optimal action region associated with action a. Since π ∗ is a single-valued mapping, the family {Ra }a∈A satisfies S=
[
Ra ,
(8)
a∈A
and Ra ∩ Ra′ = ∅,
a ̸= a′ .
(9)
Hence, the collection of optimal action regions forms a partition of the state space. T ∗ = {Ra }a∈A .
(10)
Definition 3 (Optimal Policy Tessellation). The partition T ∗ defined in (10) is called the optimal policy tessellation induced by the optimal policy π ∗ . The tessellation T ∗ provides a geometric representation of the optimal policy through the partition of the state space into optimal action regions. The sets Ra constitute the fundamental geometric objects of the framework developed in this paper. page 9
3.3
Decision Boundaries
Definition 3 shows that the optimal policy induces a tessellation T ⋆ = {Ra : a ∈ A}, which partitions the state space into optimal action regions. Beyond the regions themselves, the geometry of the tessellation is determined by the interfaces separating neighboring regions. These interfaces constitute the fundamental geometric objects studied throughout the remainder of the paper. Throughout this paper, for every subset A ⊆ S, we denote by A its closure and by int(A) its interior. Definition 4 (Region Boundary). For every action a ∈ A, the boundary of the corresponding action region Ra is defined by ∂Ra = Ra ∩ S \ Ra .
(11)
The boundary ∂Ra consists of all states that separate Ra from the remainder of the state space. Definition 5 (Pairwise Decision Boundary). Let a, a′ ∈ A with a ̸= a′ . The decision boundary shared by the two action regions Ra and Ra′ is defined by Γaa′ = Ra ∩ Ra′ .
(12)
whenever this intersection is nonempty. The set Γaa′ represents the common interface separating two adjacent optimal action regions. It is precisely across this interface that the optimal decision changes from action a to action a′ . Definition 6 (Global Decision Boundary). The global decision boundary associated with the optimal policy is Γ=
[
Γaa′ .
(13)
a,a′ ∈A a<a′
The restriction a < a′ avoids counting the same interface twice. Definition 7 (Geometric Representation of an Optimal Policy). The pair (T ⋆ , Γ)
(14)
is called the geometric representation of the optimal policy. The tessellation T ⋆ identifies the action regions, whereas Γ collects the interfaces separating them. Consequently, the geometric representation encodes both the partition of the state space induced by the optimal policy and the decision geometry governing transitions between neighboring action regions. This representation forms the mathematical foundation for the geometric estimation, complexity analysis, policy reconstruction, and decision-compression theory developed in the subsequent sections.
3.4
Policy Tessellations
The optimal action regions introduced in Section 3.2 and the boundary structure defined in Section 3.3 together determine the global geometric organization of an optimal policy. The tessellation T ∗ specifies the partition of the state space into optimal action regions, while the set Γ describes the interfaces separating neighboring regions. These two components provide complementary information: the former characterizes the spatial allocation of optimal actions, whereas the latter characterizes the transitions between them. G ∗ = (T ∗ , Γ) . page 10
(15)
Definition 8 (Policy Geometry). The pair G ∗ defined in (15) is called the policy geometry associated with the optimal policy π ∗ . The policy geometry G ∗ may be viewed as a geometric arrangement of decision regions within the state space. In this representation, the regions Ra constitute the fundamental geometric cells of the arrangement, while the boundary structure Γ determines how these cells are connected and separated. Such geometric representations are common in convex geometry, polyhedral theory, and computational geometry, where the properties of a partition are studied through the organization of its constituent regions and interfaces (Ziegler, 2012; Edelsbrunner, 1987). The present framework adopts a similar perspective for structured dynamic decision problems.
3.5
Geometric Complexity Measures
The policy geometry G ∗ introduced in Definition 8 provides a geometric representation of the optimal policy through its action regions and decision boundaries. To characterize the structural complexity of this geometry, we introduce a collection of complexity measures associated with the tessellation T ∗ and its boundary structure Γ. These measures quantify complementary aspects of policy geometry, including the complexity of decision regions, the organization of decision boundaries, and the degree of geometric regularity exhibited by the tessellation. Definition 9 (Boundary Complexity). The boundary complexity of the policy geometry is defined by CB =
X
1{Γaa′ ̸=∅} ,
(16)
a,a′ ∈A a<a′
where 1(·) denotes the indicator function. The quantity CB measures the number of distinct interfaces separating optimal action regions. Definition 10 (Region Complexity). The region complexity of the tessellation is defined by CR =
X
(17)
Nc (Ra ),
a∈A
where Nc (·) denotes the number of connected components of a set. The quantity CR measures the topological complexity of the action regions composing the tessellation. Definition 11 (Fragmentation Index). The fragmentation index is defined by F =
CR . |A|
(18)
The index F measures the average number of connected components per action region. Definition 12 (Boundary Length). Assume that S ⊆ Rd . The total boundary length of the tessellation is defined by X
L=
Hd−1 (Γaa′ ) ,
(19)
a,a′ ∈A a<a′
where Hd−1 denotes the (d − 1)-dimensional Hausdorff measure. For d = 2, the quantity L corresponds to the total length of the decision boundaries. Definition 13 (Geometric Irregularity). Assume that each region Ra has finite Lebesgue measure µ(Ra ). The geometric irregularity of the tessellation is defined by κ = pP
L
a∈A µ(Ra )
where µ denotes the Lebesgue measure on S. page 11
,
(20)
The quantity κ measures the relative complexity of the boundary structure with respect to the overall size of the state space partition. Larger values of κ correspond to increasingly irregular policy geometries. The measures introduced above are inspired by classical notions of geometric and combinatorial complexity arising in polyhedral and computational geometry (Ziegler, 2012; Edelsbrunner, 1987). In the present setting, they provide a quantitative description of the structural complexity of optimal policy tessellations.
3.6
Geometric Simplicity
The complexity measures introduced in Section 3.5 characterize complementary aspects of policy geometry. While each measure provides information about a specific structural feature of the tessellation, it is convenient to aggregate these quantities into a single measure of geometric complexity. C(G) = wB CB + wR CR + wF F + wL L + wκ κ,
(21)
where wB , wR , wF , wL , wκ > 0 are fixed weighting coefficients. Definition 14 (Policy Geometry Complexity Index). The quantity C(G) defined in (21) is called the policy geometry complexity index. The index C(G) provides a global characterization of the structural complexity of a policy geometry by jointly accounting for the number of decision interfaces, the topological complexity of the action regions, the degree of fragmentation, the total boundary size, and the geometric irregularity of the tessellation. Definition 15 (Geometrically Simple Policy). A policy geometry G is said to be geometrically simple if there exists a constant K > 0 such that C(G) ≤ K.
(22)
The constant K quantifies the maximal geometric complexity compatible with the notion of simplicity. Smaller values of K correspond to increasingly regular policy geometries. The previous definition applies to a single policy. It is often useful to extend the notion of geometric simplicity to an entire class of policies. Definition 16 (Geometrically Simple Policy Class). Let Π denote a class of admissible policies. The class Π is said to be geometrically simple if there exists a constant K > 0 such that sup C(G(π)) ≤ K.
(23)
π∈Π
Definitions 15 and 16 provide an abstract framework for studying structural regularity in dynamic decision problems. They allow geometric properties of optimal policies to be characterized independently of the particular application under consideration and will serve as the basis for the structural results established in the next section.
3.7
Discussion
The structural dynamic programming literature has traditionally focused on the characterization of optimal actions through monotonicity, threshold behavior, convexity, and comparative-statics properties (Veinott Jr, 1965; Topkis, 1998; Milgrom and Shannon, 1994; Smith and McCardle, 2002). These results provide valuable insights into the qualitative behavior of optimal policies and have played a central role in the analysis of dynamic decision problems. The framework developed in this section adopts a complementary perspective. Rather than studying optimal policies solely as mappings from states to actions, we represent them through the geometric structures they induce on the state space. This representation naturally gives rise to action regions, decision boundaries, policy tessellations, and associated measures of geometric complexity. page 12
The resulting geometric viewpoint provides a common language for describing structural regularities across a broad class of dynamic decision problems. In particular, it allows monotonicity, threshold behavior, and related structural properties to be interpreted through the geometry of the induced state-space partition. The subsequent analysis investigates how classical assumptions from structured dynamic programming constrain the geometry of optimal policy tessellations and thereby determine their intrinsic complexity.
4
Structural Dynamic Programs
4.1
Structural Assumptions
The geometric properties of optimal policy tessellations are closely linked to the structural characteristics of the underlying dynamic program. A substantial literature has identified conditions under which optimal policies exhibit monotonicity, threshold behavior, and comparative-statics properties (Veinott Jr, 1965; Veinott, 1969; Topkis, 1978, 1998; Milgrom and Shannon, 1994; Smith and McCardle, 2002). Throughout this section, the state space (S, ⪯) is assumed to satisfy Assumption 1. In addition, the action space A is assumed to be endowed with a partial order, also denoted by ⪯. The following assumptions constitute the structural framework of the subsequent analysis. Assumption 2 (Monotone Rewards). For every action a ∈ A, the reward function is increasing with respect to the state order. Specifically, s1 ⪯ s2
=⇒
r(s1 , a) ≤ r(s2 , a),
(24)
for all s1 , s2 ∈ S. Assumption 3 (Monotone Transitions). For every action a ∈ A, the transition kernel is monotone with respect to first-order stochastic dominance. That is, s1 ⪯ s2
=⇒
P (· | s1 , a) ⪯st P (· | s2 , a),
(25)
for all s1 , s2 ∈ S, where ⪯st denotes the usual stochastic order. Assumptions 2-3 constitute the classical framework of monotone dynamic programming and stochastic monotonicity (Veinott, 1969; Lovejoy, 1987; Koole, 2007). Let Z ∗ Q (s, a) = r(s, a) + γ V ∗ (s′ ) P (ds′ | s, a) (26) S
denote the optimal state-action value function. Assumption 4 (Increasing Differences). The function Q∗ exhibits increasing differences in (s, a). Specifically, Q∗ (s2 , a2 ) − Q∗ (s1 , a2 ) ≥ Q∗ (s2 , a1 ) − Q∗ (s1 , a1 ),
(27)
for all s1 ⪯ s2 and a1 ⪯ a2 . Assumption 4 is a fundamental condition in monotone comparative statics and provides one of the principal mechanisms through which threshold structures emerge (Topkis, 1998; Milgrom and Shannon, 1994). Assumption 5 (Submodularity). The function Q∗ is submodular on S × A. Equivalently, Q∗ (s1 , a1 ) + Q∗ (s2 , a2 ) ≤ Q∗ (s1 , a2 ) + Q∗ (s2 , a1 ),
(28)
for all s1 ⪯ s2 and a1 ⪯ a2 . Submodularity plays a central role in lattice programming and in the structural analysis of optimal policies (Topkis, 1978, 1998). page 13
Definition 17 (Action Difference Function). For any pair of actions a, a′ ∈ A, define ∆aa′ (s) = Q∗ (s, a) − Q∗ (s, a′ ),
(29)
for all s ∈ S. Assumption 6 (Convex Action Differences). Assume that S ⊆ Rd . For every pair of actions a, a′ ∈ A, the function ∆aa′ defined in Definition 17 is convex on S. Assumption 6 connects structured dynamic programming with classical notions of convex analysis and optimization (Rockafellar, 1997; Boyd and Vandenberghe, 2004). The assumptions introduced above encompass a broad class of dynamic decision problems arising in operations research, including inventory-control systems, queueing models, admission-control problems, maintenance planning, and partially observed Markov decision processes (Veinott Jr, 1965; Stidham Jr and Weber, 1989; Sobel, 1982; Smith and McCardle, 2002; Krishnamurthy, 2016).
4.2
Monotone Optimal Policies
The assumptions introduced in Section 4.1 belong to the classical framework of monotone dynamic programming. Their principal implication is the emergence of ordered optimal decision rules. We first recall standard monotonicity results and then derive their geometric consequences for the policy tessellation introduced in Section 3. Proposition 1 (Monotonicity of the Optimal Value Function). Suppose that Assumptions 2 and 3 hold. Then the optimal value function V ∗ is increasing on (S, ⪯). Specifically, s1 ⪯ s2
=⇒
V ∗ (s1 ) ≤ V ∗ (s2 ),
(30)
for all s1 , s2 ∈ S. Proof. The result follows from standard monotone dynamic programming arguments. Under Assumptions 2 and 3, the Bellman operator preserves monotonicity. Since V ∗ is the unique fixed point of the Bellman operator, the claim follows from successive approximation; see Veinott (1969), Puterman (2014), and Hernández-Lerma and Lasserre (2012). The monotonicity of the optimal value function provides the foundation for the monotonicity of optimal decision rules. Proposition 2 (Monotone Optimal Policy). Suppose that Assumptions 2, 3, and 4 hold. Then there exists an optimal policy π ∗ that is increasing on (S, ⪯). That is, s1 ⪯ s2
=⇒
π ∗ (s1 ) ⪯ π ∗ (s2 ),
(31)
for all s1 , s2 ∈ S. Proof. By Assumption 4, the function Q∗ satisfies increasing differences in (s, a). Topkis’ monotonicity theorem therefore implies that the set of optimal actions is increasing with respect to the state variable. Consequently, there exists a monotone optimal selector π ∗ ; (see Topkis, 1998) and Milgrom and Shannon (1994). The monotonicity of π ∗ imposes strong restrictions on the geometry of the optimal action regions introduced in Definition 2. Theorem 3 (Ordered Region Theorem). Suppose that the assumptions of Proposition 2 hold. Then every optimal action region Ra is order-convex. That is, whenever s1 , s2 ∈ Ra ,
s1 ⪯ s ⪯ s2 ,
(32)
it follows that s ∈ Ra . page 14
(33)
Proof. Let s1 , s2 ∈ Ra with s1 ⪯ s2 . Since π ∗ is increasing, the action selected by the optimal policy cannot decrease between comparable states. If there existed a state s such that s1 ⪯ s ⪯ s2 and π ∗ (s) ̸= a, then monotonicity of π ∗ would be violated. Hence every intermediate state must belong to the same action region. Theorem 3 establishes the first direct connection between structural dynamic programming and policy geometry. Monotonicity does not merely constrain the optimal action selected at a given state; it also constrains the geometric organization of the regions composing the policy tessellation. Corollary 4 (Region Complexity Bound). Under the assumptions of Theorem 3, CR = O(|A|).
(34)
Proof. Order-convex regions cannot exhibit arbitrary fragmentation. Each action region contributes at most a finite number of connected ordered components. Consequently, the total number of connected components grows at most linearly with the number of actions.
4.3
Threshold Representations
Threshold policies constitute one of the most important structural phenomena in dynamic programming and operations research. Such policies arise in a broad range of applications, including inventory control, queueing systems, admission-control problems, and maintenance planning (Scarf, 1960; Veinott Jr, 1965; Sobel, 1982; Stidham Jr and Weber, 1989). The monotonicity result established in Proposition 2 admits a more explicit characterization when the state space contains a distinguished ordered component. Throughout this subsection, assume that S = X × Z,
(35)
where X ⊆ R is totally ordered and Z denotes an arbitrary auxiliary state space. Theorem 5 (Threshold Representation Theorem). Suppose that Assumptions 2, 3, 4, and 5 hold. Then there exists a collection of threshold functions baa′ : Z → X ,
(36)
such that, for every pair of adjacent actions a ≺ a′ , π ∗ (x, z) = a
⇐⇒
x < baa′ (z),
(37)
π ∗ (x, z) = a′
⇐⇒
x ≥ baa′ (z).
(38)
and
Proof. By Proposition 2, the optimal policy is increasing with respect to the ordered state variable. Consequently, transitions between adjacent actions occur through monotone switching surfaces. The existence of threshold functions follows from standard lattice-theoretic arguments and monotone comparative statics (Topkis, 1998; Milgrom and Shannon, 1994). The threshold representation admits a natural geometric interpretation in terms of the decision boundaries introduced in Definition 5. Corollary 6 (Boundary Graph Representation). Under the assumptions of Theorem 5, every decision boundary between adjacent action regions is the graph of a threshold function. Specifically, Γaa′ = {(x, z) ∈ S : x = baa′ (z)} .
page 15
(39)
Proof. The result follows immediately from (37) and (38). The transition between neighboring action regions occurs precisely when the ordered state variable reaches the threshold value. Corollary 6 shows that threshold policies induce highly structured decision boundaries. Rather than forming arbitrary subsets of the state space, the boundaries are constrained to lie on lowdimensional graphs. A further consequence concerns the fragmentation properties of the tessellation. Corollary 7 (Absence of Fragmentation). Under the assumptions of Theorem 5, each optimal action region is connected. Consequently, F = 1.
(40)
Proof. Each action region is generated by threshold inequalities involving the ordered state variable x. Such regions are connected and therefore possess a single connected component. Hence CR = |A|.
(41)
By Definition 11, F =
4.4
CR = 1. |A|
(42)
Convex Policy Regions
The monotonicity and threshold structures established in Sections 4.2 and 4.3 constrain the ordering of optimal decisions. A stronger form of geometric regularity emerges when the dominance relations induced by the optimal state–action value function generate convex decision sets. Such conditions arise naturally in several classes of structured dynamic programs and connect the geometry of optimal policies with classical convex analysis (Rockafellar, 1997; Boyd and Vandenberghe, 2004). For every pair of actions a, a′ ∈ A, define the dominance region Daa′ = s ∈ S : Q∗ (s, a) ≥ Q∗ (s, a′ ) .
(43)
The set Daa′ contains all states for which action a weakly dominates action a′ . Assumption 7 (Convex Dominance Regions). For every pair of actions a, a′ ∈ A, the dominance region Daa′ defined in (43) is convex. Assumption 7 may be viewed as a geometric strengthening of the structural assumptions introduced in Section 4.1. It is satisfied whenever the pairwise dominance relations generated by the optimal value structure admit convex representations. The following result establishes the geometric structure of the optimal action regions. Theorem 8 (Convex Region Theorem). Suppose that Assumption 7 holds. Then every optimal action region Ra is convex. Proof. By Definition 2, a state belongs to Ra if and only if action a weakly dominates every competing action. Consequently, Ra =
\
Daa′ .
(44)
a′ ̸=a
Since each dominance region Daa′ is convex by Assumption 7, and intersections of convex sets remain convex (Rockafellar, 1997; Boyd and Vandenberghe, 2004), it follows that Ra is convex.
page 16
Theorem 8 provides a direct connection between structural properties of the dynamic program and the geometry of the induced policy tessellation. In particular, convexity excludes disconnected action regions and highly fragmented decision structures. Corollary 9 (Connected Action Regions). Under the assumptions of Theorem 8, every optimal action region Ra is connected. Proof. Every convex subset of a Euclidean space is connected. The result therefore follows immediately from Theorem 8. The absence of disconnected regions has immediate implications for the geometric complexity measures introduced in Section 3. Corollary 10 (Region Complexity). Under the assumptions of Theorem 8, CR = |A|.
(45)
Proof. By Corollary 9, each action region contributes exactly one connected component. Since the tessellation contains |A| regions, the result follows directly from the definition of CR . Corollary 11 (Absence of Fragmentation). Under the assumptions of Theorem 8, F = 1.
(46)
Proof. Combining Definition 11 with (45) yields F =
CR = 1. |A|
The convexity of the action regions also constrains the geometry of the decision boundaries. Corollary 12 (Boundary Structure). Under the assumptions of Theorem 8, the decision boundary between two actions a and a′ satisfies Γaa′ ⊆ ∂Daa′ .
(47)
Γaa′ ⊆ s ∈ S : Q∗ (s, a) = Q∗ (s, a′ ) .
(48)
Moreover,
Proof. A transition from Ra to Ra′ can occur only at states where neither action strictly dominates the other. Hence any boundary point must satisfy Q∗ (s, a) = Q∗ (s, a′ ), which is equivalent to belonging to the indifference set s ∈ S : Q∗ (s, a) = Q∗ (s, a′ ) . Since the dominance relation changes across the boundary, such points necessarily belong to the boundary of the dominance region Daa′ . Corollaries 10-12 show that convexity imposes strong geometric restrictions on optimal policy tessellations. In contrast to general decision partitions, convex policy regions exhibit minimal fragmentation, admit simple connectivity properties, and generate decision boundaries that coincide with indifference surfaces between competing actions. page 17
4.5
Geometric Simplicity
The results established in the previous subsections reveal a common phenomenon. Under standard structural assumptions from monotone dynamic programming and comparative statics, the geometry of the optimal policy tessellation remains highly organized despite the potentially large dimension of the underlying state space. We now summarize these implications through the geometric complexity measures introduced in Section 3. The first result concerns the complexity of the boundary structure. Theorem 13 (Boundary Complexity Bound). Suppose that the assumptions of Theorem 5 hold. Then the boundary complexity satisfies CB = O(|A|).
(49)
Proof. By Corollary 6, each nonempty decision boundary corresponds to a threshold surface separating two adjacent action regions. Since the action space is finite, each action can generate only a finite number of adjacent transitions. Consequently, the number of nonempty pairwise boundaries grows at most linearly with the number of actions. Therefore, CB ≤ |A| − 1, which implies (49). The next result characterizes the fragmentation properties of the policy tessellation. Theorem 14 (Minimal Fragmentation). Suppose that the assumptions of Theorem 8 hold. Then F = 1.
(50)
Moreover, F = 1 is the smallest attainable value of the fragmentation index. Proof. By Corollary 10, CR = |A|. R Substituting into Definition 11 yields F = C |A| = 1. Furthermore, every action region contributes at least one connected component. Hence CR ≥ |A|, which implies F ≥ 1. Therefore, F = 1 is the minimum achievable fragmentation level. The previous results suggest that structured dynamic programs generate policy tessellations whose complexity is governed primarily by the action space rather than by the size of the state space. To formalize this observation, we introduce a topological complexity index. Definition 18 (Topological Complexity Index). The topological complexity of an optimal policy tessellation is defined by Gtop (π) = wB CB + wR CR + wF F, where wB , wR , wF ≥ 0 are fixed weights. The following theorem constitutes the main structural conclusion of this section. Theorem 15 (Geometric Simplicity Theorem). Suppose that 1. Assumptions 2-5 hold; 2. the threshold representation of Theorem 5 holds; 3. the convexity condition of Theorem 8 holds.
page 18
(51)
Then CB = O(|A|),
(52)
CR = |A|,
(53)
F = 1,
(54)
and consequently Gtop (π ∗ ) = O(|A|).
(55)
Proof. Equation (52) follows from Theorem 13. Equation (53) follows from Corollary 10. Equation (54) follows from Theorem 14. Substituting these relations into Definition 18 gives Gtop (π ∗ ) = wB O(|A|) + wR |A| + wF . Therefore, Gtop (π ∗ ) = O(|A|). Theorem 15 establishes that broad classes of structured dynamic programs generate intrinsically simple policy tessellations. Although the underlying state space may be large, continuous, or highdimensional, the geometric organization of the optimal policy remains controlled by a number of regions and boundaries that scales only with the cardinality of the action space. This observation provides the foundation for the decision-compression and learning results developed in the subsequent sections.
4.6
Decision Compression
The geometric simplicity results established in the previous subsections suggest a distinction between two fundamentally different notions of complexity in dynamic decision problems. The first concerns the complexity of evaluating future rewards through the optimal value function. The second concerns the complexity of representing the optimal decision rule itself. While these notions are often implicitly conflated in dynamic programming, the geometric framework developed in this paper allows them to be analyzed separately. Definition 19 (Value Complexity). Let V ∗ denote the optimal value function associated with the Markov decision process. The value complexity of the problem is defined by CV = C(V ∗ ),
(56)
where C(·) denotes a nonnegative complexity functional on a prescribed class of value functions. The functional C(·) is intentionally left unspecified. Depending on the application, it may correspond to approximation dimension, description length, parameter count, covering complexity, or another suitable measure of functional complexity. The geometric analysis of Sections 3 and 4 naturally induces a second notion of complexity based on the structure of the optimal policy tessellation. Definition 20 (Decision Complexity). Let Gtop (π ∗ ) = wB CB + wR CR + wF F,
(57)
denote the topological complexity index introduced in Definition 18, where wB , wR , wF ≥ 0. The decision complexity of the optimal policy is defined by CD = Gtop (π ∗ ). page 19
(58)
The quantity CD measures the complexity of the optimal decision rule through the geometry of its induced tessellation rather than through the representation of the value function. This distinction motivates the following notion. Definition 21 (Decision Compression Ratio). The decision compression ratio is defined as DCR =
CV . CD
(59)
Large values of DCR indicate that the optimal policy admits a substantially simpler representation than the associated value function. The geometric simplicity results obtained in Section 3.6 imply that the complexity of the policy tessellation grows at most linearly with the cardinality of the action space. The following theorem formalizes the resulting compression phenomenon. Theorem 16 (Decision Compression Theorem). Suppose that the assumptions of Theorem 15 hold. Then CD = O(|A|).
(60)
CV DCR = Ω . |A|
(61)
Consequently,
Proof. By Theorem 15, CB = O(|A|), CR = |A|, and F = 1. Substituting these relations into (57) yields CD = wB O(|A|) + wR |A| + wF .
(62)
Hence, CD = O(|A|). Combining this relation with Definition 21 gives CV CV =Ω , DCR = O(|A|) |A| which establishes (61). Theorem 16 highlights a structural separation between value complexity and decision complexity. Under the regularity conditions commonly encountered in structured dynamic programs, the geometric complexity of the optimal policy remains controlled by the action space, whereas the complexity of the value function may continue to increase with the complexity of the state space. The optimal policy tessellation can therefore be interpreted as a compressed geometric representation of optimal decision making.
4.7
Discussion
The results developed throughout this section establish a unified connection between classical structural properties of dynamic programs and the geometry of optimal policies. The starting point is the well-established theory of monotone dynamic programming and comparative statics developed by Veinott (1969), Milgrom and Shannon (1994), Topkis (1998), and subsequent authors (Veinott Jr, 1965; Smith and McCardle, 2002). Under standard monotonicity, submodularity, and increasing-differences assumptions, optimal decision rules exhibit ordered behavior and admit threshold representation. The geometric framework introduced in this paper shows that these structural properties have a direct topological interpretation. Monotonicity induces ordered action regions, threshold policies generate low-dimensional decision boundaries, and convex dominance relations produce connected and convex policy regions. Together, these properties imply that optimal policy tessellations possess limited geometric complexity despite the potentially large size of the underlying state space. page 20
A central implication of this observation is the emergence of decision compression. While the complexity of the optimal value function may increase substantially with the dimensionality of the state space, the complexity of the corresponding policy tessellation remains governed primarily by the action space. Consequently, optimal decisions may admit representations that are considerably simpler than those required to describe the full value function. The chain of implications established in this section may be summarized as Monotonicity =⇒ Threshold Structure =⇒ Geometric Simplicity =⇒ Decision Compression.
(63)
This perspective provides a geometric interpretation of structural dynamic programming and motivates the subsequent study of learning and approximation methods that exploit the low-complexity structure of optimal policy tessellations.
5
Structural Geometry of Optimal Policies
5.1
Structural Geometry as a Compressed Representation
The geometric framework introduced in Section 3 associates with each deterministic policy a partition of the state space together with the corresponding boundary structure. The purpose of this subsection is to formalize this correspondence and to establish that the geometry induced by a policy contains all information required to recover the policy itself. Let Π denote the set of admissible deterministic policies. For every policy π ∈ Π, define the collection of action regions Ra (π) = {s ∈ S : π(s) = a} ,
a ∈ A.
(64)
The corresponding tessellation is T (π) = {Ra (π)}a∈A ,
(65)
and the associated boundary structure is Γ(π) =
[
Γaa′ (π),
(66)
a,a′ ∈A a̸=a′
where Γaa′ (π) = ∂Ra (π) ∩ ∂Ra′ (π).
(67)
Definition 22 (Policy Geometry). The geometric representation associated with a policy π ∈ Π is defined by G(π) = T (π), Γ(π) .
(68)
G = {G(π) : π ∈ Π}
(69)
The set
is called the family of policy-induced geometries. The inclusion of Γ(π) in (68) is not required to reconstruct the policy once the tessellation is known. Nevertheless, the boundary structure plays a central role in the complexity measures introduced in Section 3 and will be essential for the learnability results developed later in the paper. The following proposition establishes that the tessellation generated by a deterministic policy uniquely determines that policy.
page 21
Proposition 17. Let π1 , π2 ∈ Π. Then T (π1 ) = T (π2 )
(70)
π1 = π2 .
(71)
if and only if
Consequently, G(π1 ) = G(π2 )
⇐⇒
π1 = π2 .
(72)
Proof. Suppose first that π1 = π2 . Then Ra (π1 ) = Ra (π2 ) for every a ∈ A, which immediately implies T (π1 ) = T (π2 ). Conversely, assume that T (π1 ) = T (π2 ). Let s ∈ S. Since a tessellation is a partition of the state space, there exists a unique action a ∈ A such that s ∈ Ra (π1 ).
(73)
Ra (π1 ) = Ra (π2 ),
(74)
π1 (s) = a = π2 (s).
(75)
Because the tessellations coincide,
and therefore
Since the argument holds for every s ∈ S, it follows that π1 = π2 .
(76)
The final statement follows immediately from the fact that Γ(π) is uniquely determined by T (π). Proposition 17 shows that the policy geometry is not merely a graphical representation of a decision rule. The induced tessellation provides an equivalent description of the policy itself. Consequently, structural properties of optimal policies may be studied through the geometry of the associated tessellations without loss of information. This observation forms the basis of the geometric analysis developed in the remainder of the paper.
5.2
Policy Boundary Principle
The geometric representation developed in the previous subsection establishes that a deterministic policy may be identified with its induced tessellation. We now characterize the precise geometric locus at which variations of the policy can occur. Recall that, for a policy π ∈ Π, the state space is partitioned into action regions T (π) = {Ra (π)}a∈A ,
(77)
and that the associated boundary structure is Γ(π) =
[
Γaa′ (π).
(78)
a,a′ ∈A a̸=a′
The following result identifies the boundary structure as the unique geometric support of decision changes. Theorem 18 (Policy Boundary Principle). Let π ∈ Π be a deterministic policy. Then the following statements hold.
page 22
(i) For every state s ∈ S \ Γ(π),
(79)
there exists an open neighborhood U (s) ⊆ S such that ∀u ∈ U (s).
π(u) = π(s),
(80)
(ii) Every local change of the policy occurs on the boundary structure. More precisely, if s∈S
(81)
is such that every neighborhood of s contains points assigned to at least two distinct actions, then s ∈ Γ(π).
(82)
Consequently, Γ(π) = {s ∈ S : π is not locally constant at s} .
(83)
Proof. We first establish (i). Let s ∈ S \ Γ(π). Since T (π) is a partition of the state space, there exists a unique action a ∈ A such that s ∈ Ra (π). Because s ∈ / Γ(π), the point s belongs to the interior of Ra (π). Hence there exists an open neighborhood U (s) satisfying U (s) ⊆ Ra (π).
(84)
By definition of Ra (π), π(u) = a = π(s),
∀u ∈ U (s),
(85)
which proves (i). We now prove (ii). Suppose that s ∈ / Γ(π). By part (i), there exists an open neighborhood on which the policy is constant. Therefore it is impossible for every neighborhood of s to contain points assigned to different actions. Taking the contrapositive yields “π not locally constant at s” =⇒ s ∈ Γ(π). Combining this implication with part (i) establishes (83). Theorem 18 provides a complete geometric characterization of policy variation. The boundary structure is not merely a collection of interfaces between action regions; it is precisely the set of states at which local decision changes may occur. Consequently, the geometry of a policy may be viewed as consisting of two qualitatively distinct components. The interiors of action regions correspond to locally invariant decision zones, whereas the boundary structure contains the entire locus of decision transitions. This localization property will play a central role in the complexity and compression analyses developed in the subsequent sections.
page 23
5.3
Dimension-Free Policy Geometry
The previous subsection established that the entire variability of a deterministic policy is concentrated on its boundary structure. Consequently, the complexity of a policy may be studied through the combinatorial organization of its action regions and decision boundaries rather than through the ambient state space itself. This observation naturally raises the following question: to what extent does the complexity of a policy geometry depend on the dimension of the underlying state space? To address this issue, we introduce a complexity measure based exclusively on the tessellation structure. Definition 23 (Topological Policy Complexity). Let G(π) = (T (π), Γ(π)) be the geometry induced by a deterministic policy. The associated topological complexity is defined by Ctop (π) = CR (π) + CB (π) + F (π),
(86)
where • CR (π) denotes the region complexity introduced in Definition 10; • CB (π) denotes the boundary complexity introduced in Definition 9; • F (π) denotes the fragmentation index introduced in Definition 11. The quantity Ctop (π) depends only on the combinatorial structure of the tessellation and is therefore independent of metric notions such as volume, diameter, curvature, or ambient dimension. The next result shows that structural dynamic programs generate geometries whose complexity is controlled entirely by the action space. Theorem 19 (Dimension-Free Geometry Theorem). Suppose that the assumptions of Theorems 3, 5, and 8 hold. Then there exists a constant K > 0, depending only on the cardinality of the action space, such that Ctop (π ∗ ) ≤ K|A|.
(87)
Ctop (π ∗ ) = O(|A|),
(88)
d = dim(S).
(89)
CR (π ∗ ) = |A|.
(90)
CB (π ∗ ) = O(|A|).
(91)
F (π ∗ ) = 1.
(92)
Consequently,
independently of
Proof. By Corollary 10,
Furthermore, Theorem 15 implies
Finally, Corollary 11 yields
Combining (90), (91), and (92) with (86) gives Ctop (π ∗ ) = O(|A|).
(93)
Since none of the preceding quantities depends on the ambient dimension d, the resulting bound is dimension-free.
page 24
Theorem 19 shows that, under classical structural assumptions, the complexity of an optimal policy is governed by the organization of the action space rather than by the dimensionality of the state space. This result provides a first indication that policy geometries may admit substantially more compact representations than value-function descriptions in high-dimensional environments. The implications of this phenomenon are investigated in the following subsections.
5.4
Geometric Stability
The previous subsections established that optimal policies admit a compact geometric representation and that all local decision changes are concentrated on the boundary structure. A natural question is whether this geometric organization remains stable under perturbations of the underlying optimization problem. To address this issue, we introduce a quantitative measure of local decision robustness. Definition 24 (Action Gap). Let π ∗ denote an optimal policy and let a∗ (s) = π ∗ (s) be the optimal action at state s ∈ S. The action gap at state s is defined by g(s) = Q∗ (s, a∗ (s)) −
max
a∈A\{a∗ (s)}
Q∗ (s, a).
(94)
The action gap measures the separation between the optimal action and its closest competitor. By construction, g(s) ≥ 0,
(95)
s ∈ S.
Moreover, g(s) = 0 whenever at least two actions attain the same optimal value. The following result links the action gap to the boundary structure introduced in Section 3. Proposition 20. Assume that the functions Q∗ (·, a) are continuous on S for every a ∈ A. Then Γ(π ∗ ) ⊆ {s ∈ S : g(s) = 0} .
(96)
Proof. Let s ∈ Γ(π ∗ ). By Theorem 18, every neighborhood of s contains states assigned to at least two distinct actions. Since the state-action value functions are continuous, at least two competing actions must attain the same value at s. Therefore, g(s) = 0. We now consider perturbations of the optimal state–action value function. Assumption 8 (Uniform Perturbation). Let e a) = Q∗ (s, a) + ∆(s, a), Q(s,
(97)
∥∆∥∞ = sup sup |∆(s, a)| ≤ ε.
(98)
where
s∈S a∈A
e Let π e denote an optimal policy associated with Q. The next theorem shows that policy changes can only occur at states possessing a sufficiently small action gap. Theorem 21 (Boundary Stability Theorem). Under Assumption 8, π e(s) = π ∗ (s) for every state satisfying g(s) > 2ε.
(99)
{s ∈ S : π e(s) ̸= π ∗ (s)} ⊆ {s ∈ S : g(s) ≤ 2ε} .
(100)
Consequently,
page 25
Proof. Fix s ∈ S and let a∗ = π ∗ (s). For every competing action a ̸= a∗ , Q∗ (s, a∗ ) − Q∗ (s, a) ≥ g(s).
(101)
Using Assumption 8, e a∗ ) − Q(s, e a) = Q∗ (s, a∗ ) − Q∗ (s, a) + ∆(s, a∗ ) − ∆(s, a) Q(s, ≥ g(s) − 2ε. Therefore, if g(s) > 2ε, e a∗ ) > Q(s, e a) ∀a ̸= a∗ . Q(s, Hence a∗ remains optimal and π e(s) = π ∗ (s). This proves the claim. Theorem 21 establishes a geometric robustness property of structured optimal policies. States located deep inside an action region possess a strictly positive decision margin and therefore remain unaffected by sufficiently small perturbations. Only states with small action gaps may experience a change in the optimal action. Since the action gap vanishes on the boundary structure, policy modifications are necessarily concentrated near the interfaces separating neighboring action regions. Combined with Theorems 18 and 19, this result shows that the geometric complexity of an optimal policy is not only localized but also stable under small perturbations of the underlying dynamic program.
5.5
Structural Compression Theorem
The preceding subsections established four fundamental properties of policy geometries. First, Proposition 17 showed that the geometry induced by a deterministic policy provides a faithful representation of the policy itself. Second, Theorem 18 established that all local decision changes are concentrated on the boundary structure. Third, Theorem 19 demonstrated that the combinatorial complexity of the geometry remains independent of the ambient state-space dimension. Finally, Theorem 21 showed that the geometric representation is stable under sufficiently small perturbations of the underlying optimization problem. Taken together, these properties suggest that policy geometries provide a compressed description of optimal decision rules. The purpose of this subsection is to formalize this observation. Recall that the decision compression ratio introduced in Section 4 is defined by DCR =
CV , C(G ∗ )
(102)
where CV denotes the complexity of the value-function representation and C(G ∗ ) denotes the complexity of the optimal policy geometry. Theorem 16 established the general lower bound CV DCR = Ω . (103) |A| The next result characterizes the asymptotic implications of this bound for structured dynamic programs. Theorem 22 (Structural Compression Theorem). Suppose that the assumptions of Theorems 19 and 21 hold. Assume furthermore that page 26
(104)
CV = Θ(n), for some problem-size parameter n, and that |A| = O(1).
(105)
DCR = Ω(n).
(106)
C(G ∗ ) = O(|A|).
(107)
CV . DCR = Ω |A|
(108)
n . DCR = Ω |A|
(109)
DCR = Ω(n),
(110)
Then
Proof. By Theorem 19,
Combining (107) with (103) yields
Substituting (104) into (108) gives
Using (105), we obtain
which establishes the result. Theorem 22 shows that the compression achieved by policy geometry is an asymptotic phenomenon rather than a finite-dimensional artifact. As the intrinsic complexity of the value-function representation grows, the complexity of the geometric representation remains controlled by the action structure of the problem. Consequently, the gap between value complexity and geometric complexity increases at least linearly with problem size. Combined with the localization and stability properties established in the previous subsections, this result suggests that policy geometry captures the essential decision structure of a dynamic program using substantially fewer degrees of freedom than conventional value-based representations.
5.6
Geometry and Learnability
The results established in the preceding subsections suggest that the geometric representation of an optimal policy may provide a substantially simpler object to learn than the policy itself. Indeed, Proposition 17 showed that the policy geometry contains the complete information required to reconstruct a deterministic policy, while Theorem 18 established that all decision transitions are concentrated on the boundary structure. This observation motivates a geometric formulation of the policy-learning problem. Definition 25 (Boundary Learning Problem). Let G(π ∗ ) = T (π ∗ ), Γ(π ∗ )
(111)
denote the geometry induced by an optimal policy. The boundary learning problem consists of recovering the boundary structure Γ(π ∗ ) from observed state-action information. The objective of the boundary learning problem is not to estimate the policy value function or to approximate the policy on the entire state space. Instead, the goal is to identify the geometric locus at which optimal decisions change. To quantify the intrinsic difficulty of this task, we introduce the following notion. page 27
b denote an estimator of the boundary structure Definition 26 (Boundary Sample Complexity). Let Γ ∗ Γ(π ). b Γ(π ∗ )), the boundary sample complexity is defined as the For a prescribed accuracy criterion E(Γ, smallest number of observations required to guarantee b Γ(π ∗ ) ≤ δ, E Γ,
(112)
for a given tolerance level δ > 0. The corresponding quantity is denoted by NΓ (δ).
(113)
Definition 26 is intentionally model-independent. No particular statistical framework is assumed at this stage. The purpose of the definition is merely to isolate the learning difficulty associated with the boundary structure itself. The following theorem formalizes the geometric reduction underlying the subsequent learning framework. Theorem 23 (Learnability Through Boundaries). Suppose that the assumptions of Theorems 18, 19, and 21 hold. Then the recovery of the optimal policy π ∗ is equivalent to the recovery of the boundary structure Γ(π ∗ ). More precisely, there exists a reconstruction operator R : Γ(π ∗ ) 7−→ π ∗
(114)
π ∗ = R(Γ(π ∗ )) .
(115)
such that
Consequently, the policy-learning problem admits the equivalent geometric formulation π∗
⇐⇒
Γ(π ∗ ).
(116)
Proof. By Proposition 17, a deterministic policy is uniquely determined by its tessellation. By Theorem 18, the boundary structure constitutes the complete support of policy variation. Therefore, once the boundary structure is known, the corresponding tessellation is uniquely determined by the partition induced by the decision boundaries. Since the tessellation uniquely determines the policy, there exists a reconstruction operator R satisfying (115). This establishes the equivalence (116). Theorem 23 provides the fundamental connection between structural geometry and statistical learning. Rather than treating policy learning as the problem of approximating a decision rule over the entire state space, the theorem shows that learning may be reformulated as the problem of identifying the boundary structure of the optimal policy. Combined with Theorem 19, this observation suggests that the intrinsic difficulty of learning structured optimal policies is governed by the geometric complexity of their decision boundaries rather than by the ambient dimension of the state space. This geometric viewpoint forms the basis of the boundary-learning and active-sampling methodologies developed in the subsequent sections.
5.7
Discussion
The results of this section establish a direct connection between the structural properties of dynamic programs and the geometric organization of their optimal policies. Proposition 17 showed that an optimal policy may be represented without loss of information through its induced tessellation. Consequently, the analysis of optimal decision rules may be reformulated as the analysis of geometric objects defined on the state space. page 28
Building upon this representation, Theorem 18 identified the boundary structure as the unique support of local policy variation. This result isolates the geometric locus at which decision changes occur and separates invariant decision regions from transition regions. The subsequent analysis demonstrated that, under classical structural assumptions, policy geometries possess strong regularity properties. Theorems 19 and 21 showed that the complexity of the geometry remains controlled independently of the ambient state-space dimension and is stable under sufficiently small perturbations of the underlying optimization problem. These properties lead naturally to the compression results established in Theorem 22. Since the geometry retains the complete decision content of the policy while exhibiting substantially lower complexity than value-function representations, structured dynamic programs admit intrinsically compressed policy descriptions. Finally, Theorem 23 showed that the policy-learning problem may be reformulated as a boundaryidentification problem. As a consequence, the complexity of learning is governed by the geometry of decision boundaries rather than by the size of the state space itself. Taken together, the results of this section establish the following chain of implications: Structural Assumptions =⇒ Policy Geometry =⇒ Boundary Structure =⇒ Structural Compression =⇒ Learnability.
(117)
This perspective suggests that the fundamental object underlying many structured decision problems is not the value function itself, but rather the geometry induced by the optimal policy. The next sections exploit this observation to develop learning and approximation methodologies that operate directly on policy geometries.
6
Geometric Complexity and Decision Compression
6.1
Complexity Measures Revisited
The preceding sections introduced two complementary notions of complexity associated with a dynamic decision problem. The first quantity is the value-representation complexity CV , defined in Definition 19, which measures the complexity of representing the optimal value function. The second quantity is the decision complexity CD = C(G ∗ ),
(118)
introduced in Definition 20, which measures the complexity of the optimal policy geometry. These quantities describe fundamentally different objects. The quantity CV characterizes the complexity of the numerical solution of the dynamic program through the representation of the optimal value function. In contrast, CD characterizes the complexity of the optimal decision rule itself through the geometric organization of its action regions and decision boundaries. The distinction between these two notions is central to the analysis developed in this section. Throughout the remainder of the paper, value complexity and decision complexity are treated as conceptually distinct quantities and are analyzed separately. The structural results established in Sections 4 and 5 imply that the decision complexity of structured dynamic programs remains controlled by the action structure of the problem. More precisely, Theorem 19 established that Ctop (π ∗ ) = O(|A|),
(119)
while Theorem 22 showed that the resulting compression ratio satisfies DCR = Ω(n), whenever CV = Θ(n) and |A| = O(1).
page 29
(120)
The purpose of the present section is not to establish additional geometric regularity properties. Rather, it is to investigate the quantitative implications of these complexity relationships and to characterize the compression mechanisms induced by policy geometry. Accordingly, all subsequent results will be expressed in terms of the pair CV , CD , which provides a unified framework for comparing value-based and geometry-based representations of optimal decision rules.
6.2
Compression Regimes
The discussion of Section 6.1 establishes that value complexity and decision complexity may exhibit fundamentally different scaling behaviors. To study this phenomenon systematically, we introduce a classification of compression regimes based on the asymptotic behavior of the decision compression ratio. Throughout this subsection, consider a sequence of decision problems {Mn }n≥1 , indexed by a complexity parameter n. The parameter n may represent, depending on the application, the number of states, the dimension of the state space, the discretization level, or any other quantity governing the growth of the decision problem. For each problem Mn , let CV (n) denote the corresponding value complexity and let CD (n) denote the associated decision complexity. The decision compression ratio is therefore given by DCR(n) =
CV (n) . CD (n)
(121)
The asymptotic growth of DCR(n) quantifies the extent to which policy geometries provide more compact representations than value functions. The following definitions distinguish several compression regimes. Definition 27 (Weak Compression). The family {Mn }n≥1 is said to exhibit weak compression if lim inf DCR(n) > 1. n→∞
(122)
Weak compression corresponds to a regime in which geometric representations remain asymptotically more compact than value-based representations, although the compression gain remains uniformly bounded. Definition 28 (Polynomial Compression). The family {Mn }n≥1 is said to exhibit polynomial compression if there exist constants c > 0 and α > 0 such that DCR(n) ≥ c nα
(123)
for all sufficiently large n. Polynomial compression characterizes situations in which the gap between value complexity and decision complexity grows polynomially with problem size. Definition 29 (Strong Compression). The family {Mn }n≥1 is said to exhibit strong compression if DCR(n) = Ω(n).
(124)
Strong compression corresponds to a regime in which decision complexity grows at least one asymptotic order more slowly than value complexity. The three notions introduced above form a hierarchy: Strong Compression =⇒ Polynomial Compression =⇒ Weak Compression.
(125)
This classification provides a unified language for describing compression phenomena independently of any particular representation architecture. In the subsequent subsections, we investigate the structural conditions under which policy geometries achieve polynomial or strong compression.
page 30
6.3
Scaling Laws
The compression regimes introduced in Section 6.2 provide a qualitative classification of asymptotic compression phenomena. We now establish quantitative scaling laws describing how the decision compression ratio evolves with problem size. The key observation is that, under the structural assumptions developed in Sections 4 and 5, the growth of decision complexity remains controlled by the action structure of the problem, whereas value complexity may increase substantially with the size of the state space. The following theorem formalizes this relationship. Theorem 24 (Scaling Law for Decision Compression). Consider a family of decision problems {Mn }n≥1 satisfying the assumptions of Theorem 15. Assume that the corresponding value complexity satisfies CV (n) = Θ nβ , β > 0. (126) Then the decision compression ratio satisfies β n DCR(n) = Ω . |A|
(127)
CD (n) = C(Gn∗ ) ,
(128)
Proof. By Definition 20,
where Gn∗ denotes the optimal policy geometry associated with Mn . Theorem 15 implies the existence of a constant K > 0, independent of n, such that CD (n) ≤ K|A|
(129)
for all sufficiently large n. Furthermore, assumption (126) implies the existence of constants c1 , c2 > 0 such that c1 nβ ≤ CV (n) ≤ c2 nβ
(130)
CV (n) . CD (n)
(131)
c1 nβ . K|A|
(132)
for all sufficiently large n. Using Definition 21, DCR(n) = Combining (129), (130), and (131), we obtain DCR(n) ≥ Therefore,
β n DCR(n) = Ω , |A|
(133)
which establishes the result. Theorem 24 shows that the asymptotic compression achieved by policy geometries is determined by the growth rate of value complexity rather than by the dimension of the state space itself. In particular, whenever the action space remains fixed or grows more slowly than CV (n), the compression ratio diverges with problem size.
page 31
Corollary 25 (Linear Compression Regime). Suppose that CV (n) = Θ(n)
(134)
|A| = O(1).
(135)
DCR(n) = Ω(n).
(136)
and Then
Proof. The result follows immediately from Theorem 24 with β = 1. Corollary 25 recovers, as a particular case, the linear compression phenomenon established previously in Theorem 22.
6.4
Exponential Compression
The scaling law established in Theorem 24 provides a general relationship between value complexity and decision compression. An important regime arises when the complexity of representing the optimal value function grows exponentially with the dimension of the state space. Such behavior is commonly associated with the curse of dimensionality in dynamic programming (Bellman, 1957; Bertsekas, 2012; Powell, 2007). The following corollary characterizes the implications of this phenomenon for policy geometries. Corollary 26 (Exponential Compression). Consider a family of decision problems {Md }d≥1 indexed by the dimension d of the state space. Suppose that the value complexity satisfies (137) CV (d) = Θ 2d . Then the decision compression ratio satisfies d 2 DCR(d) = Ω . |A|
(138)
Proof. Applying Theorem 24 with CV (d) = Θ(2d ), yields d CV (d) 2 DCR(d) = Ω =Ω . |A| |A| This proves the result. Corollary 26 shows that exponential growth of value complexity induces an exponential separation between value-based and geometry-based representations of optimal decision rules. This phenomenon is a direct consequence of the structural properties established in Sections 4 and 5. Indeed, Theorem 19 implies that the complexity of the optimal policy geometry remains controlled by the action structure of the problem and does not scale with the dimension of the state space. Consequently, whenever value representations exhibit exponential growth with dimension, the compression advantage associated with policy geometries increases exponentially as well. The result should therefore be interpreted as a structural separation theorem: although the representation of optimal value functions may become exponentially complex, the geometric representation of optimal policies remains governed by the complexity of the action partition rather than by the ambient dimension.
page 32
6.5
Boundary Compression
The preceding results suggest that the geometric complexity of a policy is not distributed uniformly across the state space. Indeed, Theorem 18 established that all local decision changes are concentrated on the boundary structure [ Γ= Γaa′ . a,a′ ∈A a̸=a′
This localization property naturally raises the question of whether the complexity of the entire policy geometry is asymptotically determined by the complexity of its boundary structure. The following theorem answers this question in the affirmative. Theorem 27 (Boundary Compression Theorem). Consider a family of structured decision problems {Mn }n≥1 satisfying the assumptions of Theorem 15. Let CB (n) denote the corresponding boundary complexity and let CD (n) = C(Gn∗ ) denote the associated decision complexity. Then CD (n) = Θ(CB (n)) .
(139)
Proof. By Definition 20, the decision complexity is determined by the geometric characteristics of the optimal policy geometry. In particular, CD (n) = Φ(CB (n), CR (n), F (n), κ(n)) ,
(140)
for some complexity functional Φ. Theorem 15 implies that the region complexity, fragmentation index, and geometric irregularity remain uniformly bounded. Consequently, there exists a constant K > 0 such that CR (n) + F (n) + κ(n) ≤ K
(141)
for all sufficiently large n. Therefore, the only geometric quantity capable of exhibiting asymptotic growth is the boundary complexity CB (n). It follows that there exist constants c1 , c2 > 0 such that c1 CB (n) ≤ CD (n) ≤ c2 CB (n)
(142)
for all sufficiently large n. Hence, CD (n) = Θ(CB (n)), which establishes the result. Theorem 27 shows that the asymptotic complexity of a structured policy geometry is entirely governed by its boundary structure. Combined with Theorem 18, the result yields a particularly simple interpretation of policy complexity. The interiors of action regions correspond to locally invariant decision zones and therefore contribute only bounded complexity. In contrast, all asymptotically relevant geometric information is concentrated on the set of decision boundaries. Consequently, structured policy geometries admit a compressed representation in which boundary complexity becomes the fundamental quantity governing decision complexity. Corollary 28 (Boundary-Based Compression Ratio). Under the assumptions of Theorem 27, CV (n) DCR(n) = Θ . (143) CB (n) V (n) Proof. Combining DCR(n) = CCD (n) with CD (n) = Θ(CB (n)) immediately yields the result.
page 33
6.6
Information-Theoretic Compression
The geometric compression results established in the preceding subsections admit a natural informationtheoretic interpretation. Rather than measuring complexity through geometric characteristics alone, one may ask how many bits are required to describe an optimal policy or, alternatively, its associated boundary structure. This perspective is closely related to the Minimum Description Length (MDL) principle introduced by Rissanen (1978) and further developed by Grünwald (2007). Throughout this subsection, all description lengths are defined relative to a fixed admissible family of prefix codes. Definition 30 (Policy Description Length). Let Π denote a class of admissible deterministic policies. The policy description length of π ∗ ∈ Π, denoted by LΠ (π ∗ ), is the minimum number of bits required to encode π ∗ within the coding class under consideration. Definition 31 (Boundary Description Length). Let Γ∗ = Γ(π ∗ ) denote the boundary structure induced by the optimal policy. The boundary description length is defined by LΓ (Γ∗ ), the minimum number of bits required to encode Γ∗ within the same coding class. The following result establishes that, under the structural assumptions developed throughout the paper, the informational complexity of an optimal policy is asymptotically equivalent to that of its boundary structure. Theorem 29 (Information-Theoretic Compression Theorem). Consider a family of structured decision problems {Mn }n≥1 satisfying the assumptions of Theorem 27. Then there exist constants K1 , K2 > 0 such that LΓ (Γ∗n ) − K1 ≤ LΠ (πn∗ ) ≤ LΓ (Γ∗n ) + K2
(144)
LΠ (πn∗ ) = Θ(LΓ (Γ∗n )) .
(145)
for all sufficiently large n. Consequently, Proof. By Theorem 18, the optimal policy is locally constant on each connected component of S \ Γ∗n . Hence, once the boundary structure Γ∗n is specified, reconstructing the policy requires only the assignment of action labels to the resulting regions. Since the action set A is finite, the number of bits required to encode these labels is bounded independently of n. Therefore, there exists a constant K2 > 0 such that LΠ (πn∗ ) ≤ LΓ (Γ∗n ) + K2 .
(146)
Conversely, the boundary structure is uniquely determined by the policy through the induced tessellation (Proposition 17). Hence there exists a constant K1 > 0 such that LΓ (Γ∗n ) ≤ LΠ (πn∗ ) + K1 .
(147)
Combining (146) and (147) yields (144). The asymptotic relation (145) follows immediately. Theorem 29 provides an information-theoretic counterpart to Theorem 27. The result shows that the informational content of an optimal policy is asymptotically equivalent to the informational content of its boundary structure. In particular, the interiors of action regions contribute only a bounded amount of additional information once the boundaries have been specified. Consequently, structured policy geometries achieve compression not only in a geometric sense but also in a description-length sense. The dominant informational object is the boundary structure itself. Corollary 30 (Boundary Information Dominance). Under the assumptions of Theorem 29, LΠ (πn∗ ) = Θ(LΓ (Γ∗n )) = Θ(CB (n)) , whenever the boundary description length is proportional to boundary complexity. Proof. The first equivalence follows from Theorem 29. The second follows from the proportionality assumption and Theorem 27. page 34
(148)
6.7
Limits of Compression
The compression results established throughout this section rely fundamentally on the structural assumptions developed in Sections 4 and 5. In particular, the scaling laws, boundary-compression results, and information-theoretic compression properties all depend on the existence of regular policy geometries characterized by monotonicity, threshold representations, bounded fragmentation, and controlled boundary complexity. The purpose of the present subsection is to clarify the limits of this mechanism and to identify situations in which the compression advantage may deteriorate or disappear. The key observation is that decision compression is ultimately a consequence of geometric regularity. Whenever this regularity is lost, the complexity of the policy geometry may increase substantially and become comparable to the complexity of the underlying value representation. The following proposition formalizes this observation. Proposition 31 (Limits of Decision Compression). Consider a family of decision problems {Mn }n≥1 . Suppose that at least one of the following conditions holds: (i) the fragmentation index is unbounded, F (n) → ∞; (ii) the convex-region property of Theorem 8 fails, allowing optimal action regions to develop arbitrarily complex nonconvex geometries; (iii) the monotonicity assumptions of Section 4.1 are violated, so that the threshold representations established in Section 4.3 need not exist. Then the geometric complexity of the optimal policy is no longer uniformly controlled by the action structure of the problem. Moreover, there exist families of decision problems for which CD (n) = Θ CV (n) .
(149)
Proof. The compression results established in Sections 4 and 5 depend critically on the existence of a geometrically simple policy representation. Under monotonicity, convexity, and threshold structures, the complexity of the policy geometry remains controlled by a bounded number of action regions and decision boundaries. This property yields the compression phenomena described in Theorems 24, 27, and 29. If fragmentation becomes unbounded, however, the number of connected components required to represent the policy geometry may grow proportionally to the complexity of the value representation itself. Similarly, if convexity is lost, action regions may develop arbitrarily intricate geometric structures whose description requires a number of parameters comparable to that required for representing the value function. Finally, when monotonicity fails, threshold representations need not exist and the boundary structure may become arbitrarily irregular, eliminating the geometric simplicity established previously. Consequently, the complexity of the policy geometry may scale at the same asymptotic rate as the complexity of the value representation, yielding (149). Proposition 31 shows that decision compression is not a universal property of dynamic programs. Rather, it is a consequence of the structural regularities induced by monotonicity, convexity, and bounded fragmentation. From a geometric perspective, compression emerges because optimal policies can be represented through a relatively small collection of regular action regions separated by simple decision boundaries. When these regularity properties disappear, the policy geometry itself may become highly complex, thereby eliminating the compression advantage. The results of this section should therefore be interpreted as identifying a broad class of structured dynamic programs for which geometric representations provide compressed descriptions of optimal decision rules, rather than as a universal statement applying to arbitrary Markov decision processes. page 35
6.8
Discussion
The results developed throughout this section establish a coherent relationship between structural regularity, policy geometry, and decision complexity. The starting point is the structural framework introduced in Section 4. Monotonicity, threshold representations, convex action regions, and bounded fragmentation imply that optimal policies admit geometrically regular representations. These structural properties induce policy geometries whose complexity remains controlled by the action structure of the problem rather than by the size of the state space. Building upon this geometric characterization, Sections 6.3-6.6 demonstrate that policy geometries constitute compressed representations of optimal decision rules. The scaling laws show that compression increases with value complexity, the boundary-compression results identify decision boundaries as the dominant source of geometric complexity, and the information-theoretic analysis establishes an equivalent conclusion from a description-length perspective. Taken together, these results yield the following conceptual chain: Structure =⇒ Simple Geometry =⇒ Compression.
(150)
More specifically, Theorems 18 and 27 show that the informational and geometric content of a structured policy is concentrated near its boundary structure. Consequently, compression emerges because optimal policies can be represented through a comparatively small collection of regular regions separated by simple decision boundaries. At the same time, Proposition 31 clarifies that this phenomenon is not universal. Compression is a consequence of structural regularity and may deteriorate when monotonicity, convexity, or bounded fragmentation are lost. The theory therefore identifies a broad class of structured dynamic programs for which geometric representations are substantially more compact than value-based representations. The practical significance of these results lies in their implications for scalability. Whenever decision complexity grows substantially more slowly than value complexity, geometric representations provide a mechanism for mitigating the representational burden associated with large-scale dynamic programs. Compression =⇒ Scalability.
(151)
This observation provides the conceptual foundation for the learning, approximation, and algorithmic developments that follow.
7
Learning Policy Geometry
7.1
Geometric Learning Problem
Sections 3, 4, 5, and 6 established that optimal policies arising from structured dynamic programs admit geometrically regular representations. More precisely, Proposition 17 showed that a deterministic policy is uniquely characterized by its induced tessellation, while Theorem 18 identified the boundary structure as the unique locus at which decision changes occur. Furthermore, Theorem 23 established that the optimal policy can be reconstructed from its boundary geometry. Consequently, the learning problem considered in this paper differs fundamentally from classical value-function or policy-learning formulations. Rather than estimating the optimal value function V ∗ , the optimal state-action value function Q∗ , or the optimal policy π ∗ directly, the objective is to estimate the geometric object that carries the decision information. We begin by formalizing the object of interest. Definition 32 (Target Boundary Geometry). Let Γ∗ = Γ(π ∗ ) denote the boundary structure induced by the optimal policy. The set Γ∗ =
[
Γaa′
a,a′ ∈A a̸=a′
is called the target boundary geometry. page 36
(152)
The target boundary geometry constitutes the primary object of statistical inference throughout this section. The available information is represented abstractly through a collection of observations Dn = {Z1 , . . . , Zn },
(153)
where each observation Zi may contain information about the optimal decision structure. No specific sampling mechanism is imposed at this stage. The observations may arise from simulation, state queries, optimal-action evaluations, trajectory data, or any other information source capable of providing evidence regarding the underlying policy geometry. The goal is to construct an estimator bn = Γ b n (Dn ) Γ
(154)
of the unknown boundary structure Γ∗ . Definition 33 (Geometric Learning Problem). Given observations Dn , the geometric learning probb n such that lem consists of constructing an estimator Γ b n −→ Γ∗ Γ
(155)
under an appropriate notion of geometric convergence. The formulation above deliberately separates the learning target from the learning mechanism. The object to be estimated is the boundary geometry itself, whereas the statistical model governing the observations will be introduced subsequently. The justification for this viewpoint follows directly from the structural results established previously. By Theorem 23, there exists a reconstruction operator R : Γ∗ 7−→ π ∗ ,
(156)
such that the optimal policy can be recovered from its boundary structure. Consequently, learning the optimal policy is equivalent to learning the target boundary geometry in the sense that Γ∗
⇐⇒
π∗.
(157)
This equivalence transforms the original decision-learning problem into a geometric estimation problem. The remainder of this section investigates the statistical consequences of this reformulation and establishes conditions under which the boundary geometry can be learned efficiently.
7.2
Boundary Learning Principle
The geometric learning problem formulated in Section 7.1 identifies the target boundary geometry Γ∗ as the primary object of statistical inference. The purpose of the present subsection is to establish a structural principle that motivates this choice and guides the learning methodology developed in the remainder of the paper. The key observation is that the geometric representation of a structured policy exhibits a strong localization property. By Theorem 18, the optimal policy is locally constant on every connected component of S \ Γ∗ .
(158)
Consequently, decision changes may occur only on the boundary structure itself. This property implies that observations collected far from the boundary geometry carry little information regarding the location of decision transitions. Indeed, whenever a state belongs to the interior of an action region, all sufficiently small perturbations of that state produce identical optimal decisions. In contrast, observations located near the boundary geometry contain information about the transition between competing actions and therefore provide information regarding the structure of the optimal policy. The following principle summarizes this observation. page 37
Principle 1 (Boundary Learning Principle). For structured dynamic programs satisfying the assumptions of Sections 4 and 5, the statistically informative component of the policy geometry is concentrated near the target boundary geometry Γ∗ . Consequently, efficient learning of the optimal policy may be reduced to the estimation of the boundary structure rather than the estimation of the entire policy over the state space. The principle above follows directly from the combination of two structural results established previously. First, Theorem 18 shows that policy variation is confined to the boundary geometry. Second, Theorem 27 establishes that the complexity of a structured policy is asymptotically governed by the complexity of its boundary structure. Together, these results imply that the dominant source of statistical uncertainty lies in the estimation of Γ∗ . From a learning perspective, the role of the boundary geometry is therefore analogous to that of a low-dimensional sufficient representation of the decision rule. The objective is not to recover the optimal action at every state individually, but rather to identify the geometric interfaces separating the action regions. This viewpoint provides the conceptual foundation for the sample-complexity, active-sampling, and reconstruction results developed in the subsequent subsections.
7.3
Statistical Learning Model
Sections 7.1 and 7.2 identify the target boundary geometry Γ∗ as the primary object of statistical inference. The purpose of the present subsection is to introduce the probabilistic framework within which boundary estimation will be analyzed. No convergence rates or sample-complexity guarantees are established at this stage. Rather, the objective is to define the statistical objects and loss functions that will be used throughout the remainder of the section. Observation Model. Let Dn = {Z1 , . . . , Zn } denote a collection of observations generated according to an unknown probability measure P defined on a measurable space (Z, B). The framework deliberately remains agnostic regarding the sampling mechanism. The observations may arise from simulation, state-action evaluations, trajectory data, policy queries, or any other information source capable of providing information about the underlying policy geometry. Geometric Hypothesis Space. Let G denote a family of admissible boundary geometries. The target boundary geometry Γ∗ ∈ G is assumed to belong to this family. The specification of G is intentionally left abstract. Subsequent complexity bounds will depend on structural characteristics of this class rather than on the ambient state space itself. Boundary Estimators. A geometric learning procedure is a measurable mapping (159)
b n : Z n −→ G, Γ which associates to every dataset Dn an estimated boundary geometry
(160)
bn = Γ b n (Dn ). Γ b n is therefore a random element of G. The estimator Γ Definition 34 (Hausdorff Distance). Let A, B ⊆ S be nonempty closed subsets. The Hausdorff distance between A and B is defined by ( ) dH (A, B) = max sup inf d(x, y), sup inf d(x, y) , x∈A y∈B
where d(·, ·) denotes the metric on S.
page 38
y∈B x∈A
(161)
The Hausdorff distance provides a natural notion of geometric discrepancy because it measures the maximal localization error between two boundary structures. Definition 35 (Boundary Estimation Error). The estimation error associated with a boundary estib n is defined by mator Γ b n , Γ∗ . En = dH Γ b n is Definition 36 (Geometric Risk). The geometric risk of a boundary estimator Γ h i b n ) = E dH Γ b n , Γ∗ , RG (Γ
(162)
(163)
whenever the expectation exists. The quantity RG plays the role of a statistical risk function adapted to geometric estimation. Unlike classical policy-learning criteria, it measures performance directly in terms of the accuracy with which the decision boundaries are recovered. The framework introduced above deliberately separates three distinct objects: 1. the unknown target geometry Γ∗ ; 2. the admissible geometric class G; bn . 3. the estimator Γ This separation will allow the subsequent analysis to relate statistical learnability to geometric complexity. In particular, the sample-complexity results developed below will depend on structural characteristics of the boundary geometry rather than on the cardinality of the state space or the complexity of the value function representation.
7.4
Boundary Sample Complexity
The statistical framework introduced in Section 7.3 provides a probabilistic formulation of the geometric learning problem. The purpose of the present subsection is to quantify the amount of information required to estimate the target boundary geometry Γ∗ with prescribed accuracy. The key question is whether the statistical difficulty of the learning problem is governed by the size of the state space or by the complexity of the boundary geometry itself. We begin by introducing the corresponding notion of sample complexity. Definition 37 (Boundary Sample Complexity). Let ε > 0 and δ ∈ (0, 1). The boundary sample complexity is defined as n o b n such that P dH Γ b n , Γ∗ ≤ ε ≥ 1 − δ , NΓ (ε, δ) = inf n ≥ 1 : ∃ Γ
(164)
where dH denotes the Hausdorff distance introduced in Definition 34. The quantity NΓ (ε, δ) represents the smallest number of observations required to localize the target boundary geometry with geometric accuracy ε and confidence level 1 − δ. The structural results established in Sections 5 and 6 suggest that the complexity of the learning problem should be governed by the complexity of the boundary geometry rather than by the ambient state space. Indeed, Theorem 18 showed that policy variation is entirely concentrated on Γ∗ , while Theorem 27 established that the complexity of the optimal policy geometry is asymptotically equivalent to the complexity of its boundary structure. The following theorem formalizes this observation. Theorem 32 (Boundary Sample Complexity Principle). Suppose that the assumptions of Sections 4 and 5 hold. Then the sample complexity of the geometric learning problem is governed by the boundary complexity CB . More precisely, there exists a nondecreasing function
page 39
Ψ : R3+ → R+
(165)
NΓ (ε, δ) ≤ Ψ(CB , ε, δ) ,
(166)
such that
and the dependence on the state-space cardinality |S| enters only through its influence on CB . Proof. By Theorem 18, the optimal policy is locally invariant away from Γ∗ . Consequently, observations collected in the interior of action regions do not contribute to the localization of decision transitions. The informative component of the learning problem is therefore restricted to the boundary structure. Furthermore, Theorem 27 establishes that the effective complexity of the policy geometry is characterized by CB . Hence any estimator of Γ∗ requires information only about a geometric object whose complexity is measured by CB , which implies that the corresponding sample complexity is controlled by this quantity rather than by the ambient state space. Theorem 32 constitutes the first statistical consequence of the geometric framework developed in the previous sections. Its main implication is conceptual rather than quantitative. The result establishes that the relevant notion of complexity for policy learning is the complexity of the decision boundaries and not the complexity of the state space itself. Subsequent sections will exploit this principle to derive more explicit learning guarantees and active-sampling strategies adapted to the geometry of optimal policies.
7.5
Active Boundary Sampling
The preceding subsections establish that the statistical complexity of policy learning is governed by the geometry of the decision boundaries. A natural question therefore arises: Where should observations be collected in order to estimate the target boundary geometry most efficiently? The purpose of the present subsection is not to introduce a specific learning algorithm, but rather to identify the regions of the state space that contain the largest amount of information about the unknown boundary structure. Decision Gaps and Boundary Geometry. Recall from Definition 17 that, for every pair of actions a, a′ ∈ A, ∆aa′ (s) = Q∗ (s, a) − Q∗ (s, a′ ),
(167)
denotes the corresponding action-difference function. Furthermore, Corollary 6 established that pairwise decision boundaries admit the representation Γaa′ = {s ∈ S : ∆aa′ (s) = 0} .
(168)
Hence, the geometry of the optimal policy is completely determined by the zero-level sets of the action-difference functions. The following definition identifies the states that are geometrically close to decision transitions. Definition 38 (Boundary Neighborhood). Let τ > 0. For each pair of actions a, a′ ∈ A, define Baa′ (τ ) = {s ∈ S : |∆aa′ (s)| ≤ τ } .
(169)
The global boundary neighborhood is B(τ ) =
[
Baa′ (τ ).
a,a′ ∈A a̸=a′
page 40
(170)
By construction, Γ∗ ⊆ B(τ ),
∀τ > 0.
(171)
Moreover, \
B(τ ) = Γ∗ .
(172)
τ >0
Thus, B(τ ) provides a geometric approximation of the target boundary structure. The next principle identifies the regions of maximal statistical relevance. Principle 2 (Active Boundary Sampling Principle). Among all states in the state space, those belonging to boundary neighborhoods B(τ ) contain the largest amount of information regarding the location of the target boundary geometry Γ∗ . Consequently, observation mechanisms that allocate a larger fraction of samples to B(τ ) are expected to estimate the policy geometry more efficiently than observation mechanisms based on uniform exploration of the state space. The intuition follows directly from Theorem 18. Inside the interior of an action region, the optimal policy is locally invariant. Additional observations therefore provide little information regarding the location of decision transitions. In contrast, states satisfying |∆aa′ (s)| ≈ 0
(173)
lie near competing action regions. Small perturbations of the state may then alter the identity of the optimal action, making such observations particularly informative for boundary localization. The principle above should be interpreted as a structural guideline rather than a concrete algorithmic prescription. Its role is to identify the regions of the state space that concentrate the informational content relevant for learning. The statistical consequences of this localization phenomenon are developed in the subsequent subsections, where boundary-focused learning procedures are shown to exploit the geometric compression properties established in Sections 5 and 6.
7.6
Policy Reconstruction
The previous subsections formulate policy learning as a geometric estimation problem whose objective is the recovery of the target boundary geometry Γ∗ . The purpose of the present subsection is to establish the converse link between geometry estimation and policy estimation. The key question is the following: If the boundary geometry can be estimated accurately, does this suffice to recover the optimal policy? The answer follows from the structural results established in Sections 5 and 6. Recall that Theorem 23 established that the optimal policy is uniquely determined by its boundary geometry. Consequently, the estimation of Γ∗ naturally induces an estimator of the optimal policy. Definition 39 (Policy Reconstruction Operator). Let G denote the admissible family of boundary geometries introduced in Section 7.3. A policy reconstruction operator is a mapping R : G −→ Π,
(174)
which associates with every admissible boundary geometry Γ ∈ G the unique deterministic policy consistent with the induced tessellation. The existence and uniqueness of R follow from Theorem 23 together with Proposition 17. b n , the corresponding policy estimator is defined through geometric Given a boundary estimator Γ reconstruction. page 41
b n ∈ G be a boundary estimator. Definition 40 (Reconstructed Policy Estimator). Let Γ The reconstructed policy estimator is bn . π bn = R Γ
(175)
The next theorem establishes that consistency of boundary estimation implies consistency of policy reconstruction. Theorem 33 (Policy Reconstruction Principle). Suppose that b n , Γ∗ −→ 0 dH Γ
in probability. (176) b n converges to the optimal policy π ∗ in the Then the reconstructed policy sequence π bn = R Γ sense that policy discrepancies can occur only inside neighborhoods whose size vanishes with
b n , Γ∗ . dH Γ
(177)
Proof. By Theorem 18, the optimal policy is locally constant away from the boundary geometry. Therefore, any discrepancy between bn and π ∗ must arise from inaccuracies in the localization of π ∗ b decision boundaries. Since dH Γn , Γ → 0, the estimated boundaries converge geometrically to the true boundaries. Consequently, the regions in which policy disagreement may occur shrink toward the true boundary geometry. Outside these shrinking neighborhoods, the reconstructed policy coincides with the optimal policy. The claim follows. Theorem 33 provides the final link in the geometric learning framework. Combined with Theorem 32 and Principle 2, it shows that policy learning can be reduced to three successive steps: 1. estimate the boundary geometry; 2. localize the decision boundaries accurately; 3. reconstruct the policy through the operator R. Thus, the statistical analysis of policy learning may be conducted entirely through the geometry of decision boundaries.
7.7
Learning Guarantees
The preceding subsections establish a complete geometric formulation of the policy-learning problem. More precisely, 1. the target object of inference is the boundary geometry Γ∗ ; 2. the statistical complexity of the learning problem is governed by the complexity of this geometry; 3. policy estimators are obtained through the reconstruction operator R. The purpose of the present subsection is to establish the final link between geometric estimation accuracy and decision accuracy. To do so, we introduce a generic notion of policy disagreement. Definition 41 (Policy Disagreement Risk). Let µ be a probability measure on the state space S. For a policy estimator π bn , the policy disagreement risk is defined by Rπ (b πn ) = µ({s ∈ S : π bn (s) ̸= π ∗ (s)}) .
(178)
The quantity Rπ measures the probability mass of states on which the reconstructed policy disagrees with the optimal policy. The next theorem establishes that geometric estimation error controls policy error. page 42
Theorem 34 (Geometric Learning Guarantee). Suppose that the assumptions of Theorem 33 hold. Then there exists a nondecreasing function Φ : R+ → R+
(179)
Φ(0) = 0,
(180)
satisfying
such that every reconstructed policy estimator bn π bn = R Γ
(181)
b n , Γ∗ . Rπ (b πn ) ≤ Φ dH Γ
(182)
b n , Γ∗ −→ 0 dH Γ
(183)
Rπ (b πn ) −→ 0.
(184)
satisfies
Consequently,
implies
Proof. By Theorem 18, the optimal policy is locally constant away from the boundary geometry. Furthermore, Theorem 33 establishes that policy discrepancies can occur only inside neighborb n , Γ∗ . hoods whose size is controlled by the Hausdorff distance dH Γ Therefore, the disagreement set {s : π bn (s) ̸= π ∗ (s)}
(185)
is contained in a neighborhood of Γ∗ whose radius vanishes together with the geometric estimation error. The measure of this neighborhood defines a nondecreasing function Φ satisfying Φ(0) = 0, b n , Γ∗ → 0 gives (184). which yields (182). Taking the limit as dH Γ Theorem 34 constitutes the principal statistical consequence of the geometric learning framework. Combined with Theorem 32, Principle 2, and Theorem 33, it establishes the following chain of implications: Boundary Complexity =⇒Boundary Learnability =⇒ Boundary Estimation =⇒ Policy Reconstruction =⇒ Policy Accuracy.
Thus, the learning performance of structured dynamic programs can be analyzed entirely through the geometry of their decision boundaries.
7.8
Discussion
The results developed throughout this section provide a geometric interpretation of policy learning for structured dynamic programs. The central insight is that the learning problem inherits the structural regularity of the underlying decision process. Sections 4 and 5 showed that structural properties of the optimal value function induce regular geometric properties of the optimal policy. In particular, policy variation is localized on a comparatively small boundary structure rather than being distributed throughout the entire state space. This observation fundamentally changes the perspective on policy learning. Instead of viewing the objective as the estimation of a value function or a decision rule defined over the whole state space, the learning problem may be reformulated as the estimation of the target boundary geometry Γ∗ . The boundary learning principle, the sample-complexity analysis, the active-sampling framework, and the page 43
reconstruction results collectively show that the statistically relevant information is concentrated on the decision boundaries. The resulting chain of implications may be summarized as Structure =⇒ Geometry =⇒ Γ∗ =⇒ Learnability.
(186)
The learning consequences of this geometric viewpoint follow directly from the compression results established in Section 6. In particular, Theorem 27 identified the boundary structure as the effective carrier of decision complexity, while Theorem 32 showed that the statistical complexity of learning is governed by this same object. Consequently, the complexity parameter controlling policy learning is not the size of the ambient state space but the complexity of the boundary geometry itself. At a conceptual level, the results suggest the relationship CD = Θ(CB )
=⇒
NΓ = O(CB ),
(187)
up to the accuracy and confidence factors appearing in the corresponding statistical guarantees. Taken together, Sections 5, 6, and 7 establish that the learnability of structured optimal policies is determined by the geometry of their decision boundaries. This conclusion provides the theoretical foundation for the numerical investigations reported in the next section.
8
Numerical Validation of Geometric Learning Theory
The purpose of this section is not to establish the empirical superiority of a particular learning algorithm, but rather to assess whether the geometric, statistical, and information-theoretic predictions developed in Sections 3–7 are supported by controlled numerical experiments. Throughout the paper, the theoretical analysis identifies the decision-boundary geometry Γ⋆ = Γ(π ⋆ ), rather than the value function or the optimal policy itself, as the primary object of inference. Consequently, every numerical experiment is designed to estimate a theoretical quantity introduced earlier, such as the b n , the Hausdorff risk dH (Γ b n , Γ⋆ ), the policy disagreement risk Rπ , the decision boundary estimator Γ complexity CD , or the Decision Compression Ratio (DCR), and to compare the observed behaviour with the corresponding theoretical prediction. Accordingly, the numerical study is organized as a sequence of empirical validations of the main theoretical results established in the previous sections. Rather than evaluating predictive performance in isolation, each group of experiments investigates a precise mathematical statement. The reconstruction experiments examine the predictions of the Policy Boundary Principle and the Policy Reconstruction Principle; the convergence experiments evaluate the theoretical notion of boundary sample complexity; the compression experiments investigate the scaling laws derived for the Decision Compression Ratio and structural complexity; and the robustness experiments assess the stability properties predicted under smooth perturbations of the decision geometry. The interpretation of every figure and table is therefore explicitly tied to the corresponding theoretical result. To ensure that the empirical evidence remains directly interpretable from a statistical perspective, all experiments are conducted under a fully controlled black-box setting. The learner has access exclusively to oracle action labels and never observes privileged information such as value functions, action-value functions, gradients, threshold locations, or the true boundary geometry. Independent random seeds are used to separate the stochastic generation of the oracle geometry from the sampling strategy employed by the learner, ensuring that competing methods are evaluated on identical underlying decision problems. Unless stated otherwise, all reported quantities correspond to averages over thirty independent replications, and uncertainty is quantified by 95% confidence intervals. Table 1 summarizes the complete experimental protocol, including the construction of the oracle geometries, query budgets, evaluation metrics, perturbation scenarios, scalability settings, and reproducibility outputs. The protocol has been designed so that every numerical result reported in the remainder of this section can be interpreted as empirical evidence supporting or challenging a specific theoretical prediction established in Sections 3-7.
page 44
8.1
Experimental Protocol
Table 1 reports the complete experimental configuration used throughout the numerical study. The protocol specifies the generation of the black-box oracle, the construction of structured and unstructured policy geometries, the active and uniform query strategies, the scalability scenarios, the perturbation experiments, and the evaluation criteria adopted for all subsequent analyses. Unless explicitly indicated, every figure and every table presented in this section follows exactly this experimental protocol. Table 1: Experimental configuration and black-box boundary-learning protocol. Component
Setting
Description
Random replications
30 seeds
State domain
(x, z) ∈ [−1, 1]2
Action space
|A| ∈ {2, 3, 4, 6, 8, 12, 16}
Structured oracle
Smooth monotone tessellations
Unstructured baselines
Table, checkerboard, random labels
Perturbation design
Smooth boundary noise
Black-box oracle
(x, z) 7→ π ∗ (x, z)
Target object
Γ∗ = Γ(π ∗ )
Uniform baseline
Random state queries
Active method
Boundary-focused adaptive sampling
Budget grid
102 to 105
Boundary grid
240 sections
Bisection depth
At most 22 steps
Evaluation sample
100,000 states
Boundary error
b Γ∗ ) dH (Γ,
Policy error
Rπ = P{b π (S) ̸= π ∗ (S)}
Compression metrics
CD , DCR, Ltable /Lstruct
Generalization test
Out-of-geometry random tessellations
Sample complexity
NΓ (ε, δ)
Reproducibility outputs
CSV, LATEX, PDF, PNG
All statistics are computed over independent oracle geometries and independent query-design replications. Two-dimensional state space used for boundary visualization, Hausdorff evaluation, and reconstructed-policy testing. Scalability experiments vary the number of discrete oracle actions; the baseline policy-reconstruction experiment uses |A| = 4. The oracle policy is generated from smooth ordered decision boundaries, producing a low-dimensional geometric representation of the optimal policy. Unstructured and fragmented label maps are used as falsification benchmarks to test whether boundary learning fails when geometric regularity is removed. Decision boundaries are perturbed by controlled smooth perturbations with amplitude in [0, 0.10]. The learner observes only action labels and never observes value functions, action gaps, thresholds, gradients, or true boundary locations. The statistical target is the decision-boundary geometry of the oracle policy, rather than V ∗ or Q∗ . Labels are collected from uniformly sampled states and boundaries are reconstructed from label transitions. Queries are concentrated near estimated action-transition regions, followed by local bracketing and bisection of decision boundaries. Nominal query budgets are used to compare Hausdorff convergence, policy disagreement, and sample complexity. Resolution used for representing boundary curves, computing Hausdorff error, and reconstructing policies. Maximum number of label-only bisection steps used to refine each estimated boundary point. Out-of-sample Monte Carlo sample used to estimate reconstructed-policy disagreement risk. Hausdorff-type distance between estimated and oracle boundaries, used only for ex-post evaluation. Out-of-sample disagreement probability between the reconstructed policy and the black-box oracle. Decision complexity, decision-compression ratio, and MDL-style compression gain quantify the structural advantage of boundary representations. The learned reconstruction protocol is evaluated across independently generated smooth geometries not used to tune the method. b Γ∗ ) ≤ ε with prescribed success Empirical query budget required to reach dH (Γ, frequency. All raw measurements, aggregated tables, and figure inputs are saved for full reproducibility.
Notes. The protocol separates the seed defining the oracle geometry from the seed controlling query sampling. Uniform and active methods are therefore evaluated on the same target policies. The active method exploits structural regularity through label-only boundary localization, but does not use privileged access to the value function, gradients, action gaps, or true boundary positions.
8.2
Empirical Validation of Boundary Geometry Learning
The first objective of the numerical study is to validate the geometric formulation developed in Sections 5 and 7. The theoretical analysis establishes that the reconstruction problem can be formulated as the estimation of the target boundary geometry Γ⋆ = Γ(π ⋆ ), rather than as the approximation of the value function or of the policy over the entire state space. Under the structural assumptions introduced in Section 5, the statistical behaviour of the reconstructed policy is therefore determined by b approximates Γ⋆ , as quantified by the Hausdorff the accuracy with which the boundary estimator Γ ⋆ b metric dH (Γ, Γ ). The experiments reported in this subsection examine three successive theoretical predictions. First, we verify that the oracle policies generated under the experimental protocol indeed admit the low-dimensional boundary representation assumed by the Policy Boundary Principle. page 45
Second, we investigate whether the empirical evolution of the Hausdorff error agrees with the convergence behaviour predicted by the Boundary Sample Complexity theorem. Finally, we estimate the empirical sample complexity NΓ (ε, δ) required to recover the target geometry with prescribed geometric accuracy and confidence. Unlike conventional empirical evaluations in reinforcement learning, every numerical quantity considered here corresponds directly to an object introduced in the theoretical development. Consequently, the figures and tables presented below should be interpreted as empirical estimates of the theoretical quantities appearing in Sections 5 and 7, rather than as standalone performance benchmarks. 8.2.1
Oracle Policy Geometry
The Policy Boundary Principle establishes that the informational content of an optimal policy is completely characterized by its decision-boundary geometry. More precisely, under the structural regularity assumptions introduced in Section 5, the oracle policy induces an ordered tessellation of the state space whose interfaces form the target boundary set Γ⋆ . Figure 1 displays the oracle policy over the state domain generated according to the protocol described in Section 8.1. Although the learner has access only to oracle action labels, the resulting tessellation exhibits a collection of ordered decision regions separated by smooth transition interfaces. Extracting these interfaces yields the target boundary geometry shown in Figure 2. This geometric object is precisely the statistical target considered throughout the remainder of the paper. Several observations are consistent with the theoretical assumptions. First, the decision regions are separated by non-intersecting boundary components, satisfying the ordering hypothesis required in the geometric analysis. Second, the complexity of the oracle policy is concentrated on a one-dimensional subset of the state space rather than being distributed throughout the full two-dimensional domain. Consequently, estimating Γ⋆ requires recovering only the transition interfaces between adjacent actions, thereby reducing policy reconstruction to a geometric estimation problem. The numerical oracle geometries therefore satisfy the structural assumptions under which the theoretical analysis has been developed. 8.2.2
Boundary Estimation Accuracy
Theorem 32 predicts that the statistical accuracy of policy reconstruction is governed by the convergence of the boundary estimator in the Hausdorff metric. In particular, the theory predicts that concentrating oracle queries near the decision interfaces substantially decreases the geometric sample complexity required to estimate Γ⋆ . b Γ⋆ ) for increasing nominal To evaluate this prediction, we estimate the Hausdorff distance dH (Γ, query budgets using both active boundary localization and uniform state-space exploration. The resulting estimates are reported in Figure 3, while the corresponding numerical summaries appear in Table 2. Table 2: Black-box boundary learning performance. Budget
100 200 500 1,000 2,000 5,000 10,000 25,000 50,000 100,000
b Γ∗ ) Hausdorff error dH (Γ,
Policy risk Rπ
Gain
Active
Uniform
Active
Uniform
A RU π /Rπ
0.047 ± 0.005 0.031 ± 0.0004 0.016 ± 0.0004 0.008 ± 0.00004 0.004 ± 0.0001 0.001 ± 0.00004 4.9×10−4 ± 3.2×10−6 2.4×10−4 ± 3.6×10−7 1.2×10−4 ± 5.1×10−8 6.1×10−5 ± 3.4×10−8
0.417 ± 0.022 0.699 ± 0.070 0.416 ± 0.053 0.219 ± 0.019 0.115 ± 0.008 0.043 ± 0.003 0.024 ± 0.002 0.018 ± 0.003 0.016 ± 0.003 0.015 ± 0.003
0.025 ± 0.002 0.019 ± 0.0005 0.009 ± 0.0002 0.005 ± 0.00009 0.002 ± 0.00006 5.8×10−4 ± 1.8×10−5 3.0×10−4 ± 1.0×10−5 1.7×10−4 ± 9.7×10−6 7.5×10−5 ± 4.8×10−6 4.0×10−5 ± 3.2×10−6
0.270 ± 0.015 0.315 ± 0.019 0.162 ± 0.009 0.119 ± 0.005 0.057 ± 0.002 0.018 ± 0.001 0.011 ± 0.001 0.009 ± 0.001 0.008 ± 0.001 0.008 ± 0.001
10.8× 16.9× 17.7× 26.0× 25.5× 30.5× 37.4× 53.9× 113.2× 209.6×
Notes. Entries report mean ± 95% confidence interval over 30 seeds and five structured policy families. “Active” denotes the adaptive black-box boundary bisection method. “Uniform” denotes uniform random sampling over A the state space. The gain column reports the policy-risk reduction factor RU π /Rπ .
page 46
Figure 1: Black-box optimal policy tessellation. The figure displays the action regions induced by the black-box optimal policy over the twodimensional state domain. Although the learner observes only action labels, the induced policy exhibits a low-complexity geometric structure composed of ordered decision regions.
Figure 2: Target boundary geometry Γ⋆ . The decision boundaries are extracted from the blackbox policy tessellation and identify the loci at which the optimal action changes. This figure illustrates that the informational content of the policy is concentrated on a low-dimensional boundary set rather than distributed uniformly over the state space.
Figure 3: Black-box boundary estimation. The proposed active adaptive bisection procedure achieves substantially smaller Hausdorff boundary error than uniform sampling across all query budgets. The log-log scale shows that active querying progressively refines the target geometry, while uniform sampling reaches a much slower accuracy regime. The empirical results exhibit two systematic properties. First, the Hausdorff error decreases monotonically as the number of oracle queries increases, consistent with the consistency properties established in Section 7. Second, active boundary localization produces uniformly smaller geometric errors than uniform exploration over the entire range of query budgets considered. Since both methods are evaluated on identical oracle geometries generated from the same random seeds, this improvement can be attributed exclusively to the concentration of sampling effort near the decision-boundary set. Figure 4(a) investigates the convergence behaviour of the estimator itself. The observed trajectories indicate that the boundary estimator produced by active localization converges substantially faster toward Γ⋆ , whereas uniform exploration remains limited by the inefficient allocation of oracle evaluations away from the decision interfaces. The accompanying policy disagreement values reported in Table 2 decrease consistently with the geometric error, providing empirical support for the theoretical relationship established in Section 7 between boundary estimation accuracy and policy reconstruction error. Finally, Figure 4(b) and Table 2 examine the empirical boundary sample complexity NΓ (ε, δ). For every prescribed Hausdorff tolerance, the active estimator reaches the desired geometric acpage 47
curacy with substantially fewer oracle evaluations than uniform exploration. Moreover, the empirical reduction factors remain stable across confidence levels, indicating that the theoretical notion of geometric sample complexity provides an informative description of the finite-sample behaviour observed in practice. Taken together, these experiments provide consistent empirical evidence supporting the geometric learning framework developed in Sections 5 and 7. The numerical observations agree with the theoretical prediction that the statistical difficulty of black-box policy reconstruction is fundamentally governed by the estimation of the decision-boundary geometry Γ⋆ , rather than by approximation of the policy over the entire state space.
(a) Hausdorff convergence of boundary estimators.
(b) Empirical sample complexity.
Figure 4: Boundary-estimation efficiency. Active boundary sampling achieves substantially faster Hausdorff convergence than uniform sampling while requiring fewer samples to reach the same geometric tolerance.
8.3
Empirical Validation of Policy Reconstruction
The second group of experiments investigates the reconstruction guarantees established in Sections 5 and 7. Whereas the previous subsection focused exclusively on estimating the target boundary geometry Γ⋆ , the present experiments examine the second stage of the theoretical framework, namely the reconstruction of the oracle policy from the estimated boundary representation. The theoretical developments show that, under the structural assumptions introduced in Section 5, the reconstructed policy is entirely determined by the estimated boundary geometry through the b and that the corresponding policy disagreement is controlled by reconstruction operator π b = R(Γ), b Γ⋆ ). the geometric estimation error measured by dH (Γ, Consequently, policy reconstruction is analysed as a deterministic consequence of geometric estimation rather than as an independent statistical learning problem. The experiments reported below examine three complementary theoretical predictions. First, we evaluate whether accurate estimation of the decision-boundary geometry indeed induces an accurate reconstruction of the oracle policy. Second, we investigate the empirical relationship between Hausdorff estimation error and policy disagreement predicted by the Geometric Learning Guarantee. Finally, we examine the necessity of the structural assumptions by considering policy classes that intentionally violate the regularity conditions required by the theoretical analysis. Unlike conventional empirical evaluations in reinforcement learning, every numerical quantity considered in this subsection corresponds directly to an object introduced in Sections 5-7. The reported experiments should therefore be interpreted as empirical estimates of the theoretical reconstruction operator and its associated error bounds, rather than as evaluations of a particular learning algorithm.
page 48
8.3.1
Boundary-to-Policy Reconstruction
The Policy Reconstruction Principle established in Section 5 states that, under the structural assumptions defining the admissible policy class, the oracle policy is uniquely determined by its decisionb of the target boundary set has been constructed, the boundary geometry. Once an estimator Γ b is therefore completely specified by the induced partition of the reconstructed policy π b = R(Γ) state space. To examine this prediction, we reconstruct the policy associated with each estimated boundary obtained in Section 8.2 and evaluate its disagreement with the oracle policy over an independent Monte Carlo sample. Figure 6 reports the evolution of the empirical policy disagreement Rπ , whereas Figure 5 compares the oracle tessellation, the reconstructed partition, and the corresponding disagreement set. Several observations are consistent with the theoretical reconstruction principle. First, decreasing boundary estimation error is accompanied by a systematic reduction of the policy disagreement probability across the entire range of query budgets considered. Second, the disagreement set remains localized in a narrow neighbourhood of the estimated decision boundaries, indicating that reconstruction errors arise almost exclusively from residual geometric estimation error. Finally, the reconstructed tessellation shown in Figure 5 preserves the ordering and adjacency structure of the oracle partition, illustrating that the reconstruction operator successfully recovers the global policy geometry from local boundary estimates. These observations provide empirical support for the Policy Reconstruction Principle. In particular, they indicate that accurate estimation of Γ⋆ is sufficient to recover the corresponding policy partition without requiring direct approximation of the value function, action-value function, or any additional oracle information.
Figure 5: Policy reconstruction from the estimated decision boundary. The oracle policy π ⋆ , the b and the disagreement set show that the learned boundary induces an reconstructed policy R(Γ), almost identical policy partition, with very small Hausdorff and policy-disagreement errors.
8.3.2
Geometry Controls Policy Risk
The Geometric Learning Guarantee developed in Section 7 predicts that policy disagreement is controlled by the geometric estimation error. More precisely, the theoretical analysis establishes the b Γ⋆ ) , implying that improvements in existence of a monotone function Φ such that Rπ ≤ Φ dH (Γ, boundary estimation necessarily induce improvements in policy reconstruction. To evaluate this prediction, we jointly estimate the Hausdorff error and the corresponding policy disagreement over all policy families, query budgets, and independent replications. Figure 7 displays the complete collection of empirical observations, while Figure 8(a) summarizes the resulting geometric relationship. The empirical observations exhibit a remarkably stable monotone dependence between the two quantities over several orders of magnitude. On the logarithmic scale, the observed relationship is approximately linear, indicating that reductions in Hausdorff estimation error translate proportionally into reductions in policy disagreement. page 49
Figure 6: Policy reconstruction from black-box queries. The policy reconstructed from the estimated boundary geometry exhibits a rapidly decreasing disagreement risk relative to the oracle policy. Moreover, the fitted slope reported in Figure 8(a) remains close to the behaviour predicted by the theoretical analysis, with no systematic deviations observed across policy families or sampling budgets. Overall, the numerical evidence is consistent with the Geometric Learning Guarantee developed in Section 7. The experiments indicate that the Hausdorff metric captures the dominant source of reconstruction error and therefore provides an informative geometric surrogate for the statistical behaviour of the reconstructed policy.
Figure 7: Geometric estimation error controls policy error. Each point corresponds to one seed– family-budget configuration. The log–log relationship shows that the policy disagreement risk scales with the Hausdorff boundary estimation error.
8.3.3
Failure under Loss of Structural Regularity
The theoretical guarantees established in Sections 5 and 7 rely on structural assumptions describing the geometry of the oracle decision boundaries. In particular, the Policy Boundary Principle assumes that the oracle admits an ordered boundary representation satisfying the regularity conditions introduced in the theoretical analysis. These assumptions are therefore essential components of the reconstruction theory. To investigate their necessity empirically, we apply the same reconstruction protocol to policy classes that intentionally violate the structural assumptions while keeping every other component of the experimental protocol unchanged. Figure 8(b) summarizes the resulting policy disagreement across representative policy classes, whereas Table 3 reports the corresponding quantitative comparisons.
page 50
(a) Policy error versus geometric error.
(b) Failure without structural regularity.
Figure 8: Geometric control of policy error and the role of structural regularity. The near-linear log–log relationship confirms that Hausdorff boundary error controls policy disagreement, whereas unstructured or irregular decision rules lead to large reconstruction risk. The empirical observations agree with the theoretical prediction. Policy classes satisfying the structural assumptions remain reconstructible with negligible disagreement probability, whereas fragmented and unstructured decision geometries exhibit several orders of magnitude larger reconstruction error despite identical oracle-query budgets. Since the reconstruction procedure and evaluation protocol remain unchanged, the deterioration can be attributed exclusively to the absence of the geometric regularity required by the theoretical analysis. Consequently, the experiments support the interpretation that the assumptions introduced in Section 5 are genuine identifiability conditions for geometric policy reconstruction rather than technical artifacts of the mathematical proofs. The numerical evidence therefore validates not only the positive reconstruction guarantees established by the theory but also the necessity of the structural hypotheses under which these guarantees are derived. Table 3: Failure-mode validation under loss of structural regularity. Policy class
Policy risk Rπ
Oracle queries
Relative degradation
Structured Unstructured
3.97×10−5 ± 3.17×10−6
22,256 ± 194 22,114 ± 3
1.0× 4,673×
1.856×10−1 ± 4.43×10−4
Notes. Entries report mean ± 95% confidence interval over 30 seeds. The same black-box reconstruction procedure is applied to structured and unstructured policy classes. The sharp increase in Rπ under the unstructured design confirms that the method exploits boundary regularity rather than memorizing policy labels.
8.4
Empirical Validation of the Active Boundary Sampling Principle
Sections 8.2 and 8.3 established that the statistical objective of black-box policy learning is the estimation of the decision-boundary geometry Γ⋆ , and that the accuracy of the reconstructed policy is governed by the Hausdorff estimation error of this geometric object. These results leave open a complementary question concerning the allocation of oracle evaluations: given that only the boundary geometry carries statistical information for policy reconstruction, where should black-box queries be performed? Section 7 addresses this question through the Active Boundary Sampling Principle. Rather than treating every state as equally informative, the theory predicts that oracle evaluations should progressively concentrate in neighbourhoods of Γ⋆ , since only these regions contribute directly to reducing the geometric estimation error. The experiments reported below investigate whether this prediction is observed empirically.
page 51
Unlike the previous subsections, the objective is not to compare competing sampling algorithms. Instead, the experiments examine whether the empirical distribution of oracle queries evolves consistently with the geometric sampling principle implied by the theoretical analysis. Two complementary consequences are considered. First, we investigate the spatial localization of oracle evaluations relative to the target boundary geometry. Second, we evaluate whether all connected components of the decision-boundary representation converge simultaneously, as predicted by the geometric formulation developed in Sections 5 and 7. 8.4.1
Localization of Oracle Evaluations
The Active Boundary Sampling Principle predicts that informative oracle evaluations should become increasingly concentrated near the decision-boundary geometry Γ⋆ . Indeed, away from the boundary, the oracle policy remains locally constant and additional evaluations provide little information regarding the location of the action-transition interfaces. Consequently, the theory predicts that an efficient geometric estimation strategy should allocate progressively fewer evaluations to homogeneous decision regions and increasingly more evaluations to neighbourhoods of the boundary set. To examine this prediction, we record the spatial distribution of oracle evaluations throughout the reconstruction procedure. Figure 9(a) displays the resulting query locations together with the oracle decision boundaries, while Figure 10 summarizes the corresponding evolution of the relative policy-risk reduction with respect to uniform exploration.
(a) Spatial localization of active queries.
(b) Boundary-wise convergence.
Figure 9: Localization and component-wise stability of active boundary learning. Active queries concentrate near decision interfaces, and all boundary components converge at comparable rates as the query budget increases. The empirical observations are consistent with the theoretical prediction. As the reconstruction progresses, oracle evaluations become increasingly concentrated around the boundary components composing Γ⋆ , whereas only a small proportion of queries remain allocated to the interior of homogeneous decision regions. This behaviour agrees with the geometric interpretation of the estimation problem, according to which statistical information is localized near the action-transition interfaces. The increasing relative risk reduction reported in Figure 10 provides complementary evidence supporting the same conclusion. Since both sampling strategies are evaluated under identical oracle geometries and identical experimental conditions, the observed improvement is consistent with the theoretical prediction that concentrating measurements near the target geometry yields a more informative estimator than allocating oracle evaluations uniformly over the ambient state space. Taken together, these experiments provide empirical support for the Active Boundary Sampling Principle introduced in Section 7. Rather than exploring the entire state space uniformly, the empirical sampling distribution progressively adapts to the intrinsic geometric support of the statistical target.
page 52
Figure 10: Active boundary sampling efficiency gain. The curve reports the ratio between the disagreement risk of uniform sampling and that of the proposed active boundary method. Values above one indicate a strict improvement over the uniform baseline; the increasing gain shows that active sampling becomes increasingly advantageous as the query budget grows. 8.4.2
Component-wise Convergence of the Boundary Geometry
The theoretical analysis is formulated for the complete decision-boundary geometry Γ⋆ , which generally consists of several connected boundary components. Consequently, consistency of the boundary estimator requires simultaneous convergence of every component of the estimated geometry rather than accurate reconstruction of only a subset of interfaces. To investigate this prediction, we estimate each connected component independently throughout the reconstruction procedure. Figure 11 compares the reconstructed geometry with the oracle boundary, whereas Figure 9(b) reports the evolution of the component-wise Hausdorff errors as the nominal query budget increases. Several observations are consistent with the theoretical framework. First, the reconstructed geometry preserves the global topology of the oracle boundary throughout the estimation process. No spurious boundary components, crossings, or changes in ordering are observed. Second, the Hausdorff errors associated with the individual boundary components decrease at comparable rates over the entire range of query budgets considered. Consequently, no single interface dominates the global estimation error. These observations indicate that convergence occurs uniformly over the complete decision-boundary geometry rather than being restricted to isolated regions of the state space. The empirical evidence is therefore consistent with the geometric consistency properties established in Section 7 and supports the interpretation that the estimator converges toward the entire boundary representation Γ⋆ , instead of approximating only local fragments of the policy partition.
8.5
Empirical Validation of Decision Compression Theory
The previous subsections established that black-box policy learning can be formulated as a geometric estimation problem whose statistical target is the decision-boundary representation Γ⋆ . Sections 5 and 7 demonstrated that accurate estimation of this geometric object is sufficient for reconstructing the oracle policy and controlling the corresponding policy disagreement risk. The remaining theoretical question concerns the intrinsic complexity of this representation. Section 6 develops a quantitative theory of decision compression by introducing several geometric complexity measures, including the Decision Compression Ratio (DCR), the decision complexity CD , the boundary complexity CB , and the topological complexity Ctop . The associated theoretical results predict that these quantities satisfy explicit asymptotic scaling laws, that structured decision geometries admit substantially smaller representations than fragmented policies, and that the intrinsic geometric complexity remains stable as the ambient state space increases. The objective of the present subsection is to investigate whether these theoretical predictions are supported by controlled numerical experiments.
page 53
Figure 11: Black-box decision boundary reconstruction. Ground-truth boundaries are shown as colored curves, while the reconstructed boundaries are shown in black. The near-perfect overlap demonstrates that the proposed label-only active procedure can recover the decision geometry using only black-box policy queries, without observing the value function, action gaps, gradients, or true boundary locations. Rather than evaluating compression performance as an engineering criterion, we estimate the mathematical quantities introduced in Section 6 and compare their empirical behaviour with the corresponding theoretical predictions. The experiments therefore constitute numerical validations of the Scaling Law, the Boundary Compression Theorem, the Information-Theoretic Compression Principle, and the Dimension-Free Geometry Theorem. 8.5.1
Scaling Law for Decision Compression
Theorem 3 predicts that the Decision Compression Ratio satisfies an asymptotic scaling law governed by the intrinsic geometric complexity of the policy representation. In particular, the theory establishes that the compression ratio grows proportionally with the effective size of the decision problem, with asymptotic exponent equal to one under the structured boundary model developed in Section 6. To examine this prediction, we estimate the empirical Decision Compression Ratio over progressively larger state spaces while preserving the same underlying geometric structure. Figure 12 reports the resulting scaling behaviour on logarithmic axes, Figure 13 investigates the dependence on intrinsic state-space dimension, and Table 4 summarizes the estimated scaling exponent obtained from the log-log regression log(DCR) = α + β log(|S|). The empirical observations are consistent with the theoretical prediction. The estimated scaling exponent remains statistically indistinguishable from the value predicted by Theorem 3, and the coefficient of determination indicates that the asymptotic model explains nearly all observed variability. Moreover, the exponential behaviour reported in Figure 13 agrees with the theoretical interpretation that explicit policy representations become exponentially more expensive as the intrinsic dimension increases, whereas boundary-based representations preserve their geometric description. Taken together, these observations provide empirical support for the scaling law established in Section 6 and indicate that the asymptotic behaviour predicted by the theoretical analysis accurately describes the finite-sample regime considered throughout the numerical study.
page 54
Figure 12: Scaling law for decision compression. The empirical decision-compression ratio DCR(n) increases proportionally to the size of the state space on logarithmic scales, closely matching the theoretical prediction with scaling exponent β ≈ 1. The near-perfect agreement between theory and experiments validates the asymptotic scaling law established in Section 6 and confirms that the compression gain grows predictably with problem size.
Figure 13: Exponential growth of the decision-compression ratio. As the intrinsic state-space dimension increases, the decisioncompression ratio follows an exponential trend that is accurately approximated by DCR(d) ∝ e0.69d . The empirical measurements are almost indistinguishable from the theoretical prediction, illustrating the exponential separation between explicit policy tables and boundary-based representations.
Table 4: Empirical validation of the scaling law predicted by Theorem 3. The estimated exponent is obtained from the log–log regression log(DCR) = α + β log(|S|). Confidence intervals are computed from ordinary least squares. Model Scaling law
8.5.2
Estimated exponent β̂
Std. Error
95% CI
R2
1.002
0.011
[0.978, 1.026]
0.989
Structural Compression and Information-Theoretic Efficiency
The Boundary Compression Theorem predicts that representation complexity is governed primarily by the intrinsic geometry of the decision boundary rather than by the cardinality of the ambient state space. Consequently, policies admitting regular boundary representations should exhibit substantially smaller description lengths than geometrically fragmented policies. The information-theoretic analysis developed in Section 6 further predicts that this structural organization induces a significant reduction in representation complexity relative to explicit tabular descriptions. To investigate these predictions, we estimate the empirical relationships between boundary complexity CB , decision complexity CD , and representation length across both structured and unstructured policy classes. Figure 14 reports the observed dependence between boundary and decision complexity, Figure 15 compares the resulting description lengths with the identity-compression baseline, and Table 5 summarizes the corresponding complexity measures. Several observations are consistent with the theoretical analysis. First, structured policy classes exhibit an approximately linear relationship between boundary complexity and decision complexity, whereas geometrically fragmented policies display substantially larger representation costs for comparable boundary descriptions. Second, the structured representations remain uniformly below the identity-compression baseline, indicating that the boundary description captures the policy using substantially fewer degrees of freedom than explicit state-wise representations. Finally, the complexity measures reported in Table 5 exhibit systematic separation between structured and unstructured geometries across every metric considered. Overall, the empirical evidence agrees with the Boundary Compression Theorem and the information-theoretic interpretation developed in Section 6. page 55
Table 5: Comparison between structured and unstructured decision boundaries. Structured geometries preserve low decision complexity while maintaining exponentially higher compression efficiency. Metric
Structured
Unstructured
Improvement
Decision complexity CD Topological complexity Ctop Boundary description length Compression ratio (DCR)
53 8 2.1 × 104 3.2 × 103
275 45 9.0 × 104 1
×5.19 ×5.63 ×4.29 ×3200
The observed reductions in representation complexity are therefore consistent with the geometric organization of the decision boundary rather than with implementation-specific properties of the reconstruction procedure.
Figure 14: Boundary complexity versus decision complexity. Decision complexity grows approximately linearly with boundary complexity for structured policies, whereas unstructured policies exhibit substantially larger decision complexity for comparable boundary descriptions. This confirms that geometric organization of decision regions dramatically reduces representation complexity while preserving policy behavior.
8.5.3
Figure 15: Information-theoretic compression proxy. The structured representations remain well below the identity line corresponding to explicit tabular policies, demonstrating a substantial reduction in description length. The gap quantifies the information-theoretic compression achieved through boundary-based policy representations and provides empirical evidence for the compression theorem developed in Section 6.
Dimension-Free Geometry
The Dimension-Free Geometry Theorem predicts that the intrinsic topological complexity of structured decision boundaries remains uniformly bounded as the ambient state space increases. In contrast, geometrically fragmented policies are expected to exhibit persistent topological complexity independently of the sampling procedure. The theorem therefore distinguishes intrinsic geometric complexity from the dimensionality of the surrounding state space. To examine this prediction, we estimate the empirical topological complexity Ctop over progressively larger state spaces while preserving the underlying decision geometry. Figure 16 reports the resulting estimates for both structured and fragmented policy classes. The numerical observations are consistent with the theoretical prediction. Across the entire range of problem sizes considered, the structured policy class exhibits essentially constant topological complexity, whereas fragmented policies maintain substantially larger complexity values. No systematic increase of Ctop is observed for the structured geometries as the ambient state space grows, suggesting that the intrinsic boundary representation remains stable despite the increasing size of the decision problem. These observations support the interpretation proposed in Section 6 that geometric complexity is an intrinsic property of the decision-boundary representation rather than a direct consequence of the cardinality of the state space.
page 56
The empirical results are therefore consistent with the Dimension-Free Geometry Theorem established by the theoretical analysis.
Figure 16: Dimension-free geometry versus fragmentation. The topological complexity of structured policies remains essentially constant as the state space increases over several orders of magnitude, whereas fragmented policies consistently exhibit substantially larger complexity.
8.6
Robustness of Geometric Learning
The previous subsections established empirical evidence supporting the geometric learning framework developed in Sections 5-7. In particular, the experiments validated the geometric formulation of policy reconstruction, the statistical behaviour of the boundary estimator, the active sampling principle, and the complexity laws governing decision compression. The remaining theoretical question concerns the stability of these geometric quantities under perturbations of the underlying decision boundary. Section 6 establishes that the geometric representation possesses intrinsic robustness properties. More precisely, the Robustness Theorem predicts that sufficiently small perturbations of the target boundary geometry Γ⋆ induce only controlled variations of the associated complexity measures, including the decision complexity CD , the Decision Compression Ratio, and the information-theoretic description length. Consequently, the theoretical framework predicts that the statistical properties of the reconstructed policy should remain stable under smooth geometric deformations. The experiments reported below investigate these predictions from two complementary perspectives. First, we evaluate whether the complexity measures introduced in Section 6 remain stable under controlled perturbations of the oracle geometry. Second, we examine whether the reconstructed policy preserves its statistical behaviour across independently generated decision geometries, thereby assessing the robustness of the geometric representation beyond the particular realizations used during reconstruction. Unlike robustness analyses commonly encountered in machine learning, the perturbations considered here are applied directly to the mathematical object Γ⋆ , rather than to observations, rewards, or optimization procedures. Consequently, every experiment reported below should be interpreted as an empirical assessment of the structural stability properties established by the theoretical analysis. 8.6.1
Robustness to Smooth Boundary Perturbations
The Robustness Theorem established in Section 6 predicts that smooth perturbations of the target boundary geometry induce only controlled variations of the intrinsic complexity measures. In particular, the theory implies that sufficiently regular deformations of Γ⋆ should preserve the decision complexity, the Decision Compression Ratio, and the associated information-theoretic compression gain. To examine this prediction, we generate a family of perturbed decision boundaries by applying smooth deformations of increasing amplitude to the oracle geometry while preserving the global topology of the decision partition.
page 57
For every perturbation level, we estimate the corresponding decision complexity CD , the relative Decision Compression Ratio, and the MDL-based compression measure introduced in Section 6. Figure 17 reports the resulting empirical behaviour, while Table 6 summarizes the corresponding numerical values. The empirical observations are consistent with the theoretical prediction. Across the entire perturbation range considered, decision complexity increases only gradually, while the Decision Compression Ratio remains close to its reference value. Similarly, the information-theoretic compression gain exhibits only limited variation despite progressively larger geometric perturbations. Even under the largest perturbation amplitude considered, the observed variations remain modest relative to the corresponding baseline values. Overall, the numerical evidence supports the robustness properties established in Section 6. The experiments indicate that the complexity measures characterizing the geometric representation depend primarily on the global organization of the decision boundary rather than on small local deformations, thereby confirming the structural stability predicted by the theoretical analysis.
(a) Structural complexity.
(b) Compression robustness.
(c) MDL compression gain.
Figure 17: Robustness under smooth boundary perturbations. Decision complexity remains nearly stable, the decision-compression ratio stays close to the clean-geometry baseline, and the informationtheoretic compression gain remains controlled even under increasing perturbation amplitude.
8.6.2
Stability of Policy Reconstruction Across Geometries
The theoretical framework further predicts that the geometric representation should remain statistically meaningful beyond the particular oracle geometry used during reconstruction. If the quantities introduced in Sections 5-7 capture intrinsic properties of the decision boundary, then the resulting complexity measures and reconstruction errors should remain stable across independently generated geometries satisfying the same structural assumptions. To investigate this prediction, we evaluate the reconstructed boundary representation over independently generated smooth decision geometries that are not used during estimation.
page 58
Table 6: Robustness of the proposed decision-compression mechanism under smooth boundary perturbations. Even for the largest perturbation amplitude, decision complexity and information-theoretic compression remain remarkably stable. Perturbation
Decision Complexity CD
Relative DCR
MDL Compression Ltable /Lstruct
Relative variation (%)
0.000 0.002 0.005 0.010 0.020 0.035 0.050 0.075 0.100
19.21 19.21 19.21 19.22 19.23 19.26 19.34 19.55 19.89
1.000 1.000 0.999 0.999 0.999 0.997 0.993 0.983 0.967
10.39 10.39 10.39 10.38 10.37 10.34 10.28 10.11 9.87
0.00 0.02 0.05 0.11 0.24 0.61 1.06 2.05 3.26
(a) Complexity–risk Pareto frontier.
(b) Out-of-geometry generalization.
Figure 18: Complexity–risk trade-off and out-of-geometry generalization. Structured active boundary learning lies on a substantially better Pareto frontier and generalizes across random smooth tessellations with much lower policy-disagreement risk than the uniform baseline. Figure 18 reports the empirical complexity-risk frontier together with the corresponding out-ofgeometry generalization behaviour, whereas Figure 19 summarizes the joint empirical distribution of decision complexity CD and policy disagreement risk Rπ across the complete collection of randomly generated geometries. Several observations agree with the theoretical framework. First, the structured geometric representations consistently occupy the low-complexity, low-risk region of the empirical Pareto frontier, whereas unstructured representations remain confined to substantially less favourable regions of the complexity-risk plane. Second, the out-of-geometry experiments exhibit uniformly small policy disagreement across independently generated geometries satisfying the structural assumptions introduced in Section 5. Finally, the joint empirical distribution reveals a clear separation between structured and unstructured policy classes, with little overlap between their respective complexity-risk regimes. Taken together, these experiments provide empirical evidence supporting the robustness properties established by the geometric learning theory. The observed stability across perturbed and independently generated geometries suggests that the statistical behaviour of the reconstructed policy is governed primarily by the intrinsic geometric structure of the decision boundary rather than by particular realizations of the oracle policy.
8.7
Empirical Synthesis
The numerical study presented throughout Sections 8.2-8.6 was designed to examine the theoretical predictions established in Sections 5-7 under a common experimental protocol. Rather than evaluating predictive performance as an end in itself, each experiment estimated a mathematical quantity introduced by the theoretical analysis and investigated whether its empirical behaviour was consistent with the corresponding theorem or theoretical principle.
page 59
Figure 19: Complexity-risk joint distribution across random geometries. Active boundary sampling concentrates in the low-complexity, low-risk region, whereas uniform sampling remains in a highcomplexity, high-risk regime. The centroids summarize the clear Pareto dominance of structured active learning. Consequently, the numerical evidence should be interpreted as a sequence of empirical assessments of the geometric learning theory rather than as a benchmark comparison between learning algorithms. Table 7 summarizes this correspondence. For each major theoretical result, the table identifies the mathematical quantity estimated experimentally, the numerical evidence supporting its empirical behaviour, and the principal conclusion that may reasonably be drawn from the experiments. The table therefore provides a direct correspondence between the theoretical developments of Sections 5-7 and the numerical investigations reported throughout Section 8. Several general observations emerge from this synthesis. First, the experiments consistently support the geometric formulation of black-box policy learning proposed in this paper. Across all experimental settings, the decision-boundary geometry Γ⋆ behaves as the primary statistical object governing policy reconstruction. The observed evolution b and the associated Hausdorff error agrees with the theoretical interof the boundary estimator Γ pretation that policy learning may be formulated as a geometric estimation problem. Second, the empirical relationship between Hausdorff estimation error and policy disagreement is consistent with the Geometric Learning Guarantee established in Section 7. The numerical results indicate that improvements in geometric reconstruction are systematically accompanied by reductions in policy b Γ⋆ ) and Rπ . Third, the experdisagreement, in agreement with the theoretical bounds linking dH (Γ, iments examining decision compression exhibit empirical behaviour consistent with the complexity theory developed in Section 6. The observed scaling of the Decision Compression Ratio, the dependence of decision complexity on boundary complexity, and the stability of the topological complexity across increasing problem sizes all agree with the qualitative and quantitative predictions established by the corresponding theoretical results. Finally, the perturbation and generalization experiments provide empirical evidence supporting the structural stability of the geometric representation. Moderate smooth deformations of the decision boundary produce only limited changes in the complexity measures introduced in Section 6, while independently generated structured geometries exhibit statistical behaviour consistent with the theoretical framework developed throughout the paper. Naturally, these experiments do not establish the mathematical validity of the theoretical results, which follows from the proofs presented in Sections 5-7. Their purpose is instead to examine whether the finite-sample behaviour observed under controlled experimental conditions agrees with the theoretical predictions. Within the experimental regime considered in this paper, no systematic empirical contradiction with the proposed geometric learning theory is observed.
page 60
Taken together, the numerical evidence provides consistent empirical support for the theoretical framework developed in this paper. The experiments indicate that the principal geometric, statistical, and information-theoretic predictions derived in Sections 5-7 accurately describe the behaviour observed across the controlled black-box policy reconstruction problems considered throughout the numerical study. Table 7: Empirical validation of the theoretical results established in Sections 4-7. Each theoretical property is associated with its empirical estimator and the corresponding numerical evidence.
9
Theoretical result
Empirical quantity
Experimental evidence
Main conclusion
Threshold Representation (Theorem 5)
b Estimated boundary Γ
Policy Reconstruction Principle (Theorem 33) Active Boundary Sampling Principle (Principle 2)
Policy disagreement Rπ
Figs. 3, 4 Tables 2,3 Figs. 5, 8
Boundary localization and query allocation
Figs. 9a, 9b
Scaling Law for Decision Compression (Theorem 24)
Decision Compression Ratio (DCR)
Figs. 12, 16 Table 4
Boundary Compression Theorem (Theorem 27)
Decision complexity CD
Figs. 14, 15 Table 5
Information-Theoretic (Theorem 29)
Description length LΠ /LΓ
Figs. 15, 17
Boundary Stability (Theorem 21)
Robustness under smooth perturbations
Figs. 17, 18 Table 6
Geometric Learning Guarantee (Theorem 34)
Joint behaviour of dH and Rπ
Figs. 8, 19
The reconstructed boundaries converge rapidly to the oracle geometry under active sampling. Accurate reconstruction of the boundary geometry implies accurate recovery of the oracle policy. Queries naturally concentrate near decision boundaries, yielding substantially improved sample efficiency. The empirical scaling exponent agrees with the theoretical compression law and remains essentially dimension-free. Decision complexity scales with boundary complexity rather than the size of the value representation. Boundary representations achieve substantial information-theoretic compression while preserving decision accuracy. Decision compression and policy reconstruction remain stable under moderate geometric perturbations. The observed decrease of policy disagreement is consistent with the theoretical geometric learning guarantee.
Compression
Conclusion
This paper develops a geometric theory of black-box policy learning. Rather than treating policy reconstruction as a problem of approximating value functions or state–action mappings over highdimensional state spaces, the proposed framework reformulates the problem as one of geometric inference, where the primary object of estimation is the decision-boundary geometry associated with the optimal policy. Under this viewpoint, statistical estimation, computational complexity, oraclequery allocation, and information-theoretic compression become different manifestations of a common geometric representation. Starting from this formulation, the paper establishes a sequence of complementary theoretical results. The decision-boundary geometry is shown to provide a sufficient representation of structured optimal policies, and accurate estimation of this geometric object is proved to imply accurate policy reconstruction. The analysis further characterizes the statistical behaviour of boundary estimation through Hausdorff convergence and boundary sample complexity, provides a geometric interpretation of active oracle sampling, and develops a quantitative theory of decision compression based on intrinsic geometric complexity rather than the cardinality of the ambient state space. Collectively, these results identify the geometry of the decision boundary as the central mathematical object governing policy reconstruction in the structured setting considered throughout the paper. The numerical investigation was designed accordingly. Rather than evaluating predictive performance in isolation, each experiment examined a specific theoretical prediction established in Sections 5-7 by estimating the corresponding mathematical quantity under a controlled black-box protocol. Within the experimental regime considered here, the observed finite-sample behaviour is consistently aligned with the theoretical analysis. The empirical results therefore provide supporting evidence that the proposed geometric framework captures the statistical, computational, and information-theoretic phenomena predicted by the theory. The analysis presented in this paper is intentionally restricted to structured decision geometries satisfying the regularity assumptions introduced in Section 5. Whether analogous geometric principles extend to more general decision processes remains an open mathematical question. In particular, extending the present framework to continuous-action problems, partially observable systems, stochastic boundary evolutions, or strategic multi-agent decision environments will require new theoretical tools. page 61
Equally important is the development of minimax lower bounds, statistical optimality results for geometric boundary estimators, and a deeper understanding of the interplay between geometric regularity and sample complexity. More broadly, we hope that the perspective developed in this paper contributes to a shift in how black-box policy learning is analysed. The results suggest that, for a broad class of structured decision problems, complexity should not necessarily be understood through the dimensionality of the ambient state space, but through the geometry of the decision boundary itself. From this viewpoint, statistical estimation, computational efficiency, active sampling, and information-theoretic compression are no longer separate phenomena; they arise as different consequences of the same underlying geometric structure.
Competing Interests The authors declare that they have no competing financial or non-financial interests related to this work.
Data Availability This study is based exclusively on simulation experiments. The source code and all scripts required to reproduce the numerical results are available at https://github.com/phdPokou/A-Geometric-Theory-of-Decision-Boundaries
Ethics Approval This study does not involve human participants, personal data, or animals and therefore does not require ethics approval.
Funding The authors received no specific funding for this work.
References M. Anthony and P. L. Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 2009. R. Bellman. Dynamic programming: Princeton univ. press. Princeton.[Google Scholar], 1957. D. Bertsekas. Dynamic programming and optimal control: Volume I, volume 4. Athena scientific, 2012. D. P. Bertsekas. Neuro-dynamic programming. In Encyclopedia of optimization, pages 1–6. Springer, 2025. S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004. L. A. Caffarelli. A geometric approach to free boundary problems, volume 68. American Mathematical Soc., 2005. L. Devroye, L. Györfi, and G. Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013. H. Edelsbrunner. Algorithms in combinatorial geometry, volume 10. Springer Science & Business Media, 1987.
page 62
E. A. Feinberg and A. Shwartz. Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012. P. D. Grünwald. The minimum description length principle. MIT press, 2007. O. Hernández-Lerma and J. B. Lasserre. Discrete-time Markov control processes: basic optimality criteria, volume 30. Springer Science & Business Media, 2012. G. Koole. Monotonicity in Markov reward and decision chains: Theory and applications. Now Publishers Inc, 2007. V. Krishnamurthy. Partially observed Markov decision processes. Cambridge university press, 2016. M. G. Lagoudakis and R. Parr. Least-squares policy iteration. Journal of machine learning research, 4(Dec):1107–1149, 2003. A. Lazaric, M. Ghavamzadeh, and R. Munos. Analysis of a classification-based policy iteration algorithm. In ICML-27th International Conference on Machine Learning, pages 607–614. Omnipress, 2010. W. S. Lovejoy. Some monotonicity results for partially observed markov decision processes. Operations Research, 35(5):736–743, 1987. P. Milgrom and C. Shannon. Monotone comparative statics. Econometrica: Journal of the Econometric Society, pages 157–180, 1994. R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008. A. Petrosyan, H. Shahgholian, and N. N. Uraltseva. Regularity of Free Boundaries in ObstacleType Problems, volume 136 of Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, 2012. W. Polonik. Measuring mass concentrations and estimating density contour clusters-an excess mass approach. The annals of Statistics, pages 855–881, 1995. W. B. Powell. Approximate Dynamic Programming: Solving the curses of dimensionality, volume 703. John Wiley & Sons, 2007. F. P. Preparata and M. I. Shamos. Computational geometry: an introduction. Springer Science & Business Media, 2012. M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. J. Rissanen. Modeling by shortest data description. Automatica, 14(5):465–471, 1978. R. T. Rockafellar. Convex analysis, volume 28. Princeton university press, 1997. H. Scarf. The optimality of (s, s) policies in the dynamic inventory problem. 1960. S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. J. E. Smith and K. F. McCardle. Structural properties of stochastic dynamic programs. Operations Research, 50(5):796–809, 2002. M. J. Sobel. The optimality of full service policies. Operations Research, 30(4):636–649, 1982. S. Stidham Jr and R. R. Weber. Monotonic and insensitive optimal policies for control of queues with undiscounted costs. Operations research, 37(4):611–625, 1989.
page 63
R. S. Sutton, A. G. Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998. D. M. Topkis. Minimizing a submodular function on a lattice. Operations research, 26(2):305–321, 1978. D. M. Topkis. Supermodularity and complementarity. Princeton university press, 1998. A. B. Tsybakov. On nonparametric estimation of density level sets. The Annals of Statistics, 25(3): 948–969, 1997. V. N. Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, 10 (5):988–999, 1999. A. F. Veinott. Discrete dynamic programming with sensitive discount optimality criteria. The Annals of Mathematical Statistics, 40(5):1635–1660, 1969. A. F. Veinott Jr. Optimal policy in a dynamic, single product, nonstationary inventory model with several demand classes. Operations research, 13(5):761–778, 1965. P. Whittle. Optimization over time. John Wiley & Sons, Inc., 1982. G. M. Ziegler. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.
page 64