1 Introduction↩︎

Large language model (LLM) agents have demonstrated remarkable capabilities across complex interactive tasks, from embodied household reasoning [1] and text-based games [2] to symbolic reasoning [3], by combining natural-language reasoning with environmental interaction [4], [5]. Reinforcement learning (RL) has become a central training paradigm for these agents [6], [7], with multi-turn agentic variants of GRPO now driving much of the recent progress on long-horizon decision-making [8]–[11].

Yet a persistent challenge is that RL training often entrenches brittle behavioral shortcuts. This failure mode, sometimes termed reasoning collapse, arises when prolonged optimization amplifies memorized action patterns at the expense of transferable reasoning [12]–[14]. We do not claim this failure has a single cause; rather, we isolate one structural factor we can both formalize and act on: rewarding task success alone permits idiosyncratic, one-off solution patterns that satisfy the training tasks but transfer poorly. Crucially, compact, repeated solution patterns are desirable for generalization, so the difficulty is not that the policy forms shortcuts but that it also forms idiosyncratic ones that complete training tasks without composing into reusable skills. Recent efforts combat this by augmenting RL with reusable structure or experience via teacher distillation [10], reflection loops [11], or external memory [5], [15], [16]. But it remains unclear which shared structural property of the learned behavior is responsible for their gains.

We argue that existing methods that improve agent RL do so because they implicitly encourage the formation of reusable structure. In both reinforcement learning and information theory, such reusable structure is closely tied to data compression and the Minimum Description Length (MDL) principle [17], [18]. This connection suggests a broader conjecture: successful, generalizable behaviors are precisely those that admit compact, reusable decompositions. We formalize this property as the structural compressibility of successful trajectories, defined as the degree to which successful behavior, represented as a sequence of abstract skills, is built by composing a small set of reusable patterns. As illustrated in Fig. 1, an agent whose successes decompose into a compact repertoire of reusable skill compositions reasons more robustly than one that relies on idiosyncratic, one-off sequences. This perspective naturally bridges temporal abstraction in hierarchical RL, where options compress behavior into reusable subroutines [19], with the MDL principle. While BPE-based action tokenization [20], [21] and MDL-guided skill discovery [22], [23] have begun bridging these ideas by treating behavioral abstraction as compression, none integrate this compression directly into the RL training signal as a trajectory-level penalty for LLM agents. Consequently, the compression-generalization hypothesis remains untested in this setting.

To test this hypothesis, our contributions are as follows. (1) We first formalize the hypothesis that structural compressibility is a key driver of reasoning generalization in RL-trained LLM agents. (2) We introduce ReuseRL, a minimal framework that extracts a shared skill dictionary online from successful trajectories via greedy BPE-style merging and augments the per-trajectory GRPO signal with the resulting segmentation cost. (3) We ground our framework in the MDL principle via an EM-style alternating optimization, show that the pure round-length penalty is a degenerate fixed-code segmentation cost (Proposition 1), establish a PAC-Bayes generalization bound (Theorem 2), and provide a unifying interpretation of SkillRL and ERL as implicit, partial MDL minimizers. (4) On ALFWorld [1], TextWorld-Cooking [2], and Countdown-Stepwise [3], ReuseRL improves over both vanilla GRPO and the pure round-length baseline. Crucially, these results validate our central premise: successful trajectories should not merely be short; they should be compressible under a reusable skill dictionary. We isolate this effect in a self-contained RL loop, deliberately omitting experience-augmented methods like SkillRL or ERL that rely on auxiliary supervision. This allows us to rigorously validate the standalone impact of the MDL principle without confounding variables.

2 Related Work↩︎

2.1 Grammar-Based and MDL-Guided Hierarchical Abstraction↩︎

Skill discovery can be framed as sequence compression, where hierarchical abstraction yields reusable subroutines. Grounded in the MDL principle [17], [18], prior methods learn compact skill codebooks that balance dictionary size against how well the data is described [22], [23]. In RL, BPE-style merging of frequent action patterns extends this idea to temporally extended macro-actions [24]. PRISE [21] applies compression-based abstractions to improve sample efficiency, and SkillVLA [25] leverages reusable skills for combinatorial task diversity in embodied settings. PAC results for state abstraction [26] further show that compressed representations can preserve near-optimal behavior. ReuseRL builds on this line of work but applies the MDL objective online, as a per-trajectory RL signal on successful behavior, instead of as an offline criterion for constructing reusable skills.

2.2 Skill Consolidation and Experience-Augmented Reasoning↩︎

LLM agents increasingly build skills through environmental interaction. During training, ERL [11] and SkillRL [10] distill environmental feedback into behavioral corrections. Similarly, systems like RAGEN [12] and DYSTIL [27] self-improve through dense feedback, while others rely on retrieved past experiences [5], [15], [16]. Left unchecked, however, accumulating self-generated trajectories can trigger reasoning collapse, amplifying memorized shortcuts at the expense of transferable behavior [12], [14]. This motivates explicit compression of reusable behavioral structure as a regularizer, which is exactly what ReuseRL adds without relying on teacher distillation, retrieval, or other auxiliary modules.

2.3 Information-Theoretic Policy Compression↩︎

Recent works apply information-theoretic objectives to constrain LLM reasoning traces, such as adaptively penalizing raw reasoning length [28]–[30] or measuring token cost via surprisal under a language-model prior [31]. Crucially, these approaches shape reasoning at the token or length level. In contrast, ReuseRL operates at the behavioral level by compressing the structure of successful skill sequences rather than their surface-level length.

3 ReuseRL: Skill Reuse as Compression RL↩︎

3.1 Problem Setup and Skill Projection↩︎

