Learning Room-Like State Partitions from Few Transitions with Laplacian Rank Constraints

Reinforcement learning agents waste most of their experience rediscovering the same coarse structure: which states form a "room" and which transitions are the doors between rooms. Once that structure is known, an agent can plan over a handful of regions instead of thousands of states. This kind of compression is known to reduce how much data exploration needs, as shown when the symmetries are given in advance (Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction). Current spectral methods find this structure in two stages. They first learn smooth coordinates for each state from the graph Laplacian, a matrix built from which states the agent has seen lead to which. They then cut those coordinates into regions with k-means or thresholds. With little data, the observed transition graph is sparse and noisy, so the smooth coordinates blur and the second stage fails. That is exactly the stage where data is scarce.

We propose to learn the partition directly. The tool comes from graph clustering. A Laplacian rank constraint forces a learned similarity graph to split into exactly $k$ disconnected pieces, so the regions can be read off with no post-hoc clustering. In clustering benchmarks this constraint is markedly more robust to noisy affinities than two-stage spectral clustering (The Constrained Laplacian Rank Algorithm for Graph-Based Clustering). Our bet is that the sampling noise of a small, partly stale exploration buffer is the same kind of corruption. If so, the rank constraint should recover correct room partitions from several times fewer environment steps than eigenvector-then-k-means pipelines. Those partitions then define an abstract decision process and inter-region options that cut the total sample cost of learning many navigation tasks.

Core Claim

The claim is specific and falsifiable. First, a rank-constrained graph learned from an exploration buffer recovers ground-truth regions with fewer transitions than k-means applied to accurately learned Laplacian eigenvectors. Second, this advantage grows as the buffer becomes sparser or noisier. Third, it carries over to fewer total environment steps on multi-goal tasks, counting the exploration steps used to build the partition.

The first claim is the load-bearing one. If k-means on good eigenvectors matches the rank constraint at low data, the proposal reduces to existing eigenoption pipelines, and we will say so.

Research Program

Graph construction. From a buffer of $T$ observed transitions over visited states, we form a symmetrized, row-normalized count matrix $A \in \mathbb{R}^{n \times n}$, where $n$ is the number of visited states, or the number of anchor points in continuous domains. We then solve the L1 version of constrained Laplacian rank clustering:

$$\min_{S \ge 0,\; S\mathbf{1}=\mathbf{1},\; F^\top F = I_k} \; \|S - A\|_1 + \gamma\, \mathrm{Tr}(F^\top L_S F).$$

Here $S$ is the learned affinity and $L_S$ its Laplacian. $F \in \mathbb{R}^{n\times k}$ holds the eigenvectors for the $k$ smallest eigenvalues, and $\gamma$ is increased until those $k$ eigenvalues reach zero. By Ky Fan's theorem, the trace term equals the sum of the $k$ smallest eigenvalues. Driving it to zero forces $\mathrm{rank}(L_S) = n-k$, which means exactly $k$ connected components.

We choose the L1 loss because it tolerates outliers (The Constrained Laplacian Rank Algorithm for Graph-Based Clustering). Spurious or stale transitions behave like outlier edges, so the L1 version suits this setting.

Choosing $k$ and the penalty schedule. Two known weaknesses of rank-constrained methods are the need to fix $k$ and sensitivity to how fast the penalty grows. We address both. We select $k$ by the largest gap in the spectrum of $L_A$, and we report sensitivity across a sweep of $k$. The penalty $\gamma$ doubles whenever fewer than $k$ eigenvalues are near zero and halves whenever more than $k$ are. This is the standard adaptive rule from the clustering literature, and we report how often it shatters the graph into singleton components.

Continuous state spaces. Repeated eigendecompositions cost $O(n^3)$. In continuous domains we therefore first compress visited states into a few hundred anchor points and run the method on the anchor graph.

Using the partition. The learned components become macro-states. Observed transitions that cross components identify doorways. The counts of these crossings define an abstract decision process with $k$ nodes, which a high-level planner searches. For each adjacent pair of regions, an option, meaning a temporally extended skill, is trained to reach the doorway from region $i$ into region $j$. It uses a sparse intrinsic reward and is restricted to states in region $i$. This restriction directly attacks the inefficiency that Context-Specific Representation Abstraction for Deep Option Learning identified, where every option searches the whole state space. Our method enforces the restriction through a graph partition rather than through soft attention.

Theory. Impact of Connectivity on Laplacian Representations in Reinforcement Learning bounds the error of approximating values with Laplacian eigenvectors by a truncation term that grows like $1/\lambda_2$, where $\lambda_2$ is the graph's algebraic connectivity. Maze bottlenecks make $\lambda_2$ small. A partition, which forces $\lambda_2 = 0$ globally, might therefore look harmful.

We will show that it is not, by deriving a block-local version of the bound. In this version, each region $c$ gets its own eigenvector basis, and its error scales with that region's internal connectivity $\lambda_2^{(c)}$. A boundary term accounts for value coupling through doorways, which the high-level planner handles explicitly. Applying their bound per block suggests the truncation term should scale like $1/\min_c \lambda_2^{(c)}$. In walled mazes this quantity is much larger than the global $\lambda_2$. We will test this prediction numerically on gridworlds with an increasing number of walls.

Baselines

