Rank-Sized Ensembles for Exploring Low-Rank MDPs

Reinforcement learning agents explore well when they act on a plausible guess of how the world works and then correct that guess. Recent bandit theory shows that a surprisingly small collection of such guesses is enough. An ensemble whose size grows only with the problem dimension times the logarithm of the horizon matches exact Thompson sampling, the classic "sample a model from your posterior and act greedily" strategy. Separately, many environments have low-rank dynamics: the probability of moving from a state-action pair to a next state factors through a small number $d$ of latent features. We propose to join these facts. An agent should keep a small, shared-factor ensemble of perturbed latent transition models whose size scales with the rank $d$ of the dynamics, and plan with one sampled model per episode. The claim we test is that the ensemble size needed for deep exploration grows like $d \log T$ and does not depend on the number of actions or on the width of the neural representation.

This matters because every provably efficient online method for low-rank Markov decision processes (MDPs, the standard model of states, actions and stochastic transitions) explores with a deterministic bonus computed from a feature covariance matrix. That bonus is tied to a representation that keeps changing during deep training. It also has to be maximized over actions, which becomes awkward when actions are continuous. A randomized, rank-sized model ensemble avoids both problems. If the scaling claim holds, it also gives practitioners a principled rule for how many ensemble members to keep, where today that number is picked by habit.

Core Claim

