Planning Exploration in a Factor-Swapped Latent MDP

Reinforcement learning agents that learn from pixels need hundreds of thousands to millions of interactions. Much of that cost comes from exploring blindly. A well-established theory says the cost can shrink sharply when the environment's dynamics are low-rank, meaning next-state probabilities are produced by a small number $d$ of hidden factors. The algorithms that achieve those guarantees, however, depend on optimization steps that nobody can run on neural networks. The practical deep-RL descendants of this theory keep the low-rank features but replace the theory's exploration with a one-step bonus that ordinary Q-learning has to propagate slowly. This proposal takes a different route. We constrain the learned factorization to be stochastic: every observation is softly assigned to one of $m$ latent "anchor" states, and every action moves probability mass among anchors. An old trick from kernel-based RL, swapping the order of the two factors, then turns the agent's replay buffer into an exact, tiny $m \times m$ transition model. A small model like this can be solved optimistically, by value iteration, in milliseconds.

The core claim is that the expensive "plan to explore" step of provably efficient low-rank RL becomes cheap if the factorization is stochastic rather than merely low-rank. Planning an exploration bonus through the swapped latent model yields deep, multi-step exploration that heuristic bonuses on learned features do not. We will test whether this produces measurable sample-efficiency gains on the hard-exploration games of Atari 100K, at matched compute, on top of the strongest model-free agents.

Background and the gap

Theory on low-rank MDPs, decision problems where $P(s' \mid s,a) = \langle \phi(s,a), \psi(s') \rangle$ for unknown $d$-dimensional maps $\phi, \psi$, has steadily tightened sample complexity. FLAMBE learns features by maximum likelihood and then explores with an "elliptical planner," but its bound scales as roughly $d^7 A^9/\epsilon^{10}$. REP-UCB interleaves learning and optimism and improves the bound to $\tilde O(d^4A^2/\epsilon^2)$. RAFFLE does reward-free exploration and proves an $\Omega(HdK/\epsilon^2)$ lower bound. All three motivate this work, because they show low-rank structure should buy exploration efficiency. All three also constrain it, because each assumes a likelihood-maximization oracle over a finite model class and a planner that solves a global non-convex problem. Neither is tractable for neural networks.

The practical bridge is Contrastive UCB. It proves that a temporal contrastive loss recovers low-rank features, then builds SPR-UCB: Self-Predictive Representations plus an elliptical bonus on the learned embedding. It reports 0.69 mean human-normalized score on Atari 100K versus 0.62 for SPR, with gains concentrated in PrivateEye, Frostbite and Freeway. This is the closest prior work. It differs from our proposal in two ways. Its bonus is added to the per-step reward and spread by temporal-difference learning, so the agent cannot plan toward uncertainty that lies several steps away. And its practical loss drops the negative samples that its theory needs. A Unifying Framework for Action-Conditional Self-Predictive RL adds a constraint. It shows that SPR-style objectives compute low-rank approximations of the per-action transition matrices but fit "modified" value functions with projected reward artifacts. This warns us against relying on the representation alone to carry value information, which is one reason we plan with an explicit latent model instead.

The method we reuse comes from an older line that never touched exploration. Kernel-Based Stochastic Factorization and Policy Iteration Based on Stochastic Factorization write $P \approx DM$ with both factors row-stochastic and observe that $MD$ is an $m \times m$ stochastic matrix that preserves the dynamics. Using this, KBSF delivered a double-pole-balancing policy in under 7 minutes where full kernel-based RL would need about 6 months, and PISF solved a 40-million-state maintenance problem in under 5 hours. But they select anchors by k-means over fixed data and offer no exploration or sample-complexity guarantees. Our contribution is to learn the anchors from pixels and to use the swapped model for optimism.

Core Claim

Let $D_\theta(s) \in \Delta^m$ be a softmax encoder assigning observation $s$ to $m$ anchors. Following KBSF, let $M_a(z,\cdot)$ be the distribution over buffer next-states $s'_i$ from action-$a$ transitions, weighted by how strongly the source state $s_i$ belongs to anchor $z$. The swapped latent model is then computed directly from the replay buffer $\{(s_i,a_i,r_i,s'_i)\}$:

