Learned Stochastic Factorization: Exact Planning in a Small Latent MDP Discovered from Raw Observations

An agent that sees only pixels has two problems. It has to learn which features of the world matter, and it has to plan with whatever it learned. The theory of low-rank decision problems shows that if the next-state distribution can be written as a short sum of $m$ factors, both problems become easy. A separate, older line of work called stochastic factorization showed something more specific. If both factors are themselves probability tables, they can be multiplied in the opposite order to give an exact $m$-state Markov decision process, a small "latent MDP" that can be solved by ordinary policy iteration in time linear in the data. That older work needed hand-chosen kernels, so it never ran on images. The deep representation-learning methods that do run on images learn unconstrained features and then hand them to an actor-critic. That throws away the chance to plan exactly.

We propose to learn the two stochastic factors directly with neural networks, using a contrastive objective, and then plan exactly in the swapped $m$-state latent MDP. The two factors are a soft assignment of each (observation, action) pair to $m$ latent states and a soft "emission" from latent states back to observations. Exploration comes from an uncertainty bonus over the small latent table. The claim is narrow. A transition model constrained to be a mixture of $m$ latent states, and solved by exact dynamic programming, should beat the same contrastive representation fed to a gradient-trained critic in two regimes: when exploration is hard, and when the reward changes after the model is learned. In the second case, replanning costs seconds of latent value iteration instead of a new critic.

Core Claim and Mechanism

