EnvSched: Environment-Aware Scheduling Boosts Agent RL Efficiency

As the scale of executable environments for language agents grows, the cost of generating and verifying their rollouts rises sharply. Under a limited rollout budget, how can environment-level data management make agent reinforcement learning (RL) more efficient? A recent paper proposes EnvSched (Environment-aware Scheduling), an online scheduler that learns from rollout history.

Core Problem: The Rollout Bottleneck from Environment Scaling

Agent RL training relies on a large number of trajectories (rollouts) from interaction with environments. When the number of environments grows from dozens to hundreds or thousands, and each environment corresponds to different tools, state-transition logic, and verifiers, naive uniform sampling wastes a large number of rollouts on low-information interactions. The key question raised by the paper is: can task instances be jointly organized, evaluated, and scheduled together with the environments that determine their tools, states, transitions, and verification, so as to obtain more informative training batches under a limited budget?

Rollouts and agent reinforcement learning: In reinforcement learning, a rollout refers to a complete trajectory (a sequence of states, actions, and rewards) produced by an agent interacting with the environment under the current policy. For tool-calling agents, a single rollout may involve multiple rounds of tool calls, state queries, and verifier judgments, so the cost of a single trajectory is far higher than that of a single-step interaction in traditional RL. During training, methods such as policy gradient or PPO require a large number of rollouts to estimate advantage functions and update the policy; the total number of rollouts directly determines training cost. When the number of environments grows to hundreds or thousands, and each environment has multiple task instances, uniform sampling means a large amount of budget is spent on repetitive or low-information interactions. The core insight of EnvSched is that, with a fixed rollout budget, choosing "which environment-task pairs to spend budget on" is as important as "how to update the policy"; environment-level scheduling can become an efficiency lever independent of model improvements.

EnvSched's Modeling of Two Types of Scheduling Value

EnvSched assigns scheduling value to tasks through two complementary modeling choices.

Exploitation prioritizes tasks that are likely to provide informative reward differences. In RL, tasks with larger reward differences help the policy distinguish good actions from bad ones, thereby producing effective gradient signals.

Coverage, on the other hand, spreads each batch across under-observed environments and interaction patterns. This prevents the scheduler from repeatedly selecting a small number of "good tasks," which would otherwise leave data from other environments missing for long periods.

These two types of value jointly constitute the scheduling decision, ensuring both the informativeness of the batch and the diversity of environments and tasks.

Reward variance and gradient signals: In policy gradient methods, the variance of the gradient estimate is closely related to the variance of the reward. For the same task, if the reward differences produced by different actions are small, the policy can hardly distinguish good actions from bad ones, and the gradient signal is weak; conversely, tasks with large reward differences provide clearer contrastive signals and help the policy learn quickly. Therefore, prioritizing tasks with high predicted reward variance is essentially selecting samples with greater gradient information. However, pursuing high variance alone causes the scheduler to repeatedly select a small number of "good tasks," leaving data from other environments missing for long periods and causing the policy to overfit or degrade on those environments. The coverage mechanism maintains the diversity of the training distribution by spreading batches across under-observed environments and interaction patterns, avoiding environment-level "forgetting" caused by scheduling bias. The two types of value jointly constitute the scheduling decision, striking a balance between informativeness and diversity.

Dual-Relation Graph: Structured Organization of Environment-Task Pairs

EnvSched organizes environment-task pairs as nodes in a dual-relation graph.

• Within-environment edges: These capture task semantics as well as shared tools, states, and verifier structures. Tasks within the same environment often reuse the same tool set and verification logic, and within-environment edges encode these similarities into the graph structure.
• Cross-environment edges: These capture abstract execution patterns or reward topologies. Different environments may share commonalities in execution patterns or reward distributions, and cross-environment edges allow the scheduler to transfer experience across environments.

By propagating historical rollout statistics along the two types of edges, EnvSched predicts the reward variance within a task. The prediction results directly guide the scheduler: assign each batch to instances with high predicted reward variance and insufficient observation of environments and tasks.

Statistic propagation on the graph: The dual-relation graph treats each environment-task pair as a node; within-environment edges connect different tasks in the same environment, and cross-environment edges connect tasks with similar execution patterns or reward topologies. The scheduler uses reward statistics observed in historical rollouts and performs message passing along the edges to predict the reward variance of tasks that have not yet been sufficiently observed. The intuition behind this design is that tasks within the same environment share tool sets and verification logic, so their reward distributions are correlated; tasks with similar execution patterns in different environments may also have transferable reward topologies. Through graph propagation, the scheduler can make more accurate predictions with the help of neighbor information when data are sparse, without the need to run a separate pilot rollout for each task. The graph structure also makes scheduling decisions interpretable: high-variance predictions can be traced back to whether similar tasks within the environment or similar tasks across environments provided the evidence.

