PaperlayerView exact revision on arXiv

Source-linked AI summary

Spark: Strategic Policy-Aware Exploration via Dynamic Branching for Long-Horizon Agentic Learning

Jinyang Wu, Shuo Yang, Changpeng Yang, Yuhao Shen, Shuai Zhang, Zhengqi Wen, Jianhua Tao

arXiv:2601.20209v2cs.LGcs.CL

TL;DR

Long-horizon agentic reinforcement learning is constrained by scarce high-quality trajectories and limited resources. SPARK uses the agent’s intrinsic decision signals to branch exploration at critical intermediate states, and reports stronger success, sample efficiency, and generalization to unseen scenarios.

  • Problem

    Agentic reinforcement learning lacks high-quality trajectories under resource constraints, making effective learning difficult in tasks with vast state spaces and sparse successful trajectories.

    Source: §1 · p. 1

  • Method

    SPARK uses agents’ intrinsic decision signals to identify critical intermediate states and dynamically branch exploration there.

    Source: §1 · p. 2

  • Results

    Across challenging tasks, SPARK reports superior success rates, sample efficiency, and unseen-scenario generalization; on ALFWorld L2, SPARK-1.5B scores 80.5% vs. GRPO’s 29.7%.

    Source: §1 · p. 2, §3.2 · p. 5, §5 · p. 9

  • Takeaways & Limitations

    The findings highlight strategic exploration’s value in advancing capable and efficient agentic systems.

    Source: §5 · p. 9

    Intrinsic decision signals may miss exploration opportunities in extremely low-capability base models with limited self-awareness.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Reinforcement learning has empowered large language models to act as intelligent agents, yet training them for long-horizon tasks remains challenging due to the scarcity of high-quality trajectories, especially under limited resources. Existing methods typically scale up rollout sizes and indiscriminately allocate computational resources among intermediate steps. Such attempts inherently waste substantial computation budget on trivial steps while failing to guarantee sample quality. To address this, we propose \textbf{Spark} (\textbf{S}trategic \textbf{P}olicy-\textbf{A}ware explo\textbf{R}ation via \textbf{K}ey-state dynamic branching), a novel framework that selectively branches at critical decision states for resource-efficient exploration. Our key insight is to activate adaptive branching exploration at critical decision points to probe promising trajectories, thereby achieving precise resource allocation that prioritizes sampling quality over blind coverage. This design leverages the agent's intrinsic decision-making signals to reduce dependence on human priors, enabling the agent to autonomously expand exploration and achieve stronger generalization. Experiments across diverse tasks (e.g., embodied planning), demonstrate that \textsc{Spark} achieves superior success rates with significantly fewer training samples, exhibiting robust generalization even in unseen scenarios. Our code and checkpoints are available at https://github.com/jinyangwu/SPARK.

1 Introduction

SPARK addresses the scarcity of high-quality trajectories in long-horizon agentic RL by branching selectively at critical states using the agent’s own decision signals. The introduction reports higher benchmark performance, sample efficiency, and generalization to unseen scenarios.

1 Introduction

  • High-quality trajectories are scarce in resource-constrained agentic RL because vast state spaces make success sparse and a single misstep can derail a long task.Existing approaches distribute computation uniformly, wasting resources on routine steps while undersampling pivotal decisions, which can produce inefficient exploration and unstable training.Source: §1 · pp. 1–2, Figure 1 · p. 1
  • +73.5% average improvement is reported for SPARK across ALFWorld (L0-L2), ScienceWorld (L0-L2), and WebShop, alongside higher sample efficiency and generalization to unseen scenarios.The figure caption says SPARK outperforms all baselines across these tasks; the prose also reports superior success rates and sample efficiency.Source: Figure 2 · p. 2, §1 · p. 2
  • SPARK autonomously identifies critical intermediate states and branches when intrinsic signals indicate high epistemic uncertainty or semantic ambiguity, proceeding linearly through routine decisions.This policy-aware exploration topology reduces reliance on human priors and allocates resources toward sampling quality rather than exhaustive coverage.Source: §1 · p. 2
  • Dynamic branching at critical states is designed to produce more informative training trajectories and superior sample quality under constrained budgets than blind exploration.The framework targets exploration where additional branches may yield the greatest potential benefit.Source: §1 · p. 2

