TurnOPD: Optimizing the Accuracy-Time Frontier in Long-Horizon Agent Training

TL;DR

On-Policy Distillation (OPD) is the gold standard for transferring capabilities from giant teachers (like DeepSeek or GPT) to smaller, efficient student agents. However, for long-horizon tasks, vanilla OPD is painfully slow and often "forgets" to train the most difficult late-stage decisions. TurnOPD fixes this by introducing a "Turn-Aware" budget system that cuts unnecessary rollout steps and rebalances the loss function to favor deep-turn decisions, achieving comparable or better performance with over 2x speedup.

Background: The Hidden Inefficiencies of Agent OPD

In a typical OPD setup, a student agent interacts with an environment, and a teacher provides feedback via Reverse-KL divergence. While this works for short text generation, it breaks down in long-horizon agent tasks (e.g., navigating a web shop or complex house planning) due to two mismatches:

1. The External Mismatch: We often force agents to complete 50+ steps every time. If the agent fails at step 5, the subsequent 45 steps of "garbage" context yield noisy signals that waste GPU time.
2. The Internal Mismatch: Standard loss functions average KL over all tokens. Since shallow turns happen every episode but deep turns only happen when the agent survives, the gradient is dominated by "easy" early steps (e.g., just saying "Hello" or "I will start").

Methodology: The Turn-Aware Budget Controllers

The core innovation of TurnOPD is treating the training process as a resource allocation problem. It manages two budgets: How much we interact and How much we learn from each turn.

1. Adaptive Rollout-Depth Budgeting

Instead of a fixed horizon, TurnOPD calculates an optimal depth ($H_{ctrl}$) using:

• Efficiency Centroid ($H_{eff}$): A statistical "sweet spot" where the teacher's KL signal is most informative relative to the survivor rate.
• Coverage Floor ($H_{cov}$): A safety mechanism ensuring rollouts are deep enough to cover 80% of successful completions.

Figure 1: Evolution from Trajectory-level OPD to Turn-aware TurnOPD.

2. Progressive Turn-Normalized Loss

As the agent masters the basics, TurnOPD shifts its attention. Early in training, the loss is token-weighted (for stability). Later, it shifts to Turn-Balanced Weighting, giving the few "deep survivors" an equal voice in the gradient update. This ensures the model actually learns how to close a task, not just how to start it.

Experiments: Breaking the Speed Limit

The authors tested TurnOPD against Vanilla OPD and TCOD (Temporal Curriculum) across ALFWorld (Embodied AI), WebShop (E-commerce), and Multi-Hop Search (Complex QA).

Key Results:

• ALFWorld: The 1.7B model reached 86.29% accuracy in 1.93 hours, while the vanilla baseline took 4.42 hours to reach only 83.0%.
• Multi-Hop Search: TurnOPD consistently stayed at the top of the "Accuracy-Time Frontier," meaning at any given minute of GPU time, TurnOPD provided the smartest model.

Figure 2: The Accuracy-Time Frontier. TurnOPD (red line) consistently reaches higher accuracy faster than baselines.

Deep Insight: Contamination Compression

A brilliant theoretical contribution of this paper is Proposition 1. It explains why KL drops in later turns: it's not always because the student is getting smarter. Often, it's because the student-generated context becomes "stereotyped" (loops/errors), making the next token so predictable that the KL is compressed to near-zero, even if the high-level policy is still wrong. TurnOPD's adaptive depth prevents the model from being "tricked" by this compressed, low-value signal.

Conclusion and Future Outlook

TurnOPD proves that for agents, context matters more than count. By moving away from flat sequence processing to a "Turn-Aware" logic, we can train agents that are specialized for long-term planning without the prohibitive cost of full-horizon rollouts.

Limitations: The method currently relies on periodic "probes" (full-length rollouts) to update the controllers. Future work might explore completely probe-free adaptive horizons using uncertainty estimation.