Gradient Boosting Reinforcement Learning

Thank you for your detailed review and valuable feedback. Below we address each of your concerns.

1. Lack of theoretical proof of convergence & handling non-stationarity: While comprehensive theoretical analysis is beyond the current scope, GBRL builds upon established foundations from both gradient boosting and policy gradient theory. Each tree in our approach minimizes a functional gradient step, making GBRL's convergence analysis potentially related to known policy gradient convergence results. The recent work on softmax policy gradient convergence rates [1] shows O(1/t) convergence for tabular settings with true gradients. We believe similar analysis could potentially apply to GBRL, as our tree-based approximation maintains the key properties that enable convergence -- specifically, GBRL preserves the policy gradient's directional information while providing a piecewise approximation of the advantage landscape. Furthermore, GBT methods have convergence guarantees in various settings. Recent theoretical works have analyzed convergence for GBT on convex losses [2], and online gradient boosting methods have known convergence guarantees under certain conditions [3,4]. The work on non-parametric policy gradients [5] also provides a foundation for our approach. A full theoretical analysis would require examining how the tree-based approximation interacts with policy improvement dynamics and whether it preserves the Łojasiewicz condition identified in [1]. We believe our empirical evidence of convergence across diverse environments provides strong practical support for GBRL while setting the stage for future theoretical analysis.

2. Poor performance on high-dimensional unstructured tasks (Atari-RAM): We agree with your observation. GBRL's weaker performance in high-dimensional raw-feature spaces (such as Atari-RAM) arises from a fundamental difference in inductive biases between decision trees and NNs [6, 7]. Decision trees partition the input space according to single feature thresholds, whereas NNs learn complex feature compositions via continuous transformations. This makes NN more suited for environments where useful information is embedded in combinations of features. This highlights the complementary nature of GBRL to existing NN-based methods rather than positioning it as a replacement. We will expand our discussion in the revised paper to explicitly highlight this limitation and its implications.

3. Lack of comparisons to specialized architectures (TabNet, SAINT): The goal of this work is to combine the popular GBT tool with RL, analyze its performance, and overcome the challenges that this combination introduces. One major advantage that we found is GBT's robustness to OOD scenarios compared to NNs, and not only handling structured data. While specialized architectures like TabNet/SAINT excel at purely tabular data, our environments span a broader range of settings including those with mixed features, temporal dependencies, and various action spaces. Our primary focus was therefore on comparing with the standard MLP-based approaches most commonly used in RL rather than models optimized solely for tabular data. This allows us to assess GBRL's performance in the broader context of RL applications.

4. Computational cost: You raise a valid concern about the scalability of our approach. Please see our detailed response to Reviewer KuLP regarding the unbounded growth of the ensemble as the policy improves.

[1] Mei, Jincheng, et al. "On the global convergence rates of softmax policy gradient methods." International conference on machine learning. PMLR, 2020.
[2] Cortes, Corinna, Mehryar Mohri, and Dmitry Storcheus. "Regularized gradient boosting." Advances in neural information processing systems 32 (2019).
[3] Beygelzimer, Alina, et al. "Online gradient boosting." Advances in neural information processing systems 28 (2015).
[4] Hu, Hanzhang, et al. "Gradient boosting on stochastic data streams." Artificial Intelligence and Statistics. PMLR, 2017.
[5] Kersting, Kristian, and Kurt Driessens. "Non-parametric policy gradients: A unified treatment of propositional and relational domains." Proceedings of the 25th international conference on Machine learning. 2008.
[6] Grinsztajn, Léo, Edouard Oyallon, and Gaël Varoquaux. "Why do tree-based models still outperform deep learning on typical tabular data?." Advances in neural information processing systems 35 (2022): 507-520.
[7] Rahaman, Nasim, et al. "On the spectral bias of neural networks." International conference on machine learning. PMLR, 2019.

Thank you for your detailed review and constructive feedback. We address your main points below and will incorporate the suggested revisions in the final version.

Regarding line 71-72 and performance on structured tasks: We agree with this point. We will revise the contribution statement (lines 71-72) to: "In popular environments, our framework demonstrates competitive performance against NNs while showing particular strengths on structured tasks."

Regarding the critique on NNs (lines 350-353): We agree that any model class—including NNs and GBTs—can be made to fail or succeed depending on the setup. Our intent is to highlight a key difference in inductive biases. As discussed in Jeffares et al. (2024) [1], the kernel representations induced by GBTs are bounded and often behave more predictably on irregular or out-of-distribution inputs, while NN-tangent kernels can be unbounded and vary significantly on test points far from the training distribution. While techniques like LayerNorm can help stabilize neural network activations, they don't fundamentally change the difference in inductive biases and they often don't fully solve the extrapolation issues in OOD scenarios. We will revise the relevant paragraph in the paper to reflect this more clearly and avoid overgeneralization.

