PaperlayerView exact revision on arXiv

Source-linked AI summary

EnvSched: Environment-Aware Scheduling for Rollout-Efficient Agent Reinforcement Learning

Sihan Yang, Weichen Bai, Ruichuan An, Yiming Cheng, Zhiyuan Feng, Tianyi Jiang, Renye Yan, Ning Ding, Yifan Zhang, Renrui Zhang, Yehui Tang, Wentao Zhang

arXiv:2610.37609v1cs.LGcs.CL

TL;DR

As executable environments scale, generating and verifying agent RL rollouts grows increasingly costly, while existing task-selection methods leave environment structure outside the selection model. EnvSched schedules environment–task pairs using reward-variance predictions and environment coverage; it improves performance across model sizes and benchmarks, reaching a 48.81 average score on Qwen3-8B after 40 steps, above random selection’s highest score after 120 steps.

  • Problem

    Existing online RL task-selection methods model prompts or tasks but omit executable environments, despite their role in shaping tools, states, transitions, verification, and learning signals.

    Source: §1 · p. 2

  • Method

    EnvSched represents environment–task pairs in a dual-relation graph and uses propagated rollout history to schedule high-variance tasks alongside underobserved environments and tasks.

    Source: §1 · p. 3, §2.2 · p. 4

  • Results

    EnvSched consistently improves performance over random scheduling across four Qwen3 model sizes and three benchmarks at matched rollout budgets, reaching a 48.81 average score on Qwen3-8B after 40 steps versus random selection’s highest score after 120 steps.

    Source: §1 · p. 3, §4 · p. 11

  • Takeaways & Limitations

    Reward differentiation and environment coverage are complementary sources of training value, supporting environment-level data management as a data-centric direction for efficient Agentic RL.

    Source: §1 · p. 3

Abstract

from arXiv · show

As executable environments for language agents scale, generating and verifying their rollouts becomes increasingly expensive. Under finite rollout budgets, this raises an important question: can data management at the environment level make agentic reinforcement learning (RL) more efficient by organizing, evaluating, and scheduling task instances together with the environments that determine their tools, states, transitions, and verification? To address this question, we introduce EnvSched (Environment-aware Scheduling), an online scheduler that learns from rollout history. EnvSched assigns scheduling value through two complementary modeling choices: exploitation prioritizes tasks likely to provide informative reward differences, while coverage spreads each batch across underobserved environments and interaction patterns. EnvSched organizes environment--task pairs as nodes in a dual-relation graph, with within-environment edges capturing task semantics and shared tool, state, and verifier structure, and cross-environment edges capturing abstract execution and reward topology. By propagating historical rollout statistics along both edge types, it predicts within-task reward variance. These predictions guide a scheduler that allocates each batch to tasks with high predicted reward variance and underobserved environments and tasks. Environment quotas and a similarity penalty further limit concentration and redundancy, yielding informative and diverse batches without additional pilot rollouts. In RL on Qwen3-8B, EnvSched achieves an average score of 48.81 across BFCL-v3, tau-Bench, and ACEBench-Agent after 40 training steps, exceeding the highest score attained by random task selection after 120 steps. It also improves downstream performance across model sizes at the same training budget.

1 Introduction

EnvSched treats environment–task pairs as the unit of Agentic RL data management, combining reward-informativeness prioritization with environment coverage. On Qwen3-8B, it reaches an average score of 48.81 across three benchmarks after 40 steps, exceeding random selection’s highest score after 120 steps.

1 Introduction

  • Existing online task-selection methods model prompts or tasks but omit executable environments, which determine tools, initial states, transitions, and verifiers.Those environment properties shape how tasks unfold and what learning signal they produce.Source: §1 · p. 2
  • EnvSched formulates environment-level data management as jointly organizing, evaluating, and scheduling task instances with the executable environments where they run.The paper presents this as a data-centric direction for efficient Agentic RL and reports consistent rollout-efficiency gains across model sizes and improved downstream benchmark performance.Source: §1 · pp. 2–3
  • EnvSched models environment–task pairs as graph nodes, linking tasks by within-environment semantics and tool, state, and verifier structure, and across environments by abstract execution and reward topology.Historical rollout statistics propagate along both edge types to predict task reward variance; environment quotas and a similarity penalty limit concentration and redundancy.Source: §1 · p. 3
  • The scheduler combines exploitation of tasks with high predicted reward variance and coverage of underobserved environments and tasks, without additional pilot rollouts.Each batch allocates half to coverage and half to exploitation.Source: §1 · p. 3
  • 48.81 average score across BFCL-v3, τ-Bench, and ACEBench-Agent after 40 steps on Qwen3-8B exceeds random task selection’s highest score after 120 steps.The evaluation uses matched per-step rollout budgets.Source: §1 · pp. 2–3

