Offline Reinforcement Learning With Combinatorial Action Spaces

[1] Shengyi Huang and Santiago Ontañón. 2020. A closer look at invalid action masking in policy gradient algorithms. arXiv preprint arXiv:2006.14171 (2020).

[2] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, and others. 2018. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362, 6419 (2018), 1140–1144.

[3] Alex Beeson, David Ireland, and Giovanni Montana. 2024. An Investigation of Offline Reinforcement Learning in Factorisable Action Spaces. Transactions on Machine Learning Research.

[4] Shengpu Tang, Maggie Makar, Michael W. Sjoding, Finale Doshi-Velez, and Jenna Wiens. 2023. Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare (2023).

[5] Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA.

[6] Scott Fujimoto and Shixiang Shane Gu. 2021. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems 34, (2021), 20132–20145.

[7] Scott Fujimoto, David Meger, and Doina Precup. 2019. Off-policy deep reinforcement learning without exploration. In International conference on machine learning, PMLR, 2052–2062.

[8] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. 2020. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 (2020).

[9] Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. 2020. Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.09359 (2020).

W5 Experimental Setup: I suggest the authors conduct experiments in more meaningful real-world scenarios.

We appreciate the reviewer’s suggestion. The primary objective of our experimental setup is to demonstrate BVE's ability to learn effectively in environments with strong sub-action dependencies. We have addressed this in several ways. As outlined in W2, we show that BVE performs well when reward functions are non-factorizable and when sub-action dependencies vary. Furthermore, the inability of state-of-the-art baselines to learn performant policies in many of our testing environments highlights the challenges inherent in these settings, reinforcing the validity and rigor of our experimental design.

W4.1 Application to Offline RL: The paper only uses an optimization objective with a behavior cloning regularization term without further addressing OOD or distribution shift issues. This makes the offline RL setting seem unnecessary here

We appreciate the opportunity to clarify how BVE leverages established offline RL principles to mitigate overestimation bias.

The first mechanism is the behavior cloning term $\|\hat{\mathbf{a}}' - \mathbf{a}'\|$ in Equation 4, which encourages the agent to select actions similar to those of the behavior policy. This term can be viewed as a value-based analog to the behavior cloning regularizer introduced in TD3+BC (Equation 3). Despite its simplicity, such regularization has been shown to be effective across diverse problem settings [6].

Second, we sparsify the action tree to restrict Q-value evaluations to actions present in the dataset. Restricting evaluations to dataset actions was first proposed in [7] (BCQ) and is further detailed in [8]. While BCQ uses a generative model to achieve this, BVE accomplishes it by sparsifying the action tree.

In response to the reviewer’s suggestion, we have further elaborated on these mechanisms in Section 3.

W4.2 Application to Offline RL: The authors might consider examining the method's performance in an online setting

We agree that BVE is well-suited for online RL. However, our focus on offline RL is motivated by several key considerations. First, offline RL is crucial for real-world applications, many of which have combinatorial action spaces — examples include healthcare systems, traffic light optimization, and large-scale industrial processes. In these domains, online execution of a learning algorithm is infeasible and likely unsafe. Additionally, in many cases, there is a breadth of historical data that can be used for model training. Despite the significance and prevalence of these applications, this problem setting has received comparatively limited attention in the literature.

Second, as described in W4.1, BVE's sparsified tree structure mitigates overestimation error by constraining evaluation to actions observed in the training dataset. While BCQ [7] uses a similar principle, it relies on modeling the behavior policy through a conditional VAE — an approach that presents challenges for online fine-tuning [9]. BVE offers a more elegant solution: its sparse tree naturally restricts the action space in combinatorial settings without requiring explicit behavior policy modeling, thereby enabling seamless online fine-tuning after offline RL.

To validate BVE's online fine-tuning capability, we compared it with IQL, which is known for strong performance in online fine-tuning after offline RL. (FAS was excluded as, being a factorized variant of BCQ, it is unsuitable for online fine-tuning, as previously noted.) As discussed in W2, we conducted additional experiments to evaluate BVE's robustness across environments with varying sub-action dependencies, controlled by the number of pits. Relevant to our fine-tuning experiments is that, while BVE outperforms baselines in all environments, it faces its greatest challenge in the environment with 3,281 pits. This environment is particularly challenging because the agent must avoid actions in states near the starting state that become optimal only after the agent navigates past the pit. We therefore selected this most demanding case for fine-tuning, as success here implies generalizability to environments where BVE performs better.

