EnvSched paper — Reward-variance rollout scheduling — What does it mean?

The news. On October 27, 2026, a team from PKU, XJTU, THU, Samsung Research, CASIA and CUHK posted EnvSched, a scheduler that chooses which environment-task pairs an agent-RL run rolls out next. On Qwen3-8B it reaches an average score of 48.81 across BFCL-v3, τ-Bench and ACEBench-Agent after 40 training steps, above the best score random selection reached, which took 120 steps. Read the paper →

Picture a tutor who must pick today's 64 practice problems for a student, and the student will try each chosen problem eight times. A problem the student passes all eight times, or fails all eight times, tells the tutor nothing about what to fix, because the attempts do not disagree. The useful problems are the mixed ones, where some attempts pass and some fail, since the gap between a passing attempt and a failing one is the lesson.

That is how GRPO-style reinforcement learning works. For each task the model produces a group of rollouts (eight here), the environment's verifier gives each rollout a reward, and each rollout's advantage is its reward relative to the rest of its group. When every rollout in a group earns the same reward, the advantages are all zero and that task contributes almost no gradient. The paper puts it as: tasks with nearly identical outcomes provide little learning signal. Yet one rollout in an executable agent environment means many tool calls against a stateful database followed by a verifier run, so uniform random sampling pays full price for tasks that are too easy or too hard. The same logic shows up in a pass/fail check that never disagrees with itself: a test that every version passes cannot rank versions. That is an analogy from evals, not something the paper claims.

The hard part is knowing which problems are mixed before spending the rollouts. A pilot of eight rollouts per candidate would cost as much as the training it is meant to save, so EnvSched predicts each task's reward variance from rollout history it already has, with zero additional probe trajectories. It builds a dual-relation graph in which every node is one environment-task pair.

• Within-environment edges link tasks in the same environment, scored by six TF–IDF views of the instruction, verifier checks, verifier code and initial state.
• Cross-environment edges link tasks from different environments that do similar abstract work. An LLM first rewrites each task with tool names, field names and identifiers removed, leaving categories such as lookup, eligibility checking, relation replacement and dependent-state validation. The paper's example is that reassigning a consultant and transferring a hospital bed can share the same lookup, eligibility and relation-update pattern.

At each training step, the observed mean reward, variance and dispersion of a node's nearest observed neighbours (6 within-environment and 12 cross-environment by default) flow along both edge types. The two neighbour estimates are averaged into a prior and blended with the node's own history, so a never-tried task borrows its estimate from similar tasks and gradually trusts its own results as they accumulate. Back to the tutor: it has not seen this exact problem, but it has seen several that look just like it and knows how those went.

Ranking by predicted variance alone would be a trap, because the tutor would keep drilling a few topics and never find the unvisited topic full of mixed problems. So each batch is split by a coverage fraction ρ = 0.5. Of the 64 slots, 32 go first to underobserved environments and tasks (coverage) and 32 go to the highest predicted informativeness, discounted for tasks already picked many times (exploitation). A similarity penalty keeps near-duplicate tasks out of one batch, and environment quotas cap concentration. The paper's ablation on Qwen3-4B, with 200 training steps, shows why both halves are needed:

Read the last two rows as the tutor's two failure modes. Exploitation only reaches the highest variance (0.0442) but touches the fewest environments (33.95, below random's 36.53), and its BFCL-v3 score barely moves from random's (29.17 against 28.83). Coverage only touches the most environments (51.00), yet its variance (0.0357) is only a little above random's and its score trails the full scheduler (29.71 against 31.88). Each half covers the other's blind spot: the full scheduler has the best BFCL-v3 score of the six rows while sitting between the two extremes on variance and coverage.

Now the arithmetic. The paper's default batch is 64 environment-task pairs with eight rollouts each, so a training step runs 512 rollouts. Suppose (illustrative) that a random batch contains 24 tasks whose eight rewards all match. Those tasks cost 192 rollouts, 37.5% of the step, and add almost nothing to the update. Swapping them for tasks likely to be mixed puts the same 512 rollouts to work. The paper measures the effect instead of assuming it: on Qwen3-4B, mean within-task reward variance in a 64-task batch rises from 0.03208 under random scheduling to 0.04290, +34%, while median reward stays nearly flat (0.592 against 0.595).

The scheduler is cheap. Online selection took 6,985.94 seconds over the 200-step run, or 34.93 seconds per step, against roughly 25 minutes for one Qwen3-4B step on H100 hardware, so scheduling adds about 2.3% to each step. The headline comparison is for Qwen3-8B only, where 40 steps against random's 120 is 3× fewer steps. One caveat: every experiment uses a single pool of 2,550 tasks across 51 environments, so other pools are not tested in the paper.

Two habits carry over to building agents, as analogies rather than results from the paper. First, golden cases are informative only if some versions of your agent fail them; a case every version passes is a regression guard, not a progress signal. Second, the cost profile of an agent is dominated by expensive tool-running work, so deciding which runs to spend before launching them is a cost lever. EnvSched itself is a training-time method, and the paper does not apply it to eval suites.

Goes deeper in: AI Agents → Evals & Diagnostics → Pass/Fail vs Score