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 RL lacks high-quality trajectories and often wastes limited computation through uniform exploration. SPARK dynamically branches at critical decision states using intrinsic decision-making signals, and experiments report stronger success rates, efficiency, and generalization, including on unseen scenarios.

  • Problem

    Long-horizon agentic RL faces a scarcity of high-quality trajectories because vast state spaces make successful sequences sparse under resource constraints.

  • Method

    SPARK uses intrinsic decision-making signals to identify critical states and dynamically branch exploration there while proceeding linearly through routine decisions.

  • Results

    SPARK achieves superior success rates, better exploration efficiency, and robust generalization, including 80.5% versus 29.7% for GRPO on ALFWorld L2 out-of-domain tasks.

  • Takeaways & Limitations

    Strategic branching selectively expands exploration at critical decision points and achieves precise resource allocation for agentic learning.

  • Takeaways & Limitations

    The intrinsic-signal design may not fully exploit exploration opportunities in extremely low-capability base models with limited self-awareness.

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

Long-horizon agentic RL is limited by scarce high-quality trajectories and inefficient uniform exploration. SPARK addresses this by dynamically branching at critical decision points, improving resource allocation, sample quality, success rates, and generalization.

  • Agentic RL struggles because long-horizon tasks have vast state spaces where a single misstep can derail sequences, making successful trajectories sparse.
  • SPARK outperforms baselines across ALFWorld, ScienceWorld, and WebShop, achieving +73.5% average improvement.
  • Uniform exploration wastes computation on trivial steps while undersampling pivotal decisions, producing inefficient exploration and unstable training under resource constraints.
  • SPARK autonomously identifies critical intermediate states using intrinsic decision-making signals and selectively initiates additional exploration branches there.
  • Dynamic branching prioritizes sampling quality over exhaustive coverage, generating more informative trajectories under constrained budgets.
  • Experiments demonstrate superior success rates, higher sample efficiency, and robust generalization to unseen scenarios.

2 Methodology

SPARK formulates long-horizon agentic tasks as partially observable decision processes and explores them by dynamically branching at states where intrinsic signals indicate additional exploration is valuable. It enforces a global rollout budget, organizes completed trajectories into trees, and uses them for tree-based policy optimization.

  • Problem Formulation: SPARK models agentic tasks as POMDPs in which the policy generates reasoning traces and actions from interaction histories, with sparse terminal success or failure rewards.The interaction history serves as a belief-state proxy, and the objective is to maximize expected return.
  • Dynamic Branching Exploration: SPARK initializes multiple diverse trajectory roots before extending active trajectories through either linear continuation or multibranch exploration.The initial roots diversify exploration, while the branching factor can be 1 or B.
  • Dynamic Branching Exploration: A branching criterion detects intrinsic <explore> signals in reasoning traces and selectively expands trajectories at states associated with epistemic uncertainty.The criterion assigns branching based on whether the dedicated signal appears, allowing the agent to identify where additional exploration is needed without handcrafted heuristics.
  • Budget Enforcement: SPARK adjusts the effective branching factor under a global rollout budget, never exceeding N and terminating rollouts at success, failure, or horizon K.This converts selective branching into budget-constrained trajectory-tree growth.
  • Tree-Based Policy Update: Completed leaf trajectories are grouped into trajectory trees and used for tree-based policy updates with shared-prefix comparisons and group-normalized advantages.The optimization algorithm remains unchanged while tree structure supports relative credit assignment among alternatives.
  • Theoretical Perspective: The theoretical perspective reallocates intermediate computation toward pivotal SPARK points, where branching replaces single-sample decision coverage with multiple conditional continuations.For B ≥2, the resulting probability of selecting at least one desirable action strictly exceeds qt, while avoiding repeated suffix rollouts after suboptimal pivotal decisions.

3 Experiments

