A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes
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 decision-boundary geometry induced by the policy becomes the primary object of analysis. We show that, under suitable structural regularity conditions, this geometry provides the minimal representation required for policy reconstruction and determines the statistical and computational complexity of the reconstruction problem. Building upon this representation, we establish structural properties of policy-induced decision geometry, introduce intrinsic notions of boundary and decision complexity, derive information-theoretic measures of decision compression, and obtain statistical guarantees for boundary estimation and policy reconstruction from black-box policy queries. Collectively, these results demonstrate that, for the structured decision problems considered here, the complexity of policy reconstruction is governed by the geometry of the decision boundary rather than by the cardinality of the ambient state space. Controlled numerical experiments examine the principal theoretical predictions and provide empirical evidence consistent with the proposed framework.
Related
- Dynamics to decision: A mathematical theory of Lyapunov spectra and decision boundaries in deep classifiers
- Latent Similarity Gaussian Processes: A Theory-Grounded Approach to Personalized Suicide-Risk Forecasting for Clinical Decision-Support
- Robust Markov Decision Processes: An Introduction Using Convex Optimization and Game Theory
- Geometric Boundaries of the Frohmanian Symplectic Tether: Formal Tracking of the 2D Clock Test and Open Analytic Inputs for Fefferman Statement (B)
- Scalable Learning of Determinantal Point Processes with Kernel-Structured Interactions
BibTeX
@misc{pokou2026geometric,
title = {{A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes}},
author = {Fredy Pokou},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18610},
eprint = {2609.18610},
archivePrefix = {arXiv},
url = {https://inria.hal.science/hal-05749004v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes
AU - Fredy Pokou
PY - 2026
DA - 2026/09/14
PB - HAL
DO - 10.48550/arxiv.2609.18610
UR - https://inria.hal.science/hal-05749004v1
AB - Classical dynamic programming represents optimal sequential decisions through value functions and policies. While this functional representation is natural for computing optimal decisions, it does not directly identify the mathematical object governing policy reconstruction, representation complexity, or oracle-query complexity once an optimal policy is fixed. This paper addresses this question by developing a geometric theory of structured optimal policies in which the decision-boundary geometry induced by the policy becomes the primary object of analysis. We show that, under suitable structural regularity conditions, this geometry provides the minimal representation required for policy reconstruction and determines the statistical and computational complexity of the reconstruction problem. Building upon this representation, we establish structural properties of policy-induced decision geometry, introduce intrinsic notions of boundary and decision complexity, derive information-theoretic measures of decision compression, and obtain statistical guarantees for boundary estimation and policy reconstruction from black-box policy queries. Collectively, these results demonstrate that, for the structured decision problems considered here, the complexity of policy reconstruction is governed by the geometry of the decision boundary rather than by the cardinality of the ambient state space. Controlled numerical experiments examine the principal theoretical predictions and provide empirical evidence consistent with the proposed framework.
ER -