After 1,500 gradient steps of offline training — at which point BVE achieves a reward of -226.1 compared to IQL's -259.4 — we fine-tuned both policies for 5,000 timesteps. Offline training was stopped after 1,500 gradient steps as, beyond this point, BVE's performance began to surpass that of IQL. Notably, BVE discovers a policy that not only exceeds the performance of its offline counterpart but also slightly outperforms IQL's online policy.

This experiment is now included in Section 4 of our paper.

W4.3 Application to Offline RL: I recommend the authors refer to the following paper... which could be relevant to this paper's problem setup

We thank the reviewer for highlighting this relevant work. It has been included in our discussion of related work in Section 5.

W2 Accounting for Sub-Action Dependence: I recommend the author to provide a more explicit explanation or analysis of how BVE captures sub-action dependencies

We note that the standard Q-learning loss inherently accounts for sub-action dependencies, as the Q-value is defined over the complete action. However, in combinatorial discrete spaces, estimating Q-values for entire actions is challenging due to the exponential growth in the number of possible actions with the number of sub-actions. To address this, factored approaches approximate Q-values by aggregating contributions from individual components, such as through linear decomposition. While effective under certain conditions, these approaches are limited when sub-action dependencies are strong or reward structures are not factorizable. These issues are well-documented in [3] (Sections 4.1 and 4.2) and [4] (Section 3.1) and apply to all factorized methods, regardless of the underlying algorithm. BVE, in contrast, estimates Q-values for entire actions, inherently capturing sub-action dependencies. By evaluating only a small subset of possible actions at each timestep, it mitigates the curse of dimensionality that standard Q-learning faces.

Our experiments in Section 4.1 demonstrate that BVE is robust to diverse reward structures, while those in Section 4.2 confirm that BVE explicitly accounts for sub-action dependencies. To further evaluate BVE's ability to account for sub-action dependencies, we conducted a new set of experiments in environments with varying levels of sub-action dependence. This was achieved by increasing the number of pits in the environment, as a higher pit density demands greater coordination between sub-actions. To ensure a viable path from the start state to the goal state, pits were restricted to interior (non-boundary) states, which total $3^N$ in the grid world. Specifically, we generated six new datasets in an 8D grid world with 328, 656, 1640, 3281, 4921, and 6561 pits, corresponding to 5%, 10%, 25%, 50%, 75%, and 100% of interior states being pits.

The 8D grid world was chosen as it strikes a balance between action-space complexity (65,536 possible actions per state) and the computational feasibility of creating multiple new datasets.

As shown in the table above, BVE's performance remains stable across all environments, whereas FAS's performance declines significantly when half the interior states are pits. Similarly, IQL's performance deteriorates as the number of pits — and thus the dependencies among sub-actions — increases. Notably, in the environment with 6,561 pits, all interior states are pits, requiring precise coordination of every sub-action to avoid catastrophic failure; a single sub-action misstep into an interior state results in the agent falling into a pit. This experiment has been added to Section 4.

W3 Tree Search: I understand that the design concept may be similar to using a binary search method to find the maximum value, thereby obtaining the maximum among exponentially many action combinations with logarithmic operations. I suggest the authors further develop the convergence theory of Q-learning under this search paradigm

The reviewer's intuition about the tree search paradigm and its utility in combinatorial action spaces is accurate. By structuring the action space as a tree, BVE requires predictions for only a small subset of Q-values at each timestep. Regarding convergence theory, BVE inherits the convergence guarantees of tabular Q-learning in the tabular case [5]. While we agree that a rigorous theoretical analysis of BVE's convergence properties under function approximation would be valuable, this falls outside the scope of the current work. We view this as an important avenue for future research, building upon the foundations established in this study.

We would like to thank the reviewer for their positive comments and constructive feedback. We appreciate your recognition of the importance of the problem setting and the persuasiveness of our results. In response to your concerns, we have conducted additional experiments and have addressed all points raised.

We believe our responses and additional experiments sufficiently address your concerns and provide clarity. We would greatly appreciate it if you could reassess your evaluation based on these updates. Should any concerns remain, we welcome further feedback on how we might refine our work to align with your expectations for a higher score. Thank you again for your thoughtful review.

W1.1 Tree Construction: In the tree shown in Figure 1, are the elements in the third and fourth layers fixed, or can their positions be swapped?

While the nodes in the tree are not inherently ordered, once an order is established, it becomes fixed. For instance, in a 2D grid world, the tree can be constructed such that the left-most node corresponds to the "up," "down," "left," or "right" direction. However, once the tree is constructed, the sub-action assigned to the left-most node remains constant — it cannot represent "up" in one iteration and "down" in another. This principle applies uniformly to every node across all layers of the tree. This has been clarified in Section 3.

