Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization

We thank the reviewer for their time and valuable feedback!

SYMPOL is mentioned to have 50+ nodes, which could become quite unwieldy or difficult to interpret, but we do not see such examples in the paper. It would be illustrative to see a standard SYMPOL policy in addition to the cleaned up versions in Figures 7/9.

We understand this concern. Unfortunately, it is difficult to visualize such policies in the context of a paper which is why we decided to use a comparatively small example. Nonetheless, we added an example of a large tree with 59 nodes for CartPole in the appendix (now Figure 10). While the tree is comparatively large, we can observe that the main logic is contained in the nodes at higher levels, focusing on the pole angle and the pole angular velocity. The less important features are in the lower levels where splits are often made on the cart position, which is not required to solve the task perfectly. Frequently, additional nodes cover some minor additional differences (like first splitting Pole Angle < 0.0079, and then splitting Pole Angle < 0.0081). This also highlights the potential for advanced post-hoc pruning methods to increase interpretability and potentially even generalization, which is subject to future work. However, we want to note that trees of this size are not specific to SYMPOL. Related methods have similar, often even higher tree sizes, as shown in Table 10.

While the framework is sound and the results are strong, the overall novelty of the framework is limited. Apart from introducing a dynamically growing replay buffer, the technical contributions are largely a combination of existing techniques.

We agree that a core aspect of our method is the integration of GradTree into existing RL frameworks. While these methods are individually well-established, we believe that integrating GradTree into a dynamic task is a significant contribution. This integration has not been achieved previously and could have a substantial impact on the community, as well as future research in the active field of tree-based RL. Furthermore, directly applying GradTree within RL frameworks leads to unstable and ineffective outcomes, as the inherent instability in training tree-based models poses distinct difficulties in this setting.

To achieve stability and effectiveness in RL, we developed several essential adjustments. As demonstrated in our ablation study (Figure 5), these modifications are crucial for SYMPOL to maintain interpretability and achieve robust performance under end-to-end gradient-based optimization. Without these adjustments, both stability and effectiveness in RL applications would be significantly compromised.

However, with these adaptations in place, SYMPOL is framework-agnostic, allowing for straightforward integration into diverse RL algorithms beyond PPO. As illustrated in Section A.1 of the appendix, SYMPOL integrates seamlessly with A2C, demonstrating superior performance compared to alternative methods. This adaptability highlights the broad applicability and robustness of our approach across RL frameworks. In the revised version of the paper, we state our distinct contributions more explicitly in the introduction (L70-L78).

As the paper relies heavily on the contribution of GradTree, it would be helpful to have an overview of that work here, so that the finished paper reads as a more self-contained work.

We agree that it is important to provide an overview of GradTree in this paper. To provide a better understanding, we included an additional figure (now Figure 2), to clarify how GradTree works. However, due to space constraints, it is unfortunately not possible to include a more detailed description of GradTree here.

We sincerely appreciate the reviewer’s time and thoughtful feedback! We will address your concerns and questions in the following:

However, with the current experiments, it is unclear to me if the good experimental results are due to the use of GradTree or to the stabilizing of the training or both. But in any case, the contribution is not clear.

The good results originate from both the use of GradTree in combination with a stabilization of the training. Training stabilization is crucial to make GradTree work in a dynamic environment like RL, as shown in the ablation study (Figure 5). However, only GradTree can utilize the benefits of stabilization. It cannot be used to stabilize the training of alternative tree-based models. For these models, poor performance does not originate from instability during the training (as shown by the good results for MLP and SDT policies), but rather from information loss that occurs during distillation or discretization. However, it is not possible to integrate the proposed stabilization procedure into processes like distillation. This is because the model already uses the complete data from independent trajectories to fit the interpretable policy. Accordingly, the proposed stabilization can only be applied to SYMPOL and not to alternative methods for learning DT policies post-hoc. We agree that this should be explained in more detail and therefore clarified the distinct contributions of our method (L70-L86).

Contributions. Is the contribution plugging GradTree into PPO ? I do find the ablation study insightful on why the training process needs strong stabilyzing and digging this further could be a nice contribution.

TL;DR: Our approach extends beyond simply incorporating GradTree into PPO by developing essential adjustments that enable a stable, effective, and interpretable model and facilitate seamless integration into existing RL frameworks.

While our approach builds on the concept of gradient-based, axis-aligned, hard decision trees (GradTree), we extend it considerably to address the unique challenges of RL. Directly applying GradTree within RL frameworks results in unstable and ineffective outcomes, as the inherent instability in training tree-based models poses distinct difficulties in this setting.