2 Method

EnvSched schedules concrete environment–task pairs using a rollout-history loop that combines informativeness estimates with coverage of underobserved environments and tasks. Its dual-relation graph transfers historical statistics across similar tasks within and across environments to guide selection.

2.1 Problem Setup and Training Loop

  • Each training step selects distinct environment–task pairs for rollout and model update, then uses resulting rewards and histories in the next scheduling round.The scheduler repeats a rollout–update–propagation–selection loop throughout training.Source: §2.1 · p. 4

2.2 dual-relation graph

  • The dual-relation graph connects pairs through within-environment task and tool, state, and verifier similarity, and cross-environment abstract execution and reward structure.Within-environment similarity retains domain-specific information; abstract similarity supports transfer across different business terminology.Source: §2.2 · pp. 4–5

2.3 Predicting Task Informativeness

  • Historical reward statistics propagate along both relation types to form a graph prior, which is fused with each target’s history and calibrated into an informativeness score.The recorded statistics include mean reward, within-task reward variance, and mean-corrected dispersion; recent declines lower task priority.Source: §2.2 · p. 5, §2.3 · pp. 5–6, Figure 3 · p. 6

2.4 Coverage-Aware Task Scheduling

  • The scheduler allocates batch slots between coverage and exploitation, prioritizing underobserved environments and tasks in coverage and predicted informativeness in exploitation.Exposure discounting, environment quotas, and a similarity penalty limit repeated selection and redundant batch content; progress and identifier filters alter candidate eligibility.Source: §2.4 · p. 6

3 Experiments

Across the experiments, EnvSched improves benchmark performance over random scheduling while balancing reward differentiation with environment coverage. The evaluation also examines training efficiency, scheduler components, initialization, and neighborhood-size sensitivity.

3.1 Experimental Setup

  • The experiments train Qwen3-Thinking models with GRPO on 2,550 task instances across 51 executable environments, using BFCL-v3, τ-Bench, and ACEBench-Agent for evaluation.The shared batch contains 64 environment–task pairs, with 32 allocated to coverage and 32 to exploitation.Source: §3.1 · p. 7

3.2 Main Results

  • At 200 steps, EnvSched improves all three benchmark scores over random scheduling across four model sizes; Qwen3-4B gains +3.05 BFCL-v3, +3.23 τ-Bench, and +2.00 ACEBench-Agent.For Qwen3-30B-A3B, gains are +3.92, +3.03, and +2.67 points on BFCL-v3, τ-Bench, and ACEBench-Agent, respectively, without model-specific scheduler tuning.Source: §3.2 · p. 9
  • At 40 steps, Qwen3-30B-A3B scores 35.00 on BFCL-v3, 53.54 on τ-Bench, and 70.00 on ACEBench-Agent, exceeding the 200-step random baseline on all three.At 4B, the 40-step ACEBench-Agent score of 58.00 matches its 200-step score; at 8B, the 40-step τ-Bench score of 50.71 exceeds its 200-step score of 50.30.Source: §3.2 · p. 9

3.3.1 Reward Variance and Environment Coverage

  • Under the same 64-task batch budget, Qwen3-4B mean within-task reward variance rises from 0.03208 to 0.04290 (+34%), while environment coverage rises from 36.53 to 45.96 per batch (+26%).Tool coverage rises from 413.41 to 478.39 (+16%), and BFCL-v3 improves from 28.83 to 31.88; median reward remains nearly unchanged.Source: §3.3.1 · p. 9

3.3.2 Computational Cost

  • With cached similarities and fixed-capacity neighbor heaps, an incremental scheduling step costs O(N∆t log ˆK + N ˆK + NB), linear in task-pool size under the stated fixed-parameter conditions.In the measured 200-step run, selection takes 6,985.94 seconds total, or 34.93 seconds per step; sparse features use 85.87 MiB at the 2,550-task scale.Source: §3.3.2 · pp. 9–10

3.4.1 Component Contributions

  • Coverage-only scheduling reaches 51.00 environments but lowers mean reward variance to 0.0357, while exploitation-only reaches variance 0.0442 but covers only 33.95 environments; combining both objectives recovers breadth and informative reward differences.Both edge ablations reduce mean reward variance relative to the full graph; full EnvSched has the highest BFCL-v3 score among component configurations and ties the within-environment-only variant on ACEBench-Agent.Source: §3.4.1 · p. 10