We consider a task distribution \(\mathcal{D}\) over multi-turn reasoning tasks. For each sampled environment \(d \sim \mathcal{D}\), a language model policy \(\pi_\theta\) interacts with a partially observable environment for at most \(T\) steps, producing a trajectory \(\tau \sim \pi_\theta(\cdot \mid d)\) of the form \(\tau = (o_1, a_1, o_2, a_2, \ldots, o_T, a_T)\), where \(o_t\) is the observation and \(a_t\) is the action at step \(t\). Each trajectory receives a binary terminal reward \(R(\tau) \in \{0, 1\}\) indicating success or failure. The standard RL objective maximizes the expected per-trajectory success rate: \[\label{eq:rl-objective} \max_\theta \; \mathbb{E}_{d \sim \mathcal{D},\; \tau \sim \pi_\theta(\cdot \mid d)} \bigl[ R(\tau) \bigr]\tag{1}\] In GRPO-style training [7], Eq. 1 is optimized through sampled batches \(\mathcal{B} = \{(d_i,\tau_i)\}_{i=1}^{n}\) and per-trajectory advantages computed inside each batch. As argued in §1, the structural factor we isolate is the absence of pressure toward structurally reusable successful behavior under a success-only reward. The remainder of this section makes this notion precise: we represent behavior as a sequence of atomic skills, measure its reuse through a shared skill dictionary, and derive the per-trajectory signal that rewards compressible successful behavior.

3.1.0.1 Skill alphabet and projection.

We represent behavior at a higher level as a sequence of discrete atomic skills, where each skill corresponds to an interpretable primitive such as Explore, Take, etc. Let \(\Sigma = \{\sigma_1, \ldots, \sigma_{K_\Sigma}\}\) denote a finite atomic skill alphabet, where each \(\sigma_i\) is a skill. A skill projection \(\varphi\) maps each trajectory \(\tau\) to a skill sequence \(s \in \Sigma^*\), abstracting away low-level action details: \(\varphi: \tau \mapsto s \in \Sigma^*\). \(K_\Sigma := |\Sigma|\) is the size of the skill alphabet and \(^*\) denotes the Kleene star. In our instantiation, \(|\Sigma|\) is small and environment-specific, and \(\varphi\) is implemented by a rule-based mapping over the verbs of the raw actions; per-environment mapping rules are summarized in §4.

3.1.0.2 Skill dictionary.

To measure structural reuse, we represent successful behavior using a skill dictionary \(\mathcal{C} = \{p_1, \ldots, p_M\}\), where each entry \(p_j \in \Sigma^{\leq L}\) is a short skill sub-sequence of length at most \(L\). Each \(p_j\) is therefore a reusable subsequence of atomic skills, and \(|p_j|\) refers to the number of atomic skills in \(p_j\). Given the group of successful trajectories \(\mathcal{B}^+\), we restrict our attention to the universe of valid dictionaries, \(\mathcal{A} := \{\mathcal{C} \subseteq \Sigma^{\le L} : \Sigma \subseteq \mathcal{C}\}\), which guarantees that every dictionary contains all atomic singleton skills. This ensures that any atomic skill sequence \(s=\varphi(\tau), \tau\in\mathcal{B}^+\) can always be exactly represented using phrases from \(\mathcal{C}\), in the worst case as a concatenation of singletons. Given \(s\) and \(\mathcal{C}\), let \(\mathrm{seg}(s,\mathcal{C})\) denote the minimum number of dictionary phrases needed to cover \(s\) exactly; we compute this quantity by dynamic programming. Smaller values of \(\mathrm{seg}(s,\mathcal{C})\) indicate that \(s\) is more compressible under \(\mathcal{C}\). Since \(\mathcal{B}^+ \subseteq \mathcal{C}^*\) and \(\varphi\) assigns at most one skill label per environment step, every non-empty skill sequence satisfies: \(1 \leq \mathrm{seg}(s,\mathcal{C}) \leq |s| \leq T\).

3.2 Two-Part Description Length of the Successful Batch↩︎

For a sampled batch \(\mathcal{B} = \{(d_i,\tau_i)\}_{i=1}^{n}\), let \(\mathcal{B}^+ := \{\tau_i : R(\tau_i)=1, \tau_i\in\mathcal{B}\}\) denote the subset of successful trajectories, and let \(s_i = \varphi(\tau_i)\) be the skill sequence of \(\tau_i \in \mathcal{B}^+\). When \(\mathcal{B}^+ \neq \emptyset\), we evaluate a candidate skill dictionary \(\mathcal{C}\) using a standard two-part code following the MDL principle [17], [18]: one part encodes the shared dictionary itself, and the other encodes the successful skill sequences using phrases from that dictionary. We thus define the dictionary cost as \[\label{eq:dict-cost} L_{\mathrm{skill\_dict}}(\mathcal{C}) = \sum_{j=1}^{M}\bigl(|p_j|\log_2 K_\Sigma + \log_2 L\bigr)\tag{2}\] which measures the cost of storing the \(M\) phrases in \(\mathcal{C}\): \(|p_j|\log_2 K_\Sigma\) accounts for the cost of specifying the atomic skills in \(p_j\), and \(\log_2 L\) accounts for its length. The corresponding batch-level description length of \(\mathcal{B}^+\) under \(\mathcal{C}\) is \[\label{eq:bdl} \begin{align} \mathcal{L}_{\mathrm{BDL}}(\mathcal{B}^+, \mathcal{C}) &= \frac{L_{\mathrm{skill\_dict}}(\mathcal{C})}{\lvert \mathcal{B}^+ \rvert} \\ &+ \frac{1}{\lvert \mathcal{B}^+ \rvert} \sum_{\tau_i \in \mathcal{B}^+} \operatorname{seg}\!\left(\varphi(\tau_i), \mathcal{C}\right) \log_2 \lvert \mathcal{C} \rvert \end{align}\tag{3}\] The first term is the shared cost of the dictionary, amortized across successful trajectories. The second term is the average cost of reconstructing their skill sequences using phrases from \(\mathcal{C}\). From a standard coding perspective, the dynamic programming segmentation partitions a sequence into \(\operatorname{seg}(\varphi(\tau_i), \mathcal{C})\) distinct phrases. Assuming a uniform code over the dictionary entries, specifying each phrase requires \(\log_2 |\mathcal{C}|\) bits to index. Therefore, their product yields the total bits required to encode the data given the dictionary. We select the batch dictionary by minimizing this objective: \[\label{eq:opt-dict} \hat{\mathcal{C}}(\mathcal{B}^+) = \arg\min_{\mathcal{C}\in\mathcal{A}} \mathcal{L}_{\mathrm{BDL}}(\mathcal{B}^+,\mathcal{C})\tag{4}\] Equation 3 is the objective we minimize over \(\mathcal{C}\) to extract the shared dictionary. The next subsection derives the corresponding per-trajectory signal that the policy should optimize, by examining the structure of joint MDL minimization over \((\mathcal{C},\pi_\theta)\).