To achieve stability and effectiveness in RL, we developed several essential adjustments. As demonstrated in our ablation study (Figure 5), these modifications are crucial for SYMPOL to retain interpretability while achieving robust performance under end-to-end gradient-based optimization. Without these adjustments, both stability and effectiveness in RL applications would be significantly compromised.

However, with these adaptations in place, SYMPOL is framework-agnostic, allowing for straightforward integration into diverse RL algorithms beyond PPO. As illustrated in Section A.1 of the appendix, SYMPOL integrates seamlessly with A2C, demonstrating superior performance compared to alternative methods. This adaptability highlights the broad applicability and robustness of our approach across RL frameworks. To clarify the conributions of you paper, we refined the corresponding paragraph in the introduction (L70-L86).

The stabilization of the training process through dynamic buffer and batch sizes is a noteworthy finding from our study. We agree with the reviewer and are planning to investigate this component and the potential impact on the broader field of RL in future work.

I think your paper is good and I raised my score to 6. I am willing to raise it to 8 if you do the following:

Thank you for increasing your score and giving us the opportunity to refine our work further by incorporating your valuable feedback. Please find our responses below. Several adjustments have already been implemented in the revised PDF, with additional changes highlighted in red in the appendix. However, some changes require additional time, and we will include them as soon as possible.

Well you do also have this dense tree architecture which is in my opinion another perspective on Silva's work and is not fundamentally different as you claim. But I might be wrong! Please convince me!

I mean there is no need to think to hard to see that SYMPOL cannot actually solely retains a hard tree right? You do have to approximate or soften or densify the tree at some point.

We acknowledge that the dense formulation shares similarities with Silva's work and other methods utilizing soft decision trees (SDTs). However, the key distinction in our dense representation lies in the use of two separate weight vectors at each internal node, rather than a single weight vector and bias. These two vectors correspond to the components of a standard axis-aligned split: (1) the threshold determining the decision boundary, and (2) the feature selected for splitting.

The primary difference, however, stems from the training procedure, where our approach fundamentally diverges from Silva's work and SDTs/DDTs. Specifically, our method strictly retains a hard tree structure throughout training. Unlike existing methods that soften or approximate the tree during training, the hard tree structure in our model is preserved even during training. Softening is only introduced for gradient computation. When calculating the tree’s output, the structure remains hard and axis-aligned. For example, in Equation 5, we use the rounding operation to enforce hard decisions, which is excluded only during the backward pass where gradients are computed using the straight-through (ST) operator.

Similarly, we apply the hardmax function to ensure that the split index vector remains one-hot encoded during the forward pass, maintaining univariate, axis-aligned splits. During the backward pass, this non-differentiable operation is excluded, allowing gradients to be computed for a soft model. However, in the forward pass, our model always retains a hard and axis-aligned structure due to the ST operator. This approach contrasts with existing methods, where the tree remains soft during both the backward and forward passes. Consequently, SYMPOL optimizes the exact hard and axis-aligned policy that will be applied later, eliminating the need for post-processing.

Thank you for working so hard. I raised my score to 8.

I will ask for this work to be highlighted (raise my score to 10) if:

• Make SYMPOL work on control tasks be feeding linear combination (affine) of features to your model like Kohler and Delfosse 2024
• Make a clean Python library open source for everyone to use SYMPOL; it should be compatible with gymnsaium

We sincerely thank the reviewer for their time and insightful feedback!

The difference between SYMPOL and other baselines is not clear. The preliminaries section would benefit for a bigger explanation on GradTree, as its integration to PPO is the main contribution and what distinguish this work from many existing interepretable baselines such as NUDGE, INSIGHT, GBRL and SCoBots ([1]).

The main difference between SYMPOL and the mentioned baselines [1,4,5,6] is the conceptual integration into existing RL frameworks. While existing methods that integrate symbolic policies into existing frameworks require modifications of the RL framework itself, SYMPOL does not require such modifications. By utilizing GradTree, a DT policy can be learned directly from the policy gradients, making the proposed method framework-agnostic.

We clarified the distinction of SYMPOL from alternative methods at the corresponding positions in the revised version of the paper (L180-L184). Additionally, we extended the explanation of GradTree including additional figures to give a better understanding of the method (L213-L227; L247-L252).

It also took me quite some time to understand that SA-DT is equivalent to running Dagger or VIPER with their MLP.

