Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs¶

🕒 Published (v1): 2025-11-16 17:48 UTC · Source: Arxiv · Venue: AAAI · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

ATLAS extends Unsupervised Environment Design (UED) beyond fixed tasks to jointly co-design tasks and levels, training agents that generalize across novel task-level combinations. By framing tasks as reward machines and applying regret-based curriculum generation to both dimensions simultaneously, ATLAS produces solvable yet progressively challenging training problems. It vastly outperforms domain randomization, which essentially fails when only ~2.7% of randomly sampled task-level pairs are solvable.

Problem¶

Prior UED methods generate curricula over environment levels but assume a fixed, predetermined task. Training general instruction-following agents requires co-designing both tasks and levels, since random independent sampling produces mostly unsolvable pairs (e.g., a task requiring a red door in a level with no doors). No method existed to automatically generate joint autocurricula that remain solvable while scaling difficulty across both dimensions.

Method¶

ATLAS augments regret-based UED (PLR⊥, ACCEL) to operate over task-level pairs jointly. Tasks are represented as reward machines (RMs)—finite-state machines with propositional transitions—encoded via a GNN. The policy network concatenates GNN-derived RM-state embeddings with CNN observation features, passed through an RNN for history. The UED loop maintains a buffer of high-regret task-level pairs scored by MaxMC regret approximation. ACCEL extends this with three mutation types: (1) level edits (add/remove rooms, objects, agent position), (2) task edits (switch propositions, add/remove RM states), and (3) hindsight edits (create sub-problems from intermediate rollout states—either truncating to a simpler prefix or starting from a reached environment state). Mutation sequences of 7–10 edits are applied to buffer problems to explore the neighborhood of high-regret problems. The full system is trained end-to-end with PPO.

Key Contributions¶

ATLAS framework: first UED method generating joint autocurricula over both tasks (reward machines) and levels (Minigrid environments).
GNN-conditioned policy: handles variable RM topologies, enabling generalization across unseen task structures.
Structure-aware task mutations: RM-level edits (proposition switching, state addition/removal) and hindsight relabeling that exploit task structure to accelerate curriculum emergence.
Evaluation suite: 150 hand-designed task-level problems targeting low-solvability regimes, long-horizon planning (MYOPIC, PATROL, CHOICE scenarios), and implicit subgoals.
ACCEL-0 result: demonstrates that rich curricula and strong policies can emerge purely from mutations of maximally simple initial problems, without any initial diversity.

Results¶

Independent sampling yields only 2.7% solvable problems per batch; PLR⊥ and ACCEL buffer solvability grows to near 100% over training, while DR remains stuck on predominantly unsolvable problems.
ACCEL variants consistently outperform PLR⊥ on worst-case CVaR (especially low-α), while both substantially outperform DR, which solves almost no problems under independent sampling.
Under level-conditioned sampling (83.4% solvability), DR improves to match PLR⊥/ACCEL at ≈91.6% solve rate, confirming the gap is driven by solvability scarcity.
Disabling either task or level edits in ACCEL significantly reduces performance; single-edit sequences cause a ≈40% drop, 3-edit sequences a ≈15% drop; 20-edit sequences have minimal effect (≈2% variation).
Random walk-based task sampler (richer temporal dependencies) reduces solve rates on the hand-designed set by ≈35% versus sequential sampler.

Limitations¶

Evaluation restricted to Minigrid/BabyAI environments; scalability to richer domains (e.g., Craftax) is unverified.
Solvability is not guaranteed even with level-conditioned sampling; checking solvability during generation is intractable in general.
Hindsight edits are rare in practice (require rollouts ending in intermediate RM states and can only appear as the first edit), leaving potential curriculum signal unused.
Regret approximations (MaxMC) are known to correlate with success rate rather than true regret; ATLAS inherits this limitation from upstream UED.
Only RM-based task formalisms are evaluated; extension to LTL, hierarchical RMs, or natural language task conditioning is left to future work.

Relevance to Agentic AI / LLM Agents¶

ATLAS directly addresses instruction-following generalization—a core capability for agentic systems that must execute diverse tasks in novel environments. The reward machine formalism provides a structured, unambiguous analog to natural language instructions (with explicit mappings from NL to RMs referenced in the paper), making the curriculum generation pipeline potentially composable with LLM-based task generators like EUREKA or OMNI-EPIC. The joint task-level co-design principle is broadly relevant to any agent training regime where the combinatorial space of goals × environments makes uniform sampling intractable. The ACCEL-0 result—strong generalization emerging from mutation alone—suggests a scalable alternative to LLM-driven open-ended task generation that requires no learned or prompted task generator.