Quotas and Similarity Penalties: Preventing Batch Concentration and Redundancy

Variance prediction and coverage tendency alone are not enough. Without constraints, the scheduler may continuously favor a small number of high-variance tasks. To address this, EnvSched introduces environment quotas and similarity penalties: environment quotas limit the proportion of a single environment in a batch, while similarity penalties reduce the weight of tasks that are highly similar to already-selected tasks. Together, they ensure that the batch contains both informative samples and diversity in the environment and task dimensions, without requiring additional pilot rollouts to warm up the scheduler—a point that is particularly important in budget-sensitive scenarios.

Experimental Results: Higher Scores with Fewer Training Steps

The paper conducted RL experiments on Qwen3-8B. After 40 training steps, EnvSched achieved an average score of 48.81 on three benchmarks—BFCL-v3, tau-Bench, and ACEBench-Agent—surpassing the highest score achieved by random task selection after 120 training steps. This means that under the same rollout budget, EnvSched achieved better results with about one-third of the training steps. In addition, the paper points out that under the same training budget, EnvSched improves downstream performance across different model scales.

This result shows that environment-level data scheduling can become an independent lever for improving agent RL efficiency: without changing the model structure or increasing the total number of rollouts, merely by deciding "which environments and tasks to spend budget on," training effectiveness can be significantly improved.

BFCL-v3, tau-Bench, and ACEBench-Agent: These three benchmarks evaluate the tool-calling and interaction capabilities of agents from different perspectives. BFCL-v3 (Berkeley Function Calling Leaderboard) mainly evaluates the accuracy of model function calling, including multi-turn and parallel calling scenarios; tau-Bench simulates multi-turn conversations between real users and agents, requiring agents to complete tool operations while following domain policies, emphasizing rule compliance and state management during interaction; ACEBench-Agent covers a broader range of agent tasks, including tool use, multi-step reasoning, and environment interaction. Together, they form a relatively comprehensive evaluation system for tool-calling agents. EnvSched's average score of 48.81 on these three benchmarks shows that the improvements brought by its scheduling strategy are not limited to a single task type but generalize across benchmarks.

Implications for Agent RL Training

The value of EnvSched lies in elevating the granularity of scheduling from the "sample level" to the "environment-task pair level." Traditional experience replay or curriculum learning focuses more on the difficulty or value of individual samples, whereas EnvSched explicitly models the structural relationships among environments—shared tools, similar state transitions, and transferable reward topologies. This modeling approach is especially natural for tool-calling agents, because tool sets and verifiers are often reused across tasks.

Another noteworthy detail is "no additional pilot rollouts." Many adaptive sampling methods require first running a batch of exploratory rollouts to estimate task difficulty, which is itself wasteful in agent scenarios where rollouts are expensive. EnvSched directly reuses the historical statistics naturally generated during training, minimizing scheduling overhead.

Of course, the effectiveness of this method depends on the reliability of historical rollout statistics. In the early stage of training, when data are sparse, variance predictions on the graph may not be sufficiently accurate. The paper alleviates this problem through the coverage mechanism and quota constraints, but the scheduling quality during the cold-start phase still leaves room for further exploration.

Conclusion

EnvSched demonstrates the potential of environment-aware scheduling in agent reinforcement learning: by organizing environment-task pairs through a dual-relation graph, predicting reward variance, and combining coverage and diversity constraints, it significantly improves training efficiency under a limited rollout budget. For teams building large-scale agent training pipelines, this idea of "first deciding where to train, then deciding how to train" is worth learning from.

One-line Summary

EnvSched online-schedules environment-task pairs via a dual-relation graph, significantly improving agent RL efficiency under a limited rollout budget.

Paragraph Summary

EnvSched is a paper addressing the sharp rise in rollout costs in agent reinforcement learning. It proposes an online scheduler that learns from historical rollouts and allocates training budget at the environment-task pair level. The scheduler balances informativeness and diversity through two types of value modeling: exploitation (prioritizing high-reward-variance tasks) and coverage (spreading to under-observed environments and interaction patterns); it also organizes environment-task pairs into a dual-relation graph and propagates statistics along within-environment and cross-environment edges to predict within-task reward variance. Environment quotas and similarity penalties prevent batch concentration and redundancy, and no additional pilot rollouts are required. On Qwen3-8B, EnvSched achieves an average score of 48.81 on BFCL-v3, tau-Bench, and ACEBench-Agent in only 40 training steps, surpassing the highest score of random task selection at 120 steps, indicating that environment-level data scheduling can become an independent lever for improving agent RL efficiency.