3.4.2 Initialization Robustness

  • Across 100 runs, mean batch reward variance rises from 0.0596 at step 1 to 0.0813 at step 7, while exploitation hit rate rises from 57.2% to 92.1%.The initial-variance group gap falls from 32.8% to 2.8% by step 7, and the low- and high-initial-variance groups reach exploitation hit rates of 92.8% and 92.5%, respectively.Source: §3.4.2 · p. 11, Table 4 · p. 11

3.4.3 Neighborhood-Size Sensitivity

  • When either neighbor count is independently halved or doubled around the defaults Kwithin = 6 and Kcross = 12, the largest absolute deviations are 0.96, 0.81, and 1.33 percentage points on BFCL-v3, τ-Bench, and ACEBench-Agent.All tested settings outperform random scheduling on all three benchmarks.Source: Table 3 · p. 10, §3.4.3 · p. 11

4 Conclusion

EnvSched treats environment–task pairs as the unit for scheduling executable-environment RL. Across four Qwen3 model sizes, it improves all three benchmark scores over random scheduling under matched rollout budgets.

4 Conclusion

  • Across Qwen3-1.7B, Qwen3-4B, Qwen3-8B, and Qwen3-30B-A3B, EnvSched consistently improves performance over random scheduling on BFCL-v3, τ-Bench, and ACEBench-Agent under matched rollout budgets.The conclusion attributes the gains to complementary effects of reward variance and environment diversity.Source: §4 · p. 11
  • The paper presents environment-level data management as a useful data-centric perspective for efficient agentic RL.It frames this perspective as relevant to scaling increasingly capable agent models with better use of training rollout budgets.Source: §4 · p. 11
  • EnvSched selects tasks for informative reward differentiation while maintaining broad environment coverage.Its scheduling unit is the environment–task pair.Source: §4 · p. 11

A.1 Executable Environments for Agent Training

Executable environments and verifiable tasks support tool-using agent training, and EnvSched addresses their use by organizing environment–task relationships and selecting tasks from the available pool.

A.1 Executable Environments for Agent Training

  • Tool-use benchmarks including BFCL, τ-Bench, and ACEBench assess complementary aspects of tool invocation, user interaction, and task completion.EnvFactory provides 85 environments and 953 task instances [4]; EnvScaler produces 191 environments and approximately 7,000 scenarios [5].Source: §A.1 · p. 15
  • Agent World Model scales to 1,000 code-driven, database-backed environments with MCP interfaces and code-augmented reward verification [6], while Agent-World combines environment–task discovery with multi-environment RL.Agent-World also uses a self-evolving arena to diagnose capability gaps and synthesize targeted tasks.Source: §A.1 · p. 15
  • EnvSched addresses the training use of these systems by organizing environment–task relationships and selecting informative, diverse tasks from the available pool.The passage also situates these systems alongside work on embodied interaction and broad evaluation suites [26] [27] [28].Source: §A.1 · p. 15

A.2 Task Informativeness Estimation and Online Selection

Prior online-selection methods estimate task informativeness from reward variation, historical feedback, and task relationships. EnvSched adds executable-environment structure and explicit environment coverage to this line of work.

A.2 Task Informativeness Estimation and Online Selection

  • Group-relative RL uses rollout reward differences to identify informative tasks [19]; DAPO filters uniformly successful or unsuccessful groups [29], while Pilot-Commit uses pilot-sample reward variation to allocate later rollouts [30].For binary rewards, informativeness is captured by variance p(1 −p).Source: §A.2 · p. 15
  • DOTS uses reference rollouts and an attention-based difficulty predictor [16], while DPS models prompt-solving dynamics from historical outcomes [17].LEEPS combines representation-space neighbors, historical outcomes, and explore–exploit portfolios to identify prompts likely to yield nonzero reward variance without extra rollouts [18].Source: §A.2 · p. 15
  • EnvSched uses within-environment edges for shared tools, database fields, and verifier constraints, and cross-environment edges for abstract execution and reward topology.The resulting predictions guide selection using both individual task informativeness and explicit environment coverage.Source: §A.2 · p. 15

B Complete Historical Estimation

EnvSched centers historical observations, clips them to bounded ranges, and estimates task histories using relation-specific neighbors. It ranks tasks over the full environment–task pool and maps predicted variances through an empirical quantile function.