Write $D_\theta(z \mid s,a)$ for a softmax network that assigns state-action pairs to $m$ latent states. Write $b_\omega(z \mid s')$ for a second softmax network that assigns observed next states to the same latent states. Let $\rho$ be the replay-buffer distribution over states, and let $\bar b(z) = \mathbb{E}_{s \sim \rho}\, b_\omega(z \mid s)$ be the average assignment. We define the emission factor by Bayes' rule, $K(s' \mid z) = \rho(s')\, b_\omega(z \mid s') / \bar b(z)$. The model of the transition ratio is then

$$\frac{P(s' \mid s,a)}{\rho(s')} = \sum_{z=1}^{m} D_\theta(z \mid s,a)\, \frac{b_\omega(z \mid s')}{\bar b(z)}.$$

This is exactly a stochastic factorization $P = DK$. The emission density over images never has to be normalized, because $K$ lives on buffer states. The ratio form is what noise-contrastive estimation fits: a classifier separates true next states from buffer samples. We reuse that trick from Making Linear MDPs Practical via Contrastive Representation Learning, which introduced the auxiliary reference measure so that a contrastive loss stands in for intractable maximum likelihood. Our change is to force both factors onto the probability simplex. CTRL's features are unconstrained (they pass through tanh or exp), so they define a linear MDP, not a latent one.

Because both factors are stochastic, the swapped product gives a genuine latent MDP. Let $W(z)$ be the expected optimal value of a next state drawn from latent state $z$. It satisfies

$$W(z) = \mathbb{E}_{s' \sim K(\cdot \mid z)} \max_a \Big[ r(s',a) + \gamma \sum_{z'} D_\theta(z' \mid s',a)\, W(z') \Big],$$

and $Q(s,a) = r(s,a) + \gamma \sum_z D_\theta(z \mid s,a) W(z)$. Here $\gamma$ is the discount factor. The expectation over $K$ is an importance-weighted average over buffer states. This is the fixed point that Reinforcement Learning using Kernel-Based Stochastic Factorization iterates with Gaussian kernels and k-means representative states. Each sweep costs $O(nm|A|)$ for $n$ buffer states and $|A|$ actions, and the iteration is a contraction, so it converges exactly. That paper reports finishing double pole-balancing with $10^6$ transitions in under 7 minutes, against an estimated 6 months for kernel-based RL. Policy Iteration Based on Stochastic Factorization gives termination and performance-loss bounds for the same construction. We inherit the solver and its guarantees. We replace only the kernel, with one learned from data.

For exploration, the latent features $D_\theta(\cdot \mid s,a)$ are $m$-dimensional probability vectors. An elliptical bonus $\beta \|D_\theta(\cdot\mid s,a)\|_{\Lambda^{-1}}$, where $\Lambda$ is the $m \times m$ empirical covariance of visited latent features, is cheap to maintain and is added inside the latent value iteration. Theory supports this case. FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs shows that simplex (latent-variable) models are learnable with polynomial samples, using an exact maximum-likelihood oracle and explore-then-commit. Representation Learning for Online and Offline RL in Low-rank MDPs interleaves learning with optimism. Contrastive UCB shows that contrastive feature error shrinks at rate $1/\sqrt{k}$ in $k$ rounds, which is enough for near-optimism. None of these three runs the simplex case with neural networks, and none plans by factor-swapping. Our intended theoretical contribution is modest: carry the contrastive-UCB near-optimism argument through to the swapped latent MDP. The swapping step adds only the factorization error, which PISF already bounds.

Research Program

The work has three parts.

The first part builds the learner. It shares a convolutional or MLP encoder between two softmax heads, trains them with the ratio-form contrastive loss using buffer negatives, and adds an entropy regularizer that keeps latent states from going unused. Latent value iteration runs every few thousand environment steps, and a greedy or bonus-greedy policy is read off $Q$. Rank selection is a known weakness of factorization methods; Adaptive Low-Nonnegative-Rank Approximation for State Aggregation of Markov Chains adapts the nonnegative rank with an atomic regularizer. We take the simpler route of overprovisioning $m$ and pruning latent states whose average assignment $\bar b(z)$ falls below a threshold. We report sensitivity across $m \in \{32, 128, 512\}$.

The second part is analysis. We will measure, against ground truth on gridworlds, how closely the learned latent states match true bottleneck structure. We will also measure how the factorization error predicts the gap between the latent-MDP policy and the optimal policy, which tests whether the PISF-style bound is informative in practice.

The third part, the reward-transfer study, is where the approach should pay off most clearly. The model learns $D$ and $b$ reward-free, and then receives a sequence of new reward functions. For each one, it replans by latent value iteration, while competitors must retrain a critic.

We restrict the method to discrete actions. The max over actions inside the fixed point is the obstacle in the continuous case, and Low-rank MDPs with Continuous Action Spaces shows that continuous-action elliptical planning requires non-convex global optimization. Continuous control is therefore outside the core claim. We include it only as a discretized stretch experiment.

Baselines

The naive reference points are DQN-style model-free learning and SAC on the same encoder, with no auxiliary loss. These test whether any structured representation helps at all. For context on Atari 100K, Contrastive UCB reports a mean human-normalized score of 0.37 for DrQ and 0.26 for CURL.

The strongest competitor on our specific question is the same contrastive representation with a learned critic instead of exact latent planning. On Atari 100K that is SPR-UCB, which reports a mean human-normalized score of 0.69 against 0.62 for SPR (Contrastive UCB). On the gridworld and classic-control tasks, and on the discretized DMControl stretch experiment, it is CTRL-UCB with frozen features. CTRL-UCB reports 697.0 against SAC's 311.5 on walker_run_sparse (Making Linear MDPs Practical via Contrastive Representation Learning); that score is in the continuous-action setting, so it is only an upper reference for our discretized variant. All of these share our encoder architecture, replay data, number of environment steps, and wall-clock budget. Each gets the same hyperparameter-search budget of 20 configurations per domain. Beating SPR-UCB means a higher mean human-normalized score on the hard-exploration games it highlights (PrivateEye, Frostbite, Freeway), with non-overlapping 95% bootstrap intervals over at least 5 seeds. In the transfer study, beating CTRL means reaching within 5% of its final return on a new reward using at least 10× less compute after the switch.

EfficientZero (Mastering Atari Games with Limited Data) reports a 194.3% mean and 109.0% median human-normalized score. We report it as a ceiling and do not claim to beat it on aggregate Atari 100K. Its tree search, value-prefix model, and compute are a different budget class. On Minigrid and the classic tasks we found no reported result on Lacuna for EfficientZero, so there it is not a numeric baseline.

For the classical domains, the baseline is KBSF itself with Gaussian kernels on low-dimensional state (Reinforcement Learning using Kernel-Based Stochastic Factorization). The file reports runtime and qualitative success comparisons for KBSF, but no success-rate number usable as a target. Our method should match it on state inputs and keep working when the inputs are rendered images, where KBSF's kernels fail.

Three ablations isolate the key ingredients. Replacing the softmax heads with unconstrained heads turns the model into a CTRL-style linear MDP, which cannot be swapped. Planning that model with fitted Q-iteration on its features measures the value of exact latent planning. Replacing soft assignments with one-hot (Gumbel straight-through) assignments measures the value of soft aggregation over hard state abstraction. Removing the latent elliptical bonus measures the value of exploration.

Why not just…?

Why not just use CTRL's features with a standard critic? This is the most serious threat. The CTRL paper already finds that freezing contrastively learned features works well, and actor-critic methods are mature. Our argument is not that a critic cannot fit these features. It is that an exact solver over a small latent table removes a source of error and makes replanning nearly free. The unconstrained-head ablation and the reward-transfer study settle the question directly. If a frozen-feature critic matches us in final return and in replanning cost, the planning half of the proposal fails, and we will report that.

Why not just learn features first, cluster them, and run KBSF? This two-stage pipeline (CTRL features, then k-means representative states, then KBSF) is cheap and could plausibly come close. We run it as a baseline with the same features. The difference is that in a two-stage pipeline the clusters are not trained to make the factorization accurate: the factorization error that PISF's bound charges is never minimized. We predict the gap grows as $m$ shrinks, and we measure it at each $m$.

Why not use a hard discrete latent model, as in a block MDP? FLAMBE shows that low-rank and simplex models strictly generalize block MDPs, because they allow soft membership. Whether that generality matters in practice is open, and the one-hot ablation tests it. Our expectation is that hard assignment hurts on stochastic or aliased observations, such as partially observed gridworlds and sticky-action Atari, and is harmless on deterministic mazes.

Why not use self-predictive (BYOL-style) latents, which need no negatives? A Unifying Framework for Action-Conditional Self-Predictive Reinforcement Learning shows that these objectives fit low-rank approximations of the transition operator while implicitly optimizing distorted value targets. It also shows they impose no stochasticity, so their latents cannot be swapped into an MDP. We accept the cost of negative sampling to obtain a model that can actually be solved. SPR-UCB, which is BYOL-style, is our comparison point.

Proposed Experiments

The decisive check is reward transfer on Minigrid four-room and multi-room maps, and on a subset of five discrete-action Atari games. The agent learns the factors reward-free for a fixed step budget. It then faces ten new goal or reward specifications. For each one we measure return as a function of post-switch compute and environment steps, against CTRL with frozen features plus a fresh critic, and against the two-stage clustering pipeline. If latent value iteration does not reach comparable return with roughly an order of magnitude less post-switch compute, the main motivation fails.

The second check is online exploration. We run Atari 100K with emphasis on PrivateEye, Frostbite, and Freeway against SPR-UCB's reported numbers and our compute-matched reruns. We also run Minigrid sparse-reward tasks against CTRL-UCB and SPR-UCB.

The third check is fidelity. On double pole-balancing and Puddle-World, from both state and rendered-pixel inputs, we compare against KBSF. We report three things: whether learned latent states recover the representative-state structure KBSF reports (90 representative states summarizing 8,000 transitions on its tasks), whether measured factorization error predicts the policy-loss gap, and whether exact planning stays tractable at $10^6$ buffer transitions.

Discretized walker_run_sparse is reported as exploratory only, with the continuous-action limitation stated plainly.