3.3 EM-style Optimization of the MDL Objective: The segmentation cost↩︎

Jointly minimizing the description length over both the shared dictionary \(\mathcal{C}\) and the policy \(\pi_\theta\) naturally yields an EM-style alternating procedure: the current policy generates a batch of successful trajectories \(\mathcal{B}^+\), from which we infer a compressive dictionary \(\mathcal{C}\) (E-step); holding this dictionary fixed, we then update \(\pi_\theta\) to favor successful trajectories that are cheaper to encode under \(\mathcal{C}\) (M-step).

3.3.0.1 E-step (dictionary extraction).

With \(\pi_\theta\) fixed, we re-estimate the shared dictionary from the current successful batch \(\mathcal{B}^+\) by solving Eq. 4 . The dictionary-storage term \(L_{\mathrm{skill\_dict}}(\mathcal{C})/|\mathcal{B}^+|\) is constructive here: it controls which shared structure we extract by trading dictionary size against per-trajectory segmentation cost.

3.3.0.2 M-step (policy update).

With \(\mathcal{C}\) fixed at \(\mathcal{\mathcal{C}}(\mathcal{B}^+)\), we move \(\pi_\theta\) toward successful trajectories whose skill sequences are cheap to encode under \(\mathcal{C}\). Once \(\mathcal{C}\) is fixed, the only part of the joint description length that varies with the individual trajectory is the conditional segmentation cost, and this is the quantity we attach to the per-trajectory RL signal.

Concretely, we use the segmentation cost of a successful trajectory \(\tau_i\) with skill sequence \(s_i = \varphi(\tau_i)\) under dictionary \(\mathcal{C}\) as. \[\label{eq:idio} \mathrm{SegCost}(s_i \mid \mathcal{C}) := \frac{\mathrm{seg}(s_i,\mathcal{C})}{T}\tag{5}\] A trajectory that decomposes into a few long reusable phrases has \(\mathrm{seg}(s,\mathcal{C}) \ll T\) and a lower segmentation cost; a trajectory composed of unrelated singleton skills has \(\mathrm{seg}(s,\mathcal{C}) = |s| \approx T\) and the maximum segmentation cost of \(1\).

The augmented trajectory-level RL objective is therefore to maximize \[\label{eq:rl-mdl} \begin{align} &\mathop{\mathbb{E}}\limits_{\mathcal{B}\sim(\mathcal{D},\pi_\theta)^n} \Biggl[ \frac{1}{n}\sum_{i=1}^{n} \Bigl( R(\tau_i) \\ &\quad - \lambda\cdot \mathbb{1}\{R(\tau_i)=1\}\, \operatorname{SegCost}\bigl( s_i \mid \mathcal{C}(\mathcal{B}^+) \bigr) \Bigr) \Biggr] \end{align}\tag{6}\] with \(\lambda\) as the efficiency coefficient. The indicator restricts the penalty to successful trajectories, so the signal never discourages task completion. The full alternating procedure, i.e., E-step over \(\mathcal{C}(\mathcal{B}^+)\), then M-step GRPO update over \(\pi_\theta\), iteratively reduces the joint description length of the successful behavior the policy produces.

3.4 Pure Round Length as Fixed-Code MDL↩︎

Pure round-length penalties compress trajectories uniformly by discouraging all steps equally, regardless of whether those steps participate in reusable behavioral structure. In our framework, this corresponds to a degenerate fixed-code setting where the dictionary contains only singleton skills and is not allowed to merge into reusable phrases.

The proposition has a direct empirical consequence. Uniform brevity cannot distinguish sequences with the same raw length but different segmentation costs and fail to favor reusable compositional structure across different successful trajectories.

3.5 Generalization Bound on the MDL Objective↩︎

We now theoretically analyze the MDL objective utilized in the EM-style optimization of §3.3 by deriving a PAC-Bayes bound on the expected description length of successful skill sequences. Importantly, this theorem bounds the expected description length under a fixed policy distribution, rather than characterizing policy generalization after iterative RL updates. The argument guarantees that if an extracted dictionary tightly compresses an observed successful batch, its expected description length on future successful trajectories from the same distribution is formally bounded. While this does not alone prove that the per-trajectory penalty acts as a generalization-improving regularizer, it formally justifies using the empirical MDL objective as a reliable measure for evaluating the structural reusability of successful behaviors.

For a given \(\pi_\theta\), let \(Q_\theta^+\) denote the distribution over successful skill sequences induced by \(d \sim \mathcal{D}\), \(\tau \sim \pi_\theta(\cdot \mid d)\), \(s = \varphi(\tau)\), and \(R(\tau) = 1\).

This assumption states that successful reasoning trajectories are generated by composing a bounded number of reusable skill patterns from a shared vocabulary, a condition naturally satisfied in structured environments such as ALFWorld, where diverse household tasks decompose into common subroutines (e.g., Explore \(\to\) Take \(\to\) Transform \(\to\) Deliver).

3.6 SkillRL and ERL as Implicit MDL Minimizers↩︎

Recent skill-reuse frameworks implicitly compress different parts of the behavioral pipeline but do not explicitly optimize the shared successful-trajectory objective in Eq. 6 . SkillRL [10] constructs a hierarchical skill library via teacher-model distillation, effectively compressing the dictionary term \(L_{\mathrm{skill\_dict}}\) but not penalizing per-trajectory segmentation complexity during RL updates. ERL [11] embeds an experience–reflection–consolidation loop that compresses instance-level correction traces into model weights but does not enforce shared compositional patterns across trajectories. In contrast, ReuseRL explicitly minimizes the full batch-level MDL objective by the EM process, simultaneously searching for a compact shared codebook and incentivizing reusable skill compositions among successful trajectories. Formal objective comparisons for these two methods are provided in §10.

