RGMDT: Return-Gap-Minimizing Decision Tree Extraction in Non-Euclidean Metric Space
Authors: Jingdi Chen
Hanhan Zhou
Yongsheng Mei
Carlee Joe-Wong
Gina Adam
Nathaniel D. Bastian
Tian Lan
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-agent Reinforcement Learning
Decision Tree
Explainable AI
Primary area: reinforcement_learning

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

RGMDT: Return-Gap-Minimizing Decision Tree Extraction in Non-Euclidean Metric Space
Jingdi Chen
Hanhan Zhou
The George Washington University j jingdic@guu. edu edu
The George Washington University hanhan@gwu. edu
Yongsheng Mei
Carlee Joe-Wong
The George Washington University yameiCgwu. edu
Carnegie Mellon University cjoewong@andrew. cmu edu
Gina Adam
Nathaniel D. Bastian
The George Washington University ginaadam@gvu.edt edu
United States Military Academy
nathaniel. bas.eeabbaatttteeeppoontttt edu
Tian Lan
The George Washington University tlan@gwu. edu
Abstract
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 heuristie designs which do not provide any quantitative guarantees on the expected return. In this paper, establish expert policy and an optimal decision tree policy. This enables us to recast the DT extraction problem into 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 the return gap clustering loss. Both the algorithm and the upper bound are extended to multi-agent decentralized DT procedure guided by an action-value function
upper bound the return gap between the oracle
extractions by iterativelygrrow conditioned on the current DT's of other agents. Further, we propose the Return- Cap-Minimizatioon Decision Tree (RGMDT) algorithm, which surprisingly simple design and is integrated with reinforcement learning through the utilization of novel Regularized Information Maximization loss. Evaluations on tasks like D4RL show that RGMDT significantly outperforms heuristic DTT-based baselines and can achieve nearly optimal returns under given DT complexity constraints (e.g.. maximum number of DT nodes).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Deep Reinforcement Learning (DRL) has significantly advanced real-world applications in var- ious domains 5 I2
29 44 69 ZT]. However, the black-box nature of DRL's deep neural networks, with their multi-layered structures and millions of parameters, makes them largely uninterpretable. This lack of interpretability is particularly problematic in safety- critical sectors such as healthcare and aviation, where clarity in machine decision-making is cru- 45 51].
13
T6
T7
cial [4 15 27
Decision trees (DTs) address this problem by supporting rules and decision lists that enhance human understanding M
56]. However, there are two main challenges to applying DTs in DRL: (1) DTss extracted from DRL often lack performance guarantees [2] 22) There have been imitation learning-type approaches that train DT's with samples drawn from the trained DRL policy [3] but the return gap is characterized in terms of number of samples needed and does not apply to DTs with arbitrary size constraints (e.g., on the maximum number of nodes L.). (2) Although learning DT policies for interpretabilityy has been investigated in the single-agent RL. setting 37
35
36
38
42
55 58
it is
under-explored in the multi-agent setting, except for centralized methods like MAVIPER [88] which
lacks a performance guarantee. In multi-agent, decentralized settings where rewards are jointly determined by all agents' local DTs, any changes in one agent's s DT will impact the optimality of other agents' DT'. The return gap for such decentralized DT's has not been considered.
In this paper, we propose DT extraction framework, a Return Saauuun-ap---aann Mia-Miiimization Decision Tree (RGMDT) algorithm, that is proven to achieve foored-form guarantee on the expected return gap between given RL policy and the resulting DT policy. Our key idea is that each decision path of the extracted DTT maps a subset of observations to an action attached to the leaf node. Thus, constructing a DT can be considered an iterative clustering problem of the observations into different decision paths, with actions at leaf nodes as labels. Since the action-value function Q(o, a) represents the potential future return, it can be leveraged to obtain a return gap bound for the process. We show that it recasts the DT extraction problem as a non-Euclidean clustering with respect to loss defined using (o, a). Due to its iterative structure, RGMDT supports an iterative algorithm to generate return-gap-man gap-miiimizing DTs of arbitrary size constraints.
Further, we extend our algorithm multi-agent settings and provide a performance bound on the return gap. A naïve approach that simply converts each agent's (decentralized) policy into local DT cannot ensure global optimality of the resulting return since the reward is jointly determined by the DTss constructed for all agents. We develop an iteratively-grow identifies the best step to grow the DT of each agent, conditioned on the current DTss of other agents (by revising the resulting action-value function) until the desired complexity is reached. Thus, the impact of decentralized DT's on the joint reward is captured during this process. The method ensures that we learn decentralized DTs yet also guarantees return gap.
process, which iteratively
More precisely, we show that the problem is recast into a non-Euclidean clustering problem in the observation space with n agents. Each agent j computes an updated action-value function by conditioning it on other agents' current DTs (thus capturing the impact of their DT constructions on each other). Then, guided by this updated adding another label (i.e., decision path and corresponding leaf node) by a clustering function T [T lo,, T-+), Vil, which is conditioned on its local observations 0; and the DT policies of other agents T-;- The process continues iteratively across all agents until their decentralized DTss reach the desired size constraints. To analyze the resulting return gap, we show that the difference between the given DRL policy and the DT's can be characterized using a Policy Change Lemma, relying on the average distance between joint action values in each cluster (i.e., decision path). Intuitively, if the observations following the same decision path and arriving at the same leaf node likely maximized with the same action, the DT policy would have small return gap with the DRL policy x² We show that the return gap is bounded by O(v// respect to the maximum number of leaf nodes L of the DT, the number of agents n, the highest action- value Qmax and the average cosine- distance between joint action-value vectors corresponding to the same clusters. The result allows us to minimize this upper bound to find the optimal DTs.
value-auuututfon agent i grows its DT by
+ 1) 1)QQmax)) with
The main contributions are: (1). We quantify the return gap between an oracle DRL policy and its extracted DTs via an upper bound with respect to the DT size constraints. (2). We propose RGMDT, an algorithm that constructs multi-agent decentralized DTs of arbitrary sizes by minimizing the upper

---

bound of the return gap. Instead of drawing samples from the DRL policy for DT learning, RGMDT recasts the problem as an iterative non- Sun-Eucide clustering problem of the observations into different decision paths, with actions at leaf nodes as labels. (3). Rather than generating DT and subsequently applying pruning algorithms to achieve the desired complexity, the RGMD'T framework constructs DT's of any given size constraint while minimizing the upper bound of the resulting expected return gap. (4), We show that RGMDT significantly outperforms baseline DT algorithms and can be applied to complex tasks like D4RL with significant improvement.
The remainder of this paper organized as follows. Section 2 reviews related work on decision trees and their integration with reinforcement learning, with focus on interpretability and multi-agent systems, Section 3 introduces our problem formulation and defines the return gap. In Section we present the theoretical results. recasting return gap minimization as clustering in non- non-Euclidean space, and deriving bounds for both single-agent and multi-agent settings. Section 5 details the construction of SVM-based decision trees and the iteratively growing framework for minimizing return gaps, with pseudocode in the appendix. Section 6 describes the experimental setup and presents empirical results. Finally, Section 7 concludes with a summary of contributions and future directions.
2 Related Work
Effort on Interpretability for Understanding Decisions. To enhance interpretability in decision- making models, one strategy involves crafting interpretable reward functions within inverse reinforce- ment learning (IRL), as suggested by [T0] 67 68]. This approach offers insights into the underlying objectives guiding the agents' decisions. Agent behavior has been conceptualized as showing pref- erences for certain counterfactual outcomes 77, or as valuing information differently when under time constraints 34 However, extracting policies through black-box reinforcement learning (RL) algorithms often conceals the influence of observations on the selection of actions. An alternative to directly define the agent's policy function with an interpretable framework. Reinforcement learning policies have thus been articulated using a high-level programming language [60]. or by framing explanations around desired outcomes (66,, facilitating a more transparent understanding of decision-making processes.
Interpretable RL via Decision Tree-based models. Since their introduction in the 1960s, DTs have been crucial for interpretable supervised learning 47 50 [3]. The CART algorithm 8, established in 1984, is foundational in DT methodologies and underpins Random Forests (RF) p and Gradient Boosting (GB) [23], which are benchmarks in predictive modeling. These techniques are central to platforms like ranger and seikit-learn and continue to evolve, seen in the iterative random forest, which explores stable interactions in data [4 52, 64 70. To interpret an RL agent, Frosst et al (25) explain the decisions made by DRL policies by using trained neural network to create soft decision trees. Coppens et al. (19] propose distilling the RL policy into a differentiable DT by imitating a pre-trained policy. Similarly, Liu et al. (39 apply an imitation learning framework to the Q-value function of the RL agent. They also introduce Linear Model U-trees (LMUTss), which incorporate linear models in the leaf nodes. Silva et al. (57) suggest using differentiable DTs directly as function approximators for either the Q function or the policy in RL. Their approach includes a discretization process and rule list tree structure to simplify the DTss and enhance interpretabilityy Additionally, Bastani et al. (3] propose the VIPER method, which distills policies as neural networks into DT policy with theoretically verifiable capabilities that follow the Dataset Aggregation (DAGGER) method [54], specifically for imitation learning settings and nonparametric DTs. Ding et al. 20 try to solve the instability problems when using imitation learning with tree-based model generation and apply representation learning on the decision paths to improve the decision tree-based explainable RL results, which could achieve better performance than soft DTs. Milani et al. extend VIPER methods into multi-agent scenarios [48] in both centralized and decentralized ways, they also summarize paper about the most recent works in the fields of explainable AI (artificial intelligence) [49], which confirms the statements that small DTs are considered naturally interpretable.
However, traditional DT methods are challenging to integrate with RL due to their focus on cor- relations within training data rather than accounting for the sequential and long-term implications in dynamic environments. Imitation learning approaches have been explored in single-agent RL For instance, VIPER 3 trains DT's with samples from trained DRL policy, but its return gap depends on the number of samples needed and does not apply to DT's with arbitrary size constraints (c.g., maximum number of nodes L). DT algorithms remain under-explored in multi-agent
settings 42 55 58
3

---

settings, except for MAVIPER 48 that extends VIPER to multi- scenarios 46 while lacking performance guarantees and remaining a heuristic design.
3 Preliminaries and Problem Formulation
Dec-POMDP 6 models cooperative MARI,, where agents lack complete information about the environment and only have local observations. We formulate a Dec-POMDP as a tuple = (S, A, P. S2 n, R,R, 7), where S is the joint state space and A A x A2 x x A, is the joint action space, where a = (a1, 02. ......... ag) E A denotes the joint action of all agents. P(s'|s, a) S A S [0, 1] is the state transition function. 52 the observation space.
the total number of agents. R(s, a) S A + R is the reward function in terms of state and joint action a, and y the discount factor. Given a policy т, we consider the average expected return J(x) = lim E1 E> Re]. The goal of this paper is to minimize the return gap between the pre-trained RL policy providing action-values nt | (a, ...... 0n), Vi] and the DT policy T = [T:(o:) T-;), Vil where decision tree policies T-; = (T, = Ø5 0o( 14), Vj * i), where 1 g(o)), ) and the function g is the clustering function for observation oj. Define the return gap as: min J(x') J(T).
(1)
While the problem is equivalent to maximizing (T). the return gap can be analyzed more easily by contrasting T and x². We derive upper bound of the return gap and then design efficient clustering strategies to minimize it. We consider the discounted observation-bart state value and the corresponding action-value functions for the Dec-POMDP:
(*(()) = E
y
Re+i or 0, ~ T|, (o. = Ex Σ
Reti o, 0, a =a. (2)
1=0
where is the current time step. Re-writing the average expected return expectation of (T)
( lim ())(())>>(0))
where y is the initial observation distribution at time step 0, i.e., o(0) ~ μ. We will leverage this staue-value function V (o) and its corresponding action-value function Q* (o, a) to unroll the Dec-POMDP and derive closed-form upper-bound to quantify the return gap.
4 Theoretical Results and Methodology
We first recast the problem as clustering in a non-Euclidean Metric Space and then prove single- agent result. Then we expand the single-agent result to multi-agent settings. Since directly minimizing the return gap is intractable, we bound the performance of RGMDT with the return gap between the oracle policy x* [ (a: .o,........................... .. On). Vi] corresponding to obtaining the action-values Q and optimal decision tree policy T IT T,"),, where each Tr only have L nodes, and is the total number of agents. For simplicity, we V represent V and Q* to represent Q=', We assume that observation/action spaces defined in the Dec-POMDP tuple are discrete with finite observations and actions, i.e., [ < oo and |A| < oc. For Dec-POMDPs with continuous observation and action spaces, the results can be easily extended by considering -ista-de between action-valus functions and replacing summations with integrals, or sampling the action-valus functions an approximation.
Lemma 4.1. (Policy Change Lemma.) For any policies xt" and DT policy Th with L leaf nodes, the optimal expected average return gap is bounded by:
J(x²) - ---JJ(TT))))) Σ ΣΣN ao
QT (o at () "aoT (o). (1).
oml
(4)
(1) T P(o: o
where df'((o) (o) is the d-dicoounted visitation probability under decision tree Th and initial observa- tion distribution ps and Eo-t is a sum over all observations corresponding to the decision path from the parent node the leaf node I, where I indicates its class.

---

Proof Sketch. Our key idea is to leverage the state value function VT (o) and its corresponding
action-value function QT (o, a) in Eq.(2) unroll the Dec-POMDP from timestep t and onward. Detailed proof is provided in the Appendix.
Then define the action-value vector corresponding to observation oj ie.,
('(o,) (0, o,,. Vo-;l.
(5)
where o-j are the observations of all other agents and Q" (-)) is a vector of action-values weighted by marginalized visitation probabilities di (o (0,) and corresponding to different actions, i.e., (" [Q" o- x (ayl0;) a-3) - (o-j [0=](;]]] At the initial iteration step of the iteratively-grow- process, since we did not grow the DT for agent j yet, we use oracle policy r to give deterministic action aj argmax Q7(03, az) based on 0j for obtaining action-value
j-j,
vectors, and a-j are all possible actions for agents except for agent j. which makes ("(0,, o-j) vector where each entry corresponds to the full set of actions a across all agents except for agent j.
Next, constructing decision trees can be considered an iterative clustering problem of the observations into different decision paths 1; = g(oz), with actions at leaf nodes as labels. Then, the o, are divided into clusters, each labeled with the clustering label l to be used for constructing DT. We bound the policy gap between TG}) and T using the average cosine-distance of action-value vectors Q' (o,) corresponding to oj in the same cluster and its cluster center H (l) = Σo di(o)) (²
under each label I. Here do(0;) = dIT (o))/dff (1) is the marginalized probability of 0j in cluster I and o% (I) is the probability of label I under DT Th, and the environments initial observation distribution is represented by o(t = 0) ~ p. To this end, we let e(o,) Deo (Q= H()) be the cosine-distance between vectors Q (o,) and (I) and consider the average cosine-distance e across all clusters represented by different clustering labels | for one iteration of growing DT:
e Σ d5 Σ di(o,) e(o,),
(6)
The result is summarized in Thm.
Theorem 4.2. (Impact of Decision Tree Conversion.) Consider two optimal policies "t and Th obtained from the policy providing action-values and the DT, the optimal expected average return gap is bounded by:
J(T))) (
where Quaa is the maximum absolute action-value of ()();) in each cluster as Quax max 11;((;;)) and e is the average cosine-distance defined in Eq, L is maximum number of leaf nodes of the resulting DT.
Proof Sketch. We give an outline below and provide the proof in the Appendix.
Step 1: Recasting DT construction into Non-Eucho Con-Euclidean Clustering. Viewing the problem
clustering of oj. restrict policy Try (conditioned on 14j to take the same actions for all oj in the same cluster under the same label 1j. We perform clustering on the observation 0j within the observation space Q2 by grouping the corresponding aation-value vectors Q* (oj) in the action-value vector space 2,. using the -iittneeeetneee function Deo. as the clustering metric. We demonstrate that (L2, Deas) constitutes a -on-Euclidean Metric Space. The findings are detailed in Lemma 4.3 with the full proof provided in the Appendix.
Lemma 4.3. (Cosine Distance Metric Space Lemma.) Let 22 be a set of observations with associated vector representations I obtained through mapping fanction Q", and let Deas Ω2 22 IR be a distance function defined as:
-000)) i- -1Q)) (of))
Do ob)) = - (o))
(8)
where I denotes the cosine similarity. Then, the pair (St D Deas) forms a metric space. The proof is in Appendix.
5

