Predictive Compression Conjecture for Efficient Long-Horizon Reinforcement Learning

If true, this would provide a principled route for turning extremely high-dimensional RL problems into tractable low-dimensional planning problems. It could explain when representation learning genuinely removes the curse of dimensionality rather than merely improving empirical performance, and would give a concrete target for algorithms that learn compact predictive state representations before planning. This could materially reduce interaction cost and compute in robotics, control, scientific discovery, and other long-horizon RL settings.

An MDP has state space S, action space A, transition kernel P, reward function r, and discount γ∈(0,1). Observations X may be high-dimensional and are generated from the underlying state. A representation φ maps observations to latent states Z. The representation is ε_r-reward preserving if |E[r|x,a]−E[r|x’,a]|≤ε_r whenever φ(x)=φ(x’). It is ε_p-predictive preserving if the total-variation distance between the distributions of φ(X_{t+1}) conditioned on (x,a) and (x’,a) is at most ε_p whenever φ(x)=φ(x’). The representation is ε-bisimulation-like if both conditions hold with errors small enough that value functions are preserved up to O(ε). Computational efficiency means polynomial-time computation in the representation dimension, action complexity, accuracy, and confidence parameters, with no polynomial dependence on the ambient observation dimension beyond the cost of reading an observation.

The MDP is discounted and rewards are bounded. The environment admits a compact predictive representation of dimension d. The representation class or learning procedure has sufficient capacity to express such a representation and has a tractable optimization or identification procedure. For the strongest version, assume access to trajectories generated by an exploratory policy whose state-action coverage is sufficient to identify predictive equivalence classes. The conjecture is about existence of an efficient learner under these structural assumptions; it does not claim that arbitrary high-dimensional RL is efficiently solvable.

Recent RL theory continues to identify sample efficiency, high-dimensional observations, partial observability, and long-horizon exploration as major bottlenecks. A 2026 survey emphasizes that representation learning can reduce effective complexity only when exploitable structure such as low intrinsic dimension or predictive regularity exists. Recent work also demonstrates substantial empirical gains from data selection, optimization conditioning, and latent-state methods, but these results do not establish a general theorem connecting predictive representation quality to computational and sample complexity. The conjecture asks for that missing bridge: a formal theorem showing that sufficiently accurate predictive compression is both learnable and sufficient for efficient near-optimal planning. Relevant recent context includes Ahmad, Vallès & Idaghdour (2026), “Statistical limits and conditional complexity in real-world reinforcement learning”; Tang et al. (ICLR 2026), “Towards High Data Efficiency in Reinforcement Learning with Verifiable Reward”; and Cheng et al. (ICLR 2026), “Sample Efficient Offline RL via T-Symmetry Enforced Latent State-Stitching.”

https://www.frontiersin.org/journals/artificial-intelligence/articles/10.3389/frai.2026.1847643/full https://proceedings.iclr.cc/paper_files/paper/2026/hash/374050dc3f211267bd6bf0ea24eae184-Abstract-Conference.html https://proceedings.iclr.cc/paper_files/paper/2026/hash/e23133d34964a0a09f6d076fc4b922a4-Abstract-Conference.html