Research map / Reinforcement learning / Offline RL
BraVE: Offline Reinforcement Learning for Discrete Combinatorial Action Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BraVE, an offline value-based RL method that traverses a tree over a combinatorial discrete action space guided by a Q-network with branch values, and is evaluated on the CoNE grid-navigation benchmark against FAS and IQL.
Problem
Offline RL in high-dimensional discrete combinatorial action spaces, where the joint action space grows exponentially with sub-action count and exhaustive Q-maximization is intractable, while factorized Q-functions cannot capture sub-action dependencies.
Approach
Impose an N-level tree over joint actions and use a single MLP that outputs a node Q-value and branch values, so greedy traversal evaluates O(N) joint actions while keeping full joint-action Q-values; training uses a behavior-regularized TD loss plus a recursive branch-value propagation loss up the tree, with tree sparsification to dataset-observed actions.
Key results
- In an 8-D CoNE setting with 50% pits, BraVE achieves -53.5 ± 29.1 return versus -1103.6 for FAS and -96.2 for IQL under permuted action orderings.
- With non-factorizable rewards and no sub-action dependencies at ~4M actions, BraVE reaches -18.6 ± 8.3 return versus -33.9 for FAS and -66.9 for IQL.
- Normalized episode-length score in the 8-D 50%-pit setting: BraVE 71.4 versus FAS 0.0 and IQL 40.6.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BraVE instead of FAS | Offline RL on CoNE with non-factorizable rewards · CoNE, increasing action-space sizes | average return: -10.8 ± 2.3 vs -3.4 ± 0.1; -33.9 ± 27.0 vs -18.6 ± 8.3 | Helped |
| Use BraVE instead of IQL | Offline RL on CoNE with non-factorizable rewards · CoNE, increasing action-space sizes | average return: -66.9 ± 31.6 vs -18.6 ± 8.3 | Helped |
| Use BraVE instead of FAS | Offline RL on 8-D CoNE with hazardous transitions · 8-D CoNE, 50% pits | average return: -902.6 ± 274.1 vs -54.8 ± 47.9 | Helped |
| Use BraVE instead of IQL | Offline RL on 8-D CoNE with hazardous transitions · 8-D CoNE, 50% pits | average return: -106.4 ± 42.8 vs -54.8 ± 47.9 | Helped |
| Use BraVE instead of FAS | Offline RL on CoNE with five hazardous states · CoNE, 25 states | average return: -531.5 ± 31.4 vs -7.5 ± 2.4 | Helped |
| Randomize the sub-action dimension ordering | BraVE · 8-D CoNE, 50% pits, five permutations | average return | No clear effect |
| Add a small depth penalty (δ=1) to the BraVE loss (ablation) | BraVE · CoNE five-pit environments | average return | Helped |
| Set the TD-loss weight to α=0, omitting the TD term (ablation) | BraVE · CoNE, especially higher-dimensional tasks | average return | Hurt |
| Replace tree-based action selection and branch value propagation with dataset-constrained DQN (ablation) | BraVE · CoNE, including 11-D | policy effectiveness | Hurt |
| Use beam width 10 instead of larger beams (ablation) | BraVE inference · CoNE five-pit environments | average return | Helped |
| Increase beam width beyond 10 (ablation) | BraVE inference · CoNE five-pit environments | average return | Hurt |
| Use a wider beam (ablation) | BraVE inference · CoNE five-pit environments | inference time | No clear effect |
Surprising findings
- FAS collapses to a random-policy level (normalized score 0) once pits cover half the interior states in the 8-D setting.
- A DQN restricted to dataset actions with the same behavior-regularized loss fails to learn a viable policy, indicating the tree structure is critical.
Limitations
- Tree ordering of sub-action dimensions is fixed; robustness shown only via random permutations in CoNE.
- Evaluation confined to the synthetic CoNE benchmark with no real-world tasks.
- Training cost is higher due to recursive branch-value propagation up all ancestors; online learning not addressed.
Experimental setup
Datasets: CoNE offline datasets generated with stochastic A*
Benchmarks: CoNE
Metrics: average return normalized episode-length score
Baselines: Factored Action Spaces (FAS) Implicit Q-Learning (IQL) DQN
Builds on: TD3+BC implicit Q-learning BCQ factored action spaces
Closest papers by meaning
- A Clean Slate for Offline Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Exploiting Action Impact Regularity and Exogenous State Variables for Offline Reinforcement Learning (Abstract Reprint) (AAAI 2024 · similarity 0.87)
- Reinforcement Learning with Action Chunking (NeurIPS 2025 · similarity 0.87)
- Flow Matching for Offline Reinforcement Learning with Discrete Actions (NeurIPS 2026 · similarity 0.87)
- Dynamic Neighborhood Construction for Structured Large Discrete Action Spaces (ICLR 2024 · similarity 0.87)
- Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.