3.7 Algorithm and Implementation↩︎

We implement ReuseRL as a reward-shaping module within the GRPO training loop. Algorithm 2 in the appendix summarizes the procedure.

3.7.0.1 Atomic skill extraction.

Given a successful trajectory \(\tau\), we extract its skill sequence \(\varphi(\tau) \in \Sigma^*\) via a deterministic rule-based mapping over the raw action verbs. We intentionally choose a small, task-generic alphabet to capture reusable structure without collapsing into near-raw actions or losing critical behavioral distinctions. Mapping rules are summarized in §4.2.

3.7.0.2 BPE dictionary extraction with a global success buffer.

We approximate the optimal dictionary \(\mathcal{C}\) by a greedy Byte Pair Encoding (BPE) algorithm [32]. Starting from singleton phrases (one per atomic skill in \(\Sigma\)), we repeatedly propose an adjacent phrase pair \((p_a, p_b)\) for merging, where candidate pairs are ranked by frequency in the successful cluster \(\mathcal{T}\), which consists of the current successful batch \(\mathcal{B}^+\) and an optional global successful buffer \(\mathcal{G}\). The global buffer, collecting successful trajectories across batches in a FIFO structure, is to stabilize the E-step across small successful batches. A candidate merge is accepted only if adding the concatenated phrase \(p_a \circ p_b\) strictly decreases the batch objective: \[\begin{align} \Delta_{\mathrm{BDL}} &= \mathcal{L}_{\mathrm{BDL}}\!\left( \mathcal{T}_b, \mathcal{C}\cup\{p_a\circ p_b\} \right) \\ &\quad - \mathcal{L}_{\mathrm{BDL}}\!\left( \mathcal{T}_b,\mathcal{C} \right) < 0 \end{align}\] We cap phrase length at \(L = 4\) to avoid overfitting to specific trajectory-level details. This greedy procedure approximates the NP-hard optimal dictionary search [24] and terminates when no merge yields a negative MDL delta, which is further validated in §6.

4 Experimental Settings↩︎

4.1 Tasks↩︎

We evaluate ReuseRL on three text-based agentic benchmarks: ALFWorld [1] for household interaction tasks, TextWorld-Cooking [2] for recipe-following with irreversible processing errors, and Countdown-Stepwise [3] for arithmetic planning with rollback and reset actions. More details are in §12.

4.2 Atomic Skill Extraction↩︎

Based on each task, we manually define deterministic rule-based skill projection over raw actions. ALFWorld uses 5 navigation/manipulation skills, TextWorld-Cooking uses 10 recipe-execution skills, and Countdown-Stepwise uses 26 target-relative arithmetic skills. More details are in §13.

4.3 Training and Evaluation↩︎

All experiments are trained with GRPO for 300 steps. We use Qwen2.5-1.5B-Instruct [33] for ALFWorld and Countdown-Stepwise, and Qwen3-1.7B [34] in non-thinking mode for TextWorld-Cooking. For ALFWorld, we report SC@7 [35]: for each test scene, we sample \(7\) rollouts and determine success by majority vote. It has two test splits: IID and OOD. For TextWorld-Cooking and Countdown-Stepwise, we report Pass@1 averaged over three independent runs, reporting the mean and standard deviation across seeds. More implementation and evaluation details are in §12.

4.4 Compared Methods↩︎

We compare four configurations per environment: (1) Vanilla: the base model without any RL training; (2) Vanilla GRPO: standard GRPO without any compression signal; (3) pure-round-length: GRPO augmented with the penalty \(\cdot|s|/T\) on successful trajectories, which Proposition 1 shows is the fixed-code degenerate instance of ReuseRL; (4) ReuseRL-SegCost (Ours): GRPO augmented with the penalty \(seg(s, \mathcal{C})/T\), where the dictionary \(\mathcal{C}\) is extracted from the successful batch combined with the global buffer.

5 Main Results↩︎

5.0.0.1 Structural compression translates to improved reasoning generalization.

Crucially, the gains in Table 1 demonstrate that ReuseRL improves beyond vanilla GRPO and the uniform compression. The strongest evidence is its out-of-distribution and compositional transfer: ReuseRL achieves its largest absolute improvement on the ALFWorld OOD split and held-out data from TW-Cooking and Countdown-Stepwise.

5.0.0.2 Compression robustly beats GRPO in environments dominated by step-budget exhaustion.

On ALFWorld and Countdown-Stepwise, all compression methods outperform vanilla GRPO by large margins (\(+11.94\) / \(+8.56\%\) for pure-round-length on ALFWorld OOD / Countdown Pass@1, and another \(+1.49\) / \(+3.35\%\) for segmentation cost), because the intermediate states are highly reversible by actions. Invalid or suboptimal actions largely waste the step budget rather than triggering immediate fatal traps. This means any structurally consistent compression signal is informative.

5.0.0.3 Uniform length pressure backfires when redundant actions trigger irreversible failures.

On TextWorld-Cooking, pure-round-length drops significantly, \(10.94\) points even below vanilla GRPO. After the case study, failures concentrate on cook=False + cookbook-says-cook recipes, whose cook gate is off because the ingredient arrives already in cooked form (e.g.roasted red apple on the counter) even though the cookbook still mentions the cooking of the ingredients, so attempting to cook the ingredient a second time burns it. More analysis about it is detailed in §7.2.

5.0.0.4 A learned multi-step dictionary recovers task-conditional structure.

ReuseRL-SegCost improves over pure-round-length on all three benchmarks (\(+0.71\)/\(+1.49\)% ALFWorld IID/OOD, \(+17.70\)% TW-Cooking, \(+3.35\)% Countdown). The TW-Cooking gap is largest because pure-round-length minimizes raw step count and falls into the brittle cookbook-literal shortcut, whereas the segmentation cost rewards skill subsequences that recur across successful trajectories and so favors the recipe-faithful macro that generalizes. The strict empirical ordering ReuseRL-SegCost \(\succ\) pure-round-length \(\succ\) Vanilla GRPO holds on every benchmark except the middle term on TW-Cooking, where pure-round-length falls below GRPO. This inversion, predicted by Proposition 1, shows that effective compression must capture structure rather than raw length.