W1.2 Tree Construction: The output of ( f(s,a) ) includes ( v ), but based on the example in Figure 3, the dimensions of ( v ) corresponding to different layers of the tree are different. So what is the dimensionality of the output of ( f(s,a) )? Is it fixed or variable?

We appreciate the opportunity to clarify the dimensionality of our network's output. As the reviewer notes, the number of children for each node varies. The network is designed to output one more than the maximum possible number of children in the tree, with the additional output used to represent the Q-value of the current node. For example, in Figure 1, the network produces five outputs, as the nodes [0,0,0], [1,0,0], and [2,0,0] have four children. The number of network outputs remains fixed. For nodes with fewer than the maximum number of children, masking is applied to eliminate invalid outputs. This approach aligns with established techniques in both policy gradient algorithms [1] and value-based methods, such as AlphaZero [2].

We have added more detail about the output dimensionality in Section 3.

Thank you for your feedback and for helping us improve our work! We would like to kindly remind you that we have resolved your concerns. As the discussion period concludes, please do not hesitate to let us know if there’s anything else we can address before it closes.

W4.1 Ablation Study and Its Implications: Figure 1 only displays two deltas

Per the reviewer's suggestion, we extended our original ablation study — previously limited to $\delta = 1$ and no depth penalty — to evaluate $\delta$ values of 5, 10, and 15:

The results indicate that while a depth penalty generally improves performance, it should remain small, with $\delta = 1$ yielding the best results across nearly all environments. This experiment has been added to Section 4 of our paper.

W4.2 Ablation Study and Its Implications: Figure (b) showing a difference only when alpha=0

We appreciate the opportunity to clarify the impact of $\alpha$ on policy performance, as we agree that Figure 7(b) could be improved to better address outlier values (e.g., $\alpha = 0$ for the environment with approximately 65k actions). In general, we observe that in low-dimensional settings, $\alpha$ has minimal influence on performance. However, in higher-dimensional environments, larger $\alpha$ values tend to yield superior results. To illustrate this, we can compare the results for the environment with 256 actions:

To those for the environment with over 4 million actions:

We have adjusted the y-axis scale in Figure 8(b) to exclude outliers, providing a clearer illustration of this difference.

W4.3 Figure (c) suggests that DQN performs poorly even in small action spaces, raising questions about its suitability as a competitor

This experiment was designed to highlight the necessity of BVE's tree structure. Notably, we did not train a standard DQN; instead, it was trained using the loss in Equation 4 and restricted to select only actions within the dataset — two mechanisms BVE relies on to enhance offline learning, as detailed in W1. Effectively, this DQN variant represents BVE without the tree search and loss propagation described in Section 3. Crucially, this DQN variant was not intended to serve as a direct competitor to BVE, which is why it was included as an ablation study rather than as a baseline in our primary experiments.

[1] Scott Fujimoto and Shixiang Shane Gu. 2021. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems 34, (2021), 20132–20145.

[2] Scott Fujimoto, David Meger, and Doina Precup. 2019. Off-policy deep reinforcement learning without exploration. In International conference on machine learning, PMLR, 2052–2062.

[3] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. 2020. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 (2020).

[4] Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. 2020. Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.09359 (2020).

[5] Alex Beeson, David Ireland, and Giovanni Montana. 2024. An Investigation of Offline Reinforcement Learning in Factorisable Action Spaces. Transactions on Machine Learning Research.

[6] Shengpu Tang, Maggie Makar, Michael W. Sjoding, Finale Doshi-Velez, and Jenna Wiens. 2023. Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare (2023).

[7] Yangchen Pan, Amir-massoud Farahmand, Martha White, Saleh Nabi, Piyush Grover, and Daniel Nikovski. 2018. Reinforcement learning with function-valued action spaces for partial differential equation control. In International Conference on Machine Learning, PMLR, 3986–3995.

[8] Xutong Zhao, Yangchen Pan, Chenjun Xiao, Sarath Chandar, and Janarthanan Rajendran. 2023. Conditionally optimistic exploration for cooperative deep multi-agent reinforcement learning. In Uncertainty in Artificial Intelligence, PMLR, 2529–2540.

W7.1 Empirical Results and Parameter Selection: The empirical results in Figures 8 and 9 do not show statistically significant differences, raising concerns about the effectiveness.

Figures 8 and 9 present the full learning curves corresponding to the results summarized in Figures 5 and 6, respectively. In low-dimensional environments without pits, FAS performs comparably to BVE. However, in higher-dimensional environments without pits, the discrepancy between the linearly decomposed and true reward functions becomes more pronounced, resulting in instability in FAS's learning and a decline in performance, while BVE consistently outperforms IQL. In environments with pits, BVE demonstrates clear superiority over both FAS and IQL across all settings.

