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

Abstract

Agentic orchestration enables multiple autonomous agents to solve complex tasks through adaptive decomposition, delegation, and execution. However, existing orchestrators often rely on hand-crafted logic and prompting strategies, limiting adaptation and generalization across tasks and executor configurations. We propose E${}^3$-Orch, a reinforcement learning framework for effective, efficient, and extensible agentic orchestration based on a milestone-plan-act workflow. Instead of planning all subtasks upfront, E${}^3$-Orch organizes execution around milestones, a mid-level abstraction that scopes planning around meaningful intermediate objectives and allows orchestration decisions to adapt as execution progresses. For each milestone, the orchestrator builds a dependency-aware plan, assigns subtasks to suitable executors, and executes independent subtasks in parallel. We train the orchestration policy from execution feedback, using milestone and plan decisions as units for fine-grained credit assignment. Tree-structured rollouts compare alternative decisions under shared execution histories, while complementary rewards optimize task performance, execution cost, and planning completeness, including an uncertainty-aware performance reward for stochastic downstream outcomes. Across seven benchmarks, E${}^3$-Orch achieves the best task performance under multiple executor configurations, improving over the strongest baselines by $0.7$--$3.8$ points and delivering $1.16$--$1.59\times$ higher intelligence efficiency. The learned policy also transfers to unseen executor configurations introduced only at evaluation time, supporting extensible agentic orchestration.

arXiv commentWork in progress