6 Ablations↩︎

6.1 Effectiveness of Greedy BPE Dictionary Extraction↩︎

The shared dictionary objective \(\mathcal{L}_{\mathrm{BDL}}\) (Eq. 3 ) is NP-hard to minimize exactly over the admissible class \(\mathcal{A}\), so the E-step in Algorithm 2 uses a greedy BPE merge schedule. On a synthetic corpus of dummy skill sequences, this schedule comes within \(0.14\%\) of the matched brute-force optimum, recovers \(99.02\%\) of its non-singleton phrases, and runs \(285\times\) and \(2231\times\) faster than the two brute-force variants. The greedy upper bound is thus tight enough that minimizing it inline effectively reduces \(\mathcal{L}_{\mathrm{BDL}}\) over \(\mathcal{A}\) at a cost low enough to run alongside every GRPO update. Full protocol and baselines are in §14.1.

6.2 Global Success Buffer↩︎

Table 1 reports an ablation without the global success buffer. The buffer is beneficial when successful trajectories within a single batch are too sparse or diverse for BPE to identify stable reusable phrases. Removing it lowers ALFWorld SC@7 from \(97.14\)/\(93.28\)% to \(93.57\)/\(89.55\)% on IID/OOD, and drops Countdown Pass@1 from \(80.37\)% to \(68.94\)%. However, the buffer can be harmful when dominated by easy trajectory patterns. On TextWorld-Cooking, removing the buffer raises TW-Cooking Pass@1 from \(81.73\)% to \(83.50\)%, entirely on the hard split (\(9.0\%\!\to\!18.5\%\) solved, while simple games saturate at \(99.8\%\) either way). A persistent buffer over-represents majority-class macros from simple games, pruning the interleaved cut-and-cook structures required for hard recipes, whereas a thinner per-batch corpus preserves this minority structure. More details are in §14.2.

7 Case Study↩︎

We now examine how environment structure shapes the behavior induced by different compression objectives. Table 2 reports trajectory-level statistics at training step 300 that reveal failure modes and behavioral trade-offs beyond success rate alone.

4.5pt

7.1 ALFWorld: Efficiency-Driven Gains over GRPO↩︎

ALFWorld’s only failure mode is timeout, so step budget is the binding constraint; GRPO leaks it to invalid loops and action repetition, and both ReuseRL variants cut average successful-episode length from \(15.3\) to \(\sim\!9\) steps. The residual SegCost-vs-round-length gap localizes to complex multi-object tasks (§15); several high-frequency phrases recovered by ReuseRL-segmentation cost coincide with skills distilled in SkillRL’s Skillbank [10], with the correspondence listed in Table 7, §15.

7.2 TextWorld-Cooking: The Burned-Food Failure of Pure Round Length↩︎

Pure-round-length collapses onto the Burned failure mode (\(74\%\) of its failures vs.\(21\%\) for GRPO, Table 2) with the shortest failed trajectories of any method (\(10.6\) steps), while ReuseRL-SegCost achieves comparable successful-episode efficiency with substantially fewer burn failures. The mechanism—cookbook-literal cook on already-cooked ingredients—is policy-side for failing to learn the skill structures over different successful trajectories and triggering the biases of emitting the cook actions. More details about the failing are in §14.2, and Table 4, §15.

7.3 Countdown-Stepwise: Solver-Template Formation and Operation Diversity↩︎

Compression accelerates straight-through (zero-Reset) solving and uniquely expands Mul/Div usage under ReuseRL-SegCost, the signature of a learned dictionary that captures multi-step solver templates (e.g., executing a large subtraction to approach the target followed immediately by a precise division to clear the remainder). Per-method closing-OP counts and the full failure-mode partition are in §14.2 and §15.

8 Conclusion↩︎

We presented ReuseRL, augmenting GRPO with a segmentation cost \(seg(s, \mathcal{C})/T\) derived from an EM-style MDL objective. By extracting a shared dictionary of reusable skills and penalizing idiosyncratic, one-off action sequences, ReuseRL regularizes against reasoning collapse such as wasting budgets and overfitting to certain curriculum in a task. This compression forces the agent to internalize transferable logic rather than memorize task-specific shortcuts, directly improving reasoning. Empirically, this generalization is evidenced by ReuseRL’s significant gains on the ALFWorld OOD split, its avoidance of deceptive traps in TextWorld-Cooking, and its systematic formation of multi-step solver templates in Countdown-Stepwise.

Limitations↩︎

ReuseRL has four main limitations. (i) The skill projection \(\varphi\) is a rule-based per-environment mapping over action verbs; transferring ReuseRL to a new domain requires a small amount of manual schema design (although the mapping itself is short and easily verifiable, and we consider this trade-off favorable to relying on an external LLM parser). (ii) The greedy BPE dictionary search is an approximation to the NP-hard optimal-dictionary problem [24]; it is sufficient for the alphabets considered here, but the approximation gap is expected to grow with \(|\Sigma|\) and may require alternative search heuristics in larger-vocabulary domains. (iii) The generalization argument relies on Assumption 1: successful trajectories must admit a shared reusable decomposition with bounded dictionary complexity and bounded per-trajectory segment count. The assumption is a mild structural condition for the agentic benchmarks studied here, but can fail in unstructured or purely-novel reasoning domains where successful trajectories share less reusable substructure, in which case the segmentation cost signal degenerates toward the round-length penalty. (iv) Our experiments are restricted to text-based agentic benchmarks and \(1.5\)–\(1.7\)B-parameter base models; extending ReuseRL to vision-language agents and to larger backbones is left to future work.

Use of LLMs↩︎

We have NOT used LLMs to originate research ideas, NOT used LLMs to write original content in the paper, NOT used LLMs to generate data or plots.

9 Proofs and Corollary↩︎

9.1 Proof of Proposition 1↩︎

9.2 Proof of Theorem 2↩︎

9.3 Corollary on the Universal Dictionary↩︎