$$K_a[z,z'] \;=\; \frac{\sum_i \mathbb{1}[a_i=a]\, D_\theta(s_i)_z\, D_\theta(s'_i)_{z'}}{n_a(z)}, \qquad n_a(z) = \sum_i \mathbb{1}[a_i=a]\, D_\theta(s_i)_z .$$

Here $n_a(z)$ is a soft visit count for anchor $z$ under action $a$. The weight that anchor $z$ gives to buffer row $i$ is $\mathbb{1}[a_i=a]\, D_\theta(s_i)_z / n_a(z)$, so each row of $K_a$ is a weighted average of next-state assignments and is exactly stochastic. No transition network is learned.

Exploration is driven by an optimistic latent value $U$. We compute it by value iteration on

$$U(z,a) = \frac{\beta}{\sqrt{n_a(z)+1}} + \gamma \sum_{z'} K_a[z,z'] \max_{a'} U(z',a'),$$

where $\beta$ scales the bonus and $\gamma$ is the discount. The agent acts greedily on $Q_\omega(s,a) + \lambda \sum_z D_\theta(s)_z U(z,a)$, where $Q_\omega$ is the base agent's value network and $\lambda$ is a mixing weight that we anneal. Because $U$ is a planned quantity, an anchor whose neighbors are well-visited but which leads to unvisited regions three steps later still receives a high value immediately. A temporal-difference-propagated bonus cannot do this within a 100K-step budget.

Stochastic factorization is a restricted form of low-rank structure. It assumes non-negative rank, the "latent variable" subclass. For that subclass, the swapped model is a tabular MDP with $m$ states, and UCRL-style analysis applies with $m$ in place of $|\mathcal S|$. That gives a concrete theoretical target alongside the empirical one.

Research Program

The first component is representation learning for $D_\theta$. The encoder is trained so that the swapped model predicts well. Concretely, we minimize the cross-entropy between $D_\theta(s)^\top K_a$ and a stop-gradient target $D_{\bar\theta}(s')$, using a momentum encoder as in SPR. Assigning everything to one anchor would satisfy that loss trivially, so we prevent this collapse with a balanced-assignment constraint (Sinkhorn normalization of anchor usage within each batch), an inverse-dynamics head, and a contrastive term with buffer negatives. The negatives also let us test the theory-to-practice gap that Contrastive UCB left open, by switching them on and off.

The second component is the planner. $K_a$ and $n_a$ are recomputed from the buffer every few thousand steps, which is a matrix product over the buffer. Value iteration then runs on $m \le 1024$ anchors and 18 actions on GPU. We will report the wall-clock overhead, since the file documents that EfficientZero's search roughly doubles training cost.

The third component is analysis. In synthetic latent-variable MDPs with known rank, we will verify that $K_a$ recovers the true latent dynamics. We will then measure how episodes-to-solve scale with horizon and rank, and compare against the theory's predicted polynomial dependence.

Baselines

The naive reference point is the base agent with no exploration term, run with $\lambda = 0$. We use both SPR, reported at 0.62 mean human-normalized score in Contrastive UCB, and BBF. BBF is a scaled, regularized, reset-based model-free agent reported at 1.045 interquartile-mean human-normalized score on Atari 100K. It is the strongest competitor because it already reaches human-level efficiency without any dynamics model. Our method will be added on top of BBF unchanged, with BBF's published hyperparameters, so any gain is attributable to the exploration term. Beating it means a statistically reliable improvement in interquartile mean, with stratified-bootstrap confidence intervals over at least 10 seeds, at equal environment steps and with GPU-hours reported.

The closest structural competitor is SPR-UCB. We will reimplement it on the same base agents and tune its bonus scale with the same budget we use for $\beta$ and $\lambda$. The file reports only its mean score (0.69), which is a different metric from BBF's interquartile mean. We will therefore report mean, median and interquartile mean for every method rather than compare across metrics. There is no reported result found on Lacuna for per-game scores of SPR-UCB on PrivateEye, Frostbite or Freeway, so those comparisons rely on our reruns. EfficientZero (194.3% mean, 109.0% median in Mastering Atari Games with Limited Data) is reported as a compute-heavy reference rather than a matched competitor.

Two ablations isolate the key ingredient. The first, "anchor counts without planning," adds $\beta/\sqrt{n_a(z)+1}$ for the current state's anchors directly to the reward and lets temporal-difference learning propagate it. The second, "k-means anchors," replaces the learned $D_\theta$ with k-means over SPR embeddings, as in KBSF, but keeps the planner. If the first ablation matches the full method, planning through the swapped model is not doing the work. If the second matches it, learning the factorization is unnecessary.

Why not just…?

Why not just use BBF, since scale and resets already reach human-level efficiency? This is the real threat. On average-case games, BBF may leave little room. The BBF authors acknowledge that it remains below human level on some games, and the Contrastive UCB results suggest those are exploration-limited. Our claim is therefore deliberately narrow: gains should concentrate on hard-exploration games with no loss elsewhere. If BBF plus our term does not beat BBF on that subset, the idea fails.

Why not just use SPR-UCB's elliptical bonus? An elliptical bonus measures one-step novelty in feature space. Value further away arrives only through slow bootstrapping, and SPR-UCB's gain over SPR (0.69 vs 0.62 mean) is modest. The "counts without planning" ablation directly tests whether planning, not the count form, explains any improvement over SPR-UCB.

Why not just cluster SPR embeddings and use pseudo-counts? Clustering after the fact is exactly KBSF's anchor heuristic, and that line notes it misses narrow dynamical bottlenecks. Clusters chosen for visual similarity need not make $K_a$ predictive. The k-means ablation settles this: if it performs as well, we will report that the stochastic factorization adds nothing beyond the planner.

Why not just use model-based tree search like EfficientZero? It is more sample-efficient in aggregate but costs several times the compute. It also explores through its learned policy rather than through explicit uncertainty. We report it as an upper reference and measure our overhead, which comes from value iteration on at most 1024 states, against BBF's GPU-hours.

Proposed Experiments

The first experiment uses synthetic latent-variable "combination lock" MDPs, where the correct action at each of $H$ steps must be found among many distractors and observations are noisy renderings of $m^\star$ latent states. Here we measure episodes-to-solve as $H$ and $m^\star$ grow, along with the error of $K_a$ against the true latent transition matrix. The decisive check is whether the full method scales polynomially in $H$ while the counts-without-planning ablation degrades sharply. That pattern is the signature of deep exploration.

The second experiment is Atari 100K, all 26 games, 10+ seeds, reporting interquartile mean, mean and median human-normalized score. We designate PrivateEye, Frostbite and Freeway as the pre-registered exploration subset, since the file identifies them as where bonuses helped. The decisive check is a reliable gain over BBF on that subset with no significant interquartile-mean loss on the remaining games, and a gain over SPR-UCB on SPR at matched tuning. A secondary check sweeps $m$ to confirm that performance is not tied to a single anchor count. A further check removes the contrastive negatives to see whether recovering the theory's negative sampling matters in practice.