We conducted a new set of experiments to further validate these results. Specifically, we designed environments with varying levels of dependence among sub-actions by increasing the number of pits — greater coordination between sub-actions is required as the number of pits increases. To ensure a viable path from the start to the goal state, pits were restricted to interior (non-boundary) states, which total $3^N$ in the grid world. We generated six new datasets in the 8D grid world, with 328, 656, 1640, 3281, 4921, and 6561 pits, corresponding to 5%, 10%, 25%, 50%, 75%, and 100% of interior states, respectively, being pits.

We selected the 8D world as it balances action-space complexity (65,536 possible actions per state) with the computational feasibility of generating multiple datasets.

As shown in the table above, BVE's performance remains relatively stable across all environments, whereas FAS's performance declines significantly when half of the interior states are pits. Similarly, IQL's performance deteriorates as the number of pits — and thus the dependencies among sub-actions — increases. This experiments has been added to Section 4.

W7.2 Empirical Results and Parameter Selection: The selection process for IQL and FAS hyperparameters is also not clearly described.

To ensure a fair comparison, we optimized hyperparameters for all methods. Specifically, we evaluated the number of network layers, the number of hidden nodes per layer, learning rate, learning rate decay, and batch size. Additionally, we optimized algorithm-specific hyperparameters for each method.

W8 Omission of Related Work: The paper fails to cite several highly relevant works

We appreciate the reviewer suggesting these related works and agree that they are relevant. We have now cited them in Section 5. However, we believe these works are not direct competitors to BVE. For instance, [7] appears to focus on high-dimensional continuous control, leaving the applicability and implications of adapting this method for combinatorial, discrete control unaddressed.

Additionally, these methods are primarily designed for online learning, which is a non-trivial distinction. For example, [8] introduces an interesting approach, but COE relies on visitation counts of state-action pairs during training, which are derived from online exploration. In offline learning, where the dataset is fixed, generating accurate visitation counts is challenging. This limitation is similar to that of MCTS, as discussed in Section 5. Furthermore, COE's exploration strategy involves optimism-based bonuses to incentivize exploration of unvisited areas, a mechanism that is less applicable in offline learning, which focuses on leveraging the available dataset effectively.

W2 Application to Online RL: Given that the tree structure concept for managing large action spaces could also be beneficial in online RL settings — which are generally less challenging than offline settings —it’s surprising that the authors chose not to begin with online RL

We agree that BVE is well-suited for online RL. However, we focused on offline RL for several reasons. Offline RL is critical for real-world applications, many of which involve combinatorial action spaces—examples include healthcare applications, traffic light control, and large industrial processes. In these domains, online execution of a learning algorithm is infeasible and likely unsafe. Additionally, in many cases, there is a breadth of historical data that can be used for model training. Despite the importance and ubiquity of these applications, this problem setting has received relatively limited attention.

Second, as described in W1, BVE's sparsified tree structure mitigates overestimation error by constraining evaluation to actions observed in the dataset. While BCQ [2] uses a similar principle, it relies on modeling the behavior policy through a conditional VAE — an approach that presents challenges for online fine-tuning [4]. BVE offers a more elegant solution: its sparse tree naturally restricts the action space in combinatorial settings without requiring explicit behavior policy modeling, thereby enabling seamless online fine-tuning after offline RL.

To validate BVE's online fine-tuning capability, we compare it with IQL, noted for its similar strength in online fine-tuning after offline RL (FAS is excluded from this experiment since, as a factorized version of BCQ, it is not suited to online fine-tuning). As outlined in W4.1 of our response to reviewer ahEi, we conducted additional experiments to evaluate BVE's robustness across environments with varying sub-action dependencies, controlled by the number of pits. Relevant to our fine-tuning experiments is that, while BVE outperforms baselines in all environments, it faces its greatest challenge in the environment with 3,281 pits. This environment is particularly challenging because the agent must avoid actions in states near the starting state that become optimal only after the agent navigates past the pit. We therefore selected this most demanding case for fine-tuning, as success here implies generalizability to environments where BVE performs better.

After 1,500 gradient steps of offline training — at which point BVE achieves a reward of -226.1 compared to IQL's -259.4 — we fine-tuned the policies for 5,000 timesteps. We stopped offline training after 1,500 gradient steps because, after this point, BVE's performance began to surpass IQL's. Importantly, BVE finds a policy that not only surpasses the one learned offline but also slightly outperforms IQL's online policy.

This experiment has been included in Section 4 of our paper.

