mlsanityData to 14 Oct 2026

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

arXiv 2410.16517 ↗First posted 21 Oct 2024cs.LG cs.AIcited by 2

On the map: Deep reinforcement learning methods → Interpretable and logic-guided RL

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).

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.

Builds on

32 of 72 references.

References · 32

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  2. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,427
  3. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,240
  4. 2017Distilling a Neural Network Into a Soft Decision Treecited by 236
  5. 2013The Complexity of Decentralized Control of Markov Decision Processescited by 231
  6. 2018Programmatically Interpretable Reinforcement Learningcited by 193
  7. 2018Verifiable Reinforcement Learning via Policy Extractioncited by 177
  8. 2015ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and Rcited by 172
  9. 2017Learning Discrete Representations via Information Maximizing Self-Augmented Trainingcited by 149
  10. 2015Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction modelcited by 140
  11. 2019Optimal Sparse Decision Treescited by 105
  12. 2018Toward Interpretable Deep Reinforcement Learning with Linear Model U-Treescited by 65
20 more
  1. 2022A Policy-Guided Imitation Approach for Offline Reinforcement Learningcited by 59
  2. 2021Scalable Bayesian Inverse Reinforcement Learningcited by 56
  3. 2017Iterative Random Forests to detect predictive and stable high-order interactionscited by 42
  4. 2019Conservative Q-Improvement: Reinforcement Learning for an Interpretable Decision-Tree Policycited by 29
  5. 2020A Scalable MIP-based Method for Learning Optimal Multivariate Decision Treescited by 23
  6. 2020What Did You Think Would Happen? Explaining Agent Behaviour Through Intended Outcomescited by 20
  7. 2023MAC-PO: Multi-Agent Experience Replay via Collective Priority Optimizationcited by 20
  8. 2024Modeling Other Players with Bayesian Beliefs for Games with Incomplete Informationcited by 17
  9. 2020CDT: Cascading Decision Trees for Explainable Reinforcement Learningcited by 15
  10. 2020Inverse Active Sensing: Modeling and Understanding Timely Decision-Makingcited by 12
  11. 2022Value Functions Factorization with Latent State Information Sharing in Decentralized Multi-Agent Policy Gradientscited by 12
  12. 2022A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functionscited by 12
  13. 2023Real-time Network Intrusion Detection via Decision Transformerscited by 12
  14. 2017An Optimization Approach to Learning Falling Rule Listscited by 10
  15. 2023RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learningcited by 8
  16. 2023AccMER: Accelerating Multi-Agent Experience Replay with Cache Locality-aware Prioritizationcited by 7
  17. 2023RIDE: Real-time Intrusion Detection via Explainable Machine Learning Implemented in a Memristor Hardware Architecturecited by 7
  18. 2024Collaborative AI Teaming in Unknown Environments via Active Goal Deductioncited by 6
  19. 2024Bayesian Optimization through Gaussian Cox Process Models for Spatio-temporal Datacited by 5
  20. 2023ConcaveQ: Non-Monotonic Value Function Factorization via Concave Representations in Deep Multi-Agent Reinforcement Learningcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026MINT: Minimal Information Neuro-Symbolic Tree for Objective-Driven Knowledge-Gap Reasoning and Active Elicitationcited by 4
  2. 2026Retaining Suboptimal Actions to Follow Shifting Optima in Multi-Agent Reinforcement Learningcited by 3

Similar, not cited

Close in wording, no citation either way

  1. 2024Optimizing Interpretable Decision Tree Policies for Reinforcement Learning
  2. 2024Solving Offline Reinforcement Learning with Decision Tree Regression
  3. 2026ORCAID: Oblique Rule-Based Continuous-Action Interpretation for Deep RL Policies
  4. 2024Putting the Iterative Training of Decision Trees to the Test on a Real-World Robotic Task
  5. 2024Interpretable Modeling of Deep Reinforcement Learning Driven Scheduling
  6. 2023Optimal Decision Tree Policies for Markov Decision Processes
  7. 2024Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization
  8. 2024BET: Explaining Deep Reinforcement Learning through The Error-Prone Decisions