Experiments evaluate SPARK across long-horizon agentic domains, showing strong performance, sample and token efficiency, generalization, and benefits from selective dynamic branching. Ablations further identify conditions that balance exploration diversity, depth, and budget.

  • Main Results: SPARK consistently outperforms prompting, supervised fine-tuning, and reinforcement-learning baselines across model scales and task domains.On ScienceWorld L2, SPARK-1.5B reaches 49.2%, exceeding GPT-5 at 33.6% and Gemini-2.5-Pro at 30.5%.
  • Main Results: +23.3% on ALFWorld Look and +39.4% on Pick2 show gains over GRPO from branching at critical states.The larger improvement on multi-step Pick2 than simple Look supports selective allocation toward decision-critical steps.
  • Generalization: 80.5% versus 29.7% on ALFWorld L2 demonstrates SPARK’s stronger out-of-domain success than GRPO.Across ALFWorld and ScienceWorld, SPARK limits ID-to-OOD degradation to 16.9% and 29.2%, compared with GRPO’s 61.2% and 48.3%.
  • Efficiency: 84.4% success with 20% of ALFWorld training data surpasses GRPO’s 76.6% with 100% data.At 40% data, SPARK reaches 89.1%, while GRPO and GiGPO fall to 22.7% at 20% data.
  • Efficiency: 6.9%, 47.0%, and 11.2% relative token consumption reductions occur on ALFWorld, ScienceWorld, and WebShop.Sharing common prefixes reduces redundant generation while concentrating exploration at critical decision points.
  • Ablation Study: 69.5%→45.3% on ScienceWorld shows that fixed-probability branching degrades performance relative to selective branching.Longer horizons amplify the cost of allocating exploration independently of decision criticality.
  • Ablation Study: 80.7% at M = 4 is the best initial-root result under fixed budget N = 8.M = 2 limits initial diversity, whereas M ≥ 6 exhausts budget before later adaptive branching.
  • Exploration Quality: 15.4% versus 27.1% repetitive actions on 1.5B L2 represents a 43% reduction for SPARK.The gap widens on harder splits, where concentrating search at uncertain states avoids redundant trial-and-error.

4 Related Work

Prior work improves exploration through process supervision, inference-time search, and tree-structured reinforcement learning, but long-horizon agentic learning remains resource-constrained. These approaches commonly rely on expensive annotations or uniform branching that does not target critical decisions.

  • Agentic Reinforcement Learning: Process Reward Models provide dense intermediate feedback but require expensive annotations that scale poorly to open-ended environments.
  • Strategic Exploration: Inference-time search and tree-structured reinforcement learning explore diverse paths, yet related methods typically apply uniform branching across steps.

5 Conclusion

SPARK is an RL framework for long-horizon agentic learning that uses dynamic branching to expand exploration at critical decision points. Empirical results report stronger success, exploration efficiency, and generalization, highlighting strategic exploration’s value for capable and efficient agents.

  • SPARK selectively expands exploration at critical decision points to achieve precise resource allocation.
  • Empirical results report superior success rates, better exploration efficiency, and robust generalization for SPARK.

Limitations

The study’s strategic branching relies on intrinsic decision-making signals, but this may underuse exploration opportunities in extremely low-capability base models with limited self-awareness.

  • Limitations: Intrinsic decision-making signals reduce reliance on external supervision while identifying critical decision points for dynamic branching.The authors propose learning-based calibration that combines internal signals with external feedback to improve state awareness.
  • Limitations: The theoretical analysis is heuristic rather than a rigorous proof of SPARK’s effectiveness.It is intended to motivate the method and provide intuition for its empirical behavior.
  • Limitations: SPARK concentrates exploration by branching at critical states instead of allocating computation uniformly across trajectory steps.Critical states have U(s) > τ, while routine states have U(s) ≤ τ and proceed linearly.
  • Limitations: The analysis assumes diminishing returns from additional exploratory branches when describing the value of concentrated exploration.Under concavity of f, the tree structure is argued to enable deeper exploration where it matters most.