W3 Broader Applicability and Contributions: The potential for applying the tree-structure approach in other offline RL methods raises questions about the broader significance of the work. If applicable, the contribution could be more substantial.

We appreciate the reviewer highlighting the significance of BVE's tree structure. Indeed, we agree that the advantages of this approach extend beyond our specific implementation. While the loss function in Equation 4 is both simple and effective, the tree structure itself is not inherently tied to this particular function. Moreover, as the reviewer noted in W2, the utility of the tree structure is not confined to the specific setting explored in our work. We believe this approach holds promise in various combinatorial contexts, with constrained RL being a particularly compelling example.

We feel this work provides a foundation for future research on combinatorial action spaces. To avoid overly broad claims, however, we focused specifically on offline RL, employing the loss function defined in Equation 4.

Thank you for recognizing the novelty and practical significance of our approach to addressing an important yet under-explored problem. We have carefully considered your feedback, conducted additional experiments, and performed further analyses based on your suggestions.

We believe our responses and the new experiments adequately address your concerns, and we kindly request your reconsideration of our score. If any issues remain, we would greatly appreciate further guidance on how we might improve our work to meet the standards for a higher evaluation. Thank you again for your time and feedback.

W1 Clarity on Action Space Reduction: It is not evident from the paper which design choice specifically helps to prevent overestimation in an offline setting

We appreciate the opportunity to clarify how BVE draws from well-established offline RL principles to reduce overestimation bias.

The first mechanism is the behavior cloning term $\|\hat{\mathbf{a}}' - \mathbf{a}'\|$ in Equation 4, which encourages the agent to select actions similar to those chosen by the behavior policy. This term can be viewed as a value-based analog to the behavior cloning regularizer introduced in TD3+BC (Equation 3). Despite its simplicity, such regularization has been shown to be effective across diverse problem settings [1].

Second, we sparsify the action tree to restrict Q-value evaluations to actions present in the dataset. Restricting evaluations to dataset actions was first proposed in [2] (BCQ) and is further detailed in [3]. While BCQ uses a generative model to achieve this, BVE accomplishes it by sparsifying the action tree.

As per the reviewer’s suggestion, we have elaborated on these mechanisms in Section 3.

We truly appreciate your feedback and the opportunity to improve our work based on your input! As a reminder, we have addressed the concerns you raised. Please let us know if there’s anything else you’d like us to address before the discussion period closes.

W4.2 Empirical analysis: The ablation studies could provide deeper insights by more systematically exploring beam width's impact on performance

As described in W3.1, we have added this ablation study in response to the reviewer's recommendation.

W4.3 Empirical analysis: A more detailed analysis of how performance scales with increasing numbers of sub-actions would help understand the method's limitations

We agree that exploring how many sub-actions BVE can scale to would be valuable. However, our original experiments already demonstrate its efficacy in an environment with over 4 million possible actions and more than 48 million states. Notably, in addition to outperforming the baselines across all environments, BVE exhibits only a moderate performance drop as complexity increases.

W5.1 Scope of claims: The paper states BVE "outperforms state-of-the-art methods" but this is only demonstrated against two baselines

We acknowledge that including additional baselines would further strengthen the demonstration of BVE's efficacy. However, to the best of our knowledge, factorization is the only approach specifically designed for offline learning in discrete, combinatorial action spaces. While it is possible to include additional factorized baselines, as discussed in W1, the limitations of value function decomposition are well-documented, and empirical evidence in [1] indicates that factorized BCQ (FAS in our experiments) performs comparably to other factorized offline methods.

W5.2 Scope of claims: While empirical results suggest reduced overestimation bias, the mechanism and conditions for this reduction could be better explained with theoretical analysis

We appreciate the opportunity to clarify how BVE leverages well-established offline RL principles to address overestimation bias.

The first mechanism is the behavior cloning term $\|\hat{\mathbf{a}}' - \mathbf{a}'\|$ in Equation 4, which encourages the agent to select actions similar to those chosen by the behavior policy. This term can be viewed as a value-based analog to the behavior cloning regularizer introduced in TD3+BC (Equation 3). Despite its simplicity, such regularization has been shown to be effective across diverse problem settings [3].

The second mechanism is the sparsification of the action tree, restricting Q-value evaluations to actions present in the dataset. This approach mitigates overestimation bias by avoiding erroneous Q-values caused by extrapolation error, as described in [4] (BCQ) and [5]. In BCQ, this restriction is achieved through a generative model, whereas BVE accomplishes the same effect by sparsifying the action tree.

Q1.1 Theory: Could you outline what theoretical guarantees might be possible for the tree traversal algorithm's convergence properties?

