SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes
Authors: Xuyuan Xiong
Pedro Chumpitaz-Flores
Kaixun Hua
Cheng Hua
Venue: NeurIPS 2025 poster ()
Keywords: Decision Tree
Markov Decision Processes
Primary area: reinforcement_learning

Abstract: Interpretable reinforcement learning policies are essential for high-stakes decision-making, yet optimizing decision tree policies in Markov Decision Processes (MDPs) remains challenging. We propose SPOT, a novel method for computing decision tree policies, which formulates the optimization problem as a mixed-integer linear program (MILP). To enhance efficiency, we employ a reduced-space branch-and-bound approach that decouples the MDP dynamics from tree-structure constraints, enabling efficient parallel search. This significantly improves runtime and scalability compared to previous methods. Our approach ensures that each iteration yields the optimal decision tree. Experimental results on standard benchmarks demonstrate that SPOT achieves substantial speedup and scales to larger MDPs with a significantly higher number of states. The resulting decision tree policies are interpretable and compact, maintaining transparency without compromising performance. These results demonstrate that our approach simultaneously achieves interpretability and scalability, delivering high-quality policies an order of magnitude faster than existing approaches.

SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes
Xuyuan Xiong' Pedro Chumpitaz-Flores' Kaixun Hua Cheng Hua"
SShangaii Jiao Tong University University of South Florida
Abstract
Interpretable reinforcement learning policies are essential for high-stakes decision- making, yet optimizing decision tree policies in Markov Decision Processes (MDPs) remains challenging. We propose SPOT, a novel method for computing decision tree policies, which formulates the optimization problem as mixed- integer linear program (MILP). To enhance efficiency, branch-and-bound approach that decouples the MDP dynamics from tree-structure constraints, enabling efficient parallel search. This significantly improves runtime and scalability compared to previous methods. Our approach ensures that each iteration yields the optimal decision tree. Experimental results standard bench- marks demonstrate that SPOT achieves substantial speedup and scales to larger MDPs with significantly higher number of states. The resulting decision tree policies are interpretable and compact, maintaining transparency without compro- mising performance. These results demonstrate that our approach simultaneously achieves interpretability and scalability, delivering high-quality policies an order magnitude faster than existing approaches.
employ reduced-space
Introduction
In high-stakes or safety-critical domains, it is crucial that reinforcement learning (RL) policies be understandable by humans. Rather than relying on post-hoc explanations of opaque neural policies (e.g.. via LIME or SHAP), which can be incomplete or misleading [27), more direct approach is to learn inherently interpretable policies. Decision tree policies have attracted significant attention as suitable interpretable model class: they are simple, rule-based decision structures (threshold tests on state features leading to actions) that can represent non-linear behavior while remaining human- comprehensible. size-lime limited decision tree (bounded depth or number of leaves) is simulatable by person (one can manually follow the decision path) and decomposable (each decision node is an understandable rule).
Optimizing a policy constrained to be a decision tree is notoriously difficult 66. Rudin (2019) [9 identified optimizing sparse logical models such as decision trees as the foremost grand challenge in interpretable machine learning, emphasizing the distinction between inherently interpretable models and post-hoc explanation methods. Unlike differentiable function approximators, decision trees have a discontinuous, nin-diiferentiable structure that precludes straightforward gradient- based training. The space of possible trees grows combinatorially with depth, making brute-force search intractable except for very small cases. In supervised learning, greedy algorithms like CART [ can find reasonably good trees but are not guaranteed to find the optimal tree and may perform arbitrarily poorly in some cases. In the context of MDPs, an added challenge is that the policy's decisions in one state can influence the distribution optimize the tree static dataset of state-action examples; we must consider the global dynamics of the MDP when evaluating a tree policy. Overall, finding an optimal or ncar-optimal decision tree
states encountered elsewhere. This means we cannot simply
Corresponding Authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

policy in an MDP is combinatorial optimization problem on top of the usual RL complexities, and generally NP-hard. These challenges have motivated a variety of research efforts lear decision tree policies in a tractable way.
1.1 Interpretable Policy Learning in RL
I2
1
Goal
5, 0.6.7
y88
300
0.67
if 0.3.3
0.33
Start
0
#1100
0.33
0.67
1
21
(a)
(b)
Figure 1: Left: An interpretable policy learned by a decision tree of depth = 2. Right: Illustration of the Frozen Lake 4x4 (Stochastic) Markov Decision Process.
A number of prior works have proposed methods learn interpretable RL policies (decision trees or other rule-based representations) that balance interpretability and performance. These methods can be broadly categorized into: (1) relaxation-based or programmatic methods that directly train restricted policy, and (2) imitation and distillation methods that extract an interpretable policy from a complex one. We review key representatives of each approach:
One strategy is to soften or relax the tree representation to enable (approximate) gradient- based optimization. For example, Gupta et al. (2015) [12] introduced policy tree model that is optimized via policy gradient, using a smooth parameterization of the splitting criteria. These approaches embed the non-differentiable tree into continuous optimization, often achieving decent performance, but they do not guarantee a globally optimal tree. Another innovative idea is to reformulate the RL problem itself to enforce tree policy: Topin al. (2021) [22 proposed Iterative Bounding MDPs (IBMDPs), a meta-MDP construction in which any optimal policy corresponds to a decision tree for the original MDP. By solving the IBMDP with standard deep RL algorithms, they indirectly obtain a tree-structured policy. This approach allows using powerful function approximation during training while yielding discrete tree policy in the end, but the solution quality still depends on the RL training procedure. Finally, beyond decision trees, researchers have explored programmatic policy learning. Verma al. (2018) (24] introduced Programmatically Interpretable RL (PIRL), using a high-level domain-specific programming language to represent policies. Their method, NDPS (Neurally Directed Program Search), first trains a neural network policy and then performs a guided search in the space of programs to find policy that mimics the neural policy's 's decisions.
Another framework for obtaining interpretable policy is to leverage teacher, typically high- performance but complex policy, and train a simpler model to imitate it. Dataset Aggregation (DAgger) [8 is classic approach where agent gradually collects states by following its current policy and labels them with actions from an expert policy, iteratively improving the learned policy. VIPER (Verifiable Imitation Policy Extraction) [4] builds on this idea specifically learn decision tree policies. VIPER augments DAgger by using the teacher's Q-value information to focus the learning on important states. This results in smaller, more accurate decision trees than naive imitation learning. VIPER demonstrated success in distilling deep RL agents (like DQN policies) into compact decision trees that can be formally analyzed. In summary. imitation based methods can produce high-quality tree policies if the teacher is strong; however, they inherit fundamental limitation: if the optimal policy in the MDP is too complex to represented by small tree, a student forced to imitate that complex optimal (or any complex teacher) will struggle. The student might use its limited capacity to mirror the teacher's decisions in parts of the state space that are actually unnecessary to obtain high reward. In fact, recent work found that when a limited-depth tree is optimal for

---

OMDT: Direct Solution, Slower
SPOT: Iterative Solution, Faster
Tree Variables
Policy Variables
Tree Variables
Limited Quantity
Abundant Quantity
Limited Quantity
BB on Both Tree and Policy Variables
BB Tree Variables Only
Figure 2: Branching Strategy Comparison between SPOT and OMDT. OMDT uses standard solvers (e.g., Gurobi), requiring branching on all integer variables, thus linearly increasing complexity with the number of states. In contrast, SPOT employs two-stage reduced-space -pace muuch-and-boume approach, branching only on tree variables.
the task, directly optimizing that tree yield better performance than imitating a complex policy [27]. This highlights an imitation gap: the best interpretable policy may differ from the behavior of a black-box optimal policy, so chasing the latter via imitation can be counterproductive. In light of this, a promising direction is to optimize the decision tree policy directly for the MDP's returns, rather than relying teacher.
1.2 Optimal Decision Tree Policies
To overcome the performance limitations approximate methods, researchers have begun tackle the exact optimization of decision-tree policies in MDPs. Over the past decade, several works have formulated the decision tree induction problem mixed-integer program (MIP) or other combinatorial optimization problem to find the globally optimal tree.
Notably, Bertsimas & Dunn (2017) 66 and Verwer & Zhang (2017) 23 introduced MIP models for optimal classification trees, and subsequent extensions incorporated various constraints (fairness [I] robustness to adversarial examples (26), etc.) Due the NP-hard nature of optimal tree induction, variety of techniques have been explored to improve solver efficiency: dynamic programming for
small trees [10). constraint programming and SAT formulations [14 16
20
23 and specialized
branch-and -nd---undddddddd---- search algorithms that cleverly prune the search space 2
3 These works
demonstrated that for glassification/reeressooo tasks with fixed dataset, one can often compute an optimal decision tree for modestly sized problems, providing guarantee of maximal accuracy given the tree size. Vos and Verwer 27 brought this exact optimization approach into the RL setting. OMDT (Optimal MDP Decision Trees) formulates finding decision-tree policy for given discrete MDP as a single comprehensive MIP. In essence, their formulation combines the standard linear programming formulation of an MDP's optimal policy with additional integrality constraints that restrict the policy to the structure of binary decision tree. They link each state's decision to traversal of some path in the tree and enforce consistency of actions with the tree's predictions. Using MILP solver, OMDT can directly maximize the expected discounted return of a size-limited decision tree policy. However, the exact approach comes with scalability challenges. Solving large MILP that encodes the entire MDP and a complex policy structure computationally intensive. In OMDT's experiments, the approach was feasible for MDPs with on the order of 103-10* states and for trees of depth up to around 5-7. The authors report that in some environments with larger state spaces (e.g., tic-tac-toe game MDP), OMDT required hours of runtime surpass the performance of the approximate VIPER method. This has motivated us to improve the scalability tree policies.
A key open challenge is how to achieve scalability for decision tree policies. In particular, can design algorithms that find the tree policy more efficiently than directly solving MILP,, enabling problems with more states?
3

---

In contrast to OMDT's single huge MILP solve, we introduce a decision- tree policy iteration frame- work that alternates between evaluating the current tree policy and improving it. At each policy improvement step, finding the optimal decision tree (with respect to the current value function) is formulated as an MILP, but we solve it using a reduced-space branch-and-houm procedure, which leverages the problem's 's structure by decoupling the MDP constraints. By distributing our approach across multiple processors, we exploit parallelism to further speed up the search for the optimal tree policy in each iteration. Empirically, in our experiments, this approach outperforms OMDT in both runtime and scalability, finding optimal or near-optimal tree policies in problems where the baseline MILP approach fails or takes prohibitively long.
Our work addresses gaps interpretable reinforcement learning by developing a scalable and efficient algorithm for optimizing interpretable decision -areion--eeeeeee policies in Markov Decision Processes (MDPs). The key contributions of this work are summarized as follows:
The proposed method produces compact, interpretable policies suitable for deployment in sensi- tive, safety-critical domains.
We propose a novel decomposition strategy inspired by policy iteration. Instead of directly solving a monolithic optimization, we iteratively decompose the problem into smaller, more tractable subproblems. We provide theoretical guarantees that each of these subproblems can be solved to global optimality. ensuring overall high-quality solutions.
By leveraging the decomposition strategy, the optimization problems arising in each iteration be- come independently solvable and highly parallelizable This significantly enhances computational efficiency and scalability.
Extensive numerical experiments on standard benchmarks demonstrate that our approach yields solutions dramatically faster than state-of-the-arr methods. We observe significant runtime improvements and demonstrate the capability to efficiently handle larger problem instances.
2 Preliminaries
Markov Decision Processes. A Markov Decision Process (MDP) provides a mathematical frame- work for modeling sequential decision-making problems under uncertainty. Formally, an MDP is defined as a tuple (S,A, A, P. 7), where S is a finite set of states, AA a finite set of actions, PARK represents the transition probability from state i to state i' given action k. Ryy denotes the immediate reward received for transitioning from state i to i' under action k. and y E [0. 1) is the discount factor. The goal is to find policy ı that maximizes the expected cumulative discounted reward Eg EE 7d R
Solving MDPs via Linear Programming and its Dual Formulation. For a finite, discounted MDP, an optimal policy can be computed by formulating and solving a linear programming (LP) problem. Let Vú denote the optimal value function state i, let Po( represent the probability of starting in state i, and let Pirk and Rark denote, respectively, the transition probability and immediate reward when action is executed state transitioning to state i'. The primal LP formulation directly encodes the Bellman optimality conditions in terms of state values:
min Σ Po()) V.
iES
s.t. V4 - ? Σ
PURK Vy 2
P Ruc. ViES,
YES
PES
At optimality, these constraints hold with equality for at least one action per state. Intuitively, the primal LP minimizes each state's value while satisfying the constraints derived from Bellman's equation, resulting in the optimal value function. Subsequently, an optimal policy can be derived by selecting the action(s) in each state that yield equality in the corresponding constraints.
Taking the dual of the primal LP yields an alternative formulation where the variables explicitly represent the frequency with which each state-action pair is utilized. Define Pau 2 0 as the discounted occupancy measure, representing the expected discounted number of times the agent visits state
"We use i to represent state and & to represent action, differing from the traditional notation of s and a. This choice is made distinguish from variables commonly used in decision tree contexts.

---

and selects action k. The dual LP maximizes the total expected discounted reward subject to linear now-balance constraints:
ΣΣ
Pik
Park Riskk)
REA
1'68
S.L.
Σ REA
Pikk Pk= - po(i) +
EE PeWPPRs
ViES.
(I)
NESKEA
In this formulation, the term the left-hand side of each constraint represents the flow out of state i, while the right-hand side represents the flow into state i, consisting of contributions from the initial state distribution and transitions from predecessor states. Any feasible solution l thus corresponds to a valid policy, and the dual objective directly quantifies the expected return of this policy.
Scalable Policy Optimization with Trees
The primary challenge in solving the full dual optimization problem for tree-structured MDP policies arises from the coupling introduced by the MDP transition dynamics. Specifically, the system of equations defined by Eq. (1) creates fully interconnected set of constraints, wherein each state's 's decision variables depend on transition probabilities that link them to all other states. This interconnectedness implies that the optimization problem is not decomposable; it cannot be divided into smaller, independently solvable subproblems because the transition terms inherently couple all state-action variables together. Consequently, directly solving the complete dual formulation becomes computationally impractical.
To address this issue, draw inspiration from the classical value iteration algorithm [3] Rather than attempting to solve the entire coupled system simultaneously. we adopt an iterative strategy. We start with an initial estimate of the value function, denoted by Volld and perform single-ste) Bellman update for each state based on this fixed value. For each state i, the single-step Bellman update can be formulated
min V
S.t. V
Σ Purk Voll 2 PES
EPic Racks Vk E A.
YES
It can be found that iteratively solving Eq. corresponds exactly performing value iteration. The critical advantage of adopting this iterative approach in our formulation is its inherent decomposability. Specifically, in the Bellman backup L.P presented above, the constraints separated by state. Fach state is associated with its own independent set of inequalities, which eliminates direct coupling and interdependencies between states.
Analyzing the dual form of this single-step LP provides insights into the underlying policy updates. Specifically, the dual formulation of Eq. (2) for state i can be expressed as
Σ
Mikk Σ PRreR + Voold)
max
REA
PES
Σ Hik = 1,
s.t.
REA
Psk 2 0, EKE
where Ma is the dual variable which also considered as the policy. When extending this policy update formulation jointly across all states S, we arrive at the following aggregated optimization problem
max
Σ $ Σ
Σ
Pur + VVold)
(3a)
IES
REA
PES
s.t.
Σ = 1, ViES,
(3b)
REA
Pik 2 O, ViESKEEA.
(3c)
5

---

The resulting Here, the coefficient " serves as weight, indicating the relative importance given to each state i during the overall policy update. This conceptualization further clarified Proposition |
Now, we introduce the decision tree policy constraints. Consider that each state i has an associated feature vector x; R., with each feature scaled the unit interval [0, 1]. The decision tree consists of nodes indexed by t = , T, where T = 2D+1 - 1 denotes the total number of nodes for tree of depth D. Following the notation from [15], we let p(t) [t/2] denote the parent of node t, and define the sets (t) and Ax(t) to include the ancestors of node where the left or right branch, respectively, is taken along the path from the root to node The tree nodes are partitioned
into decision nodes TB f1...., [ and leaf nodes Tı = {|T/2] + ,,..., T).
constraints for the decision- teee-tree---tee seresstrueeeeed policy optimization problem are as follows:
Tree Constraints
Ckt 1
E Tr.
(3d)
REA
Σ Zit 1,
ViES
(3e)
TET2
T (I; + c Emin)
+ Emin S bm + (1 + Emax [11 -2z),
AE Tw. E A S
(3f)
a I33 2 bm (1 zz);
T
VI Tr, AR(!),E
(3g)
Σ agt de j=1
VLE TB
(3h)
0 5 b S di,
Vt E TB
(3i)
di dp(t),
Vt E TB
(3j)
Binary Constraints
age; de E {0,1},
VE TB
(3k)
E [0,1],
VI E Tr.
(31)
Ckt E [0,1],
Yk E A,t E Tr.
(3m)
Policy-Tree Coupling Constraint
Zit + Ck2
S Pakk
Vi S
(3n)
In alignment with the constraint-design framework from [15], the tree structure is encoded through four sets of variables: a, b, c, d. At each decision node / E TB, the binary variable de indicates whether node splits. When a split occurs, it is characterized by a binary feature selection vector
a, [a dFr] E 10, and a threshold b. E [0, 1]. At the leaves, Cia specifies the action assigned to leaf and Zá records if state terminates leaf I. Constants e, Emax, Emin stabilize the mixed-integer big-M calculations as described in 7 (See also Appendix A).
These constraints collectively preserve the logical and structural coherence of the decision tree. Specifically, Constraint (3d) ensures that each Icaf node is associated with exactly one action label. Constraint (3e) guarantees that each state is assigned uniquely one leaf node. Constraints (3r) and (3g) implement the appropriate branching behavior, directing states correctly based on their feature values. Constraints (3h) and (3i) ensure proper handling of non-splitting nodes: when split occurs at a node (i.e., de 0), all states reaching this node follow the right branch, ultimately directing them consistently towards the right-most leaf. Constraint (3j) maintains hierarchical consistency, enforcing that splits at parent nodes precede splits at child nodes, thereby ensuring logical downward propagation of tree branches. Finally, Constraint (3n) explicitly restricts the feasible policy space to policies that can be represented by decision trees.
Next, we explicitly derive "*th This quantity is the discounted occupancy measure, representing the expected cumulative number of discounted visits each state under the current policy nld Formally, it is defined as:
y MP((s = old
1=

---

Algorithm 1: Scalable Policy Optimization with Trees (SPOT)
Input: Number of iterations n, a sequence of thresholds {Φr )b=) Initialize random policy wo and compute its value function vo:
2 Set Vold < Vo:
3 for | = to n do
Fix: Select tree parameters as tunable with probability Φạ; fix others;
With Vold, solve Problem ( via Algorithm 2 to obtain policy mi Evaluate: Compute V/2 and state distribution TT for ny:
Solve:
Update: Pold + Vi. $rold $
7
8 end
Output: The policy in ( Tnd with highest expected return
where Ps( = i denotes the probability of being in state at time step & when following policy Told The complete Algorithm is presented in Algorithm [
Proposition 1. Each iteration of SPOT corresponds performing one-step policy gradient ascent update starting from qd In particular, the update maximizes the same first-order objective that the policy gradient theorem uses, resulting new policy that a greedy improvement on wold
SPOT differs from traditional policy gradient methods in key way: instead of taking small update step in the gradient direction, we fully re-optimize the policy μ to maximize the surrogate linearized objective around olod This can be interpreted as performing exact policy improvement rather than incremental improvement. Therefore, one iteration of SPOT corresponds to a one-step greedy policy improvement that leverages the structure of the policy gradient objective while optimizing completely under the current value estimate of old
Proposition 2. If the class of decision-tree policies is expressive to represent an optimal MDP policy, and the weighting vector dold is strictly positive, then SPOT is guaranteed to converge to the optimal solution.
4 Reduced-Space Branch-and- Framework
The optimization problem described by (3) can be viewed two-stage stochastic programming (TSSP) problem. Although traditional off-the-shelf solvers are generally effective, directly solving these large-scale problems is often computationally intensive or even intractable in practice.
To address this challenge, we propose a reduced-space branch-and-bowe anuud (RSBB) framework speeif- ically designed for solving mixed-integer TSSP problems, enhanced with carefully constructed lower and upper bounds (9]. This RSBB procedure initiates with the full feasible region Mo and iteratively refines the optimality gap by bisecting Mo into progressively smaller subsets, discarding any subregions that cannot contain the optimal policy. At each iteration, a subregion M is assessed by computing lower bound 3(M) and an upper bound a (MM) If the gap between these bounds satisfies a (MM) ((M) < 6, where ó represents an extremely small threshold, the algorithm terminates. Otherwise, the subregion M is further partitioned according to defined branching rule, and the process continues iteratively.
A significant advantage of this RSBB approach is its proven convergence, which occurs despite branching exclusively on tree-structure descriptive variables, such as the split-indicator and threshold vectors (i.e., b, d in constraints of Problem (3). This convergence property remains valid [15] even the presence of constraints involving both continuous and binary second-stage variables.
Theorem 1. RSBB converges to the global optimum, formally expressed as
lim 0; = lim Bg = E-000
1->0c
The finite nature of the feasible region for optimal policies arises naturally from the finite number of distinct tree structures that can result from the discrete selection of thresholds b at each decision node.
Here, ff indicates the complete MILP formula of Problem 3
7

---

4.1 Two Stage Stochastic Program
Note that variables a, b, c, d describe the structure of the decision tree and are the same for states, while policy-related variables and jt are state-specific and describe the allocation and reward of with fixed Voll can be reformulated as the following formula:
specific state. Therefore, Problem (
f(Mo) = max MEMo
[)(m),
(5)
where we denote m = (a, b,,bb, e, d) as all first-stage variables and Qi(-) represents the optimal value of the second-stage problem:
Qi(m) = max T
Σ Wiik E
Pirk (RePk + +V,
(6a)
s.t. Constraints 3a
3d
Gn).
(6b)
The closed set My == [mm, m²) denotes the region of the first stage variables. (.)). (-) represent the lower and upper bounds of each variable. In each branch-and-bound (BB) node with a specific partition M C Mo. we solve the problem f(M) max Σ (.))).
MEM LES
Leveraging this problem reformulation and decomposable structure, we can derive effective lower and upper bounding strategies within the RSBB framework to solve Problem (5) The lower bounds can be directly constructed using existing techniques from the optimal decision tree literature [[S], including scenario grouping, relaxed mixed-integee linear programming (MILP) bounds, and simple primal bound searches. Unlike traditional formulations for optimal decision tree policy learning, the decomposable structure of our approach enables straightforward parallelization, which significantly accelerates convergence.
However, to fully leverage the unique structure and decomposability of Problem we introduce tailored closed-form decomposable upper bounding strategy specifically designed for this maxi- mization problem. Additionally, this approach allows us to implement effective bound-tightening techniques that accelerate convergence within the RSBB framework by pre-determining the optimal actions for certain states during the branch-and-bound process. The overall structure and procedure of the RSBB algorithm are summarized Algorithm (see Supplementary Material).
Algorithm 2: Reduced-Spaal Branch-and-Boun for Optimal Tree Policy
Input: My. non-zero tolerance
Set iteration index = 0, MI < {Mo}
Initial upper and lower bounds a; (M))), = B(M)):
3 repeat
Node Selection
Select a set M E M satisfying 3(M) = B3;
M+ M (M);
i i+;+;;
Branching
Partition M into subsets Mj and M2 according the branch strategy in Section Add each subset to M to create separated descendent nodes;
10
11
Bounding
12
Compute a(M, ((M)), (M2)), (M2);
13
If 3.(,), {1, 2} is infeasible for some & E S, MI + M {M,};
8 - (
M' E M];
15
a; - max [a=1,, (M1), (M2));;
Remove all M from M if (M') $ 3;;
17
1 asl < 6, STOP:
18
until MI
0:
4.2
Closed-Form Upper Bounding Strategy
At each BB node, the optimization problem includes an implicit constraint known as the non- anticipativity constraint within the stochastic programming literature. This constraint requires that

---

all states share the same first-stage variables (i.e., the decision tree structure). non-anticipatiiity constraint, we derive an upper bounding problem defined
By relaxing this
((M) = max M.EM
ΣQ((m))
FES
This relaxed problem naturally decomposes into [S] independent subproblems: (M) := max Qi(m) with a(M) = Σ o,(M). The optimal value a; for each state i can be efîi- mEM
iES
ciently computed by enumerating all possible leaf nodes that state could reach, without explicitly solving any optimization problems. The computational complexity of this enumeration approach is O ([TBl - (Tzl). Since decision trees typically maintain a small depth for interpretability, this calcu- lation can substantially outperform traditional optimization methods. Given a bound M = [mm m=). the enumeration process exhaustively identifies all feasible leaf nodes for state i, thereby determining the globally optimal value of (M(M).
State Action Pre-dctermination An important benefit of the enumeration process utilized in the closed-form upper bound calculation is the reduction of feasible leaf nodes for each state i from full set Tz to smaller set Tz.- Here, Ts. denotes the set of leaf nodes reachable by state i given the current subregion M. By comparing the action selection indicators сş. with their associated range (i.e., d (xr) across each leaf node t T. it becomes possible to pre-determine the optimal action and reward for certain states even before solving their corresponding subproblems explicitly. Specifically, the reward and optimal action for state under the current branch-and-bound (BB) node can be evaluated by, for any k E E,
Qi if N dls = Ck otherwise,
R
(8)
where means the upper bound is not determined.
Once the optimal action and corresponding value for specific state have been determined at a node within the BB algorithm, this state be excluded from subsequent upper-bound calculations. This effectively reduces the computational load by decreasing the number of states to consider. Importantly, these predetermined state-action pairs remain valid throughout all subsequent descendant nodes in the BB search tree. This proactive state-action determination significantly mitigates computational complexity, especially deeper levels of the search tree. By avoiding redundant optimization subproblems for previously determined states, the overall efficiency and scalability of the algorithm are markedly enhanced.
5 Experiments
We evaluate our algorithm by comparing it to OMDT 27 on large-scale MDPs.
MDP Preparation We prepare set of 9 MDP datasets to evaluate methods: sys_ ad__ sys_as vys_ad_2 2, sic_vs_rant tiger_ vs vs__att,,,.. ant, csma_ 2_2, csma_ 2_4, firewire, wlan0, and wlan1. The first four MDPs are available at/tttps:/ com com/ maining five can be found at atltttps://githhi The properties of MDPs shown Table
while the re-
Comparison We evaluate two variants of our method: (1) direct application of SPOT (Algorithm D. and (2) SPOT with warm start, referred to as SPOT+WS. In SPOT+WS, initial solution generated by OMDT under a 5-minute time constraint serves as a warm start, subsequently refined by SPOT. All experiments were performed with a uniform 60-minute computational budget. Table reports the performance results for both variants, including the warm-start baselines.
Table I summarizes the normalized returns for 9 benchmark MDPs. SPOT+WS consistently outper- forms both vanilla SPOT and OMDT, achieving notable improvements (e.g.. 1201.7% on firewire and 505. 05.95% on csma_ 2_2). Furthermore, our analysis reveals that the warm start strategy is partic- ularly effective for SPOT on larger MDPs, such as firewire, csma_ 2_4, and wlan0. Even when OMDT already yields strong results (c.g., wlanO), SPOT maintains comparable performance.

---

Table Comparison of OMDT and SPOT on Large MDPs with Tree Depth D =3 Values represent normalized returns. The gain is calculated SPOT and SPOT+WS gains relative to the absolute value of OMDT (60min). The threshold is set to Φ1 0.5
MDP
[S]
[-4]
F' OM OMDT (60 min)
SPOT (60 min)
SPOT-WS (60 min)
SPOT Gain (%)
SPOT+WS Gain (1)
eya_ad
aya_ad_2
tic_vo_raa ran
2424
9
27
-1,0120
-1,0143
-1.0081
-1.0188
+0.6113
-0.1499
siger_vw_ant
625
5
0,471500
0.81333
0.84102
0.65309
+3.4045
-19.7016
cana, 2,2
1038
8
11
1.2025e-4
4.7552e-4
2,38988-4
2.8681e-3
-49,5165
+,005955
7958
8
-1.1582e-2
-1.1582e-2
-1.1899e-2
1,14662-4
-1.0103
+100.99
firwwire
-9,935005
4.8977e-2
-1,0055--2
0.63757
-1204926
+1201.7
0:93899
wlan1
6825
13
-0,76336
0,98730
0,99694
0.99694
+0.9764
+0,9764
6 Conclusion
In this paper, we presented a novel framework, SPOT, designed for computing decision tree policies in Markov Decision Processes (MDPs). Our approach addresses the critical computational bottlenecks encountered when optimizing tree-structured policies through policy iteration and reduced- branch-and-boumd algorithm. SPOT provides solid improvements on challenging MDPs while maintaining competitive performance on simpler instances
Despite these results, method has some limitations. Its performance still relies the efficiency of the underlying optimization solver, which may restrict scalability for extremely large or complex MDPs. Future research could explore solver-independent acceleration methods approximate formulations to extend applicability to very large-scale decision-making problems.
Acknowledgments and Disclosure of Funding
The authors are grateful to Wenhui Zhao for his valuable feedback. Cheng Hua is partly sup- ported by the National Natural Science Foundation of China 172, 72394370:72394375. (4495130:22495122) Shanghai Education Commission Chenguang Program (22CGA12), and Shang- hai Jiao Tong University Office of Liberal Arts (ZHWK2502).
References
[1] Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriminative decision-making. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 1418-1426, 2019.
[2] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and-boum search. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3146-311 1453,,,, 2020.
[3] Gačl Aglin, Siegfried Nijssen, and Pierre Schaus. Pyd18. a library for learning optimal decision trees. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 5222-522- 2021.
[4] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable Reinforcement Learning via Policy Extraction, January 2019.
[5] Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, USA, edition, 1957.
[6] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106: 1039- 1082, 2017.
[7] Dimitris Bertsimas and Jack Dunn. Machine Learning Under a Modern Optimization Lens. Dynamic Ideas LLC, Belmont, MA, 2019.
[8] Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone, Classification and regression trees. Routledge, 2017.
10

---

[9] Yankai Cao and Victor M. Zavala. A scalable global optimization algorithm for stochastic nonlinear programs. Journal of Global Optimization, 75(2):393-416 October 2019. Publisher: Springer Science and Business Media LLC.C
[10] Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter Stuckey. Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1 2022.
[11] Claire Glanois, Paul Weng, Matthieu Zimmer, Dong Li, Tianpei Yang. Jianye Hao, and Wulong Liu. A survey interpretable reinforcement learning. Machine Learning, 1348))5847-5880, 2024.
[12] Ujjwal Das Gupta, Erik Talvitie, and Michael Bowling. Policy tree: Adaptive representation for policy gradient. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, 2015.
[13] R. A. Howard. Dynamic Programming and Markov Processes. MIT Press, Cambridge, MA, 1960.
[14] Hao Hu, Mohamed Siala, Emmanuel Hebrard, and Marie-José Huguet. Learning optimal decision trees with maxsat and its integration in adaboost. In IJCAI-PRICAI 2020, 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence, 2020.
[15] Kaixun Hua, Jiayang Ren, and Yankai Cao. A scalable deterministic global optimization algorithm for training optimal decision tree. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 8347-8359. Curran Associates, Inc., 2022.
[16] Nina Narodytska, Alexey Ignatiev, Filipe Pereira, and Joao Marques-Sine Silva. Learning optimal decision trees with sat. In International Joint Conference on Artificial Intelligence 2018, pages 1362-1368. Association for the Advancement of Artificial Intelligence (AAAI), 2018.
[17] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994.
[18] 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.
[19] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206-215, 2019.
[20] André Schidler and Stefan Szeider. Sat-based decision tree learning for large data sets. Journal of Artificial Intelligence Research, 80:875-911 918, 2024.
[21] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances neural information processing systems, 12, 1999.
[22] Nicholay Topin, Stephanie Milani, Fei Fang, and Manuela Veloso. Iterative bounding mdps: Learning interpretable policies via non-interpretable methods. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9923-9931, 2021.
[23] Hélene Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus. Learning optimal decision trees using constraint programming. Constraints, 25:226-250 2020.
[24] Abhinay Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. ArXiv, abs/1880400 1804.02477, 2018
[25] Sieco Verwer and Yingqian Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In Integration of Al and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017 Proceedings 14, pages 94-103, Springer, 2017.

---

[26] Daniël Vos and Sicco Verwer Efficient training of robust decision trees against adversarial examples. International Conference on Machine Learning, pages 10586-10595, PMLR, 2021.
[27] Daniël Vos and Sicco Verwer. Optimal Decision Tree Policies for Markov Decision Processes. In Proceedings the Phirty-Secone International Joins Conference on Artificial Intelligence, pages 5457-5465, Macau, SAR China, August 2023. International Joint Conferences on Artificial Intelligence Organization.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
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 claims made in the abstract and introduction accurately reflect the core contributions of the paper, including the proposed decomposition strategy, the accompanying theoretical analysis, and the well-designed experiments that support the main findings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
NA answer to this question will not be 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 include aspirational goals as motivation 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]
13

---

Justification:
We state our limitations in the conclusion.
Guidelines:
The answer NA means that the paper has 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-specifiitiinn asymptotic approximations only holding locally). The authors should reflect on 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't '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 a complete (and correct) proof?
Answer: [Yes]
Justification: All proof are put in appendix and all theory clearly stated with proper assumptions.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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 properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The detailed experiment setting are explained Section and we also provide complete code in the supplementary material for reproduction.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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 a 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 is 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 NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the whole code package including the testing data file in the supplementary material for reproduction.
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/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" 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
/ //niss.ccppulic//guue http:///cc/giiee//eeeuuubiiiiiin
for more details.
The authors should provide instructions on 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.
15

---

At submission time, to 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 is 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 our experimental settings in Section 5,
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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, or 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 have additional experiment results with statistical analysis such as error bars in the appendix file of supplementary material package.
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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error 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 out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question:
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?
Answer: [Yes]
Justification: Section and Supplementary material provide the details.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount 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 NeurlPS Code of Ethics
Answer: [Yes]
Justification:
This work conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the part of introduction, we state the importance of explainable RL model in many critical applications, which will help the development of society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point 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 a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
17

---

Justification:
The 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.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: 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?
Answer: [Yes]
Justification:
The resource of datasets introducted in Section and part of them comes from the free release the author of OMDT paper, while others are xxxXx. Their usage complies with their terms of access and non-commercial research intent.
Guidelines:
The answer NA means that the paper does not 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
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, papprssii thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does 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 anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

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 as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in 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 in the main paper.
According to the NeurIPS Code of Ethies, 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
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?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on 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.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.LM policy hato:e//nearrps.cc//ooffeeeeeeee for what should or should not be described.
19

---

A Notation
We now clarify the symbols we used writing:
Table 2: Summary of Notation
Category
Description
Example Variables
Decision Variables
Optimization variables to be solved
Gjt E (0,1), be E 10, puk E [0,
MDP Parameters
Fixed transition probabilities and rewards
Park Rick Y
Algorithm Constants
Fixed hyperparameters and com- puted values
Smaz--mmnn D7"""
State/Action Indices
Index sets for states and actions
i E S
Time Indices
Temporal or iteration indices
B
Case study: tiger_vs_ant
The tiger_ an_ environment is 5x5 grid world in which tiger pursues antelope. The state the tuple antelope_x, antelope_y _, tiger_X tiger_y, with features normalized [0,1]. The tiger can move up, right, down, left, or wait. The antelope moves randomly among valid cells, never leaving the grid or stepping onto the tiger's current cell. The agent receives a reward when the tiger catches the antelope (same cell) and otherwise, and the episode ends upon capture, and rewards are discounted with a factor y E (0, 1). The task is challenging because the agent must anticipate stochastic antelope motion and positioning restrict escape routes
wait
yos
antilope y s 0.6
yes
no
if [igeer_ps5 0.6
up
yes
no
left
aatelopeeee j 0.2
yes
up
if tiger s 0.4
no
yes
no
down
antilope y y 0.66
n
yes
up
antilope 0.8
no
right
Figure 3: Learned interpretable decision tree policy with D 3 in environment tiger_vs. vs_ant
We will demonstrate the interpretability of the above learned policy through the following aspects:
1. Domain- MManingfuul Behavior (which shows the strategic coherence)
From the learned decision tree policy, we summarize the following strategies:
Cornering Strategy: When antelope is trapped near the left wall (æ < 0.2),, the tiger adapts:
2c, Emaa-EEin are introduced to Big-M reformulation on tree direction constraints. Here is vector of length (i.e., the number of state features), where for each state feature j. we define 6, as follow ( = mitt Zi,, [((+1). # æı,, i [|S] - 1]}. where Ti.j denotes the ith largest value in the jth feature. Gmin miny {c; and Emaz maxi(c; {
20

---

If tiger is well-positione (x I 0.6), it waits patiently or chases vertically
If tiger is far away (x 0.6), it prioritizes closing the horizontal gap
Pursuit Strategy: In open areas, the tiger uses intelligent vertical positioning:
Moves upward when positioned below the prey (tiger_y -y - 0.4)
Moves downward when positioned above the prey (tiger > 0.4)
Escape Prevention: Near top boundary (antelope_y > 0.8), the policy focuses on blocking escape routes rather than direct pursuit
2. Addresses Complexity Concern (This pattern correlates to the concept of Simulatability in [II]
Only 8 decision rules cover the entire 625-state space (5 states)
Each path through the tree corresponds to a clear strategic situation
The shallow depth (D 3) ensures human comprehension
3. Uses Interpretable Features (This pattern correlates to the concept of Decomposability in
Spatial boundaries: Recognizes walls (æ s 0.2 for left edge, > 0.8 for top)
Relative positioning: Implicitly reasons about tiger-antelope spatial relationships
No complex engineered features: Uses raw normalized coordinates that directly map to grid positions.
Additional Experiment Details
C.1 Experiment Details
Details of SPOT Implementation. During SPOT training, we adopt a time-constrained setup with total runtime budget of one hour (60 minutes) and maximum of five minutes allocated per iteration. At each step, we retain the best solution found within the allotted time window. We fix the threshold Φi 0.5 and, for simplicity, set all coefficients Phi epsilon-decay strategy: when computing Vold the evaluation is based greedy policy with exploration probability = 1/1, where denotes the current iteration index. With probability the policy randomly selects alternative actions rather than the greedy one. This mechanism encourages the policy to explore beyond the most immediate choices. In each iteration, we use Algorithm 2 compute the solution.
To enhance exploration, we employ an
C.2 Experiments with Tree Depth D
Setup. The MDP setup and method comparison follow those in Section 5. The SPOT implementation except that the tree-depth parameter now set to
details are identical Section CT
Table reports the normalized return across all benchmarks. We find that even the vanilla SPOT method surpasses OMDT in seven out of nine instances for example, it increases the return sys_ad, 2 from 0.75403 to 0.83337 (+10.76%) and reduces the loss on sic_vs_ra__ from -1.00610 -1.0009. Incorporating warm-start initialization further amplifies these improvements: on csma_2_2, SPOT+WS boosts the return from 0.00024 to 0.01485 (+6101. 14%%) and on firewire, from -0.009935 to 0.63699 (+611490%), Even in the moderate case of csma_ 2_4, warm starts boost performance by +100 +100.97% (-0.01158 158 - 0.01 147). These results confirm that SPOT's depth tuning yields steady improvements and that warm-start strategies can unlock substantial additional performance gains in more challenging MDPs.
Results.
C.3 Experiments on Running Time
To demonstrate SPOT's efficiency in solving each iteration problem, we conduct experiments com- paring the runtime of different solution methods on the same optimization task.
21

---

Table Comparison of OMDT and Our Methods on Large MDPs with Tree Depth D
Values
are normalized returns.
MDP
[8]
[A]
F'
OMDT (5 min)
OMDT min)
min)
SPOT-WS min)
SPOT (9)
SPOT+WS (%)
aya_ad,1
256
9
0.90823
0:94403
0.95416
0.95027
+1,073
+0.0000
eyo_ad,
256
9
0.24003
0,75403
0.833357
0.83519
+10.52
+10.76
tic_varran
2424
9
27
-1.017301
-1.00k10
-1,00089
0.38958
+0.517%
+138.7
riger_va,
625
0.53266
0.80-644
0.925477
0.81389
+14.77
+1.150
capa, 2,2
2.39002e4
2.3964c-4
-1.2253e-2
1.4848-22
+6101.14
-1.1583e-2
1.1466e-4
firepire
4093
10
-9.9350--3
-9.9550e-3
0.63699
0.63757
#6511.6
+6517.4
wland
2954
6
13
0.42805
1,00000
0,97792
0,97792
-2.308
-2.308
wlan1
6825
13
-0.76973
0.37665
0.99694
0,99694
+164.68
+164.88
Setup. For each MDP, we initialize the policy by selecting fixed action across all states. Based on this fixed policy, compute the corresponding value function yold and set q= the softmax of the discounted state-action occupancy measure. We then perform single iteration of optimization to find a tree with depth D under three different approaches: (i) solving directly with Gurobi, (ii) using RSBB (reduced space aanechannd-buudd in serial, and (iii) using RSBB in parallel across 10 CPU cores. The solver is configured with a gap tolerance of 0.01 and maximum runtime of 14,800 seconds. Each setup is repeated five times, and we report the mean and standard deviation of the runtime.
Results. Figure 4 summarizes the results. For all instances except tic_vs seraaa and tiger_ vs. _s__vs____t ant, where none of the methods reach optimality within the time limit, parallel RSBB consistently achieves superior efficiency. For example, on the firewire benchmark, solving directly with Gurobi requires 11,528.124 whereas parallel RSBB completes the task in only 15.91 Similarly, on csma_ 2__, Gurobi exceeds the 14,800s limit, while parallel RSBB finishes in just 42.568 s. This dramatic reduction computation time highlights the efficiency of the parallel RSBB approach.
200
(a)
(b)
(d)
(c)
(f)
g
(h)
Figure 4: Running time comparisons across different MDPs using Gurobi, serial RSBB, and parallel
RSBB. Each bar represents the mean runtime, with error bars showing standard deviation.
D Proofs
D.1 Proof of Proposition] I
Given the current policy old consider the optimization performed by SPOT at the update step:
Proof.
max Σ
D dl Σns Lus Σ
Park Park (Rayk + +VVol)))
subject to Et H4k for each state and Pokk 2 O. Here Park and Rayk are the transition probability and reward for taking action in state and landing in state i', and Voold is the value of state under old, This objective is the expected total discounted return of the new policy evaluated under the state visitation weights of the old policy. To see this, define the Q-value of a. old for state-action pair (i, k)
22

---

as
(i,k) Pirk (Rerk + vV
Using this definition, we can rewrite the objective in a simpler form:
Mik 1 (i, (1,
max
This expression represents the expected Q-value of the new policy, weighting each state by its discounted occupancy ".-" under xold Because o= is fixed during this optimization, the objective separates by states. Maximizing it will assign, for each state i, all probability mass to the action k that has the highest Q k). In other words, the optimal μ is the greedy policy new defined by new (k/i) for k arg max, Q (i, a). This yields the maximum of the weighted Q-value objective.
To connect this update the policy gradient, recall the policy gradient theorem 21 For differen- tiable policy go, the gradient of the expected return J(TT) can be written as
V VoJ(TO)
VaTo 1)) (i,
In particular, at 0 = old (i.e. at the current policy), the direction of steepest ascent in policy space is determined by the term E, "b Σn QThh Vo Intuitively, this means that in each state i, increasing the probability of an action & will increase J at rate proportional to Φ Q (i, k).. The optimization we performed above uses this same signal: क. Q" (i, k) appears as the coefficient of Uss in the objective. Thus, choosing the action that maximizes Q (i, for each state (i.e. setting Usk 1 at the maximizing k) is precisely what the policy gradient would prescribe - it favors actions with the largest positive impact on the objective. In fact, the above y-update can be seen as solving for the policy that maximizes the first-order expansion of J(T)) around æ By taking greedy, full step in the direction of this gradient (rather than an infinitesimal step), SPOT produces the deterministic policy new that locally maximizes the expected return improvement.
D.2 Proof of Proposition 2
Proof. Assume that the decision tree policy class has enough capacity to represent the optimal policy. This means at each iteration, when SPOT optimizes the tree policy, it can effectively carry out policy improvement step with respect to the current value function Vold, We show that this improvement step will monotonically increase the policy's performance and reach optimality.
More specifically, for fixed Vold the objective follows:
Σ JAik EPiR Park (Reck + >Voll).
max
Because the maximization separates by state (note that pix for each state appears only in the term for state i ), we can optimize each state's decision independently. Let us define the Q-value of taking action ls in state under the old policy as
Q (i, = Σ Puck (Rwk + +Voll).
3'
Maximizing the inner sum over actions for given state i will simply pick the action that maximizes this Q-value. In other words, for each state
Σ Eua
(i,b) = max QT" (i,
max Mi
since the optimal choice is to put all the state's probability mass on the single action k that yields the highest QT"h (i, k) (this corresponds to choosing that action deterministically in state i ). Therefore, the entire objective decouples over states and can be written as:
Σ $ max Q (i, k). k
23

---

The policy zew that achieves this maximum is precisely the greedy policy improvement over nolld for each state i, s/eeww (i) arg max; Q k).. By construction, this new policy new is decision tree (deterministic) policy, assuming the tree function approximator is flexible enough to represent that state-to-action mapping.
Crucially, because T7"h > O for every state i, no state is ignored in this optimization. The strictly positive weights ensure that improving the Q-value in any state will increase the overall objective. In other words, the weighted objective preserves the true ordering policy yields higher value at some state without lowering it elsewhere, the objective (with all-positive weights) will also be higher for that policy. This guarantees that the greedy step indeed aligns with improving the actual value function of the policy.
policy performance: if one
The described greedy update is exactly the policy improvement step from dynamic programming. By the policy improvement theorem [7], the new policy n=" is guaranteed to be no worse than olld in terms of its value for all states, and in fact strictly better for at least one state if zold was not already optimal. In other words, V* (t) N V (i) for all states i, with a strict inequality for some state as long as old is not optimal. Because our decision-tree function class can represent the policy exactly and SPOT guarantees solving the optimal policy in each step, finds the optimal policy after convergence.
D.3 Proof of Theorem 1
The proof of Theorem follows naturally from observing that the set of feasible solutions is finite. Specifically, since each decision node in the tree can only take a finite set of meaningful split values the number of distinct decision tree structures generated from these splits is also finite. Consequently, a finite enumeration of solutions is inherently guaranteed, making the convergence of the proposed RSBB algorithm straightforward
Additionally, Problem (5) can be viewed as specialized instance of a two-stage stochastic pro- gramming problem. Consequently, the convergence analysis for our RSBB algorithm can leverage established methodologies presented in earlier literature, particularly the frameworks described by [9] and [15]. Although our problem features a distinct cost function formulation tailored for reinforce- ment learning policy optimization, the fundamental structure of the branching process in SPOT closely mirrors that of the classification tree optimization problems studied in [15]. Specifically, the choice of branching variables in each iteration, such as the split indicator variables (d), state feature selection indicator variables (a), and threshold variables (b), remain identical to those in previous optimal decision tree frameworks. Therefore, despite variable & being continuous rather than discrete, the convergence properties derived in earlier works can also be applied in the current problem. This continuity does not compromise convergence guarantees, as the underlying finite combinatorial structure induced by discrete structural variables ensures that the algorithm systematically explores finite solution space and thus converges to the global optimum.
E Branching Strategy for Algorithm 2
Algorithm 2 branching strategy prioritizes variables according to their structural significance within the optimal decision tree. The binary variables d, which directly encode whether individual decision nodes perform splits, naturally form the foundational structure of the tree. Therefore, branching decisions first focus on these split-indicator variables.
For the remaining variables (a, b, c), we employ a heuristic procedure as follows: we first compute a branching threshold defined as
111b" 1' We then compare 7 to a uniformly generated random number in the range [o, 1). If this random number exceeds 7, branching occurs on the discrete variable a, which specifies the splitting feature at the decision node. Should all components of already be fixed, we instead branch on the variable c, controlling the action assignment at leaf nodes. Alternatively, if the random number is less than or equal to t, branching conducted on the continuous variable 6, selecting the midpoint between its current bounds the branching point.
24

---

Within each category of variables (a, b, c), we systematically prioritize branching based on ascending node indices; for example, if two reature-selection variables O₁,, and aj,++ remain undetermined. branching will occur first on the variable associated with the lower-indexed node, i.e., Uj,t-
25


Reviews:
[{"review_id": "9JM5AcFaPL", "reviewer": "Reviewer_iZpk", "summary": "This paper develops a decision tree representation for the optimal policy to a problem represented as a Markov Decision Process (MDP), in order to be as transparent as possible for decision makers applying the policy.  \nThis is a combinatorially complex problem, so the solution method applies a combination of techniques to arrive at an efficient solution, including mixed-integer linear programming (MILP) and a reduced-space branch-and-bound (RSBB) framework.  \nThe decision tree optimization and the MDP dynamics are artfully decoupled so that significant subtasks can be performed in parallel.  \nThe authors claim to achieve a more interpretable and scalable solution to deliver optimal policies an order of magnitude faster than existing approaches.", "questions": "How many processors would be needed to obtain the reported speed ups for csma and firewire?\n\nWhy do you report the “best gain” of the regular algorithm with or without warm start on the alternative algorithm as opposed to the gain from each?  You are considering whichever method works better, and even relying on the alternative algorithm for a warm start in order to show any improvement over that alternative algorithm, such as for wlan0 and csma_2_2 in both Table 1 and Table 2.\n\nAre there any other limitations to your results besides the concerns about the efficiency of the underlying optimization solver?\n\nYour algorithm compares very well as described when parallel processors can be employed for some test problems, but not others, and sometimes with a warm start, and sometimes without a warm start.  Why do you overstate its relative performance in general?", "limitations": "These are challenging problems and, although the innovations introduced appear to make a difference for some problems, the optimization solver is not the only limitation.  \n\nThis seems to be promising work in progress, and I am concerned that the benefits in general are overstated.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The algorithm is complex with multiple reframings and transformations, and it is rather hard to follow.  Many of the details of the innovations to previous work, including the RSBB framework, are only fully described in the appendix.\n\nThe innovations to allow parallel processing appear to be original, but their significance seems overstated.  While the new algorithm outperforms the alternatives on multiple test datasets, on others the improvement cannot be characterized as “an order of magnitude faster than existing approaches.”  It does perform better when compared with tree depth 4 than with tree depth 3, and speed up with parallel processing is sometimes more significant than other times, but I could not find how many processors it would take to achieve that speed up.", "was_revised": true, "final_justification": "I found the insights from the reviewers and the responses from the authors to be quite helpful.\n\nI believe that the paper’s emphasis on decision trees for interpretability of the optimal policy makes sense, but that the paper can still be improved based on many of the reviewers’ suggestions.", "rebuttal": "Thank you for your thoughtful and constructive review of our SPOT paper. We appreciate your detailed feedback and address each of your major concerns below.\n\n> How many processors would be needed to obtain the reported speed ups for csma and firewire? \n\nAll experiments reported in this paper, including those for csma and firewire, were conducted using 10 CPU cores, as detailed in Appendix B.3. This hardware configuration was maintained consistently across all benchmark problems to ensure fair and reliable comparisons.\n\n\n> Why do you report the “best gain” of the regular algorithm with or without warm start on the alternative algorithm as opposed to the gain from each? You are considering whichever method works better, and even relying on the alternative algorithm for a warm start in order to show any improvement over that alternative algorithm, such as for wlan0 and csma_2_2 in both Table 1 and Table 2.\n\nYou raise a valid point about clarity in our reporting. While we show individual performance for SPOT and SPOT+WS, we will revise the tables to report separate performance gains for each method instead of only the \"best gain.\"\nRegarding the warm-start setup: SPOT+WS uses the 5-minute solution from OMDT as initialization but is compared against OMDT’s full 60-minute solution. We think this constitutes a fair comparison, as it leverages a lightweight version of a standard optimization technique to achieve improved performance within the same overall computational budget.\n\n> Are there any other limitations to your results besides the concerns about the efficiency of the underlying optimization solver?\n    \n> These are challenging problems and, although the innovations introduced appear to make a difference for some problems, the optimization solver is not the only limitation.\n    \nWe agree that our method also has limitations. First, it cannot guarantee global optimality when the decision tree is not sufficiently deep to represent the true optimal policy. While our algorithm is applicable to deeper trees, solver limitations may prevent us from obtaining globally optimal solutions in such cases. Second, for small problems, the baseline OMDT can often find high-quality solutions quickly, leaving limited room for further improvement regardless of our algorithmic advances. That said, scalability remains a key challenge in interpretable reinforcement learning. As shown in Tables 1 and 2, OMDT struggles with problems involving more than 1,000 states, whereas our method maintains strong performance at this scale.\n\n> Your algorithm compares very well as described when parallel processors can be employed for some test problems, but not others, and sometimes with a warm start, and sometimes without a warm start. Why do you overstate its relative performance in general?\n\nWe appreciate the reviewer's careful examination of our results. We would like to clarify several points:\n\n- **Parallel processing is used consistently for SPOT:** To ensure a fair comparison, all experiments were run on identical hardware, giving every method (OMDT, SPOT, and SPOT+WS) access to the same multi-core processors. The parallelization in our SPOT algorithm is an inherent feature of its branch-and-bound design, not a selective advantage. This parallel implementation yield speedup compared to its serial counterpart, as detailed in Appendix B.3.\n- **Performance across different MDPs:** We acknowledge that performance gains vary across test problems. This variation is due to the diverse characteristics of the MDPs (ranging from 256 to 7958 states). We report all results transparently, including cases where improvements are marginal (e.g., wlan0 with 0% gain) to provide a complete picture.\n- **Warm start vs. Cold start:** We evaluate both variants to demonstrate our method's versatility. Empirically, we observe that for larger MDPs (like `firewire, csma_2_4, wlan0, wlan1`),  SPOT with warm start consistently achieves superior performance.\n    \nWe will revise our claims to more precisely state that \"SPOT consistently improves or matches baseline performance across diverse MDPs, with particularly strong gains on complex instances,\" rather than implying universal superiority.\n    \n> This seems to be promising work in progress, and I am concerned that the benefits in general are overstated.\n\nWe respectfully disagree with the characterization as \"work in progress\" and would like to address the concern about overstated benefits:\n\n* **Complete methodology:** Our work presents a fully developed algorithmic framework with (i) theoretical foundations for the policy iteration scheme, (ii) a complete branch-and-bound algorithm with proven correctness, and (iii) comprehensive empirical validation on established benchmarks.\n* **Realistic benefit reporting:** We report the full spectrum of results - from marginal improvements (0.2% on sys_ad_1) to substantial gains (1201.7% on firewire). This reporting demonstrates that we are not cherry-picking results. The \"best gain\" column shows the actual improvements achieved.\n* **Numerical robustness:** Our experiments evaluate multiple benchmark MDPs across varying problem sizes to ensure robust conclusions. The consistent improvements observed across diverse problem structures validate the general applicability of our approach.\n\nWe acknowledge that our abstract and introduction may have used overly broad language. We will revise these sections to more accurately reflect that \"SPOT provides solid improvements on challenging MDPs while maintaining competitive performance on simpler instances,\" which better represents our empirical findings."}, {"review_id": "reyBm57hLD", "reviewer": "Reviewer_3Gn1", "summary": "This paper proposes **Scalable Policy Optimization with Trees** (SPOT), a method for learning optimal decision tree policies in Markov Decision Processes (MDPs). SPOT formulates policy optimization as a sequence of mixed-integer linear programs (MILPs), decoupling the tree structure from the MDP dynamics via a reduced-space branch-and-bound (RSBB) framework. Empirical results on several discrete MDP benchmarks show that SPOT outperforms a prior MILP-based method (OMDT).", "questions": "NA", "limitations": "The author only mentioned \"*Its performance still relies on the efficiency of the underlying optimization solver, which may restrict scalability for extremely large or complex MDPs*\" in Section 6.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The algorithm design seems reasonable.\n- The paper provides convergence guarantees under certain conditions.\n- SPOT demonstrates policy quality on several benchmark MDPs compared to OMDT.\n\n## Weaknesses\n\n- **Narrow relevance to modern RL**: The paper is positioned as an interpretable RL contribution, yet it operates in a highly constrained setting (small tabular MDPs, decision trees). It does not engage with current trends in deep RL, offline RL, or neuro-symbolic methods, limiting its broader impact for the NeurIPS community.\n- **Sparse and outdated related work**: This area seems very niche, and the literature review is narrow, with very few references from the past 2--3 years and minimal engagement with recent interpretable RL or explainable AI research. There are only 23 references in this paper. Only one from 2024, one from 2023, and two from 2022. Only one from NeurIPS. The paper could benefit from positioning itself more clearly within the broader ML community.\n- \"*Decision tree policies have attracted significant attention as a suitable interpretable model class*\": This is very questionable and debatable. First, no references. \"Significant attention\" must be supported by sufficient references. Second, I don't think decision trees are inherently interpretable. \"Simulatable by a person\" is not a requirement for interpretability. One can \"run\" a neural network by hand, given enough time. Nevertheless, the experiments didn't show how we can interpret the policy anyway. No interpretability analysis, user study, or policy explanation is presented in experiments to support this core motivation.\n- The theoretical convergence guarantee assumes that the class of decision tree policies can represent the optimal policy. This is a very strong and often false assumption. This contradicts other parts of the paper where the authors acknowledge that small trees are fundamentally limited in expressivity.\n- \"*This significantly improves runtime and scalability compared to previous methods*\": I can't observe this from the experimental results. Since \"*all experiments were performed with a uniform 60-minute computational budget.*\" If the author wants to show speedup, they should show how long it takes to achieve the same performance. \"OMDT (5m)\" is unnecessary and unfair.", "was_revised": true, "final_justification": "This paper may have some interesting ideas, but I don't believe the empirical results and claims align. The references and content added in the rebuttal should be reviewed again before accepting the paper. Therefore, I maintain my original score.", "rebuttal": "> Narrow relevance to modern RL: The paper is positioned as an interpretable RL contribution, yet it operates in a highly constrained setting (small tabular MDPs, decision trees). It does not engage with current trends in deep RL, offline RL, or neuro-symbolic methods, limiting its broader impact for the NeurIPS community.\n\nWe thank the reviewer for the valuable feedback. We respectfully argue that our focus on tabular MDPs and decision trees is not a limitation, but a choice to tackle a fundamental problem: finding provably optimal policies within an interpretable model class [2]. This pursuit is critical for building trustworthy AI systems suitable for high-stakes domains where safety and verifiability are paramount. Far from being disconnected from modern RL [1,6], our work engages directly with its key challenges. First, we address the well-documented \"imitation gap,\" a known issue where distilling complex deep RL policies is often suboptimal compared to direct optimization of the interpretable model itself. Second, tree-based policies are highly relevant to modern offline RL, where recent work has shown that they offer remarkable training speed and stability by reframing the problem as regression [3]. Third, our method provides a foundational, verifiable building block for neuro-symbolic systems, which require high-quality symbolic components to ensure reliability [4]. Finally, our work contributes to what has been identified as a \"grand challenge\" in machine learning: the scalable optimization of sparse logical models such as decision trees [5]. \n\n\n> Sparse and outdated related work: This area seems very niche ... The paper could benefit from positioning itself more clearly within the broader ML community.\n\nWe thank the reviewer for the feedback. We respectfully disagree with the characterization of the related work as sparse or outdated and wish to clarify our work's position within the contemporary research landscape. The pursuit of inherently interpretable policies, such as decision trees, represents a major modern thrust in Explainable AI [6], particularly for safety-critical sequential decision-making. Our work engages with a vibrant and diverse field of recent tree-based RL methods, including gradient-boosted ensembles (e.g., GBRL [7]), concept-based learning (e.g., LICORICE [8]), and direct optimal policy search [2], where our work is situated. Our direct predecessor, OMDT [2], established the use of monolithic MILP formulations for this task. The primary contribution of our paper, SPOT, is to overcome the critical scalability bottleneck of this prior work. Our iterative decomposition and reduced-space branch-and-bound approach is not an ad-hoc heuristic but rather a novel application of a state-of-the-art optimization pattern that mirrors recent advances in the broader Machine Learning for Mixed-integer Optimization community (e.g., Apollo-MILP [9]). This methodology allows us to scalably produce globally optimal, size-constrained policies. This is a crucial capability, as single optimal trees are amenable to efficient formal verification [10], whereas verifying tree ensembles is known to be NP-complete [11], making our approach highly relevant for developing verifiably robust and trustworthy AI systems.\n\nWe acknowledge the reviewer’s point that the paper would benefit from engaging more extensively with recent literature, especially from the last two years and from top venues such as NeurIPS. We will revise the manuscript to better position our work within the landscape.\n\n> \"Decision tree policies have attracted significant attention as a suitable interpretable model class\" ... No interpretability analysis, user study, or policy explanation is presented in experiments to support this core motivation.\n\nWe respectfully disagree with the reviewer’s claim that decision trees lack “significant attention” and inherent interpretability, as this perspective appears to overlook a substantial body of literature. Decision tree policies have received considerable attention in reinforcement learning [2，12], with breakthrough work VIPER (NeurIPS 2018) [13] establishing the field, followed by developments including OMDT (IJCAI 2023) [2]. Decision trees are inherently interpretable due to their simulatability and decomposability properties [14], as established by foundational works including Breiman et al.'s CART [15], Quinlan's ID3 algorithm [16], and modern interpretability frameworks by Lipton [14]. Unlike neural networks, decision trees enable complete mental simulation of the decision process and provide \"extraction of human-readable decision rules with full verification of input-output mapping\" [17]. Empirical user studies consistently demonstrate superior interpretability of decision trees over neural networks [18,19], with quantitative evidence showing significantly higher interpretability ratings (p < 0.001) [12]. Rudin et al. identified \"optimizing sparse logical models such as decision trees\" as the #1 grand challenge in interpretable ML [6], distinguishing inherently interpretable models from post-hoc explanations. While we acknowledge the limitation regarding interpretability analysis in our experiments, the established theoretical foundations and extensive RL literature clearly support decision trees as a suitable interpretable model class for policy learning.\n\n>The theoretical convergence guarantee assumes that the class of decision tree policies can represent the optimal policy ... where the authors acknowledge that small trees are fundamentally limited in expressivity.\n\nWe thank the reviewer for this important observation. The reviewer is correct that Proposition 2's assumption requiring decision tree policies to represent the optimal policy is strong and often unrealistic. To clarify: Proposition 2 establishes that SPOT converges to the globally optimal policy within the constrained decision tree policy space, not the unconstrained MDP optimum. In practice, we expect this assumption to be violated for most problems with small trees, but this doesn't diminish SPOT's value since it still finds the best possible tree policy given size constraints while avoiding poor local optima within the tree space. Moreover, the resulting policies are more robust and interpretable.\n\nWe acknowledge that this limitation is inherent to all optimal decision tree methods (including OMDT). SPOT’s advantage lies in its computational efficiency for identifying the optimal tree, rather than in overcoming the expressivity constraint. \n\n\n>\"This significantly improves runtime and scalability compared to previous methods\" ... \"OMDT (5m)\" is unnecessary and unfair.\n\nWe thank the reviewer for this important point. The reviewer is correct that our main experiments with uniform 60-minute budgets do not directly demonstrate speedup. We address this with dedicated runtime experiments **in Appendix B.3**, which compare solving identical optimization problems using (i) Gurobi directly, (ii) serial RSBB, and (iii) parallel RSBB. These results show substantial speedups for large problems—for example, parallel RSBB solves the firewire benchmark in 15.91 seconds versus 11,528 seconds for Gurobi, and completes csma_2_4 in 42.57 seconds while Gurobi exceeds the 14,800-second limit. We agree that the main text should better emphasize these runtime comparison results to support our speedup claims.\n\n**References**\n\n[1] Glanois et al., \"A survey on interpretable reinforcement learning,\" *ACM Computing Surveys*, 2024.\n\n[2] Vos, D., & Verwer, S., \"Optimal Decision Tree Policies for Markov Decision Processes,\" *Proceedings of IJCAI*, 2023.\n\n[3] Koirala, R., et al., \"Decision Tree Policies for Offline Reinforcement Learning,\" *Conference on Robot Learning (CoRL)*, 2024.\n\n[4] Delfosse, Q., et al., \"Interpretable and Explainable Logical Policies via Neurally Guided Symbolic Abstraction,\" *Advances in Neural Information Processing Systems (NeurIPS)*, 2023.\n\n[5] Rudin, C., et al., \"Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges,\" *Statistics Surveys*, 2022.\n\n[6] Rudin, C., \"Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead,\" *Nature Machine Intelligence*, 2019.\n\n[7] Liu, C., et al., \"Gradient Boosting Reinforcement Learning,\" *Proceedings of ICML*, 2025.\n\n[8] Ye, Z., et al., \"LICORICE: Label-Efficient Concept-Based Interpretable Reinforcement Learning,\" *Proceedings of ICLR*, 2025.\n\n[9] Liu, H., et al., \"Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming,\" *Proceedings of ICLR*, 2025.\n\n[10] Kantaros, Y., et al., \"Formal Verification of Decision-Tree-Controlled Continuous-Time Systems,\" *Advances in Neural Information Processing Systems (NeurIPS)*, 2023.\n\n[11] Kook, J., et al., \"On the Computational Hardness of Interpreting Ensemble Models,\" *Proceedings of ICML*, 2025.\n\n[12] Silva, A., et al., \"Optimization Methods for Interpretable Differentiable Decision Trees Applied to Reinforcement Learning,\" *Proceedings of AISTATS*, 2020.\n\n[13] Bastani, O., et al., \"Verifiable Reinforcement Learning via Policy Extraction,\" *Advances in Neural Information Processing Systems (NeurIPS)*, 2018.\n\n[14] Lipton, Z. C., \"The Mythos of Model Interpretability,\" *Communications of the ACM*, 2018.\n\n[15] Breiman, L., et al., \"Classification and Regression Trees,\" *Routledge*, 1984.\n\n[16] Quinlan, J. R., \"Induction of Decision Trees,\" *Machine Learning*, 1986.\n\n[17] Loh, W. Y., \"Decision trees: From efficient prediction to responsible AI,\" *PMC*, 2022.\n\n[18] Huysmans, J., et al., \"An empirical evaluation of the comprehensibility of decision table, tree and rule based predictive models,\" *Decision Support Systems*, 2011.\n\n[19] Bell, A., et al., \"It's Just Not That Simple: An Empirical Study of the Accuracy-Explainability Trade-off in Machine Learning for Public Policy,\" *Proceedings of FAccT*, 2022."}, {"review_id": "7Jz6u7eKJt", "reviewer": "Reviewer_CDVk", "summary": "The paper presents a novel method for computing policies for Markov decision processes (MDPs) represented as decision trees.\nIn particular, the scalability issues arising in previous approaches are addressed through a new formulation of the underlying optimization problem. These MILPs can be decomposed, allowing for parallelized optimization. \nAn experimental evaluation compares the new approaches with a baseline.", "questions": "Q1. Why does SPOT outperform SPOT+WS on some benchmarks (sys_ad, tic_vs_ran, ...)? Is the initial solution used as a warm start worse than the standard initialization of SPOT in these cases?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n+ The paper is overall well-written.\n+ The method addresses important limitations of previous work.\n+ The key theoretical properties one would expect (optimality, convergence) are proven.\n+ The experimental evaluation shows improvements over the state-of-the-art baseline on all benchmarks.\n\n\n## Weaknesses\n\n- There are some (minor) issues with parts of the technical presentation, in particular around decision trees and the MILP encoding.\n\nIn more detail:\n\nThere is a lack of preliminaries on decision trees. There is no clearly marked definition, and while the key ingredients are in the paper (l183-190),\nI think the paper would become clearer and more self-contained if decision trees were briefly introduced, similarly to how MDPs are introduced. \nIn a similar vein, the decision trees rely on some set of features F that currently appear out of nowhere. It would make sense to connect the set of features to the MDPs you consider (i.e., via a factored state-space or a labeling function).\n\nWhile the MILP formulation is rather straightforward, its presentation could be improved. In particular, constraints 4c and 4d are the two most complicated constraints that require a more detailed explanation beyond what's currently there. More explanation on what \"appropriate branching behavior\" and \"directing states correctly\" mean is necessary here. \n\nI would also encourage making more explicit what symbols are variables (and their allowed domains) and what are constants.\n\n## Typos / other comments\n\n- Mention that additional experimental results may be found in the appendix.\n- I find it a bit weird that Frozen Lake is used as an example in the introduction, but is not present in the experiments.\n- l280: global -> globally\n- Eq.9: undtm -> use a symbol like \\bot\n- l298: \"We evaluate our algorithm by comparing it to OMDT [23] on large-scale MDPs.\" I suppose these MDPs are large-scale in the context of decision-tree policies, but in general, MDPs with |S| < 10000 should not be considered large-scale. Make this remark more accurate.\n- l304: SPOT1 -> I think you meant something like \"SPOT (Alg. 1)\"\n- The use of a warm start shows up out of nowhere in the experiments. It would be better to (briefly) discuss this option earlier in the paper.", "was_revised": true, "final_justification": "I believe this paper is a strong contribution, and the authors have addressed all my concerns in the rebuttal. I continue to recommend acceptance.", "rebuttal": "Thank you for your thoughtful and constructive review of our paper. We appreciate your positive assessment and the opportunity to clarify and strengthen our contributions.\n\n> There is a lack of preliminaries on decision trees. There is no clearly marked definition, and while the key ingredients are in the paper (l183-190), I think the paper would become clearer and more self-contained if decision trees were briefly introduced, similarly to how MDPs are introduced. In a similar vein, the decision trees rely on some set of features F that currently appear out of nowhere. It would make sense to connect the set of features to the MDPs you consider (i.e., via a factored state-space or a labeling function).\n\nWe sincerely thank the reviewer for this valuable suggestion to enhance the paper’s clarity and self-containment. We will include detailed and formal preliminaries on optimal decision trees in Section 2 if the paper is accepted. The definition of our tree model primarily follows the formulations used in the optimal decision tree literature, particularly Hua et al. (2022) [1] and Bertsimas and Dunn (2019) [2]. In the following, we provide a brief overview.\n\n**Decision Trees for Policy Representation**\n\nA decision tree is a hierarchical structure that maps state features to actions through a sequence of binary tests. Formally, a decision tree of depth $D$ consists of:\n\n- **Decision nodes** $T_D = \\{1, \\ldots, \\lfloor T/2 \\rfloor\\}$ where $T = 2^{D+1} - 1$\n- **Leaf nodes** $T_L = \\{\\lfloor T/2 \\rfloor + 1, \\ldots, T\\}$ \n- **Splitting rules**: Each decision node $t$ performs a test of the form $x_j \\leq \\theta_t$ for feature $j$ and threshold $\\theta_t$\n- **Action assignments**: Each leaf node $\\ell$ is assigned an action $a_\\ell \\in A$\n\nThe decision tree policy $\\pi(i)$ for state $i$ is determined by traversing from the root to a leaf based on the feature vector $x_i$, then returning the action assigned to that leaf.\n\nThis formalization connects the abstract MDP states to the concrete tree structure through the feature mapping $\\phi$, making the approach more transparent.\n\n> While the MILP formulation is rather straightforward, its presentation could be improved. In particular, constraints 4c and 4d are the two most complicated constraints that require a more detailed explanation beyond what's currently there. More explanation on what \"appropriate branching behavior\" and \"directing states correctly\" mean is necessary here.\n    \nThank you for this important feedback regarding the clarity of constraints (4c) and (4d). We refer these two constraints to the work of Hua et al. (2022) [1] and Bertsimas and Dunn (2019) [2]. We will provide much more detailed explanation in the paper once accepted.\n\n**Constraint (4c) - Left Branch Conditions:**\n$a^T_m(x_i + ε_{im} - ε_{min}) + ε_{min} ≤ b_m + (1 + ε_{max})(1 - z_{it})$\n    \n- **When $z_{it} = 1$** (state i assigned to leaf t): Enforces $a^T_m x_i ≤ b_m$ for all ancestor nodes m where the path goes left\n- **When $z_{it} = 0$**: Big-M term deactivates the constraint    \n    \n**Constraint (4d) - Right Branch Conditions:**\n $a^T_m x_i ≥ b_m - (1 - z_{it})$\n    \n- **When $z_{it} = 1$**: Enforces $a^T_m x_i ≥ b_m$ for all ancestor nodes m where the path goes right\n- **When $z_{it} = 0$**: Constraint is relaxed\n\nThese constraints ensure **path consistency**: if state $i$ is assigned to leaf $t$, its features must satisfy every splitting condition along the root-to-leaf path. This prevents impossible assignments where a state reaches a leaf through a path inconsistent with its feature values. A detailed reference of the seting of $\\epsilon$ can check Appendix A of Hua et al. (2022)[1] and Chapter 8.2 of Bertsimas and Dunn (2019) [2] .\n\n> I would also encourage making more explicit what symbols are variables (and their allowed domains) and what are constants.\n\nThank you for this important feedback. We acknowledge that our notation could be much clearer in distinguishing between optimization variables and problem constants. The current presentation intermixes decision variables (e.g., $a_{jt} \\in {0,1}$, $b_t \\in [0,1]$, $\\mu_{ik} \\in [0,1]$) with fixed MDP parameters (e.g., $P_{i,i',k}$, $R_{i,i',k}$, $\\gamma$) and algorithm constants (e.g., $\\epsilon$, $\\Phi_i^{\\pi^{\\text{old}}}$).\n| Category | Description | Example Variables |\n|----------|-------------|-------------------|\n| **Decision Variables**| Optimization variables to be solved | $a_{jt} \\in \\{0,1\\}$, $b_t \\in [0,1]$, $\\mu_{ik} \\in [0,1]$ |\n| **MDP Parameters**| Fixed transition probabilities and rewards | $P_{i,i',k}$, $R_{i,i',k}$, $\\gamma$ |\n| **Algorithm Constants**| Fixed hyperparameters and computed values | $\\epsilon$, $\\Phi_i^{\\pi^{\\text{old}}}$ |\n| **State/Action Indices**| Index sets for states and actions | $i, i' \\in \\mathcal{S}$, $k \\in \\mathcal{A}$ |\n| **Time Indices**| Temporal or iteration indices | $t$|\n    \n\n> I find it a bit weird that Frozen Lake is used as an example in the introduction, but is not present in the experiments.\n\nThank you for this observation. Frozen Lake was chosen as an illustrative example in the introduction due to its simple structure that clearly demonstrates how decision tree policies work. However, in the experiments, we focus on larger, more challenging MDPs where SPOT's scalability advantages over OMDT are most apparent. \n\n> Mention that additional experimental results may be found in the appendix.    \n> l280: global -> globally\n> Eq.9: undtm -> use a symbol like \\bot\n> l298: \"We evaluate our algorithm by comparing it to OMDT [23] on large-scale MDPs.\" I suppose these MDPs are large-scale in the context of decision-tree policies, but in general, MDPs with |S| < 10000 should not be considered large-scale. Make this remark more accurate.\nl304: SPOT1 -> I think you meant something like \"SPOT (Alg. 1)\"\n> The use of a warm start shows up out of nowhere in the experiments. It would be better to (briefly) discuss this option earlier in the paper.\n\nThank you for these helpful presentation suggestions, we will address them in the new version.\n\n> Q1. Why does SPOT outperform SPOT+WS on some benchmarks (sys_ad, tic_vs_ran, ...)? Is the initial solution used as a warm start worse than the standard initialization of SPOT in these cases?\n\nThank you for this excellent question. Warm start does not guarantee better performance compared to standard initialization - it simply provides a potentially good starting point. The effectiveness depends on the problem's characteristics and the search heuristics employed.\n\nOur algorithm performs gradient-like updates at each iteration, but the optimization landscape is highly non-convex with multiple local optima. It's possible that the standard random initialization lands in a region with better local geometry than the OMDT warm start solution, leading to superior final solutions within the same time budget. Additionally, the warm start solution from OMDT (generated under a 5-minute constraint) may not always represent the best starting point for SPOT's iterative refinement process.\n\nThis phenomenon is not uncommon in non-convex optimization where different initialization strategies can lead to different local optima, and the \"better\" starting point is problem-dependent.\n\n**References**\n[1] Hua et al., \"A Scalable Deterministic Global Optimization Algorithm for Training Optimal Decision Tree,\" *Advances in Neural Information Processing Systems (NeurIPS)*, 2022.\n\n[2] Dimitris Bertsimas and Jack Dunn, \"Machine learning under a modern optimization lens,\" *Dynamic Ideas LLC*, 2019."}, {"review_id": "BNgxmoICqK", "reviewer": "Reviewer_LbzP", "summary": "The authors study the problem of optimizing decision tree policies in Markov Decision Processes (MDPs).\nIn particular, the authors introduce SPOT, a novel framework for learning interpretable and high-performing decision tree policies in MDPs.\nUnlike traditional black-box reinforcement learning models, SPOT directly optimizes decision tree structures using a mixed-integer linear programming formulation.\nTheoretical and empirical results show that SPOT achieves fast runtimes and good performance across several benchmark MDPs, generating compact and interpretable policies even for large-scale problems.", "questions": "Page 1:\nYou argue that directly learning interpretable decision tree policies is preferable to post-hoc explanations of black-box models.\nWhat are the key limitations you've observed with explanation methods like LIME or SHAP in RL settings?\n\nPage 2:\nFigure 1:\nPlease elaborate on the caption.\nWhat is the main takeaway here?\n\nPage 3:\nWhere is Section 1.1? :)\n\nPage 4:\nCan you please put formal statements of your results in the Introduction?\n\nPage 5:\nHow does SPOT perform when the optimal policy cannot be well-approximated by a shallow decision tree?\nGiven that decision trees are inherently limited in expressiveness with small depth, it would be interesting to see how SPOT handles situations where a more complex policy is required.\n\nPage 6:\nThe explanations are very good :)\n\nI do not understand lines 200 -- 204.\n\nPage 7:\nHow does the reduced-space branch-and-bound framework maintain solution quality while only branching on first-stage (tree structure) variables?\n\nPage 8:\nCan you please clarify the purpose of using the Reduced-Space Branch-and-Bound (RSBB) method in the SPOT algorithm? :)\n\nHow does the RSBB framework ensure scalability and convergence when optimizing decision-tree policies?\n\nPage 9:\nIn your experiments, SPOT+WS significantly outperforms OMDT on some benchmarks.\nCan you please elaborate on the characteristics of these environments that make SPOT particularly effective? :)\n\nThe Conclusion section is too small :)\nPlease elaborate on future work.", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe theoretical guarantees of the main theorems.\n\nWeaknesses:\nSee Questions below.", "was_revised": true, "final_justification": "The authors have effectively addressed my comments and concerns.", "rebuttal": "We thank the reviewer for your thoughtful comments that helped us improve this paper. Below, we would like to provide point-to-point responses to your major comments mentioned and hope they are to your satisfaction.\n\n> Page 1: You argue that directly learning interpretable decision tree policies is preferable to post-hoc explanations of black-box models. What are the key limitations you've observed with explanation methods like LIME or SHAP in RL settings?\n    \nWe appreciate the reviewer's insightful question about the limitations of post-hoc explanation methods in RL settings. We agree that elucidating the precise shortcomings of these popular techniques in the RL setting strengthens the motivation for our work. Below we summarise the main limitations of methods like LIME and SHAP when applied to RL policies:\n\n- **Inconsistent across nearby states**: The stochastic nature of RL environments and policies can lead to unstable explanations across similar states, making it difficult to derive consistent insights about the policy's behavior.\n- **Ignores long‑term value**: Attribution is usually computed w.r.t. immediate Q‑value or probability of the chosen action, not the downstream return.\n- **Heavy computation cost**: Generating explanations for every state-action pair during deployment introduces significant computational costs.\n- **Non‑stationary policy distribution**: During training the data distribution shifts; explanations computed mid‑training quickly become obsolete.\n\nIn contrast, our interpretable decision tree approach learns a global, consistent, and symbolic policy that can be directly inspected and validated by domain experts without incurring additional computational overhead.\n    \n> Page 2: Figure 1: Please elaborate on the caption. What is the main takeaway here?\n    \nThank you for pointing this out. We will expand the caption to better convey the key message. Figure 1 demonstrates an interpretable policy learned by our decision tree approach, where each path from root to leaf represents a clear decision rule. The main takeaway is that our method produces policies that are directly interpretable—domain experts can trace any decision by following the tree structure, understanding exactly which features lead to specific actions, unlike black-box neural network policies that require post-hoc explanations.\n    \n>Page 3: Where is Section 1.1? :)\n\nThank you for catching this formatting issue. Section 1.1 begins on Line 38, page 2.\n\n>Page 5: How does SPOT perform when the optimal policy cannot be well-approximated by a shallow decision tree? Given that decision trees are inherently limited in expressiveness with small depth, it would be interesting to see how SPOT handles situations where a more complex policy is required.\n\nThis is an excellent question that highlights a fundamental trade-off in our approach. Empirically, we found that even with limited expressiveness (e.g., depth $D=3$), SPOT can find competitive solutions for complex MDPs like `firewire` within the 60-minute computational budget. While shallow trees may not capture the full complexity of optimal policies in some domains, they often identify robust decision rules that perform well in practice. We acknowledge this limitation and plan to investigate in future work: (1) adaptive depth selection based on problem complexity, and (2) hybrid approaches that maintain interpretability while increasing expressiveness for domains requiring more complex policies.\n  \n>I do not understand lines 200 -- 204.\n\nWe apologize for the unclarity in our explanation. We will revise lines 200-204 to improve clarity. Specifically:\n\n- Constraints (4a) and (4b) both ensure that a decision tree leaf only represents one action (one policy one action) and one state can only corresponding to one unique policy.\n- When a branching node has a split ($d_t > 0$): Constraints (4c) and (4d) activate the standard branching logic—states go left if their feature value is below the threshold b_m, and right otherwise.\n- When a node has no split ($d_t = 0$): Constraints (4e) and (4f) ensure special handling. Since no branching occurs, all states reaching this node must proceed to the right branch. This is achieved by setting the threshold $b_t = 0$ (from 4f), which, combined with constraint (4d), forces all states rightward since any feature value $x_i ≥ 0$.\n\nMore details could refer to the Appendix A of Hua et al. (2022) [1] and Section 8.2 of Bertsimas and Dunn (2019) [3]. We will also rewrite this section with clearer language and possibly add a small example to illustrate this branching logic more intuitively.\n\n \n>Page 7: How does the reduced-space branch-and-bound framework maintain solution quality while only branching on first-stage (tree structure) variables?\n\nBriefly speaking, at each node of our RSBB procedure, we construct a lower bound by relaxing the non-anticipativity constraints (i.e., allowing each sample to have its own tree model), while we compute a simple upper bound by fixing the first-stage decision variables to the current feasible solution. With these two bounding strategies, the convergence of RSBB is ensured by branching exclusively on the first-stage variables, while **branching on the second-stage variables is handled implicitly through the evaluation of the lower and upper bounds**. Detailed proofs can be found in Cao and Zavala (2019)[2] and Hua et al. (2022)[1].\n  \n>Page 8: Can you please clarify the purpose of using the Reduced-Space Branch-and-Bound (RSBB) method in the SPOT algorithm? :)\n    \nThe RSBB method serves as a computational efficiency enhancement. It achieves the same optimal solution quality as standard branch-and-bound but significantly faster by exploiting the problem structure, **branching only on tree structure variables** while solving action assignments analytically. Moreover, both bounding strategies can be evaluated by independently solving scenario-specific subproblems, which enables efficient parallel computation. These efficiency improvements are crucial for the empirical success of SPOT on larger problems.\n\n>How does the RSBB framework ensure scalability and convergence when optimizing decision-tree policies?\n\nOur scalability are achieved through the reduce of branching variables and the trivial parallelism for solving the bounding problems in each BB node. As a systematic enumeration algorithm. The convergence is guaranteed by systematically exploring the solution space and dividing it into smaller subproblems, and using bounding functions to eliminate portions of the space that cannot contain the optimal solution. \n\n>Page 9: In your experiments, SPOT+WS significantly outperforms OMDT on some benchmarks. Can you please elaborate on the characteristics of these environments that make SPOT particularly effective? :)\n\nThis is an insightful question. Due to the highly non-convex nature of the decision tree optimization problem and its complex loss landscape, we cannot yet provide definitive characteristics that predict when SPOT will excel. Our empirical results suggest SPOT performs particularly well in large scale MDP and where good warm-start solutions exist, but a thorough theoretical characterization remains an important direction for future work.\n    \n>Page 4: Can you please put formal statements of your results in the Introduction?\n>The Conclusion section is too small :) Please elaborate on future work.\n    \nThank you for these constructive suggestions. We will revise our paper in the new version.\n\n**References**\n\n[1] Hua et al., \"A Scalable Deterministic Global Optimization Algorithm for Training Optimal Decision Tree,\" *Advances in Neural Information Processing Systems (NeurIPS)*, 2022.\n\n[2] Cao, Y., & Zavala, V. M., \"A scalable global optimization algorithm for stochastic nonlinear programs,\" *Journal of Global Optimization*, 2019.\n\n[3] Dimitris Bertsimas and Jack Dunn, \"Machine learning under a modern optimization lens,\" *Dynamic Ideas LLC*, 2019."}]

Author rebuttal:

Meta-review: Three out of four reviewers (iZpk, CDVk, LbzP) were ultimately positive, recognizing the method's technical soundness, theoretical guarantees, and empirical improvements over baselines. Reviewer CDVk noted it as "a strong contribution" with proven optimality and convergence properties, while Reviewer LbzP praised the "excellent" theoretical guarantees and significance.

The main dissenting voice was Reviewer 3Gn1, who raised concerns about narrow relevance to modern RL, sparse literature review, and questionable interpretability claims. However, the authors provided comprehensive rebuttals addressing these concerns, including expanded literature positioning, a detailed interpretability case study, and clarification of theoretical assumptions.

While Reviewer 3Gn1 maintained their borderline reject position, the other reviewers found the work technically solid with clear contributions to interpretable RL. The method addresses an important problem—finding provably optimal, interpretable policies—which is valuable for safety-critical applications even if not directly applicable to deep RL settings.

The work provides novel algorithmic contributions through its reduced-space branch-and-bound approach, demonstrates scalability improvements over existing methods, and maintains theoretical rigor with convergence guarantees.
Decision: Accept (poster)