---

Step 2: Rewrite the return gap in vector form. Re-writing the optimal expected average return gap derived in Policy Change Lemma 4.1 in vector terms using action-value vectors (o,) and an auxiliary maximization function & mmax (o))) that returns the largest component of vector (o)):
J S
Σ 12 E de(0)) & Piax ( (o;) T Pmax Σ de(oz) Q (o,))),, (9)
Step 3: Projecting action-value vectors toward cluster centers. By projecting (oz) toward (1), (0j) could be re-written as (o; = Q-(o)) + cos Oo.- Hi, then we could upper bound 2 Pmaz (Q" (o,)) by:
Pmax TamxxQQ'( (o;) S & max (cos (o; Hi) + & max (Q+
Taking sum over all oj in the cluster, have [ 2 max (cos Oo, Hii 2 mmax (Ht), since the projected components cos Oo,- Hy should add up to exactly Hi. To bound Eq. remains to bound the orthogonal components Q (0z).
(i
9 's return gap, it
Step 4: Deriving the upper bound w.r.t. cosine- distance. We derive upper bound the return gap by bounding the orthogonal projection errors using the average cosine distance within each cluster.
man (Q' (0,) S =(())())))mmm
(10)
Using the concavity of the square root with (q.(6). we derive the desired upper bound (TTT)) J(T()) I O(veQmaxx) for one iteration of growing the DT, then for I = log2 + 1) - 1 iterations (I is the depth of the DT), the upper bound O( e
1)]Qmxx)xx Here we assume that the DT is a perfectly balanced or full binary tree. If it is a complete binary tree, the number of iterations number of iterations is I = L - 1. Then we extend this upper bound to multi-agent settings in Thm.
log2 [L. . In the worst-case scenario of highly unbalanced tree, the
Theorem 4.4. In n-agent Dec-POMDA the return gap between policy n¹ corresponding to the obtained action-values and decision tree policy T conditioned on clustering labels is bounded by:
- ( 0 ((ve))/o, ( 1) - 1)nQmax))
(11)
Proof Sketch. Beginning from π² = [x] (ax 01 02..... . on), Vi], we can construct a sequence of policies, each replacing the conditioning on oj by constructed decision tree T, for 1 to j = n, one at a time. This will result in the decision tree policies TL = [T (oj, -=-;)]- Applying Thm. 4.2 for n times, we prove the upper bound between J(x*) and ((T2) for multi-agent scenarios. Remark 4.5. Thm. 4.4 holds for any arbitrary finite number of leaf nodes L. Furthermore, increasing reduces the average cosine distance (since more clusters are formed) and, consequently, a reduction in the return gap due to the upper bound derived in Thm.
5 Constructing SVM-based Decision Tree to Minimize Return Gaps
The result in Thm. inspires a iteratively-grov-DT framework RGMDD, which constructs mourn-gap-minimiziig multi-agent decentralized DTTs of arbitrary sizes. This because RGMDD grows a binary tree iteratively (in both single and multi-agent cases) until the desired complexity is reached. The method addressed two challenges: (1). RGMDT constructs the optimal DT that minimizes the return gap given the complexity of the DT (e.g., the number of the leaf nodes). (2). RGMDT addressed the scalability problems of multi-agent DT construction with provided theoretical guarantees. We summarize the pseudo-code in the Appendix.
Non-Euclidean Clustering Labels Generation. We approximate the non non- Euclidean clustering labels 1= for each agent using DNNs parameterized by & = {EI...., E..)............ Prior to growing the decision tree (DT) for each agent j. we sample minibatch of K₁ transitions X, from the replay buffer R, which includes iiservation-action-reaaas K2 most frequent observations o fz in X', and retrieve their associated actions using the trained
pairs from all agents. We then identify the top
policy n", forming set X-j. We combine these samples with (o,, x (o;))) from X, to form the

---

dataset D for training. The oracle critic networks, parameterized by w, compute the action-values for this dataset, approximating the vectors (² ). 9e, (o₂) updated by optimizing a Regularized
Information Maximization (RIM) loss function 32
K1
((ge,) - Σ ("
113 - 1-12- (m)) Hmmylo)),,
(12)
p= (E
the first term is Ducality-preservy encouraging action-value vectors close to each other to be grouped together. This is achieved using the cosine distance Doos to identify the K3 nearest neighbors of each action-value vector. The second term, the mutual information loss, quantifies the mutual information between the observation o, and the cluster label my. It aims to balance cluster size and clarity by evaluating the difference between the marginal entropy H (mg) and the conditional entropy H (m))o)))
clustering loss, which enhances the cohesion of clusters by
Single-agent DT Construction via Iterative Clustering. To grow a decision tree (DT) for agent j. each decision path of RGMDT maps subset of observations to an action attached to the leaf node (decision paths for different leaf node counts are visualized in Appendix). The process iteratively groups observations and assigns actions as labels at each path's s end. The main challenge is determining the optimal division of observations at each node and defining the split conditions. For each split, the RGMDT framework uses a sample matrix of observations X E dddx" and associated class labels Y E Rixn, where n and d are the number of examples and dimensions, respectively. Each label 4 = g(o;) corresponds to a category 42,,22..... }z). which is generated from non-euclidean clustering function g with cosine-distance loss function ((ge.). ). and L being the maximum number of leaf nodes. We use Support Vector Machines (SVM) [1] to identify the optimal hyperplane H(X) that maximizes the margin between the closest class points, known as support vectors. This results in the optimized hyperplane (X) defined by w o - p" = 0. The DT, structured binary tree for multi-class classification, incorporates this SVM-derived hyperplane. Each node splits into two child nodes based on the hyperplane's 's criteria: left for w - p" < 0 and right for w o p² 2 O. Note that the splits are still based on linear thresholds. The construction of the T, is complete until it reaches the maximum number of leaf nodes L by iteratively repeating the splitting and clustering for
1og2 + iterations. The child node in the last iterations will become a leaf node assigned the class label = arg max; { ni | = 1,, 1,, :........... the total number of sample points in the current leaf node, and nı is the number of sample points in class i. Classification can be conducted based on the 'ī- For observation with an unknown class, it constantly goes through the split nodes and finally reaches a leaf node where / indicates its class (62)
...:.:. Jr.).
where is
Perratvely-Growinn DT for Multi-agent. In each iteration, we obtain a revised Q(o, a) by condi- tioning it on the current DTs of all other agents, i.c., if two actions are merged into the same decision path, then the Q(o. a) are merged too. Then we grow the DT guided by the revised Q(o, a), which iteratively identifies the best step to grow the DT of each agent conditioned on the current DT's of other agents. To simplify, consider agents # j as conceptual super agent -j. With a constraint of L leaf nodes, we iteratively grow DT's for agent j and super agent -j. growing one more level for each agent per iteration with total of 1og, + 1 iterations. At the initial iteration (i 0), for agent j. we calculate 07z o) = [Q (Qz o_,, TT" (a,lo;), am5) do lo;]] and grow DT T using the clustering function g(o;). For super agent -j the DT is based on (o
which integrates the DT from agent j. Each subsequent iteration updates the DT's by recalculating
Q+ using the prior iteration's 's DT' to ensure consistent action choices within clusters for both agents.
6 Evaluation and Results
Experiment Setup and Baselines. We test RGMDT on both discrete and continuous state space problems in the maze environments and the D4RL 226. To explore how well RGMDT scales in multi-agent environments, we also constructed similar target-chasing tasks in the maze following the same settings as the Predator-Prey tasks in the Multi-Agent Particle Environment (MPE) [40] (detailed in Appendix). We use Centralized Q Learning and Soft Actor- (SAC) 30 to obtain the action-value vectors. We compare RGMDT against strong baselines. The baselines include different types of Imitation DT's 48 Each DT policy is directly trained using dataset collected by running the expert policies for multiple episodes. No resampling is performed. The observations of an agent are the features, and the actions of that agent are the labels. (1). Single Tree Model
7

---

Nomalize bax Compane Stups
1:397
1:057
1.005
1482
1.61
1:40
1.599
2.5
1:344
1.14
1206
2.0
1
1.0
1,0
2.0
1,2
Romalise
6.5
0.5
10
4031
0800
Methods
Methods
Merthods
(a) Simple Task
(b) Meduim Task
(c) Hard Task
Moan Epicade Reward
Mean Episode Reward 1o
CNIT
Mean Episode neware
15
30
CART
-30
CART
Raccars Hols
50
100
-30
201
250
301
32
200
15t
200
255
100
-20
120
201
Episode
376
201
(d) Simple Task
(c) Medium Task
(f) Hard Task
Figure 1: Evaluation on Maze tasks. (a)-(c): RGMDT (purple bar) completes the tasks in fewer steps than all the baselines. (d)-(f): RGMDT (blue line) achieves higher mean episode reward than all the baselines in all scenarios with varying complexities, which illustrates its ability minimize the return gap in hard environments.
using CART which is the most famous traditional DT algorithm whose splits are determined by choosing the best cut that maximizes the gain. (2). DT algorithms with Bootstrap Aggregating error correction methods: Random Forest (RF) 99 that reduces variance by averaging multiple deep DTs, trained on different parts of the same training set; Extra Trees (ET) (28] that uses the
whole dataset grow the trees which make the boundaries more randomized. (3). Boosting For Error Correction, Gradient Boosting DTs [24] that builds shallow trees in succession where each tree helps correct errors made by the previously trained tree. (4). Multi-agent Verifiable Reinforcement Learning via Policy Extraction (MAVIPER): centralized DT' training algorithm that jointly grows the trees of each agent (48), which extends VIPER (3) in multi-agent settings. All the experiments are repeated 3-5 times with different seeds. More details about the evaluations are in the Appendix.
Single Agent Task. In the single-agent task, an agent trained to navigate to a target without colliding with walls to complete the task. We increase the complexity of the environment and evaluate the RGMDT across three different levels of complexity (detailed Appendix). For each experiment, compare agents' performance using RGMDT against baselines using two metries: the number of time steps required to complete the task (fewer is better) and the mean episode rewards (higher is better). We conducted each experiment five times for both metrics using different random seeds to ensure robustness.
Figures -a Ic illustrate the normalized task completion steps for all methods relative to RGMDT's average performance. RGMDT consistently outperforms the baselines by completing tasks in fewer steps, increasing its advantage in more complex tasks. In the most challenging task, where only 10 steps are allowed complete the hard task, RGMDT typically finishes in about steps,
Table I: RGMDT achieved higher rewards with a smaller sample size and node counts on D4RL.
80,000 samples
800,000 samples
Algorithm
40 nodes
64 nodes
40 nodes
64 nodes
RGMDT
567.27 160.47
176.70+150.11
467.27 = 134.78
458.70 70 + 98.07
CART
443.47 153.49
448.85 154.12
458.47 = 131.48
460.90 = 90.40
RF
345.81 178.43
452.89 134.76
456.41 = 124.23
489.92 = 71.69
ET
196.55 + 147.92
448.98 119.40
441.01 = 138.43
451.80 = 83.24

---

whereas the baselines often fail, resulting in normalized steps that are twice as high as RGMDT. Figures [d] to [ display the mean episode reward curves over 300/500 episodes for methods tested post-offline training with DT's of maximum 4 nodes in 3 types of tasks. RGMDT consistently outperforms all baselines, with the performance improvement becoming more obvious as task complexity increases. In the simplest task, both RGMDT and baseline DT's earn positive rewards. However, RGMDT shows a significant performance advantage in the medium complexity task. the most challenging task, while most baselines struggle to complete the task, RGMDT completes it and achieves higher rewards. The results show RGMDT's effectiveness in minimizing the negative effects of fewer decision paths, thereby maintaining its performance in increasingly complex environments.
Figure 2 demonstrates the impact of leaf node counts on RGMDT's performance in the hard task, compar- ing mean episode rewards for RGMDT and baselines with [ = 4, 8, 16, 32 leaf nodes. RGMDT's per- formance improves with an increasing number of leaf nodes. Notably, with just [L] = leaf nodes, RGMDT is the only method to complete the task and outperform all baselines. With more than |L| 4 leaf nodes, RGMDT's performance approaches the near-optimal levels of the expert RL policy. This per- formance supports Thm. 4.4/s prediction that return gaps bounded by O(v (log2 muxx)) and that these gaps decrease as more leaf nodes re- duce the average cosine-distance across clusters, as noted in Remark [4.5] Decision paths for different leaf node counts visualized in the Appendix.
30
Monn
-10
Expert
AONDT
15 Number Loal Nodes
Figure 2: The normalized mean episode re- ward increases as the total number of leaf nodes increases(Hard Maze).
D4RL. Table. presents the achieved rewards for four algorithms (RGMDT, CART, RF, and ET) on the Hooper problem instance from the D4RL datasets [26). evaluated across different training sample sizes (800,000 and 80,000) and DT node counts (40 and 64). Each cell shows the achieved reward and its standard deviation. The bold values indicate that RGMDT achieves higher rewards than all baselines, especially with smaller sample sizes and node counts. When trained with 800, 000 samples, RGMDT performs better when the node counts reduced from 64 to 40, while the baselines' achieved rewards decrease. When the sample size is reduced tenfold to 80, 000, RGMDT achieves 69.33% and 21.40% improvements in the achieved rewards with 64 and 40 nodes, respectively, whereas other baselines suffer from the sample size reduction. It shows that RGMDT provides a succinct, discrete representation of the optimal action-value structure, leading to less noisy decision
Moan huwara
Moon Eppcor Roward
RGMDT MAVIPER
Initation
..... Imitation RF
Imitation CART
Complete
Eatoode
Colsdd
(a) 2 agent Nodes
(b) 2 agent 4 Nodes
(c) 2 agent 8 Nodes
45
RGNDT
43
MAVIPER
Insitation
Imitation RF Imstaatinn CART
Complete Reward
Eatrods
Ecbook
To bode
(d) 3 agent Nodes
(e) 3 agent 4 Nodes
(l) 3 agent 8 Nodes
Figure 3: Comparisons on the n-agent tasks: (a)-(c) 2 agents, (d)-(f) 3 agents. RGMDT with limited leaf nodes can Iearn these tasks much faster than the baselines and have better final performance, even when most the baselines fail on the task with 2 and 4 leaf nodes.

---

15
14 Ca Reward
AL Expert
RGHOT
Imitation ET
Imitation RF
MAVIPER
humber of Lead hoda
Numbo Loaf Nodas
(a) 2-agent Task
(b) 3-agent Task
Figure 4: The reward of RGMDT (starred purple bar) outperforms all baselines and increases with the number of leaf nodes, achieving performance comparable the expert RL (no hatch style bar).
Table 2:
All changes contributed to the improvement of RGMDT, especially the non-Euclidean clustering and iteratively-growDD designs.
Description
Task Completed
Mean Reward
Described RGMDT model
Yes
41.95 + 3.08
Removed SVM hyperplane, using CART Removed SVM hyperplane, using ET Removed SVM hyperplane, using RF Removed SVM hyperplane, using GBDT Removed Non- Euw.iieann-Custtereee Clustering Module Removed iteratively-groww process
No
26. 16 + 3.74
Yes
36.79 + 2.15
No
21.59 + 3.81
Yes
37.76 + 2.42
No
23.85 = 2.23
No
16.29 + 4.72
paths and allowing agents discover more efficient decision- making DT conditioned the non- euclidean clustering labels with smaller sample sizes and fewer nodes.
Multi-Agent Task. In Figures Ba Sc, RGMDT outperforms all baselines, particularly as the number of leaf nodes decreases. Notably, with just 2 leaf nodes, all baselines fail to complete the task, whereas RGMDT succeeds with significantly higher rewards. This performance trend continues in more challenging scenarios, as shown in Figures 3d 3f where no baseline can complete the 3-agent task with 4 leaf nodes. This demonstrates RGMDT's capability to adapt to fewer leaf nodes and more complex environments by efficiently utilizing information from action-valus vectors. Figure F confirms that RGMDT's performance improves with more leaf nodes, achieving near-optimal levels with | = 4 or more, consistent with the findings of Thm. 4.4 and supporting its application in multi-agent settings as noted in Remark 4,5
Ablation Study: Table. compares various configurations of the RGMDT model in a multi-agent setting, highlighting task completion and mean rewards. Notably, RGMDT completed tasks with an average reward of 41.95 3.08. Configurations without using SVM to derive the linear splitting hyperplane at each split and employing algorithms like CART, ET, RF, and GBDT show varied success: ET and GBDT complete tasks, while CART and RF cannot. Removing the Non-Fuclidens Clustering Module or the wwratieelyggrow-DD specifically designed for multi-agent contexts results in task failures, particularly the latter, which records the lowest mean reward. Results show all changes improved RGMDT, especially the non-Euclidean clustering and prrrtively-grow--re designs.
7 Conclusion and Future Works
This paper introduces an iteratively- Sooelly-groo----- DT framework for MARL, which views clustering label generation as a non-euclidean clustering problem and quantifies the optimal return gap between the given RL policy and the resulting DT policy with a closed-form upper bound. We propose novel class of DT algorithm, RGMDT, designed to minimize the return gap using limited leaf nodes. RGMDT significantly outperforms the baselines and achieves nearly optimal returns. Further research will delve into the regression tree that more suitable for the continuous state/action spaces, and we will also include the re-sampling module to enhance algorithm.
10

---

Acknowledgements
This work was supported in part by the U.S. Military Academy (USMA) under Cooperative Agree- ment No. W911NF-22-2-000
Office of Naval Research (ONR) grants N00014-23-1-2850 and
N00014-24-1-2073. The views and conclusions expressed in this paper are those of the authors and do not reflect the official policy or position of the U.S. Military Academy, U.S. Army, U.S. Department of Defense, U.S. Government, or the perspectives of the Office of Naval Research.
References
[1] Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18(234):1-78, 2018.
[2] Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, pages 834-846, 1983.
[3] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama, Verifiable reinforcement learning via policy extraction. Advances in neural information processing systems, 31, 2018.
[4] Sumanta Basu, Karl Kumbier, James B Brown, and Bin Yu. Iterative random forests to discover predictive and stable high-order interactions. Proceedings of the National Academy of Sciences, 115(8))1943-144 2018.
[5] Rolando Mottiista-Mottnnaooo Renato Galluzzi, Kangrui Ruan, Yongjie Fu, and Xuan Di Autonomous navigation at unsignalized intersections: A coupled reinforcement learning and model predictive control approach. Transportation research part C: emerging technologies, 139: 10366, 2022.
[6] Daniel Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of markov decision processes. Mathematics of operations research, 27(4): 8 819-840, 2002.
[7] Ioana Bica, Daniel Jarrett, Alihan Hüyük, and Mihaela der Schaar. Learning" what-if" explanations for sequential decision-making. arXiv preprint arXiv:2007. 2020.
[8] Breiman, Friedman, Olshen, and Stone. Classification and regression trees (chapman y hall, eds.). Monterey, CA, EE. UU.: Wadsworth International Group, 1984.
[9] Leo Breiman. Random forests. Machine learning, 45:5-32, 2001.
[10] Alex J Chan and Mihaela van der Schaar. Scalable bayesian inverse reinforcement learning. arXiv preprint arXiv:2102.06483, 2021.
[11] Chaofan Chen and Cynthia Rudin. An optimization approach to learning falling rule lists. In International conference on artificial intelligence and statistics, pages 604-612. PMLR, 2018.
[12] Jingdi Chen, Yimeng Wang, and Tian Lan. Bringing faimess actor-critic reinforcement learning for network utility optimization. In IEÉE INFOCOM 2021-IEEE Conference on Computer Communications, pages 1-10. IEEE, 2021.
[13] Jingdi Chen, Tian Lan, and Nakjung Choi. Distributional-utiityy actor-critic for network slice performance guarantee. In Proceedings of Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing. pages 161-170, 2023.
[14] Jingdi Chen, Lei Zhang, Joseph Riem, Gina Adam, Nathaniel D Bastian, and Tian Lan. Explain- able learning- intrusion detection supported by memristors. In 2023 IEEE Conference on Artificial Intelligence (CAI), pages 195-196. IEEE, 2023.

---

[15] Jingdi Chen, Lei Zhang, Joseph Riem, Gina Adam, Nathaniel D Bastian, and Tian Lan. Ride: Real-time intrusion detection via explainable machine learning implemented in memristor hardware architecture. In 2023 IEEE Conference on Dependable and Secure Computing (DSC), pages 1-8. IEFE, 2023.
[16] Jingdi Chen, Hanhan Zhou, Yongsheng Mei, Gina Adam, Nathaniel D Bastian, and Tian Lan. Real-time network intrusion detection via decision transformers. arXiv preprini arXiv:2312.07696, 2023.
[17] Jingdi Chen, Tian Lan, and Carlee Joe- Voe-Wong. Rgmcomm: Return gap minimization via discrete communications in multi-agent reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 17327-17336, 2024.
[18] Sungmoon Cheong, Sang Hoon Oh, and Soo- Young Lee. Support vector machines with binary tree architecture for multi-class classification. Neural Information Processing-Letee Letters and Reviews, 2(3):47-51, 2004.
[19] Youri Coppens, Kyriakos Efthymiadis. Tom Lenaerts, Ann Nowé, Tim Miller, Rosina Weber, and Daniele Magazzeni. Distilling deep reinforcement learning policies in soft decision trees. In Proceedings of the IJCAI 2019 workshop on explainable artificial intelligence, pages 1-6,
2019.
[20] Zihan Ding, Pablo Hernandez-Laal, Gavin Weiguang Ding, Changjian Li, and Ruitong Huang. Cdt: Cascading decision trees for explainable reinforcement learning. arXiv preprint arXiv:2011.07553, 2020.
[21] Tom Erez. Yuval Tassa, and Emanuel Todorov. Infinite horizon model predictive control for nonlinear periodic tasks. Manuscript under review, 4, 2011.
[22] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
[23] Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 1189-1232, 2001.
[24] Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1199-12) 2001. ISSN 00905364. WRRLhttp://www.jstte org/ stable/2699986
[25] Nicholas Frosst and Geoffrey Hinton. Distilling a neural network into a soft decision tree. arXiv preprint
2017.
[26] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning, 2021.
[27] Atul Gawande. Checklist manifesto, the (HB). Penguin Books India, 2010.
[28] Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63:3-42, 2006.
[29] Kailash Gogineni, Yongsheng Mei, Tian Lan, Peng Wei, and Guru Venkataramani. Acemer: Ac- celerating multi-agent experience replay with cache locality-aware prioritization. In 2023 IEEE 34th International Conference on Application- -speciffc Systems, Architectures and Processors (ASAP), pages 205-212. IEEE, 2023.
[30] Tuomas Haamooja Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprini arXiv: 18/2.0591 2018.
[31] Alex Haynes, Thomas Weiser, William Berry, Stuart R Lipsitz, Abdel-Hadi S Breizat, E Patchen Dellinger, Teodoro Herbosa, Sudhir Joseph, Pascience I Kibatala, Marie Carmela M Lapitan, et al. surgical safety checklist to reduce morbidity and mortality in a global population. New England journal of medicine, 360(5):491-499 2009.
12

---

[32] Weihua Hu, Takeru Miyato, Seiya Tokui, Eiichi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. In International conference on machine learning, pages 1558-1567. PML. PMLR, 2017.
[33] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems, 32, 2019.
[34] Daniel Jarrett and Mihaela Van Der Schaar. Inverse active sensing: Modeling and understanding timely decision-making, arXiv preprini urXiv:2006. 14141, 2020.
[35] Himabindu Lakkaraju and Cynthia Rudin. Learning cost-effective and interpretable treatment regimes. In Artificial intelligence and statistics, pages 175-175. PMLR, 2017.
[36] Benjamin Letham, Cynthia Rudin, Tyler H. McCormick, and David Madigan. Interpretable classifiers using rules and Bayesian analysis: Building better stroke prediction model. The Annals of Applied Statistics, 9(3):1350 1371, 2013. doi: 10.1214/15-A0AS842 URL
https: :stps://doi.. org/10.
10. 1211/1111111000 AOAS848
[37] Huiqun Li, Hanhan Zhou, Yifei Zou, Dongxiao Yu, and Tian Lan. Concaveq: Non-monotonic value function factorization via concave representations in deep multi-agent reinforcement learning. In Proceedings of the Tiihty-Lighth AAAI Conference on Artificial Intelligence (AAAI-2024), volume 38, 2024.
[38] Zachary C Lipton. The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery. Queue, 16(3):31 2018.
[39] Guiliang Liu, Oliver Schulte, Wang Zhu, and Qingcan Li. Toward interpretable deep reinforce- ment learning with linear model u-trees. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018, Dublin, Ireland, September 10-14, 2018, Proceedings, Part Il 18, pages 414 429. Springer, 2019.
[40] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative--omppttivv environments, 2017. URL https://arxxi org/abs/1706 1706. 02275
[41] Gjorgji Madjarov, Dejan Gjorgjevikj, and Ivan Chorbev. A multi-class svm classifier utilizing binary decision tree. Informatica, 2009.
[42] Andrew Kachites McCallum. Reinforcement learning with selective perception and hidden state. University of Rochester, 1996.
[43] Yongsheng Mei, Tian Lan, Mahdi Imani, and Suresh Subramaniam. A bayesian optimization framework for finding local optima in expensive multimodal functions. ECAI 2023, pages 1704-170 1711. IOS Press, 2023.
[44] Yongsheng Mei, Hanhan Zhou, Tian Lan, Guru Venkataramani, and Peng Wei. Mac-po: Multi- agent experience replay via collective priority optimization. arXiv preprint arXiv:2302. 10418, 2023.
[45] Yongsheng Mei, Mahdi Imani, and Tian Lan. Bayesian optimization through Gaussian Cox process models for spatio-temporal data. In The Twelfth International Conference on Learning Representations, 2024.
[46] Yongsheng Mei, Hanhan Zhou, and Tian Lan. Projection-pptmne monotonic value function factorization in multi-agent reinforcement learning. In Proceedings of the 2024 International Conference on Autonomous Agents and Multiagent Systems, 2024.
[47] Robert Messenger and Lewis Mandell. modal search technique for predictive nominal scale multivariate analysis. Journal of the American statistical association, 67(330):768-777 1972.
[48] Stephanie Milani, Zhicheng Zhang, Nicholay Topin, Zheyuan Ryan Shi, Charles Kamhoua, Evangelos F. Papalexakis, and Fei Fang. Maviper: Learning decision tree policies for inter- pretable multi-agent reinforcement learning, 2022.
13

---

[49] Stephanie Milani, Nicholay Topin, Manuela Veloso, and Fei Fang. Explainable reinforcement learning: A survey and comparative review. ACM Computing Surveys, 56(7):1-36, 2024.
[50] James N Morgan and John A Sonquist. Problems in the analysis survey data, and a proposal. Journal of the American statistical association, (14302):41544535 1963.
[51] Manisha Natarajan and Matthew Gombolay. Effects of anthropomorphism and accountability on trust in human robot interaction. In Proceedings of the 2020 ACM/IEEE international conference on human-robot interaction, pages 33 43,42, 2020.
[52] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2836 2011.
[53] J. Ross Quinlan. Induction of decision trees. Machine learning, 1:81 1:81-106, 1986.
[54] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth interna- tional conference on artificial intelligence and statistics, pages 627-635 JMLR Workshop and Conference Proceedings, 2011.
[55] Aaron M Roth, Nicholay Topin, Pooyan Jamshidi, and Manuela Veloso. Conservative q- improvement: Reinforcement learning for interpretable decision-tree policy. urXiv preprint arXiv:1907.01 01 180, 2019.
[56] Cynthia Rudin. Algorithms for interpretable machine learning. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1519-1519, 2014.
[57] Andrew Silva, Taylor Killian, Ivan Dario Jimenez Rodriguez, Sung- Haun Son, and Matthew Gombolay. Optimization methods for interpretable differentiable decision trees in reinforcement learning. arViv preprint arXiv:I903.08. 093388, 2019.
[58] Andrew Silva, Matthew Gombolay, Taylor Killian, Ivan Jimenez, and Sung-Hyun Son. Op- timization methods for interpretable differentiable decision trees applied reinforcement learning. In International conference on artificial intelligence and statistics, pages 1855-1865. PMLR, 2020.
[59] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033. IEEE, 2012.
[60] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, pages 5045-5054. PMLR, 2018
[61] Fei Wang, Quan Wang. Feiping Nie, Weizhong Yu, and Rong Wang. Efficient tree classifiers for large scale datasets. Neurocomputingg 284:70-79, 2018.
[62] Fei Wang, Quan Wang, Feiping Nie, Zhongheng Li, Weizhong Yu, and Fuji Ren. A linear multivariate binary decision tree classifier based on k-means splitting. Pattern Recognition, 107: 107521, 2020.
[63] Pawel Wawrzyáski. A cat-like robot real-time learning to run. In Adaptive and Natural Computing Algorithms: 9th International Conference, ICANNGA 2009, Kuopio, Finland, April 23-25, 2009, Revised Selected Papers pages 380-390. Springer, 2009.
[64] Marvin N Wright and Andreas Ziegler. ranger: fast implementation of random forests for high dimensional data in c++ and r. arXiv preprint arXiv: / 2015.
[65] Haoran Xu, Li Jiang, Li Jianxiong, and Xianyuan Zhan. A policy-guided imitation approach for offline reinforcement learning. Advances Neural Information Processing Systems, 35: 0085-4098. 2022.
14

---

[66] Herman Yau, Chris Russell, and Simon Hadfield. What did you think would happen? explaining agent behaviour through intended outcomes. Advances Neural Information Processing Systems, 33: 33:18375-18386, 2020.
[67] Zuyuan Zhang, Mahdi Imani, and Tian Lan. Modeling other players with bayesian beliefs for games with incomplete information. arXiv preprint arXiv:2405.14122, 2024.
[68] Zuyuan Zhang, Hanhan Zhou, Mahdi Imani, Taeyoung Lee, and Tian Lan. Collaborative ai teaming in unknown environments via active goal deduction. arXiv preprint arXiv:2403.15341, 2024.
[69] Hanhan Zhou, Tian Lan, and Vaneet Aggarwal. Pac: Assisted value factorization with coun- terfactual predictions in multi-agent reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 36: 2022.
[70] Hanhan Zhou, Tian Lan, and Vaneet Aggarwal. Double policy estimation for importance sampling sequence modeling-basee reinforcement learning. NeurIPS 2023 Foundation Models for Decision Making Workshop, 2023.
[71] Hanhan Zhou, Tian Lan, and Vancet Aggarwal. Value functions factorization with latent state information sharing in decentralized multi-agent policy gradients. IEEE Transactions on Emerging Topics in Computational Intelligence, 7(5):1351-131) 2023.
[72] Haoran Zhu, Pavankumar Murali, Dzung Phan, Lam Nguyen, and Jayant Kalagnanam. A scalable mip-based method for learning optimal multivariate decision trees. Advances in neural information processing systems, 33:1771-1781, 2020.
15