Why do certain algorithms perform differently than others? Apart from inherent algorithmic differences, the main difference for GBRL is the number of fitted trees per update.

• A2C - performs a single gradient step per rollout using the entire batch. In GBRL, this results in a single constructed tree per rollout. Since GBTs update the value and policy functions directly, such large, coarse updates can destabilize learning.
• PPO - in contrast, uses minibatches and multiple epochs per rollout. This allows GBRL to fit several small trees per rollout, yielding more stable and incremental updates.
• AWR - is an off-policy algorithm. Therefore, GBRL could potentially build many trees without adding sample complexity. However, we noticed that our best performing models had a huge computational cost to finish training. As a result, we resorted to reducing the number of gradient steps per update at the expense of performance. Future work could investigate methods for optimizing GBRL with a fixed tree budget (such as pruning and distillation), which may enable the applicability of more demanding RL algorithms, such as AWR, using GBRL.

In general, as each tree approximates a gradient step, GBRL benefits from frequent updates to refine its ensemble gradually. This makes it particularly well-suited to algorithms that support minibatching and multiple epochs per rollout. We will include a targeted PPO-based ablation study in the appendix to demonstrate the impact of minibatching performance. Results can be found in the following link: https://pasteboard.co/ENlUg1ffghZU.png.

Other improvements:
We greatly appreciate your detailed comments on presentation and formatting issues. We will implement all of your suggested improvements to enhance the clarity, readability, and technical accuracy of our paper.

Regarding specific questions:

1. Figure 5; which RL algorithm was used for GBRL and NN, PPO? What neural network architecture was used? We compared GBRL to NNs using PPO and a standard MLP with two hidden layers, each containing 64 units and tanh activations. This architecture is the default in Stable Baselines3, and a common choice in RL literature, for these environments. As such, we used the same NN architecture for the Equation environment. We used PPO for all experiments in section 5.2.

2. Figure 11; how come AWR-GBRL performs so poorly on pendulum-v1? AWR-GBRL performs poorly on Pendulum-v1, despite working well on many other environments. Since PPO-GBRL and AWR-NN succeed in this task, we believe the issue lies in the optimization process specific to AWR. Although we did try to tune hyperparameters for this setup, it's likely that the configuration remains suboptimal.

[1] Jeffares, A., Curth, A., and van der Schaar, M. "Deep Learning Through a Telescoping Lens: A Simple Model Provides Empirical Insights on Grokking, Gradient Boosting & Beyond." Advances in Neural Information Processing Systems, 37, 2024.

Thank you for your positive assessment of our paper, recognizing the comprehensive experiments and the value of our approach for structured data in RL. We address each of your concerns below and will revise the paper accordingly.

Regarding the "unbounded growth of the ensemble as the policy improves":
You raise a valid concern about the scalability of our approach. In our current implementation, ensemble size does increase with training steps. There are several possible approaches to address this limitation:

• Tree Pruning: One can reduce memory requirements through pruning redundant or low-importance splits after training.
• Ensemble Compression: One can distill knowledge from large ensembles into smaller, more efficient tree structures.
• Adaptive Growing Strategy: Rather than adding trees at fixed intervals, one can add them selectively based on performance plateaus or gradient magnitudes.

While we briefly mentioned these approaches in the paper, we will expand the limitations section to further explain these approaches as future research directions.

Regarding "additional ablations on hyperparameter sensitivity":
This is an excellent suggestion. We performed these experiments, provide them below, and will add them to the paper. Specifically, we propose to add an ablation study of GBRL-based PPO in the appendix examining:

• Learning rate ablation for policy and value function components: Here, we keep one fixed while changing the other. Similar to training with neural network estimators, we observe that large learning rates harm stability, whereas low learning rates result in very slow convergence. The results can be seen in the following links: https://pasteboard.co/PxZtndOMFuzZ.png, https://pasteboard.co/2W5UT93RBNrn.png.

• Tree depth limitations. This ablation shows that tree depth has a large impact on convergence, however deeper trees lead to increased runtime and compute cost. A larger tree depth corresponds to a better gradient approximation, which may explain the faster convergence shown in these results. In the paper, we chose a maximal tree depth of 4, a value that balances performance (the ability to solve environments) with maintaining a reasonable wallclock time-to-converge. The results can be found in the following link: https://imgur.com/iu0IUsT.