A.3 Sample Complexity Advantage

SPARK’s sample-complexity argument says that branching at a small number of critical states concentrates comparable action samples there, potentially matching uniform exploration with fewer trajectories.

  • A.3 Sample Complexity Advantage: O(M · ρ) fraction of samples may suffice for SPARK to match uniform exploration performance, where ρ = Kc/K.This claim is presented under favorable conditions and with M roots.
  • A.3 Sample Complexity Advantage: Uniform sampling provides at most O(N) effective action samples per critical state after N trajectories.Each trajectory contributes at most one action sample at each critical state.
  • A.3 Sample Complexity Advantage: SPARK branches multiple alternatives under shared prefixes, increasing comparable action samples at critical states within a fixed leaf budget.Shared prefixes avoid repeatedly sampling routine interaction histories, although they introduce correlations between samples.
  • A.3 Sample Complexity Advantage: 40% of training data was sufficient for SPARK to match RLVMR’s peak performance in the reported empirical validation.The authors relate this observation to an estimated critical-state ratio ρ ≈ 0.4, up to constant factors.
  • A.3 Sample Complexity Advantage: The heuristic analyses suggest an Ω(K/Kc) exploration advantage and approximately an M · ρ sample fraction when Kc ≪ K.The authors state that these analyses provide conceptual justification rather than rigorous proofs.

B.1 Datasets

The evaluation covers three long-horizon agentic domains—ALFWorld, ScienceWorld, and WebShop—with task splits designed to test both in-distribution performance and generalization to unseen settings.

  • B.1 Datasets: Three long-horizon domains are evaluated: ALFWorld, ScienceWorld, and WebShop.Tasks are categorized as L0 seen categories/instances, L1 seen categories with unseen instances, and L2 unseen categories and instances.
  • B.1 Datasets: ALFWorld evaluates household task execution, with the Unseen split testing generalization to completely novel domestic environments.The benchmark combines high-level goal decomposition with low-level action execution.
  • B.1 Datasets: ScienceWorld contains 30 scientific tasks across 10 virtual environments, often requiring horizons exceeding 30 steps.It tests experimentation, measurement, and strict logical reasoning in a large state space.
  • B.1 Datasets: WebShop contains over 1.1 million products and evaluates purchase-task completion on 500 test queries.The benchmark reports both task completion Score and Success Rate for open-ended search and attribute matching.
  • B.1 Datasets: SPARK is compared with GRPO, GiGPO, RLVMR, several general-purpose language models, ReAct, and ETO.These baselines span reinforcement-learning methods, language-model agents, and exploration-centered training.
  • B.1 Datasets: Success Rate is the primary metric, while WebShop additionally reports a partial-credit task completion Score.Success Rate records complete task success; Score reflects completion of intermediate sub-goals.

B.4 Implementation Details

Implementation uses a small successful-trajectory SFT phase to initialize intrinsic exploration signals, followed by RL with fixed rollout, optimization, and branching settings.

  • B.4 Implementation Details: 300 successful trajectories initialize the model’s ability to generate intrinsic exploration signals during SFT.The dataset combines 90% retro-annotated trajectories with 10% trajectories from real teacher-model interactions.
  • B.4 Implementation Details: 90% of the SFT data comes from retro-annotated golden paths, while 10% comes from newly generated successful interactions.Retro-annotation adds synthesized reasoning traces and selectively inserts <explore> tags.
  • B.4 Implementation Details: <explore> tags are robust to replacement by <exploring> and are concentrated in early trajectory steps.The authors interpret this distribution as reflecting temporal exploration necessity rather than random placement.
  • B.4 Implementation Details: Different SFT teacher models produce only marginal downstream performance differences, indicating that SFT primarily serves format alignment.The tested substitutions are Kimi-K2, Gemini-2.5-Flash, and Qwen2.5-32B.
  • B.4 Implementation Details: RL uses 512-token responses, 30-step episodes, learning rate 1 × 10^-6, group size N = 8, and batch size 16.The reward is 10 for success, 0 for failure, with a -0.1 penalty for invalid actions.
  • B.4 Implementation Details: SPARK defaults to 4 initial roots and branching factor 2, with experiments run on 4 NVIDIA A100-80GB GPUs.Prompt-length limits are 2,048, 4,096, and 6,000 tokens for ALFWorld, ScienceWorld, and WebShop.

