Research map / Learning theory and algorithms / Sample complexity
Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TrailBlazer (adaptive tree-based sampling that refines only a few paths and forgets extra samples after MAX-node choice) instead of uniform/UCT-style sampling | Monte-Carlo planning with generative model · MDPs with finite N next states | sample complexity exponent of 1/epsilon | Helped |
| Use TrailBlazer in MDPs with infinite next states (N = ∞) when the problem-difficulty measure d is zero (non-vanishing action gaps) | TrailBlazer · MDPs with N = ∞ | sample complexity order in 1/epsilon | Helped |
| Apply TrailBlazer in the evaluation case without control (K = 1) | TrailBlazer · MDPs with K = 1 (Monte-Carlo evaluation) | sample complexity order | No clear effect |
| Replace the sampled-node history with only the first m samples (forgetting extra AVG samples drawn due to MAX nodes) | TrailBlazer AVG nodes · theoretical design | sample complexity | Helped |
Closest papers by meaning
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.88)
- Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning (NeurIPS 2026 · similarity 0.87)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.87)
- Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts (NeurIPS 2026 · similarity 0.87)
- Power Mean Estimation in Stochastic Continuous Monte-Carlo Tree Search (ICML 2025 · similarity 0.87)
- Sequential Monte Carlo for Policy Optimization in Continuous 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.