cs.LGSep 16, 2026

A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes

Authors: Fredy Pokou

Organizations: MRE, INOCS

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.

Explore similar work

CardsList
Jun 24, 2026cs.LG

Low-Complexity Policy Tessellations in Structured Markov Decision Processes

We study optimal-policy geometry in structured Markov decision processes. While approximate dynamic programming and reinforcement learning typically approximate high-dimensional value functions, we show that optimal policies induce simpler decision tessellations. We propose boundary-based policy approximations that learn policy regions directly. A policy-loss decomposition links performance degradation to action margins and explains why errors concentrate near indifference boundaries. Inventory control and queue admission experiments show lower policy error, smaller value gaps, faster error decay, and stability than reinforcement learning baselines.
Fredy Pokou
Markov Decision ProcessesOptimal PoliciesPolygons
AskPDF
Jun 9, 2026cs.AI

Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets

Many Markov decision processes (MDPs) in operations research have feasible actions that are state dependent and defined implicitly by various operational constraints. These features make it difficult to use standard deep reinforcement learning (DRL) algorithms, whose action interfaces typically assume either a fixed finite action catalog or a simple Euclidean space. Motivated by a Taylor expansion of the optimal action-value function, we propose Bellman--Taylor score decoding, a framework that moves policy learning to a Euclidean score space while enforcing feasibility through an action decoder. The induced latent-score MDP then can be optimized by standard DRL algorithms without differentiating through the decoder. We provide a performance guarantee showing that the optimality gap of this approach decomposes into a structural approximation error and an algorithmic learning error. Lastly, we apply this framework to a queueing network control problem, where the policy essentially learns a state-dependent index-based dispatching rule. Numerical experiments show near-optimal performance in small instances and considerable improvements over benchmarks in larger systems.
Yi Chen, Rushuai Yang, Qiang Chen +2
Markov Decision ProcessesBellman EquationValue FunctionsAction SpaceDecisions
AskPDF
May 17, 2025cs.LG

Adaptive Resolving Methods for Markov Decision Processes with Function Approximations

Learning the optimal policy for Markov decision process problems (MDPs) from samples is a fundamental problem in online and data-driven decision-making. Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the MDP problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on a linear programming (LP) reformulation and repeatedly resolves the identified reduced linear system as new transition samples arrive. After the optimal basis is identified, we show that, after NN resolving rounds, the expected averaged iterate achieves an instance-dependent O~(Cinst/N)\widetilde O(C_{\mathrm{inst}}/N) objective shortfall and signed constraint residual. We separately account for the historical samples used for basis identification and the d2d_2 transition queries used in each resolving round, which yields the corresponding total transition-query complexity. We further complement our result with a \textit{robust} O(1/N)O(1/\sqrt{N}) bound that is independent of ΔΔ. In comparison to the guarantees established in the previous literature, our instance dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the wide applications and efficient empirical performances of our algorithms.
Jiashuo Jiang, Yinyu Ye, Yiming Zong
Markov Decision ProcessesOptimal PoliciesApproximationTransitionsDecisionsAction Space
AskPDF