In the tabular case, BVE converges with the same guarantees as tabular Q-learning [6]. While we agree that a rigorous theoretical analysis of BVE's convergence properties under function approximation would be valuable, we consider it beyond the scope of the current work. This is an important direction for future research, as it could build upon the foundation established here.

Q1.2 Theory: How would you characterize the relationship between beam search approximation and policy optimality in your method?

As described in W3.1, beam search does not influence the learned Q-values; it is used exclusively during policy extraction. As demonstrated in W3.1, we conducted additional experiments to evaluate the impact of beam search on the quality of the extracted policy. Furthermore, as noted in W2, since beam search is decoupled from the learning process, the beam width can be optimized independently after learning, provided the environment permits optimization in a manner analogous to fine-tuning.

Q1.3 Theory: Could you elaborate on the specific conditions under which BVE would be expected to perform optimally?

A key condition for BVE's effectiveness is an environment with a combinatorial, discrete action space, as such spaces align naturally with the tree structure central to BVE's operation. However, we believe BVE's true strength lies in environments where sub-actions are strongly dependent or reward functions are not factorizable. By explicitly accounting for sub-action dependencies, BVE can learn highly performant policies in these challenging settings, where current state-of-the-art methods are less effective [1, 2].

Q2.1 Comparative evaluation and claims: Have you considered comparing against factorized adaptations of BCQ, CQL, and IQL?

As detailed in W1, our FAS baseline is a factorized adaptation of BCQ. Given the reported similarity in performance among factorized variants of offline RL methods in [1], as well as the known limitations of factorized methods described in [1] (Sections 4.1 and 4.2) and [2] (Section 3.1), we believe our experiments sufficiently demonstrate the strengths of BVE relative to factorized methods.

W3.2 Technical details: A clearer explanation of terminal state handling would aid reproducibility

In our implementation, terminal states yield a reward of 10, after which the episode terminates, and the agent begins the next iteration in the starting state. Notably, action selection in terminal states is inconsequential to the loss function in Equation 4, as the true Q-value for all terminal states is 0. Therefore, if $s'$ is a terminal state, the update target is simply 10. We have clarified this point in Section 3.

W3.3 Technical details: The trade-offs between computational cost and performance deserve more thorough quantification

As detailed in W3.1, we have included a new experiment to quantify the computational overhead associated with beam search. Regarding learning efficiency, Figures 8 and 9 in the original paper show that, except in environments with small action spaces (256 or fewer), BVE requires fewer gradient steps than both IQL and FAS to learn a performant policy.

W4.1 Empirical analysis: The method's robustness to different data distributions could be more thoroughly investigated

We have conducted two new sets of experiments to evaluate BVE's robustness to different data distributions. First, we created environments with varying levels of dependence among sub-actions by increasing the number of pits in the environment — more pits require greater coordination between sub-actions. To ensure a viable path from the start state to the goal state, pits were restricted to interior (non-boundary) states, which total $3^N$ in the grid world. Specifically, we generated six new datasets with 328, 656, 1640, 3281, 4921, and 6561 pits in the 8D grid world, corresponding to 5%, 10%, 25%, 50%, 75%, and 100% of interior states being pits.

We selected the 8D world as it offers a balance between action-space complexity (65,536 possible actions per state) and the computational feasibility of generating multiple new datasets.

As shown in the table above, BVE's performance remains relatively stable across all environments, whereas FAS's performance drops sharply when half the interior states are pits. Similarly, IQL's performance deteriorates as the number of pits — and consequently, the dependencies among sub-actions — increases.

Second, as described in Section 4 of our paper, we use an augmented form of A$^*$ to generate our datasets. In our original experiments, the A$^*$ agent selects the optimal action with a probability of 0.1, choosing randomly otherwise. To extend this analysis, we created three new datasets for the 8D world with 3,281 pits. These datasets were generated by an A$^*$ agent selecting the optimal action with probabilities of 0.2, 0.3, and 0.4, respectively. We selected the 8D world with 3,281 pits for these experiments because, as shown in the table above, it is the environment that poses the greatest challenge for BVE, making success in this setting more likely to generalize to environments where BVE performs better.

As can be seen in the above table, BVE consistently outperforms both IQL and FAS across all environments. However, as the proportion of optimal actions in the dataset increases, IQL's performance approaches that of BVE. This is expected given the short time horizon of the problem setting, where the expected number of optimal demonstrations per state is 1,000 when the suboptimal rate is 0.4.

These experiments have been included in Section 4 of our paper.

W3.1 Technical details: The paper could better explain the interaction between depth penalty and beam search during action selection

