Beyond Sparse Rewards: Self-Supervised Structural Reinforcement Learning via Combinatorial State Restoration

The pervasive bottleneck in scaling Reinforcement Learning (RL) for Large Language Models (LLMs) lies in the heavy reliance on sparse, human-annotated, and hard-to-verify reward signals. Furthermore, the inherent long-range structural and logical richness of vast, general-purpose pre-training corpora remains largely untapped by conventional RL paradigms. To surmount this bottleneck and inject a powerful new form of structural supervision, we introduce Combinatorial State Restoration (CSR), a novel self-supervised RL environment and task. CSR transforms canonical corpus documents into a sophisticated sequential decision-making challenge: the policy network is required to optimally reconstruct the original linear trajectory of textual macro-states (chunks) from a globally permuted observation space. This objective intrinsically compels the agent to internalize distant semantic dependencies and macro-narrative coherence, moving beyond simple token-level or span-level value predictions. By dynamically modulating the state fragmentation granularity and incorporating a multi-stage curriculum, CSR provides a robust, highly scalable, and resource-efficient verifiable reward mechanism. This approach leverages the ubiquity of unannotated data to generate an infinitely scalable stream of high-quality structural reasoning rollouts, fundamentally elevating the policy's capacity for generalized intelligence.