E${}^3$-Orch: Towards Effective, Efficient, and Extensible Agentic Orchestration with Reinforcement Learning

Agentic orchestration enables multiple autonomous agents to collaborate on complex tasks through adaptive task decomposition, delegation and execution. However, existing orchestrators largely rely on hand-crafted orchestration logic and prompting strategies, limiting their ability to adapt and generalise across tasks and executor configurations. In this work, we propose E${}^3$-Orch, a reinforcement learning framework for learning effective, efficient, and extensible agentic orchestration through a $\text{milestone-plan-act}$ workflow. Rather than planning all subtasks upfront, E${}^3$-Orch organises execution around $\text{milestones}$, a mid-level abstraction that scopes planning and execution around meaningful intermediate objectives, enabling the orchestrator to adapt its decisions as the task evolves. For each milestone, the orchestrator constructs a dependency-aware plan, delegates subtasks to suitable executors, and parallelises independent subtasks for efficient execution. We learn the orchestration policy from execution feedback, using milestone and plan decisions as natural units for fine-grained credit assignment. To estimate their downstream contributions, we construct tree-structured rollouts that compare alternative decisions under shared execution histories. The policy is jointly optimised for task performance and efficiency through complementary rewards for performance, execution cost, and planning completeness, including an uncertainty-aware performance reward that accounts for stochastic downstream outcomes. Across seven benchmarks spanning diverse domains, E${}^3$-Orch achieves the best task performance under different agent configurations, improving on the strongest baselines by $0.7$-$3.8$ points, and achieves $1.16$-$1.59\times$ higher intelligence efficiency. The learned policy also transfers to new agent configurations introduced only at evaluation time, supporting the extensibility of agentic orchestration.