Naive references. The first reference point is a flat policy-gradient agent, trained with proximal policy optimization (PPO) and no abstraction. On MiniGrid KeyDoor, the flat advantage actor-critic agent reported in Context-Specific Representation Abstraction for Deep Option Learning scores 0.04 success reward, which shows how weak unstructured learning is there. The second reference point is ground-truth room labels supplied as an oracle partition. This gives an upper bound on what any learned partition can buy.

The key ablation. The strongest competitor on the partition question is two-stage: learn eigenvectors with the augmented Lagrangian objective of Proper Laplacian Representation Learning, which recovers ordered eigenvectors and eigenvalues, then run k-means. We also run the variant that first applies the reachability scaling of Reachability-Aware Laplacian Representation in Reinforcement Learning. That scaling stops distances from bleeding through walls and so should cluster better.

These pipelines receive the identical buffer, the same $k$, and the same downstream options and planner. The only thing that changes is how the partition is produced, which isolates the contribution of the rank constraint. We also report Towards Better Laplacian Representation in Reinforcement Learning with Generalized Graph Drawing as an eigenvector learner. Its reported similarity to ground-truth eigenvectors is 0.96 to 0.99 on GridRoom and GridMaze when given a well-covering offline dataset. Our baseline will therefore not be handicapped by poor eigenvectors in the high-data regime.

Classical spectral clustering. We also run normalized cut directly on $A$. Constrained Laplacian rank clustering generalizes normalized cut as $\gamma \to \infty$. On COIL20 it reports 87.36% accuracy against 79.44% for normalized cut (The Constrained Laplacian Rank Algorithm for Graph-Based Clustering), but that is image clustering, not reinforcement learning.

Downstream competitors. For downstream sample efficiency we compare against four methods:

All methods share the same exploration budget, network sizes, and an equal hyperparameter search of 20 configurations each. Exploration steps count toward every method's total.

What counts as beating them. The proposal succeeds if the rank-constrained partition reaches an adjusted Rand index of 0.9 against true rooms with at most half the transitions the ALLO-plus-k-means pipeline needs, on at least two of three maze families. It must also reduce total steps to a fixed multi-goal success threshold relative to the best downstream competitor. No reported adjusted-Rand partition numbers were found on Lacuna for any of these Laplacian learners, so we generate those curves ourselves.

Why not just…?

Why not just run k-means on well-learned eigenvectors? This is the real threat. When coverage is good, eigenvectors from the augmented Lagrangian or generalized graph drawing objectives are nearly exact, and k-means on them may match our method. The evidence that it degrades comes only from clustering, where two-stage methods collapse as affinity noise rises while rank-constrained learning holds up to noise level 0.8 (The Constrained Laplacian Rank Algorithm for Graph-Based Clustering). There is also the observation that unscaled eigenvectors bleed through walls (Reachability-Aware Laplacian Representation in Reinforcement Learning). Neither result shows the effect under reinforcement-learning sampling noise. Our partition-quality-versus-buffer-size curves settle the question directly. If the curves overlap at low $T$, we will drop the claim.

Why not just use classical normalized cut on the count graph? Normalized cut is the limiting case of our objective, so it is cheap to include. The difference is the L1 fidelity term, which can delete spurious edges rather than only reweighting them. A paired comparison under injected stale transitions shows whether that difference matters.

Why not just shape rewards with a good Laplacian distance and skip partitioning? For a single fixed goal, reachability-aware shaping or the Green's-function potential of From Representation to Action: A Unified Laplacian Framework for Spatial Representation and Path Planning, which reports 100% success with path length about 1.08 times optimal, may be as good or better. We concede that regime. A partition pays off when the same structure is reused across many goals and when environment changes are local. A door closing alters only the abstract edges, whereas a global potential must be recomputed. Our multi-goal and door-toggling experiments test exactly these cases.

Why not just detect bottlenecks with Value Power Strength? That method finds doorway states but not regions. It also needs many value functions trained on random rewards, and it is sensitive to value-estimation noise. We compare doorway-detection precision and total samples at equal budget.

Proposed Experiments

Partition recovery from few samples. The first and decisive experiment runs on GridRoom-4, GridRoom-16, GridMaze-9, and GridMaze-19, and on walled $30\times30$ grids following Giorgi et al. Using uniform-random and PPO-driven exploration buffers of increasing size $T$, we plot adjusted Rand index against true rooms for every partitioning method. We repeat this with a fraction of transitions drawn from an outdated policy, mimicking the replay-buffer staleness described in Online Laplacian-Based Representation Learning in Reinforcement Learning. The prediction is a leftward shift of our curve that widens with staleness.

Block-local value approximation. On the same grids we compute value approximation error for global versus block-local eigenvector bases as the number of walls grows. This checks whether error tracks $1/\min_c \lambda_2^{(c)}$ rather than $1/\lambda_2$.

Downstream sample cost. On MiniGrid MultiRoom and KeyDoor, and on PointMaze-FourRooms with anchor graphs, we measure total environment steps to 90% success averaged over held-out goals. Exploration steps are included, which addresses the concern that geometric methods merely move sample cost into pretraining. KeyDoor is a useful probe because its graph includes the has-key variable. A correct partition there should separate "before key" from "after key" states, a semantic split that Value Power Strength reports detecting.

Door toggling. A door-toggling variant tests whether re-solving only the affected blocks preserves performance more cheaply than recomputing global representations.

All results use 10 seeds with 95% confidence intervals. We will report the failure rate of the penalty schedule and sensitivity to $k$ as first-class results, not footnotes.