Reinforcement learning (RL) theory has strong guarantees for one restricted case. If the agent's value estimates are linear combinations of a fixed feature vector, and that feature space is "closed" under one step of planning, then efficient exploration with polynomial sample cost is provable. The guarantees weaken gracefully as closure fails. The size of the failure, called the inherent Bellman error, enters the regret bound multiplied by the square root of the feature dimension. Vision has its own well-studied failure: when a pole or another car crosses an object in an image, the object's visible pixels split into disconnected pieces. Detectors then report several objects where there is one, and trackers lose identity. This is occlusion-induced fragmentation.
This note proposes to connect the two by measurement. We will build environments where fragmentation can be dialed up and down. We will estimate the inherent Bellman error of different visual feature constructions directly, and test whether that number predicts how badly a provably efficient linear RL algorithm degrades. The central hypothesis is that occlusion contributes two separable kinds of Bellman error. The first, a splitting error, comes from a visible object being cut into a variable number of fragments. A perception module that groups fragments into a single object removes it. The second, a hiding error, comes from an object vanishing entirely. No per-frame grouping can remove it, because the information is not in the frame, so it needs memory. If this decomposition holds, it tells practitioners which perceptual machinery a linear learner actually needs. It also turns an abstract misspecification term into something one can measure and engineer.
Core Claim
The theory papers all take the feature map as given. Learning Near Optimal Policies with Low Inherent Bellman Error. (ELEANOR) proves regret of order $\sum_t d_t\sqrt{K} + \sum_t \sqrt{d_t}\,\mathcal{I}K$ with a matching lower bound. Here $d_t$ is the feature dimension at step $t$, $K$ is the number of episodes, and $\mathcal{I}$ is the inherent Bellman error. Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration (FRANCIS) works under the same low-error assumption for reward-free exploration. Neither asks where $\mathcal{I}$ comes from in a visual task. FLAMBE learns low-rank features from observations, but it assumes the observations are Markovian. Occlusion violates exactly that assumption.
On the vision side, Affinity Derivation and Graph Merge for Instance Segmentation reconnects fragments with long-range pixel affinities. SGN does so with a learned fragment-merging network. BCNet separates occluder and occluded object into two layers. All three are judged by mask precision, never by whether their outputs make downstream control easier.
Our claim is that inherent Bellman error is the right yardstick for occlusion-handling perception when the downstream learner is linear. We also claim it decomposes, approximately additively, into a splitting term and a hiding term. The splitting term should grow with the number of fragments for features computed on raw visible masks. It should stay flat for features computed after fragment association. The hiding term should be untouched by association and should drop only when features carry a persistent estimate of hidden objects. A second claim follows. Across conditions, measured $\mathcal{I}$ should predict the regret of least-squares value iteration better than either feature dimension or the perception module's segmentation precision does. If it does not, the misspecification term in the theory is not the operative bottleneck in visual RL, which is itself worth knowing.
Research Program
Environments with separable occlusion. We will build a JAX environment in the style of POBAX, which supplies memory-requiring partially observable tasks, including visually occluded Mujoco and maze domains. Our environment renders a small 2D scene from a known latent state: agent position, a few moving target objects with simple dynamics, and static occluders. Reward depends on the latent state, for example reaching or intercepting a target.
Two occluder knobs are varied independently. Thin bars cut objects into $k$ visible pieces without hiding them, which gives pure splitting. Wide slabs make objects fully invisible for a controllable fraction of time, which gives pure hiding. Because we own the simulator, we can reset to any latent state and draw many next-state samples. This generative access is what makes estimating Bellman error possible. Once the latent state is known, the task is designed to be approximately a linear MDP under an oracle feature map, namely radial-basis features of true object positions. That gives a reference with near-zero $\mathcal{I}$.
Feature constructions held to equal dimension $d$. All feature maps feed the same linear value function. There are five, ordered by how much occlusion structure they encode.
The first is a random projection of pixels. The second is per-fragment features: an instance segmenter's visible masks are each encoded to position and size, then pooled. The third is fragment-associated features: fragments are merged into one object per identity before encoding, using a perception module in the style of BCNet or affinity graph merge. The fourth adds amodal completion, which is shape completion of the hidden part as in Amodal Instance Segmentation With KINS Dataset.. The fifth adds persistence: a last-seen position and time-since-seen per object identity, carried across frames.
The persistence features make the representation a function of history rather than of the current frame. That is the honest way to address hiding, and it remains linear at the value layer.
Estimating inherent Bellman error. For a feature map $\phi$, we estimate
$$\hat{\mathcal{I}}(\phi)=\max_{w\in\mathcal{B}}\ \min_{v}\ \big\| r + \gamma\,\hat{\mathbb{E}}_{s'}\max_{a'}\phi(s',a')^\top w \;-\; \phi^\top v \big\|_{\infty,\hat{\rho}}$$
The symbols are as follows. $w$ ranges over a bounded ball $\mathcal{B}$ of linear value weights. $v$ is the least-squares projection of the one-step backup onto the features. $\hat{\mathbb{E}}_{s'}$ averages over 32 or more sampled next states from each reset state. The norm is the worst case over a held-out set of states $\hat{\rho}$, drawn from a mixture of the visitation distributions of all learners.
The outer maximum is approximated by gradient ascent on $w$ with restarts, seeded with the iterates the RL learner actually visits. We report both the adversarial value and the value at those visited iterates, because the theory's quantity is a worst case while practice may only touch a benign subset.
The splitting and hiding components come from the factorial design. Measuring $\hat{\mathcal{I}}$ on pure-bar, pure-slab, and combined scenes tests additivity directly.
Linear learners. We use least-squares value iteration with elliptical bonuses, the algorithm analyzed in On Reward-Free Reinforcement Learning with Linear Function Approximation. We also run its randomized variant from Frequentist Regret Bounds for Randomized Least-Squares Value Iteration. ELEANOR's global optimism is not computationally tractable in general, as its authors note. We will therefore run it only at very small $d$, as a check that the trends do not depend on the choice of optimism. For reward-free experiments we run FRANCIS-style randomized exploration. We also track the smallest eigenvalue of the feature covariance, to test the file's conjecture that hiding drives FRANCIS's explorability coefficient toward zero.
Perception modules. The fragment-association and amodal modules are trained on the synthetic occlusion dataset released with BCNet. Before any RL, we confirm they function on KINS and OVIS so that perception quality is a measured covariate rather than an unknown. Prior work makes one risk explicit: BCNet degrades on occluder types unseen in training. We therefore include held-out occluder shapes in the RL environments, so that perception failures propagate into $\hat{\mathcal{I}}$ and we can observe the effect.
Baselines
The naive reference point is the random pixel projection with a linear value function, plus per-fragment features with no grouping. These show what linear RL gets with no occlusion structure at all. Beating them is necessary but uninteresting.
The oracle reference is latent-state features. It bounds the achievable regret and calibrates the $\hat{\mathcal{I}}$ estimator, which should read near zero there.
The strongest competitor for the question of which features a linear learner should use is learned recurrent features. A recurrent network (GRU) encoder is trained with recurrent PPO, the strongest family evaluated in POBAX. It is then frozen at dimension $d$ and given to the same linear learner. This is the most serious rival because it can in principle learn both grouping and persistence from reward, without hand-designed perception. It gets the same environment interaction budget for representation pretraining that our perception modules get from supervised data, matched in total frames, plus the same hyperparameter search budget. No reported result was found on Lacuna for recurrent PPO returns on Visual Mujoco or MiniGrid mazes. POBAX reports only that memory agents substantially beat memoryless ones. So we will run it ourselves.
The ablation that isolates the key ingredient compares fragment-associated features with per-fragment features. Everything else is identical: segmenter, encoder, pooling, and $d$. The only difference is whether fragments of one object are merged. A second ablation adds or removes persistence on top of association.
For the perception modules, the reported reference numbers come from the cited papers. BCNet reports 28.87 AP for hidden-part prediction on KINS. ASN reports 32.2 amodal mAP on KINS, against a 30.4 PANet baseline. On OVIS, CMTrack R-CNN goes from 15.4 to 17.1 AP with BCNet's head, and baseline heavily-occluded AP falls as low as 5.6. Our modules need to land in that range for the RL conclusions to transfer to realistic perception.
Beating a baseline means lower measured $\hat{\mathcal{I}}$ and lower cumulative regret at the same $d$ and episode budget, with confidence intervals over at least ten seeds that do not overlap.
Why not just…?
Why not just use a recurrent network's hidden state and skip explicit grouping? This is the real threat. A GRU trained with enough reward signal may learn fragment association implicitly. If so, frozen GRU features would match our associated-plus-persistence features. OVIS gives indirect evidence that generic temporal models struggle under sustained occlusion: baselines peak at 16.3 mAP and drop to 5.6 AP on heavily occluded objects. That evidence comes from passive video, though, not reward-trained control, so it does not settle the question. The learned-GRU-features baseline settles it. If GRU features reach the same $\hat{\mathcal{I}}$ and regret, the conclusion becomes "learned memory suffices, and $\hat{\mathcal{I}}$ is the tool for verifying it." In that case the paper's contribution shifts to the measurement and decomposition, not the perception design. We also report the GRU's $\hat{\mathcal{I}}$ separately on pure-splitting scenes, where no memory is needed. This shows whether learned memory also learned grouping.
Why not just raise the feature dimension until the error disappears? Larger random or pixel features can shrink misspecification. But ELEANOR's bound and lower bound show that the leading regret term grows linearly in $d$, while misspecification is amplified by $\sqrt{d}$. So dimension trades one cost for another rather than escaping it. We sweep $d$ for the pixel and per-fragment features and plot regret against $d$. If some $d$ makes naive features competitive with associated features at small $d$, the structured approach loses its case, and we will report that.
Why not just run deep RL end to end and ignore linear guarantees? For raw return, deep recurrent PPO may well win, and we report it as a reference. The question here is different. It is whether occlusion structure can place visual tasks inside the regime where the linear theory's guarantees and diagnostics apply. Off-policy deep updates can diverge with function approximation, as Convergent TREE BACKUP and RETRACE with Function Approximation shows. The value of a measurable $\mathcal{I}$ is that it lets one predict failure before training.
Why not just track boxes with a Kalman filter? We include it as a persistence variant. A constant-velocity filter on detected box centers supplies the persistence features in place of last-seen memory. The affinity graph-merge paper documents that boxes on fragmented objects come out duplicated or bloated across the occluder. We therefore expect filtering without association to fix hiding but not splitting. The factorial design measures exactly this.
Proposed Experiments and Decisive Checks
The first check validates the estimator. $\hat{\mathcal{I}}$ for oracle features should be near zero. For latent features corrupted with known additive noise, $\hat{\mathcal{I}}$ should rise monotonically with the noise level.
The second check tests the decomposition on the factorial bar-by-slab grid. With bars only, per-fragment features should show $\hat{\mathcal{I}}$ increasing with fragment count $k$, while associated features stay flat. With slabs only, association should not help and persistence should. On combined scenes, the sum of the two single-factor excesses should approximate the joint excess. Large interaction terms would falsify the clean two-mechanism story.
The third check is predictive validity. Across all conditions, feature maps, and held-out occluder shapes, we compute the rank correlation between $\hat{\mathcal{I}}$ and the cumulative regret of least-squares value iteration at fixed $K$. We compare it with the correlations for $d$ alone and for the perception module's mask AP. The claim succeeds only if $\hat{\mathcal{I}}$ is the strongest predictor. It should also explain the cases where a higher-AP perception module yields worse control, which we expect under unseen occluders.
The fourth check covers reward-free exploration. On slab scenes, we test whether the smallest covariance eigenvalue along occluded-object coordinates collapses for non-persistent features. We then test whether FRANCIS-style exploration stalls accordingly. Finally, we transfer the best and worst feature constructions to POBAX's visually occluded Mujoco and maze tasks. There we cannot compute $\hat{\mathcal{I}}$ exactly, because next-state sampling depends on state copying in those environments. We will use the visited-iterate estimate where state copying is available, and report regret only where it is not.
References
- Learning Near Optimal Policies with Low Inherent Bellman Error
- Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
- FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
- Affinity Derivation and Graph Merge for Instance Segmentation
- SGN: Sequential Grouping Networks for Instance Segmentation
- Occlusion-Aware Instance Segmentation Via BiLayer Network Architectures
- Benchmarking Partial Observability in Reinforcement Learning with a Suite of Memory-Improvable Domains
- Amodal Instance Segmentation With KINS Dataset.
- On Reward-Free Reinforcement Learning with Linear Function Approximation
- Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
- Convergent TREE BACKUP and RETRACE with Function Approximation