Equation ?? makes the roles of \(B^\star\) and \(K^\star\) explicit: a smaller universal dictionary and fewer reusable segments per successful trajectory directly imply a smaller out-of-sample description length for future successful trajectories. Combined with the EM picture of Section 3.3—in which the E-step reduces \(\mathcal{L}_{\mathrm{BDL}}\) in \(\mathcal{C}\) and the M-step reduces the empirical segmentation cost at fixed \(\mathcal{C}\)—this corollary is what justifies the per-trajectory penalty in Eq. 6 as a generalization-improving regularizer.

10 Implicit MDL: SkillRL and ERL Objective Decompositions↩︎

10.0.0.1 SkillRL as implicit library compression.

SkillRL [10] constructs a hierarchical skill library \(\mathcal{S} = \mathcal{S}_g \cup \mathcal{S}_k\) (general and task-specific skills) via teacher-model distillation. Each skill \(s_j\in\mathcal{S}\) is a natural-language behavioral rule compressed from multiple trajectories by an external teacher model. This distillation can be viewed as constructing an implicit codebook \(\mathcal{C}_{\mathrm{skill}}\) where each entry encodes a reusable behavioral subroutine, and the skill-evolution and retrieval hyperparameters effectively manage which parts of this library are exposed to the base policy. However, SkillRL does not penalize the segmentation complexity of successful trajectories during RL updates: the policy may still combine retrieved skills in arbitrarily complex ways. At a high level, SkillRL optimizes \[\label{eq:skillrl} \begin{gather} J_{\mathrm{SkillRL}}(\theta,\mathcal{S}) = \mathbb{E}_{\mathcal{B}}\!\left[ \frac{1}{n}\sum_{i=1}^{n} R(\tau_i^{\mathcal{S}}) \right],\\ \mathcal{S} \leftarrow \texttt{Evolve}\!\left( \mathcal{S}, \pi_\theta, \mathcal{D}_{\mathrm{val}} \right). \end{gather}\tag{8}\] where \(\tau_i^{\mathcal{S}}\) denotes a trajectory generated with retrieved skills. Moreover, their evolving library \(\mathcal{S}\) does not compresses the dictionary term \(L_{\mathrm{skill\_dict}}\) since they only allow addition of skills, the objective contains no explicit success-conditioned term of the form \(\mathbb{1}\{R(\tau_i)=1\}\cdot\mathrm{SegCost}(\cdot)\) during policy optimization, and the top-\(K\) retrieval only controls memory exposure rather than shared segmentation cost across successful trajectories.

10.0.0.2 ERL as implicit instance-level internalization.

ERL [11] implements an experience–reflection–consolidation loop: for a failed or under-performed trajectory \(\tau^{(1)}\), the policy generates a structured reflection \(\Delta\) and a corrected trajectory \(\tau^{(2)}\), and an internalization loss \(\mathcal{L}_{\mathrm{distill}}(\theta) = -\mathbb{E}[\mathbb{1}(R(\tau^{(2)})>0)\log\pi_\theta(\tau^{(2)}\mid d)]\) trains the base policy to reproduce successful corrections without the reflection context. In MDL terms, ERL starts with a two-part code \(L(\Delta)+L(\tau^{(2)}\mid\Delta)\) and compresses it into a single-part code \(L(\tau^{(2)})\) by absorbing the codebook (reflections) into model weights—a genuine form of description-length minimization, but at the instance level: each reflection addresses a single episode rather than capturing structural patterns shared across trajectories. The effective ERL objective is \[\label{eq:erl} \begin{align} J_{\mathrm{ERL}}(\theta) &= \mathbb{E}_{\mathcal{B}}\!\Biggl[ \frac{1}{n}\sum_{i=1}^{n} \Bigl( R(\tau_i^{(1)}) \\ &\quad {}-\eta\, \mathbb{1}\!\left\{ \substack{ R(\tau_i^{(1)})=0, R(\tau_i^{(2)})=1 } \right\} \\ &\quad {}\cdot \mathrm{KL}\!\left( \pi_\theta(\cdot\mid d_i,\Delta_i) \,\middle\|\, \pi_\theta(\cdot\mid d_i) \right) \Bigr) \Biggr]. \end{align}\tag{9}\] where the indicator activates the reverse-KL term only when the first attempt fails and the reflected second attempt succeeds. ERL therefore compresses an instance-specific two-part code into model weights but does not search for a shared structural dictionary across the successful batch.

11 Algorithm↩︎

Algorithm 2 summarizes the full ReuseRL training loop.

12 More Training and Evaluation Details↩︎

12.0.0.1 Task Details

ALFWorld requires an agent to complete household tasks (e.g., “heat a potato and place it on the counter”) by issuing natural-language actions in a partially observable simulated environment; the maximum interaction horizon is \(T=50\) steps and a successful trajectory receives terminal reward \(+10\), which means \(R(\tau)\in\{0,10\}\) because following the verl-agent [9] framework we have a invalid action penalty set as 0.01 and this sometimes prevents the model from collapsing their outputs. This mechanism has applied to all environments used here. TextWorld-Cooking is the cooking game under the TextWorld framework: the agent must read the recipe, find all ingredients, process them (cut/slice/dice), cook them, prepare the meal, and eat it; ordering matters and some processing steps could directly lead to failures such as burning the food, an irreversible terminal failure. The current generated training and evaluation data both follow a \(4{:}1\) simple-hard division/splits based on the rooms, ingredients, is_cook, and is_cut settings; the hard setting is room=6, ingredients=2, is_cook=True, is_cut=True and the simple setting refers to room=1, ingredients=1, is_cook=True|False, is_cut=True|False. We use \(T=40\) and terminal reward \(+10\) on success. Countdown-Stepwise is a stepwise variant of the Countdown game from Reasoning-Gym in which each action is either a single arithmetic operation between two numbers from the current number pool (Add, Sub, Mul, or Div), Rollback to undo the previous operation, or Reset to restore the initial pool. We train and evaluate on \(3\)- to \(4\)-number scenarios with target values in \([10,999]\), \(T=30\), and terminal reward \(+10\) on success. All three environments verify intermediate steps so that successful trajectories are process-correct.

12.0.0.2 Training Details