---

A Impact Statements
The proposed framework can iteratively grow decision trees for multi-agent environments, while we do not see an immediate threat of ethical and societal consequences, is essential to address and mitigate any risks of misuse or unintended consequences from applying malicious training datasets or improper use of certain scenarios.
B Additional Related Work Discussion
Effort on Interpretability for Understanding Decisions. To enhance interpretability in decision- making models, one strategy involves crafting interpretable reward functions within inverse rein- forcement learning (IRL), as suggested by [10]. This approach offers insights into the underlying objectives guiding the agents" decisions. Agent behavior has been conceptualized as showing pref- erences for certain counterfactual outcomes 77. or as valuing information differently when under time constraints 34 However, extracting policies through black-box reinforcement learning (RL) algorithms often conceals the influence of observations on the selection actions. An alternative is to directly define the agent's policy function with an interpretable framework. Reinforcement learning policies have thus been articulated using a high-level programming language [60], or by framing explanations around desired outcomes [66]. facilitating more transparent understanding of decision-making processes.
Decision Trees.
Since their introduction in the 1960s, DT's have been crucial for interpretable
supervised learning 47 50 [33] The CART algorithm 8 established in 1984, foundational in
DT methodologies and underpins Random Forests (RF) 9 and Gradient Boosting (GB) [23]. which are benchmarks in predictive modeling. These techniques are central to platforms like ranger and scikit-learn and continue to evolve, as seen in the iterative random forest, which explores stable interactions in data 52 64 70). However, traditional DT methods are challenging to integrate with RL due to their focus correlations within training data rather than accounting for the sequential and long-term implications in dynamic environments. Imitation learning approaches have been explored in single-agent RL settings 42, 55 (8). For instance, VIPER (3] trains DTs with samples from trained DRL policy, but its return gap depends on the number of samples needed and does not apply to DT's with arbitrary size constraints (e.g.. maximum number of nodes L). DT algorithms remain under-explored in multi-agent settings, except for MAVIPER [48] that extends VIPER to multi-agent scenarios 46) while lacking performance guarantees and remaining heuristic design.
Interpretable RL via Tree-based models. To interpret an RL agent, Frosst 25 explain the decisions made by DRL policies by using trained neural net to create soft decision trees. Coppens et al. [99 propose distilling the RI. policy into a differentiable DT by imitating a pre-trained policy. Similarly, Liu et al. [39] apply imitation learning framework to the Q-value function of the RL agent. They also introduce Linear Model U-trees (LMUTTs), which incorporate linear models in the leaf nodes. Silva et al. (57] suggest using differentiable DTs directly as function approximators for either the Q function or the policy in RL. Their approach includes a discretization process and rule list tree structure to simplify the trees and enhance interpretability. Additionally, Bastani et al. (3 propose the VIPER method, which distills policies as neural networks into a DT policy with theoretically verifiable capabilities that follow the Dataset Aggregation (DAGGER) method proposed in (54), specifically for imitation learning settings and nonparametric DT's. Ding et al. (20) try to solve the instability problems when using imitation learning with tree- model generation and apply representation learning on the decision paths to improve the decision tree-based explainable RL results, which could achieve better performance than soft DTs. Milani et al. extend VIPER methods into multi-agent scenarios [48] in both centralized and decentralized ways, they also summarize a paper about the most recent works in the fields of explainable AI 44 which confirms the statements that small DTs are considered naturally interpretable.
C Background and Preliminaries
C.1 Decision Tree
Multivariate Decision Tree: Wang et al. 66 introduced two variants of multivariate decision tree classifiers structured full binary trees: the Randomly Partitioned Multivariate Decision
16

---

Tree (MDTI) and the Principal Component Analysis (PCCA)-Patitionn Multivariate Decision Tree (MDT2). MDTI and MDT2 utilize a unified approach to construct binary tree through top-down recussive partitioning, ceasing when no further nodes require division. Initially, the root node encompasses all training data. The process simplifies as (1). Split the current node into left and right children using multivariate hyperplane. (2). Apply split condition; nodes meeting this condition are further partitioned, while others become leaf nodes, adopting the majority class for prediction. (3). Proceed to the next node for partitioning, repeating from step I until no dividable nodes remain.
The framework focuses on two main aspects: constructing the multivariate hyperplane for each node's split and defining the split condition. We'll Il detail these aspects by examining single split, involving node with a sample matrix X E Rdx= and corresponding class labels Y E R x where and represent the number of examples and dimensions, respectively. Each label yi E (4.42.....e l... i= 1, ..,,..., n. corresponds to one of classes.
Splitting via Hyperplane: To split nodes, MDTI and MDT2 use a hyperplane defined as:
w 0,
(13)
where w indicates the hyperplane's 's normal direction, x is a sample from X, and p denotes the threshold. Splitting directs samples to left or right child nodes:
{
x E
X1 X2
if x>p
(14)
ffw.xpp.
where X1 and X2 denote the subsets of samples assigned to the left and right child nodes, respectively,
In Eq. (3), the hyperplane is defined by two parameters, and p. where w represents the normal vector and the cut-point. Both MDTI and MDT2 follow the same approach to determine For given w, sample points from the matrix X projected onto w, resulting in projections (P(x)) = w -,, 1.2,...,
nz}. The cut-point is then set as the median of these projections:
p median (P(z)) x; E X, in, i2. n)
(15)
MDTI and MDT2 differ in their methods for determining the hyperplane's normal vector w. In MDTI, a vector v = [V), ..,..., va]a in nddx1 matching the dimensionality of sample point x, is randomly generated with each element within the range [-1, 1]. MDTI then uses the normalized vector v as the normal direction w:
W
|v
(16)
MDT2 adopts a heuristic approach instead of random vector generation, to establish the normal direction w. This method uses the principal component analysis (PCA) to select the most significant principal component from the sample matrix X and designate as w. Beginning with X [x) X2......., x.)., we first centralize this matrix by deducting the mean value of all sample points,
(x1 + +x..) Subsequently, eigenvalue decomposition is applied to the covariance matrix = XXT yielding eigenvalues λ > A2 > ... > Xa and their associated eigenvectors E1, Ea. MDT2 then selects the eigenvector corresponding to the largest eigenvalue of S to serve as the normal direction, i.e.,
resulting X X1 m. X2- m...,, X., m]. where
(17)
This method of determining the normal direction maximizes the variance of the sample set along w. Consequently, the partitioning aligns with the orientation that maximizes the differentiation among instances in the sample set.
Split Condition: After each split, child nodes are evaluated with a split condition to determine if further division is necessary. A child node undergoes additional splitting if it meets the defined condition:
purity(R.) = max {"
n2 | 1 12... 11.,2...,,4 <5
where represents either X, or X2, r is the total number of sample points R, n, is the count of sample points in class i, and 8 is predetermined threshold within (3, 1]. Conversely, if child node fails to meet this condition, is designated as leaf node with the class label 1* = arg max; ( 24 i 4,, 12......ee).
17

---

When all nodes have been successfully split, the construction of a multivariate decision tree model (either MDTI or MDT2) is complete. this model, split nodes store the parameters w and whereas leaf nodes are tagged with class label /" E (1,,4....,,4)
Classification:
Classification using the constructed tree model involves determining the appropriate class for data point whose class is unknown. This process is initiated by placing the data point at the tree's root node and sequentially navigating through the tree based on the data point's position relative the hyperplanes defined by w and at each split node. This traversal continues until a leaf node is reached, at which point the class label 1" assigned that leaf node designates the data point's 's class.
C.2 Support Vector Machines (SVM) optimization
In this paper, we apply Support Vector Machines (SVM) 41 identify the optimal hyperplane that
separates different clusters with the maximum margin in the observation space S2,. The objective of SVM is to find hyperplane described by w x - p 0 that maximizes the margin between the two nearest data points of any class, which are termed support vectors. This can be formulated as an optimization problem:
min | w.P 2
(18)
which is subject to the constraints for all i (where indexes the training examples):
y w x, - p) 2
(19)
Here, yi represents the class labels, which are assumed to be 1 or 11, and x; are the feature vectors of the training examples. To solve this optimization problem, we introduce Lagrange multipliers ag 2 0 for each constraint, leading to the Lagrangian:
L(w, p. a) w/ll
1
Σ ( -p) -1].
(20)
The conditions for optimality CCarush-Kunn-iee conditions) lead to the dual problem, which is dependent only on the Lagrange multipliers a. The dual problem can be expressed as:
a,ajViy;8, X2,
(21)
iJ=1
subject to a; 2 0 and Σi= 0ill = 0. After solving the dual problem, the optimal values of a; are used determine w:
w
a,y,
(22)
For any support vector x, (where 0₂ > 0), p can be computed using:
p
yo-
(23)
The hyperplane
p ==0 0 effectively partitions the observation data points based the mapped cluster centers, we can achieve a robust partitioning of the observation data points into distinct groups based on the Non-Euclidean distance of the action-value vector space Q
Then we Incorporate the parameters w and p obtained from SVM into the construction a decision tree, which is binary tree architecture for multi-class classification [18). For each node in the tree, use the SVM-derived hyperplane w x - p = O to split the data. This split divides the node into two child nodes. Left child node: Contains data points that satisfy Contains data points that satisfy w X p 2 0.
p < O. Right child node:
C.3 Construting Decision Trees Minimizing Return Gaps
For the construction of decision trees, we adapt the non-euclidean clustering labels generated from the Z,. and incorporate the parameters w and obtained from training the Support Vector Machines (SVM) conditioned on samples (oj. 14).
Methodology Overview: After applying SVM to determine the optimal hyperplane characterized by the normal vector w and bias term p. we utilize these parameters to construct decision trees that classify data points based their positions relative the hyperplane. This approach enables the
18