In the revised version, we clarified the relationship between SA-DT and VIPER, which was not explicitly outlined in the initial submission (L343-L346). In general, SA-DT can be considered as a version of DAGGER. Therefore, SA-DT and VIPER are conceptually similar, but VIPER (Q-DAGGER) includes advanced sampling and weighting strategies for training samples — techniques not incorporated in SA-DT, as used, for example, by Silva et al. (2020). Furthermore, we included an additional experiment directly comparing VIPER, SA-DT and SYMPOL (Section A.3). The conclusions remain consistent with the ones presented in the initial version of the paper.

Thank you for your clarification. I checked the paper, the provided modifications improve it a lot, and you clarified the difference between SA-DT and VIPER.

However, I think that the claim that SYMPOL is the only RL framework-agnostic method is wrong.

• The differentiable logic policies of NUDGE are optimized using the policy gradients
• INSIGHT and SCoBots simply extract EQL and Object-centric DT from policy gradients' optimized NNs

This claim would anyway not change my ratings, as I consider SYMPOL a nice contribution to the Interpretable RL field.

Finally, the OCAtari environments are not much more "continuous" than the minigrid ones. Take Pong for example, if you consider the 3 relevant objects: the player, enemy, and the ball. The x position of the enemy and the player being fixed, (they can be discarded, as explained by [7]).

You thus end up with 4 variables: Player.y, Enemy.y, Ball.x, Ball.y. These values have a discrete range of ~100 values.

Eventually you can add dx and dy for each object (with even smaller range).

Would SYMPOL not be applicable to such an environment ?

I consider that your method does not need extra evaluation to confirm the paper's claim, and that the claims are enough to make it accepted, so don't feel pressure to run these experiments, I am just trying to understand if someone could run them if they wanted to compare SYMPOL to other interpretable RL method.

Thanks for your answer, I am already raising my score.

The reviewer is confused about the information loss experiments, described in Fig 1 and Table 3. Is the test reward on the same environment as the trained one? If so, why is there a performance drop of (Silva et al. (2020))? Did you mean the trained model has a stochastic probability while the test model is greedy that is, selecting the action with the maximum Q?

TL;DR: Training evaluates original models (e.g., neural networks for SA-DT), while testing uses interpretable, deterministic models (e.g., distilled DTs) on distinct random seeds. Clarifications and additional training curves have been added to the revised paper.

Thank you for your feedback and for highlighting the need for clarification regarding the information loss experiments in Figure 1 and Table 3. To clarify, the test environments indeed differ from the training environments due to distinct random seeds used in the test phase. This explains why the rewards are not identical for SYMPOL. For other methods, however, the differences in performance additionally arise from the contrasting models used in training and testing phases. Specifically, during training, loss is reported on the model in its original form (e.g., the neural network policy for SA-DT), while during testing, we evaluate the interpretable model (e.g., the distilled decision tree for SA-DT), which operates in a deterministic manner.

We acknowledge that these details were not sufficiently explained in the original figure and have revised the paper accordingly to make this distinction clearer (L35-L39). Also, we included an additional figure on the training curves in the main paper (now Figure 3) which should provide additional clarification.

[1] Farquhar, Gregory, et al. "Treeqn and atreec: Differentiable tree-structured models for deep reinforcement learning." arXiv preprint arXiv:1710.11417 (2017).

[2] Jiang, Zhengyao, and Shan Luo. "Neural logic reinforcement learning." International conference on machine learning. PMLR, 2019.

[3] Cao, Yushi, et al. "GALOIS: boosting deep reinforcement learning via generalizable logic synthesis." Advances in Neural Information Processing Systems 35 (2022): 19930-19943.

We appreciate the reviewer’s time and thoughtful feedback!

The reviewer is not convinced with the claim of "first method that trains a DT via stochastic policy gradient in an end-to-end manner". Making the learning of DTs differentiable has been investigated for a long time, such as [1]. It is safe to make this claim through a thorough literature review.

TL;DR: SYMPOL does not learn differentiable or soft DTs, but instead maintains univariate, hard decisions during training and inference. Clarifying paragraph was added to the revised paper.

We understand the concern raised by the reviewer and agree that this needs to be explained more thoroughly. Therefore, we have added an additional paragraph in the related work section distinguishing SYMPOL from existing methods involving Differentiable / Soft Decision Trees (L138-L143). We have also included the mentioned relevant references to the related work section (L131).

