Research map / Reinforcement learning / MDPs and planning

SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes

NeurIPS 2025 · Reinforcement learning › MDPs and planning · approach: Average-reward and regularized MDPs · 0 citations (OpenAlex)

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 SPOT, a policy-iteration framework that solves each improvement step as a decision-tree MILP using reduced-space branch-and-bound with parallel search, yielding faster optimal decision tree policies for MDPs than OMDT.

Problem

Optimizing decision tree policies in MDPs is combinatorial and NP-hard; exact MILP formulations (OMDT) do not scale to MDPs with many states.

Approach

Decompose the tree-policy MDP optimization into per-iteration policy-improvement subproblems (value-iteration/policy-iteration style), and solve each via a reduced-space branch-and-bound that branches only on tree-structure variables, with a closed-form decomposable upper bound and parallel evaluation.

Key results

• On the depth-3 benchmarks, SPOT+WS improves normalized return over OMDT (60 min) by 1201.7% on firewire and 505.95% on csma_2_2 under a 60-minute budget.
• On firewire with depth 3, parallel RSBB takes 15.91 s versus 11,528.12 s for direct Gurobi; on csma_2_4 Gurobi exceeds the 14,800 s limit while parallel RSBB finishes in 42.568 s.
• Vanilla SPOT underperforms OMDT on some instances, e.g., csma_2_2 (-49.5%) and firewire (-120.5%) at depth 3 with 60 minutes.

Measured effects reported in the paper

Surprising findings

• Vanilla SPOT is worse than OMDT on several depth-3 instances (e.g., firewire, csma_2_2), so gains depend on the warm start from OMDT.
• Reported gains on some instances (e.g., csma_2_2 and firewire) are computed relative to very small or negative OMDT baselines, inflating percentages.

Limitations

• Performance relies on the efficiency of the underlying optimization solver and may limit scalability to very large MDPs.
• Vanilla SPOT is not consistently better than OMDT; the warm start from OMDT is needed for the largest gains.
• Convergence to global optimum claims rely on finite-tree arguments and borrowed results from prior stochastic programming literature, with the proofs sketched.

Experimental setup

Datasets: sys_ad_1 sys_ad_2 tic_vs_ran tiger_vs_ant csma_2_2 csma_2_4 firewire wlan0 wlan1

Benchmarks: sys_ad_1 sys_ad_2 tic_vs_ran tiger_vs_ant csma_2_2 csma_2_4 firewire wlan0 wlan1

Metrics: normalized return runtime (s) gain (%) relative to OMDT

Baselines: OMDT Gurobi MILP solver VIPER

Builds on: OMDT value iteration policy iteration VIPER

Closest papers by meaning

• In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search (AAAI 2025 · similarity 0.90)
• A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees (AAAI 2024 · similarity 0.89)
• Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization (ICLR 2025 · similarity 0.88)
• Tree Search-Based Policy Optimization under Stochastic Execution Delay (ICLR 2024 · similarity 0.87)
• Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.87)
• Model-Based Exploration in Monitored Markov Decision Processes (ICML 2025 · similarity 0.86)