# RGMDT: Return-Gap-Minimizing Decision Tree Extraction in Non-Euclidean Metric Space

arXiv: https://arxiv.org/abs/2410.16517 · HTML: https://mlsanity.com/paper/2410.16517/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 32 of its 72 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

## Builds on (most cited first, 30 of 32)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [Distilling a Neural Network Into a Soft Decision Tree](https://mlsanity.com/paper/1711.09784/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and R](https://mlsanity.com/paper/1508.04409/) (2015)
- [Learning Discrete Representations via Information Maximizing Self-Augmented Training](https://mlsanity.com/paper/1702.08720/) (2017)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Toward Interpretable Deep Reinforcement Learning with Linear Model U-Trees](https://mlsanity.com/paper/1807.05887/) (2018)
- [A Policy-Guided Imitation Approach for Offline Reinforcement Learning](https://mlsanity.com/paper/2210.08323/) (2022)
- [Scalable Bayesian Inverse Reinforcement Learning](https://mlsanity.com/paper/2102.06483/) (2021)
- [Iterative Random Forests to detect predictive and stable high-order interactions](https://mlsanity.com/paper/1706.08457/) (2017)
- [Conservative Q-Improvement: Reinforcement Learning for an Interpretable Decision-Tree Policy](https://mlsanity.com/paper/1907.01180/) (2019)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [What Did You Think Would Happen? Explaining Agent Behaviour Through Intended Outcomes](https://mlsanity.com/paper/2011.05064/) (2020)
- [MAC-PO: Multi-Agent Experience Replay via Collective Priority Optimization](https://mlsanity.com/paper/2302.10418/) (2023)
- [Modeling Other Players with Bayesian Beliefs for Games with Incomplete Information](https://mlsanity.com/paper/2405.14122/) (2024)
- [CDT: Cascading Decision Trees for Explainable Reinforcement Learning](https://mlsanity.com/paper/2011.07553/) (2020)
- [Inverse Active Sensing: Modeling and Understanding Timely Decision-Making](https://mlsanity.com/paper/2006.14141/) (2020)
- [Value Functions Factorization with Latent State Information Sharing in Decentralized Multi-Agent Policy Gradients](https://mlsanity.com/paper/2201.01247/) (2022)
- [A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions](https://mlsanity.com/paper/2210.06635/) (2022)
- [Real-time Network Intrusion Detection via Decision Transformers](https://mlsanity.com/paper/2312.07696/) (2023)
- [An Optimization Approach to Learning Falling Rule Lists](https://mlsanity.com/paper/1710.02572/) (2017)
- [RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2308.03358/) (2023)
- [AccMER: Accelerating Multi-Agent Experience Replay with Cache Locality-aware Prioritization](https://mlsanity.com/paper/2306.00187/) (2023)
- [RIDE: Real-time Intrusion Detection via Explainable Machine Learning Implemented in a Memristor Hardware Architecture](https://mlsanity.com/paper/2311.16018/) (2023)
- [Collaborative AI Teaming in Unknown Environments via Active Goal Deduction](https://mlsanity.com/paper/2403.15341/) (2024)

## Built on by (most cited first, 2 of 2)

- [MINT: Minimal Information Neuro-Symbolic Tree for Objective-Driven Knowledge-Gap Reasoning and Active Elicitation](https://mlsanity.com/paper/2602.05048/) (2026)
- [Retaining Suboptimal Actions to Follow Shifting Optima in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.17062/) (2026)

## Abstract (arXiv)

Deep Reinforcement Learning (DRL) algorithms have achieved great success in solving many challenging tasks while their black-box nature hinders interpretability and real-world applicability, making it difficult for human experts to interpret and understand DRL policies. Existing works on interpretable reinforcement learning have shown promise in extracting decision tree (DT) based policies from DRL policies with most focus on the single-agent settings while prior attempts to introduce DT policies in multi-agent scenarios mainly focus on heuristic designs which do not provide any quantitative guarantees on the expected return. In this paper, we establish an upper bound on the return gap between the oracle expert policy and an optimal decision tree policy. This enables us to recast the DT extraction problem into a novel non-euclidean clustering problem over the local observation and action values space of each agent, with action values as cluster labels and the upper bound on the return gap as clustering loss. Both the algorithm and the upper bound are extended to multi-agent decentralized DT extractions by an iteratively-grow-DT procedure guided by an action-value function conditioned on the current DTs of other agents. Further, we propose the Return-Gap-Minimization Decision Tree (RGMDT) algorithm, which is a surprisingly simple design and is integrated with reinforcement learning through the utilization of a novel Regularized Information Maximization loss. Evaluations on tasks like D4RL show that RGMDT significantly outperforms heuristic DT-based baselines and can achieve nearly optimal returns under given DT complexity constraints (e.g., maximum number of DT nodes).