2 Methodology

SPARK frames long-horizon agentic learning as a POMDP and replaces uniform exploration with budget-constrained branching at uncertain, pivotal decisions. Its analysis explains how branching improves coverage of desirable actions at pivotal steps while reducing redundant computation.

2.1 Problem Formulation

  • Tasks are modeled as POMDPs where interaction history proxies belief, each step comprises observation, reasoning, and action, and episodes end at success, failure, or horizon K under sparse binary terminal rewards.Source: §2.1 · pp. 2–3

2.2 Dynamic Branching Exploration

  • SPARK seeds M independent roots (typically 3–5), branches at <explore>-marked uncertainty, and adjusts branching under global leaf budget N.This targets pivotal decisions rather than spending rollout budget uniformly across routine and critical steps.Source: §2.2 · pp. 3–4
  • Completed leaf trajectories are grouped by task, assigned binary terminal rewards propagated to their steps, and used for relative-credit clipped policy updates compatible with GRPO-style pipelines.Source: §2.2 · p. 4

2.3 Theoretical Perspective on SPARK

  • At pivotal decisions, B≥2 conditional branches strictly raise the chance of selecting a desirable action over single linear sampling, compounding trajectory discovery across pivotal steps.SPARK also avoids repeatedly rolling out suffixes from suboptimal pivotal choices, reducing redundant computation and overall token usage.Source: §2.3 · p. 5

3 Experiments

Experiments evaluate SPARK across embodied decision making, scientific reasoning, and web navigation, examining performance, efficiency, generalization, and ablations of dynamic branching and exploration quality.

3.1 Experimental Settings

  • The benchmarks cover ALFWorld household tasks, ScienceWorld tasks with horizons up to 30+ steps, and WebShop’s 1.1M products.Success Rate measures task completion; WebShop also reports Average Score for partial success.Source: §3.1 · p. 5

3.2 Main Results

  • SPARK outperforms prompting, SFT, and RL baselines across 1.5B and 7B backbones, with SPARK-1.5B reaching 49.2% on ScienceWorld L2 versus GPT-5’s 33.6% and Gemini-2.5-Pro’s 30.5%.The reported results span ALFWorld, ScienceWorld, and WebShop.Source: §3.2 · p. 5, Table 1 · p. 6

3.3 Exploration Efficiency Analysis

  • At 20% ALFWorld training data, SPARK reaches 84.4% success versus GRPO’s 76.6% at 100%, while token consumption is 6.9%, 47.0%, and 11.2% of chain-like methods on ALFWorld, ScienceWorld, and WebShop.Sharing common trajectory prefixes reduces redundant token generation, while allocating exploration to critical decision points improves sample quality.Source: Table 2 · p. 6, §3.3 · p. 6, Figure 4 · p. 7

3.4 Cross-Domain Generalization

  • SPARK limits ID-to-OOD performance drops to 16.9% on ALFWorld and 29.2% on ScienceWorld, achieving OOD success rates of 80.5% and 49.2%, versus GRPO’s 29.7% and 10.9%.GRPO’s corresponding performance drops are 61.2% on ALFWorld and 48.3% on ScienceWorld.Source: Table 3 · p. 7, §3.4 · p. 7