We appreciate the opportunity to clarify the relationship between the depth penalty ($\delta$) and beam search. Both mechanisms are introduced to mitigate errors in action selection caused by inaccurate branch value estimates near the tree root. However, they operate in distinct phases and do not directly interact. Specifically, $\delta$ is applied during learning to penalize branch value errors closer to the tree root, prioritizing corrections at higher tree levels where decisions have a broader influence on action selection. Beam search, on the other hand, is used exclusively after training, during policy extraction, to facilitate broader exploration of action combinations.

To further investigate the effects of these mechanisms, we conducted two new experiments. First, we extended our original ablation study — which previously assessed only $\delta = 1$ and no depth penalty — to include $\delta$ values of 5, 10, and 15:

From this experiment, we observe that while a depth penalty generally improves performance, it should be kept small, with $\delta = 1$ yielding the best results across nearly all environments. We have included this experiment in Section 4 of our paper.

Additionally, we measure the effect of varying beam widths on both return and computational overhead. Due to space constraints, we present results below for the environment with over 4 million action spaces, as it requires the largest tree. However, we have conducted the same experiments for all environments with at least 16,000 actions, and these results have been also be included in Section 4 of our paper.

Our results indicate that beam width does not need to be very large to achieve optimal performance — typically, a beam width of 10 is sufficient. More importantly, the choice of beam width has minimal practical impact on runtime for most real-world applications, as inference time remains well under one second, even with beam widths far exceeding what is necessary or optimal. These results were obtained using a system with a 10-core CPU, 32 GB of unified memory, and no GPU.

Thank you for your thoughtful comments and valuable feedback. We greatly appreciate your recognition of the novelty and practical significance of our approach in tackling an important yet under-explored problem setting. We have carefully addressed your concerns and conducted additional experiments and analyses based on your suggestions.

We believe our responses and the new experiments sufficiently address your concerns, and we kindly request that you consider revising your score. Should any concerns remain after reviewing our responses, we would be grateful for further guidance on how to improve our work to meet your expectations for a higher score. Thank you again for your time and insightful suggestions.

W1 Limited comparative evaluation: Particularly relevant is the recent parallel work on factorized action spaces which offers baselines and testing environments

Thank you for bringing this recent work (henceforth [1]) to our attention — we have cited it alongside our existing factored action space baseline [2]. To clarify, [2] introduces a factorized version of BCQ that aligns with the approach described in [1] (as acknowledged in [1] Section 3.2). While we agree that comparing BVE’s performance against other factorized offline RL algorithms is of interest, the results in [1] indicate that factorized BCQ performs comparably to the factorized versions of other offline RL methods.

More critically, the limitations of factorized approaches are well-documented and recognized in both [1] (Sections 4.1 and 4.2) and [2] (Section 3.1). Specifically, factorized action spaces are effective when dependencies among sub-actions are weak and/or reward structures are factorizable. These limitations are algorithm-agnostic, applying to all factorized approaches. In contrast, our objective is to develop an approach that is robust to diverse reward structures (as demonstrated by our experiments in Section 4.1) and explicitly accounts for sub-action dependencies (as demonstrated by our experiments in Section 4.2).

Regarding the environments in [1], the results indicate that sub-actions in these spaces exhibit limited inter-dependence. Specifically, while sub-actions in the DeepMind Control Suite environments require coordination, the optimal value of one sub-action does not strongly depend on the value of another. For example, consider a scenario where applying a torque of 0.5 to the cheetah's back thigh rotor is optimal. The agent must simultaneously learn that, in the state where such a torque is applied, a torque of 0.1 to the cheetah's back shin rotor is also optimal. However, these sub-actions remain independently optimal; their effectiveness does not depend on the presence or absence of the other. While coordination is necessary for achieving optimal performance, the sub-actions themselves are not mutually dependent. This contrasts with several real-world settings. In healthcare, for instance, two medications may be independently effective but, when combined, could produce antagonistic effects. While we acknowledge that BVE is applicable to such spaces, our primary focus is on addressing action spaces where current factorized methods are less effective.

W2 Theoretical analysis: The paper would benefit from theoretical analysis of convergence properties and formal bounds on beam search approximation error

We would like to clarify that beam search is not used during learning and, therefore, does not influence BVE’s convergence properties. Instead, beam search is applied only during policy extraction, after the value estimates have been learned. Because it is decoupled from the learning process, the beam width can be optimized independently after learning, provided the environment allows for optimization in a manner analogous to fine-tuning. This has been clarified in Section 3.

[1] Alex Beeson, David Ireland, and Giovanni Montana. 2024. An Investigation of Offline Reinforcement Learning in Factorisable Action Spaces. Transactions on Machine Learning Research.