B Complete Historical Estimation

  • Historical observations are centered against a current global reference, with the first observed batch supplying initialization when no step-level reference exists.Centered observations are clipped to [0, 0.25] for v and [0, 1] for m and d.Source: B Complete Historical Estimation · pp. 15–16
  • Within- and cross-environment similarities define relation-specific task distances, adaptive bandwidths, and neighbor weights.The relations use Sfull and Sabs, respectively.Source: B Complete Historical Estimation · p. 16
  • Tasks without observed neighbors for a relation use the current global reference, and percentile ranks use average ties across all N environment–task pairs.The empirical quantile function is computed over predicted variances for all N tasks using linear interpolation.Source: B Complete Historical Estimation · p. 16

B.1 Observation Statistics and Priority Construction

EnvSched combines rollout reward statistics and recency-weighted task histories to estimate priority, then schedules through coverage and exploitation with candidate filters and a static-structure cold start.

B.1 Observation Statistics and Priority Construction

  • Each selected environment–task pair yields K rewards, from which the implementation computes reward mean, population variance, and mean-corrected dispersion.The dispersion and clipping definitions use the training pool reward scale [0, 1].Source: §B.1 · p. 16
  • Task histories use earlier observations weighted by half-life, with the current reference substituted when no history is available.Predicted mean and dispersion reconstruct a second variance estimate that is combined with the direct variance prediction.Source: §B.1 · pp. 16–17
  • The final priority is computed independently for each half-life and incorporates recent decline.The complete score is recomputed separately for long and short half-lives, including centering, neighbor aggregation, percentile ranks, and quantile mapping.Source: §B.1 · p. 17

C Scheduling Rules and Cold Start

  • Coverage first favors candidates with lower current-step coverage, cumulative environment selections, and task observation counts, subject to environment and consecutive-task caps.The experimental caps are C1 = 4, C3 = 11, and Ctask = 2; the remaining choice uses informativeness and a batch-similarity penalty.Source: C Scheduling Rules and Cold Start · p. 17
  • A task with at least three scorable transitions and a non-positive estimated residual is excluded from exploitation but remains eligible for coverage.New observations can make it eligible for exploitation again.Source: C Scheduling Rules and Cold Start · p. 17
  • The identifier filter replays saved high-reward trajectories and removes suspicious actions only when their removal lowers reward; cold start instead selects representative tasks using static structure.Cold start takes one representative per environment, then fills remaining slots using global and within-environment novelty, with at most two tasks per environment in the first batch.Source: C Scheduling Rules and Cold Start · p. 17

D Static Representation and Runtime Configuration

The appendix specifies EnvSched’s static representations, runtime settings, and cross-environment graph-construction prompt. It also gives the structured prompt input and introduces qualitative cases illustrating scheduler decisions.

D Static Representation and Runtime Configuration

  • The default pool has 2,550 tasks across 51 environments, with 64 pairs per batch split evenly between coverage and exploitation.Each pair receives eight rollouts; fixed graph, history, and scheduling hyperparameters are shared across model sizes.Source: D Static Representation and Runtime… · pp. 17–18
  • Six TF–IDF views encode task text, verifier checks and code, initial context, and the complete operation description; numeric values are abstracted into categories for cross-environment similarity.The six view weights are (0.28, 0.08, 0.16, 0.12, 0.16, 0.20).Source: D Static Representation and Runtime… · p. 18

E Cross-Environment Graph Construction Prompt

  • Within-environment edges use concrete TF–IDF features, whereas cross-environment edges use an abstract representation that removes domain-specific identifiers.The prompt maps a task specification to a structured description of required operations and their dependencies, then uses the abstraction for Sabs.Source: E Cross-Environment Graph Construction… · p. 18, §E.1 · p. 18

E.1 What This Prompt Extracts

  • The extraction prompt describes operations, prerequisite gates, dependencies, reward-check groups, and conflicts such as ordering, mutual exclusion, or destructive effects.It abstracts away tool names, entity identifiers, and database fields while retaining dependency structure, gate types, and group relations.Source: §E.1 · pp. 18–20

E.2 System Prompt

  • The system prompt extracts factual execution and reward topology from static task evidence, explicitly forbidding rollout-based predictions or difficulty labels.It requires a partition of verifier checks into groups controlled by the same operation or prerequisite gate.Source: §E.2 · p. 21
  • The system prompt distinguishes execution-ready task literals from identifiers that require a tool path, and uses fixed vocabularies for operation families and gate provenance.The initial-state summary is evidence for the static analyzer, not information shown to the agent.Source: §E.2 · pp. 21–22