3.5 Ablation Study and Analysis

  • Selective branching outperforms fixed-probability branching, while B=2 balances local exploration depth with global budget preservation.On ScienceWorld, fixed-probability branching degrades performance from 69.5% to 45.3%; increasing B from 2 to 4 consistently lowers performance as it exhausts the leaf budget at single states.Source: Table 4 · p. 7, §3.5 · pp. 7–8, Table 5 · p. 7
  • With fixed total budget N=8, performance peaks at M=4 (80.7%), compared with 67.6% at M=2 and 72.1% at M=6.Too few roots restrict initial diversity, while excessive roots consume budget needed for later branching.Source: Figure 5 · p. 7, §3.5 · p. 7
  • In an ALFWorld egg-retrieval task, SPARK explores alternatives after signaling uncertainty at Step 6, finds the egg at Step 7, and completes by Step 10, unlike GRPO’s repeated loop.GRPO repeatedly checks the same three locations from Steps 6–30.Source: Figure 6 · p. 8, §3.5 · pp. 8–9
  • On 1.5B L2, SPARK’s repetitive-action ratio is 15.4% versus GRPO’s 27.1%, and its exploration frequency adjusts as the policy matures and task complexity varies.On ALFWorld, the exploration ratio drops to 0.29 at Step 150; on WebShop, it converges to approximately 0.17.Source: Table 6 · p. 8, §3.5 · p. 8, Table 7 · p. 8

4 Related Work

Related work addresses long-horizon agentic RL through dense process supervision or larger exploration budgets, while strategic exploration methods often branch uniformly. SPARK instead uses intrinsic decision signals to allocate branching selectively.

Agentic Reinforcement Learning

Strategic Exploration

  • Inference-time search and tree-structured RL explore diverse reasoning paths, but typically branch uniformly, wasting resources on trivial steps and under-exploring critical junctures (Zhang et al., 2025c; Wu et al., 2024; Yao et al., 2023; Hao et al., 2023; Hou et al., 2025; Wu et al., 2025; Ji et al., 2025).The cited inference-time search methods include ToT and RAP.Source: §4 · p. 9
  • SPARK uses intrinsic decision-making signals to branch selectively at high-uncertainty states, prioritizing trajectory quality over exhaustive coverage under budget constraints.This enables autonomous exploration-budget allocation with less reliance on external supervision and improves sample quality.Source: §4 · p. 9

5 Conclusion

SPARK is an RL framework for long-horizon agentic learning that uses dynamic branching to selectively explore critical decision points. Empirical results show superior success rates, better exploration efficiency, and robust generalization.

5 Conclusion

  • SPARK is a novel RL framework for long-horizon agentic learning.Source: §5 · p. 9
  • SPARK selectively expands exploration at critical decision points through strategic dynamic branching.This enables precise resource allocation.Source: §5 · p. 9
  • SPARK achieves superior success rates, better exploration efficiency, and robust generalization.The work highlights strategic exploration as valuable for advancing capable and efficient agentic systems.Source: §5 · p. 9

Limitations … A.2 Exploration Efficiency under Budget Constraints

The appendix motivates SPARK’s budget-efficient branching with informal analysis: concentrating exploration on sparse critical states can improve exploration under equal rollout budgets. The paper also notes that intrinsic decision signals may be less effective for very low-capability models.

Limitations

  • Intrinsic decision signals may miss exploration opportunities in extremely low-capability base models with limited self-awareness.Future work will explore learning-based calibration that combines internal signals with external feedback to improve state awareness and robustness.Source: Limitations · p. 9

Appendix of SPARK

  • The SPARK appendix provides additional theoretical analysis, experimental details, results, and analysis.Source: Appendix of SPARK · p. 12

A Theoretical Analysis

  • The theoretical analysis is heuristic rather than a rigorous proof, offering conceptual insight into exploration efficiency under constrained computational budgets.It is intended to motivate the method design and interpret empirical findings.Source: A Theoretical Analysis · p. 12

A.1 Problem Setup and Notations

  • In critic-free GRPO, reasoning traces implicitly estimate uncertainty, marking high uncertainty with <explore>; states with U(s)>τ are critical and those with U(s)≤τ are routine.Critical states are typically sparse in long-horizon tasks: Kc ≪ K.Source: §A.1 · p. 12