C.1 Sample Efficiency

SPARK improves sample efficiency across long-horizon and multimodal tasks by concentrating exploration on informative trajectories rather than uniformly expanding rollouts. Its gains extend to inference-time scaling and visual benchmarks.

  • SPARK consistently outperforms reinforcement-learning baselines across ALFWorld and ScienceWorld sample-efficiency comparisons.
  • Sokoban requires spatial reasoning and long-term planning to push boxes onto designated targets.The illustrated execution path is down, left, down, right, then reaching the goal.
  • SPARK outperforms competitive baselines across ALFWorld, ScienceWorld, and WebShop at Pass@16 inference evaluation.The evaluation samples n = 32 trajectories and reports success using k = 16.
  • 88.3% average success exceeds GRPO by 11.3 points on multimodal Sokoban and EZPoints benchmarks.SPARK also exceeds ReAct by 80.9 points, reaching 88.3% versus 7.4%.

C.4 Sensitivity Analysis on Total Budget

SPARK benefits from additional branching budget up to an intermediate point, after which performance plateaus. Its learned exploration signal also supports test-time branching, while the paper contrasts selective branching with costly conventional tree search and acknowledges limited baseline coverage.

  • C.4 Sensitivity Analysis on Total Budget: Increasing total budget N from 4 to 8 yields gains of +7.8% on L0 and +12.5% on L1.Further scaling to N = 16 produces diminishing returns, with performance plateauing; N = 8 balances exploration breadth and efficiency.
  • C.4 Sensitivity Analysis on Total Budget: <explore>-conditioned branching at inference yields consistent gains across all benchmarks.The strategy branches when the model emits <explore> and selects the best continuation by majority voting.
  • C.4 Sensitivity Analysis on Total Budget: SPARK’s Wilcoxon signed-rank comparison against GRPO across benchmarks and model scales gives p = 9.7e-4, rejecting H0 at α = 0.05.The test pairs SPARK and baseline performance and evaluates whether their differences are significant.
  • E.1 Discussion on Tree-Based Baselines: At 30 steps, binary branching produces 2^30 > 10^9 potential trajectories, making exhaustive tree search impractical.SPARK instead triggers branching selectively at critical states using intrinsic decision-making signals.
  • E.1 Discussion on Tree-Based Baselines: The empirical comparisons focus on chain-like RL methods such as GRPO, while adapting tree methods to long-horizon agentic domains remains future work.

E.4 Failure Mode Analysis

SPARK’s selective branching can fail when the base model cannot reliably recognize uncertainty or when critical decisions are densely distributed. The examples illustrate exploration signals appearing during object search and web-product retrieval tasks.

  • SPARK may miss critical states or branch spuriously when the base model poorly recognizes uncertainty.The paper identifies unreliable <explore> triggering as a failure mode.
  • When critical decisions are densely distributed, selective branching may lose its advantage over uniform exploration.The paper proposes learned uncertainty estimators and curriculum strategies as possible future remedies.
  • ALFWorld examples: In ALFWorld, the agent emits <explore> while searching likely locations for an egg before placing it in a microwave.
  • ALFWorld examples: In a second ALFWorld task, the agent explores likely sidetables, drawers, or tables before placing two watches in a dresser.
  • WebShop examples: In WebShop, exploration appears while formulating searches constrained by product attributes, colors, sizes, and prices.The examples include women’s tops under $50 and men’s moisture-wicking shirts under $40.
Loading 2601.20209v2…