• Batch size. Using a rollout length of 2048 samples, we analyze the impact of PPO batch size on performance. We observe that batch size significantly impacts convergence. Specifically, smaller batches result in GBRL building more trees per rollout, improving adaptability. However, smaller batches also lead to noisier gradient estimates due to limited samples per constructed tree (blue, 16 samples per batch, starts much faster, but fails to converge to a stable solution). Conversely, larger batches stabilize training by reducing variance through averaging within leaves (more samples per utilized per constructed tree), but build fewer trees per rollout (gray, 2048 samples per batch, is very stable but also very slow to converge). Hence, both excessively small and large batch sizes negatively impact performance. Results can be found in the following link: https://pasteboard.co/ENlUg1ffghZU.png.

Regarding the lack of "in-depth theoretical analysis":
Please see our detailed response to Reviewer 6bS7 regarding the lack of theoretical proof of convergence and handling non-stationarity.

[1] Mei, Jincheng, et al. "On the global convergence rates of softmax policy gradient methods." International conference on machine learning. PMLR, 2020.
[2] Cortes, Corinna, Mehryar Mohri, and Dmitry Storcheus. "Regularized gradient boosting." Advances in neural information processing systems 32 (2019).
[3] Beygelzimer, Alina, et al. "Online gradient boosting." Advances in neural information processing systems 28 (2015).
[4] Hu, Hanzhang, et al. "Gradient boosting on stochastic data streams." Artificial Intelligence and Statistics. PMLR, 2017.
[5] Kersting, Kristian, and Kurt Driessens. "Non-parametric policy gradients: A unified treatment of propositional and relational domains." Proceedings of the 25th international conference on Machine learning. 2008.

Thank you for your thoughtful review. Below we address your points, which we will also clarify in the revised paper.

Stable Baselines3 and RL Zoo3: Our GBRL method was implemented within the Stable Baselines3 framework, a widely-used reinforcement learning library providing standard implementations for RL algorithms [1]. We compared GBRL against baseline neural networks (NNs) provided by RL Zoo3 [2], which include tuned hyperparameters for each environment, ensuring a fair and standardized evaluation.
NN architecture : For all experiments, we used a standard MLP with two hidden layers, each containing 64 units and tanh activations. This architecture is the default in Stable Baselines3 for the environments we tested and is widely used as a baseline in RL literature. We maintained this consistent architecture across all environments to ensure fair comparison.

• Advantage computation: We use Generalized Advantage Estimation (GAE) as proposed by Schulman et al. (2018) [3] to compute the advantage: $A_t = \delta_t + (\gamma\lambda)\delta_{t+1} + \ldots + (\gamma\lambda)^{T-t-1}\delta_{T-1}$, where $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$. The GAE parameters $\gamma$ and $\lambda$ for each environment are provided in Table 2 of the appendix.
• Critic: We use on-policy actor-critic algorithms, where the critic predicts the value function (not action-value Q). We use a standard L2 loss between the critic's prediction and the target return estimate: $L_\text{critic}(θ) = ||V_\theta(s_t) - G_t||^2$, where $G_t$ is either a Monte Carlo return estimate or a bootstrapped n-step return, depending on the specific algorithm (PPO, A2C, or AWR).

Both the GAE and target return calculations were done using built-in functions in Stable_baselines3.

Multi-objective training with GBT: In GBRL, we compute gradients for both the actor and critic objectives per timestep. We then concatenate these gradients: $g_t := [g_{t, \text{actor}}, g_{t, \text{critic}}]$ and use them to build a decision tree. At each candidate node split, we evaluate a score function to decide the best split. However, since the actor and critic gradients can differ in magnitude, this score can become biased toward one objective. To address this, we explored two strategies:

• Gradient normalization per output dimension with L2-based split scoring.
• Cosine similarity, which emphasizes gradient direction over magnitude.

Both approaches are supported in our codebase and produce good results, while the cosine similarity seems to perform slightly better. The results are visualized for the Cartpole environment in the following link: https://pasteboard.co/qXY0zekTq7uM.png. We will add this result as part of an ablation study to the appendix of the final version.

[1] Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., and Dormann, N. "Stable-Baselines3: Reliable Reinforcement Learning Implementations." Journal of Machine Learning Research 22 (2021): 1–8.

[2] Raffin, A. "RL Baselines3 Zoo." GitHub repository, 2020. https://github.com/DLR-RM/rl-baselines3-zoo

[3] Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. "High-Dimensional Continuous Control Using Generalized Advantage Estimation." arXiv preprint arXiv:1506.02438 (2015).