Write the low-rank transition as $P(s' \mid s,a) = \langle \phi(s,a), \psi(s') \rangle$. Here $\phi(s,a) \in \mathbb{R}^d$ embeds the current state and action, and $\psi(s')$ embeds the next state. We learn $\phi$ with an action-conditional self-predictive objective, and a latent model predicts the next-state embedding $z'$ and the reward $r$ linearly from $\phi$. The ensemble does not store $M$ independent copies of this model. It stores a mean $\bar{\Theta}$ and a single shared factor $A_t \in \mathbb{R}^{(d \times d') \times M}$. At the start of each episode the agent samples a model

$$\Theta_\zeta = \bar{\Theta} + A_t \zeta, \qquad \zeta \sim \mathrm{Unif}\{\pm 1\}^M / \sqrt{M},$$

where $\zeta$ is a random sign vector. It then plans greedily in the latent space under $\Theta_\zeta$ for the whole episode. The factor $A_t$ is trained by the symmetrized two-sided ridge objective of Ensemble++ (explained below), applied to latent transition targets rather than to bandit rewards.

The new claims have three parts. First, the perturbation lives in the transition factor, not in the value head, so a single sample yields consistent optimism across many future steps and across reward functions. Second, the minimal $M$ that recovers exact-posterior performance scales as $\Theta(d \log T)$ in the transition rank $d$, and stays flat in the number of actions and in the backbone width. Third, the ensemble grows "anytime" by appending columns to $A_t$ on a doubling schedule, so no horizon has to be fixed in advance.

Relation to Prior Work

The mechanism comes from the logarithmic-ensemble line of work. Ensemble Sampling introduced perturbed-data ensembles as a stand-in for Thompson sampling. Ensemble sampling for linear bandits: small ensembles suffice proved that $m = \mathcal{O}(d \log T)$ members with symmetric $\pm 1$ perturbations give $\mathcal{O}((d\log T)^{5/2}\sqrt{T})$ regret even over continuous action sets. Improved Regret of Linear Ensemble Sampling sharpened this to $\tilde{\mathcal{O}}(d^{3/2}\sqrt{T})$, but its argument needs $m = \Omega(K\log T)$ and a finite set of $K$ arms.

Scalable Exploration via Ensemble++ and HyperAgent (Li et al.) replace the independent replicas with one shared factor. That factor is updated incrementally by a symmetrized ridge objective, and the required size $\Theta(d\log T)$ does not depend on the number of actions. We reuse this machinery directly. However, all of these works are single-step bandits with given features. None of them has transitions, multi-step credit assignment, or learned dynamics factors. The tension between the two bounds, a looser rate over continuous actions versus a tighter rate that needs $K$-dependent size, is exactly what our action-count sweep probes empirically.

The low-rank MDP line supplies the setting and motivates the gap. FLAMBE learns $\phi,\psi$ by maximum likelihood and explores by elliptical planning. REP-UCB interleaves representation learning with a covariance-based bonus and needs roughly $d^4 A^2/\epsilon^2$ samples. Contrastive UCB recovers the factors with a temporal contrastive loss and adds the same kind of bonus, with a practical variant (SPR-UCB) on Atari. All three explore deterministically through $\|\phi\|_{\Sigma^{-1}}$ and carry action-count dependence in their guarantees. We keep their representation learners and replace only the exploration mechanism.

A Unifying Framework for Action-Conditional Self-Predictive RL constrains our design in two ways. It shows that action-conditional self-prediction learns a low-rank approximation of per-action dynamics $T_a$, which justifies using it as our $\phi$ learner. It also identifies a "modified value function trap", in which such representations bottleneck value fitting. We therefore report whether model-space randomization changes value-fitting error, rather than assuming it does.

Stochastic factorization contributes a planning trick. It shows that swapping the factors of a factored transition matrix gives a small $d \times d$ latent chain that preserves the planning-relevant structure. We use it to make per-sample planning cheap in the tabular and synthetic settings.

Research Program

The work has four parts.

The first part builds the agent. It uses a self-predictive encoder in the style of SPR/BYOL-AC for $\phi$, a linear latent transition and reward model on top, and a shared-factor ensemble over that model trained with Ensemble++'s symmetrized objective on a first-in-first-out buffer. Each episode samples one model and plans with it. Planning is exact latent value iteration on the swapped $d\times d$ chain in small domains, and short latent rollouts that feed the value target in Atari.

The second part is a controlled scaling study on synthetic low-rank MDPs, where we set the rank $d$, the number of actions $K$, and the representation width independently. For each configuration we find the smallest $M$ whose regret is within 10% of an exact Gaussian posterior sample of the same latent model, which is only computable in this synthetic regime. We then fit the dependence of that minimal $M$ on $d$, $K$, width and $T$.

The third part addresses representation drift. When $\phi$ is retrained, a covariance matrix accumulated on old features becomes stale. We measure how quickly an SGD-updated shared factor re-calibrates, compared with periodically recomputing the covariance.

The fourth part is a modest theory step. It extends the master regret argument of Janz et al. to linear MDPs with known $\phi$ and model-space perturbations, which is the case where it most plausibly goes through. We state openly that learned-feature guarantees remain out of scope.

Baselines

The naive reference is base SPR with ε-greedy exploration, run on the same encoder, data budget and tuning budget. It tells us whether any structured exploration helps at all. On Atari 100K, Contrastive UCB reports a mean human-normalized score of 0.62 for base SPR.

The strongest existing method is SPR-UCB from the same paper. It adds a covariance bonus on learned features to SPR and reports a mean human-normalized score of 0.69 on Atari 100K, against 0.37 for DrQ and 0.26 for CURL. It is the strongest competitor because it uses the same representation family and targets exactly the hard-exploration games we care about. We will rerun it in our codebase with identical encoder, replay and hyperparameter search budget, and treat our own rerun as the reference. Beating it means a higher mean and interquartile-mean score across the 26 games over at least five seeds, with the gain concentrated on PrivateEye, Frostbite and Freeway. On deterministic-start MountainCarContinuous we compare against CODEX. That paper reports only that it discovered about twice as many unique states as MaxEnt and uniform random exploration, with no absolute count. Beating it means greater unique-state coverage and faster first goal-reaching at equal environment steps. For Minigrid, no reported result found on Lacuna for exploration return; the Khetarpal et al. results there concern value fitting.

The key ablation isolates where the perturbation lives. It is the obvious transplant: Ensemble++ applied to the linear Q-value head on the same $\phi$, with the same $M$ and the same update rule. If this matches our model-space variant, the transition-factor story is unnecessary. A second ablation replaces the shared factor with $M$ independent bootstrap heads at equal parameter count, which tests whether the shared factor matters beyond parameter savings.

Why not just…?

Why not just keep the elliptical UCB bonus, which is cheap with rank-one inverse updates? This alternative is a real threat on discrete-action Atari. There, updating a $d\times d$ inverse costs $O(d^2)$ per step, no more than updating our factor. Our argument is not raw compute. It rests on two other points. First, the bonus must be maximized jointly with $Q$ over actions, which is non-convex for continuous actions, whereas a sampled model is simply planned against. Second, the accumulated covariance goes stale whenever $\phi$ is retrained. The drift study and the MountainCar comparison test these points directly. If SPR-UCB matches us on Atari and continuous control, we will report the ensemble as offering no advantage in discrete settings.

Why not just sample from an exact Gaussian posterior on the value head, as randomized least-squares value iteration does? In the synthetic study this is precisely our upper reference, and in fixed-feature linear MDPs we expect it to be as good as our method. The open question is whether it remains calibrated under representation drift and whether value-space randomization gives the same multi-step, reward-agnostic optimism as model-space randomization. The head-versus-model ablation and the drift study answer this. If value-head sampling wins, the proposal reduces to "use Ensemble++ as a cheap value-head posterior", and we will say so.

Why not just use a large Bootstrapped-DQN-style ensemble? Prior theory for such ensembles required size linear in the horizon; LinPHE is the special case $m = T$ in Lee and Oh. Ensemble++ already dominates Ensemble+ and EpiNet on the regret-versus-parameters frontier in bandits. Our scaling study extends that comparison to MDPs by plotting regret against parameter count for independent heads and for the shared factor.

Proposed Experiments

The decisive check is the synthetic scaling sweep, which can support or refute the claim independently of the other results. The claim holds if minimal $M$ grows roughly linearly in $d$ and in $\log T$, and stays flat as $K$ rises from 4 to 256 and as backbone width rises fourfold. The claim fails if minimal $M$ tracks $K$ or width. A $K$-dependence would indicate that the Lee–Oh finite-arm mechanism, not rank, governs MDP ensembles.

The second check is the head-versus-model ablation on the synthetic suite and Minigrid. Model-space perturbation should reach rewards faster in long-horizon sparse tasks. It should also transfer its exploration to a new reward without retraining, which a value-head ensemble cannot do.

The third check is Atari 100K and deterministic-start MountainCar against the rerun SPR-UCB and CODEX baselines under equal budgets. We also report value-fitting error, to see whether the modified value function trap limits the gains.