First Things First: Priority Scheduling with On-Demand Skill Evolution in Minecraft

As autonomous agents move toward practical use, reliably handling long-horizon, complex tasks remains a key challenge. Minecraft provides a controllable open-world testbed, yet existing benchmarks largely focus on isolated goals such as finding, collecting, or crafting, leaving the changing priorities and capability gaps of complex execution underexplored. Open-world agents may fail because they execute the wrong available behavior at the wrong time, or because they lack a reliable capability for a necessary subgoal. To probe this gap, we introduce seven long-horizon tasks, such as preparing from scratch and defeating a zombie, or repeatedly chopping trees until 100 logs are collected, and evaluate agents by both task success and completion efficiency. We introduce PRIME (Priority-guided Runtime Scheduling with Importance-aware Missing-skill Evolution), which couples runtime priority scheduling with selective skill evolution. PRIME maintains a priority-based schedule that adapts to task state and progress, while task-critical missing skills trigger validated evolution for future reuse. Across seven Minecraft tasks and three high-level model families, PRIME consistently improves task success and completion efficiency, with the largest gains on long-horizon and dynamically changing tasks.