A.2 Exploration Efficiency under Budget Constraints

  • With equal rollout budget N, SPARK’s advantage scales with K/Kc when f is concave and N M·Kc ≫ 1.The analysis compares N independent chains with a tree using M roots and selective branching at critical states.Source: §A.2 · p. 13
  • Independent sampling spreads effort across N × K state-action pairs, while SPARK shares routine prefixes and concentrates budget B ≈ N M·Kc at critical states.The analysis argues that independent sampling gives only O(1) exploration depth per critical state.Source: §A.2 · p. 13

A.3 Sample Complexity Advantage · A.4 Summary · B Additional Experimental Details

The analysis argues that branching at critical states can reduce sample requirements, and reports that SPARK matches RLVMR’s peak performance with 40% of the training data. It frames exploration and sample-complexity advantages as heuristic explanations for SPARK’s empirical results.

A.3 Sample Complexity Advantage

  • The heuristic focuses on resolving action preferences at a small number of critical decision points rather than uniformly improving behavior at every step.T(ϵ) denotes the number of comparable action samples needed to identify a near-optimal action at a critical state within error ϵ.Source: §A.3 · p. 13
  • Independent sampling provides O(N) action samples per critical state, while SPARK branches alternatives under shared prefixes to concentrate samples and resolve uncertainty faster.Although shared prefixes correlate samples, paired branch comparisons increase information density per generated token by avoiding redundant resampling of routine interaction histories.Source: §A.3 · p. 13
  • The analysis estimates that SPARK needs an O(M · ρ) fraction of uniform methods’ trajectories for the same decision accuracy, where ρ = Kc/K.This is a heuristic estimate, not a rigorous bound.Source: §A.3 · p. 13, §A.4 · p. 14
  • SPARK matches RLVMR’s peak performance using only 40% of the training data, with this fraction comparable in order of magnitude to the estimated critical-state ratio ρ ≈ 0.4.The passage notes that this agreement holds up to constant factors.Source: §A.3 · p. 13

A.4 Summary

  • Tree-structured branching concentrates budget at critical states, suggesting an Ω(K/Kc) exploration-efficiency advantage over independent sampling when Kc ≪ K.Source: §A.4 · p. 13
  • The summary presents the M · ρ sample-complexity estimate as conditional on favorable conditions for matching uniform methods’ performance.Source: §A.4 · p. 14
  • The analyses offer conceptual justification for SPARK’s reported performance and sample efficiency, but are not rigorous proofs.Source: §A.4 · p. 14

B.1 Datasets · B.2 Baselines · B.3 Evaluation Details

The appendix specifies three long-horizon evaluation domains and their generalization levels, the model, agent, and RL baselines, and the metrics and protocol used for comparison.

B.1 Datasets

  • Benchmarks span L0 seen categories and instances, L1 seen categories with unseen instances, and L2 unseen categories and instances across three long-horizon agentic domains.The paper identifies ALFWorld, ScienceWorld, and WebShop as the evaluation domains.Source: §B.1 · p. 14
  • ALFWorld evaluation uses the Unseen split (L2) to test generalization to novel domestic environments.Tasks require high-level goal decomposition and low-level action execution in a text-based household environment.Source: §B.1 · p. 14
  • ScienceWorld covers 30 scientific tasks across 10 virtual environments, with horizons often exceeding 30+ steps and strict logic requirements.Tasks include conducting experiments and measuring substances.Source: §B.1 · p. 14
  • WebShop contains over 1.1 million products and evaluates 500 test queries using task completion Score and success rate.Agents search and click to purchase items matching user requirements in a large-scale, semi-structured space.Source: §B.1 · p. 14

B.2 Baselines

B.3 Evaluation Details

  • Success Rate (SR.) is primary; WebShop additionally reports partial-credit task completion Score, with evaluation batch size 128 and random seed 0.The seed and batch size are fixed across evaluation experiments.Source: §B.3 · pp. 15–16

