Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Refining Minimax Regret for Unsupervised Environment Design
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Bayesian level-perfect minimax regret (BLP), a refinement of minimax regret for unsupervised environment design, and ReMiDi, an algorithm that iteratively refines MMR policies so learning does not stagnate on irreducible-regret levels.
Problem
Regret-based unsupervised environment design reaches minimax regret policies, but when levels have irreducible regret the adversary keeps sampling those levels and learning stagnates on other reducible levels (regret stagnation).
Approach
Iteratively solve refined minimax regret games: after reaching MMR, restrict later adversaries to levels whose trajectories are distinguishable from previous MMR levels, and update the policy only on those trajectories. The resulting Bayesian level-perfect MMR policy keeps MMR guarantees while improving worst-case regret on the remaining levels.
Key results
- On Brax robotics, ReMiDi reaches 257 on Ant, 321 on Cheetah, 193 on Hopper and 344 on Walker, versus about -50 to 148 for PLR^perp and minimax return.
- In the lever game, PLR^perp solves invisible-answer levels at about 1/64 (~0.015) while ReMiDi also solves visible-answer levels perfectly, which PLR^perp fails at.
- In the tabular irreducible-regret setting, regret-based UED converges to sampling only the highest-regret levels and gets suboptimal regret on others, while ReMiDi reaches optimal regret on all levels.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ReMiDi instead of PLR⊥ | Brax Ant · Ant (Brax) | return: -50 ± 2 -> 257 ± 35 | Helped |
| Use ReMiDi instead of Minimax Return | Brax Ant · Ant (Brax) | return: -49 ± 4 -> 257 ± 35 | Helped |
| Use ReMiDi instead of PLR⊥ | Brax Cheetah · Cheetah (Brax) | return: -19 ± 14 -> 321 ± 16 | Helped |
| Use ReMiDi instead of Minimax Return | Brax Cheetah · Cheetah (Brax) | return: -16 ± 3 -> 321 ± 16 | Helped |
| Use ReMiDi instead of PLR⊥ | Brax Hopper · Hopper (Brax) | return: 67 ± 19 -> 193 ± 2 | Helped |
| Use ReMiDi instead of Minimax Return | Brax Hopper · Hopper (Brax) | return: 86 ± 15 -> 193 ± 2 | Helped |
| Use ReMiDi instead of PLR⊥ | Brax Walker · Walker (Brax) | return: 126 ± 68 -> 344 ± 21 | Helped |
| Use ReMiDi instead of Minimax Return | Brax Walker · Walker (Brax) | return: 148 ± 67 -> 344 ± 21 | Helped |
| Train with ReMiDi rather than regret-based UED | Tabular UPOMDP with shared observations and irreducible regret · Six tabular trajectories | regret | Helped |
| Train with ReMiDi rather than PLR⊥ | T-maze and normal-maze setting · Held-out test mazes | solve rate | Helped |
| Train with ReMiDi rather than PLR⊥ | Blindfold maze setting · Held-out test mazes | solve rate | Helped |
| Train with ReMiDi rather than PLR⊥ | Lever game, visible-answer levels · Visible-answer levels | solve rate | Helped |
Surprising findings
- Minimax regret UED can satisfy the MMR objective while the resulting policy is effectively random on levels where the answer is visible (lever game).
- Being minimax regret on each of two local subgames does not make a policy minimax regret over the whole game (temporal inconsistency of local regret).
Limitations
- Theoretical guarantees hold only at Nash equilibrium, which is not guaranteed to be reached in practice.
- ReMiDi requires knowing the likelihood of trajectories under sets of environments a priori, which may be impractical.
- Requires multiple outer-loop iterations (approximated with a small number, e.g. 4), and the experiments are designed to exhibit irreducible regret, which is not common in prior benchmarks.
Experimental setup
Datasets: MiniGrid mazes (procedurally generated T-mazes and standard mazes) lever game Brax robotics environments (Ant, Half-Cheetah, Hopper, Walker) tabular one-step game
Benchmarks: MiniGrid held-out test mazes (SixteenRooms, Labyrinth, StandardMaze, etc.) Brax locomotion with no disturbances lever game visible/invisible answer evaluation tabular regret
Metrics: solve rate regret return
Baselines: PLR^perp Robust PLR Minimax return (PLR^perp with negative return score) PAIRED
Builds on: PLR PAIRED JaxUED minimax regret UED
Closest papers by meaning
- Marginal Benefit Driven RL Teacher for Unsupervised Environment Design (AAAI 2025 · similarity 0.90)
- No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery (NeurIPS 2024 · similarity 0.90)
- Improving Regret Approximation for Unsupervised Dynamic Environment Generation (NeurIPS 2025 · similarity 0.90)
- Policy-Regret Minimization in Markov Games with Function Approximation (ICML 2025 · similarity 0.89)
- Adversarial Environment Design via Regret-Guided Diffusion Models (NeurIPS 2024 · similarity 0.89)
- A Minimaximalist Approach to Reinforcement Learning from Human Feedback (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.