# Improved Monte Carlo Planning via Causal Disentanglement for Structurally-Decomposed Markov Decision Processes

arXiv: https://arxiv.org/abs/2406.16151 · HTML: https://mlsanity.com/paper/2406.16151/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 39 references that are in the map.
- First posted on arXiv 23 Jun 2024.

## Builds on (most cited first, 5 of 5)

- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [On Causally Disentangled Representations](https://mlsanity.com/paper/2112.05746/) (2021)
- [Invariant Causal Imitation Learning for Generalizable Policies](https://mlsanity.com/paper/2311.01489/) (2023)
- [Monte Carlo Tree Search with Boltzmann Exploration](https://mlsanity.com/paper/2404.07732/) (2024)

## Abstract (arXiv)

Markov Decision Processes (MDPs), as a general-purpose framework, often overlook the benefits of incorporating the causal structure of the transition and reward dynamics. For a subclass of resource allocation problems, we introduce the Structurally Decomposed MDP (SD-MDP), which leverages causal disentanglement to partition an MDP's temporal causal graph into independent components. By exploiting this disentanglement, SD-MDP enables dimensionality reduction and computational efficiency gains in optimal value function estimation. We reduce the sequential optimization problem to a fractional knapsack problem with log-linear complexity O(T log T), outperforming traditional stochastic programming methods that exhibit polynomial complexity with respect to the time horizon T. Additionally, SD-MDP's computational advantages are independent of state-action space size, making it viable for high-dimensional spaces. Furthermore, our approach integrates seamlessly with Monte Carlo Tree Search (MCTS), achieving higher expected rewards under constrained simulation budgets while providing a vanishing simple regret bound. Empirical results demonstrate superior policy performance over benchmarks across various logistics and finance domains.