Training is performed on Nvidia RTX Pro 6000 96 GB GPUs with tensor parallelism, using the verl-agent framework [9] on top of verl [37]. The efficiency coefficient is \(\lambda=10\) for both penalty-based variants as mentioned previously our binary reward setting is \(R(\tau)\in\{0,10\}\), following [9]. The evaluation inference engine is based on vLLM [38]. The skill-projection rules and BPE search are CPU-only and run inline with the GRPO update loop; the global FIFO success buffer is sized at \(256\) skill sequences.

12.0.0.3 Evaluation Details

The Qwen2.5-1.5B-Instruct is using temperature=0.4 for sampling while the Qwen3-1.7B is following the recommended sampling setting: the temperature=0.7 top_p=0.8, and top_k=20, respectively. The Alfworld’s two test splits: IID and OOD have 140 and 134 scenes, respectively. The Textworld-Cooking and Countdown-Stepwise have 1000 and 1024 generated test examples.

13 Atomic Skill Alphabets and Rule-Based Mappings↩︎

This appendix details the deterministic verb-matching rules that implement the skill projection \(\varphi\) for each environment. Table [tab:skill-mappings] lists the action prefix patterns and their atomic-skill targets. We additionally provide one worked example per environment to illustrate how a raw trajectory becomes an atomic-skill sequence.

5pt

13.1 ALFWorld (\(|\Sigma|=5\))↩︎

13.1.0.1 Worked example.

Goal. “put a clean ladle on countertop 1”

Trajectory.

go to drawer 1
open drawer 1;
take ladle 1 from drawer 1;
go to sinkbasin 1;
clean ladle 1 with sinkbasin 1;
go to countertop 1;
put ladle 1 on countertop 1.

Projection. \[\begin{align} \varphi(\tau)=(& \mathrm{\small Explore}, \mathrm{\small Explore}, \mathrm{\small Take},\\ &\mathrm{\small Transport}, \mathrm{\small Transform}, \mathrm{\small Transport},\\ &\mathrm{\small Deliver}). \end{align}\]

13.2 TextWorld-Cooking (\(|\Sigma|=10\))↩︎

13.2.0.1 Worked example.

Trajectory.

examine cookbook
open fridge;
take carrot from fridge
dice carrot;
cook carrot with stove;
prepare meal
eat meal.

Projection. \[\begin{align} \varphi(\tau)=(& \mathrm{\small Read\_Recipe}, \mathrm{\small Open}, \mathrm{\small Take},\\ &\mathrm{\small Cut}, \mathrm{\small Cook}, \mathrm{\small Prepare\_Meal},\\ &\mathrm{\small Eat\_Meal}). \end{align}\]

13.3 Countdown-Stepwise (\(|\Sigma|=26\))↩︎

Each step’s action is parsed into one of three forms: \(\mathrm{Op}(\langle\mathrm{op}\rangle,n_1,n_2)\), \(\mathrm{Rollback}\), or \(\mathrm{Reset}\). For an \(\mathrm{Op}\) action with operands \((n_1,n_2)\) and target \(T_{\mathrm{tgt}}\), each operand is assigned a target-relative role: \[\mathrm{role}(n)= \begin{cases} \mathrm{near\_target}, & \text{if } |n-T_{\mathrm{tgt}}| \leq 0.10|T_{\mathrm{tgt}}|,\\ \mathrm{small}, & \text{if } n<T_{\mathrm{tgt}}-0.10|T_{\mathrm{tgt}}|,\\ \mathrm{large}, & \text{otherwise.} \end{cases}\] The two role tags are sorted alphabetically before being joined, treating the operation as unordered. Thus, op(+, 1, 10) and op(+, 10, 1) induce the same unordered role pair. With four operators and six unordered role pairs from \(\{\mathrm{large},\mathrm{near\_target},\mathrm{small}\}\), this yields \(4\times 6=24\) operation skills, plus Rollback and Reset, for a total of \(26\).

13.3.0.1 Worked example.

Puzzle. \(\{80,2,28,1\}\) with target \(T_{\mathrm{tgt}}=54\). Here \(n>59.4\) is \(\mathrm{large}\), \(|n-54|\leq 5.4\) is \(\mathrm{near\_target}\), and all remaining values are \(\mathrm{small}\).

Trajectory with roles.

op(-, 80, 28): \(80\mapsto\mathrm{large}\), \(28\mapsto\mathrm{small}\);
op(+, 52, 2): \(52\mapsto\mathrm{near\_target}\), \(2\mapsto\mathrm{small}\);
op(*, 54, 1): \(54\mapsto\mathrm{near\_target}\), \(1\mapsto\mathrm{small}\).

Projection. \[\begin{align} \varphi(\tau)=(& \mathrm{\small OP\_Sub-large-small},\\ &\mathrm{\small OP\_Add-near\_target-small},\\ &\mathrm{\small OP\_Mul-near\_target-small}). \end{align}\]

14 Ablation Details↩︎

14.1 More Details about BPE Merging↩︎

14.1.0.1 Setup.

We quantify the approximation gap between greedy BPE-merging and exhaustive brute-force (BF) search over all candidate dictionaries. The benchmark is a synthetic corpus of around 200 random skill sequences with dummy atomic skills (\(|\Sigma|=5\), i.e.\(\{A, B, C, D, E\}\)), with sequence lengths sampled uniformly from 2 to 6 and each group consisting of 10 sequences. We compare against two admissible brute-force variants. BF-all-singletons requires every corpus singleton to be retained in the candidate dictionaries, matching BPE’s structural invariant. BF-original drops this constraint and attains the true \(\min L_{BDL}\) by pruning singletons whose every occurrence is covered by a longer phrase.

14.1.0.2 Approximation quality.

BPE attains a mean penalty of \(7.25\), within \(0.14\%\) of BF-all-singletons (\(7.24\)) and recovering \(99.02\%\) of its non-singleton phrases, showing that the greedy schedule is essentially exact within its own search space. BF-original reaches \(7.01\), a \(3.3\%\) reduction below BPE’s upper bound, but shares only \(66.34\%\) of non-singleton phrases with BPE and requires exhaustive search.

14.1.0.3 Runtime.