B.4 Implementation Details · C Supplementary Results

SPARK’s cold-start SFT dataset combines retro-annotated and organically generated successful trajectories to teach exploration formatting, while supplementary results indicate robustness to tag variation and teacher choice. RL then optimizes strategy through environment interaction under fixed rollout and branching settings.

B.4 Implementation Details

  • The SFT dataset contains 300 successful trajectories, with 90% retro-annotated and 10% generated through real interactions.The dataset initializes the model’s ability to generate intrinsic exploration signals.Source: §B.4 · p. 16
  • For the 90% retro-annotated portion, Kimi-K2 adds reasoning traces and selectively inserts <explore> tags into observation-action sequences from RLVMR baseline datasets.The source sequences contain no intermediate reasoning steps; tags are inserted at steps of epistemic uncertainty.Source: §B.4 · p. 16
  • The 10% real-interaction portion consists of new successful teacher-model trajectories, recording spontaneous reasoning with <explore> and <think> tags.Source: §B.4 · p. 16
  • <explore> tags are concentrated early in trajectories and decline as tasks progress, while replacing them with <exploring> causes no meaningful performance degradation.This indicates tag placement follows temporal exploration needs rather than random placement.Source: §B.4 · p. 16, Table 9 · p. 16
  • Substituting Gemini-2.5-Flash or Qwen2.5-32B for Kimi-K2 yields only marginal downstream performance differences, indicating strategy optimization occurs during RL interaction.The comparison uses a 1.5B backbone.Source: §B.4 · p. 17, Table 10 · p. 17
  • RL uses capped episodes and responses, rule-based success rewards, invalid-action penalties, and fixed group-based sampling and branching parameters.Responses are limited to 512 tokens and episodes to 30 steps; success earns 10, failure 0, and invalid actions incur -0.1. Group size is 8, batch size 16, rollout temperature 0.4, KL coefficient 0.01, and history length at most 5. SPARK uses 4 initial roots and branching factor 2; experiments use four NVIDIA A100-80GB GPUs.Source: §B.4 · p. 17

C.1 Sample Efficiency · C.2 Inference Scalability · C.3 Multimodal Extension

Across sample-efficiency, inference-scalability, and multimodal evaluations, SPARK reports stronger results with limited training data, additional inference-time budget, and visual tasks. The results emphasize selective exploration and applicability beyond text-only settings.

C.1 Sample Efficiency

  • With 20% of the training data, SPARK reaches 84.4% success versus GRPO’s 76.6% using the full dataset.The comparison is on ALFWorld L0 with Qwen2.5-1.5B.Source: §C.1 · p. 17, Table 11 · p. 17
  • SPARK matches RLVMR’s peak performance using only 40% of total samples.The passage attributes this result to extracting higher information density from limited environment interactions.Source: §C.1 · p. 17

C.2 Inference Scalability

  • For inference scalability, SPARK is evaluated with 32 candidate trajectories per task and the Pass@16 success-rate metric.The passage defines Pass@k using the total sampled trajectories, the number of successful trajectories, and the evaluation threshold.Source: §C.2 · p. 17
  • In ScienceWorld, SPARK reaches 94.9% success at Pass@16, surpassing the strongest baseline by 30.1 points.The evaluation reports Pass@16 rates on ALFWorld, ScienceWorld, and WebShop.Source: §C.2 · p. 17, Table 13 · p. 18

C.3 Multimodal Extension

  • The multimodal evaluation uses Qwen2.5-VL-3B-Instruct on Sokoban and EZPoints, supporting SPARK’s reported modality-agnostic applicability.Sokoban requires spatial reasoning and long-term planning to push boxes onto targets; EZPoints requires perceiving cards and forming arithmetic steps to reach 12.Source: §C.3 · pp. 17–18
  • SPARK averages 88.3% success across Sokoban and EZPoints, gaining 11.3 points over GRPO’s 77.0%.It also scores 88.3% versus GPT-5’s 71.9% and ReAct’s 7.4%, gains of 16.4 and 80.9 points, respectively.Source: §C.3 · p. 18, Table 14 · p. 18

