mlsanityData to 7 Oct 2026

Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction

arXiv 2406.00614 ↗First posted 2 Jun 2024cs.LG cs.AIcited by 6

Not on the map. Why?

Abstract (arXiv)

Monte Carlo Tree Search (MCTS) has showcased its efficacy across a broad spectrum of decision-making problems. However, its performance often degrades under vast combinatorial action space, especially where an action is composed of multiple sub-actions. In this work, we propose an action abstraction based on the compositional structure between a state and sub-actions for improving the efficiency of MCTS under a factored action space. Our method learns a latent dynamics model with an auxiliary network that captures sub-actions relevant to the transition on the current state, which we call state-conditioned action abstraction. Notably, it infers such compositional relationships from high-dimensional observations without the known environment model. During the tree traversal, our method constructs the state-conditioned action abstraction for each node on-the-fly, reducing the search space by discarding the exploration of redundant sub-actions. Experimental results demonstrate the superior sample efficiency of our method compared to vanilla MuZero, which suffers from expansive action space.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 18 of its 44 references that are in the map. First posted on arXiv 2 Jun 2024.

Builds on

18 of 44 references.

References · 18

  1. 2016Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localizationcited by 6,690
  2. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  3. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,135
  4. 2021Deep Reinforcement Learning at the Edge of the Statistical Precipicecited by 781
  5. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 424
  6. 2021Mastering Atari Games with Limited Datacited by 235
  7. 2021Online and Offline Reinforcement Learning by Planning with a Learned Modelcited by 90
  8. 2020Monte-Carlo Tree Search as Regularized Policy Optimizationcited by 59
  9. 2021Vector Quantized Models for Planningcited by 47
  10. 2013Context-Specific Independence in Bayesian Networkscited by 43
  11. 2023Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcarecited by 41
  12. 2020CAMPs: Learning Context-Specific Abstractions for Efficient Planning in Factored MDPscited by 18
6 more
  1. 2021Reinforcement Learning in Factored Action Spaces using Tensor Decompositionscited by 6
  2. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  3. 2023Adaptive Discretization using Voronoi Trees for Continuous POMDPscited by 6
  4. 2024On Discovery of Local Independence over Continuous Variables via Neural Contextual Decompositioncited by 4
  5. 2022GrASP: Gradient-Based Affordance Selection for Planningcited by 2
  6. 2022Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playingcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 1.

6 papers.

  1. 2025STORM: Search-Guided Generative World Models for Robotic Manipulationcited by 7
  2. 2025MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planningcited by 5
  3. 2026NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Searchcited by 4
  4. 2025AUPO -- Abstracted Until Proven Otherwise: A Reward Distribution Based Abstraction Algorithmcited by 3
  5. 2025Investigating Intra-Abstraction Policies For Non-exact Abstraction Algorithmscited by 2
  6. 2025Discovering State Equivalences in UCT Search Trees By Action Pruningcited by 0