Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes
2026-07-29 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how an agent can remember just enough about its past in situations where it can't see everything, to make good decisions. They focus on a special type of problem where visible actions shuffle hidden states in a predictable way and find the smallest possible memory needed to keep track of this. They show how to compress the agent's observations into stable groups that exactly represent the current situation and how to update this memory reliably. Their method allows standard reinforcement learning to work efficiently by using this special memory, and experiments confirm it matches ideal performance with less memory than other methods.
Partial ObservabilityMarkov PropertyPOMDPHolonomy-cover Decision ProcessStable QuotientMemory CompressionReinforcement LearningFinite-state ControllerState Abstraction
Authors
Zuyuan Zhang, Yongshan Chen, Mahdi Imani, Tian Lan
Abstract
An agent acting under partial observability must retain a recursively updateable statistic of history that restores the Markov property, but the smallest such statistic is generally unknown. We characterize this minimal Markov sufficient statistic for holonomy-cover decision processes, a structured POMDP class in which the visible dynamics are Markov and every realized visible transition applies a fixed permutation to a hidden mode. In particular, we construct the stable quotient, the coarsest observation-wise abstraction preserving one-step rewards and quotient successors, and prove that the pair of the current observation and stable class forms an exact finite Markov state. When the current class is correctly initialized, exact class tracking requires exactly the minimal memory symbols, in the sense that under reachability and pairwise decision separation at a maximizing observation, no arbitrary finite-memory controller can use fewer. Under resettable diagnostics, nearest-prototype class inference has exponentially decaying error, and a calibrate-then-restart reduction transfers finite-MDP guarantees to the recovered state. The results enable \emph{Holonomy Memory Reinforcement Learning}. It represents memory by the current stable class, updates it through ordered edge transports, identifies local class coordinates when diagnostics are available, and applies a standard finite-MDP RL backbone after synchronization. Experiments recover an exact compression from raw states to quotient states and achieve perfect paired-order accuracy with three decision-time memory states, matching the quotient oracle and outperforming the non-oracle baselines.