C.4 Sensitivity Analysis on Total Budget … E.3 Discussion on Reducing Dependence on Human Priors

SPARK’s supplementary analyses report diminishing returns beyond a total budget of 8, test-time gains from <explore>-conditioned branching, and a statistically significant advantage over GRPO. The discussion contrasts its intrinsic, selective exploration with external or tree-based approaches and argues that it reduces reliance on human priors while supporting generalization.

C.4 Sensitivity Analysis on Total Budget

  • Increasing total budget N from 4 to 8 improves L0 by 7.8% and L1 by 12.5%, while N = 16 yields diminishing returns.The reported pattern makes N = 8 the balance between exploration breadth and efficiency, without requiring excessive budget allocation.Source: §C.4 · pp. 18–19

C.5 Test-Time Branching

  • Spark-inference yields consistent gains across all benchmarks when branching on <explore> and selecting continuations by majority voting.The <explore> signal, designed for training-time rollout topology, also indicates decision uncertainty at inference; Table 16 presents the test-time branching results.Source: Table 16 · p. 19, §C.5 · p. 19

C.6 Statistical Analysis

  • A p-value of 9.7e-4 across benchmarks and 1.5B and 7B scales leads to rejecting no difference between SPARK and GRPO at α = 0.05.The analysis uses a Wilcoxon signed-rank test and reports evidence of a significant SPARK advantage over GRPO.Source: §C.6 · p. 19

D Case Study

  • Figures 10–13 provide illustrative examples from the ALFWorld and WebShop benchmarks.Source: D Case Study · p. 19

E.1 Discussion on Tree-Based Baselines

  • Conventional tree exploration faces prohibitive branching costs over 20–30+ interaction horizons, so SPARK selectively branches at critical states and comparisons focus on chain-like RL methods such as GRPO.The discussion notes that adapting tree methods to long-horizon agentic domains remains future work; existing tree-based approaches have mainly targeted math tasks.Source: §E.1 · pp. 19–20

E.2 Discussion on Related works

  • Unlike ARPO (Dong et al., 2026), FR3E (Zheng et al., 2025), and DeepSearch, SPARK uses intrinsic <explore> reasoning rather than external statistical signals or controller heuristics.The discussion characterizes SPARK as proactive across the trajectory horizon and cites its out-of-domain performance in Table 3 as evidence of robust generalization.Source: §E.2 · p. 20

E.3 Discussion on Reducing Dependence on Human Priors

  • SPARK’s <explore> signal lets agents identify uncertainty without task-specific annotations or handcrafted rules, supporting adaptation to novel scenarios.The discussion points to robust generalization on out-of-domain L2 splits as evidence that exploration can emerge from learned intrinsic signals without explicit supervision.Source: §E.3 · p. 20

E.4 Failure Mode Analysis

Despite strong performance across diverse benchmarks, SPARK can underperform when uncertainty signals fail to identify critical states or when critical decisions are densely distributed. Learned uncertainty estimators or curriculum strategies could help address these limitations.

Failure Mode Analysis

  • SPARK may miss exploration opportunities or branch spuriously when a limited-capability base model fails to trigger the <explore> signal reliably at critical states.The signal may also be triggered at routine steps.Source: §E.4 · p. 20
  • When critical decisions are densely distributed throughout a trajectory, selective branching loses its advantage and may not significantly outperform uniform exploration.Source: §E.4 · p. 20
  • Future work could use learned uncertainty estimators to calibrate branching decisions or curriculum strategies to progressively refine exploration signals.Source: §E.4 · p. 20

Related papers

Loading 2601.20209v2…