E.3 User Message Format

  • The prompt input is structured JSON containing shared environment information, task instructions, initial-state summaries, verifier checks, and relevant tool implementations.The appendix introduces three Qwen3-4B cases involving previously unselected tasks, whose predictions therefore rely on other environment–task pairs.Source: §E.3 · p. 23, F Qualitative Case Studies · p. 23

F.1 Within-Environment Edges: env_141-task_27 at Step 28

Within-environment neighbors share tools and verifier conditions, making their rollout outcomes relevant to an unselected task. In the insurance-policy case, the realized task variance exceeded the batch mean despite the environment being heavily sampled.

F.1 Within-Environment Edges: env_141-task_27 at Step 28

  • The target was unseen despite 56 prior rollout groups across 40 tasks in its heavily sampled environment.All six within-environment neighbors had been rolled out; they shared tools and an ordering constraint against duplicate coverage types.Source: §F.1 · p. 24
  • 0.04 was the fused predicted variance, combining a within-environment neighbor estimate of 0.05 and a cross-environment estimate of 0.02.The global reference was 0.03, and the two relation estimates were fused with equal weight.Source: §F.1 · p. 24
  • 0.078 realized variance exceeded the step’s batch mean variance of 0.036 for an unselected insurance-policy task.Seven of eight trajectories formed two behavioral groups: four stopped after authorization checks, while three completed most of the edit sequence and passed 10–12 of 16 checks.Source: §F.1 · p. 24

F.2 Cross-Environment Edges: env_190-task_8 at Step 40

This case study shows how tasks from different domains can inform one another when they share an execution pattern. For the allergy task, cross-environment neighbors provide reward-variance information that same-environment tasks alone cannot provide.

F.2 Cross-Environment Edges: env_190-task_8 at Step 40

  • Cross-environment neighbors share the work pattern of finding a requested record, checking authorization, and making specific edits, despite operating on different records and tools.Examples include editing a member’s mood history, rescheduling sessions, and advancing a claim.Source: §F.2 · pp. 25–26
  • Five of eight rollouts scored zero after failing to resolve the patient; the other three reached the verifier, with one scoring 0.7857 and two 0.2143.The task’s mean reward was 0.152 and variance 0.066, against a batch mean realized variance of 0.038 at that step.Source: §F.2 · pp. 25–26
  • The cross-environment neighbors’ variances average 0.04, while same-environment neighbors average 0.02; their equal-weight fusion yields a prediction of 0.03.The same-environment tasks had near-zero variances, reflecting consistent outcomes in that environment but not indicating whether a different allergy task would be similarly easy.Source: §F.2 · p. 26
  • The task is selected during exploitation at batch rank 33, with predicted mean reward 0.562 and predicted dispersion 0.136.The scheduler had no history for this task; its environment had been sampled 48 times across 26 tasks, while the nearest same-environment tasks had low observed variances.Source: §F.2 · pp. 25–26

F.3 Both Relations Contributing: env_156-task_5 at Step 4

At an early training step, both graph relations provide neighbors for a many-lookup task. Their fused estimate informs exploitation selection, and the resulting rollouts show varied outcomes around lookup and downstream task completion.

F.3 Both Relations Contributing: env_156-task_5 at Step 4

  • Within-environment neighbors shared clinic and time-slot tools, while cross-environment neighbors shared a many-lookup pattern in which resolving a name gates downstream actions.The cross-environment neighbors came from hospital patient management, a review platform, and a licensing board.Source: §F.3 · p. 27
  • The within-environment estimate was 0.07 and the cross-environment estimate 0.10, fusing to 0.09 against a global reference of 0.06.The task had no own history, and its environment had only five prior groups over four tasks.Source: §F.3 · pp. 26–27
  • The task ranked 40th in the exploitation phase, with q = 0.9861, predicted mean reward 0.505, and predicted dispersion 0.387.It required rescheduling two donors, releasing and blocking appointment slots, checking another donor’s eligibility, and creating an appointment.Source: §F.3 · pp. 26–27
  • The task’s mean reward was 0.510 and variance 0.202, twice the batch mean realized variance of 0.091; two trajectories passed all twelve checks.Three trajectories completed rescheduling blocks but failed downstream checks, while one failed to resolve a facility name within 40 turns.Source: §F.3 · p. 27

Related papers

Loading 2610.37609v1…