In related work, including [1], differentiable decision trees typically correspond to soft decision trees (SDTs), which achieve differentiability by relaxing discrete decisions related to feature and path selection at internal nodes. This approach is fundamentally different from SYMPOL, which does not use differentiable decision trees. Instead, SYMPOL leverages GradTree to optimize standard, non-differentiable decision trees through gradient descent. As a result, SYMPOL retains univariate, hard decisions, which are more interpretable than the oblique splits involving multiple features in SDTs and differentiable decision trees.

However, we agree that our initial claim might be misleading. We do not assert that ours is the first work that trains a DT via stochastic policy gradient in an end-to-end manner. As the reviewer notes, this approach has been frequently explored in related work. However, existing work typically focuses on Differentiable or Soft DTs for end-to-end learning, whereas we utilize hard, axis-aligned DTs while still preserving gradient-based optimization. To clarify, we have adjusted the claim in the abstract of the revised paper (L20-L23) and added a more detailed discussion and comparison with existing work in the related work section (L138-L143; L247-L252).

There are some other works focusing on learning a differentiable symbolic policy which is based on first-order logic, such as [2,3], which is not compared and discussed in this paper.

TL;DR: We focus on DTs providing greater flexibility through learnable feature-threshold comparison. References and discussion have been added to the revised paper.

Thank you for highlighting this relevant work. We have added the suggested references and included a comparison in our related work section. Both NLRL [2] and GALIOS [3] aim to synthesize symbolic policies using logical rules, leveraging differentiable inductive logic programming. This allows for gradient-based optimization, similar to SYMPOL. The main distinction lies in the type of symbolic policy optimized by each approach: SYMPOL learns a decision tree, whereas NLRL and GALIOS learn sets of logical rules. Although both approaches share similarities, DTs offer greater flexibility by not only combining atomic conditions but also comparing features against thresholds — a critical capability for handling continuous observation spaces. As noted in the related work section, this paper focuses on learning DT-based policies, so a direct experimental comparison with rule-based methods is beyond the scope of our work. Nevertheless, we briefly discuss these methods in the revised related work section (L100-L105).

Looks like that defining the syntax and semantics of DTs relies on human knowledge, maybe the reviewer is wrong, which can be clarified during rebuttal.

TL;DR: SYMPOL does not require human knowledge for defining the syntax and semantics of the DT.

When learning a DT with SYMPOL, no human knowledge or human interaction is required. The user only has to define the maximum depth of the tree which can be seen as a hyperparameter (or simply fixed to a high value like 10). The entire DT as RL policy is then learned end-to-end with gradient descent and the learned policy (which is a decision tree as for instance in Figure 4) can be inspected by the user. We hope that our answer clarified this. If there are any concerns remaining, please let us know so that we can refine our paper to avoid future confusion.

There are some typos in References.

Thank you for highlighting this. We have improved this in the revised version of the paper.

line 414- 415: "In RL, especially for smaller policies, the runtime is mainly determined by the actor-environment interaction..." - This sentence is hard to follow. Can the authors unpack this sentence?

We have unpacked and clarified the sentence as follows in the revised version of the paper (L428-L431): "In RL, the actor-environment interaction frequently constitutes a significant portion of the total runtime. For smaller policies, in particular, the runtime is mainly determined by the time required to execute actions within the environment to obtain the next observation, while the time required to execute the policy itself having a comparatively minimal impact on runtime."

Did this work simply incorporate GradTree into the PPO framework?

TL;DR: Our approach extends beyond simply incorporating GradTree into PPO by developing essential adjustments that enable a stable, effective, and interpretable model and facilitate seamless integration into existing RL frameworks.

Thank you for your constructive feedback. While our approach builds on the concept of gradient-based, axis-aligned, hard decision trees (GradTree), we extend it considerably to address the unique challenges of RL. Directly applying GradTree within RL frameworks results in unstable and ineffective outcomes, as the inherent instability in training tree-based models poses distinct difficulties in this setting.

To achieve stability and effectiveness in RL, we developed several essential adjustments. As demonstrated in our ablation study (Figure 5), these modifications are crucial for SYMPOL to retain interpretability while achieving robust performance under end-to-end gradient-based optimization. Without these adjustments, both stability and effectiveness in RL applications would be significantly compromised.

However, with these adaptations in place, SYMPOL is framework-agnostic, allowing for straightforward integration into diverse RL algorithms beyond PPO. As illustrated in Section A.1 of the appendix, SYMPOL integrates seamlessly with A2C, demonstrating superior performance compared to alternative methods. This adaptability highlights the broad applicability and robustness of our approach across RL frameworks. In the revised version of the paper, we discussed the contributions and advantages more thoroughly (L70-L85; L180-L184).