BPE takes \(0.053\) ms per group (\(10.9\) ms total), versus \(11.86\) ms (\(2430.6\) ms total) for BF-all-singletons and \(118.58\) ms (\(24308.5\) ms total) for BF-original, giving \(285\times\) and \(2231\times\) speedups respectively. The combination of a tight approximation gap and negligible runtime is what makes inline E-step dictionary extraction practical within the GRPO loop.

14.2 More Details about the Global Success Buffer Ablation↩︎

14.2.0.1 Countdown-Stepwise closing operations (Table 3).

Countdown-Stepwise has exactly two terminal-loss conditions: Timeout (the \(30\)-step budget is exhausted) and Stuck (the model issues Op or an unparsable action while the working pool has fewer than two numbers, which the env treats as unrecoverable). Within-episode Reset/Rollback counts and invalid-action counts are descriptors of rollout noise but not termination criteria. Table 3 reports the raw count of closing operations per method—the operation that puts the pool at \([\,\text{target}\,]\)—broken down by operator. Only the buffered segmentation cost lifts the rare \(*\) and \(/\) closures (e.g.\(\mathrm{OP}(*,1,T)\) to absorb a leftover \(1\)); removing the buffer collapses the Mul count from \(36\) to \(18\), essentially matching GRPO (\(20\)).

4.0pt

14.2.0.2 TextWorld-Cooking mechanism (Table 4).

We call a TW-Cooking recipe cook=False + cookbook-says-cook when its cook gate is off—the ingredient arrives in the observation already in cooked form, e.g.roasted red apple on the counter—but the cookbook page still mentions the cooking of the ingredients; attempting to cook the ingredient a second time burns it. There are \(260\) such games in the \(1000\)-game validation split. Table 4 reports, per method, (1) the share of decision steps whose chain-of-thought references a cooking verb (cook|roast|fry|grill|stove|oven), (2) the conditional rate at which such steps emit a cook action, and (3) the per-game emission rate of cook actions split by cookbook content. The four policies think about cooking at comparable rates (24–61%); only the cookbook-literal fixed-code policy commits to a cook action conditional on that thought (\(73\%\)), while both segmentation cost variants suppress the action to \(0.3\%\).

5pt

15 Extended Case-Study Material and Learned-Dictionary Examples↩︎

This appendix collects the per-method trajectory analyses supporting Section 7, together with representative high-frequency non-singleton phrases from the learned dictionary \(\widehat{\mathcal{C}}\) and their correspondence to skills distilled by SkillRL [10]. All trajectory-level numbers below are computed on the same single seed’s step-\(300\) eval JSON per method.

15.0.0.1 ALFWorld (Table 5).

Failed ALFWorld episodes all hit the \(50\)-step cap; behavioral signal therefore lives in the action-quality metrics on successful episodes. Vanilla GRPO leaks roughly one-quarter of its slots to “Nothing happens.” returns and repeats earlier actions on \(40\%\) of slots; both ReuseRL variants and pure-round-length reduce these pathologies to single digits.

3.0pt

15.0.0.2 ALFWorld failure modes on the OOD split (Table [tab:alf-failure-modes]).

Every failed ALFWorld episode hits the \(50\)-step cap; we label timeouts by what was still missing. never_picked_target means no effective take of the goal object; two_partial_deliver means only one of two instances was placed on pick_two_obj_and_place; picked_no_transform means the agent took the goal object but never executed an effective clean/heat/cool (checked only after a successful take). On the OOD split (\(134\) logical games, \(938\) episodes), ReuseRL-SegCost improves SC@7 by \(1.49\) pp over pure-round-length (\(93.28\) vs.\(91.79\)) with \(21\) fewer failed rollouts (\(50\) vs.\(71\)). The gap is driven almost entirely by never_picked_target on held-out multi-phase tasks—especially pick_clean_then_place_in_recep (\(n{=}217\)), where Pure-Length accumulates \(19\) search failures vs.\(6\) for segmentation cost—not by two_partial_deliver (three failures each on Two-Obj) or lamp-ordering errors (both methods reach \(100\%\) on Look+Light). Overall OOD never_picked_target falls from \(64\) to \(44\), matching the analysis that uniform step counting over-penalizes exploratory prefixes that the BPE dictionary treats as reusable structure.

3.0pt

15.0.0.3 TextWorld-Cooking (Table [tab:case-tw-detail]).

Failed TW-Cooking episodes fall into three terminal conditions: Burned (the terminal observation contains burned), Wrong processing/order (a non-burn rule violation such as trying to slice an ingredient that should be chopped), and Timeout (the \(40\)-step budget is exhausted without either lost marker). Pure-Length fails fast—mean failed-episode length \(10.6\) steps—and almost always by burning; both segmentation cost variants fail near the step ceiling like GRPO.

3.0pt

15.0.0.4 Countdown-Stepwise (Table [tab:case-cd-detail]).

An episode in Countdown-Stepwise terminates under exactly two negative conditions: (i) Timeout, where the agent exhausts the maximum allocation of 30 steps without reaching the target value, and (ii) Stuck, a premature failure where the agent attempts to execute an arithmetic operation or emits an unparsable command when fewer than two numbers remain available in the working pool, rendering further evaluation mathematically impossible. Both compression methods, pure-round-length and ReuseRL-SegCost drive the failures toward Timeout (it has stopped getting stuck), while the no-buffer variant exhibits the opposite shift—a side-effect of having deleted Reset from its repertoire (zero RESETs in \(99.9\%\) of successes), leaving it unable to recover from early suboptimal operations once the numbers are collapsed.

3.0pt

15.0.0.5 Learned dictionary phrases (Table 6) and SkillRL correspondence (Table 7).

The phrases recovered by ReuseRL-SegCost reflect environment-specific reusable structure: navigation-and-place skeletons in ALFWorld, recipe-faithful processing chains in TextWorld-Cooking, and multi-step solver templates in Countdown-Stepwise. On ALFWorld the learned non-singleton phrases align closely with skills distilled in SkillRL’s Skillbank [10].

6pt

References↩︎

---

1. We will release all code and data under an open-source license upon publication.↩︎