[2] Shengpu Tang, Maggie Makar, Michael W. Sjoding, Finale Doshi-Velez, and Jenna Wiens. 2023. Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare (2023).

[3] Scott Fujimoto and Shixiang Shane Gu. 2021. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems 34, (2021), 20132–20145.

[4] Scott Fujimoto, David Meger, and Doina Precup. 2019. Off-policy deep reinforcement learning without exploration. In International conference on machine learning, PMLR, 2052–2062.

[5] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. 2020. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 (2020).

[6] Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA.

Q2.2 Comparative evaluation and claims: Could you evaluate BVE on the DeepMind Control Suite environments with discretised actions

As discussed in W1, while we agree that BVE is applicable to such settings, our primary focus is on environments with non-factorizable reward structures and/or strong dependencies among sub-actions, which are common in real-world scenarios. The results reported in [1] suggest that sub-actions in the DeepMind Control Suite environments exhibit limited interdependence. Specifically, while sub-actions in these environments require coordination, the value of one sub-action does not strongly depend on the value of another.

For instance, consider applying a torque of 0.5 to the cheetah's back thigh rotor. In parallel, the agent must learn that, in the state where such a torque is applied, a torque of 0.1 is optimal for the back shin rotor. However, these sub-actions are independently optimal; their effectiveness is not conditional on the presence or absence of the other. This contrasts with several real-world settings. For example, in healthcare, two medications might be independently effective but could produce antagonistic effects when combined.

Q2.3 Comparative evaluation and claims: What evidence supports the claim about "effectively capturing sub-action dependencies" beyond the current experiments?

As described in W4.1, we conducted additional experiments to evaluate BVE's robustness to varying strengths of sub-action dependencies. Notably, in the 8D environment with 6,561 pits, all interior states are pits. In this setting, failure to perfectly account for sub-action dependencies leads to the agent falling into a pit, resulting in catastrophic failure.

Q3.1 Technical implementation and scaling: Could you explain how the depth penalty and beam search interact during action selection?

As described in W3.1, these mechanisms are designed to reduce errors in action selection caused by inaccurate branch value estimations near the tree root. However, they do not directly interact, as they are applied in different phases. Specifically, the depth penalty is used during learning to penalize branch value errors closer to the tree root, prioritizing corrections at higher levels of the tree where decisions have a broader impact on the selected action. Beam search, on the other hand, is used exclusively after training, during policy extraction, to enable broader exploration of action combinations. We have clarified this point in Section 3.

Q3.2 Technical implementation and scaling: What is the computational overhead of tree construction and traversal compared to baselines?

In our experiments, tree construction occurs dynamically. Specifically, when performing branch value estimation, as detailed in Algorithm 1, a node's children are computed at runtime. Depending on the size of the tree and the nature of the environment, these values could be cached or the entire tree precomputed. However, we note that generating children at runtime is computationally inexpensive.

As discussed in W3.1, we conducted an additional experiment to measure the impact of different beam widths on returns and computation time. During learning, tree traversal corresponds to a beam width of 1, which, as shown in the results in W3.1, is a computationally efficient procedure.

Q3.3 Technical implementation and scaling: How are terminal states handled in the tree structure?

As detailed in W3.2, if $s'$ is a terminal state, the update target is equal to the reward, since the true Q-value of a terminal state is always 0.

Q4.1 Empirical analysis: How does the method's performance scale with increasing numbers of sub-actions?

As detailed in W4.3, BVE scales to environments with over 4 million sub-actions and 48 million states. Notably, in addition to outperforming the baselines across all environments, BVE experiences only a moderate performance drop from the simplest to the most complex environment.

Q4.2 Empirical analysis: Could you characterize the method's robustness to different data distributions?

As detailed in our response to W4.1, we present results from two new sets of experiments demonstrating BVE's robustness to data distributions with varying strengths of sub-action dependencies and levels of dataset expertise.

Q4.3 Empirical analysis: Could you provide more detailed analysis of how beam width affects the trade-off between performance and computational cost?

As detailed in W3.1, we have empirically investigated this trade-off through a new set of experiments. Our findings show that beam widths do not need to be very large to achieve optimal performance — typically, a width of 10 is sufficient. Furthermore, the choice of beam width has minimal impact on runtime in most real-world applications, as inference time remains well under a second, even with beam widths far exceeding what is necessary or optimal, including when using a processor without a GPU.

We sincerely appreciate your feedback and your support of our work! We would like to remind you that we have addressed your concerns. As the discussion period nears its conclusion, please let us know if there are any remaining points we can address within the timeframe.