Research map / Reinforcement learning / Visual and representation RL
In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search
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 Broccoli, a backtracking search that enumerates discretised decision-tree policies for deterministic black-box environments and uses trace-based pruning to find size-minimal optimal tree policies.
Problem
Synthesising small, interpretable decision-tree control policies for deterministic black-box systems with black-box specifications, with optimality guarantees, where prior methods need expert policies, RL, or explicit environment models.
Approach
A backtracking search over decision-tree shapes and discretised predicates, where a per-node distance value from observed traces lets the search skip predicate thresholds that would provably yield an already-seen trace (trace-based pruning), combined with early stopping and symmetry pruning.
Key results
- Trace-based pruning reduces runtime by one to two orders of magnitude on CartPole (3.13s to 0.22s) and MountainCar (4.72s to 0.21s) for a single initial state, and about 4x on Pendulum (13.75s to 3.19s).
- With 100 initial states, runtime grows sub-linearly; for example CartPole rises from 0.22s to 1.28s with pruning.
- Runtime grows exponentially with the number of predicates per dimension and with the number of predicate nodes (e.g., Pendulum N=6 takes 5.36s with 826k trees).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add trace-based pruning (ablation) | Broccoli · CartPole, 1 initial state | runtime (seconds): 3.13 -> 0.22 | Helped |
| add trace-based pruning (ablation) | Broccoli · MountainCar, 1 initial state | runtime (seconds): 4.72 -> 0.21 | Helped |
| add trace-based pruning (ablation) | Broccoli · Pendulum, 1 initial state | runtime (seconds): 13.75 -> 3.19 | Helped |
| add trace-based pruning (ablation) | Broccoli · CartPole, 100 initial states | runtime (seconds): 7.46 -> 1.28 | Helped |
| add trace-based pruning (ablation) | Broccoli · MountainCar, 100 initial states | runtime (seconds): 6.55 -> 0.40 | Helped |
| add trace-based pruning (ablation) | Broccoli · Pendulum, 100 initial states | runtime (seconds): 131.4 -> 23.93 | Helped |
| increase predicate granularity from X=5 to X=20 (ablation) | Broccoli · CartPole | runtime (seconds): 102 -> 287 | Mixed |
| increase predicate granularity from X=5 to X=20 (ablation) | Broccoli · MountainCar | runtime (seconds): 6.26 -> 446 | Hurt |
| increase predicate granularity from X=5 to X=20 (ablation) | Broccoli · Pendulum | runtime (seconds): 6.58 -> 366 | Hurt |
| increase maximum predicate nodes from N=3 to N=6 (ablation) | Broccoli · CartPole | runtime (seconds): 0.1 -> 39.92 | Hurt |
| increase maximum predicate nodes from N=3 to N=6 (ablation) | Broccoli · MountainCar | runtime (seconds): 0.12 -> 14.1 | Hurt |
| increase maximum predicate nodes from N=3 to N=6 (ablation) | Broccoli · Pendulum | runtime (seconds): 0.3 -> 5.36 | Hurt |
Surprising findings
- On CartPole, finer predicate discretisation sometimes decreased runtime because a perfect balancing tree was found sooner.
Limitations
- Exponential runtime in tree size and predicate granularity; infeasible for large trees or high-dimensional environments.
- Restricted to deterministic environments with discrete actions; continuous actions need discretisation.
- No direct comparison to other tree-synthesis methods because the setting differs.
Experimental setup
Datasets: Gymnasium CartPole Gymnasium MountainCar Gymnasium Pendulum
Benchmarks: CartPole MountainCar Pendulum
Metrics: runtime (seconds) number of trees explored runtime variance across initial states
Baselines: search without trace-based pruning
Builds on: Stratego mixed-integer linear programming policy synthesis
Closest papers by meaning
- SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes (NeurIPS 2025 · similarity 0.90)
- Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization (ICLR 2025 · similarity 0.88)
- Subgoal-Guided Policy Heuristic Search with Learned Subgoals (ICML 2025 · similarity 0.87)
- Generative Model for Decision Trees (AAAI 2024 · similarity 0.86)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.86)
- A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees (AAAI 2024 · similarity 0.85)
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.