Geometry shapes decision policies in structured sequential problems
A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes
Machine Learning
Summary
Making good decisions step by step is usually done using mathematical methods that calculate how valuable each choice is. This paper looks at a different way by studying the shape and boundaries that separate one choice from another in structured problems. The authors show that understanding these boundaries helps explain how complex it is to recreate or learn the best decision strategies. They provide ways to measure this complexity and prove that it depends more on these geometric boundaries than just the size of the problem. Their theory is supported by computer simulations that match their predictions.
What this means in practice
- •For sequential decision system designers: Design models that reconstruct optimal policies efficiently by focusing on the geometry of decision boundaries instead of the full state space size.
- •For robotics control engineers: Improve policy learning algorithms with geometric insights to reduce computational overhead in structured decision tasks.
Tested on simulated data.
Authors
Fredy Pokou
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.