BraVE: Offline Reinforcement Learning for Discrete Combinatorial Action Spaces
Authors: Matthew Landers
Taylor W. Killian
Hugo Barnes
Thomas Hartvigsen
Afsaneh Doryab
Venue: NeurIPS 2025 poster ()
Keywords: Offline Reinforcement Learning
Batch Reinforcement Learning
Combinatorial Action Spaces
Reinforcement Learning
Discrete Action Spaces
Large Action Spaces
Sequential Decision Making
Primary area: reinforcement_learning

Abstract: Offline reinforcement learning in high-dimensional, discrete action spaces is challenging due to the exponential scaling of the joint action space with the number of sub-actions and the complexity of modeling sub-action dependencies. Existing methods either exhaustively evaluate the action space, making them computationally infeasible, or factorize Q-values, failing to represent joint sub-action effects. We propose \textbf{Bra}nch \textbf{V}alue \textbf{E}stimation (BraVE), a value-based method that uses tree-structured action traversal to evaluate a linear number of joint actions while preserving dependency structure. BraVE outperforms prior offline RL methods by up to $20\times$ in environments with over four million actions.

BraVE: Offline Reinforcement Learning for
Discrete Combinatorial Action Spaces
Matthew Landers'; Taylor W. Killian?, Hugo Barnes', Thomas Hartvigsen', Afsaneh Doryab University of Virginia, ²MBZUAI
Abstract
Offline reinforcement learning in high-dimensional, discrete action spaces is chal- lenging due to the exponential scaling of the joint action space with the number of sub-actions and the complexity of modeling sub-action dependencies. Existing methods either exhaustively evaluate the action space, making them computation- ally infeasible, factorize Q-values, failing represent joint sub-action effects. We propose Branch Value Estimation (BraVE), a value-based method that uses tree-structured action traversal to evaluate linear number joint actions while preserving dependency structure. VE outperforms prior offline RL methods by up x in environments with over four million actions,
Introduction
Offline reinforcement learning (RL) enables agents learn decision-making policies from fixed datasets, avoiding the risks and costs inherent in online exploration [21] [22]. Existing methods have shown strong performance in low-dimensional discrete settings and continuous control tasks
19 20). However, many real-world decisions require selecting actions from high- dimensional, discrete spaces. In healthcare, for example, practitioners must choose among thousands of possible combinations of procedures, medications, and tests at each decision point [33
[2 13 15
Such settings give rise to combinatorial action spaces, where the number of actions grows exponen- tially with dimensionality, scaling as I[ ma for N sub-action dimensions. In offline reinforcement learning, this structure induces two primary challenges: evaluating and optimizing over a large, discrete action space is computationally demanding: and making accurate decisions requires model- ing sub-action dependencies from fixed datasets. Standard value-based methods can, in principle, capture sub-action dependencies but require evaluating or maximizing the Q-function over the full action space, which is intractable in nigh-dimensiooal settings. Conversely, recent approaches B 27 factorize the Q-function under conditional independence assumption, reducing computational cost but limiting expressivity by precluding the modeling of sub-action interactions, which are critical in many real-wort sal-world domains.
We introduce Branch Value Estimation (BraVE), a value-based offline RL method for combinatorial action spaces that avoids the scalabilit--expresivity tradeoff of prior approaches. BraVE imposes a tree structure over the action space and uses a neural network to guide traversal, evaluating only linear number of candidate actions while preserving sub-action dependencies. To support this structured selection process, the Q-function is trained with behavior-regularized temporal difference (TD) loss and branch value propagation mechanism.
Our experiments show that BraVE consistently outperforms state-of-the-an baselines across a suite of challenging offline RL tasks with combinatorial action spaces containing up 4 million discrete
"mlanders virginia.edi edu
"Code is available at httppppr//gtauu..oo////ettteeeea
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

actions. In high-dinn -ineensieaii environments with strong sub-action dependencies, BraVE improves average return by up to 20x over state-of-the-art offline RL methods. While baseline performance degrades with increasing sub-action dependencies or action space size, BraVE maintains stable performance.
Our contributions are as follows:
1. We propose behavior-regularize TD loss that captures sub-action dependencies by evalu- ating complete actions rather than marginal components in combinatorial spaces.
2. We introduce BraVE, an offline RL method for discrete combinatorial action spaces that cap- tures sub-action interactions and scales to nigh-dimensional settings via Q-guided traversal over a tree-structured action space.
3. We empirically show that BraVE outperforms state-of taite-of-the-eee art baselines in environments with combinatorial action spaces, maintaining high returns and stable learning as both action space size and sub-action dependencies increase.
2 Preliminaries
Reinforcement learning problems can be formalized as a Markov Decision Process (MDP), MM- (S, A. p, 7. where S is set of states, AA is set of actions, p S A S - [0, 1] is function that gives the probability of transitioning to state s' when action a is taken in state s, r: S x A + R is a reward function, 7 E [0, 1] is discount factor, and μ S - [0, 1] is the distribution of initial states. A policy π S + P(A) is a distribution over actions conditioned on a state (a s) Ia(a+
8 = s).
While the standard MDP formulation abstracts away the structure of actions A. we explicitly assume that the action space is combinatorial; that is, A is defined as Cartesian product of sub-action spaces. More formally, = A₁ x A2 x ... x AN, where each AA is discrete set. Consequently, a, is an N N-dimensional vector wherein each component is referred to as sub-action.
The agent's goal is to learn policy x² that maximizes cumulative discounted returns:
H
n² arg max Bx
Ex'(ss,
where Su μ4, a2 TT(- s:), and 81+1 p(- |t, az).
In offline RL, the agent learns from static dataset of transitions B = {(st, az, Tt, $(41) 1i=0
generated by, possibly, mixture of policies collectively referred to as the behavior policy nT.
Like many recent offline RL methods, our work uses approximate dynamic programming to minimize temporal difference error (TD error) starting from the following loss function:
Es (++
27
(
max max ((s',a',0") Q(s, a;;
(I)
where the expectation is taken over transitions (s, s') sampled from the replay buffer B, Q(s, a; 0) a parameterized Q-function that estimates the expected return when taking action a in state s and following the policy thereafter, and Q(s, a; 0=) is a target network with parameters 0_, which is used to stabilize learning.
For -iitt---iittibttioon actions a', Q-values can be inaccurate, often causing overestimation errors due the maximization in Equation (I) To mitigate this effect, offline RL methods either assign lower values to these out-of -it-o---ittibuttion actions via regularization or directly constrain the learned policy. For example, TD3+BC [13] adds a behavior cloning term to the standard TD3 [14] loss:
π arg max B(a,a)=B [}Q (s, (s)) (=(s) - a
where À is scaling factor that controls the strength of the regularization.
More recently, implicit Q-learning (IQL. 19 used SARSA-style TD backup and expectile loss to perform multi-step dynamic programming without evaluating out-of-sample actions:
27
I(()=
E.
r
+
Q(s', Q(s
(3)
((R())
where 2(s) {a A TT(a s) > 0} are actions in the support of the data.

---

= 2
a= [0.0.0]
[1.0.]]
[2.0.0]
02
[0.1,0]
0g
0g
a= [0.1,1]
0= [0.1.2]
Figure 1: BraVE's tree representation for 3-dimensional combinatorial action [01, M2, 0a), where each sub-action a, E {0, 1,2). Each node encodes complete action vector, with explicitly chosen sub-actions according to the traversal path from root, and remaining dimensions filled with default value (here, O). At depth k the value of sub-action ay is selected, with sibling nodes differing only in that dimension.
Branch Value Estimation (BraVE)
The Q-function, (ss, a) in Equation (T. encodes long-term value by mapping each state-action pair to its expected return. When actions comprise multiple sub-actions itly captures sub-action dependencies by accounting for interactions that influence both immediate rewards and future transitions, making it natural target for learning in structured combinatorial action spaces. However, combinatorial action spaces, the exponential growth of joint actions renders both forward passes and Q-value estimation computationally intractable [30 34].
"0l,,..,,,,, aNy. Q(s, a) implic-
Factorizing the Q-function across action dimensions tractability. While this reduces computational cost, it sacrifices expressivity by ignoring sub-action dependencies, leading to estimation errors when sub-actions jointly influence transitions or rewards. In such settings, including real-world domains like treatment recommendation, summing marginal Q-values can produce divergent estimates (Appendix A
27
common strategy for improving
We introduce Branch Value Estimation (BraVE), an offline RL method that avoids this scalabil- expresssssvv tradeoff. BraVE assigns values complete action vectors (s,, preserving their interdependencies, but avoids exhaustively scoring every action by imposing a tree structure over the space and using neural network to guide traversal that selectively evaluates small subset of actions. This results in only linear number of evaluations per decision, enabling BraVE VE to scale to high-dimensional combinatorial settings without sacrificing value function fidelity.
3.1 Tree Construction
BraVE imposes a tree structure over the combinatorial action space, assigning a complete N- dimensional action vector to each node. This vector is constructed by combining the sub-action values explicitly selected along the path from the root with predefined default values (e.g., a, = 0 in the binary case) for all unassigned dimensions.
The tree originates from root node corresponding the start of traversal, where no sub-actions have been selected. From this root, branches extend to child nodes by explicitly assigning a value aş E As to the k-th sub-action dimension dg. A node at depth therefore represents a complete action vector in which the first l sub-actions (ai...., ..k) have been explicitly set, and the remaining sub-actions (ak+1..... .......... aN) retain their default values. Sibling nodes at depth & differ from their parent only in the newly assigned component, and differ from each other only in their choice of ag. That is, they differ only in the k-th component of the complete action vector they represent, as illustrated in Figure This dimension-by -idmeeniion construction ensures that reaching leaf node, where all N sub-action values have been explicitly assigned, requires traversing at most levels.
While this specific N -edephh, cimension--odered tree is adopted for its computational efficiency, the general BraVE framework places no constraints on the tree structure. Any tree in which each node represents a complete joint action, and in which root-to-leaf paths systematically cover the action space, valid instantiation. For example, a flat tree with a single level and [A children for each possible joint action recovers the naive alternative of exhaustively evaluating

---

Q(s, a) over the entire space. Our implementation, however, deliberately uses the deeper, N N-level structure to guarantee number of node evaluations linear in N, which is crucial for tractability in high-dimensional spaces.
This structural flexibility extends beyond tree depth and layout. The ordering of sub-actions, the choice of default values, and the tree topology are all implementation details rather than core components of the method. Regardless of the selected configuration, however, the chosen structure should remain fixed throughout training to ensure consistent semantics for traversal and value estimation. The tree itself may be constructed dynamically each timestep or precomputed and cached.
BraVE imposes no restrictions on the cardinality of individual sub-actions; each ad may be drawn from an arbitrary discrete set Ag. For clarity, however, all examples and figures that follow assumee multi-binary action space, where each sub-action is either included (a; = 1) or excluded (a; = 0).
3.2 Tree Sparsification
To mitigate overestimation error and stabilize learning, BraVE introduces an inductive bias by sparsifying the action space tree, restricting it to include only actions observed in the dataset B. This idea is conceptually related to BCQ [T3], which constrains policy evaluation to actions deemed plausible by a learned generative model. BraVE, by constrast, enforces this constraint structurally by pruning branches from the tree that correspond to implausible or unsupported sub- action combinations.
This design is particularly effective in real-world settings where certain sub-actions are incompatible and rarely, if ever, appear together. For example, in treatment planning or medication recommendation, specific drug combinations may be avoided due to known adverse interactions. By limiting the tree to feasible actions observed in the data, BraVE avoids evaluating unrealistic behaviors, reduces computational overhead, and curbs value inflation driven by unsupported extrapolation.
3.3 Q-Guided Tree Traversal
á' [0,0,0]
To compute the greedy action à' arg max,' Q(s', a required by Equa- tion (1). BraVE traverses the action space tree using a neural network (-) to guide decisions at each node. At node Andde the network receives as input the current state s, which may be discrete or continuous, and the N N-dimensional action vector corresponding to agode- It outputs a scalar node Q-value q = Q(s, amode: 8 and a vector of branch values v E R Mami. While reflects the value of selecting the current node's 's complete action, the branch values v estimate the maximum Q-value obtainable in the subtree rooted at the j-th child. The network produces both and in single forward pass, with the branch values v representing a learned estimate of each subtree's potential.
=
D'
[11,4. 11
a' 1=
[1,0,0] q'
(11,9.1
0'2
[1,100]
Figure 2: BraVE traversal a 3-D binary action space (full tree shown bottom-right), Starting from the root [0, O, 0), the agent selects ái = 1 since its branch value (11) exceeds both those of alternative children (4, -1) and the root's Q-value (8). Traversal proceeds until reaching [1, 1, where the Q-value (16) exceeds the child's branch value (1); terminal condition. Masked values (-) are ignored.
Importantly, the network f is a standard MLP requiring no specialized architecture. The tree is not encoded into the network input; instead, it is an external structure that organizes the arg max computation.
Though the number of children can vary across nodes, the network output dimensionality remains fixed. Specifically, ff returns one scalar for the current node and .max maxa |Aal branch values. For example, if the maximum sub-action cardinality across all dimensions is three, the network produces four outputs total. Following standard practice in structured prediction and reinforcement learning [8 26 masking is applied ignore unused entries v for nodes with fewer than M Mmax children.
children

---

[0,0,..0]
12)
Y max 9,3,5,2) 9,3,54
[22,555
[1,0.0]]
12) max 8,933 3
27 [12,93
[1.10,0]]
(B 12)
8
max/8.6.7 6,71
[12,7
0;
[1,1,1,0]
(6 (6- == 2(r +74) - d1=6
Figure 3: Example of loss propagation in 4-D binary action space (full tree shown bottom-ripe right). Starting from the node [1, 1, 1.0] (bottom left), target (Equation[5) is propagated its parent [1, 1, 0, 0j. new target is computed as the maximum of the propagated value, the parent's 's own Q-value, and the hranch values of alternative child nodes. This process recurses up the tree to compute all node losses.
Traversal begins at the root node. each step, the network evaluates (q, v) at the current node. If 2 max, ej, traversal terminates and the corresponding action apode is returned as â'. Otherwise, the algorithm proceeds the child indexed by arg max; v/. This greedy descent continues until either the termination condition is satisfied or a leaf node is reached, Notably, traversal may terminate at internal nodes rather than always proceeding to fully specified leaf. A full example of this process is shown in Figure 2
This traversal mechanism enables BraVE's computational efficiency: it evaluates a single node per sub-action dimension, resulting in ((N) complexity - factor of II. [Aal/N fewer evaluations than exhaustive scoring. The tree serves as the structural scaffold that makes this targeted, linear-time traversal possible.
3.4 Loss Computation
BraVE trained using a behavior-regularizze temporal difference (TD) loss that penalizes value estimates for actions unlikely under the dataset. Given transition (s, s' a²) sampled from the replay buffer B, the TD target computed using the action à' = arg max ( a'; a'; selected via the tree traversal procedure described in Section 3.3 The loss is defined as:
LTD (0) Ess.a.n.' a')=- (A 7
- l a'll Q( a: 0)
(4)
where À is regularization coefficient and |â' - a'|l penalizes deviation from the behavior action, following principles introduced in TD3+BC (Equation 2
We combine this behavior-regularizee TD loss with a branch value supervision loss LBaVEs resulting in total objective L = aLTD - LBaVE, where controls the relative weighting of the TD term. To compute LBRAVE. begin from node sampled from B and reuse the TD target
Y A (r QQss ('','''''''''")) O'; l| a'll
(5)
as the supervisory signal. This target then propagated recursively up the tree. At each step, target is used to update the parent node's estimate for the corresponding branch value. The propagated target is updated at each level to reflect the maximum of Y and the existing sibling branch values, ensuring consistency with the max-based traversal logic. This process continues up to the root, training the branch values v at each node through direct supervision from LBAVE to estimate the highest Q-value accessible through its subtree. The full LBaVE computation procedure is provided in Algorithm I and illustrated in Figure 3
The recursive mechanism underlying LEEVE stabilizes learning by propagating training signals not only to the node corresponding to the sampled action but also to every ancestor on its path. Consequently, internal nodes including those not directly sampled - receive gradient updates. Because all branches share single global Q-network, these updates generalize across similar states and actions, enabling BraVE to form reliable estimates even in rarely-sampled regions of the tree.
5

---

3.5 Enhancements for Stability and Policy Quality
We mitigate the sensitivity of BraVE's hierar- chical structure to inaccurate branch value esti- mates using two complementary mechanisms: depth penalty applied during training and beam search used during inference. During training, we apply depth-based weighting fac- tor ó in the BraVE loss computation. Because the branch value target is propagated upward from a sampled action node to the root, this weighting amplifies the influence of errors closer to the root, where mistakes propagate to more of beam search
Algorithm 1 Compute BraVE Loss
Require:
f(0): neural network with parameters 0
f(0") ): target network with parameters 0
{s, a, r, s', a'a): transition from B
a': action selected via tree traversal given s
1: (g. v) t- f(s. 0)
2: (g v - f (s' a 0-)
3: Y (r +777
| a'l
4: total loss + (g- - Y)²
the tree. At inference time, to improve action selection robustness. Instead
5: node <- a
6: d=1
of committing to single greedy path, the al- gorithm retains the top-W actions (ranked by predicted values) at each tree level. The final action is selected from the union of all beams, allowing for broader exploration of high-value combinations and improving policy quality.
7: while node is not nall do
8:
parent +- GETPARENT(node)
9:
q. V - fs 0)
10:
children + GETCCILDREN
11:
+ index of node in children
12: loss <- ((v[i] - Y)+ 5d)
total loss f- total loss loss
14:
vii] < Y
4 Experimental Evaluation
Y < max(q,
16:
node +- parent
We evaluate BraVE in the Combinatorial Navigation Environment (CoNE), high- dimensional discrete control domain designed to stress-test policy learning under large action spaces and sub-action dependencies. In CONE, actions are formed by selecting subsets of atomic motion primitives (sub-actions), corresponding to directional moves along orthogonal axes. The agent chooses which primitives to activate at each timestep, resulting in a combinatorial action space of size |A] 2215 where D is the number of spatial dimensions.
17:
d f- d+1
18:
end while
19:
return total loss/d
The agent starts from fixed origin so and must reach designated goal g. At each timestep, it receives a negative reward r -p(s.9) g) proportional to its Euclidean distance from the goal. Episodes terminate upon reaching the goal (with reward +10) or falling into a pit, failure state that incurs a penalty of r = -10 p(9o.g) g). This penalty structure ensures that failure is strictly worse than any successful trajectory, even those that are long or indirect.
CoNE exhibits both combinatorial complexity and tightly coupled action dynamics. Some sub-action combinations synergistic, such as activating orthogonal directions to move diagonally, opposing movements cancel out, and others lead to failure by directing the agent into hazardous regions of the state space. These structured dependencies mean that the effectiveness of a sub-action often depends critically on the presence or absence of others.
This stands in contrast to discretized variants of popular continuous control environments 228 where sub-actions require coordination but can be learned independently [3]. In CONE, by contrast, sub-actions that are individually beneficial can be harmful in combination, effect common in real-world settings such as drug prescription, where treatments may interact antagonistically (see Appendix A).
Dataset Construction We generate offline datasets using a stochastic variant of A". At each step, the optimal action is selected with probability 0.1, and random valid action chosen otherwise. This procedure yields diverse mixture of trajectories with varying returns, including both near-optimal and suboptimal behavior. The resulting datasets reflect realistic offline settings in which learning must proceed from heterogeneous, partially optimal demonstrations.
Baselines We compare Bra to two representative baselines: (1) Factored Action Spaces (FAS) 27 the state-of-the-art for offline RL in combinatorial action spaces; and (2) Implicit Q-Learning

---

[A|
BraVE
FAS
IQL
16
1.5 0.0
1.5 0.0
- 1.5
64
-0.4 + 0.0
-0.4 +.0
-6.1
256
-2.0 =011
0.6
4.5
1024
-3,4 =011
203
- 5.8
4096
-6.9 1.6
-71
- 1.7
16k
-6.1 0.4
-25.6
33.3
- +.0
65k
-8.2 2.2
-24.4 10.4
27.00 11.5
260k
-13.8 +54
-42.2
32.3
-88.4 17.7
1M
-9.6
1.2
-114
18.2
-3.77
31.0
4M
18.66 8.3
-33.9 + 27.0
-66.9 31.6
Table 1:
In environments with non-factorizable reward structures and no sub-action dependencies BraVE and FAS perform similarly in low-dimensional settings, but action dimensionality increases, BraVE maintains high returns and stable policies, while FAS's performance deteriorates. IQL performs worst in all settings.
(IQL) [19] strong general-purpose algorithm included assess the need for methods purpose-built for combinatorial structures. Following prior work [27]. we implement FAS using a factored variant of BCQ [15] All methods are trained for 20,000 gradient steps and evaluated every 100 steps.
4.1 Performance Across Reward Structures and Sub-Action Dependencies
FAS has shown strong performance in offline RL for combinatorial domains B 27), however, its effectiveness depends on the assumption that rewards decompose cleanly across sub-actions and that dependencies among sub-actions are weak. These assumptions are often violated in real-world settings, where the effect of one sub-action may depend critically on the value of another. To evaluate BraVE in precisely these challenging conditions, construct suite of CoNE environments that systematically vary along both axes of complexity.
We measure performance across 10 randomly generated environments in each of two settings: the first includes non-fate contorctore reward structures without sub-action dependencies, and the second includes both non-factorinn con-facttri rewards and dependent sub-actions. For each task, we vary dimensionality from 2-D (IA) 16) to 11-D (I-A) million), where each additional dimension introduces two new sub-actions. Each environment has size 5 in every dimension. The agent starts in the top-left corner and must reach goal the bottom-right. Results are averaged over five random seeds.
Non-Factorizable Reward Structures Only We begin with environments that contain no pits. In these settings, the transition dynamics are factorizable across sub-actions. However, the reward function cannot be linearly decomposed. As shown Table [ FAS performs comparably BraVE in oww-dimensional tasks but degrades dimensionality increases. Because the reward depends on the state induced by the full action vector, the FAS approach of assigning rewards to individual sub-actions introduces modeling bias that grows with action dimensionality, causing its learned Q-values diverge from the true values. BraVE avoids this instability by evaluating complete joint actions directly, maintaining high performance across all action-space space sizes. IQL, performs significantly worse than BraVE across all action space sizes, suggesting that methods not explicitly designed for combinatorial actions struggle even when transitions are factorizable. Complete learning curves are provided in Appendix B.
Non-Factorizable Rewards and Sub-Action Dependencies We next evaluate performance under increasing sub-action dependency induced by hazardous transitions. In an 8-D environment (I.4) 65, 536), we vary the number of pits from 5% 100% of the 6,561 interior (non- coundoondrr) states, ensuring that there is always feasible path to the goal along the boundary of the state space (where pits are never placed). As shown in Table 2 BraVE maintains stable performance across all pit densities. FAS, by contrast, degrades sharply once pits occupy half of the interior, and IQL declines steadily as dependency strength increases. These results highlight BraVE* ability handle tightly coupled decision-making even when adverse interactions between sub-actions common. These
7

---

Pit %
Bra VE
FAS
IQL
-8.2
+ 2.2
24.4 10.4
11.5
-19.0
2.3
-78.4 99.7
85.8 45.0
10
-16.9
- 3.3
- 177.1
25
-42.9
+ 43.3
-178.6
212.8
+
50
-54.8
+ 47.9
-902.6
274.1
-106.4 + 42.8
75
-42.9
+ 34.3
-942.8 + 278.1
-110.0 34.3
100
-1..6
+ 22.4
-1131.4 + 0.0
-112.4 22.8
Table 2: BraVE maintains stable performance environments with non-factorizable rewards and sub-action dependencies, whereas FAS exhibits sharp decline when pits occupy at least half of the interior states, IQL performance also degrades as sub-action dependencies increase.
results are further contextualized by the normalized episode-length score reported in Appendix B.2 where complete learning curves are also provided.
Sparse but Critical Sub-Action Dependencies Having established that BraVE performs well under strong sub-action coupling, we examine settings with only five pits, representing a negligible fraction of the state space in high dimensions. We continue scaling the state space until Bra and FAS converge to similar average returns, allowing us to assess how each method handles sparse but critical dependencies. As shown in Table Bra VE performs reliably even when the state space is small and each action carries substantial risk. FAS, by contrast, requires a much larger state space before the influence of the pits becomes diluted and its performance approaches that of BraVE. This demonstrates that even small number of pits sufficient to invalidate naive factorizations. Complete learning curves are provided in Appendix B.3
S
BraVE
FAS
IQL
25
-7.5
+ 2.4
531.55 31.4
-12.1 + 5.8
125
-2.9
0.2
-579.8 7.2
-14.1 13.6
625
-5.6
1.5
-480.3
152.9
-22.4 20.6
3125
-6.3
0.7
-147.4
292.6
-28.0 + 22.8
15625
-12.4
+ 7.9
-18.9 4.6
-37.8 + 17.4
Table 3: When sub-action dependencies are sparse but critical, BraVE performs reliably even in small state spaces with high-risk actions. FAS approaches BraVE's performance only once the joint action space exceeds 15 thousand. IQL performs worse than BraVE in all settings.
4.2 Robustness to Action Order
BraVE's tree structure is defined by a fixed sequence of sub-action dimensions. To assess sensitivity to action ordering, trained BraVE, FAS, and IQL using five random permutations of this sequence in the 8-D, 50% pit CoNE setting, which is empirically the most challenging 8-D variant (see Table2]. Results averaged over these permutations reported in Table
These findings are consistent with those Table 2 showing that BraVE outperforms FAS by an order of magnitude and is roughly twice effective IQL. This demonstrates that Bra BraVE's performance is robust to the ordering sub-action dimensions and does not rely on a favorable structural arrangement.
4.3 Online Fine-Tuning
BraVE's data-driven tree sparsification (Section 3.2 inherently constrains action selection to observed behaviors, principle shared by offline methods that model the behavior policy using generative approaches [15]. However, BraVE imposes this constraint structurally, eliminating the reliance on an explicit behavior model that can complicate online fine-tuning [23 Consequently, BraV can

---

BraVE
FAS
IQL
-53.5
29.1
11103.6 51.4
96.2 + 51.8
Table 4: Performance on the 8-D, 50% pit CoNE task, averaged over five random permutations of the sub-action dimensions. BraVE's effectiveness not dependent specific tree construction.
be directly fine-tuned online without modification. Appendix C shows that BraVE matches IQL's performance during fine-tuning when both methods begin from comparable offline initialization.
4.4 Ablations and Hyperparameters
We conduct ablation and hyperparameter studies to quantify the contribution of each of Bra Ve's design choices. First, we examine the depth penalty 6, which scales the loss by a node's ' position in the tree. A small penalty (& 1) consistently yields the best results, confirming the importance of prioritizing accuracy near the root. Second, we vary the loss weight to analyze the trade-off between the regularrree TD loss and the BraVE loss. Performance remains stable across range of a values, but omitting the TD term entirely (a- = 0) leads to significant degradation, particularly in higher-dimensional tasks. Third, we isolate the contribution of BraVE's tree structure by training standard DQN baseline, which omits the hierarchical traversal and branch value propagation, This variant fails to learn viable policy, confirming that Vr's structured decomposition is critical to its success. Fourth, we evaluate the effect of beam width on performance and inference time. A width of 10 is sufficient for strong performance, with larger widths offering negligible gains at minimal runtime cost, reflecting the approach's practical efficiency. Full results are presented Appendix D
Related Work
5.1 Tree-based RL
Tree-based methods in RL have historically been applied to ordered decision processes. Most notably, Monte Carlo Tree Search (MCTS) (6, as used in AlphaZero [26). recursively selects actions using the PUCT algorithm (2] However, sequential structure makes ill-suited for unordered action spaces like those considered here, where sub-actions must be selected simultaneously.
TreeQN [10 blends model-free RL with online planning by constructing a tree over learned state representations, refining value estimates via tree backups. Differentiable decision trees (DDTs) (25) enable gradient-based learning in RL by replacing the hard splits typical of decision trees with smooth transitions, which can later be discretized for interpretability. In the offline setting, Ernst et al. [9] apply tree-based regression (c.g., CART, Kd-trees) to approximate f-fuctiions via fitted Q-iteration.
5.2 Combinatorial Action Spaces
Many RL. approaches have been developed for combinatorial action spaces, particularly in domain- specific contexts such text-based games [16] 17 34 routing 7 24 TSP (4, and resource allocation [ These methods often depend on domain structure, whereas BraVE is domain-agnostic.
General-purpose approaches include distributed action representations 29 curriculum-based ac- tion space growth [1]. and search-based amortized Q-learning (32) which replaces exact action maximization with optimization over sampled proposals. Wol-DDPG [ embeds discrete actions into continuous spaces, though this approach has been found to be ineffeetive in unordered settings [5] Notably, these are online approaches, and their application to offline settings is often non-trivial. For example, Zhao et al. [35] rely on state-action visitation counts, which are generally infeasible to obtain offline.
Closer to our setting, Tang al. [77 and Beeson al. S evaluate Factored Action Spaces (FAS in our experiments), which linearly decompose the Q-function by conditioning each term on a single sub-action. While this reduces dimensional complexity, relies on sub-action independence; condition that often fails in real-world domains. Crucially, these limitations are algorithm-agnose and apply to factorized variants of all offline RI. methods. BraVE, by contrast, structures the action space to retain sub-action dependencies without incurring exponential cost.

---

Discussion and Conclusion
In many real-world decision-makin making problems, combinatorial action spaces arise from the simultane- ous selection of multiple sub-actions. Offline RL in these settings remains challenging due to the cost of optimization and the difficultyy of modeling sub-action dependencies from fixed datasets. Standard methods do not scale, while factorized approaches improve tractability at the expense of expressivity. We present Branch Value Estimation (BraVE), an offline RL method for discrete combinatorial action spaces. By structuring the action space as a tree, BraVE captures sub-action dependencies while reducing the number of actions evaluated per timestep, enabling scalability to large spaces. BraVE outperforms state-of-the- art baselines across environments with varying action space sizes and sub-action dependencies.
While BraVE demonstrates strong performance, several limitations and opportunities for future work remain. First, the tree structure is defined by a fixed ordering of the sub-action dimensions. While Section 42 demonstrates robustness to this choice in CoNE, future work could explore methods for learning or adaptively selecting the dimension sequence. Second, while BraVE's inference complexity is linear in the number of dimensions (N), the size of the network's s output layer and the tree's branching factor grow with the sub-action cardinality ([Aa)), which may impact performance on tasks with extremely high-cardinality discrete actions. Third, the recursive update for LBaVE requires backpropagation through all parent nodes of a sampled action, incurring a greater computational cost during training than standard Q-learning update. Fourth, empirical validation is confined to the synthetic CoNE benchmark; future work should assess BraVE's generalizability across a broader range of combinatorial tasks and real-world applications. Finally, adapting the BraVE framework to online learning is an important direction for future work, requiring the development of new mechanisms manage the pngloration--xploitaaiinn trade-off within the structured action space.
Despite these limitations, BraVE provides flexible and extensible foundation for future research on combinatorial action spaces. We believe its applicability extends well beyond the specific setting explored in this paper. particular, constrained RI. presents a promising direction, as BraVE's tree structure naturally supports the exclusion of inadmissible action combinations through pruning.
References
[1] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. In International conference on machine learning, pages 104-114 114. PMLR, 2020.
[2] David Auger, Adrien Couetoux, and Olivier Teytaud. Continuous upper confidence trees with polynomial intooration-oosistenn In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part I 13, pages 194-209. Springer, 2013.
[3] Alex Beeson, David Ireland, and Giovanni Montana. An investigation of offline reinforcement learning in factorisable action spaces. arXiv preprint arXiv:2411. 2024.
[4] Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv:161 1.09940, 2016.
[5] Changyu Chen, Ramesha Karunasena, Thanh Nguyen, Arunesh Sinha, and Pradeep Varakan- tham. Generative modelling of stochastic actions with arbitrary constraints in reinforcement learning, Advances in Neural Information Processing Systems, 36, 2024.
[6] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72-83. Springer, 2006.
[7] Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combinatorial actions: An application vehicle routing. Advances in Neural Information Processing Systems, 33:609-6200 6260, 2020.
[8] Gabriel Dulac-Aroold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap. Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv:1512.07677 2015.
10

---

[9] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
[10] Gregory Farquhar, Tim Rocktäschel, Maximilian Igl, and Shimon Whiteson. Treeqn and atreec: Differentiable tree-structured models for deep reinforcement learning, arXiv preprint arXiv:1710.114411 1417, 2017.
[11] Gregory Farquhar, Laura Gustafson, Zeming Lin, Shimon Whiteson, Nicolas Usunier, and Gabriel Synnaeve. Growing action spaces. In International Conference on Machine Learning, pages 3040-3051, PMLR, 2020.
[12] Yuwei Fu, Wu Di, and Benoit Boulet. Batch reinforcement learning in the real world: A survey. In Offline RI. Workshop, NeurolPS, 2020.
[13] Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34:20132-20 2012222,,,,5--- 2021.
[14] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. International conference on machine learning, pages 1587-1596. PMLR, 2018.
[15] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International conference on machine learning, pages 2052-2062. PMLR, 2019.
[16] Ji He. Jianshu Chen, Xiaodong He, Jianfeng Gao, Lihong Li, Li Deng, and Mari Ostendorf. Deep reinforcement learning with natural language action space, arXiv preprint arXiv: 1511.0663, 2015.
[17] Ji He, Mari Ostendorf, Xiaodong He, Jianshu Chen, Jianfeng Gao, Lihong Li, and Li Deng. Deep reinforcement learning with combinatorial action space for predicting popular reddit threads. arXiv preprint arXiv: /60.003677 2016.
[18) Shengyi Huang and Santiago Ontañón. A closer look at invalid action masking in policy gradient algorithms. arXiv preprint arXiv:2006. /4/71, 2020.
[19] Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learming. arXiv preprint arXiv:2110.06169, 2021.
[20] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine Conservative q-learning for offline reinforcement learning. Advances in neural information processing systems, 33: 1179-1191, 2020.
[21] Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning: State-of-the-art, pages 45-73. Springer, 2012.
[22] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint urXiv:2005.06643 2020.
[23] Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006. 20t.:99000.09359, 2020.
[24] Mohammadreza Nazari, Afshin Oroojlovy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[25] Andrew Silva, Matthew Gombolay, Taylor Killian, Ivan Jimenez, and Sung-Hyun Son. Op- timization methods for interpretable differentiable decision trees applied to reinforcement learning. In International conference artificial intelligence and statistics, pages 1855-1865. PMLR, 2020.
[26] David Silver, Thomas Hubert, Julian Schritwieser,, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 14206419) 2018.

---

[27] Shengpu Tang, Maggie Makar, Michael Sjoding, Finale Doshi- Doshi-Velez, and Jenna Wiens. Lever- aging factored action spaces for efficient offline reinforcement learning in healthcare. Advances in Neural Information Processing Systems, 45:34272-342866 2022.
[28] Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint
2018.
[29] Arash Tavakoli, Fabio Pardo, and Petar Kormushev. Action branching architectures for deep inforcement learning. In Proceedings of the aaai conference on artificial intelligence, volume 32, 2018.
[30] Sebastian Thrun and Anton Schwartz. Issues in using function approximation for reinforcement learning. In Proceedings of the 1993 connectionist models summer school, 1993.
[31] Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez- Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymnasium: standard interface for reinforcement learning environments, 2024. URL https://arxiv. org/ abs/2407 17032
[32] Tom Van de Wiele, David Warde-Farley, Andriy Mnih, and Volodymyr Mnih. Q-Jeaming in enor- mous action spaces via amortized approximate maximization. arXiv preprint arXiv:2001.08/ 16, 2020.
[33] Jinsung Yoon. James Jordon, and Mihaela Schaar. Asac: Active sensing using actor-critic models, In Machine Learning for Healthcare Conference, pages 45 451-473, PMLR, 2019.
[34] Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J Mankowitz, and Shie Mannor. Learn what not to learn: Action elimination with deep reinforcement learning. Advances neural information processing systems, 31, 2018.
[35] Xutong Zhao, Yangchen Pan, Chenjun Xiao, Sarath Chandar, and Janarthanan Rajendran. Conditionally optimistic exploration for cooperative deep multi-agent reinforcement learning. PMLR, 2023.
In Uncertainty in Artificial Intelligence, pages
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction (Section D present BraVE as a novel offline reinforcement learning method for combinatorial action spaces, designed to model sub- action dependencies while maintaining tractability. 'hee claims of improved performance over prior methods are supported by the algorithmic details in Section and the empirical results in Section 4
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 can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section ( (Diccussion and Conclusion) outlines several limitations of BraVE and corresponding directions for future work. These include the reliance on a fixed sub- action ordering for tree construction, scalability challenges with high sub-action cardinality or deep trees during LBraV E computation, dependence on offline dataset quality, and the opportunity for broader empirical evaluation.
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 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 well-specification, 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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: The paper does not present new theoretical results or proofs; its contributions are primarily empirical.
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 to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: BraVE is described in detail in Section 3 with pseudocode provided in Algorithm T Section 4 outlines the experimental setup, environments, baselines, and
training procedures. Additional environment details are included in Appendix B To support reproducibility, have released our code at: hhttss://aat haapsymu/nnoymmou.. 4open. science/r/ SraVE-28C1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, 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 to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
14

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path 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: An anonymized link our implementation is provided in footnote on page 1. This supplemental material includes instructions for running the code and reproducing results. It also contains implementation of CoNE, including the dataset generation process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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 gww.///u//////eeeeeeeo www.eeeSuumsssioooolllooo
/
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section (Experimental Evaluation) describes the enviromment setup, dataset construction, baselines, and experimental configurations. Training specifics, including the number of gradient steps and evaluation frequency, are also included in Section 4 Details regarding Bra Bra'E's hyperparameters (c.g., a, d) and ablation studies are provided in Section 4 and Appendix D An anonymized implementation has been published to support reprodueibility.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
15

---

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: All experimental results reported in Tables and include means and standard deviations computed over five random seeds, as stated in Section [ Learning curves in Appendices B and incllude shaded regions indicating one standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results 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 be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one 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 range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix B specifies that experiments were run on a single NVIDIA A40 GPU. Appendix D reports wall-clock training times for key experiments conducted 10-core CPU with 32 GB of unified memory and no GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
16

---

Justification: This work involves algorithmic development for reinforcement learning in simulated environments and does not involve human subjects, sensitive data, or applications with direct ethical implications beyond general considerations relevant to Al research. We have reviewed the NeurIPS Code of Ethics and believe our work is in full compliance.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper presents foundational algorithmic contributions for offline rein- forcement learning for combinatorial action spaces. While some potential application areas (e.g.. healthcare, logistics) carry societal implications, this work does not explore specific deployment scenarios their broader societal impact, which would be highly dependent on the application context.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an 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 to 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms 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 models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
This paper introduces new algorithm (BraVE) and simulated environment (CoNE). Neither the algorithm nor the environment/data generation process presents a high risk of misuse.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. 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: [NA]
Justification: This paper does not rely external assets such third-party code, datasets, or pre-trained models beyond standard librarics (c.g.. PyTorch) that do not require special licensing. The CoNE environment and datasets generated by the authors.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pawerssi.ppwwiiie........ thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The primary asset introduced in this work is the BraVE algorithm and its implementation, described in Section 3amoonnnnadd and released with instructions via an anonymized link. The CoNE environment is also asset, described in Section 4 and included in the published code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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: subjects.
The research involves neither crowdsourcing nor experiments with human
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The research does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 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 this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs not used as important, original, or non-standard component of the core methods in this research.
Guidelines:
The answer NA
that the core method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy http:p/:/herrrpss.cc///eeeeeeeee for what should or should be described.
19

---

A Limitations of Standard Value-Based Estimation and Q-Function Factorization in Combinatorial Action Spaces with Sub-Action Dependencies
10.00
6.56
7.29
8.10
9.00
10.00
10.00
10.00
6.56
7.29
100.00
-10.00
9.00
10.000
6.56
6.56
-10.00
8.10
8.10
-10.00 -10.00
5.90
-10.00
-10.00
7.29
7.29
(a) 2-D grid
(b) Q-values
Figure 4: 2-D grid with five pits and the true maximum Q-values in each state.
Consider a two-dimensional grid with five pits, which provides a simplified instance of CONE, allowing us to clearly illustrate the limitations of standard methods. At each state, the agent chooses from 16 possible actions (IAl = 16), corresponding to combinations movement directions (e.g., [U], [UD], [UDL], [ULR]. [UDLR], [D], [DR], ..... Transitions yield reward of 0 unless they lead to the goal (r = 10) or a pit (r = -0),, as shown in Figure 44]
Sub-action dependencies are inherently captured by the standard Q-function, as they affect both immediate rewards and future returns:
(=(8,a)= + a() EE xt(a [
(8))x(('
S'ES
a'EAA
Thus, the agent can learn the true maximum Q-value in each state (Figure recover the optimal policy.
4b) and, consequently,
Accurately estimating the Q-function is challenging in combinatorial action spaces, where the number of possible actions grows exponentially with the action dimension. This complexity limits the applicability of value-based RL methods, such as IQL, which require estimating values for all actions.
More specifically, IQL's policy loss is defined as:
L (Φ) ((,,)) [exp (Q(ss,;;;)) ((s; log na(a s)]
In discrete action settings, the policy aa(a s) is typically parameterized distribution. That is, a policy network maps the state a vector of logits (s(s) BlA,, where |A] is the number of discrete actions. The softmax function then transforms these logits into probability distribution:
flat categorical
(s)(
aT(a 8)
El4 exp(Cx(s)))
This formulation requires a forward pass through the policy network to produce logits for all possible actions, incurring computational cost and modeling complexity that scale with (A].
BraVE evaluates only a subset of possible actions at each timestep, allowing it to exploit the Q- function's 's capacity capture sub-action dependencies without predicting an exponential number of action values or logits simultancously. Factored approaches (FAS) [3 [7], by contrast, simplify computation by linearly decomposing the Q-function, conditioning each component on single sub-action and the full state. While this reduces the dimensional complexity of the action space, it imposes structural constraints on the reward and Q-function definitions:
D
1>
r(s.a)
Σ ra(s, aa) and Q(s, a) Σ d=1
qa(s, ad)
(6)
d=1
20

---

that may limit expressiveness in settings with sub-action dependencies and cause the Q-function to diverge.
More specifically, when sub-actions are combined (e.g., "up" + "left",, FAS retrieves partial Q-values qi (s, up) and (2 left) from different next states, rather than from single consistent next state determined by the combined action. This results in artificially inflated values, as the summations in Equation (6) incorrectly assume independence. Iterative Bellman updates, used in Q-learning. amplify this inconsistency, ultimately causing Q-value divergence.
The independence assumption holds in discretized variants of popular continuous control environ- ments, where sub-actions typically influence distinct parts of the state space [28] B1. However, this assumption is violated in many real-world settings, limitation explicitly acknowledged in the FAS
literature 3 27
21

---

B CoNE Learning Curves
We compare BraVE's performance to two state-of-the-arr baselines: Factored Action Spaces (FAS) 27 3]. which learns linearly decomposable Q-functions for offline combinatorial action spaces, and Implicit Q-Learning (IQL) [99, a general-purpose offline RL, method. All methods are evaluated across 20 instances of CoNE. In CoNE, the sizes of both the action and state spaces increase exponentially with the environment's dimensionality: a D-dimensional setting with M positions per axis yields AA = 2nD joint actions and [| MD distinct states. All experiments were conducted on a single NVIDIA A40 GPU using Python 3.9 and PyTorch 2.6.
In all curves, results are averaged over seeds; shaded regions indicate one standard deviation.
B.1 Non-Factorizable Reward Structures Only
In environments without pits, transition dynamics factorizable across sub-actions, The reward function, however, remains non-lineas and cannot be decomposed. Below we present the training curves corresponding to the results in Table
BraVE
IQL
FAS
||] 16
|1| 64
||| 256
|A] = 1,024
-10
Epiceds Rowadd
Rewend
Spiiel:: Rowanl
-30
-00
-100
-90
128
31
77
216
80
144
216
Graden Stops
Gradinn Staps
Grad.mn Steps
Grudiest Steps
[
4,096
[ 16.384
[.4]
65,536
[4] 262.144
Egiedd Rewsed
-30
Epiead Rewand
-200
-100
-75-
-150-
-2:00
-25
-000
300-
114
-00
Gradient Steps
Gradlett Steps
Gindlent Steps
Crodient Steps
[4] 1,048,576
[4] 4.194,304
-100
Eqpiedd Resood
2000
-710
-000
400
-1ze
-000
116
Gradkent Stepe
Ordiient Stoge
Figure 5: Learning curves for BraVE, FAS, and IQL in environments with non-factorizable reward structures but no sub-action dependencies.
In low-dimensional settings, FAS performs similarly to BraVE, but its performance degrades as dimensionality increases due to the bias introduced by linear Q-function decomposition. BraVE, by contrast, remains stable across all action space sizes by evaluating joint actions directly. IQL performs relatively poorly in all configurations, indicating that general-purpont offline RL methods struggle even when transition dynamics are factorizable.
22

---

B.2 Non-Factorizable Reward Structures and Sub-Action Dependencies
To assess performance under increasing sub-action dependencies, we introduce hazardous transitions by varying the density of pits in an 8-D environment (I.A] 65, 536). The number of pits ranges from 5% to 100% of the 6,561 interior -on-boondary) states. Below we present the training curves and normalized episode-length scores corresponding to the results in Table 2
BraVE
IQL
FAS
0% Pit Coverape
5% Coverage
Pit Caverage
25% Pír Coverage
Epieads Rowid
106-
Eginode Rovvrr
158
Eprcsdi:
-030
200
4re.
-001
258
-1000
-100
36
16
15
26
56
114
13k
24
10k
20c
126
15A
20.
Gradicat Stope
Gradicat Steps
Grafienn Stops
Grudiirt Steps
50% Coverage
Coverage
100% Coverage
-200
-200
Rooud
Epiodde Rewaad
-400
-630
-0:3
Epionde
-400
-203
-2000
(190)
-1933
-1200
Grodient Stogs
Gradlett Stops
Gradiect Stops
Figure 6: Learning curves for BraVE, FAS, and IQL in environments with non- non-factorizable reward structures and sub-action dependencies.
Learning Curves BraVE maintains stable returns across all pit densities, whereas FAS degrades sharply when pits cover at least half the interior states. IQL performance degrades as dependency strength increases. These results demonstrate BraVE's effectiveness environments with tightly coupled sub-action effects and frequent adverse interactions.
Normalized Episode-Length Score To further contextualize performance, we compute normal- ized episode-lengto score that places each method on 0-100 scale, where 0 corresponds to random policy and 100 an oracle planner. defined as:
scoreneem = 100 length length
length random length oracle
where length is the average episode length of the evaluated policy, length is the episode length of random policy (which consistently times out at 100 steps), and length oracto is the optimal path length computed via A search.
The normalized scores in Table reinforce the findings from Table BraVE consistently achieves scores above 70, indicating ncar-optimal behavior even in the most hazardous settings. FAS, by contrast, collapses to 0 equivalent to random policy once dependencies become sufficiently strong.
23

---

Pit %
BraVE
FAS
IQL
99.3
89.6
88.0
92.8
57.3
52.9
10
94.1
20.2
51.3
25
78,5
0.0
54.7
50
71.4
0.0
40.6
75
78.5
0.0
38.4
100
79.3
37.0
Table 5: Normalized episode-lengle scores (0=random, 100=oracle) in the 8-D CoNE environment with varying pit densities. Scores show BraVE maintaining high performance while FAS's performance collapses to that of random policy.
B.3 Sparse but Critical Sub-Action Dependencies
To isolate the effect of sparse but critical sub-action dependencies, we consider environments with only five pits, representing negligible fraction of the state space in higher dimensions. Starting in the 2-D environment, we progressively scale the state space until BraVE and FAS converge to similar average returns, allowing evaluate how each method handles low-frequency but high-impact hazards. Below we present the training curves corresponding to the results in Table 3
BraVE
IQL
FAS
[S] 125
[|]] = 625
100
Eptoede Rewaad
-180
-200
1200
-100
-200
200
-000
-00
<00
400
4
1/6
62
18k
12
20c
&.
18k
15k
Grudient Stepe
Gradleet Stope
Gradiert Stope
[ = 3,125
[ 15.625
Egioak Rosord
-c0-
Ejioak:
-000
-120-
-008
200
10k
24
116
15k
26
Gradeet Steps
Gradlent Steps
Figure 7: Learning curves for BraVE, FAS, and IQL in environments with sparse but critical sub- action dependencies.
BraVE performs reliably across all settings with sparse but critical sub-action dependencies even when the environment is small and each action carries significant risk. FAS, by contrast, requires much larger state spaces before the influence of the pits diminishes and its performance approaches that of BraVE. These findings indicate that even small number of hazardous transitions can invalidate simplistic factorizations. IQL performs worse than BraVE VE in all settings.
24

---

C Online Fine-Tunie Tone-Tuning After Offline Learning
To evaluate BraVE's capacity for online fine-tuning, we compare it to IQL, method known for strong online adaptation following offline pretraining. FAS is excluded from this experiment because, as factorized version BCQ, not suited to online fine-tuning 223
We conduct this experiment in an 8-D environment with 3,281 pits (50% of interior states), which is empirically the most challenging 8-D CoNE configuration for BraVE. Success in this setting best indicates generalizability to environments where BraVE demonstrates stronger performance.
Both methods first trained offline for 1,500 gradient steps, after which BraVE achieves average return -226.1 compared to IQL's -29..4. We terminate offline training at this point, as BraVE consistently surpasses IQL beyond this threshold (see Figure 6p. Online fine-tuning then proceeds for an additional 5,000 environment steps.
-100-
Episode Reward
-200-
-300
-400-
Bra VE IQL
k
2
3
4
5
Gradient Steps
Figure 8: Learning curves for finetuning BraVE and IQL. after 1,500 offline gradient steps.
As shown in Figure 8 the methods achieve comparable final performance during tne-tuning, with BraVE slightly outperforming IQI..
25

---

D Ablation and Hyperparameter Learning Curves
This section presents learning curves from four ablation and hyperparameter studies: (1) the effect of varying the depth penalty 6, (2) BraVE's sensitivity to a, the weight of the TD error in the total loss, (3) the importance of BraVE's tree structure, and (4) the effect of beam width on both return and computational overhead. A summary of these results appears in Figure ! with full details and D.4 respectively. All experiments are conducted in
provided Appendices D.I D.2
D.3
five-pit environments.
200
-200
Final Return
Final Return
400
1000
-600
-150
d=5
800
-200
1000
-250
1200
No Peralit
300
256
1024
40%
lok
65%
260k
IM
4M
236
1024
4096
16k
65h
260lk
IM
4M
Action Space Size
Action Space Size
Depth penalty ablation
Varying
200
|A| 16k
|A| 65k
200
Steps per Second
| 260k
Final Return
400
150
|A| 1M
|4| 4M
600
100
50
-1000
DQN
BraVE
12200
256
1024
4f19
1ok
risk
26ilk
IM
4M
50
100
200
300
400
500
Action Space Size
Beam Width
(c) Comparison to DQN
(d) Steps per second for varying beam widths
Figure A small depth penalty (6 1) yields the best performance across all environments
(Figure 9ap. Performance remains relatively stable across range of values; however, omitting the TD loss entirely (a = 0) can result suboptimal policies (Figure (b). Although constraining the DQN select actions within B introduces inductive bias, fails to produce viable policy (Figure Pc). Beam width has minimal practical impact on runtime as inference remains under one second even with beam widths well above the optimal setting (Figure 9d)
26

---

D.1 Depth Penalty Ablation
6=1 1
6=5
6= 10
== 15
No penalty
[|| 16
[A]
[A] - 64
[A]
Egisak Rewaed
-100
Eginsk Reward
200
-300
200
Episedk
-110
-000
-100
-00
646
466
-90
-00
16k
Hkk
24
-016
I6k
24
.900
Gradient Steps
Grudiest Steps
Grudient Steps
Gradien Siepa
|
M|
|||= = 1,024
250
Eptold Rewword
-300
Eptodd Stemoud
-290
-30-
-000
-900
-00-
<00
-100
-000
-1250
116
15k
Gradient Stops
Goodlent Shaps
Gadden Staps
Grodient Steps
||] = 4,096
|A] = 4,096
Epiialee Recoand
-00
410
-100
-100
22
18k
52
106
15k
2/4
Grodhent Stepe
Ordient Stege
Figure 10: Learning curves for BraVE with varying depth penalty values (8).
While the depth penalty improves performance, it should remain small; = 1 yields optimal results across nearly all environments.
27

---

D.2 Varying TD Weight in Loss
10
5
15
25
[|] = 16
|
[A| = 64
|
110
Eptonk Rowsnl
-100
Eqiankk Rowent
-100
Epiuat
Epinnt
-100
400
440
-00
-10
16
12k
26
26
10k
18k
26
24
10k
18k
Grudieat Stope
Gradicat Stzps
Grudiesd Steps
Grddiert Steps
|A| = 256
|.|] = 256
[ 1,024
|A|= = 1,024
110
Epjoak Roward
-100
Epboue Kowaod
-200
-400
-200
-00
-200
186
36
104
17
24
FG Godeett Staps
114
15k
36
Grddent Steps
Grudlest Steps
Grudlezt Steps
[A]] 4,096
|A| 4,096
Eric-d: Roconl
-210
-100
Epicod:
-306
10R
15k
26
52
10E 15k
24
Grodent Stepe
Gradinn Stege
Figure 11: Learning curves for BraVE with varying TD loss weight values (a)).
Performance is relatively stable across a values low-dimensional enviromments, with the exception of the 2-D case, where the high pit density makes accurate decision decision-making critical. In higher- dimensional settings, BraVE becomes more sensitive to the choice of a. In particular, omitting the TD loss term (a = result in catastrophic failures, especially in complex environments such as the 8-D setting.
28

---

D.3
Comparison to DQN
To isolate the effect of BraVE's tree structure, we compare it DQN constrained selecting actions from the dataset B and trained using BraVEr behavior-regullrizze TD loss (Equation 4
BraVE
DQN
[A]] = 16
|A| 64
||| 256
|||= = 1,024
Epaaod Towar
-100
Eposoii Riowor
-200-
-270
-220
-400
-40
346
-116
-300
-16
-28-
-10
18k
104
26
15k
Gradicat Stope
Gradica Stepe
Grdiict Steps
Gindiirt Steps
|A| = 4,096
|A| 16,384
65,536
Epionk Rowaed
-200
-200
Egioode Revaad
+00
Epiont:
Eptoode
-800
-000
-990
1ik
216
lik
18k
zic
10L
20c
-190
1
Grudicat Stops
Grudiest Staps
Gradicnt Staps
Crallent Stepa
[|]] 5,048,576
[.4] 4,194,304
Egiiode Borward
-100
-400
900
900
-900
-1200
Giadicet Staps
Gradient Stops
Figure 12: Learning curves for BraVE and DQN constrained select actions from B and trained with BraVE's behavior-regularizer TD loss (Equation effectively, BraVE without tree- based action selection branch value propagation.
Although the DQN is trained with the same behaaior-regularrzze TD loss as BraVE and is restricted to selecting actions in B, fails to learn an effective policy. This suggests that the DQN struggles to capture sub-action dependencies, particularly in large action spaces. For example, in the 11-D environment, must evaluate all 8,927 unique actions in B simultaneously. BraVE mitigates this complexity by organizing the action space as a tree, reducing the number of required predictions to small subset Q-values at each timestep.
29

---

D.4 Beam Width
Because beam search used only during policy extraction after value estimates have been leamned - it remains independent of the learning process. This decoupling allows for post-training optimization of beam width, provided the environment permits hyperparameter tuning. To evaluate the impact of beam width on both return and computational overhead, we measure return, environment steps per second, and total episode runtime beam widths ranging from 500.
||| 16k
|A|=
65k
|||
260k
|A|
1M
|A| 4M
200
3.0-
Total Time in Seconds
2.5
150
2.0
Return
1.5
25
Steps
1.0-
0.5-
0.0
300
400
500
300
500
300
400
500
Beam Width
Beam Width
Beam Width
Figure 13: Effect of beam width on return and computational cost, measured environment steps per second and total episode runtime.
beam width of 10 is generally sufficient for near-optimal performance. Larger beams can degrade performance by exploring low-confidence regions of the tree, where Q-value estimates are less reliable. Narrower beams act as a form of regularization, limiting search well-learned regions of the action space.
Beam width has negligible practical impact runtime: inference times remain well below one second, even for beam widths far exceeding the optimal setting. These results are based on tests conducted on 10-core CPU with 32 GB of unified memory and GPU.
30


Reviews:
[{"review_id": "xcFRE7TBie", "reviewer": "Reviewer_KDjC", "summary": "Authors introduce BraVE an offline RL algorithm for combinatorial discrete action spaces with multiple dimensions related to different sub-actions.\n\nThe problem of evaluating the action-value function maximum over a large combinatorial action space $\\max_a Q(s,a)$ (given a state $s$) needed for action-value function learning using TD method is alleviated by using dedicated neural network $f$ and organizing \nactions into a tree structure where, given some fixed ordering over sub-action dimensions, in each tree level one sub-action is decided.\n\nThe trick is that the network $f(s,a)$ is trained to output $Q(s,a)$, where $a$ corresponds to some tree node, but also to output maximum values over sub-trees corresponding to all its child nodes.\n\nThis is done by updating $f$ loss with every $Q$ target computation. \n\nSuch $f$ then allows for fast $\\max_a Q(s,a)$ evaluation (linear in number of action space dimensions). \n\nBesides this basic idea authors include many practical improvements  including:\ntree sparsification (to include only nodes which corresponds to actions actually present in the off-line dataset),\nmasking (when number of sub-actions across sub-action dimensions varies),\ndepth-penalty weight (helping to weight more the errors closer to the root node where decisions are more critical),\nand beam search (for better robustness during inference).\n\nAuthors demonstrate feasibility of the method on their proposed benchmark which allows for strongly dependent sub-actions (depending on a given state) with superior performance over compared baselines.", "questions": "1) I am missing information on how the $f$ network is initialized\nin order to fit with $\\max_a Q(s,a)$ evaluation. One could  train it with some lower bound on $Q$ values, but it seems to introduce an inconvenient bias. Could you clarify this?\n\n2) From Figure 13a, it seems that increasing beam width brings rather problems (decrease in return). Could you comment on this?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The paper is well written, the presentation is clear, and the proposed method is well motivated.\n\nAlthough there is not much math, I found no errors and typos in the math formulas.\n\nI found the proposed idea of how to cope with $\\max_a Q(s,a)$ evaluation compelling.\n\nI would  like to see the generalization of the proposed method to the standard online RL setting where probably also tree structure has to be updated due to possible distribution shift.\n\nGenerally, I have no complaints about the paper.", "was_revised": true, "final_justification": "The paper approach is novel addressing a gap in current RL portfolio (combinatorial discrete action spaces with dependent sub-action in offline setting). The authors clarified all my questions. I also read the other reviews. As a result I think the paper should be accepted.", "rebuttal": "Thank you for your very positive review. We are delighted that you found our core idea **\"compelling\"** and **\"generally have no complaints about the paper\"**. We also appreciate your recognition of the **\"practical improvements\"** that strengthen BraVE beyond its core tree-based traversal framework. We are grateful for your confidence in our work. Below, we address your questions and comments in more detail.\n\n### Q1: How is network initialized in order to fit with $\\max_a Q(s,a)$ evaluation?\n\nWe use standard initialization (Kaiming) as in a typical DQN. No special treatment is needed: both node Q-values ($q$) and branch values ($\\mathbf{v}$) are learned jointly via Bellman supervision and the $L_\\text{BraVE}$ loss (Algorithm 1, Figure 3). The branch values are not pre-initialized or pre-trained. Instead, $L_\\text{BraVE}$ drives them to match the maximum of their children, enabling structure to emerge from data without relying on priors or artificial constraints.\n### Q2: Why does increasing beam width sometimes decrease return?\nThis is an excellent observation. Beyond a beam width of ~50, performance can degrade because broader searches enter parts of the tree where Q-values are less reliable. Narrower beams implicitly regularize by keeping search within high-confidence regions.\nTo ensure this point is clear in the paper, we have added the following clarification to Section 4.3:\n> This degradation arises because broader beams may explore low-confidence regions of the tree where Q-values are less reliable. Narrower beams serve as a form of regularization, restricting search to well-learned regions of the action space.\nSince beam search is used only at inference time, beam width remains a tunable hyperparameter that can be adjusted post hoc based on compute or task requirements.\n### Q3: How might BraVE extend to the standard online RL setting?\n\nWe agree that the online setting is an exciting and important direction for future work. Enabling online use would indeed require an alternative mechanism (such as dynamic tree construction), since our current approach builds and sparsifies the tree using a fixed offline dataset $\\mathcal{B}$ (Sections 3.1-3.2).\n\nTo help point others in this direction, we have added the following sentence to the Discussion and Conclusion (Section 6) describing BraVE’s potential relevance beyond the offline RL:\n\n> Finally, while our work focuses on the offline setting, we believe BraVE provides a strong foundation for online combinatorial RL. Extending our framework would require addressing a new form of exploration–exploitation trade-off, potentially by replacing our dataset-driven tree sparsification with a dynamic mechanism for growing and pruning the action tree during learning."}, {"review_id": "wXYmFyRPjR", "reviewer": "Reviewer_cJdX", "summary": "This paper introduces Brave, a novel offline RL algorithm designed to handle high-dimensional, discrete combinatorial action spaces. The paper says that existing methods are either computationally infeasible due to exhaustive evaluation of vast number of actions, or sacrifices accuracy by factorizing Q-values. Brave addresses this trade-off by imposing a tree structure on the action space, allowing it to evaluate maxQ with a linear number of evaluations while preserving the dependency structures of action dimensions. The method employs a Q-guidance to traverse this tree, and these guidance are trained with a behavior-regularized temporal difference loss. The experiments show Brave is significantly outperforming baselines.", "questions": "- Can we simply use BraVE as an online algorithm if we do not put l2-behavior-regularization? If yes, why should the paper focus on the offline setting?\n- By having additional binary indicator of whether the action is selected or not, Q-function of BraVE seems to have different neural architecture compared to other algorithms. How is this implemented, and how do you ensure a fair comparison with other baselines?\n- As difficulty of the problem (|A| or |S|) increases, the experiments result does not have a clear trend. For example in table 3, FAS shows much better performance on |S|=15625 compared to |S|=25. What is the reason to this?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Proposes a novel method to cleverly implement Q-learning on large combinatorial action space\n- Algorithm well explained\n- Significantly outperforms other baselines\n\nWeaknesses\n- While the proposed method is about handling large combinatorial action space, the paper limits its scope on offline RL settings, and the contribution specific to offline setting is minor (adding l2 regularization). Considering that the main contribution can be applied to any RL settings, I believe that the paper should have been focused on standard online setting rather than offline setting.\n- While the paper only says about the FAS approach in the paper, actually there have been a number of different approaches toward large combinatorial action space. If we insist learning with Q-learning-based algorithms, we can either learn an action embedding [1], or use a model-based approach through Q=r+V [2].\n[1] Dulac-Arnold, Gabriel, et al. \"Deep reinforcement learning in large discrete action spaces.\" (2015)\n[2] Vinyals, Oriol, et al. \"Grandmaster level in StarCraft II using multi-agent reinforcement learning.\" nature 575.7782 (2019): 350-354.\n  - If we are OK with other type of algorithms, policy-based algorithms (e.g., PPO) or sequence modelling approaches (e.g., Decision Transformer) will be able to easily solve the problem.\n  - Therefore, I am not very satisfied with the empirical evaluations done in the paper; it is even very hard to get a feeling about whether Brave is working or not, as FAS and IQL are mostly broken and any other types of algorithm, or oracle policy, are not included.\n- Furthermore, all three algorithms experimented have a very different behavior regularizations. IQL - quantile regression, FAS - BCQ like, BraVE - l2 regularization. While the difference between BraVE and FAS on how to handle large combinatorial action space is the main focus here, some of the performance differences may have been originated from these different behavior regularizations; I would say this is not a good way to demonstrate the performance of the proposed method.", "was_revised": true, "final_justification": "I understand the point of the authors, and some of my reviews might be mis-claiming to certain extent. However, I do not think the paper is as \"strong\" as score 5, considering its weak presentation and experimentations.", "rebuttal": "Thank you for your review.  We are overall pleased that you recognize BraVE as a **\"novel\"** method that **\"cleverly implements Q-learning on large combinatorial action space\"** and how it **\"significantly outperform[s] baselines.\"**\n\nSeveral of your concerns appear to reflect an online RL perspective. However, our method is explicitly designed for the offline setting, with contributions motivated by challenges specific to that regime. These points can be resolved by increasing the clarity of the paper, as outlined point-by-point below. We hope these clarifications warrant a reconsideration of your score. Thank you again for your thoughtful and constructive review.\n\n### W1: The paper limits its scope to offline RL, while the method could be applied online\n\nWe appreciate the opportunity to clarify our work's positioning. Our focus on offline RL is deliberate and central to our contribution, which goes well beyond simple L2 regularization.\n\nFirst, BraVE introduces a tree sparsification mechanism (Section 3.2) that is only possible in the offline setting. It uses the fixed dataset $\\mathcal{B}$ to prune the action tree, restricting Q-value estimation to actions with empirical support. This serves as a structural regularizer that mitigates overestimation from out-of-distribution actions — a key challenge in offline RL that does not arise in the online setting.\n\nSecond, we focus on the offline setting because of its practical importance. As stated in our introduction, many domains with combinatorial action spaces, such as treatment planning, resource allocation, or industrial control, preclude online exploration due to safety, ethical, or cost constraints.\n\nOffline RL has emerged as a distinct field in which methods are designed precisely to address these challenges [1]. Modern offline algorithms, such as BCQ [2] and IQL [3], are defined by their approaches to the distribution shift caused by fixed data. Our work is situated within this paradigm, offering a new structural approach to a well-established offline RL problem.\n\nWhile core ideas from BraVE may be adaptable to the online setting, our work is specifically designed for offline RL — a distinct setting with its own challenges.\n\nTo resolve your concern, we have updated the Discussion and Conclusion (Section 6) by adding the following:\n\n> Finally, while our work focuses on the offline setting, we believe BraVE provides a strong foundation for online combinatorial RL. Extending our framework would require addressing a new form of exploration–exploitation trade-off, potentially by replacing our dataset-driven tree sparsification with a dynamic mechanism for growing and pruning the action tree during learning.\n\n### W2: Comparison to other approaches for large combinatorial action spaces\n\nThank you for these suggestions. We compare BraVE against the **most relevant and state-of-the-art baselines under the offline RL setting**. Our choice of baselines is principled and more comprehensive than related works’, as detailed below.\n\nFirst, we note that Dulac-Arnold et al. [4] is already cited in Section 5.2 as a foundational method for large discrete action spaces. However, it is inherently an **online** algorithm with no straightforward extension to offline RL. Similarly, PPO is an on-policy online method, and thus not directly applicable to our setting. While Decision Transformer is a valid offline approach, it reframes RL as sequence modeling — conceptually different from value-based learning. Since our work is situated in the value-based paradigm, we compare against IQL (SOTA in value-based offline RL) and FAS (SOTA in combinatorial spaces). Demonstrating that BraVE overcomes the failure modes of these widely-used methods is, we believe, a more direct and informative contribution.\n\nOur evaluation is also more thorough than many recent works in this space. For instance, Tang et al. [5] (FAS) compared only against BCQ, while Beeson et al. [6] compared multiple factored methods against each other and an oracle, but not against non-factored approaches like IQL. By comparing BraVE against both a strong factored baseline (FAS) and a non-factored baseline (IQL), we provide a more complete and rigorous characterization of BraVE's advantages.\n\n### W3: It is difficult to assess BraVE's performance because FAS and IQL are \"mostly broken\" and an oracle policy is not included\n\nWe respectfully but firmly disagree.\n\nBraVE was explicitly designed to address the failure modes of existing offline RL methods in the presence of sub-action dependencies. The CoNE benchmark was constructed to isolate and control this challenge. Our hypothesis — that standard algorithms like IQL and FAS would fail under these conditions — is strongly validated by the observed empirical results.\n\nThat these baselines perform poorly is not a shortcoming of our evaluation; it is a **core experimental finding** and a primary motivation for BraVE. Highlighting these failure cases is critical for progress in this area, and underscores the need for approaches that go beyond naive factorization or flat value estimation.\n\nTo further contextualize performance and address the concern that an oracle policy is not included, **we compute a new metric, the normalized episode-length score, to measure each method's performance relative to an oracle baseline for the results in Table 2**. This score places each method on a 0–100 scale, where 0 corresponds to a random policy and 100 to an oracle planner. It is defined as:\n\n$$\\text{score}\\_\\text{norm} = 100 \\cdot \\frac{\\text{length}\\_\\text{random} - \\text{length}\\_\\text{agent}}{\\text{length}\\_\\text{random} - \\text{length}\\_\\text{oracle}}$$\n\nwhere $\\text{length}\\_\\text{agent}$ is the average episode length of the evaluated policy, $\\text{length}\\_\\text{random}$ is the episode length of a random policy (which consistently times out at 100 steps), and $\\text{length}\\_\\text{oracle}$ is the optimal path length computed via A$^*$ search.\n\nBelow are the scores for the setting with non-factorizable rewards and sub-action dependencies (Table 2):\n\n| Pit % | BraVE |  FAS |  IQL |\n| --- | :---: | :--: | :--: |\n| 0     |  99.3 | 89.6 | 88.0 |\n| 5     |  92.8 | 57.3 | 52.9 |\n| 10    |  94.1 | 20.2 | 51.5 |\n| 25    |  78.5 |  0.0 | 54.7 |\n| 50    |  71.4 |  0.0 | 40.6 |\n| 75    |  78.5 |  0.0 | 38.4 |\n| 100   |  79.3 |  0.0 | 37.0 |\n\nThese results show that BraVE maintains strong performance as sub-action dependencies become more severe, precisely the regime where prior methods fail. This validates both CoNE as a benchmark and BraVE as an effective solution.\n\n### W4: Performance differences may stem from differences in behavior regularization\n\nWe appreciate this concern. Our comparison used the published, SOTA versions of IQL and FAS, which include their respective behavior regularization mechanisms: expectile regression in IQL, and BCQ-style filtering in FAS. These are not auxiliary add-ons, but integral components of each algorithm. Creating custom versions of these methods using a shared regularizer (e.g., our L2 penalty) would introduce untested variants, undermining reproducibility and fairness. We believe that comparing BraVE against strong baselines as defined in prior work is the most standard and principled approach.\n\nMoreover, the large performance gaps (e.g., $-41.6$ vs. $-1131.4$), are unlikely to be caused by regularization alone and instead reflect BraVE's superior modeling of sub-action dependencies.\n\n### Q1: Can BraVE be used as an online algorithm if we omit the L2 regularization?\n\nPlease see W1.\n\n### Q2: Does BraVE use a different neural architecture (e.g., a binary indicator)?\n\nBraVE does not use binary indicators or encode any tree-specific structure into the Q-network input. The Q-function is implemented as a standard MLP that takes the full state $s$ and full action vector $a$ as input — the same input format used by IQL.\n\nThe tree is used solely to structure the $\\arg\\max$ operation during inference and to define the recursive loss used to train the $\\mathbf{v}$ values. It does not modify the architecture or provide additional context to the Q-function itself.\n\nWe have clarified this in Section 3.3 to make the model architecture and input specification more explicit:\n\n> Importantly, the network $f$ is a standard function approximator (e.g., an MLP) and does not require any specialized architecture. It takes as input the state $s$ and the complete action vector $\\mathbf{a}_\\text{node}$. The tree is not encoded into the network input; instead, it is an external structure that organizes the $\\arg\\max$ computation and defines the recursive supervision used to train the branch values $\\mathbf{v}$.\n\n### Q3: Why does FAS perform better on $|\\mathcal{S}| = 15625$ than on $|\\mathcal{S}| = 25$?\n\nIn Table 3, the number of pits is fixed at 5. As the state space grows, these pits comprise a smaller fraction of the environment. FAS's apparent improvement reflects this reduced exposure, not an improved ability to handle hazardous interactions.\n\nBraVE, by contrast, maintains consistent performance across environment sizes because it models sub-action dependencies correctly, regardless of how frequently they arise. This contrast highlights BraVE's robustness, even when rare events play a critical role in task success.\n\n[1] Levine et al. Offline reinforcement learning: Tutorial, review, and perspectives on open problems (2020).\n\n[2] Fujimoto et al. Off-policy deep reinforcement learning without exploration (2019).\n\n[3] Kostrikov et al. Offline reinforcement learning with implicit q-learning (2021).\n\n[4] Dulac-Arnold et al. Deep reinforcement learning in large discrete action spaces (2015).\n\n[5] Tang et al. Leveraging factored action spaces for efficient offline reinforcement learning in healthcare (2022).\n\n[6] Beeson et al. An investigation of offline reinforcement learning in factorisable action spaces (2024)."}, {"review_id": "qqdfXv3Z8e", "reviewer": "Reviewer_2ATV", "summary": "In this paper, the authors address the problem of offline reinforcement learning in environment with combinatorial action spaces. The proposed method represent the action space with a tree structure where each node represents a complete action and each level correspond to an action dimension.  Each node is characterized by a value estimate and a vector of branch values for each subtree, these values are estimated by a neural network. The neural network is trained using a regularized TD learning loss as well as a custom branch value supervision loss.\n\nThe resulting algorithm is evaluated on a synthetic dataset from a n-dimensional navigation problem against an offline RL baseline (IQL) and an offline RL with value factorization (FAS). \n\nThe proposed method has similar performance as FAS for low dimensional action space but outperforms both baselines by a lot as the action space grows.", "questions": "-\tWhy a tree and not a graph?\n-\tWhat is the definition of $\\hat{a}$?\n-\tCould you provide more intuition about why the reward cannot be factorized in your experiments?\n-\tWhat is the impact of the order of the action dimension when constructing the tree in BRAVE?\n-\tHow would BRAVE perform on a non synthetic dataset?", "limitations": "Most of the limitations are acknowledged by the authors:\n\n-\tDiscrete actions required\n-\tThe ordering of the action can impact the performance (although no guidance is provided on that)\n-\tIt is an offline method, so it depends on the quality of the dataset", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n- The idea of representing the value function by a tree is interesting and as far as I know novel and present a strong contirbution.\n\n- The paper is well organized, and fairly easy to follow (except the section on the loss calculation). \n\n- The method shows strong performance on the synthetic dataset compared to the baseline. The experiments seem well-designed and they evaluate the method in controlled settings. The results are quite convincing. Some of the description of how the environments are generated could be improved.\n\n**Weaknesses**\n\n1. Why only evaluating on synthetic data? I understand the importance of the experiments proposed to evaluate the algorithm in a controlled setting but it would have made an even stronger case to add an example on a real dataset.\n\n2. The ablation study is an important part of the analysis and lack discussions. The authors provide curves in appendix but do not discuss the results. I believe such a discussion should be included to the main text. \n\n3. Another aspect that is missing and I think crucial is the analysis of the order of the tree. It seems to me that the way the tree is constructed can impact the result greatly, as some actions might be more important than others, if they appear very deep in the tree the performance might be impacted. In the related work discussion MCTS it is mentioned that a sequential structure need to be imposed, however it seems to me that the tree constructed by brave also need to impose some arbitrary structure on the action space. The authors acknowledge this limitation in the conclusion but still I think it could use a dedicated experiment.\n\n4. Explanation of the algorithm sometimes lack clarity\n\n- The loss computation is a key component of the method but lack some clarity. $\\hat{a}$? is not defined, and it is not described how $v$ is learned. \n- I also did not understand why v, the best value of each subtree, needs to be learned and not computed after the training from the estimated q values. The pseudo code provides a little bit more insights but it would help to make the text consistent. \n- Some of the explanation of the results could use more justification, for example when the authors explain the behavior of FAS on high dimensional problem l258.\n- The experimental setup with sub-action dependencies is hard to understand. The number of pits is said to increase to 100%, does that mean the whole state space is a pit?", "was_revised": true, "final_justification": "I raised my score to accept after reading the author's rebuttal. I believe the tree based approach is original and interesting, and the problems of combinatorial offline RL that could be addressed are fairly wide. The authors provided reasonable justifications for the weaknesses that I mentioned. One could criticize that the experiments are a bit limited in scope (synthetic environments), but I would argue that it is also a strength of this paper, they designed a well controlled environment to truly understand the performance gap between the proposed method and the baseline.", "rebuttal": "Thank you for your thoughtful review. We're excited you found our work to be a **\"novel\"** and **\"strong contribution\"**. We also appreciate your comments that our experiments are **\"well-designed\"** and that our **\"results are quite convincing\"**. \n\nWe’re glad to see that many of your remaining concerns focus on clarification and additional detail — particularly around the loss, ablations, and tree ordering — and we are pleased to report that these have been fully addressed through improved explanations and new experiments. If you feel these updates resolve your concerns, we hope you will consider updating your evaluation accordingly. We would be glad to continue the discussion should any further questions arise. Thank you again for your thoughtful review.\n\n### W1: Evaluation limited to synthetic data\n\nWe believe synthetic environments are sufficient for this work because our goal is to isolate and analyze sub-action dependencies under controlled conditions. While real-world offline RL evaluations may be ideal, they typically rely on off-policy evaluation (OPE), which is known to be noisy and biased. Prior work such as Tang et al. [1] used OPE and expert evaluation for domain-specific insights, which is appropriate for their application-based paper. However, for an algorithmic contribution like ours, we find that a high-fidelity simulator enables direct measurement of policy performance via ground-truth rollouts, providing a clearer and more reliable evaluation signal and ultimately a deeper understanding of BraVE’s strengths and weaknesses compared to SOTA methods.\n\nWe view real-world deployment and evaluation as important future work and have added this text to the conclusion (Section 6):\n\n> While our current evaluation uses controlled synthetic environments to enable clear algorithmic analysis, real-world deployment and evaluation is an important direction for future work.\n\n### W2: Ablation discussion should be in the main text\n\nThank you for this suggestion. We agree, and have revised Section 4.2 to summarize the key findings from Appendix B as follows:\n\n> We conduct a series of ablation and hyperparameter studies to assess the contribution of BraVE's design decisions. First, we examine the effect of the depth penalty $\\delta$, which scales the loss based on a node's position in the tree. A small penalty ($\\delta=1$) consistently yields the best results, confirming the importance of emphasizing accuracy near the root. Second, we vary the loss weight $\\alpha$ to examine the trade-off between the behavior-regularized TD loss and the BraVE loss. While performance is stable across a range of $\\alpha$ values, omitting the TD term entirely ($\\alpha=0$) leads to degradation, particularly in higher-dimensional tasks. Third, to isolate the role of BraVE's tree structure, we compare against a DQN baseline trained with the same loss but without hierarchical traversal or branch value propagation. This variant fails to learn viable policies, highlighting the benefits of BraVE's structured decomposition. Fourth, we evaluate the effect of beam width on performance and inference time. A width of 10 is sufficient for strong performance, and even large widths incur minimal runtime overhead, demonstrating the method's practical efficiency. Finally, we assess BraVE's sensitivity to sub-action dimension ordering. We retrain BraVE, FAS, and IQL across five random action orderings in the most challenging 8-D, 50% pit setting. Results remain consistent with our main findings (Table 2), confirming that BraVE's performance does not depend on a favorable ordering. Full results are presented in Appendix D.\n\nWe thank you for encouraging this improvement. Note that the action order ablation was added in direct response to your feedback and is further discussed in W3.\n\n### W3: Missing analysis of action dimension ordering\n\nWe fully agree that this analysis is important and **we have conducted a new experiment to evaluate BraVE's sensitivity to action dimension ordering as follows**.\n\nWe trained BraVE, FAS, and IQL using five different randomly permuted action orderings in the 8-D, 50% pit CoNE setting, which is empirically the most challenging 8-D variant. The results are shown below:\n\n|        BraVE       |          FAS         |         IQL        |\n| :----------------: | :------------------: | :----------------: |\n| $-53.5 \\pm 29.1$ | $-1103.6 \\pm 51.4$ | $-96.2 \\pm 51.8$ |\n\n\nThese findings are consistent with those originally reported in Table 2, showing that BraVE outperforms FAS by an order of magnitude and is roughly twice as effective as IQL. This demonstrates that BraVE’s performance is robust to the ordering of sub-action dimensions and not dependent on a favorable arrangement. We have added this analysis to Section 4.3.\n\n### W4: $\\hat{\\mathbf{a}}'$ is undefined\n\nThe variable $\\hat{\\mathbf{a}}'$ is defined on lines 138 and 171, as well as in the Require section of Algorithm 1, as the action selected via tree traversal. Please let us know if you believe it would be helpful to reiterate this definition elsewhere in the text.\n\n### W5: It is unclear why and how $\\mathbf{v}$ is learned\n\nThe greedy action $\\hat{\\mathbf{a}}'$ is needed to compute the Bellman target for updating $Q(s, \\mathbf{a})$ (Equation 1). During the forward pass, however, the Q-values for all descendant nodes are not available, as they are themselves outputs of the network being trained. To avoid evaluating the full combinatorial action space at each step, we rely on the network's estimates of $\\mathbf{v}$ to guide tree traversal toward promising branches. In this way, $\\mathbf{v}$ is fundamental to learning $Q$, and thus cannot be computed post hoc from already-trained Q-values. We have clarified in Section 3.3 as:\n\n> Crucially, these branch values must be learned and predicted by the network, as they guide the efficient search for$\\hat{\\mathbf{a}}'$ used in the Bellman target computation (Equation 1), before the values of descendant nodes are themselves known.\n\nAs described beginning on Line 179 and illustrated in Figure 3, $\\mathbf{v}$ is learned via the $L_{\\text{BraVE}}$ loss, which recursively enforces consistency between branch values and the maximum Q-value of a node's descendants. We have clarified this training mechanism in Section 3.4:\n\n> In this way, the propagated targets directly supervise the network's predictions for the branch values $\\mathbf{v}$ at each node. Thus, $\\mathbf{v}$ is explicitly learned through $L_{\\text{BraVE}}$ to reflect the highest Q-value available in each subtree.\n\n### W6: It is unclear why FAS's performance degrades in high-dimensional problems when rewards are non-factorizable\n\nFAS’s performance degrades in this setting due to its fundamental simplifying assumption of linear value decomposition in the reward $r(s, a) = \\sum_{d=1}^D r_d(s, a_d)$.\n\nMore specifically, the reward function $r = -\\text{distance}(s, g)$ depends on the joint effect of all sub-actions and cannot be decomposed additively. For example, the joint action “move up and left” leads to a diagonal movement with a specific reward. Evaluating “move up” and “move left” separately would yield different states and thus different rewards, breaking the additive assumption (see Appendix A). We have clarified this reasoning in Section 4.1 to better support the empirical findings:\n\n> Because the reward is computed from the final state resulting from the full action vector, it is not meaningful to assign individual rewards to sub-actions in isolation. This mismatch introduces a modeling bias into FAS that grows with action dimensionality. As a result, FAS learns inaccurate Q-values and exhibits degraded performance. BraVE avoids this instability by evaluating full joint actions directly, maintaining high performance across dimensions.\n\n### W7: It is unclear if 100% pit coverage in Table 2 means the whole state space is a pit\n\nAs noted on line 266, 100% pit density refers to the fraction of *interior* (non-boundary) states that are designated as pits. To make this more explicit, we have clarified the text in Section 4.1 as follows:\n\n> In an 8-D environment (\\$|\\mathcal{A}| = 65,536\\$), we vary the number of pits from 5% to 100% of the 6,561 interior (non-boundary) states, ensuring that there is always a feasible path to the goal along the boundary of the state space. Boundary states are never assigned as pits.\n\n### Q1: Why a tree and not a graph?\n\nThe tree provides a structured framework for optimizing over high-dimensional combinatorial actions. It partitions the joint action space by progressively fixing sub-action components at each level, enabling efficient traversal and targeted evaluation of full action candidates. This structure supports recursive training of both Q-values and subtree maxima via the $L_{\\text{BraVE}}$ loss.\n\nWhile a graph could offer similar structural benefits, it introduces cycles and multiple paths between nodes, which complicates inference and learning by making value propagation more difficult. The tree, by contrast, offers a clean and tractable structure that aligns well with our optimization objective. Our results confirm the practical effectiveness of this approach.\n\n### Q2: What is the definition of $\\hat{a}'$?\n\nPlease see W4.\n\n### Q3: Why is the reward non-factorizable?\n\nPlease see W6. The reward $r = -\\text{distance}(s, g)$ is non-factorizable because it depends on the joint outcome of the full action vector and cannot be expressed as a sum of rewards for individual sub-actions.\n\n### Q4: What is the impact of action ordering?\n\nPlease see W3. Our new experiments demonstrate that BraVE is robust to the ordering of sub-actions.\n\n### Q5: How would BraVE perform on a non-synthetic dataset?\n\nPlease see W1.\n\n[1] Tang et al. Leveraging factored action spaces for efficient offline reinforcement learning in healthcare (2022)."}, {"review_id": "4Wp2bqYKdQ", "reviewer": "Reviewer_BzAb", "summary": "This paper proposed to handle combinatorial action spaces which can be very large in offline RL. The authors proposed to construct a tree to sequentially handle each action dimension relying on node Q values and branch V values. The authors further restricted the tree to only dataset actions to sparsify the tree to lower computational cost.", "questions": "Besides the questions in the weakness section, I am curious that can this sequential traversal approach be applied to softmax action selection?", "limitations": "No societal impact applicable. For limitations, the authors have discussed some limitations of the paper, as the tree traversal indeed relies on a fixed predefined ordering of sub-action dimensions.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\\\n\nHandling combinatorial action spaces is of fundamental interest to RL. I think the paper is overall well-written and the tree-based method is principled. Positioning the tree structure in offline RL where only dataset actions are used is also very clever and matches that of conservative offline RL. I also like the idea of $q$ and $v$ values that estimate node and subtree values so that the tree does not need to be fully traversed before an action can be picked. \n\n**Weakness:**\\\nHowever, it seems the paper is not complete in several aspects. I believe the paper can benefit from more explanations both theoretically and empirically:\n1. the tree essentially acts as a policy to output actions given input states. That means for every input state we should maintain a tree and more importantly have all its node and branch values **accurately estimated**. However, this seems to be prohibitive for continuous states since we need to build infinitely many trees. How did you deal with continuous states? Did you apply some binning? When dealing with continuous spaces, the network function $f(\\cdot, \\cdot; \\theta)$ typically maps to a distribution like Gaussian, and we can generally hope the network generalize to similar states, but I don't see how that is possible given the way the tree was constructed in BraVE.\n\n2. for the tree to be useful, we need to have accurate estimates of $q,v$. But because $v$ is a summary of values of all subtrees, how did BraVE ensure that the values from unchosen subtrees (evetually leaf nodes) were accurate? Did you need extra assumptions or structures on the network $f$ to ensure unchosen leaf nodes had reasonable values? More generally, if $q$ and $v$ had estimation errors, how did the errors influence action selection? Because of the tree structure, I would expect that the chance of picking a wrong action depends on tree level. This type of discussion would add to the contribution of the paper.\n\n3. I am afraid that the experiments are limited in diversity. In the first paragrah of the paper the authors mentioned applications like healthcare but they were not touched in the experiments. Moreover, some related papers tested the discretized continuous action spaces, that would also add to the credibility of the paper, see ref [1].  Related to this, I found it very strange that IQL can perform well even with this large discretized action space in supp? Why this is the case?\n\nReferences:\\\n[1] Path Consistency Learning in Tsallis Entropy Regularized MDPs, ICML 2018", "was_revised": true, "final_justification": "The paper studies combinatorial action spaces which is of vital importance to RL. Despite some issues on clarification limitations such as error influence conditioned on tree level, I believe the paper offers contributions that will be of interest to the RL community. The authors engaged in discussion actively, and I have requested the authors to clearly point out the remaining issues since they do not overweigh the contributions.", "rebuttal": "Thank you for your review. We’re glad you agree that this space is of **\"fundamental interest to RL\"** and appreciate your kind remarks that our **\"tree-based method is principled\"** and that our sparsification strategy is **\"very clever\"** and well-aligned with conservative offline RL. We also appreciate your interest in our $q$ and $\\mathbf{v}$ structure, and agree that the ability to select actions without full tree traversal is a key strength. \n\nWe are pleased that your concerns primarily relate to clarification, and we have addressed each one with additional explanation and technical detail. We have also conducted a new experiment based on your feedback. We hope these improvements make the paper's contribution and readiness for publication clear. If you find that your concerns have been fully addressed, we would be grateful if you’d consider updating your evaluation. We are happy to continue the discussion if further questions arise. Thank you again for your thoughtful and constructive review.\n\n### W1: How does BraVE handle continuous state spaces?\n\nBraVE handles continuous state spaces naturally and does not require building infinitely many trees. As described in Section 3.1, the tree is defined over the **discrete action space**, not the state space. The network $f(\\theta)$ takes a state $s$ (which may be discrete or continuous) as input and returns Q-values and branch values over the action tree for that specific $s$. Generalization to similar states is achieved through the function approximation capacity of the neural network, as is standard in deep RL. To select an action for any given input state, BraVE performs a single tree traversal guided by the network's outputs for that state. No state binning or discretization is required. We have added the following clarification to Section 3.1:\n\n> At a node $\\mathbf{a}\\_\\text{node}$, the network receives as input the current state $s$, which may be discrete or continuous, and the $N$-dimensional action vector corresponding to $\\mathbf{a}\\_\\text{node}$.\n\n### W2: How does BraVE ensure accurate estimates for unchosen subtrees?\n\nBraVE does not explicitly ensure the accuracy of unchosen subtrees during a single action-selection pass. Instead, accurate estimates emerge over time as the model is optimized. Over the course of training, BraVE receives supervision across the tree via sampled actions from the offline dataset. The $L_{\\text{BraVE}}$ loss (Algorithm 1, Figure 3) propagates value targets upward from sampled actions, so that with sufficient coverage, all relevant nodes and branches receive learning signals. This is analogous to how DQN learns Q-values for actions not selected in a single step, but through repeated sampling over time.\n\n### W3: Sensitivity to estimation errors at different tree depths\n\nYou are correct that estimation errors — particularly those near the root of the tree — can have a disproportionate impact on downstream decision-making. To mitigate this, we proposed two complementary mechanisms which are described in Section 3.5. First, we apply a depth penalty $\\delta$, which increases the training signal for nodes closer to the root. This prioritizes the correction of early-stage errors, which influence a larger portion of the tree. Second, at inference time, we use beam search to explore multiple promising paths simultaneously rather than committing to a single greedy trajectory. This improves robustness to local estimation errors and guides more accurate action selection. The impact of these mechanisms is analyzed in our ablation studies (Appendix D); we have also expanded the main text to summarize the key findings.\n\n### W4: Experimental diversity\n\nOur focus is on introducing and isolating the algorithmic contribution of BraVE — a method designed to address complex sub-action dependencies — in environments that exhibit these structures clearly and controllably. We constructed CoNE specifically for this purpose. In many existing benchmarks (e.g., discretized continuous control), sub-action dependencies are weak or absent [1]. Consequently, they are ill-suited for validating the specific challenge BraVE targets.\n\n### W5: Why does IQL perform reasonably well despite the large action space?\n\nIQL's relative success, though still significantly outperformed by BraVE (typically by a factor of $2-5\\times$), is not entirely surprising. As a strong, general-purpose offline RL algorithm, it makes no structural assumptions and can, in principle, represent any Q-function — unlike factorization-based methods such as FAS. However, this generality comes at a significant cost in modeling complexity, as we detail in Appendix A. BraVE’s tree and sparsification introduce structure and inductive bias that improves efficiency and scalability by guiding learning toward plausible and high-value regions of the action space.\n\n### W6: Tree traversal relies on a fixed predefined ordering of sub-action dimensions\n\nTo assess BraVE’s robustness to the ordering of sub-action dimensions, **we have conducted a new experiment as follows**.\n\nWe trained BraVE, FAS, and IQL using five different randomly permuted action orderings in the 8-D, 50% pit CoNE setting, which is empirically the most challenging 8-D variant. The results are shown below:\n\n|        BraVE       |          FAS         |         IQL        |\n| :----------------: | :------------------: | :----------------: |\n| $-53.5 \\pm 29.1$ | $-1103.6 \\pm 51.4$ | $-96.2 \\pm 51.8$ |\n\n\nThese findings are consistent with those originally reported in Table 2, showing that BraVE outperforms FAS by an order of magnitude and is roughly twice as effective as IQL. This demonstrates that BraVE’s performance is robust to the ordering of sub-action dimensions and not dependent on a favorable arrangement. We have added this analysis to Section 4.3.\n\n### Q1: Can this framework support softmax (stochastic) action selection?\n\nYes — in principle, the tree traversal framework could be adapted to support stochastic policies via softmax selection. Instead of choosing the maximal branch value at each node, one could sample branches according to a softmax over the $\\mathbf{v}$ values (e.g., $\\text{softmax}(\\mathbf{v} / \\tau)$ for temperature $\\tau$). This results in a stochastic policy over joint actions. In turn, the Bellman target would shift from using $\\max_{\\mathbf{a}'} Q(s', \\mathbf{a}')$ to an expectation under this stochastic policy, effectively turning the update into a soft Q-learning or expected SARSA-style rule.\n\nThis would require some modifications to both inference and learning but is entirely compatible with the tree framework. Designing a full actor-critic variant with a parameterized policy is another promising direction for future work. Thank you for the suggestion.\n\n[1] Beeson et al. An investigation of offline reinforcement learning in factorisable action spaces (2024).\n\n[2] Tang et al. Leveraging factored action spaces for efficient offline reinforcement learning in healthcare (2022)."}]

Author rebuttal:

Meta-review: After some extensive discussion with the authors, the reviewers converged on a positive assessment of the paper. There were no concerns raised about the ability of the authors to modify their paper to incorporate lessons learned from the discussion, so my meta-review is positive.

One suggestion for the authors: While your focus is on combinatorial actions, it still might be appropriate to review some of the work on continuous actions since the techniques are not so different and could be applied to combinatorial domains with little or no modification. See, for example, the work of Jason Pazis, which explored both tree in a Q-learning setting, and other methods of splitting the action space in the case of approximate linear programming. (Please note, this is not a complaint or accusation that your work is not original, but genuinely meant as something you might find interesting if you haven’t already explored it.)
Decision: Accept (poster)