[1] Wei, Hua, et al. "Intellilight: A reinforcement learning approach for intelligent traffic light control." Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 2018.

[2] Yau, Kok-Lim Alvin, et al. "A survey on reinforcement learning models and algorithms for traffic signal control." ACM Computing Surveys (CSUR) 50.3 (2017): 1-38.

[3] Yu, Chao, et al. "Reinforcement learning in healthcare: A survey." ACM Computing Surveys (CSUR) 55.1 (2021): 1-36.

[4] Nambiar, Mila, et al. "Deep offline reinforcement learning for real-world treatment optimization applications." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.

[5] Yu, Zheng, et al. "Deep reinforcement learning for cost-effective medical diagnosis." arXiv preprint arXiv:2302.10261 (2023).

[6] Fatemi, Mehdi, et al. "Medical dead-ends and learning to identify high-risk states and treatments." Advances in Neural Information Processing Systems 34 (2021): 4856-4870.

We thank the reviewer for their time and valuable feedback!

This work evaluates its experiments on a series of toy tasks that could be easily solved. Can it achieve competitive performance in complex tasks, like Mujoco and Atari games?

TL;DR:SYMPOL excels in moderate-complexity tasks, where interpretability is crucial, and also holds potential for real-world applications in domains such as reinforcement learning for healthcare and traffic control.

While SYMPOL is technically adaptable to complex environments, we prioritize tasks where interpretability is both feasible and provides actionable insights. In high-complexity settings like Mujoco or Atari games, achieving holistic interpretability becomes challenging due to the model size and complexity required. The demonstrated strength of SYMPOL lies in tackling scenarios of moderate complexity, where its interpretability provides tangible benefits.

This, however, does not exclude real-world applications of the proposed method. Suitable scenarios could be traffic-light control [1,2] or healthcare [3,4] and medical diagnosis [5,6], where interpretability offers practical insights and transparency. Evaluating such use cases and quantifying the real-world impact of enhanced interpretability is an avenue for future research.

Future research could explore an ensemble-based approach, such as Gradient-Boosted Reinforcement Learning (GBRL), to enhance the scalability of SYMPOL for more complex tasks. However, evidence from GBRL suggests that tree-based methods are generally not well-suited for environments with unstructured data domains, such as Atari games. Similarly, tasks requiring complex physical modeling, like Mujoco, are more effectively addressed by neural network policies.

This work is also hard to follow, the contribution and the method should be highlighted and stated.

While our paper already includes a dedicated paragraph on the contributions in the introduction, we agree that this paragraph would benefit from more explicit emphasis on the relevant aspects. Therefore, we included a bullet-point list to clearly state the contribution of the method and hope this addresses the reviewer's concerns.

Please abatement the contribution of this work. This work is not the first to use DT to represent RL policy, i.e., the work "MIXRTs: Toward interpretable multi-agent reinforcement learning via mixing recurrent soft decision trees", arXiv:2305.10091, 2022. They utilized SDT in multi-agent RL complex tasks two years ago.

TL;DR: SYMPOL does not learn differentiable or soft DTs, but instead maintains univariate, hard decisions during training and inference. A clarifying paragraph has been added to the revised paper.

Thank you for highlighting additional related work on decision trees in reinforcement learning. However, we emphasize a fundamental distinction between our approach and the referenced work, "MIXRTs: Toward interpretable multi-agent reinforcement learning via mixing recurrent soft decision trees." Unlike soft decision trees (SDTs), which approximate decisions with probabilistic nodes, our method uses hard, axis-aligned DTs that enforce discrete decisions, leading to more interpretable policies. We will add the suggested work to our refined related work section. Additionally, we included a dedicated paragraph to distinguish our contribution from soft and differentiable decision trees (L131; L138-L143).

We also agree with the reviewer that our initial claim may have been misleading. We do not claim that our work is the first to use DTs to represent policies in reinforcement learning. As the reviewer notes, this approach has been extensively explored in prior work. However, existing work typically focuses on SDTs for end-to-end learning. Instead, we utilize hard, axis-aligned DTs while still preserving gradient-based optimization. To clarify, we have amended the claim in the abstract (L20-L23) and expanded the related work section with a more detailed discussion and comparison with existing methods (L138-L143; L247-L252).