Research map / Multi-agent systems and games / Cooperative multi-agent RL
RGMDT: Return-Gap-Minimizing Decision Tree Extraction in Non-Euclidean Metric Space
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 RGMDT, which extracts multi-agent decentralized decision trees from a DRL policy by iteratively clustering observations under a cosine-distance (non-Euclidean) loss, with a closed-form bound on the return gap.
Problem
Extracting interpretable decision-tree policies from pretrained deep RL policies with a quantitative guarantee on expected return, especially for multi-agent decentralized settings where prior methods (VIPER, MAVIPER) are heuristic or sample-based.
Approach
Bounds the return gap between an oracle policy and a size-L decision tree by the average cosine distance between action-value vectors within each leaf cluster, recasts DT construction as non-Euclidean clustering of observations with actions as labels, and grows agents' trees iteratively with action-values revised conditioned on other agents' current trees.
Key results
- On D4RL Hopper with 80,000 samples and 64 nodes, RGMDT achieved 776.70 ± 150.18 versus 448.85 for CART and 452.89 for RF.
- In the ablation, removing the iteratively-grow-DT process dropped mean reward from 41.95 to 16.29 and removing the non-Euclidean clustering module led to task failure.
- With 4 or more leaf nodes, RGMDT's performance in multi-agent tasks reportedly approaches the expert RL policy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RGMDT instead of the strongest listed baseline, CART | Decision-tree extraction on D4RL Hooper · D4RL Hooper, 80,000 samples, 40 nodes | reward: 443.47 ± 153.49 -> 567.27 ± 160.47 | Helped |
| use RGMDT instead of the strongest listed baseline, RF | Decision-tree extraction on D4RL Hooper · D4RL Hooper, 80,000 samples, 64 nodes | reward: 452.89 ± 134.76 -> 776.70 ± 150.18 | Helped |
| use RGMDT instead of the strongest listed baseline, CART | Decision-tree extraction on D4RL Hooper · D4RL Hooper, 800,000 samples, 40 nodes | reward: 458.47 ± 131.48 -> 467.27 ± 134.78 | Helped |
| use RGMDT instead of the strongest listed baseline, RF | Decision-tree extraction on D4RL Hooper · D4RL Hooper, 800,000 samples, 64 nodes | reward: 489.92 ± 71.69 -> 458.70 ± 98.07 | Hurt |
| replace the SVM hyperplane with CART splits (ablation) | RGMDT · Multi-agent task | mean reward: 41.95 ± 3.08 -> 26.16 ± 3.74 | Hurt |
| replace the SVM hyperplane with ET splits (ablation) | RGMDT · Multi-agent task | mean reward: 41.95 ± 3.08 -> 36.79 ± 2.15 | Hurt |
| replace the SVM hyperplane with RF splits (ablation) | RGMDT · Multi-agent task | mean reward: 41.95 ± 3.08 -> 21.59 ± 3.81 | Hurt |
| replace the SVM hyperplane with GBDT splits (ablation) | RGMDT · Multi-agent task | mean reward: 41.95 ± 3.08 -> 37.76 ± 2.42 | Hurt |
| add the non-Euclidean clustering module (ablation) | RGMDT · Multi-agent task | mean reward: 23.85 ± 2.23 -> 41.95 ± 3.08 | Helped |
| add the iteratively-grow-DT process (ablation) | RGMDT · Multi-agent task | mean reward: 16.29 ± 4.72 -> 41.95 ± 3.08 | Helped |
Surprising findings
- Replacing the SVM hyperplane with ET or GBDT still completes the multi-agent task, while CART and RF fail.
Limitations
- Splits are linear (SVM hyperplanes), and the authors note that regression trees for continuous spaces are future work.
- Bound assumes finite observation and action spaces; continuous cases are only sketched.
- Experiments are limited to maze tasks and a single D4RL Hopper instance with 3-5 seeds.
Experimental setup
Datasets: D4RL Hopper custom maze target-chasing tasks (MPE predator-prey style)
Benchmarks: D4RL Hopper maze single-agent tasks multi-agent predator-prey maze tasks
Metrics: mean episode reward task completion steps achieved reward with standard deviation
Baselines: CART Random Forest Extra Trees Gradient Boosting DT MAVIPER
Builds on: VIPER MAVIPER regularized information maximization support vector machines CART
Closest papers by meaning
- Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization (ICLR 2025 · similarity 0.87)
- ORCAID: Oblique Rule-Based Continuous-Action Interpretation for Deep RL Policies (NeurIPS 2026 · similarity 0.87)
- RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learning (AAAI 2024 · similarity 0.86)
- SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes (NeurIPS 2025 · similarity 0.85)
- SkillTree: Explainable Skill-Based Deep Reinforcement Learning for Long-Horizon Control Tasks (AAAI 2025 · similarity 0.85)
- RICE: Breaking Through the Training Bottlenecks of Reinforcement Learning with Explanation (ICML 2024 · similarity 0.84)
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.