Summary
ACCEL (Adversarially Compounding Complexity by Editing Levels) merges the two UED lineages: the regret-based curators (PAIRED, Robust PLR) that have robustness guarantees but struggle to find good levels in large design spaces, and the evolutionary open-ended methods (POET, MCC) that compound complexity but need domain heuristics and huge compute. ACCEL keeps a Robust-PLR buffer of high-regret levels and, instead of only sampling random new levels, makes small edits (mutations) to replayed levels and keeps the edits that are still high-regret. Curricula start simple and compound in complexity matched to the agent, with no environment-specific heuristics. In MiniHack lava grids, MiniGrid mazes and BipedalWalker terrains it beats PLR⊥ and PAIRED, reaching POET-level terrain complexity on a single GPU with under 0.05% of POET’s environment samples.
Key points
- Algorithm: sample a level from the PLR buffer (or a random one), roll out the student, score regret; then edit high-regret levels (add/remove a wall, tweak terrain) and re-score the edits, adding those that remain high-regret to the buffer. Levels are only added to the buffer if they have high regret, so editing is filtered by the same criterion.
- Evolution supplies the search (edits from previously useful levels); regret supplies principled selection and inherits the DCD minimax-regret guarantee.
- Emergent complexity across three domains: mazes fill with structure, lava grids grow, BipedalWalker terrain gets rougher — without hand-written difficulty schedules.
- Outperforms DR, PAIRED, PLR⊥ on held-out human-designed levels and on a BipedalWalker generalization suite.
- Compute: comparable level complexity to POET with <0.05% of POET’s environment interactions, single GPU.
- Future work: richer editors (NCA, generative-model latents), extinction events, explicit diversity objectives (Enhanced POET’s novelty), co-adapting the agent’s configuration.
Relevance
- Open-Endedness — the synthesis point of the UED thread: bridges Paired Open-Ended Trailblazer (POET)‘s evolutionary compounding with Replay-Guided Adversarial Environment Design’s regret curation; the strongest practical UED baseline in the note’s reading list.
- Unsupervised Environment Design — home concept since 2026-09-10
Notes
(batch ingest; no notes yet)