Research map / Reinforcement learning / MDPs and planning
A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees
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 LCEOPT, an online POMDP solver that runs a lazy cross-entropy search over finite-depth policy trees whose nodes hold continuous actions, avoiding action-space partitioning.
Problem
Online planning in POMDPs with continuous and high-dimensional action spaces, where MCTS-based solvers with action-space partitioning scale poorly.
Approach
Represents policies as fixed-depth policy trees parameterized by node actions and runs a Cross-Entropy search over those parameters with a lazy scheme that samples only the action components actually visited during Monte Carlo rollouts, with a marginal-likelihood update over partial (incomplete) parameter vectors.
Key results
- LCEOPT achieves 832.1 on SensorPlacement-12 versus 456.8 for the best baseline ADVT, and beats all baselines on every problem except ContTag.
- On SensorPlacement-12 with M=5, lazy sampling takes 5.13 s versus 3928.45 s for the basic method to reach 50 CE-iterations, up to roughly two orders of magnitude savings.
- On ContTag, ADVT (0.37) slightly outperforms LCEOPT (0.02).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · ContTag | average total discounted reward: 0.37 -> 0.02 | Hurt |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · Pushbox2D | average total discounted reward: 356.9 -> 399.7 | Helped |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · Pushbox3D | average total discounted reward: 327.8 -> 358.6 | Helped |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · Parking2D | average total discounted reward: 43.1 -> 53.4 | Helped |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · Parking3D | average total discounted reward: 34.6 -> 47.2 | Helped |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · SensorPlacement-6 | average total discounted reward: 859.2 -> 914.3 | Helped |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · SensorPlacement-8 | average total discounted reward: 794.1 -> 885.5 | Helped |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · SensorPlacement-10 | average total discounted reward: 631.4 -> 858.8 | Helped |
| Use LCEOPT instead of ADVT | continuous-action POMDP solver · SensorPlacement-12 | average total discounted reward: 456.8 -> 832.1 | Helped |
| Use lazy rather than basic policy sampling (ablation) | LCEOPT · SensorPlacement-12, policy-tree depths M=1 to M=5 | CPU time for 50 CE-iterations: 2.65 -> 1.09; 12.61 -> 1.58; 137.56 -> 2.2; 900.97 -> 3.07; 3928.45 -> 5.13 | Helped |
| Use lazy rather than basic policy sampling (ablation) | LCEOPT · ContTag, policy-tree depths M=1 to M=5 | CPU time for 50 CE-iterations: 0.43 -> 0.43; 0.64 -> 0.64; 0.91 -> 0.90; 1.23 -> 1.19; 1.57 -> 1.39 | Helped |
| Use lazy rather than basic policy sampling (ablation) | LCEOPT · ContTag | average total discounted reward: -0.11 -> 0.15 | No clear effect |
Surprising findings
- Lazy and basic sampling give similar rewards despite different distribution update rules, and on ContTag the basic method is comparable at shallow depths.
Limitations
- Restricted to discrete observation spaces; continuous observations left to future work.
- Policy tree size grows exponentially with depth, and the effective horizon is short (2 steps for many problems) because of heuristic leaf values.
- Designed for problems with a fixed-size policy parameterization; ContTag is slightly outperformed by ADVT.
Experimental setup
Datasets: ContTag Pushbox2D Pushbox3D Parking2D Parking3D SensorPlacement-6 SensorPlacement-8 SensorPlacement-10 SensorPlacement-12
Benchmarks: ContTag Pushbox2D Pushbox3D Parking2D Parking3D SensorPlacement-6 SensorPlacement-8 SensorPlacement-10 SensorPlacement-12
Metrics: average total discounted reward 95% confidence interval CPU time per 50 CE-iterations
Baselines: POMCPOW VOMCPOW ADVT
Builds on: Cross-Entropy method POMCPOW ADVT OPPT
Closest papers by meaning
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.89)
- SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes (NeurIPS 2025 · similarity 0.89)
- Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach (AAAI 2025 · similarity 0.88)
- A Policy Gradient Method for Confounded POMDPs (ICLR 2024 · similarity 0.88)
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.87)
- Scalable Policy-Based RL Algorithms for POMDPs (NeurIPS 2025 · similarity 0.87)
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.