---

decision tree to make binary decisions at each node using the linear boundaries defined by SVM, thus combining the interpretability of decision trees with the robust classification capability of SVM. The algorithm is summarized in Algo. 2
Initialization: Start by considering the entire dataset as the root node. The goal is partition this dataset into subgroups that are as homogeneous as possible in terms of the target variable.
Node Splitting Using w and pt For each node in the tree, use the SVM-derived hyperplane W x p = to split the data. This split divides the node into two child nodes. Left child node: Contains data points that satisfy x p O. Right child node: Contains data points that satisfy W X p 0.
Recursion: Recursively apply the node splitting step to each child node, reapplying SVM to the data points the child node to find a new optimal hyperplane for further splits. This process continues until the pre-defined maximum number of the leaf nodes is reached.
Decision Making: Each leaf node the resulting tree represents decision outcome, with the class label determined by the majority class of the data points within that node.
Spperplane-Based Decision Boundaries: The decision boundaries in the constructed decision tree are linear and defined by the hyperplanes from SVM. This provides a clear geometric interpretation of the decision-man making process, where each decision node effectively acts linear classifier.
D Theoretical Proofs
D.1 Proofs for Lemma 4.1
Proof. To simplify, denote the policy generated by decision tree T We prove the result in this lemma by leveraging observation- state value function V (o) in Eq 2 and the corresponding action value function (o, a) E, Ei 7' Rets Or = o, a to unroll the Dec-POMDP. Here we consider all other agents + j as conceptual agent denoted by -j.
J(m") J(r)
= E, -
E, -0V
(1 0,01
+ (706,000000000000-00000000000000
= E1, (,000-100((000000000000))+++00 Q")"
E, -4,(1=>)]44
+ 1000
(1 - (1)00
(24)
Alo_ (f),,))))))))))
0p o
Σ ΣΣΣ jj a
(-)0)))))))
Σ
Q² (o Oj at Q(0
oy
Σ Σ az, Q" (o,))) -d)(0))
Step 1 is to use Eq. 3 with initial observation distribution o00) at time / = 0 to re-write the average expected return gap; Step separate the observations as agent j and the other agents as single conceptual agent -j. then (o-j. oy); Step 3 and step 4 are obtain the sub-optimality-gan
19

---

of policy オ, defined as = -o a"), by substracting and plus a paction-value function Q (0) Step is unroll the Markov chain from time / = 0 to time
1; Step 6 is to use sub-optimality-gan accumulated for all time steps to
represent the return gap; Step and step 8 is to absorb the discount factor 1 - 7 by multiplying the (o) = (1 7) -t= P( = of (4) which is the 7-discounted visitation probability of
observations under policy given initial observation distribution μı; Step 9 is to revert A A" a) back to 2 (0. a²) (o, a) Step 10 is to replace the second term Q"(o,at with Q" a*)
Since (0, a²) ) larger than Q" (o, a ) therefore, the inequality is valid.
D.2 Proofs for Thm. 4.2
Proof. To simplify the notations, we denote the policy generated by decision tree T as π. Here we prove the return gap between the decision tree policy и and optimal RL policy x for one iteration first. Since the observability of all other agents * remains the same, we consider them as conceptual agent denoted by- -j. For simplicity, we use x² to represent Tip and π to represent **)))) in distribution functions. Similar to the illustrative example, we define the action value vector corresponding observation 0z. i.e.
(o,,,) 10 (o-), Vo-sl.
(25)
where o-j are the observations of all other agents and (z) is a vector of action values weighted by marginalized visitation probabilities (o-o)))) and corresponding to different actions:
(o()),00) = (o (o-): (o(5)) Yal, ,o_, ~ (o (lo)), Ya ~ (o a). (26)
Here n² (o. denotes the observation-
distribution given policy म, which means μr (o. a) (T[(T)(()))) We also denote d= (!) is the visitation probability of label L, and do(or) is the marginal- ized probability of o, in cluster 1, i.e.
d)(oo) d7(())
(,(1))
d(oo,)
(27)
0ymll
Since the optimal return J((t)) is calculated from the action values by max, (o, a), we rewrite this in the vector form by defining a maximization function mmax ( (Q" 0j)) that returns the largest component of vector (o 05). With slight abuse of notations, we also define T Pmax (Q= Eo,; & max (Q* (0=j:o;)) as the expected average return conditioned on oj. Then Eoywe de(o;)) max m (o,)) could be defined as selecting the action from optimal policy T()) where agent chooses different action distribution to maximize (Q" (oz)). We could re-write this term with the action-value function as:
Σ dilo,) 4 maz mmax((" (o;))
Σ d((o,)) Σ mara 0pml
d[(o)) dz(l)
(28)
Σ
mara (0a,, oo,0o_)))
ayvll
Σ (T))
17710)
0,-0
then we used the fact that while ((T()) conditioning on complete 0j can achieve maximum for each vector Q* (oj). policy TT2) is conditioned on labels lúj rather than complete 0j and thus must take the same actions for all 0j in the same cluster. Hence we can construct a (potentially sub-optimal) policy to achieve Imax Eo, do())) (*()))) which provides a lower bound on J(T()) Plugging
in (7) 4 max (Eo,~ d((0;) Q"(o))) can be re-written as:
20

---

① maxx
Σ d((0)) (*(o;))
Σ mama
(
(29)
a-j
Oy
Σ 0-1 oyrul
mata
(0- de (0
Multiplying the two equations above Eq. 29 and Eq 28 with (1)) which is the visitation probability
of label I to replace the term Eojsl 2a_, 1Q" (0- oj a²) oj, a)] di ( 0j) in the
Eq. 24
obtain upper bound the return gap:
J(TT)) (TTO)
Σ Σ EI 10 (0 "3,aa")))))). Q(0-).00. -d oj),
o-3
Σ (0
d((o;) max (o;))
(30)
Oyrll
Σ di(o)) (o,))
max
0ynd
To quantify the resulting return gap, we denote the center of cluster of vectors (*()) for oj ~ I under label as:
H(I)
Σ d(lo)) (o,) 05~1
(31)
We contracts clustering labels to make corresponding joint action-values (Q)( g(0z) 1) close to its center (1). Specifically, the average cosine-distance is bounded by small for each label 1, i.e.
Σ (o,), d700)
(32)
Σ ((oz) (0 Se, VI.
<
0,
where c(o,)= = Enyss Deos (o,), (())/K, K, K is the number observations with the same label 1, and Doos (A, B) 1
A-B is the cosine distance function between two vectors A and B. |||||||||
For each pair two vectors (o,) and (I) with (O,) (()) S e(o;), we use cos cos0,, to denote the cosine-similane similarrty between each (o,) and its center (I). Then we have the cosine distance (o,), (I) 1- cos fop I <(o,). By projecting (o,),, toward (l). (o;) could be re-written as (0,) = Q (o,) + cos 0,y Hm, where Q (o,) is the auxiliary vector orthogonal to vector Hm.
Then plug the decomposed Q vectors (o)) into the return gap got in Eq. (3,, the first part of the last step of Eq. (30) is bounded by:
d(() Pmaz (Q* (o;))
m
Σ d((or) o maz (Q) (o,) + H(!) cost.;),
(33)
di(o;): i (0,));;) man (iI(1) cos 00
< Σ d(oo)) p maa (Q (Q' (o,)) + aaa (())).
21

---

We use ||a||2 to denote the L-2 norm of a vector a. Since the maximum function & (Q' can be bounded by the L2 norm C' - 11I l22 for some constant C. We define constant Qmax as the maximine absolute value of Q" (o²) in each cluster as Qmax max Qo())) (oz) sin(O), and ss))
Since v cos² v c(o,) ) the maximum
value of (o²) could also be bounded by Qmax i.e.:
L Pman (2" (o,)) - C- 110
C 110 la |sin
(34)
=C Qmax 1 [1 (()))))
c(or))?
I OlV ((1;) Qmax).
Plugging Eq. 34 into Eq. (3). we have:
Σ di do(o;) man (Q" (o,))
Σ de(0;)
man (Q (0j)) + & man (H())),
(35)
Σ de(o)) (((yelo)))maa + $ manl (H())))
0,1l
Σ d(oo)) (0( ((ax))mmx)) + ma
0p
It is easy to see from the last step in Eq. 30 that the return gap J( (TG) is bounded by the first part Σ, (1)E ~, d(oo)) max (o;)) which has an upper bound derived in Eq. then the return gap could also be bounded by the upper bound in Eq. 35 i.e.,
J ) - (T())
= Σ d (1) Σ d((o)) $ pmar(Q" (Q)))
man! Σ de(os) (")
oyrll
Σ t0
Σ d((o,) -0(() + Pmax (H))
+ max Σ do(o;) ('(0)))
ayrul
(36)
$ Σ (0 Σ
Σ
d((0;) O( ((o,))mmmxx))
Σ (00) -0 (1
Σ di(o;) c(o;))mms agmll
Σ (1))) O(veQuax),
= =mVeQmmax)
we can derive the desired upper bound - ((T()) S O(VeQmax) for the two policies in one iteration. then for (log, (L) + 1) iterations of generating L-leaf- DTs, the upper bound is ( ((T)) < ((1((logz(L) (L) 1)xeQmaxx) Lemma 4.2
22

---

D.3 Detailed process of calculation of the average cosine distance defined in Equation 6
Within each cluster, we compute the cosine distance between every action-value vector and the clustering center, thereby obtaining the value E(az).
To obtain the expectation of the cosine distance for each particular cluster denoted by 1, we compute the product of each <(oz) with di(o;), where do())) represents the marginalized probability of 0z in cluster 1.
Having computed the expected cosine distance for each cluster 1, we proceed to obtain the average cosine distance across all clusters. This is accomplished by multiplying di) to each Eajet (1,) e(oz), where (1) denotes the visitation probability of label I.
D.4 Proof of Lemma 4.3
We group vectors (og) with smaller cosine distances together ensure their similarity in the same group. Then we could obtain L clusters Ci...., Cr corresponding to their centers H1 (1)..... (1), where each cluster Cj contains set of vectors qj = (o;).
Once we have the cluster center (I) in the action value vector space (o;) E 2,. need to map them back to the original observation space S2.. Since we have the action value function, we could use the inverse transformation Q-1 to map each cluster center (1) from the action value vector space 2j back to the observation space 22,. i.e.,
I = (H(()
(37)
Since the cosine distance is a measure of similarity between two vectors that not based on the Euclidean distance, but rather on the angle between the vectors, this is non-euclidean distance metric. We can define our metric space as in Lemma. 4.3
Proof. To prove that the observation space Ω2 with the cosine distance function Dens as defined forms a metric space, we need verify that Deas satisfies the conditions of metric. (1). Non- negativity and Identity of Indiscernibles: For any of. of E Ω2 the cosine similarity of them is within the range [-1, Therefore, 1 f(Â (of), Q* (of)) ranges from 0 to 2, ensuring non- negativity. Moreover, (of, of) = 0 if and only if f(Â' (o9),
1, which occurs only when (o)), ('(o) are in the same direction and, assuming normalization, are identical, thus satisfying the identity of indiscernible. (2). Symmetry: The cosine similarity between two vectors is symmetric, which directly implies that (o og) (oo 0z). (3). Triangle Inequality (Nuanced Interpretation): Given the angular basis of f. the traditional triangle inequality for linear distances needs careful interpretation. For cosine distances, the triangle inequality may not strictly apply. Instead, the 'distance' measures angular differences, aligning under specific conditions with a version of the triangle inequality tailored for angles. Consequently, (M2, Deos) fulfills key metric space properties but better termed a pseudometrie space due to the nuanced interpretation of the triangle inequality with cosine distances.
E Algorithm
IterativelyGrrow-DD Process: To simplify, consider agents i * as a conceptual super agent -j. With limit of L leaf nodes, we iteratively grow DTs for agent j and super agent -j. adding two nodes for each agent per iteration with total of log)(L) + iterations. For agent j at iteration = 0, Qui=0 (o,, = [Q, o_,, (a,lo;) a-z) dT((=-lo;)], ap- ply Lemma. 4.3 we got not1j-1 1j=0 = g(oz) and DT T for iteration O. For agent -j. we con- di
sider the clustering for (oi="(o_,,0)) 0z) = (Q' oj, x (a_;lo-,)) T, (()) (o,(o,o-_))] We use (o,) replace ay in @ (o_ since the agent j is restricted to taking the same actions for all oj in the same cluster with label 4,. apply Lemma. 4.3 we got DT
in the interaction 0 for agent -j. For each iteration k. for growing DT for agent agent j takes actions based on () agent -ý takes actions based on ( then (0,0,,,0))) (Q) -- T, - (o,), T is used for clustering and training
23

---

Algorithm 1 Non-Euclidean Clustering (NEC)
1: Input:Ki, K2, K3, A, Replay buffer R. current parameters { (fI:...,E.. {n
2: for /= to 7 do
3:
for agent j to do
4:
Get top-Kı samples X = " , R from replay buffer R;
5:
Sample the top K2 frequent observations {o kz from Rz;
6:
Got the corresponding actions = (o
7:
Combine them and form set X-, fo -j ा 1));;;
8:
Form the sampled trajectories by combining (oj, π (oz)) in X, and (o-j, (0-))) in
K-3 D (o xT" (a)) & k=))
9:
Query the oracle critic networks parameterized by w with D as the input to get the
(ojs O-ji xt
10:
Update de, by minimizing the loss Lgge)) defined in the main paper;
11: end for
12:
end for
13:
Output: Clustering label generation functions: = -E, (og).
DT (o;); for growing DT for agent -j in the same iteration k. since agent j updates its - DT. (" 0,) (0-). T (o- (o;)) is used for clustering and obtaining DT
Tj (o,).
E.1 Computational Complexity of RGMDT
Since we grow RGMDT with a small number of leaf nodes L, it's time- and space-efficient compared other large DTs and DNNs. (1). Time Complexity: It is determined by the Non-Eucliddean clustering and DT construction steps, estimated as O(T n² log L), where represents the number of iterations of clustering for convergence, n. is the number of Q-value samples, and T. is the maximum number of leaf nodes. This reflects the intensive computation required for non-Euclidean distance calculations and iterative tree growth. (2).Space Complexity It's O(K (n + L)). This accounts for the storage of n Q-value samples each with d dimensions and the DT structures with L leaf nodes per tree across K agents.
E.2 Real-World Applications of RGMDT
The superior performance of RGMIDT with small number of leaf nodes enhances its compact- ness and simplifies its implementation in practical scenarios. Compared to DNNs, its simpler DT structure requires less computational and memory resources during inference, making well-suited for aesource-limited environments in real-world applications like robotics, network security, and 5G network slicing resource management. For example, DT's have been implemented in memristor devices to support real-tine wal-timee intrusion detection in scenarios requiring low latency and high speed [15]. RGMDT's interpretable structure makes more suitable for memristor- tions in resource-constrained environments for network intrusion detection achieves detection speeds of microseconds, together with significant area reduction and energy efficiency, with performance guarantee that previous DT's fail to provide.
hardware implementa-
F Experiments
We conducted experiments on the Ubuntu 20.04 system, with Intel(R) Core(TM) 19-7290K CPU (4.4 GHz), 4x NVIDIA 2080Ti GPU and 256 GB RAM. The algorithm is implemented in Python 3.8, using main Python libraries NumPy 1.22.3 and Pandas 2.0.3. The code will be made available on GitHub after accepted.
The proposed algorithm is evaluated on both single-agent and multi-agent goal-achieving tasks. For maze tasks, we build the tasks based on Mujoco [59], agents must reach the goal simultaneously to complete this task while avoiding collisions between agents and the obstacles. Note that these tasks are quite challenging:
(1) We increase the maze dimension and place the high-reward goal at the corner of the maze surrounded by high-penality obstacles which are harder for agents to
24

---

Algorithm 2 Return-Gap Minimization Decision Tree Construction (RGMDT)
1: Input: R = (o, a, R, o'). π .ff.....TTT.. " Sampling size K1, K2, Nearest neighbors' size K3. Maximum leaf nodes I..
2: Initialize non-euclidean clustering network weights Ç for each agent j at random;
3: Initialize non-euclidean clustering target weights ç & for each agent j at random;
4: Output: DT [T ] for n agents.
5: for agent j 1 to n do
6: Get K samples X; - ( Rki ,.*h) from replay buffer R;
7: Sample the top K2 frequent observations {o kz from Xz:
8: Got the corresponding actions = = x (o
9: Combine them and form set X-, {o π (o= ;):
Form the sampled trajectories by combining (0,, " (0,)) in X2 and (o-j, n" (o-;)) X-,
as (o πO" (o Rk112, ,o o(H
11:
Query the π²" = [mi....,ne T with D as the input to get the (o, omj) =
[Q" (03, 0-j; (0 (aylo;;
a-3) ( (o=1oo))];
12:
Update 98, by minimizing the loss L(ge,) defined in the main paper;
13:
Got 1/ =0, (oy);
14:
Apply Function Grow One-Iteration DT Φ(o,, 4, L), get DT 7,i=0 for iteration Replace T with T
15:
end for
17:
for iteration k = 1, ................................ log, (L) + do
18:
for agent j = 1 to do
19:
Get top-K1 samples X, = (o a Rh ohhi from replay buffer R;
20:
Sample the top K2 frequent observations {o =3 from Xy;
21:
Got the corresponding actions Az Tizk-
Combine them and form set X- = -3 Timk- (o
23:
Form the sampled trajectories by combining (0,, (i=) in H3 and )) in X_j as D (otikz T" (o Rhike oahika);
(o-j, (o
24:
x with D as the input to get the T~ o-z) Query the n² T-ik-l(o_ (o-y);
[ ......,
[Q" (oj, o-j: T (o,). T-,k-1
Update Ø5, by minimizing the loss L(g,,) defined in the main paper; Got ji=k = 95, (o,);
26:
27:
Apply Function Grow One-Iteration DT Φ(o;, Lj, L), get DT (o;) for iteration
28:
Replace Ti with (o;)) when doing the iteration step for other agents -j;
29: end for
end for
31: function GROW ONE-ITERATION DT c(D, L)
32:
Sample a matrix X E [Rdxn of oj from D and its associated class labels Y E R11x" ,
1 g(oy);
33:
Apply SVM for obtaining w,
Partition node's data into left and right child nodes using:
35:
if w p < ( then
36:
Assign x to left child node;
37:
else
38:
Assign x to right child node;
39:
end if
40:
end function
41:
Output: Return the constructed decision tree T [T,4 ...., T.4 for n agents.
25

---

reach, and agents' observations do not include any information about the goal, so they need to grow DTs iteratively based on their joint action value vectors and get the information about their joint observation space to find the rewarding state. (2) The reward space is highly sparse and delayed: for all the tasks, only when the agents complete the task can they receive a reward signal r (shared by all the agents); otherwise, they will receive = 0.0. Hence, agents without highly efficient knowledge of the observation space cannot complete these tasks. In the experiments results, we conduct experiments with tasks of increasing complexity (e.g. Figure [ showing that the more difficult the task is, the more advantageous our approach becomes.
F.1
Environment Details
F.1.1 Single Agent Scenarios
This is a tabular- case maze task. Consider a W by H grid world, where landmark 1 with a high reward of 1 is always placed at the higher left corner (1, 1). while landmark 2 with a low reward of r2 is always placed at the middle diagonal position ([W/2), HH))). There are No obstacles that are randomly placed on the map and there is collision penalty (negative reward signal ra- = -r2) if the agent covers the obstacles. There is no movement cost. The task is completed and the reward rı (or r2) is achieved only if the agent occupies of the rewarding landmarks before or at the end of the game. Otherwise. The game terminates in T steps or when the task is completed. The maximum training episodes are Ne.
Single Agent Maze Task:
Simple Maze: W = 4, H = 4. there is only one target landmark placed in the top left corner and there are no obstacles. T and N₂ = 3000.
Medium Maze: W 8, 8, there only one target landmark placed in the top left corner and there are two obstacles. T = 8 and N₂ 5000.
Hard Maze: W = 10, H 10, there are two target landmarks placed in the top left corner and in the middle of the maze map, there are two obstacles, both are close to the higher rewarding states. T = 10 and N: = 5000.
This environment is based on the work done by Erez, Tassa, and Todorov in (1 The environment aims to increase the number of independent state and control variables as compared to the classic control environments. The hopper is a two-dimensional one-legged figure that consist of four main body parts the torso at the top, the thigh in the middle, the leg in the bottom, and single foot on which the entire body rests. The goal is to make hops that move in the forward (right) direction by applying torques on the three hinges connecting the four body parts. More details can be found in https://ymmaaiimm http:/mmaaiuu.aaaaa...o
D4RL- Hopper:
This environment is based on the work 663 The HalfCheetah is 2- dimensional robot consisting of 9 body parts and 8 joints connecting them (including two paws). The goal is to apply torque on the joints to make the cheetah run forward (right) fast as possi- ble, with a positive reward allocated based on the distance moved forward and a negative reward allocated for moving backward. The torso and head of the cheetah only be applied on the other 6 joints over the front and back thighs (connecting to the torso), shins (connecting to the thighs), and feet (connecting to the shins). More details can be found in httss//gymnasium.
D4RL- Half Cheetah:
fixed, and the torque can
F.1.2 Multi Agent Scenarios
Predator-prey maze version: agents must reach the goal simultaneously to complete this task while avoiding collisions between agents and the obstacles. Note that these tasks are quite challenging: (1) We increase the maze dimension and place the high-reward goal at the corner of the maze surrounded by high-penality obstacles which are harder for agents to reach; (2). agents' observations do not include any information about the goal and other agents, so they need to grow DTTs iteratively based on their joint action value vectors and get the information about their joint observation space to find the rewarding state.
Each time an agent covers with a target, the agent is rewarded with +71, if the agents reach the target at the same time, they will be given group reward +72 or +ra based on the rewarding target type (higher rewarding state or lower rewarding state). The agents are also given a group reward En' min(d(p,.. 4 ke {L....,K],,n NN), where the p,, and qg the coordinates
26

---

of agent n and target k. The reward of the agents will be decreased for increased distance from targets.
F.2 Empirical Performance Comparison between RGMDT and DRL
We show empirical performance comparisons between RGMDT and DRL in Figure (single-agent task) and Figure E (multi-agent task) in the main body. We also add Figure [ in Appendix (.8.2 show that the return gap is bounded by the average cosine distance as quantified by our analysis and theorems and diminishes as the average cosine distance decreases due to the use of more leaf nodes (i.e., more action labels leading to lower clustering distance).
1. Figure 2
Shows RGMDT's enhanced performance with increasing leaf nodes, nearing optimal levels of RL with L = or more. This supports Theorem 4.4|s prediction that return gaps decrease the average cosine distance is minimized.
2. Figure 4 Confirms RGMDT's s performance improves with more leaf nodes in the multi- agent scenario, achieving near-optimal levels with |L] = more, consistent with the findings of Theorem 4.4 and supporting its application in multi-agent settings as noted in
Remark 4.5
3. Figure 5 Plots average cosine distance and the return gap between RGMDT and the expert DRL policies for different leaf node counts (8, 16, 32). The results, analyzed from the last 30 episodes post-convergence, justify Theorem $ analysis: the return gaps are indeed bounded by O(Ve/(logz the average cosine distance over all clusters decreases due to using more leaf nodes, which also validates the results in Remark 4.5
1) max)) and the average return gap diminishes as
F33
Comparing RGMDT with Simple DT Baselines
We include the Imitations DT baseline using CART, directly trained on the RL policy's 's actions and observations without resampling. The observations and actions are features and labels respectively. The results (Fig. Fig. 4 Table. Table.. ( demonstrate that RGMDT's superior performance becomes more noticeable with a limited number of leaf nodes since with fewer leaf nodes (or a more complex environment), some of the decision paths must be merged and some actions would change. RGMDT minimizes the impact of such changes on return.
F44 Other Interpretable RL baselines
RGMDT is the first work for multi-agent DT with performance guarantees. Since agents' decisions jointly affect state transition and reward, converting each agent's decision separately into DTTs may not work and accurately reflect the intertwined decision-making process. Our work is able to solve this problem and provide guarantees. Thus, we didn't 't find other interpretable multi-agent baselines with performance guarantees except for MA-VIPER and its baselines which have been compared with RGMDT in current evaluations.
F.5 Other Evaluating Environments
When evaluating RGMDT, reviewed how other DTT-baed models were tested. The VIPER 3 evaluated the algorithm in Atari Pong, and cart-pole environments, which are much simpler environ- ments than ours, they also evaluated the algorithm in Half-cheetah tasks which are included in our D4RL tasks. The MA-VIPER [48] only evaluated their DT algorithms in MPE environment [40] for multi-agent scenarios, which we implement the same Predator-prey prey maze tasks using the same settings. We note that most existing papers evaluate DT-based algorithms only on classification datasets B3 72. contrast, our evaluation includes D4RL environments, which is a more complex environment widely used for evaluating RI. algorithms (and not just D'T-based methods) 65). Our evaluations show that the extracted DT's (both single- and multi-agent) able to achieve similar performance comparable to DRI. algorithms on complex D4RI. environments. In the future, we could consider applying RGMDT to simulated autonomous driving and healthcare scenarios where insight into a machine's makingg process is important, and human operators must be able to follow step-by-step procedures that can be provided with DT.
F.6 Impact of Leaf Node Counts on RGMDT's Performance
Remark shows that Theorem 4.4 holds for any arbitrary finite number of leaf nodes L. Furthermore, increasing the maximum number of leaf nodes L reduces the average cosine distance (since more
27

---

clusters are formed) and, consequently, a reduction in the return gap due to the upper bound derived in Theorem 4.4 Evaluation results for varying numbers of leaf nodes: Specifically, in Figure. (single-agent tasks), Figure. Figuue 4 (multi-agent tasks), and Table. (D4RL. tasks) we show RGMDT's performance improves with an increasing number of leaf nodes, which is consistent with the findings of Theorem 4.4 and Remark
4.5 in both single- and multi-agent tasks.
F.7 Comparison with Other Interpretable RL Methods
RGMDT is the first multi-agent DT model with performance guarantees. Since the agent's 's decisions jointly affect state transition and reward, converting each agent's decision separately into DT's may not work and accurately reflect the intertwined decision-making process. RGMDT is able to solve this problem and provide guarantees. RGMDT offers a more interpretable form of policy representation by directly mapping observations to actions. This differs significantly from:
1. Reward Decomposition: While this method breaks down the reward function into compo- nents for clarity, lacks in providing straightforward explanation of decision processes or translating complex data into a simple, explainable policy structure like DTs.
2. Option Discovery: It focuses on identifying sub-policies or "options" within complex RL policy.. These options can be seen as temporally extended actions, providing a higher- level understanding of the policy structure. However, it focuses on identifying such skill components, which could still be represented by deep skill policy, c.g., in deep option discovery, and is less interpretable than a decision tree, which provides clear decision paths based on observations.
F8 Addtional Ablation Studies
We added new set of experiments assess how errors of non-Euclidean clustering and return gaps influence the algorithm's 's performance,
F8.1
Experiment 1. Ablation Study on Non-Euclidea Clustering Error Impact
We conducted experiments for Ablation Study using two other clustering metrics Euclidean and Manhattan distances to replace the Non-Euclidean Clustering metrics cosine distance used in the original RGMDT. We also introduced noise levels from 0.0 0.6 simulate various environmental conditions and compared the performance of different clustering metrics across the same error levels to assess how each metric manages increasing noise.
Table. 3 shows that cosine distance exhibits high resilience, maintaining significantly higher rewards than the other metrics up an error level of 0.6, indicating robust performance. In contrast, Euclidean distance consistently underperformed, failing to meet targets even at zero error, highlighting its inadequacy for tasks requiring
Euclidean measures. Meanwhile, Manhattan distance performed better than Euclidean but was still inferior to RGMDT, with performance dropping as error increased, thus confirming Theorem 4.4, minimizing cosine distance effectively reduces the return gap. The ablation study confirms that non non-nonnneee Euclidean clustering errors significantly impact the performance, with RGMDT showing notable robustness, particularly under higher error conditions, highlighting its capacity to utilize the geometric properties of sampled Q-values for DT construction. This is because RGMDT aims to group the observations that follow the same decision path and arrive at the same leaf node (which is likely maximized with the same action, guided by action-values ) in the same cluster, therefore, non-cuclidean clustering metric cosine distance is more efficient here (proven in Theorem 4.4).
F88.2 Experiment Impact of Return Gaps Errors on Performance
The goal of RGMDT is to minimize return gaps. So we could only conduct an additional experiment demonstrating that return gaps decrease RGMDT minimizes cosine distance. Since minimizing return gaps is our primary objective, their initial measurement isn't possible until after RGMDT training.
Directly minimizing the return gap is challenging, but Theorem 4.4 proves that it is bounded by O( ///////lggg.... + 1) 1)nQQmax), where e the average cosine-distance within each cluster. This finding motivates the RGMDT, which reduces the return gap by training non-Eut Euclidean clustering
28

---

network to optimize e with cosine disttne loss. Thus, RGMDT effectively minimizes the return gap error.
Fig. in the rebuttal PDF shows the correlation between average cosine-distance e and the return gap across clusters with 8, 16, and 32 leaf nodes. We calculated the return gap using mean episode rewards from the last 30 episodes after RGMDT and expert RL policies converged. The findings justify Theorem 4.4 ss analysis that the return gap decreases as reduces with more leaf nodes, validating the results in Remark 4.5
F.9 Interpretability of RGMDT
Note that RGMDT is the first work for multi-agent DT with performance guarantees. Since the agents' decisions jointly affect state transitions and rewards, converting each agent's decision separately into decision trees may not accurately reflect the intertwined decision-making process. Our work addresses this problem and provides theoretical guarantees.
RGMDT enhances the interpretability of DRL policies by translating them into DT structures. Small decision trees (with tree depth less than 6) are generally considered interpretable because they provide a clear, step-by-step representation of decision- maasiinnmmaingg processes based on input features, as further discussed in 48
Key aspects enhancing RGMDT's interpretability include:
1. Clear Decision Paths: DTTs offer explicit paths from root leaf nodes, each linked specific action, unlike the complex approximations in DRL policies.
2. Quantifiable Performance Guarantee: RGMDT quantifies the return gap between the DRL and DT policies, ensuring reliable measure of how closely the DT mimics the DRL policy,
3. Interpretability at Different Complexity Levels: RGMDT can generate a DT with a return gap guarantee for any decision tree size, providing trade-off between interpretability and accuracy. A smaller DT offers better interpretability at the cost of a higher return gap. Regardless, our method ensures theoretical guarantees on the return gap. According to [48]. DTs with a tree depth less than 6 (2 = 64 leaf nodes) can be considered naturally interpretable. Notably, with only more than L optimal performance of the expert DRL policy in both single-agent and multi-agent scenarios, while other baselines fail to complete the task (as supported by results Figure and Figure 4).
leaf nodes, RGMDT achieves near-
4. Cluster-Based Approach: RGMDT clusters observations into different decision paths in the DT, grouping similar decisions and making it easier to understand which types of observations lead specific actions.
We have provided some DT visualizations of maze tasks in Appendix F.11 illustrating how agents make decisions based on their observations (e.g., location coordinates this task). more concrete example is given in Figure 7 to Figure 10 Appendix FF.1 the features include agents' X and Y coordinates. For this 4-node DT, the right decision path shows that if the agent's coordinate is larger than 0.4652, the decision goes to the right node. By further splitting based the agent's coordinates (if X is larger than 0.0125), two decision paths indicate taking actions to go 'right' (X < 0.0125) or 'up' (X > 0.0125).
E.10 Additional Experiments on Interpretability
To illustrate non-euclidean clustering labels interpretation, we run RGMDT on two-agent grid-world maze for casy visualization and add four more figures (Fig. 6 to further visualize the relationships between: 1. action and labels; 2. position and labels, since DT generation is guided by non-euclidean clustering results.
Fig. shows that the non-euclidean clustering labels used in RGMDT are naturally interpretable. We explored the relationship between non oon-uuclddean clustering labels, agent positions, and actions. Fig. 6a and Fig. show how agent positions during training correlate with clustering labels: 'blue', "green", 'pink', and 'orange' indicate labels '0', '1', '2', and '3', respectively. Agents near the high-reward target are typically labeled '1', while those near the lower-reward target get labeled '2'. Additionally, Fig. 66 and Fig. (dd demonstrate that agents take actions 'down', 'up", 'right', and 'left' conditioned on specific labels '0" '1', '2', '3', respectively. Putting these together, when an RGMDT
29

---

Table 3: The superior performance of RGMDT when using non-Euclidean cosine-distance metrics indicates that the algorithm effectively utilizes the geometric properties of sampled Q-values for DT construction. This is supported by analysis which links RGMDT's robustness to its ability to minimize the return gap using cosine distance. This advantage becomes particularly evident conditions, where traditional Euclidean and other non-Euclidean metries fail.
under higher As errors increase, a performance drop across all metrics is typical, highlighting the importance of -on-Euclidean clustering. RGMDT's design to cluster observations following similar decision paths into the same leaf nodes-typicalle maximized by the same actions as guided by the action-value (ss, ennenheccss its effectiveness. This approach confirms that the cosine-distance metric is more suitable for maintaining performance in the face of clustering errors, as proven in Theorem 4.4
Clustering Metrics
Error Level
If Reached Target
Mean Reward
Non-Euclidean (RGMDT)
0.0
Yes
11.65 + 0.88
Non-Euclidean (RGMDT)
0.1
Yes
9.25 + 0.65
Non-Euclidean (RGMDT)
0.2
Yes
8.67 = 0.77
(RGMDT)
0.4
Yes
6.34 = 0.58
-on-Euclidean (RGMDT)
0.6
No
2.29 = 0.54
Euclidean
0.0
No
3.66 + 1.03
Euclidean
0.1
No
3.32 + 0.75
Euclidean
0.2
No
2.82 0.82
Euclidean
0.4
No
2.03 0.65
Euclidean
0.6
No
-1.62 0.92
Manhattan
0.0
Yes
5.67 + 0.93
Manhattan
0.1
No
4.52 - 1.22
Manhattan
0.2
No
3.84 + 0.84
Manhattan
0.4
No
2.13 + 0.75
Manhattan
0.6
No
0.92 + 1.22
agent approaches the high-reward target, the position will be labeled as '1', instructing other agents to move 'up' or 'left', which effectively guides other agents to approach the high-reward target located at the upper left corner of the map, influencing strategic movements towards targets.
F.11 Decision Tree Visualization
30

---

35
0.06
Return Gap (left)
30
Average Cosine Distance
Avg Cos Dis (right)
0.05
0.0415
25
Return Gap
0.0372
0.04
20
15.192
0.03
15
0.0207
8.289
0.02
2.510
0.01
0.00
8 nodes
16 nodes Number of Leaf Nodes
32 nodes
Figure The return gap (left) is bounded by average cosine distance (right) and diminishes as average cosine distance (right) decreases due to the increase of the maximum number of leaf nodes.
31

---

'1'
'1'
'0'
'1'
'2'
'2'
'2'
'1'
'2'
'0'
'0'
'0'
'0'
'3'
'2'
'0'
'3'
(a) Lahel- (agent 1)
(b) Lahel-position (agent 2)
Non-Euclidean Clustering Label
Agent
Non-Eun Nun-Euclidean Clustering Label
Agent 2
0.150
0.15
0.125
0.100
0.10
0.075
~
0.050
0.05
m.
0.025
Down
Left
Right
Up
Down
Left
Right
Up
(c) Label-action (agent 1)
(d) Label-action (agent 2)
Figure 6: Interpretable Non-Euclidean Clustering Labels: (a)-(b): The positions are more likely to be labeled as when closer to the higher-reward target (circle), while more likely be labeled as '2' when closer to the lower-reward target (triangle): (c)-(d): both agents are more likely to take action 'down', 'up', 'right', 'left' conditioned labels '0', '1', 22', and '3', respectively.
32

---

10
down
up
right
left
0.4625
0.9125
agent Y coordinate
0.0125
0.9125
agent X coordinate
0.01250.
1625
0.9125
agent coordinate
n=18 down
n= left
right
n=37
Figure 7: Visulazing the RGMDT decision path for Hard Maze with the maximum number of leaf nodes equals 4.
33

---

right left
0.00120 1992
0.7512
agent coordinate
0.001.20110
1982
0.7812
agent coordinate
agent coordinate
down
dowi
0/0112
CA4622
0.7812
0.0312
0.4082 coordinate
0.7912
agent Y coordinate
0..01.20..1
7812
up
0.2012
bu53000 7812
agent coordinate
agent coordinate
UP
left
down
right
Figure 8: Visulazing the RGMDT decision path for Simple Maze with the maximum number of leaf nodes equals 8.
34

---

coordrate
coordinate
agent Y coordinato
agent X coordinate
agent
agenixX coordinate
agent Y coordinato
a201 spent Y cocrcinaaae
apont X ecordinate
agenrt X coordir
3gont coood rato
Figure 9: Visulazing the RGMDT decision path for Medium Maze with the maximum number of leaf nodes equals 16.
35

---

Figure 10: Visulazing the RGMDT decision path for Hard Maze with the maximum number leaf' nodes equals 32.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction state the claims made, including the contributions made in the paper and important assumptions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed in Sec. about assumptions and how to address them.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
37

---

Answer: [Yes]
Justification: We provide the full assumptions and proof of all theoretical contributions either in the main paper or in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide all the information needed to reproduce the results presented in this paper together with the source code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
38

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all the information needed to reproduce the results presented in this paper together with the source code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Policy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwppppgpuuiiieeeee /otpc//uuudeeeooeuuubiiiiii SroodeSubiissi.e ssiiiiolcccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We explained all the details training settings in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We include the error bars in the experiment results section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
39

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We explained all the details on training settings in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp///aaouus..../p/.lll//taaa
Answer: [Yes]
Justification: We conducted the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discussed the potential positive societal impacts and negative societal impacts of the work performed at the beginning of the appendix.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
40

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We believe this paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
41

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "adOrCR1qDI", "reviewer": "Reviewer_p7eT", "summary": "This paper considers extracting decision tree (DT) based policies from DRL policies for the purpose of interpretability. The authors present an upper bound on the return gap of the oracle policy and the DT policy, which helps formulate the DT extraction problem into a non-euclidean clustering problem. The authors then propose a multi-agent variant with an iteratively-grow-DT procedure, and propose a practical algorithm (RGMDT) which outperform heuristic baselines in the maze the D4RL benchmark.", "questions": "- Are there any other competitive (DT-based or non DT-based) baselines for interpretable RL not covered in the current experiments of the paper? Are there any other more realistic environments beyond maze and D4RL that can be used?\n- Can the authors comment on the computational complexity (in terms of time and space) of the proposed algorithm? How scalable is the proposed algorithm to real-world applications, e.g., robotics?", "limitations": "N/A.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Methodology: Using clustering to reformulate DT extraction is a fresh perspective.\n- Theoretical guarantee: The paper provides a formal guarantee on the proposed algorithm.\n- Flexibility: The proposed algorithm is applicable in both single-agent and multi-agent settings.\n- Experiments: The paper presents concrete performance improvement over selected baselines.", "weaknesses": "- Presentation: I suggest the authors to enhance the clarity of the writing. More intuitive illustrations can greatly enhance the paper's impact. Also, it would be helpful to move some variants of figures in Appendix E2 in the main body of the paper to better illustrate the idea. \n- Related works: I suggest the authors to add a section, either in the main body or the appendix, to sufficiently discuss existing works including interpretable RL. For example, some relevant early works, e.g., [Frosst & Hinton (2017)](https://arxiv.org/pdf/1711.09784) and [Ding et al. (2021)](https://arxiv.org/pdf/2011.07553), are missing in the paper.\n\nReferences:  \n[1] Frosst, Nicholas, and Geoffrey Hinton. \"Distilling a neural network into a soft decision tree.\" arXiv preprint arXiv:1711.09784 (2017).  \n[2] Ding, Zihan, Pablo Hernandez-Leal, Gavin Weiguang Ding, Changjian Li, and Ruitong Huang.  \"Cdt: Cascading decision trees for explainable reinforcement learning.\" arXiv preprint arXiv:2011.07553 (2020).  \n[3] Milani, Stephanie, Nicholay Topin, Manuela Veloso, and Fei Fang. \"Explainable reinforcement learning: A survey and comparative review.\" ACM Computing Surveys 56, no. 7 (2024): 1-36.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Interpretability Presentation\nWe will **move DT visualization to the main body** to better illustrate RGMDT's interpretability. To illustrate non-euclidean clustering labels interpretation, we run RGMDT on a 2-agent grid-world maze for easy visualization and **add four additional figures** (**Fig.2 in the rebuttal PDF**) to visualize the relationships between: **1.action and labels**; **2. position and labels**, since RGMDT's generation is guided by non-euclidean clustering results.  \n**Fig.2 in rebuttal PDF** shows that the non-euclidean clustering labels used in RGMDT are naturally **interpretable**. We explored the relationship between position- and action-labels. **Fig.2(a)** and **Fig.2(b)** show how agent positions during training correlate with clustering labels: 'blue', 'green', 'pink', and 'orange' indicate labels '0', '1', '2', and '3', respectively. Agents near the high-reward target are typically labeled '1', while those near the lower-reward target are labeled '2'. Additionally, **Fig.2(c)** and **Fig.2(d)** shows that actions such as 'down', 'up', 'right', 'left' align with specific labels, influencing strategic movements towards objectives. For example, an agent labeled '1' near a high-reward target suggests movements 'up' or 'left', guiding others towards the high-reward target in the upper left corner of the map.\n# Interpretable RL Related Work \nWe **initially included a discussion** on interpretable RL but removed it **due to page limit**. Due to 6000-character limit per response, we can't include it here. **Please see the global rebuttal for the related work section ([1-5] for interpretable RL, [6-14] for tree-based models, [6],[12],[14] for 3 mentioned references).**\n# Other Interpretable RL baselines\nRGMDT is the first work for **multi-agent DT with performance guarantees**. Since agents' decisions jointly affect state transition and reward, converting each agent's decision separately into DTs may not work and accurately reflect the intertwined decision-making process.  Our work is able to solve this problem and **provide guarantees**. Thus, we **didn't find other interpretable multi-agent baselines with performance guarantees** except for MA-VIPER and its baselines which **have been compared with RGMDT in current evaluations**.\n# Other Evaluating Environments\nWhen evaluating RGMDT, we reviewed **how other DT-based models were tested**. The VIPER _O.Bastani et al. Verifiable reinforcement learning via policy extraction.NeurIPS,2018_ evaluated the algorithm in **Atari Pong, cart-pole** environments, which are **much simpler environments than ours**, they also evaluated the algorithm in Half-cheetah tasks which **is included in our D4RL tasks**. The MA-VIPER _S. Milani et al. Maviper: Decision tree policies for multi-agent RL,2022_ only evaluated their DT algorithms in **MPE environment** _R. Lowe et al. Multi-agent actor-critic for mixed environments.NeurIPS,2017_ **for multi-agent scenarios**, in which we implement the **same Predator-prey** maze tasks **use the same settings**, see experimental details in **Appendix F.1.2**. We note that most existing papers evaluate DT-based algorithms **only on classification datasets** _X. Hu et al. Optimal sparse decision trees. NeurIPS,2019; H. Zhu et al. Learning optimal multivariate decision trees. NeurIPS,2020_. In contrast, our evaluation includes **D4RL environments**, which is **a more complex environment widely used for evaluating RL** algorithms (and not just DT-based methods) _H. Xu et al. A policy-guided imitation approach for offline RL.NeurIPS,2022_. Our evaluations show that the extracted DTs (both single- and multi-agent) is able to achieve similar performance comparable to DRL algorithms on complex D4RL environments. **In the future**, we could consider applying RGMDT to simulated **autonomous driving** and **healthcare** scenarios where the insight into a machine’s decision-making process is important and human operators must be able to **follow step-by-step procedures that can be provided with DT**. \n# Computational Complexity\n**Since we grow RGMDT with a small number of leaf nodes $L$, it's time- and space-efficient compared to other large DTs and DNNs**. **(1).Time Complexity**: It is determined by the Non-Euclidean clustering and DT construction steps, estimated as $O(T \\cdot n^2 \\cdot \\log L)$, where $T$ represents the number of iterations of clustering for convergence, $n$ is the number of Q-value samples, and $L$ is the maximum number of leaf nodes. This reflects the intensive computation required for non-Euclidean distance calculations and iterative tree growth. **(2).Space Complexity**: It's $O(K(n \\cdot d + L))$. This accounts for the storage of $n$ Q-value samples each with $d$ dimensions and the DT structures with $L$ leaf nodes per tree across $K$ agents.\n# Real-World Applications\nThe **superior performance** of RGMDT with a small number of leaf nodes **enhances its compactness and simplifies its implementation in practical scenarios**. Compared to DNNs, its **simpler DT structure** requires **less computational and memory resources** during inference, making it well-suited for **resource-limited environments** in real-world applications like **robotics**, **network security**, and **5G network slicing resource management**. **For example**, DTs have been implemented in memristor devices to support real-time intrusion detection in scenarios requiring low latency and high speed (_Chen, J., et al. \"Ride: Real-time intrusion detection via explainable machine learning implemented in a memristor hardware architecture.\" 2023 IEEE DSC_). RGMDT's **interpretable structure** makes it more suitable for memristor-based hardware implementations in resource-constrained environments for **network intrusion detection achieves detection speeds of microseconds, together with significant area reduction and energy efficiency**, with **performance guarantee** that previous DTs fail to provide.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eAP0jv4Cc2", "reviewer": "Reviewer_uDjD", "summary": "The authors proposes a method called Return-Gap-Minimization Decision Tree (RGMDT) to extracting interpretable decision tree policies from learned parametric RL policies. The authors first propose a method to quantify the return gap between an oracle RL policy and its extracted decision tree policy, which provides a guarantee for the performance of the DT policy. The RGMDT is built upon the idea to minimizing this gap, which works by recasting the DT extraction problem as an iterative non-euclidean clustering problem. In this clustering problem, the goal is to clustering different observations into different decision tree paths, where the leaf nodes are corresponding to the action.  Additionally, the authors also extend the algorithm to the multi-agent setting and provide theoretical analysis for the performance guarantee as well.  Empirically, RGMDT performs much better than DT but being more interpretable than RL polices.", "questions": "See weakness.", "limitations": "See weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed algorithm is theoretically sound and the analysis is well-executed. The extension to the multi-agent is great, though I would say it has very limited applicability given that multi-agent RL seem still not work well in practice. The experiments support the claim and demonstrate the effectiveness of the proposed method.", "weaknesses": "- 1. Although the authors have compared RGMDT to several DT extraction baselines, it doesn't compare with such a baseline: train a simple decision tree on the RL policy's action and observations. This should be doable and is an important baseline to compare against.\n\n\n- 2. Some ablation studies are missing. For example, it would be great if the authors could ablate how the error of non-Euclidean clustering and the return gap impact the final performance. How sensitive is the algorithm to these errors?\n\n\n**Questions**:\n\n- a. How does the performance of RGMDT change with the size of the DT (like, the maximum number of leaf nodes)? The paper shows results for different maze sizes, but it would be nice to see the trend more systematically.\n\n- b. How does RGMDT compare to other interpretable RL approaches, such as reward decomposition or option discovery?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Query on Simple DT Baselines\nWe include the requested **Imitations DT** baseline using **CART**, directly trained on the **RL policy's actions and observations** (lines 265-271) as described, without resampling. The observations and actions are **features** and **labels** respectively. The **results (Fig.1-4, Table.1-2)** demonstrate that RGMDT's superior performance becomes more noticeable with a limited number of leaf nodes since with fewer leaf nodes (or a more complex environment), some of the decision paths must be merged and some actions would change. RGMDT minimizes the impact of such changes on return. \n# Query on Ablation Studies\nWe added **a new set of experiments** to assess how errors of non-Euclidean clustering and return gaps influence the algorithm’s performance, detailed in **Table.1** and **Fig.1** in the **rebuttal PDF file**.\n## Experiment 1: Ablation Study on Non-Euclidean Clustering Error Impact\nWe conducted experiments for **Ablation Study** using two other clustering metrics **Euclidean and Manhattan distances** to replace **the Non-Euclidean Clustering metrics cosine distance** used in the original RGMDT. We also introduced **noise levels from 0.0 to 0.6** to simulate various environmental conditions and compared the performance of different clustering metrics across the same error levels to assess how each metric manages increasing noise. \n\n**Table.1 in the rebuttal PDF file** shows that **cosine distance** exhibits high resilience, maintaining **significantly higher rewards** than the other metrics up to an error level of 0.6, indicating **robust** performance. In contrast, **Euclidean distance** consistently underperformed, failing to meet targets even at zero error, highlighting its inadequacy for tasks requiring non-Euclidean measures. Meanwhile, **Manhattan distance** performed better than Euclidean but was still inferior to RGMDT, with performance dropping as error increased, thus **confirming Thm. 4.4** that **minimizing cosine distance effectively reduces the return gap**. The ablation study confirms that **non-Euclidean clustering errors** significantly impact the performance, with **RGMDT showing notable robustness**, particularly **under higher error conditions**, highlighting its capacity to utilize the geometric properties of sampled Q-values for DT construction. This is because RGMDT aims to group the observations that follow the same decision path and arrive at the same leaf node (which are likely maximized with the same action, guided by action-values $Q(s,a)$) in the same cluster, therefore, **non-euclidean clustering metric cosine-distance** is more **efficient** here (**proven in Thm. 4.4**). \n## Experiment 2: Impact of Return Gaps Errors on Performance\n**The goal of RGMDT is to minimize return gaps**. So we could only conduct **an additional experiment** demonstrating that **return gaps decrease as RGMDT minimizes cosine-distance**. Since minimizing return gaps is our **primary objective**, their initial measurement isn't possible until after RGMDT training.\n\nDirectly minimizing the **return gap** is challenging, but **Thm. 4.4** proves that it is bounded by $O(\\sqrt{\\epsilon/(\\log_{2}(L+1) - 1)}Q_{\\rm max})$, where $\\epsilon$ is the average **cosine-distance** within each cluster. This finding motivates the RGMDT, which **reduces the return gap** by training a non-Euclidean clustering network $g$ to optimize $\\epsilon$ **with a cosine-distance loss**. Thus, RGMDT effectively **minimizes the return gap error**.\n\n**Fig.1 in the rebuttal PDF** shows the correlation between **average cosine-distance $\\epsilon$** and the return gap across clusters with 8, 16, and 32 leaf nodes. We calculated the return gap using mean episode rewards from the last 30 episodes after RGMDT and expert RL policies converged. The findings **justify Thm. 4.4's analysis** that the return gap decreases as $\\epsilon$ reduces with more leaf nodes, **validating the results in Remark 4.5**\n# Impact of Leaf Node Counts on RGMDT's Performance\n**Remark 4.5 (line 200)** shows that **Thm.4.4** holds for **any arbitrary finite number of leaf nodes $L$**. Furthermore, increasing the maximum number of leaf nodes $L$ reduces the average cosine distance (since more clusters are formed) and, consequently, a reduction in the return gap due to the upper bound derived in Thm.4.4.\n**Evaluation results for varying numbers of leaf nodes:** Specifically, in **Fig.2 (single-agent tasks), Fig.3-4 (multi-agent tasks), and Table 1 (D4RL tasks)** we show **RGMDT's performance improves with an increasing number of leaf nodes**, which is consistent with the findings of Thm.4.4 and Remark 4.5 **in both single- and multi-agent tasks**.  \n# Comparison with Other Interpretable RL Methods\nRGMDT is the **first multi-agent DT model with performance guarantees**. Since the agent's decisions jointly affect state transition and reward, converting each agent's decision separately into DTs may not work and accurately reflect the intertwined decision-making process. RGMDT is able to solve this problem and provide guarantees.\nRGMDT offers a more interpretable form of policy representation by directly mapping observations to actions. This differs significantly from:\n1. **Reward Decomposition**: While this method breaks down the reward function into components for clarity, **it lacks in providing a straightforward explanation of decision processes or translating complex data into a simple, explainable policy structure like DTs**.\n2. **Option Discovery**: It focuses on identifying sub-policies or \"options\" within a complex RL policy. These options can be seen as temporally extended actions, providing a higher-level understanding of the policy structure. However, it focuses on identifying such skill components, **which could still be represented by a deep skill policy, e.g., in deep option discovery**, and is less interpretable than a decision tree, which provides clear decision paths based on observations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1dhxB4LfeP", "reviewer": "Reviewer_Cxpi", "summary": "This work provides an upper bound on the return gap between the DRL policy and its extracted DT policy. Based on this, it proposes the RGMDT algorithm with a simple design that can be extended to multi-agent settings using an iteratively-grow-DT procedure. The RGMDT algorithm outperforms other DT-based algorithms in the D4RL tasks.", "questions": "1. This work provides an upper bound on the return gap between the DRL policy and its extracted RGMDT from a theoretical perspective. However, how does the empirical performance compare?\n\n2. My main concern is how RGMDT can interpret and understand the policy of DRL. How does RGMDT enhance the interpretability of DRL policies?", "limitations": "There could be more discussion to the limitations", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work proposes the Return-Gap-Minimization Decision Tree (RGMDT), which minimizes the return gap between itself and the DRL policy for any given size.\n\n2. The RGMDT can be extended to a multi-agent framework using an iterative non-Euclidean clustering formulation.\n\n3. The RGMDT achieves more promising performance than other DT-based algorithms in D4RL tasks.", "weaknesses": "One of the motivations of this work is that DRL policies cannot be interpreted and understood well, and that decision trees (DT) could help improve interpretability. However, I don't see how the proposed method, RGMDT, enhances interpretability. This work seems to only demonstrate the superior performance of RGMDT compared to other DT-based algorithms, without addressing how it aids in the interpretability of DRL policies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Interpretability of RGMDT\nNote that RGMDT is **the first work for multi-agent DT with performance guarantees**. Since the agent's decisions jointly affect state transition and reward, converting each agent's decision separately into decision trees may not work and accurately reflect the intertwined decision-making process.  Our work can solve this problem and provide guarantees.\n\nRGMDT enhances the interpretability of DRL policies by translating them into DT structures. **Small Decision trees (tree depth less than 6) are generally considered interpretable** because they provide a clear, step-by-step representation of decision-making processes based on input features, as further discussed in [1] and will be added in our final version.\n\n**Key aspects enhancing RGMDT's interpretability include**:\n1. **Clear Decision Paths**: DTs offer **explicit paths** from the root to leaf nodes, each **linked to a specific action**, unlike the complex approximations in DRL policies.\n2. **Quantifiable Performance Guarantee**: RGMDT **quantifies the return gap** between the DRL and DT policies, ensuring **a reliable measure** of how closely the DT mimics the DRL policy.\n3. **Interpretability at different complex levels**: Since RGMDT can generate a DT with a return gap guarantee for **any decision tree size**, it provides a **trade-off between complexity level and accuracy of interpretability**. A smaller DT can offer better interpretability at the cost of a higher return gap. In any case, our method ensures theoretical guarantees on the return gap. According to [1], **DTs with tree depth less than 6 ($2^6=64$ leaf nodes) can be considered naturally interpretable**. Notably, **with only more than $|L|=4$ leaf nodes**, **RGMDT achieves near-optimal performance of the expert DRL policy** in **single-agent** and **multi-agent** scenarios while **other baselines fail to complete the task** (**supported by results in Fig.2 and Fig.4**). \n4. **Cluster-Based Approach**: The method's foundation in **clustering observations into different paths** in the DT helps **group similar decisions**, making it easier to **understand which types of observations lead to which actions**.\n\nWe have provided some **DT visualization** of maze tasks in **Appendix. E.2**. It shows **how agents make decisions based on their observations** (location's coordinates in this task). \nGive a more **concrete example**, like in **Fig.5, Appendix E.2**, the features include agents' X and Y coordinates, For this 4-node DT, the right decision path shows that if the agent's Y coordinate is larger than $0.4652$, the decision goes to the right node. By further splitting it according to the agent's X coordinates (if $X$ is larger than $0.0125$), two decision paths are indicating taking actions going 'right' ($X \\leq 0.0125$) or going 'up' ($X > 0.0125$). \n\n[1] Stephanie Milani, et al. Maviper: Learning decision tree policies for interpretable multi-agent reinforcement learning, 2022.\n\n# Additional Experiments on Interpretability\nTo illustrate **non-euclidean clustering labels interpretation**, we run RGMDT on a two-agent grid-world maze for easy visualization and **add four more figures** (see **Fig.2 in the rebuttal PDF file**) to further visualize the relationships between: **1.action and labels**; **2.position and labels**, since DT generation is guided by non-euclidean clustering results.  \n\n**Fig.2 in rebuttal PDF** shows that the non-euclidean clustering labels used in RGMDT are naturally **interpretable**. We explored the relationship between non-Euclidean clustering labels, agent positions, and actions. **Fig.2(a)** and **Fig.2(b)** show how agent positions during training correlate with clustering labels: 'blue', 'green', 'pink', and 'orange' indicate labels '0', '1', '2', and '3', respectively. Agents near the high-reward target are typically labeled '1', while those near the lower-reward target get labeled '2'. Additionally, **Fig.2(c)** and **Fig.2(d)** demonstrate that agents take actions 'down', 'up', 'right', 'left' conditioned on specific labels '0', '1', '2', '3', respectively. Putting these together, when an RGMDT agent approaches the high-reward target, the position will be labeled as '1', instructing other agents to move 'up' or 'left', which effectively guides other agents to approach the high-reward target located at the upper left corner of the map, influencing strategic movements towards targets\n\n# Empirical Performance Comparison between RGMDT and DRL\nWe show empirical performance comparisons between RGMDT and DRL in **Fig.2 (single-agent task)** and **Fig.4 (multi-agent task)** in the main body. \nWe also add **Fig.1 in the rebuttal PDF** to show that **the return gap is bounded by average cosine distance** - as quantified by our analysis and theorems - and diminishes as average cosine distance decreases due to the use of more leaf nodes (i.e., more action labels leading to lower clustering distance).\n1. **Fig.2**: Shows RGMDT's enhanced performance with increasing leaf nodes, nearing optimal levels of RL with $|L|=4$ or more. This supports Thm.4.4's prediction that return gaps decrease as the average cosine distance is minimized.\n2. **Fig.4**: Confirms RGMDT's performance improves with more leaf nodes in the multi-agent scenario, achieving near-optimal levels with $|L|=4$ or more, consistent with the findings of Thm.4.4 and supporting its application in multi-agent settings as noted in Remark.4.5.\n3. **Fig.1 in rebuttal PDF**: Plots average cosine distance and **the return gap between RGMDT and the expert DRL policies** for different leaf node counts (8, 16, 32). The results, analyzed from the last 30 episodes post-convergence, justify Theorem 4.4's analysis: the return gaps are indeed bounded by $O(\\sqrt{\\epsilon/(\\log_{2}(L+1) - 1)}nQ_{\\rm max})$, and the average return gap diminishes as the average cosine-distance over all clusters decreases due to using more leaf nodes, which also validates the results in Remark 4.5.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Three more experiments are added in PDF
# Response to Reviewer p7eT's Query on the Interpretable RL Related Work
We have had a section discussing interpretable RL in the related work section which includes all the three mentioned references (**[6],[12],[14]**), but we deleted it due to the page limit. We will add back the following paragraph **discussing Interpretable RL in the final version**.

**Effort on Interpretability for Understanding Decisions**: To enhance interpretability in decision-making models, one strategy involves crafting interpretable reward functions within inverse reinforcement learning (IRL), as suggested by **[1]**. This approach offers insights into the underlying objectives guiding the agents' decisions. Agent behavior has been conceptualized as showing preferences for certain counterfactual outcomes **[2]**, or as valuing information differently when under time constraints **[3]**. However, extracting policies through black-box reinforcement learning (RL) algorithms often conceals the influence of observations on the selection of actions. An alternative is to directly define the agent's policy function with an interpretable framework. Reinforcement learning policies have thus been articulated using a high-level programming language **[4]**, or by framing explanations around desired outcomes **[5]**, facilitating a more transparent understanding of decision-making processes.

**Interpretable RL via Tree-based models**: To interpret an RL agent, Frosst et al **[6]** explain the decisions made by DRL policies by using a trained neural net to create soft decision trees. Coppens et al. **[7]** propose distilling the RL policy into a differentiable DT by imitating a pre-trained policy. Similarly, Liu et al. **[8]** apply an imitation learning framework to the Q-value function of the RL agent. They also introduce Linear Model U-trees (LMUTs), which incorporate linear models in the leaf nodes. Silva et al. **[9]** suggest using differentiable DTs directly as function approximators for either the Q function or the policy in RL. Their approach includes a discretization process and a rule list tree structure to simplify the trees and enhance interpretability. Additionally, Bastani et al. **[10]** propose the VIPER method, which distills policies as neural networks into a DT policy with theoretically verifiable capabilities that follow the Dataset Aggregation (DAGGER) method proposed in **[11]**, specifically for imitation learning settings and nonparametric DTs. Ding et al. **[12]** try to solve the instability problems when using imitation learning with tree-based model generation and apply representation learning on the decision paths to improve the decision tree-based explainable RL results, which could achieve better performance than soft DTs. Milani et al. extend VIPER methods into multi-agent scenarios **[13]** in both centralized and decentralized ways, they also summarize a paper about the most recent works in the fields of explainable AI **[14]**, which confirms the statements that small DTs are considered naturally interpretable.

# References

[1] Chan, Alex J., and Mihaela van der Schaar. "Scalable Bayesian inverse reinforcement learning." arXiv preprint arXiv:2102.06483 (2021).

[2]Bica, Ioana, et al. "Learning" what-if" explanations for sequential decision-making." arXiv preprint arXiv:2007.13531 (2020).

[3] Jarrett, Daniel, and Mihaela Van Der Schaar. "Inverse active sensing: Modeling and understanding timely decision-making." arXiv preprint arXiv:2006.14141 (2020).

[4] Verma, Abhinav, et al. "Programmatically interpretable reinforcement learning." International Conference on Machine Learning. PMLR, 2018.

[5] Yau, Herman, Chris Russell, and Simon Hadfield. "What did you think would happen? explaining agent behavior through intended outcomes." Advances in Neural Information Processing Systems 33 (2020): 18375-18386.

[6]Nicholas Frosst and Geoffrey Hinton. Distilling a neural network into a soft decision tree. arXiv preprint arXiv:1711.09784, 2017.

[7]Youri Coppens, Kyriakos Efthymiadis, Tom Lenaerts, Ann Nowé, Tim Miller, Rosina Weber, and Daniele Magazzeni. Distilling deep reinforcement learning policies in soft decision trees. In Proceedings of the IJCAI 2019 workshop on explainable artificial intelligence, pages 1–6, 2019.

[8]Guiliang Liu, Oliver Schulte, Wang Zhu, and Qingcan Li. Toward interpretable deep reinforcement learning with linear model u-trees. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018, Dublin, Ireland, September 10–14, 2018, Proceedings, Part II 18, pages 414–429. Springer, 2019.

[9]Andrew Silva, Taylor Killian, Ivan Dario Jimenez Rodriguez, Sung-Hyun Son, and Matthew Gombolay. Optimization methods for interpretable differentiable decision trees in reinforcement learning. arXiv preprint arXiv:1903.09338, 2019.

[10]Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. Advances in neural information processing systems, 31, 2018.

[11]Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 627–635. JMLR Workshop and Conference Proceedings, 2011.

[12]Zihan Ding, Pablo Hernandez-Leal, Gavin Weiguang Ding, Changjian Li, and Ruitong Huang. Cdt: Cascading decision trees for explainable reinforcement learning. arXiv preprint arXiv:2011.07553, 2020.

[13]Stephanie Milani, Zhicheng Zhang, Nicholay Topin, Zheyuan Ryan Shi, Charles Kamhoua, Evangelos E. Papalexakis, and Fei Fang. Maviper: Learning decision tree policies for interpretable multi-agent reinforcement learning, 2022.

[14]Stephanie Milani, Nicholay Topin, Manuela Veloso, and Fei Fang. Explainable reinforcement learning: A survey and comparative review. ACM Computing Surveys, 56(7):1–36, 2024.

Meta-review: The paper introduces the Return-Gap-Minimization Decision Tree (RGMDT) algorithm, which extracts interpretable decision tree policies from deep reinforcement learning models, with a focus on multi-agent systems. The key innovation is the formulation of DT extraction as a non-Euclidean clustering problem, providing a formal guarantee on the return gap between the oracle policy and the extracted DT policy. This approach shows strong empirical performance, particularly in complex environments, and extends to multi-agent settings.

The paper is well-written and provides solid empirical evidence to support its claims. The theoretical foundation is robust, and the use of non-Euclidean clustering is a noteworthy contribution. However, reviewers highlighted some limitations, such as the need for clearer presentation and a more explicit focus on interpretability in practice. The initial absence of a comparison with simpler DT baselines was also noted but was addressed in the authors' rebuttal. 

Overall, the approach is innovative and effective, but further refinement in presentation and interpretability demonstration could enhance the paper's impact.
Decision: Accept (poster)